Copyright © 2006 Gradiance Corporation.

LR(0) Parsers

---

---

Canonical LR(0) parsing, sets of items.

---

1.

Below are the LR(0) sets of items for the ambiguous grammar S → (S) | [S] | SS | ε Since the grammar is ambiguous, we will have to resolve conflicts in some way. Build a simple-LR parsing table with the following heuristics to resolve conflicts: Prefer to shift rather than to reduce. Prefer to reduce by any production other than S → ε if possible according to the SLR table-construction rules. Construct this SLR parsing table. Then, identify from the list below the state-lookahead combination for which reduction by S → ε is called for.

a)	State I4 on lookahead $.
b)	State I0 on lookahead ).
c)	State I0 on lookahead (.
d)	State I7 on lookahead S.

2.	Construct the LR(0) sets of items for the grammar: S' → S S → +SS | *SS | a Then, select from the list below the set that is NOT one of the sets of items for this grammar.

a)	S→*S.S
b)	S→+SS.
c)	S→*S.S S→.+SS S→.*SS S→.a
d)	S→*.SS S→.+SS S→.*SS S→.a

3.	Below are the LR(0) sets of items for the ambiguous grammar S → (S) | [S] | SS | ε If we use an SLR(1) parser, for which of these states is there a reduce/reduce conflict?

a)	I7
b)	I8
c)	I1
d)	I6

4.	Consider the augmented grammar: S' → S S → aSb | ab Which of the following is the kernel of one of the sets of valid LR(0) items for the grammar?

a)	{S→a.Sb}
b)	{S→aS.b, S→a.b}
c)	{S→a.b}
d)	{S→ab.}

5.	Below are the LR(0) sets of items for the ambiguous grammar S → (S) | [S] | SS | ε If we use an SLR(1) parser, for which of these states and lookahead symbols is there a shift/reduce conflict?

a)	I0 has a shift/reduce conflict on lookahead $.
b)	I8 has a shift/reduce conflict on lookahead [.
c)	I4 has a shift/reduce conflict on lookahead ).
d)	I1 has a shift/reduce conflict on lookahead (.

6.	Construct the LR(0) sets of items for the grammar: S' → S S → SS+ | SS* | a Then, identify one of those sets of items from the list below.

a)	S'→S.
b)	S→SS.+ S→SS.* S→S.S+ S→S.S* S→.SS+ S→.SS* S→.a
c)	S→SS*. S→S.S+ S→S.S* S→.SS+ S→.SS* S→.a
d)	S→SS+. S→.SS+ S→.SS* S→.a