Exercise 2.4.3: Design an LL(1) parse table for the following grammar.
S -> xSz S -> ySz S -> lambda.
The table consists of columns which have terminals and rows for non-terminals.
[table]
x, y, z, lambda, EOS
S, xSz, ySz, z, lambda, error[/table]
Exercise 2.4.4: How many symbols of lookahead would be required by an LL parser when parsing strings based on the following grammar? Design a corresponding parse table.
S -> xSy S -> xy
Ok, let’s take a look at some derivations:
xy xxyy xxxyyy etc.
You can see that we need LL(2). And get the following table.
[table]
, xx, xy, yy, yx
S, xSy, xy, yy, yx[/table]
Exercise 2.5.4: Construct an LR(1) parse table for the grammar below.
S -> xSy S -> lambda.
Ok, let’s start with some examples again of possible derivatives:
lambda xy xxyy xxxyyy
And here’s the table:
[table]
, x, y, lambda, S
1, shift 2, , S -> lambda,
2,shift 4, shift 3, , 5
3, , S -> xSy, S -> xSy, 6
4, , shift 3, , ,
5, , shift 3, , ,
6, , , accept, , [/table]
Pretty simple, however took some thinking through. I started with the simplest example and implemented it, and then did the other one. Thanks to the recursive nature of the problem you solve one problem for all problems basically.
Here’s the stack content for xxyy:
1 1 x 2 1 x 2 x 4 1 x 2 x 4 y 3 1 x 2 x 4 y 3 1 x 2 S 1 1 x 2 S 1 y 3 1 S 6 accept
It works.