Convert the grammar to program
Parsing based on grammar
Steps for parsing
- Write a simple grammar
-
Refine the grammar
- Eliminate ambiguity. (If grammar leads to more than one parse tree for string then its ambiguous)
- Ambiguity can be eliminated by adding left or right association rules, precedence rules.
- Left association is achieved by left recursion.
- Right association by right recursion.
- Higher precedence is added by expanding the symbol later in the grammar.
- Ambiguity can be eliminated by adding left or right association rules, precedence rules.
- Top down paring doesn’t allow left recursion. To eliminate the left recursion use below formula.
- Eliminate common prefixes (left factoring) or non deterministic grammar.
- Eliminate ambiguity. (If grammar leads to more than one parse tree for string then its ambiguous)
Formula to eliminate lefte recursion
Simple formula
Strings generated: βα*
A -> Aα|β
A -> βA'
A'-> αA'|ε
Generic formula
A -> Aα₁|Aα₂|Aα₃...|β₁|β₂|β₃
A -> β₁A'|β₂A'|β₃A'...
A'-> A'α₁|A'α₂|A'α₃...|ε
Left factoring formula
A'-> αA'
Ambiguous grammar examples
S->aS/Sa/a
S->aSbS/bSaS/ε
R->R+R/R*R/R*/a/b/c
Left recursive grammar exmaples
E->E+F|F
F->F*T|T
T->a|b|c
Non deterministic grammar examples
The α symbol is repeating, so we can’t decide until which rule to apply until we check the next symbol (β₁β₂,β₃)
A -> αβ₁|αβ₂|αβ₃
To eliminate non deterministic (left factoring)
A -> αA'
A'-> β₁|β₂|β₃