The final programming assignment is to augment your PSub parser and type checker to generate intermediate code for a stack machine. I suggest that you start by adding code-generation actions to the original PSub grammar (augmented by the type-checking actions) and then convert the resulting productions to LL(1) form as usual; however, you will only need to turn in the LL(1) version of the translation scheme. As for the previous project, your semantic actions need not be written as fully-elaborated code---just enough so that I can verify that you know what actions need to be performed.
In addition to the augmented LL(1) grammar, you should also submit the source to your parser modified to include the type-checking and code-generation actions, as well as the result of compiling the example program given in the first assignment (still in /pub/cis606/pp1input on the cis machines). In recognition of the complexity and cumulativity of this sequence of projects, I will not be placing an emphasis on obtaining correct output from a perfectly working compiler; you may expect to obtain a decent grade from submitting a sufficiently detailed translation scheme and presenting some attempt at implementation---a complete and correct implementation will likely result in extra credit.
This assignment will be due at the start of class on Friday, December 9. To be fair to the other students, I will not grant extensions; if your program is not working by the deadline, submit what you have and I will try to assign partial credit. You may work in pairs (but not in larger groups); in fact, I would encourage this method if you are comfortable working with someone else, as it means less for me to grade!
Below is the list of instructions you should assume for the stack machine. Note that we are assuming that integers, reals, and booleans all take one word of storage; the arithmetic operations beginning with `f' are the floating point versions, which expect real arguments and produce real results. In the descriptions of the instructions, the array s[ ] is the stack, whose top element is top; the array m[ ] is the entire memory; the register pc is the program counter, localbase points to the data section of the current activation record, and globalbase points to the global data area (you should assume that these registers are appropriately initialized at the start of execution). Finally, we assume that addresses are integers, so that integer arithmetic operations apply to them for computing offsets and array indices.
Here is the suggested way to lay out the memory and activation records for PSub (details of this will be discussed in class):
|---------------| |-----------------|
globalbase: | | | Return Value |
| Global Data | | (if function) |
| and | |-----------------|
| Code | | Control Link |
| | |-----------------|
|---------------| | Machine State |
| | |-----------------|
| Stack | localbase: | Actual Params |
top: | | | | |
| V | |-----------------|
| | | Local Data |
|---------------| | |
|-----------------|
Using this model, the following (useless) PSub program should compile to the code given below:
program joe;
var n: integer;
q, r: real;
function f(x: integer; var y: real; z, w: real): integer;
var a, b: boolean;
begin
y := y + z;
f := x * 5;
w := q
end;
begin
q := f(n, q, n, r/3)
end.
0 abs: -- standard identifiers, to be linked ... 23 write: 24 joe: 51 -- start of main program 25 n: 26 q: 27 r: 28 f: 29 -- start of f 29 take 4 -- parameters 30 take 2 -- local variables 31 pushl 1 -- address of y 32 fetch -- lvalue passed in y 33 pushl 1 -- y again 34 fetch 35 pushl 2 -- address of z 36 fetch -- value of z 37 fetchp -- dereference lvalue from y 38 fadd 39 store -- y := y + z 40 pushl -3 -- address for return value 41 pushl 0 -- address of x 42 push 5 -- integer constant 5 43 fetchp -- value of x 44 mul 45 store -- f := x * 5 46 pushl 3 -- address of w 47 pushg 26 -- address of q 48 fetch -- value of q 49 store -- w := q 50 return -- end of f 51 pushg 26 -- address of q 52 push 0 -- dummy return value for f 53 pushg 25 -- address of n 54 pushg 26 -- address of q 55 pushg 25 -- address of n 56 pushg 27 -- address of r 57 push 3 -- integer constant 3 58 float 59 fetchp -- value of r 60 fdiv 61 param -- w gets argument r / 3 62 fetch -- value of n 63 float 64 param -- z gets argument n 65 param -- y gets argument address of q 66 fetch -- value of n 67 param -- x gets argument n 68 pushg 28 -- address of f 69 fetch -- start of function f 70 call 71 float 72 store -- q := f(n, q, n, r/3) 73 halt
add s[top-1] := s[top-1] + s[top]; top := top - 1
sub s[top-1] := s[top-1] - s[top]; top := top - 1
mul s[top-1] := s[top-1] * s[top]; top := top - 1
div s[top-1] := s[top-1] div s[top]; top := top - 1
mod s[top-1] := s[top-1] mod s[top]; top := top - 1
neg s[top] := -s[top]
eq s[top-1] := s[top-1] = s[top]; top := top - 1
leq s[top-1] := s[top-1] <= s[top]; top := top - 1
float s[top] := inttofloat(s[top])
floatp s[top-1] := inttofloat(s[top-1])
fadd s[top-1] := s[top-1] + s[top]; top := top - 1
fsub s[top-1] := s[top-1] - s[top]; top := top - 1
fmul s[top-1] := s[top-1] * s[top]; top := top - 1
fdiv s[top-1] := s[top-1] / s[top]; top := top - 1
fneg s[top] := -s[top]
feq s[top-1] := s[top-1] = s[top]; top := top - 1
fleq s[top-1] := s[top-1] <= s[top]; top := top - 1
or s[top-1] := s[top-1] or s[top]; top := top - 1
and s[top-1] := s[top-1] and s[top]; top := top - 1
not s[top] := not s[top]
iff s[top-1] := s[top-1] = s[top]; top := top - 1
impl s[top-1] := s[top-1] <= s[top]; top := top - 1
swap temp := s[top]; s[top] := s[top-1]; s[top-1] := temp
copy s[top+1] := s[top]; top := top + 1
pop top := top - 1
push v s[top+1] := v; top := top + 1
pushl v s[top+1] := v + localbase; top := top + 1
pushg v s[top+1] := v + globalbase; top := top + 1
fetch s[top] := m[s[top]]
fetchp s[top-1] := m[s[top-1]]
store m[s[top-1]] := s[top]; top := top - 2
param s[top+2] := s[top]; top := top - 1
take n top := top + n
goto l pc := l + globalbase
gofalse l (if s[top] = false then pc := l + globalbase); top := top - 1
call s[top+1] := pc; pc := s[top] + globalbase; s[top] := localbase;
localbase := top + 2; top := top + 1
return top := localbase - 3; pc := s[top+2]; localbase := s[top+1]
halt exit program