In class, we considered (part of) an attribute grammar for arithmetic expressions. A more complete LL(1) grammar for arithmetic expressions is the following:
S → E$
E → T E′ E′ → AT E′ E′ →ε
T →FT′ T′ →MFT′ T′ → ε
F → id
F → num F → ( E ) A→+ A→-
M→* M → /
The attribute grammar we discussed in class calculated the value of a given expression. In this question, you are to solve the same problem, but you should take a different approach:
• Instead of directly computing the value of the expression, you are to generate C code that computes the value of the expression at runtime. Specifically, if you run the parser generated from the grammar annotated with your action routines, the parser should print C code to evaluate the parsed expression to stdout.
• You are to use action routines written in C to generate this C code.
The code you generate has access to a stack of doubles that can be manipulated using the following two functions:
• A function void push(double) that pushes a double onto a global stack holding values of type double.
• A function double pop() that removes the topmost entry from the global stack of doubles and returns it.
The code you generate should place the final result of evaluating the arithmetic expression into a variable result of type double.
As an example, with the help of the global stack of doubles, the expression 3 + (4 + x) / y can be evaluated as follows:
double tmp1, tmp2, result;
push(3);
push(4);
push(x);
tmp2 = pop();
tmp1 = pop();
push(tmp1 + tmp2);
push(y);
tmp2 = pop();
tmp1 = pop();
push(tmp1 / tmp2);
tmp2 = pop();
tmp1 = pop();
push(tmp1 + tmp2);
result = pop();
This (or equivalent code) is what your parser should print on stdout when run on the expression 3 + (4 + x) / y. To be perfectly clear, the action routines you attach to the productions in the grammar should be C code that prints the above code when parsing the expression 3 + (4 + x) / x. The action routines themselves should not contain this code. (They can’t, because the action routines don’t change depending on the arithmetic expression we parse, but the generated C code must change with the parsed arithmetic expression.)
Your code should assume that the scanner annotates every terminal with the following information:
• For a number literal num, a string num.val that is a valid string representation of the floating point value of the number literal.
• For an identifier id, a string id.name that holds the name of the C variable this identifier refers to.
In your action routines, refer to the different symbols in a production by their position in the production, as is common in parser generators that use action routines. The left-hand side of the production is symbol $0. The symbols on the right-hand side are numbered from 1, left to right. You are allowed to associate attributes with symbols in the grammar. For example, it may be helpful to annotate each M or A with an attribute op that stores the operator it represents as a string. You’d achieve this using:
A→+{ $0.op = “+”; }
To illustrate your task a little more clearly, here is one possible (somewhat convoluted) set of action
routines that would generate C code to print the parsed expression instead of evaluating it:
S → E$
E → T E′
E′ → AT E′ {printf(“printf(\”%s\”);”, $1.op);} E′ →ε
T → FT′
T ′ → M F T ′ {printf(“printf(\”%s\”);”, $1.op);} T′ →ε
F → id {printf(“printf(\”%s\”);”, $1.name);}
F → num {printf(“printf(\”%s\”);”, $1.val);}
F → ( {printf(“printf(\”(\”);”);} E ) {printf(“printf(\”)\”);”);} A→+{$0.op = “+”;}
A→−{$0.op = “-“;}
M → ∗ {$0.op = “*”;} M → / {$0.op = “/”;}
When parsing the expression 3 + (4 + x) / y using this annotated grammar, the output printed to stdout would be
printf(“3”);
printf(“+”);
printf(“(“);
printf(“4”);
printf(“+”);
printf(“x”);
printf(“)”);
printf(“/”);
printf(“y”);
which is C code that prints the original expression. The action routines you provide is to print C code that evaluates the expression instead of printing the expression.