A parse tree is a diagrammatic representation of the parsed structure of a sentence or string.
In the syntax analysis phase, a compiler verifies whether or not the tokens generated by the lexical analyzer are grouped according to the syntactic rules of the language. This is done by parse tree.
Than from parse tree intermediate code can be generated.
A parse tree for a grammar G is a tree where
- The root is the start symbol for G
- The interior nodes are the nonterminals of G
- The leaf nodes are the terminal symbols of G.
- The children of a node T (from left to right) correspond to the symbols on the right hand side of some production for T in G.
Ambiguous grammar:
A grammar that produces more than one parse tree for some sentence is said to be ambiguous.
There are two ways to draw a parse tree:
1. Top-down Approach:
- Starts with the starting symbol S
- Goes down to tree leaves
2. Bottom-up Approach:
- Starts from tree leaves
- Proceeds upward to the starting symbol S
Leftmost and Rightmost Derivation of a String:
1.Leftmost derivation:
A leftmost derivation is obtained by applying production to the leftmost variable in each step.
For example, S –> a+b*c
2. Rightmost derivation:
A rightmost derivation is obtained by applying production to the rightmost variable in each step.
For example, S –> a+b*c
