Answer Happy

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 ab+. 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).

1. ELE2 + T 2. E → E - T 3. ET 4. Ti -T F . 5. Ti-T2 / F . E,.val := sum(E2.val, Tval) E,.val := differencelEz.val, T.vall E.val := T.val T..val :=product/T2.val, F.vall Ti.val := quotient/T2.val, F.vall Tval := Eval Fi.val := additive_inverselF2.val) Eval := E.val • Eval :=const.val 6. T-→ F 7. Fi -→ - F2 8. F (E) . 9. F const Figure 4.1 A simple attribute grammar for constant expressions, using the standard arith- metic operations. Each semantic rule is introduced by a sign. Lid LT LT >, LT --> • Lc:= 1 + LT.C LT.C :=LC LTC = 0

1. ET TT TT.st: Tval • E.val := TT.val • TT1.val := TT 2.val 2. TT + T TT2 TT2.st: TT.st + T.val 3. TT + - TTT2 TT2.st: TT.st - T.val 4. TT - E TT.val := TT.st TT..val := TT2.val . • T.val := FT.val • FT1.val := FT2.val • FT1 val := FT2.val 5. T F FT FT.st: F.val 6. FT + * F FT2 FT2.st:= FT1.st x Eval 7. FT + / FFT2 FT2.st: FT.st : Eval 8. FT - € FT.val := FT.st 9. F - - 12 Fival := - F2.val 10. F -- (E) Eval := E.val . 11. F const . Eval:=const.val Figure 4.3 An attribute grammar for constant expressions based on an LL(1) CFG. In this grammar several productions have two semantic rules.