In this week's practical we shall be extending the Parva compiler to recognise and compile code for programs with more than one void function. Although these will not allow for parameters, inter-function communication can be achieved through the use of global variables, as exemplified by
int global1, global2;
void routine () {
int local1, local2;
local1 = global1 + local2;
}
void main () {
int x;
routine();
}
where, to make it simple, all global declarations are to be made before any functions are defined, and where it is intended that the run time organisation will be on the lines of
Stack frame for function Globals
.-----------------------------------. .--------------------------.
| | | | | .... | | | |
`-----------------------------------' `--------------------------'
^ ^
CPU.BP CPU.GP
with addressing opcodes extended so that ADR -Local will push a local address (computed relative to CPU.BP) onto the stack and GAD -Global will push a global variable address (computed relative to CPU.GP) onto the stack. This tutorial explores some of the aspects of the system that you will need to incorporate into the compiler.
(a) The first Parva compiler had productions like
Parva = "void" "main" "(" [ "void" ] ")" Block .
Block = "{" { Statement } "}" .
Statement = ConstDeclaration | VarDeclarations | Assignment ...
Assignment = Variable ( "=" Expression | "++" | "--" ) ";"
How would these have to be altered to handle multi-function programs?
Parva = { ConstDeclaration | VarDeclarations } { function } .
Function = "void" Identifier "(" [ "void" ] ")" Block .
Block = "{" { Statement } "}" .
Statement = ConstDeclaration | VarDeclarations | Assignment ...
Assignment = Variable ( "=" Expression | "++" | "--" ) ";"
(b) Suggest what the runtime arrangement would be for the above program at the instant where main has started execution.
Stack frame for main Globals
.--------------------------------------------.
| x | RA | DL | global2| global1|
`--------------------------------------------'
^ ^
CPU.BP CPU.GP
(c) What would the runtime arrangement be at the instant where main has called routine and routine has just started execution?
Stack frame for routine Stack frame for main Globals
500 501 502 503 504 505 506 507 508
.--------------------------------------------------------------------------------.
| local2 | local1 | RA | DL | x | RA | DL | global2| global1|
`--------------------------------------------------------------------------------'
^ ^
CPU.BP CPU.GP
(d) Suggest what sort of code you should generate for the above program. You will clearly need to have two new opcodes, say CAL X to call a routine whose code begins at location X, and RET, to be able to return from a routine back to the caller.
DSP 2 ; space for globals
CAL main ; call main
HLT ; call it a day
routine: DSP 4 ; space for locals local1 + local2 + DL + RA
ADR -1
GAD -1
VAL
GAD -2
VAL
ADD
STO ; local1 = global1 + local2;
RET
main: DSP 3 ; space for local x + DL + RA
CAL routine ; routine();
RET
(e) Suggest how an emulator might handle the CAL and RET opcodes.
(f) What modifications would be needed to the symbol table handler to deal with such programs?
(g) To deal with the problem of mutually recursive functions one could introduce the concept of the "function prototype", as exemplified by
void routine2 (); // prototype, header only
void routine1 () { routine2(); }
void routine2 () { routine1(); }
void main () { routine1(); }
What implications does this have for the grammar and the compiler, and how do you handle these?