# LR(1) but not LALR(1) grammar from the Dragon book
terminal a b c d e
nonterminal E Integer
nonterminal T Integer
nonterminal F Integer
topsym E
E --> a T d
E --> a F e
E --> b T e
E --> b F d
T --> c
F --> c
EOF
////////////////
Trace of my LR(1) parser generator follows. Note that if we combined state 6
with state 9, we would get a reduce-reduce conflict. The problem is that
the LALR and SLR methods are not taking advantage of all the information that
the viable prefix state machine gives us: that if the first symbol read was
"a", then we should reduce "c" to T on lookahead "d", but if the first symbol
was "b", we should reduce "c" to F on lookahead "d". The LR(1) items
calculate the possible lookaheads based on the current state. From the
initial state 0, we go to state 1 on shifting "a", and to state 2 on
shifting "b". State 1 goes to state 6 on shifting "c", but state 2 goes to
state 9 on shifting "c".
////////////////
FSM with 15 states created
state 0:
E --> .a T d , EOF
E --> .a F e , EOF
E --> .b T e , EOF
E --> .b F d , EOF
START --> .E EOF , EOF
state 1:
E --> a .T d , EOF
E --> a .F e , EOF
T --> .c , d
F --> .c , e
state 2:
E --> b .T e , EOF
E --> b .F d , EOF
T --> .c , e
F --> .c , d
state 3:
START --> E .EOF , EOF
state 4:
E --> a T .d , EOF
state 5:
E --> a F .e , EOF
state 6:
T --> c . , d
F --> c . , e
state 7:
E --> b T .e , EOF
state 8:
E --> b F .d , EOF
state 9:
T --> c . , e
F --> c . , d
state 10:
START --> E EOF . , EOF
state 11:
E --> a T d . , EOF
state 12:
E --> a F e . , EOF
state 13:
E --> b T e . , EOF
state 14:
E --> b F d . , EOF
Nullible Nonterminals:
FIRST SETS:
E : a b
T : c
F : c
START : a b
fsm 0,a = s1
fsm 0,b = s2
fsm 0,E = g3
fsm 1,c = s6
fsm 1,T = g4
fsm 1,F = g5
fsm 2,c = s9
fsm 2,T = g7
fsm 2,F = g8
fsm 3,EOF = ac
fsm 4,d = s11
fsm 5,e = s12
fsm 6,d = r4
fsm 6,e = r5
fsm 7,e = s13
fsm 8,d = s14
fsm 9,d = r5
fsm 9,e = r4
fsm 10,EOF = r6
fsm 11,EOF = r0
fsm 12,EOF = r1
fsm 13,EOF = r2
fsm 14,EOF = r3