Bottom-Up Parsing - Crafting a Compiler - page 203

1 Start → Exprs $

2 Exprs → Ea

3 | Fb

4 E → Eplusnum

5 | num

6 F → Fplusnum

7 | num

State 0 Goto State 2 Goto

Start →• Exprs $ 1 E → num •

Exprs→•Ea 4 F → num •

Exprs→•Fb 3

E →•Eplusnum 4

E →•num 2

F →•Fplusnum 3

F →•num 2

Figure 6.19: A grammar that is not LR( k ).

Start ⇒ rm Exprs $

⇒ rm Ea$
⇒ rm Eplusnuma$
⇒ rm

E plus ... plus num a $

⇒ rm num plus ... plus num a $

A bottom-up parse must play the above derivation backwards. Thus, the first
few steps of the parse will be:

0 Initial Configuration num plus ...plus num a $

nu 2

0 shift num plus ...plus num a $

With num on top-of-stack, we are in State 2. A deterministic, bottom-up parser
must decide at this point whether to reduce num to an E or an F.Ifthedecision
were delayed, then the reduction wouldhavetotakeplaceinthemiddleof
the stack, and this is not allowed. The information needed to resolve the
reduce reduce conflict appears just before the $ symbol. Unfortunately, the

relevant a or b could be arbitrarily far ahead in the input, because strings
derived from E or F can be arbitrarily long.
In summary, simple grammars and languages can have subtle problems
that prohibit generation of a bottom-up parser. It follows that a top-down
parser would also fail on such grammars (Exercise 16). The LR(0) construction

/