Revision as of 19:24, 24 March 2012

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)

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

@@ Line 14: / Line 14: @@
 == Solution ==
-=== Semantic tree and dependency graph ===
+[[Image:Top-Down Parsing-exercise-06.png|Temporary handwritten solution]]
-"x" is an inherited attribute (propagation in blue); "val" is a synthesized attribute (propagation in red).
-Temporary handwritten solution.
-[[Image:Top-Down Parsing-exercise-6-semantic-tree-1.png]]
-=== 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.
-[[Image:Top-Down Parsing-exercise-6-semantic-tree-2.png]]
-[[category:Teaching]]
-[[category:Compilers]]
 [[category:Teaching]]
 [[category:Compilers]]