Bottom-Up Parsing - Crafting a Compiler - page 229

26. Show that the following holds for any LALR(1) construction:

(a) For any state s containing the item A →α•β ,

ItemFollow (( s , A →α•β )) ⊆ Follow(A)

(b)

ItemFollow (( s , A →α i •β i )) = Follow(A)

s

A →α i •β i ∈ s

27. Perform the LALR(1) construction for the following grammar:

1 Start → S$

2 S → xC1y1C2y2C3y3

3 | A1

4 A1 → b1 C1

5 | a1

6 A2 → b2 C2

7 | a2

8 A3 → b3 C3

9 | a3

10 C1 → A2

11 C2 → A1

12 | A3

13 C3 → A2

28. Recall the E algorithm given in Figure 6.28. Using

the grammars in Figure 6.31 and Exercise 27 as a guide, show how to
generate a LALR(1) grammar that requires n iterations for ItemFollow sets
to converge in E

val I tem P rop G raph

val I tem P rop G raph .

29. For the grammar shown in Figure 6.35, complete the LALR(1) construc-
tion from Figure 6.37.

30. Which of the grammars in Exercise 10 are LALR(1)? Justify your answers.

31. Show the LR(1) construction for the grammar in Exercise 4.