Elimination of left recursion and left factoring the grammars
https://www.youtube.com/watch?v=3_VCoBfrt9c
Tool for grammars
http://smlweb.cpsc.ucalgary.ca/start.html
Grammars
http://faculty.ycp.edu/~dhovemey/fall2010/cs340/lecture/lecture9.html
- Does followset follow the left-recursive grammar?
- Does parseTable follow the left-recursive grammar?
Note that the way that you deal with left recursion in an LL grammar is essentially by converting to right recursion and then post-processing the parse tree to turn it back into left recursion. Breaking it down, you convert to
- Only Left Factoring needs to be handled. No Left Recursion.
S -> A |B |C |D |F. A -> a t | a u | a v | . B ->b |. C -> c |. D -> d |. F -> f | .
First and Follow sets are needed for parse tables. There are a couple ways to check if a grammar is an LL(1) grammar, a unique parse table is one way. And not all grammars are LL(1) grammars, so if your input grammar is not LL(1) parsable you cannot proceed.
This shows the example that I should use left factored production.
https://web.stanford.edu/class/cs143/lectures/lecture07.pdf
- First set need to give references to non-terminals.
RHYME -> SOUND PLACE | PING. SOUND -> ding dong. PLACE -> dell. PING -> pong.
S -> A B C D F. A -> a |. B -> b |. C -> c. D -> d|. F -> f|.
S -> A B C D F.
A -> a t | a u | a v |.
B -> b |.
C -> c.
D -> d |.
F -> f |.
E -> i E' E' -> + iE' | e
- Top down parser.
E() { if (l == 'i') { match('i'); E'(); } } l = getchar();
Other function.
E'() { if ( l == '+') { match('+'); match('i'); E'(); } else return; }
function match.
match(char t) { if (l == t) { l = getchar(); else printf("error"); }
main program.
main() { E(); if( l == "$") printf("parsing success"); }
- Operator Precedence Parser.
- Operator Grammar.
Operator Grammar.
E -> E + E | E * E | id
- There should not be two variables that are adjacent.
- Operation Relation Table.
- It is a bottom up parsing.
In order to decrease the size of the operator precedence table, we go for operator function table.
- Error detecting capability of function table is going to be lesser than Error detecting capability of relation table.
- Canonical collection of LR(0) items.
- Canonical collection of LR(1) items.
S -> AA A -> aA | b
S' -> S S -> AA1 A -> aA | b
- Accepting state.
- LR(0)
- SLR(1)
S -> dA | aB A -> bA | C B -> bB | C
Figure out if the grammar is
- LL(1)
- LR(0)
- SLR(1)
E -> E + T | T T -> T F | F F -> F * | a | b
- LR (1) Item = LR(0) items + look ahead.