1.  (40pt) Consider the language:

P = {w l w e {(, ), [, ]}* $$,  all parentheses in w are properly balanced} .

(a)  (10pt) Construct a grammar,  G1 , for P that is LL(1).   Build its LL(1) parse table  (as in

Fig. 2.20) to prove that it is LL(1).

(b)  (10pt) Construct a grammar, G2 , for P that is SLR(1) but not LL(1). Build its SLR(1) parse

table (as in Fig. 2.28) to prove that it is SLR(1). Prove also that it is not LL(1).

(c)  (4pt) Construct a grammar, G3 , for P that is not SLR(1). Prove that it is not SLR(1).

(d)  (4pt) Show the parse tree and the left derivation for the string  [([])()]$$ in G1 .

(e)  (4pt) Show the trace of the table-driven LL(1) parse (as in Fig. 2.21) using G1  for the same

string.

(f)  (4pt) Show the parse tree and the right derivation for the string  [([])()]$$ in G2 .

(g)  (4pt) Show the trace of the table-driven SLR(1) parse (as in Fig. 2.30) using G2  for the same

string.

The grammars G1●●3  above must have a production P → S$$, with P not appearing anywhere else in the grammar. The parse tables are built as done in the textbook, not as done by jflap. You can use jflap to help but you need to modify its output. Do not upload screenshots from jflap. Write your own tables.

2.  (30pt) Expressions can be written without the need of parentheses in postfix form (also called reverse Polish notation). The name comes from the fact that the operator comes after the operands: a + b is written as a b +. A postfix expression can be easily evaluated using a stack.

(a)  (10pt) Using the underlying grammar from Fig. 4.1,  write  an  S-attributed grammar that

associates with the root of the parse tree the postfix expression corresponding to the (infix) expression produced by the tree.

(b)  (5pt) Use this  S-attributed attributed grammar to draw the annotated parse tree for the

expression (-  3  +  2)  *  7  -  1. Show the attribute flow (arrows and values).

(c)  (10pt) Using the underlying grammar from Fig. 4.3,  write an L-attributed grammar that associates with the root of the parse tree the postfix expression corresponding to the (infix) expression produced by the tree.

(d)  (5pt) Use this L-attributed attributed grammar to draw the annotated parse tree for the expression (-  3  +  2)  *  7  -  1. Show the attribute flow (arrows and values).

3.  (30pt) Consider the grammar below for floating point numbers:

Float    -→   Left  .  Right

Left    -→   Digit Left more

Left more    -→   Left

Left more    -→   ε

Right    -→   Digit Right more

Right more    -→   Right

Right more    -→   ε

Digit    -→   0|1|2|3|4|5|6|7|8|9