Write an LL(1) grammar with action routines and automatic attribute space management that generates the reverse Polish translation described in Exercise 4.7.

Data From Exercise 4.7:

Suppose that we want to translate constant expressions into the postfix, or “reverse Polish” notation of logician Jan Łukasiewicz. Postfix notation does not require parentheses. It appears in stack-based languages such as Postscript, Forth, and the P-code and Java bytecode intermediate forms mentioned in Section 1.4. It also served, historically, as the input language of certain hand-held calculators made by Hewlett-Packard. When given a number, a postfix calculator would push the number onto an internal stack. When given an operator, it would pop the top two numbers from the stack, apply the operator, and push the result. The display would show the value at the top of the stack. To compute 2 × (15 − 3)/4, for example, one would push 2 E 1 5 E 3 E - * 4 E / (here E is the “enter” key, used to end the string of digits that constitute a number).

Using the underlying CFG of Figure 4.1, write an attribute grammar that will associate with the root of the parse tree a sequence of postfix calculator button pushes, seq, that will compute the arithmetic value of the tokens derived from that symbol. You may assume the existence of a function buttons(c) that returns a sequence of button pushes (ending with E on a postfix calculator) for the constant c. You may also assume the existence of a concatenation function for sequences of button pushes.

Transcribed Image Text:

1. E + E2 + T E1.val := sum(E2.val, T.val) 2. Е — Е -Т E1.val := difference(E2.val, T.val) 3. E + T E.val := T.val T1. val := product(T2.val, Eval) T1. val := quotientT2. val, Eval) 4. Ti + T2 * F 5. T + T2 / F 6. Т- F T.val := Eval 7. F + - F2 F1.val := additive.inverse(F2.val) 8. F (E) Eval := E.val 9. F+ const Eval := const.val