I don't understand the relantioship between parsing tree and derivation. The parsing tree is invariant with respect to the derivation, but does this mean that regardless of the derivation (rightmost or leftmost) the parsing tree remains the same? Or according to the method (rightmost or leftmost) does the parsing tree change? Pls help me Sorry for my bad english.
Parsing Tree and Derivation?
362 Views Asked by xXMarcoXx At
1
There are 1 best solutions below
Related Questions in PARSING
- TypeScript: Type checking while parsing an arbitrary JSON that is typed/
- How to have fixed options using Option.Applicative in haskell?
- How to convert mathematical expression to lambda function in C++?
- JsonObject throws an exception: JSONObject["employer_website"] is not a string (class org.json.JSONObject$Null : null)
- Trying to fix my c++ code for it to read the right amount of nodes from a file
- Selenium get page after "loading" page
- Parse tag in html via Google Sheets (importxml)
- FluentD / Fluent-Bit: Concatenate multiple lines of log files and generate one JSON record for all key-value from each line
- Editing non-String values in JComboBox
- Handling multiple errors in Bison parser
- Which is the most idiomatic way to parse an i32 from ascii in Rust
- I got this error from a JSON Validator - what does this mean?
- Conflict between lexer rules in ANTLR4 for Fortran grammar
- mqtt message parsing problem in a node.js
- How to print error code from URL response in swift
Related Questions in TREE
- Python - how to make tree without any library
- how to get the full path of antd tree
- Python Quadtree won't insert values
- Top View Of Binary Tree Depth First Search Using TreeMap
- Select/filter tree structure in postgres
- PySimpleGUI tree doesn't Insert data into tree
- Is it possible to create a node-link diagram with ggplot?
- Represent a full, but not complete, binary tree with an array structure
- Redirecting stdout with execvp
- Prevent selected node to be unselect primevue Tree component
- Binary Search Tree (BST) - array representations
- Debugging AVL Tree Deletion: Unbalanced Node Not on Deletion Path
- How to shorten line length in react-d3-tree
- installed dm-tree vs imported tree
- Why the height of segment tree is O(logn)
Related Questions in COMPILER-CONSTRUCTION
- Reference: Crafting Interpreters. Print statement is not able to evaluate expression. Help me fix this (details below)
- Load function written in amd64 assembly into memory and call it
- I have implemented till Statements and State in Tree Walk Interpreter. I am pissed with an error
- Resolve shift/reduction conflict in grammar for expressions in PLY for calls to embedded functions
- Grammar for access to properties and calls to embedded functions
- LLVM code generation causes problems with pointer arithmetic
- what does react compiler mean actually?
- Errors on Recursive Descent Parsing Java
- Java CUP produces Shift-Reduce conflict when parsing a grammar for a C++ type language
- Three-Address-Code (TAC) and Conjunction/Disjunction
- How do I write an implicit cast for my strongly typed interpreter? (C++)
- Yacc parser not reducing specific production rules as intended
- Why is the function version tag consistently "Base" in HDF5 library?
- Sly parser, how are recursively defined types implemented?
- Does a non terminal token need an explicit definition?
Related Questions in GENERIC-DERIVATION
- scala 3 get field types of case class
- Tuples in Scala 3 Compiler Operations for Typeclass Derivation
- How to access method valueOf of an unknown enum in Scala 3
- Shapeless - How to derive LabelledGeneric for Coproduct
- Scala how to derivate a type class on a trait
- How to derive a Generic.Aux if the case class has a type parameter - Shapeless
- How to Decode a Generic Case Class with semiautomatic in Circe in Scala 3
- Parsing Tree and Derivation?
- Year on year growth rates for multiple columns basis unique ID & years in rows
- Scala 3 Method Too large when using Mirror
- Scala typeclass for providing an instance either from derivation or from an existing implicit value
- Cats auto derived with Seq
- Cannot Serialise a Map with Sealed Trait as Key Type
- Is it possible to have a sub-trait inheirit a class parameter from another trait?
- Type Class Derivation accessing default values
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
The parse tree is a record of the derivation. Each non-leaf node of the tree is the result of a single derivation step.
At the root of the parse tree and at the beginning of the derivation, you find the grammar's start symbol. A derivation step replaces a non-terminal with the right-hand side of some production which has that non-terminal on the left-hand side. In the tree, the node corresponding to the non-terminal is given a sequence of children, each one a symbol in the right-hand side of the production. Terminal symbols become leaf nodes and non-terminals will eventually become the top of a subtree.
If the grammar is unambiguous, there is only one parse tree for each derivable sentence. But that parse tree represents a large number of possible derivations, unless the grammar is linear (that is, the right-hand side of every production contains at most one non-terminal). In a derivation which is being built, you can select any non-terminal for the next derivation step; in the parse tree, you can select any node representing a non-terminal which does not yet have children.
The leftmost and rightmost derivations are just two of these many possibilities. (Again, unless the grammar is linear, in which case the leftmost and rightmost derivations are the same derivation.) But a derivation doesn't have to be leftmost or rightmost. At each step, it can choose any non-terminal, not only the leftmost or rightmost one. In the tree representation, a possible derivation can be generated by any valid topological sort of the nodes.
But that doesn't matter in practical terms. The only useful practical question is whether there is more than one different parse tree for each sentence in the grammar, which is exactly the same as asking whether there is more than one leftmost derivation or more than one rightmost derivation.