Figure 1: Grammar G_{1} and an LALR Parser for that Grammar

The action of an LALR parser for grammar G_{1} on the string (x+y*z)*x

0:(x+y*z)*x$
s4
0(4:x+y*z)*x$
s5
0(4x5:+y*z)*x$
r6, goto 3
0(4F3:+y*z)*x$ F->x
r4, goto 2
0(4T2:+y*z)*x$ T->F
r2, goto 8
0(4E8:+y*z)*x$ E->T
s6
0(4E8+6:y*z)*x$
s5
0(4E8+6y5:*z)*x$
r6, goto 3
0(4E8+6F3:*z)*x$ F->y
r4, goto 9
0(4E8+6T9:*z)*x$ T->F
s7
0(4E8+6T9*7:z)*x$
s5

0(4E8+6T9*7z5:)*x$
r6, goto 10
0(4E8+6T9*7F10:)*x$
r3, goto 9
0(4E8+6T9:)*x$ T->T*F
r1, goto 8
0(4E8:)*x$ E->E+T
s11
0(4E8)11:*x$
r5, goto 3
0F3:*x$ F->(E)
r4, goto 2
0T2:*x$ T->F
s7
0T2*7:x$
s5
0T2*7x5:$
r6, goto 10
0T2*7F10:$
r3, goto 2
0T2:$
r2, goto 1
0E1:$
halt

Let G_{2} be the following ambiguous grammar, which illustrates the “dangling else” problem. The Parser table has a shift-reduce conflict, which we resolve using the “closest if” rule. Informally, the alphabet symbols have the following meanings:

S statement
L list of statements
a statement with no control structure
w while condition
i if condition
e else
b begin
n end

Figure 2: G_{2} and its LALR Parser Table, to Fill in

We can avoid the conflict by choosing an unambiguous context-free grammar equivalent to G_{2}, namely G_{3} below.

Informally, the alphabet symbols have the following meanings:

S statement
M matched statement
U unmatched statement
L list of statements
a statement with no control structure
w while condition
i if condition
e else
b begin
n end

Figure 3: LALR Parser Table for the Unambiguous Grammar G_{3} Figure 4: LALR Parser Table for an Ambiguous Grammar Equivalent to G_{1}