Lectures from youtube¶
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
Improvements¶
First set need to give references to non-terminals.
Test 1¶
RHYME -> SOUND PLACE
| PING.
SOUND -> ding dong.
PLACE -> dell.
PING -> pong.
Test 2¶
S -> A B C D F.
A -> a |.
B -> b |.
C -> c.
D -> d|.
F -> f|.
Test 3¶
S -> A B C D F.
A -> a t | a u | a v |.
B -> b |.
C -> c.
D -> d |.
F -> f |.
Recursive Descent Parsers¶
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 grammar and Operator precedence parser¶
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.
LR parsing, LR(0) items and LR(0) parsing table¶
Canonical collection of LR(0) items.
Canonical collection of LR(1) items.
S -> AA
A -> aA | b
LL(0) Parsing example and SLR(1) table¶
S' -> S
S -> AA1
A -> aA | b
Accepting state.
LR(0)
SLR(1)
Examples of LR(0) and SLR(1)¶
S -> dA | aB
A -> bA | C
B -> bB | C
Figure out if the grammar is
LL(1)
LR(0)
SLR(1)
Examples of LR(0) and SLR(1)¶
E -> E + T | T
T -> T F | F
F -> F * | a | b
CLR(1) and LALR(1) Parsers¶
LR (1) Item = LR(0) items + look ahead.