You are given the following (ambiguous) grammar for expressions.
expr → expr + expr
expr → expr * expr
expr → NUM
expr → VAR
where NUM and VAR are tokens. The lexer provides an attribute
NUM.val that is the (integer) value of a NUM token. It also provides
an attribute VAR.name that is the name of a variable (a string).
You would like to translate
these expressions into instructions for a stack machine. The stack
machine has the following instructions.
| PUSH_INT k | Push integer k onto the stack |
| PUSH_VAR k | Push the value of the variable at offset k onto the stack |
| ADD | Pop the top two numbers from the stack and push their sum |
| MULT | Pop the top two numbers from the stack and push their product |
The PUSH_INT instruction can handle any integer that the lexer will produce as an attribute of a NUM token. You have access to three support functions: get_var_offset(v) returns the offset where the variable named v is stored; gen1(I) generates single-part instruction I, and gen2(I,k) generates two-part instruction I, with parameter k. (For example, MULT is a single-part instruction, since it has no additional information, but PUSH_INT is a two-part instruction since it contains the integer to push.)
Write semantic actions to be performed at each production that will generate code to compute a given expression and leave its value on the top of the stack. Do not worry that the grammar is ambiguous. That is a parsing problem, not a semantic one. Write the actions to generate the code as the parsing is done.
Exercise 6.6.1(a) (p. 408 of the text). That is, give translation rules using the BE.false and BE.true attributes for translating repeat S while B, which means the same thing as C++ or Java statement do S while (B). Translate into a sequence of 3-address codes in a style similar to the one used in the book in Figure 6.36.
Suppose that your parser works by building abstract syntax trees for expressions and statements, generating code for them later. How can you generate code for a C++ or Java for-loop (exercise 6.6.1(b)) without writing any extra rules for generating code?