in Books, Doing Books, Theory of Computation

Theory of Computation #9

Exercise 2.4.3: Design an LL(1) parse table for the following grammar.

The table consists of columns which have terminals and rows for non-terminals.

x y z lambda EOS
S xSz ySz z lambda error

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.

Ok, let’s take a look at some derivations:

You can see that we need LL(2). And get the following table.

xx xy yy yx
S xSy xy yy yx

Exercise 2.5.4: Construct an LR(1) parse table for the grammar below.

Ok, let’s start with some examples again of possible derivatives:

And here’s the table:

x y lambda S
1 shift 2 S -> lambda
2shift 4 shift 3 5
3 S -> xSy S -> xSy 6
4 shift 3
5 shift 3
6 accept

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:

It works.

Write a Comment