Write a recursive descent compiler for the following grammar:
Here,
Since
Your lexical analyzer should be hand-coded for this project; that is, you will not use a lexical analyzer generator.
The statements will be encoded for a hypothetical stack machine with the following instructions:
PUSHv— push v (an integer constant) on the stack
RVALUE l— push the contents of variable l
LVALUEl— push the address of the variable l
POP— throw away the top value on the stack
STO— the rvalue on top of the stack is place in the lvalue below it and both are popped
COPY— push a copy of the top value on the stack
ADD — pop the top two values off the stack, add them, and push the result
SUB — pop the top two values off the stack, subtract them, and push the result
MPY — pop the top two values off the stack, multiply them, and push the result
DIV — pop the top two values off the stack, divide them, and push the result
MOD — pop the top two values off the stack, compute the modulus, and push the result
POW — pop the top two values off the stack, compute the exponentiation operation,
and push the result
HALT— stop execution
You may use
C, Java, Ada, or Python to write your program. You will, of course, find it necessary to remove left recursion in certain productions. Your compiler will prompt for the name of the input program file, and send the output to standard output.
No symbol table is necessary for this exercise. If you construct one, management would be suitably impressed.
On errors, a “meaningful” error message should be printed; i.e., “DO expected in line xx”, “expression expected”, etc. Management would be impressed if you attempted to recover from an error rather than simply halting compilation.
For example, if you are translatiing
begin answer := alpha + 2 * gamma div (C3P0 – R2D2) end
Your compiled code would be:
LVALUE answer
RVALUE alpha
PUSH 2
RVALUE gamma
MPY
RVALUE C3P0
RVALUE R2D2
SUB
DIV
ADD
STO
HALT
begin
alpha := 20; gamma := 11; C3P0 := 5; R2D2 := 4;
answer := alpha + 2 * gamma div (C3P0 - R2D2);
gun := (i mod ammo)^2^2^2
end
