Top-Down Parsing/Exercise 6

Problem

Consider the following grammar, where F is the initial symbol and {a,b,c,d,e} is the set of terminal symbols:

F -> G b | O c F e
O -> a
G -> F c | O c d | (eps)

1. Examine the grammar and rewrite it so that an LL(1) predictive parser can be built for the corresponding language.
2. Compute the FIRST and FOLLOW sets for all non-terminal symbols in the new grammar and build the parse table.
3. Show the analysis table (stack, input, and actions) for the parsing process of the acbe input sequence.

Solution

Semantic tree and dependency graph

"x" is an inherited attribute (propagation in blue); "val" is a synthesized attribute (propagation in red).

Temporary handwritten solution.

Attribute grammar using only synthesized attributes

We start by noting that the semantic computed by the previous grammar corresponds to base 5-like numbering (although the digits do not belong to base 5).

The new grammar is trivial to write:

<text>

</text>

"val" is a synthesized attribute (propagation in red).

Temporary handwritten solution.