Problem Description:

Write a recursive descent compiler for the following grammar:



Here,

Since

Your lexical analyzer should be hand-coded for this assignment; 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 projectple, 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