In the kit PRAC13A.ZIP you will find all the sources for the solution discussed here.
I am sure that by the end of the week most people must have got most of the way to a solution.
It may help to see the sort of code that we might generate for some programs. Essentially we must
So a program like this
int b, a = 5;
void main () {
int x;
print("hi gang");
}
must lead to code like this
DSP 2 ; globals
GAD -2
LIT 5
STO ; initialise global a
CAL main ; get going at last - this starts life as "CAL undefined"
HLT
main: DSP 3 ; DL, RA 1 local var - at this point we backpatch the CAL
PRS "hi gang"
RET
Function prototypes cause more complications! One solution, which probably most people adopted, is to use the prototype declaration to generate a forward jump to the body of the function, to be patched later when the function is properly defined. That way "forward" calls all get handled as "backward" jumps initially, no matter how many there are, and so code like this
int b, a = 5;
void forward () ; // prototype
void main () {
int x;
print("hi gang");
a = x;
forward();
a++;
forward();
}
void forward() {
print(" - thanks for all the fun", a)
}
might lead to to
DSP 2 ; globals - offset 1 for b, 2 for a
ADR -2
LIT 5
STO ; initialise global a
CAL main ; get going at last - this starts life as "CAL undefined"
HLT
forward: BRN forwdef ; starts life as BRN undefined
main: DSP 3 ; DL, RA 1 local var, offset 3 - at this point we backpatch the CAL
PRS "hi gang"
GAD -2 ; global variable address
ADR -3 ; local variable address
VAL
STO
CAL forward ; backwards call
GAD -2 ; global variable address
PPP ; local variable address
CAL forward ; backwards call
RET
forwdef: DSP 2 ; DL, RA, no locals
PRS " - thanks for all the fun"
GAD -2 ; global access
VAL
PRN ; print(a)
RET
Of course there are always "things you might not have thought of", relating to such monsters as functions that are declared forward, but never subsequently defined, attempts to define functions initially introduced by prototypes for a second time, never remembering to define the main function, or attempting to call the main function from within the code itself. Here is a suggested way to handle all this in the attribute grammar.
Note that I redefined the CGen->call interface from the original one in the kit, so that it would more closely resemble those used to generate BRN and BZE instructions. I also introduced the constants global and local so that those obscure 0 and 1 constants in the original kit were eliminated.
COMPILER Parva $CX
const int local = 1;
const int global = 0;
/*--------------------------------------------------------------------------*/
PRODUCTIONS
Parva
= (. arithtypes = typeset(TABLE_none, TABLE_ints, TABLE_chars);
booltypes = typeset(TABLE_none, TABLE_bools);
CGEN_labels enterlabel, startlabel;
bool mainDefined = false;
looplevel = 0;
loopexit = CGen->undefined;
/* no globals declared yet */
int framesize = 0;
/* DSP ?? */
CGen->openstackframe(enterlabel); .)
{ ConstDeclaration<global>
| VarDeclarations<framesize, global>
}
(.
/* fixup the global DSP */
CGen->fixup(enterlabel, framesize);
/* prepare to "call main" - but we don't know where to go yet, so store
the position of the CAL instruction */
CGen->call(startlabel, CGen->undefined);
/* all over once main returns */
CGen->leaveprogram(); .)
{ Function<startlabel, mainDefined>
} EOF (.
/* did we ever see a main function? */
if (!mainDefined) SynError(236); .)
.
/* Parse any and all functions the same way */
Function<CGEN_labels startlabel, bool &mainDefined>
= (. int framesize;
bool found;
CGEN_labels enterlabel;
TABLE_entries oldentry, entry; .)
"void" Ident<entry.name> (.
/* We prepare a table entry assuming it will be a completely defined function */
entry.idclass = TABLE_procs;
entry.type = TABLE_none;
entry.level = 0;
/* Did we just find "main" ? */
entry.p.isMain = strcmp(entry.name, "main") == 0;
CGen->storelabel(entry.p.entrypoint);
/* Careful - we may be filling in a "forward reference for a previously declared prototype,
so look to see if there is an entry in the table already */
Table->search(entry.name, oldentry, found);
/* and check just in case you were dumb enough to define it more than once! */
if (found && oldentry.idclass == TABLE_procs
&& oldentry.p.defined) SemError(237); .)
/* The "(" [ "void" ] ")" is delayed in the scheme of things till here in the ATG file
to help get error messages into the right place */
"(" [ "void" ] ")"
( (.
/* The stack frame has to have a size of at least 2 to cater for DL and RA */
framesize = 2;
maxframe = framesize;
/* If we have found "main" we can backpatch that CAL we set up at the start of
all this adventure */
if (entry.p.isMain) {
mainDefined = true;
CGen->backpatch(startlabel);
}
/* Are we fixing up an old forward declared function? */
if (found && oldentry.idclass == TABLE_procs) {
/* Yes, so now we can mark it as defined */
oldentry.p.defined = true;
/* We can fill in the "BRN undefined" instruction we planted when we saw the prototype */
CGen->backpatch(oldentry.p.entrypoint);
/* We can now fix the table entry - we now know the proper entry point at last */
CGen->storelabel(oldentry.p.entrypoint);
Table->update(oldentry);
} else {
/* It was not a prototype function - it is one that is being defined "properly" */
entry.p.defined = true;
/* so add the new symbol table entry rather than play with the old one any longer */
Table->enter(entry);
}
/* DSP ?? */
CGen->openstackframe(enterlabel); .)
Block<framesize> (.
/* Fix the DSP once we know how many local variables we had */
CGen->fixup(enterlabel, maxframe);
/* Generate the return after all the statements */
CGen->leaveproc(); .)
| ";" (.
/* Here is where we deal with function prototypes! */
entry.p.defined = false;
/* "main" is a special case - we have already got a CAL ?? waiting to fix that one
but in other cases we generate a BRN ??? that will be fixed later when the
body of the function is finally encountered */
if (!entry.p.isMain && !found)
CGen->jump(entry.p.entrypoint, CGen->undefined);
/* But we need to add the entry unless it is a repeat prototype which causes no harm */
if (!found) Table->enter(entry); .)
)
.
We have to be able to call functions, which means a change to the Assignment parser. Note how the call to Designator needs a larger set of allowed classes than before. The actions for a call are introduced ahead of the "(" ")" syntax in an attempt to get any error messages closer to the identifier.
AssignmentOrCall
= (. TABLE_types vartype, exptype;
TABLE_entries entry; .)
**** Designator<classset(TABLE_vars, TABLE_procs), entry, vartype>
( (. if (entry.idclass != TABLE_vars) SemError(210); .)
( AssignOp
Expression<exptype> (. if (compatible(vartype, exptype))
CGen->assign(vartype == TABLE_chars);
else SemError(218); .)
| "++" (. if (arithtypes.memb(vartype))
CGen->increment(vartype == TABLE_chars);
else SemError(218); .)
| "--" (. if (arithtypes.memb(vartype))
CGen->decrement(vartype == TABLE_chars);
else SemError(218); .)
)
**** | (. if (entry.idclass == TABLE_procs) {
**** if (entry.p.isMain) SemError(239);
**** /* Careful - the first argument here is a dummy one! */
**** else CGen->call(entry.p.entrypoint, entry.p.entrypoint);
**** }
**** else SemError(210); .)
**** "(" ")"
) WEAK ";" .
We also need a trivial modification to the code for a ReturnStatement:
ReturnStatement
**** = "return" WEAK ";" (. CGen->leaveproc(); .) .
To support all this we need to modify the stack machine:
typedef enum {
running, finished, badmem, baddata, nodata, divzero, badop, badind, badval,
badadr
} status;
typedef int STKMC_address;
class STKMC {
...
private:
struct processor {
STKMC_opcodes ir; // Instruction register
int bp; // Function Base pointer
int gp; // Global Base pointer
int sp; // Stack pointer
int mp; // Mark Stack pointer
int pc; // Program counter
};
The modifications to the interpreter are as follows. Note the runtime checks to see whether an attempt is being made to branch to, or call, an undefined address (such as would happen if we had used a prototype and never completed it):
case STKMC_brn: // unconditional branch
if (mem[cpu.pc] < 0) ps = badadr;
else cpu.pc = mem[cpu.pc]; break;
case STKMC_cal: // call function
if (mem[cpu.pc] < 0) ps = badadr;
else if (inbounds(cpu.sp - 2)) {
mem[cpu.sp - 2] = cpu.pc + 1;
mem[cpu.sp - 1] = cpu.bp;
cpu.bp = cpu.sp;
cpu.pc = mem[cpu.pc];
}
break;
case STKMC_ret: // return from function
cpu.sp = cpu.bp;
cpu.pc = mem[cpu.bp - 2];
cpu.bp = mem[cpu.bp - 1];
break;
Modifications are needed to the table handler. Here is what I used
struct TABLE_entries {
TABLE_alfa name; // identifier
TABLE_idclasses idclass; // class
int self, level;
TABLE_types type;
union {
struct {
int value;
} c; // constants
struct {
int size, offset;
bool canchange, scalar;
} v; // variables
**** struct {
**** CGEN_labels entrypoint;
**** bool defined, isMain;
**** } p; // functions or procedures
};
};
class TABLE {
public:
...
void update(TABLE_entries entry);
// update a table entry after changing various fields
};
To handle the rather asymmetric scope rules we alter the enter routine
void TABLE::enter(TABLE_entries &entry)
{ int look;
find(entry.name, look);
**** if (look > 0 && entry.level == symtable[look].level)
Report->error(201);
else
{ if (top == tablemax) // Symbol Table overflow
{ printf("Symbol table full\n"); exit(1); }
top++; entry.self = top;
symtable[top] = entry;
}
}
void TABLE::update(TABLE_entries entry)
{ symtable[entry.self] = entry; }
The best idea is to build up a chain of the break statements within the code itself, in the manner described in the text book on page 224. These all appear at first to chain in the wrong way, but when the end of the loop is reached a simple walk through the chain fixes everything up. Here is how simple it really all is! (We need similar code in DoStatement and in ForStatement, of course - see the full ATG files).
WhileStatement<int &framesize>
= (. CGEN_labels startloop, oldexit, testlabel, dummylabel; .)
"while" WEAK "(" (. CGen->storelabel(startloop); .)
Condition WEAK ")" (. looplevel++; oldexit = loopexit;
loopexit = CGen->undefined;
CGen->jumponfalse(testlabel, CGen->undefined); .)
Block<framesize> (. CGen->jump(dummylabel, startloop);
CGen->backpatch(testlabel);
CGen->backpatchlist(loopexit);
loopexit = oldexit; looplevel--; .) .
Here looplevel and loopexit are "global" variables - so that they can be seen both by WhileStatement and by BreakStatement. looplevel is used as a simple way of allowing the semantic check that one can only have the syntactically trivial break statement within the context of loops. We cannot use a simple Boolean variable for this purpose, as we need to be able to handle nested loops. The same need is that which requires us to save and restore loopexit before and after we parse the loop body statement. After this, the BreakStatement parser is trivially easy (note the clever use of the call to CGen->jump with what appears to be the same parameter in two places. Work it out for yourselves!)
BreakStatement
= "break" (. if (!looplevel) SemError(230);
CGen->jump(loopexit, loopexit); .)
WEAK ";" .
This all works in conjunction with a new routine in the code generator:
void CGEN::backpatchlist(CGEN_labels location)
{ CGEN_labels nextlabel;
while (location != undefined) { // stop when we get the sentinel
nextlabel = Machine->mem[location+1]; // keep a copy of the link
Machine->mem[location+1] = codetop; // fix the branch instruction
location = nextlabel; // and move to the next one
}
}
PARVA1.ATG embodies another solution. Here the idea is to generate rather kludgy code, so that a while loop looks like this
startloop evaluate condition
if false, goto endloop
goto loopbody // jump over next operation
breakpoint goto endloop // all breaks come here
loopbody ....
goto breakpoint // a break statement
....
goto breakpoint // another break statement
....
goto startloop // round the loop again
endloop // continue after loop
The advantage of this is that there are always exactly two backpatch operations per loop. The break statements are turned into simple (but nasty) backward, rather than (nice) forward jumps. The code generation is actually even more long winded than for the elegant method. We still need the global variables; we still need to save and restore loopexit.
WhileStatement<int &framesize>
= (. CGEN_labels startloop, oldexit, testlabel, dummylabel; .)
"while" WEAK "(" (. CGen->storelabel(startloop); .)
Condition WEAK ")" (. looplevel++; oldexit = loopexit;
CGen->jumponfalse(testlabel, CGen->undefined);
CGen->jump(dummylabel, CGen->undefined);
CGen->jump(loopexit, CGen->undefined);
CGen->backpatch(dummylabel); .)
Block<framesize> (. CGen->jump(dummylabel, startloop);
CGen->backpatch(testlabel);
CGen->backpatch(loopexit);
loopexit = oldexit; looplevel--; .) .
BreakStatement
= (. CGEN_labels dummylabel; .)
"break" (. if (!looplevel) SemError(230);
CGen->jump(dummylabel, loopexit); .)
WEAK ";" .
Some might think that this is silly, for one can only execute one break statement in a loop. True - executing a break statement means you leave the loop; you cannot carry on within the loop to another break statement. But one has to be able to generate code for multiple break statements - consider, for example (another silly one)
while (i < 10) {
read(a); if (a == 0) { break; }
read(b); if (b == 0) { break; }
i++;
}
Having seen how the backpatchlist code generator routine clevely allows one to have a linked list of forward jumps might inspire you to wonder whether we could not use the same sort of trick to eliminate the forward jumps used earlier to handle the function prototypes. And, of course, we can. Here are extracts from the attribute grammar to show you how easy it all is. In the function parse, in place of
entry.p.defined = false;
if (!entry.p.isMain && !found)
CGen->jump(entry.p.entrypoint, CGen->undefined);
if (!found) Table->enter(entry); .)
we have even less code!
entry.p.defined = false;
**** entry.p.entrypoint = CGen->undefined;
if (!found) Table->enter(entry); .)
At the point where we used to backpatch a forward jump
CGen->backpatch(oldentry.p.entrypoint);
we backpatch a list of forward calls:
**** CGen->backpatchlist(oldentry.p.entrypoint);
To build up the list of forward calls we modify the AssignmentOrCall parser. To the code
| (. if (entry.idclass == TABLE_procs) {
if (entry.p.isMain) SemError(239);
/* Careful - the first argument here is a dummy one! */
else CGen->call(entry.p.entrypoint, entry.p.entrypoint);
}
else SemError(210); .)
"(" ")"
we add one line:
| (. if (entry.idclass == TABLE_procs) {
if (entry.p.isMain) SemError(239);
/* Here is where we create the linked list of forward calls */
else CGen->call(entry.p.entrypoint, entry.p.entrypoint);
**** if (!entry.p.defined) Table->update(entry);
}
else SemError(210); .)
"(" ")"
Easy and elegant, you must admit!
Essentially we want to be able to replace sequences like
ADR -n with PSH -n
VAL
and
ADR -n with Evaluate value
Evaluate value POP -n
STO
where possible. This optimization can only be performed if the address concerned is the address of a scalar - where array manipulations are concerned we have to retain the ADR instructions as part of the code that computes the array element's address at runtime and checks that this is in range.
The Designator actions generate the ADR opcode only if it is needed as part of an array access. Of course we must also distinguish the situations where PSH can be used in place of VAL - this is done in the Factor parser.
In the solution I have taken the opportunity of showing how we might use another compiler pragma ($O+ or $O-) to select whether one wants the optimized code or not. Here are the relevant details
PRAGMAS
**** OptimiseOn = "$O+" . (. CGen->usePopPsh = true; .)
**** OptimiseOff = "$O-" . (. CGen->usePopPsh = false; .)
OneVar<int &framesize, TABLE_types type, int level>
= (. TABLE_entries entry;
TABLE_types exptype; .)
(. entry.idclass = TABLE_vars; entry.v.size = 1;
entry.v.scalar = true; entry.type = type;
entry.v.offset = framesize + 1;
entry.level = level; .)
Ident<entry.name>
[ ArraySize<entry.v.size, level>
(. entry.v.scalar = false; .)
] (. Table->enter(entry);
framesize += entry.v.size;
if (framesize > maxframe) maxframe = framesize; .)
[ AssignOp (. if (!entry.v.scalar) SemError(210);
**** if (!CGen->usePopPsh)
**** CGen->stackaddress(entry.level, entry.v.offset); .)
**** Expression<exptype> (. if (!compatible(entry.type, exptype)) SemError(218);
**** if (CGen->usePopPsh)
**** CGen->store(entry.level, entry.v.offset, entry.type == TABLE_chars);
**** else CGen->assign(entry.type == TABLE_chars); .)
] .
AssignmentOrCall
= (. TABLE_types vartype, exptype;
TABLE_entries entry; .)
Designator<classset(TABLE_vars, TABLE_procs), entry, vartype>
( (. if (entry.idclass != TABLE_vars) SemError(210); .)
( AssignOp
Expression<exptype> (. if (compatible(vartype, exptype))
**** if (entry.v.scalar && CGen->usePopPsh)
**** CGen->store(entry.level, entry.v.offset, entry.type == TABLE_chars);
**** else CGen->assign(vartype == TABLE_chars);
else SemError(218); .)
**** | "++" (. if (entry.v.scalar && CGen->usePopPsh)
**** CGen->stackaddress(entry.level, entry.v.offset);
if (arithtypes.memb(vartype))
CGen->increment(vartype == TABLE_chars);
else SemError(218); .)
**** | "--" (. if (entry.v.scalar && CGen->usePopPsh)
**** CGen->stackaddress(entry.level, entry.v.offset);
if (arithtypes.memb(vartype))
CGen->decrement(vartype == TABLE_chars);
else SemError(218); .)
)
| (. if (entry.idclass == TABLE_procs) {
if (entry.p.isMain) SemError(239);
else CGen->call(entry.p.entrypoint, entry.p.entrypoint);
if (!entry.p.defined) Table->update(entry);
}
else SemError(210); .)
"(" ")"
) WEAK ";" .
Designator<classset allowed, TABLE_entries &entry, TABLE_types &destype>
= (. TABLE_alfa name;
TABLE_types exptype;
bool found; .)
Ident<name> (. Table->search(name, entry, found);
if (!found && isalpha(name[0]))
{ SemError(202); // forced add to table
strcpy(entry.name, name);
entry.idclass = TABLE_vars; entry.v.scalar = true;
entry.v.size = 1; entry.type = TABLE_none;
entry.v.offset = 0; entry.v.canchange = true;
}
if (!allowed.memb(entry.idclass)) SemError(206);
destype = entry.type;
if (entry.idclass != TABLE_vars) return;
**** if (!CGen->usePopPsh)
**** CGen->stackaddress(entry.level, entry.v.offset); .)
( "[" (. if (!found) { entry.v.scalar = false; Table->enter(entry); }
if (entry.v.scalar) SemError(204);
**** if (CGen->usePopPsh)
**** CGen->stackaddress(entry.level, entry.v.offset); .)
Expression<exptype> (. if (!arithtypes.memb(exptype)) SemError(227);
/* determine size for bounds check */
CGen->stackconstant(entry.v.size);
CGen->subscript(); .)
"]"
| (. if (!found) Table->enter(entry);
if (!entry.v.scalar) SemError(205); .)
) .
ReadElement
= (. TABLE_types vartype;
TABLE_entries entry;
char str[600];
CGEN_labels startstring; .)
String<str> (. CGen->stackstring(str, startstring);
CGen->writestring(startstring); .)
|
**** Variable<vartype, entry> (. if (entry.v.scalar && CGen->usePopPsh)
**** CGen->stackaddress(entry.level, entry.v.offset);
switch (vartype)
{ case TABLE_ints : CGen->readintvalue(); break;
case TABLE_bools : CGen->readboolvalue(); break;
case TABLE_chars : CGen->readcharvalue(); break;
case TABLE_none : /* error already */ break;
} .) .
Factor<TABLE_types &f>
= (. int value;
TABLE_entries entry; .)
Designator<classset(TABLE_consts, TABLE_vars), entry, f>
(. switch (entry.idclass)
{ case TABLE_vars :
**** if (entry.v.scalar && CGen->usePopPsh)
**** CGen->stackvalue(entry.level, entry.v.offset);
**** else
**** CGen->dereference(); break;
case TABLE_consts :
CGen->stackconstant(entry.c.value); break;
} .)
| Number<value> (. CGen->stackconstant(value); f = TABLE_ints; .)
| Char<value> (. CGen->stackconstant(value); f = TABLE_chars; .)
| "true" (. CGen->stackconstant(1); f = TABLE_bools .)
| "false" (. CGen->stackconstant(0); f = TABLE_bools .)
| "(" Expression<f> ")" .
Originally I had thought of adding the FOR loop to the practical, but then relented. Since I have a solution to hand, here it is for anyone who is curious. You might like to puzzle it out if you have read this far! It is a rather nasty one, as so many checks are needed, and also because the last part of the control sequence has to be parsed before the Block itself, although of course the corresponding control code has to be executed after the statements for the Block.
ForStatement<int &framesize>
= (. CGEN_labels startloop, testlabel, bodylabel,
startepilogue, oldexit, dummylabel;
TABLE_types controltype, exptype;
TABLE_entries entry1, entry2; .)
"for" WEAK "("
Designator<classset(TABLE_vars), entry1, controltype>
(. if (!entry1.v.scalar || !arithtypes.memb(controltype)
|| entry1.level == global)
SemError(225);
if (!entry1.v.canchange) SemError(229); .)
AssignOp
Expression<exptype> (. if (compatible(controltype, exptype))
if (CGen->usePopPsh)
CGen->store(entry1.level, entry1.v.offset, controltype == TABLE_chars);
else CGen->assign(controltype == TABLE_chars);
else SemError(218);
CGen->storelabel(startloop) .)
WEAK ";" Condition (. CGen->jumponfalse(testlabel, CGen->undefined); .)
[ ";" (. CGen->jump(bodylabel, CGen->undefined);
CGen->storelabel(startepilogue); .)
Designator<classset(TABLE_vars), entry2, controltype>
(. if (strcmp(entry1.name, entry2.name))
SemError(226); .)
( AssignOp
Expression<exptype> (. if (compatible(controltype, exptype))
if (CGen->usePopPsh)
CGen->store(entry2.level, entry2.v.offset, controltype == TABLE_chars);
else CGen->assign(controltype == TABLE_chars);
else SemError(218); .)
| "++" (. if (CGen->usePopPsh)
CGen->stackaddress(entry2.level, entry2.v.offset);
CGen->increment(controltype == TABLE_chars); .)
| "--" (. if (CGen->usePopPsh)
CGen->stackaddress(entry2.level, entry2.v.offset);
CGen->decrement(controltype == TABLE_chars); .)
) (. CGen->jump(dummylabel, startloop);
CGen->backpatch(bodylabel);
startloop = startepilogue; .)
]
")" (. looplevel++; oldexit = loopexit;
loopexit = CGen->undefined;
Table->protect(entry1) .)
Block<framesize> (. CGen->jump(dummylabel, startloop);
CGen->backpatch(testlabel);
CGen->backpatchlist(loopexit);
loopexit = oldexit; looplevel--;
Table->unprotect(entry1); .) .