a) Build the LR(0) DFA for this grammar:
S → E eof E → id E → id (E) E → E + id
b) Is this an LR(0) grammar? Give evidence.
c) Is this an SLR grammar? Give evidence.
d) Is this an LR(1) grammar? Give evidence.
Solution:
b) This is not an LR(0) grammar: when parsing the string “id(”, in state q1 we can either reduce “E → id.” or we can shift “(” and go to q2.
c) An SLR parser uses follow sets, let's compute them:
The conflict at node q1 is resolved because we can reduce “E → id.” only if , which is not the case. We thus have only one choice, shift '(' and go to q2.
Example: run of the algorithm with input “id(id)” (the stack grows from left to right).
c) We said that the grammar is SLR, because all SLR grammars are LR(1), we can say the grammar is LR(1) too.
Example: LR(1) automaton, the algorithm run is similar to the previous one.
Consider the following grammar:
S → E eof \\ E → while E do E\\ E → E ^ E\\ E → (E)\\ E → ID\\
a) Compute the set follow(E).
b) Build the automaton (draw it or give the states and transition table) for LR(0) parsing of this grammar (according to Automata for LR Parsing without Lookahead).
c) Consider the behavior of the LR(0) parser using the automaton. Are there any shift-reduce conflicts ?