Sources of full solutions for these problems may be found on the course web page as the file PRAC25A.ZIP (Java) or PRAC25AC.ZIP (C#).
The extra pragmas needed in the refined Parva compiler are easily introduced. We need some static fields:
public static boolean
debug = false,
listCode = false,
warnings = true;
The definitions of the pragmas are done in terms of these:
PRAGMAS
DebugOn = "$D+" . (. debug = true; .)
DebugOff = "$D-" . (. debug = false; .)
WarnOn = "$W+" . (. warnings = true; .)
WarnOff = "$W-" . (. warnings = false; .)
CodeOn = "$C+" . (. listCode = true; .)
CodeOff = "$C-" . (. listCode = false; .)
It is convenient to be able to set the options with command line parameters as well. This involves a straightforward change to the Parva.frame file:
for (int i = 0; i < args.length; i++) {
if (args[i].toLowerCase().equals("-l")) mergeErrors = true;
else if (args[i].toLowerCase().equals("-d")) Parser.debug = true;
** else if (args[i].toLowerCase().equals("-w")) Parser.warnings = false;
** else if (args[i].toLowerCase().equals("-c")) Parser.listCode = true;
else inputName = args[i];
}
if (inputName == null) {
System.err.println("No input file specified");
System.err.println("Usage: Parva [-l] [-d] [-w] [-c] source.pav [-l] [-d] [-w] [-c] ");
System.err.println("-l directs source listing to listing.txt");
System.err.println("-d turns on debug mode");
** System.err.println("-w suppresses warnings");
** System.err.println("-c lists object code (.cod file)");
** System.exit(1);
}
Finally, the following change to the frame file gives the option of suppressing the generation of the .COD listing.
if (Parser.listCode) PVM.listCode(codeName, codeLength);
To be as sympathetic as possible in the face of confusion between various operators is easily handled - we make the parsers that identify these operators accept the incorrect ones, at the expense of generating an error message (or, if you want to be really kind, issue a warning only):
EqualOp<out int op> (. op = CodeGen.nop; .)
= "==" (. op = CodeGen.ceq; .)
| "!=" (. op = CodeGen.cne; .)
** | "=" (. SemError("== intended?"); .)
** | "<>" (. SemError("!= intended?"); .) .
AssignOp
** = "="
** | ":=" (. SemError("= intended?"); .) .
Similarly, recovering from the spurious intoduction of then into an IfStatement is quite easily achieved:
IfStatement<StackFrame frame> (. Label falseLabel = new Label(!known); .)
= "if" "(" Condition ")" (. CodeGen.branchFalse(falseLabel); .)
** [ "then" (. SemError("then is not used in Parva"); .)
] Statement<frame> (. falselabel.here(); .) .
The suggestion was made that when an identifier was not found in the symbol table, a suitable entry could quietly be inserted into the table in the hope of reducing the number of irritating "undeclared identifier" messages that might otherwise pop up. This is quite easily done from within the production for Designator. Note the way in which we modify the newly inserted entry if we establish that the undeclared identifier appears to be of a reference type.
Designator<out DesType des> (. String name;
int indexType; .)
= Ident<out name> (. Entry entry = Table.find(name);
** boolean notDeclared = !entry.declared;
** if (notDeclared) {
** SemError("undeclared identifier");
** entry = new Entry(); // new is critical
** entry.name = name;
** entry.kind = Entry.Var;
** entry.type = Entry.noType;
** entry.offset = 0;
** Table.insert(entry);
** }
des = new DesType(entry);
if (entry.kind == Entry.Var) CodeGen.loadAddress(entry); .)
** [ "[" (. if (notDeclared) entry.type++;
** else if (isRef(des.type)) des.type--;
else SemError("unexpected subscript");
if (entry.kind != Entry.Var)
SemError("unexpected subscript");
CodeGen.dereference(); .)
Expression<out indexType> (. if (!isArith(indexType)) SemError("invalid subscript type");
CodeGen.index(); .)
"]"
] .
Adding the basic Repeat loop to Parva is very easy, since all that is needed is a "backward" branch.
** RepeatStatement<StackFrame frame> (. Label startLoop = new Label(known); .)
** = "repeat" { Statement<frame> }
** "until" "(" Condition ")" WEAK ";" (. CodeGen.branchFalse(startLoop); .) .
Adding the optional, possibly repeated, elsif clauses requires a little care to make sure that the correct sequence of branches is generated. It is possible, of course, that the outLabel will turn out never to have been "used", but fortunately the here method of the Label class takes this in its stride!
IfStatement<StackFrame frame> (. Label falseLabel = new Label(!known);
** Label outLabel = new Label(!known); .)
= "if" "(" Condition ")" (. CodeGen.branchFalse(falseLabel); .)
[ "then" (. SemError("then is not used in Parva"); .)
] Statement<frame>
** { (. CodeGen.branch(outLabel);
** falseLabel.here();
** falseLabel = new Label(!known); .)
** "elsif" "(" Condition ")" (. CodeGen.branchFalse(falseLabel); .)
** [ "then" (. SemError("then is not used in Parva"); .)
** ] Statement<frame>
** }
** ( "else" (. CodeGen.branch(outLabel);
** falseLabel.here(); .)
** Statement<frame>
** | /* no else part */ (. falseLabel.here(); .)
** ) (. outLabel.here(); .) .
Most submissions, however, were on the lines of the production below. This "works", but can generate BRN instructions where none are needed. For example, source code like
if (i == 12) k = 56;
leads to object code like
12 LDA 0
14 LDV
15 LDC 12
17 CEQ
18 BZE 27
20 LDA 5
22 LDC 56
24 STO
25 BRN 27 // unnecessary
27 ....
IfStatement<StackFrame frame> (. Label falseLabel = new Label(!known);
Label outLabel = new Label(!known); .)
= "if" "(" Condition ")" (. CodeGen.branchFalse(falseLabel); .)
[ "then" (. SemError("then is not used in Parva"); .)
** ] Statement<frame> (. CodeGen.branch(outLabel);
falseLabel.here(); .)
{ "elsif" "(" Condition ")" (. falseLabel = new Label(!known);
CodeGen.branchFalse(falseLabel); .)
[ "then" (. SemError("then is not used in Parva"); .)
** ] Statement<frame> (. CodeGen.branch(outLabel);
falseLabel.here(); .)
}
[ "else" Statement<frame> ] (. outLabel.here(); .) .
The syntax of the BreakStatement is, of course, trivial. The catch is that one has to allow these statements only in the context of loops. To find a context-free grammar with this restriction is not worth the effort. As with nested comments in languages that allow them, it is easier just to have a (global) counter that is incremented and decremented as parsing of loops starts and finishes.
However, loops must be handled in a way that allows them to be nested, with all the breaks in each loop directed at the correct place for that loop - and many of these involve forward references. As it happens, the Label class we already use allows for this to be handled neatly, and we can get away with using a global label. However, we need a little local stack to be introduced in each loop parsing production, so that this global label can be kept up to date.
Once you have seen the solution it probably looks almost obvious. One way is as follows: Extra static fields are declared in the parser (declared at the top of the ATG file):
** static int loopLevel = 0; // = 0 outside of loops, > 0 inside loops ** static Label loopExit = new Label(!known); // current target for "break" statements
and the production for the BreakStatement then follows as
BreakStatement
** = "break" (. if (loopLevel == 0)
** SemError("break is not within a loop");
** CodeGen.branch(loopExit); .)
** WEAK ";" .
The WhileStatement and RepeatStatement productions now have quite a lot of extra actions:
** WhileStatement<StackFrame frame> (. loopLevel++;
** Label oldExit = loopExit;
** loopExit = new Label(!known);
Label startLoop = new Label(known); .)
= "while" "(" Condition ")" (. CodeGen.branchFalse(loopExit); .)
Statement<frame> (. CodeGen.branch(startLoop);
** loopExit.here();
** loopExit = oldExit;
** loopLevel--; .) .
** RepeatStatement<StackFrame frame> (. loopLevel++;
** Label oldExit = loopExit;
** loopExit = new Label(!known);
Label startLoop = new Label(known); .)
= "repeat" { Statement<frame> }
WEAK "until"
"(" Condition ")" WEAK ";" (. CodeGen.branchFalse(startLoop);
** loopExit.here();
** loopExit = oldExit;
** loopLevel--; .) .
Another solution, which some might think of, dispenses with the counter by initializing loopExit to null:
** static Label loopExit = null; // current target for "break" statements
and the production for the BreakStatement follows as
BreakStatement
** = "break" (. if (loopExit == null)
** SemError("break is not within a loop");
** else CodeGen.branch(loopExit); .)
** WEAK ";" .
And, for example the RepeatStatement production now becomes:
** RepeatStatement<StackFrame frame> (. Label oldExit = loopExit;
** loopExit = new Label(!known);
Label startLoop = new Label(known); .)
= "repeat" { Statement<frame> }
WEAK "until"
"(" Condition ")" WEAK ";" (. CodeGen.branchFalse(startLoop);
** loopExit.here();
** loopExit = oldExit; .)
It might not at first have been obvious, but hopefully everyone eventually saw that this extension is handled by clever modifications to the Assignment production, which has to be factorized in such a way as to avoid LL(1) conflicts. The code below achieves all this (including the tests for compatibility that some students probably omitted) by assuming the existence of a few new machine opcodes, as suggested in the textbook.
Assignment (. int expType;
DesType des; .)
= Designator<out des> (. if (des.entry.kind != Entry.Var)
SemError("invalid assignment"); .)
** ( AssignOp
** Expression<out expType> (. if (!assignable(des.type, expType))
** SemError("incompatible types in assignment");
** CodeGen.assign(des.type); .)
** | "++" (. if (!isArith(des.type))
** SemError("arithmetic destination needed");
** CodeGen.increment(des.type); .)
** | "--" (. if (!isArith(des.type))
** SemError("arithmetic destination needed");
** CodeGen.decrement(des.type); .)
** )
WEAK ";" .
while the prefix forms of the statements are somewhat easier:
IncOrDecStatement (. DesType des;
boolean inc = true; .)
= ( "++" | "--" (. inc = false; .)
) Designator<out des> (. if (des.entry.kind != Entry.Var)
SemError("invalid assignment");
if (!isArith(des.type))
SemError("arithmetic destination required");
if (inc) CodeGen.increment(des.type);
else CodeGen.decrement(des.type); .)
WEAK ";" .
The extra code generation routines are straightforward:
public static void increment(int type) {
// Generates code to increment the value found at the address currently
// stored at the top of the stack.
emit(PVM.inc);
}
public static void decrement(int type) {
// Generates code to decrement the value found at the address currently
// stored at the top of the stack.
emit(PVM.dec);
}
As usual, the extra opcodes in the PVM make all this easy to achieve at run time. Some submissions might have forgotten to include the check that the address was "in bounds". I suppose one could argue that if the source program were correct, then the addresses could not go out of bounds, but if the interpreter were to be used in conjunction with a rather less fussy assembler (as we had in earlier practicals) it would make sense to be cautious.
case PVM.inc: // int ++
adr = pop();
if (inBounds(adr)) mem[adr]++;
break;
case PVM.dec: // int --
adr = pop();
if (inBounds(adr)) mem[adr]--;
break;
This was the biggest "hack" in this practical, but was hopefully straightforward, since you had been given the unattributed grammar in which the required operator precedence levels had already been sorted out for you. The code follows - note how the short-circuit semantics are achieved for the Boolean operators:
Expression<out int type> (. int type2;
Label shortcircuit = new Label(!known); .)
= AndExp<out type>
{ "||" (. CodeGen.booleanOp(shortcircuit, CodeGen.or); .)
AndExp<out type2> (. if (!isBool(type) || !isBool(type2))
SemError("Boolean operands needed");
type = Entry.boolType; .)
} (. shortcircuit.here(); .)
.
AndExp<out int type> (. int type2;
Label shortcircuit = new Label(!known); .)
= EqlExp<out type>
{ "&&" (. CodeGen.booleanOp(shortcircuit, CodeGen.and); .)
EqlExp<out type2> (. if (!isBool(type) || !isBool(type2))
SemError("Boolean operands needed");
type = Entry.boolType; .)
} (. shortcircuit.here(); .)
.
EqlExp<out int type> (. int type2;
int op; .)
= RelExp<out type>
{ EqualOp<out op>
RelExp<out type2> (. if (!compatible(type, type2))
SemError("incomparable operands");
type = Entry.boolType; CodeGen.comparison(op); .)
} .
RelExp<out int type> (. int type2;
int op; .)
= AddExp<out type>
[ RelOp<out op>
AddExp<out type2> (. if (!isArith(type) || !isArith(type2))
SemError("incomparable operands");
type = Entry.boolType; CodeGen.comparison(op); .)
] .
AddExp<out int type> (. int type2;
int op; .)
= MultExp<out type>
{ AddOp<out op>
MultExp<out type2> (. if (!isArith(type) || !isArith(type2)) {
SemError("arithmetic operands needed");
type = Entry.noType;
}
CodeGen.binaryOp(op); .)
} .
MultExp<out int type> (. int type2;
int op; .)
= Factor<out type>
{ MulOp<out op>
Factor<out type2> (. if (!isArith(type) || !isArith(type2)) {
SemError("arithmetic operands needed");
type = Entry.noType;
}
CodeGen.binaryOp(op); .)
} .
Factor<out int type> (. type = Entry.noType; .)
= Primary<out type>
| "+" Factor<out type> (. if (!isArith(type)) {
SemError("arithmetic operand needed");
type = Entry.noType;
} .)
| "-" Factor<out type> (. if (!isArith(type)) {
SemError("arithmetic operand needed");
type = Entry.noType;
}
CodeGen.negateInteger(); .)
| "!" Factor<out type> (. if (!isBool(type))
SemError("Boolean operand needed");
type = Entry.boolType; CodeGen.negateBoolean(); .)
.
Primary<out int type> (. type = Entry.noType;
int size;
DesType des;
ConstRec con; .)
= Designator<out des> (. type = des.type;
switch (des.entry.kind) {
case Entry.Var:
CodeGen.dereference();
break;
case Entry.Con:
CodeGen.loadConstant(des.entry.value);
break;
default:
SemError("wrong kind of identifier");
break;
} .)
| Constant<out con> (. type = con.type;
CodeGen.loadConstant(con.value); .)
| "new" BasicType<out type> (. type++; .)
"[" Expression<out size> (. if (!isArith(size))
SemError("array size must be integer");
CodeGen.allocate(); .)
"]"
| "(" Expression<out type> ")"
.
Notice carefully how the detection of a type incompatibility in some cases is accompanied by forcing the expression or sub-expression to be of the noType type, and sometimes of the boolType type. This has been done to try to minimize the number of error messages thereafter. You might like to think whether this is a good strategy, or whether it could be improved still further.
We have to refactor the productions defining the various operators in a slightly different way as well:
AddOp<out int op> (. op = CodeGen.nop; .)
= "+" (. op = CodeGen.add; .)
| "-" (. op = CodeGen.sub; .)
.
MulOp<out int op> (. op = CodeGen.nop; .)
= "*" (. op = CodeGen.mul; .)
| "/" (. op = CodeGen.div; .)
| "%" (. op = CodeGen.rem; .)
.
EqualOp<out int op> (. op = CodeGen.nop; .)
= "==" (. op = CodeGen.ceq; .)
| "!=" (. op = CodeGen.cne; .)
| "=" (. SemError("== intended?"); .)
| "<>" (. SemError("!= intended?"); .)
.
RelOp<out int op> (. op = CodeGen.nop; .)
= "<" (. op = CodeGen.clt; .)
| "<=" (. op = CodeGen.cle; .)
| ">" (. op = CodeGen.cgt; .)
| ">=" (. op = CodeGen.cge; .)
.
These extensions are handled by further modifications to the Assignment production. The code below shows this (including the tests for compatibility that some students omitted) by assuming the existence of the DUP opcode, as suggested in the textbook.
For the boolean assignment operators &= and |= we have to make sure that we generate "short circuit" operations. This adds a bit to the apparent complexity of the production, as you can see below:
Assignment (. int expType;
DesType des;
int op;
Label shortcircuit = new Label(!known);.)
= Designator<out des> (. if (des.entry.kind != Entry.Var)
SemError("invalid assignment"); .)
( AssignOp<out op> (. switch (op) {
case CodeGen.nop:
break;
case CodeGen.add:
case CodeGen.sub:
case CodeGen.mul:
case CodeGen.div:
case CodeGen.rem:
if (!isArith(des.type))
SemError("arithmetic destination required");
CodeGen.duplicate();
CodeGen.dereference();
break;
case CodeGen.and:
case CodeGen.or:
if (!isBool(des.type))
SemError("boolean destination required");
CodeGen.duplicate();
CodeGen.dereference();
CodeGen.booleanOp(shortcircuit, op);
break;
} .)
Expression<out expType> (. if (!compatible(des.type, expType))
SemError("incompatible types in assignment");
switch (op) {
case CodeGen.nop:
break;
case CodeGen.and:
case CodeGen.or:
shortcircuit.here();
break;
case CodeGen.add:
case CodeGen.sub:
case CodeGen.mul:
case CodeGen.div:
case CodeGen.rem:
CodeGen.binaryOp(op);
break;
}
CodeGen.assign(des.type); .)
| "++" (. if (!isArith(des.type))
SemError("arithmetic destination required");
CodeGen.increment(des.type); .)
| "--" (. if (!isArith(des.type))
SemError("arithmetic destination required");
CodeGen.decrement(des.type); .)
)
WEAK ";" .
The AssignOp production is rather more complex than before. It returns the associated binary operation that will be needed in the compound assignment operations.
AssignOp<out int op> (. op = CodeGen.nop; .)
= "="
| ":=" (. SemError("= intended?"); .)
| "+=" (. op = CodeGen.add; .)
| "-=" (. op = CodeGen.sub; .)
| "*=" (. op = CodeGen.mul; .)
| "/=" (. op = CodeGen.div; .)
| "%=" (. op = CodeGen.rem; .)
| "&=" (. op = CodeGen.and; .)
| "|=" (. op = CodeGen.or; .)
.
The extra code generation routine needed is straightforward:
public static void duplicate() {
// Generates code to push another copy of top of stack
emit(PVM.dup);
}
As usual, the extra opcodes in the PVM make all this easy to achieve at run time. Many submission forgot to include the check that the address was "in bounds". I suppose one could argue that if the source program were correct, then the addresses could not go out of bounds, but if the interpreter were to be used in conjunction with a rather less fussy assembler (as we had in earlier practicals) it would make sense to be cautious.
case PVM.dup: // duplicate top of stack
cpu.sp--;
if (inBounds(cpu.sp)) mem[cpu.sp] = mem[cpu.sp + 1];
break;
Based on the discussion in the tutorial, here is a solution to the problem of adding a ForStatement loop to Parva:
ForStatement<StackFrame frame> (. boolean up = true;
int expType;
String name;
loopLevel++;
Label oldExit = loopExit;
loopExit = new Label(!known); .)
= "for" Ident<out name> (. Entry control = Table.find(name);
if (!control.declared) {
SemError("undeclared identifier");
control = new Entry(); // new is critical
control.name = name;
control.kind = Entry.Var;
control.type = Entry.noType;
control.offset = 0;
Table.insert(control);
}
if (isRef(control.type) || control.kind != Entry.Var)
SemError("illegal control variable");
CodeGen.loadAddress(control); .)
"=" Expression<out expType> (. if (!compatible(expType, control.type))
SemError("incompatible with control variable"); .)
( "to" | "downto" (. up = false; .)
)
Expression<out expType> (. if (!compatible(expType, control.type))
SemError("incompatible with control variable");
CodeGen.startForLoop(up, loopExit);
Label startLoop = new Label(known); .)
Statement<frame> (. CodeGen.endForLoop(up, startLoop);
loopExit.here();
CodeGen.pop3();
loopExit = oldExit;
loopLevel--; .)
.
This solution includes the possibility of the loop body incorporating one or more BreakStatements, and also handles the problem of the undeclared control variable by entering it into the symbol table.
The extra code generating methods are as follows:
public static void startForLoop(boolean up, Label destination) {
// Generates prologue test for a for loop (either up or down)
if (up) emit(PVM.sfu); else emit(PVM.sfd);
emit(destination.address());
}
public static void endForLoop(boolean up, Label destination) {
// Generates epilogue test and increment/decrement for a for loop (either up or down)
if (up) emit(PVM.efu); else emit(PVM.efd);
emit(destination.address());
}
public static void pop3() {
// Generates code to discard top three elements from the stack
emit(PVM.pop3);
}
and, finally, the magic that makes this all work efficiently is achieved with the new opcodes that are interpreted as follows:
case PVM.sfu: // start for loop "to"
if (mem[cpu.sp + 1] > mem[cpu.sp]) cpu.pc = mem[cpu.pc];
else {
mem[mem[cpu.sp + 2]] = mem[cpu.sp + 1]; cpu.pc++;
}
break;
case PVM.sfd: // start for loop "downto"
if (mem[cpu.sp + 1] < mem[cpu.sp]) cpu.pc = mem[cpu.pc];
else {
mem[mem[cpu.sp + 2]] = mem[cpu.sp + 1]; cpu.pc++;
}
break;
case PVM.efu: // end for loop "to"
if (mem[mem[cpu.sp + 2]] == mem[cpu.sp]) cpu.pc++;
else {
mem[mem[cpu.sp + 2]]++; cpu.pc = mem[cpu.pc];
}
break;
case PVM.efd: // end for loop "downto"
if (mem[mem[cpu.sp + 2]] == mem[cpu.sp]) cpu.pc++;
else {
mem[mem[cpu.sp + 2]]--; cpu.pc = mem[cpu.pc];
}
break;
case PVM.pop3: // discard 3 elements from top of stack
cpu.sp += 3;
break;