Sources of full solutions for these problems may be found on the course web page as the files PRAC25A.ZIP (Java) and PRAC25AC.ZIP (C#).
This prac was handled very well by a few groups, but in some cases virtually no effort seemed to have been made. This surely represents a sadly lost opportunity to extract a great deal of insight into the compilation proces.
A subtle point that virtually nobody seems to have picked up is that it is possible to supply an "action" to an empty alternative in a grammar. Many people wrote code like this
Something (. boolean seenSecond = false; .)
= First
[ Second (. HandleSecond();
seenSecond = true; .)
] (. if (!seenSecond) HandleNoSecond(); .)
Third .
but this may be more easily handled sometimes as follows:
Something (. boolean seenSecond = false; .)
= First
( Second (. HandleSecond(); .)
| /*nothing */ (. HandleNoSecond(); .)
)
Third .
This technique is used to good effect in several place in the solutions below.
These solutions are developed in the order the tasks were set, in each case making no use of ideas that were to follow. The complete solution in the kit, however, puts all the pieces together consistently.
The extra pragmas needed in the refined Parva compiler are easily introduced. We need some static fields:
public static boolean
debug = false,
optimize = 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; .)
** CodeOn = "$C+" . (. listCode = true; .)
** CodeOff = "$C-" . (. listCode = false; .)
** OptimizeOn = "$O+" . (. optimize = true; .)
** OptimizeOff = "$O-" . (. optimize = 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 if (args[i].toLowerCase().equals("-o")) Parser.optimize = true;
else inputName = args[i];
}
if (inputName == null) {
System.err.println("No input file specified");
** System.err.println("Usage: Parva [-l] [-d] [-w] [-c] [-o] source.pav [-l] [-d] [-w] [-c] [-o]");
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.err.println("-o optimized code");
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(); .) .
Several people made heavy weather of this, or missed the point, which is that one can dispense with the old ConstDeclarations completely and allow code like
const int maxPlus10 = max + 10;
with a general Expression after the assignment operator. This is achieved by allowing the optional const before a variable declaration to set a flag that can be passed down to the OneVar parser. The symbol table entries are extended to record this flag (full details can be found in the full source kit).
VarDeclarations<StackFrame frame> (. int type;
** boolean canChange = true; .)
** = [ "const" (. canChange = false; .)
] Type<out type>
** OneVar<frame, type, canChange>
** { WEAK "," OneVar<frame, type, canChange> }
WEAK ";" .
Care must be taken - if a variable is marked const then the defining expression must be present:
** OneVar<StackFrame frame, int type, boolean canChange>
(. int expType; .)
= (. Entry var = new Entry(); .)
Ident<out var.name> (. var.kind = Entry.Var;
var.type = type;
** var.canChange = canChange;
var.offset = frame.size;
frame.size++; .)
( AssignOp (. CodeGen.loadAddress(var); .)
Expression<out expType> (. if (!compatible(var.type, expType))
SemError("incompatible types in assignment");
CodeGen.assign(var.type); .)
** | (. if (!canChange)
** SemError("defining expression required"); .)
) (. Table.insert(var); .) .
Within the productions for Assignment and ReadElement it is then necessary to test whether the variable that is associated with the relevant designator can be changed. This is best achieved by extending the DesType class to record whether one may alter this variable.
class DesType {
// Objects of this type are associated with l-value and r-value designators
public Entry entry; // the identifier properties
public int type; // designator type (not always the entry type)
** public boolean canChange;
public boolean isSimple; // true unless it is an indexed designator
public DesType(Entry entry) {
this.entry = entry;
this.type = entry.type;
** this.canChange = entry.canChange;
}
} // end DesType
This is more subtle than one may realize. If the reference to an array is marked constant, this does not preclude altering the individual elements within the array, and this is achieved once the indexing expression is recognized:
Designator<out DesType des> (. String name;
int indexType; .)
= Ident<out name> (. Entry entry = Table.find(name);
if (!entry.declared)
SemError("undeclared identifier");
des = new DesType(entry);
if (entry.kind == Entry.Var) CodeGen.loadAddress(entry); .)
** [ "[" (. des.canChange = true; // elements may be altered
if (isRef(des.type)) des.type--;
else SemError("unexpected subscript");
if (entry.kind != Entry.Var)
SemError("unexpected subscript");
des.isValue = false;
CodeGen.dereference(); .)
Expression<out indexType> (. if (!isArith(indexType)) SemError("invalid subscript type");
CodeGen.index(); .)
"]"
] .
The productions for Assignment and ReadElement then become
Assignment (. int expType;
DesType des; .)
= Designator<out des> (. if (des.entry.kind != Entry.Var)
SemError("invalid assignment");
** if (!des.canChange)
** SemError("may not alter this variable"); .)
AssignOp
Expression<out expType> (. if (!compatible(des.type, expType))
SemError("incompatible types in assignment");
CodeGen.assign(des.type); .)
WEAK ";" .
ReadElement (. String str;
DesType des; .)
= StringConst<out str> (. CodeGen.writeString(str); .)
| Designator<out des> (. if (des.entry.kind != Entry.Var)
SemError("wrong kind of identifier");
** if (!des.canChange)
** SemError("may not alter this variable");
switch (des.type) {
case Entry.intType:
case Entry.boolType:
CodeGen.read(des.type); break;
default:
SemError("cannot read this type"); break;
} .) .
Incorporating the Pascal-like specification of a field width for output is quite easy. One extends the semantics of the PRNI and PRNB opcodes so that they will pop two values off the stack - the first being the fieldwidth and the second being the value to print. The OutFile.write methods had already been overloaded to handle this idea:
case PVM.prni: // integer output
if (tracing) results.write(padding);
** fieldWidth = pop();
** results.write(pop(), fieldWidth);
if (tracing) results.writeLine();
break;
case PVM.prnb: // boolean output
if (tracing) results.write(padding);
** fieldWidth = pop();
** if (pop() != 0) results.write(" true ", fieldWidth);
** else results.write(" false ", fieldWidth);
if (tracing) results.writeLine();
break;
Ensuring that the two values would be available on the stack is easily achieved as shown below. Note that if the optional fieldwidth expression is omitted, code to push a default fieldwidth of 0 is generated instead. Also note how and where the necessary type checking is introduced.
WriteElement (. int expType, formType;
String str; .)
= StringConst<out str> (. CodeGen.writeString(str); .)
** | Expression<out expType> (. if (!isArith(expType) && !isBool(expType))
** SemError("cannot write this type"); .)
** ( ":" Expression<out formType> (. if (formType != Entry.intType)
** SemError("fieldwidth must be integral"); .)
** | (. CodeGen.loadConstant(0); // default .)
** ) (. switch (expType) {
case Entry.intType:
case Entry.boolType:
CodeGen.write(expType); break;
default:
break;
} .) .
Adding the basic Repeat loop to Parva is very easy too, 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); .) .
It might not at first have been obvious, but hopefully everyone eventually saw that all this extension is handled by a clever modification to the Assignment production, which has to be factorized to avoid LL(1) conflicts.
Assignment (. int expType;
DesType des; .)
= Designator<out des> (. if (des.entry.kind != Entry.Var)
SemError("invalid assignment");
if (!des.canChange)
SemError("may not alter this variable"); .)
( AssignOp
Expression<out expType> (. if (!compatible(des.type, expType))
SemError("incompatible types in assignment");
CodeGen.assign(des.type); .)
** | "++" (. if (!isArith(des.type))
** SemError("arithmetic type needed");
** CodeGen.increment(des.type); .)
** | "--" (. if (!isArith(des.type))
** SemError("arithmetic type needed");
** CodeGen.decrement(des.type); .)
) WEAK ";" .
The extra code generating methods are almost trivial. Several submissions simply added the inc and dec operators into the switch statement for the method for binaryOperation, but this is misleading - these are not binary (infix) operators.
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);
}
Adding an else option to the IfStatement is easy once you see the trick! Note the use of the "no else part" option associated with an action, even in the absence of any terminals or non-terminals. As mentioned earlier, this is a very useful trick to remember.
IfStatement<StackFrame frame> (. Label falseLabel = new Label(!known); .)
= "if" "(" Condition ")" (. CodeGen.branchFalse(falseLabel); .)
Statement<frame>
** ( "else" (. Label outLabel = new Label(!known);
** CodeGen.branch(outLabel);
** falseLabel.here(); .)
** Statement<frame> (. outLabel.here(); .)
** | /* no else part */ (. falseLabel.here(); .)
** ) .
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 I had not thought 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; .)
(I mentioned before that it is always fun to be presented with neat solutions that one had not thought of previously. Well done, guys!)
The GoToStatement and labels are most simply introduced as two distinct statement forms. The algorithms needed to handle this rather frowned-upon construct are essentially to be found in chapter 11.5:
** GoToStatement (. Label lab;
** int target; .)
** = "goto" IntConst<out target> ";" (. LabEntry labelEntry = LabelTable.find(target);
** if (labelEntry == null) {
** lab = new Label(!known);
** LabelTable.insert(new LabEntry(target, lab));
** }
** else lab = labelEntry.label;
** CodeGen.branch(lab); .) .
**
** Lab (. int label; .)
** = IntConst<out label> (. LabEntry labelEntry = LabelTable.find(label);
** if (labelEntry == null)
** LabelTable.insert(new LabEntry(label, new Label(known)));
** else if (labelEntry.label.isDefined())
** SemError("label already defined");
** else labelEntry.label.here(); .) .
It is also necessary to introduce a test that all labels have been properly defined by the end of compilation. You can hunt through the full solution to see where this is done at the end of the Parva production.
As stated in the prac sheet, this is something that must be done with great care. Various of the productions - Assignment, OneVar, Designator and Primary need alteration. The trick is to modify the Designator production so that it does not generate the LDA opcode immediately. But we need to distinguish between designators that correspond to "simple" variables that are to be manipulated with the LDL and STL opcodes, and array elements which will still require use of LDV and STO opcodes. So the DesType class is extended yet again:
class DesType {
// Objects of this type are associated with l-value and r-value designators
public Entry entry; // the identifier properties
public int type; // designator type (not always the entry type)
** public boolean canChange;
** public boolean isSimple; // true unless it is an indexed designator
public DesType(Entry entry) {
this.entry = entry;
this.type = entry.type;
** this.canChange = entry.canChange;
** this.isSimple = true;
}
} // end DesType
The Designator production is now attributed as follows - note in particular where the code generation occurs:
Designator<out DesType des> (. string name;
int indexType; .)
= Ident<out name> (. Entry entry = Table.find(name);
if (!entry.declared)
SemError("undeclared identifier");
des = new DesType(entry); .)
[ "[" (. des.canChange = true;
if (isRef(des.type)) des.type--;
else SemError("unexpected subscript");
if (entry.kind != Entry.Var)
SemError("unexpected subscript");
** des.isSimple = false;
** CodeGen.loadValue(entry); .)
Expression<out indexType> (. if (!isArith(indexType)) SemError("invalid subscript type");
** CodeGen.index(); .)
"]"
] .
Within the Primary production, when a Designator is parsed one must either complete the array access by generating the LDV opcode, or generate the LDL opcode.
Primary<out int type> (. int value = 0;
type = Entry.noType;
int size;
DesType des;
ConstRec con; .)
= Designator<out des> (. type = des.type;
switch (des.entry.kind) {
case Entry.Var:
** if (des.isSimple) CodeGen.loadValue(des.entry);
** else CodeGen.dereference();
break;
default:
SemError("wrong kind of identifier");
break;
} .)
| Constant<out con> ... // as before .
When variables are declared we can always make use of the LDL code if they are initialized:
OneVar<StackFrame frame, int type, bool canChange>
(. int expType; .)
= (. Entry var = new Entry(); .)
Ident<out var.name> (. var.kind = Entry.Var;
var.type = type;
var.canChange = canChange;
var.offset = frame.size;
frame.size++; .)
( AssignOp
Expression<out expType> (. if (!compatible(var.type, expType))
SemError("incompatible types in assignment");
** CodeGen.storeValue(var); .)
| (. if (!canChange)
SemError("defining expression required"); .)
) (. Table.insert(var); .)
.
The production for ReadElement will have to generate the LDA opcode if the element to be read is a simple variable:
ReadElement (. string str;
DesType des; .)
= StringConst<out str> (. CodeGen.writeString(str); .)
| Designator<out des> (. if (des.entry.kind != Entry.Var)
SemError("wrong kind of identifier");
if (!des.canChange)
SemError("may not alter this variable");
** if (des.isSimple) CodeGen.loadAddress(des.entry);
switch (des.type) {
... // as before
Similarly, the production for Assignment may have to generate the LDA opcode if the ++ or --operation is applied to simple variables, and to choose between generating the STL or STO opcodes for regular assignment statements:
Assignment (. int expType;
DesType des; .)
= Designator<out des> (. if (des.entry.kind != Entry.Var)
SemError("invalid assignment");
if (!des.canChange)
SemError("may not alter this variable"); .)
( AssignOp
Expression<out expType> (. if (!compatible(des.type, expType))
SemError("incompatible types in assignment");
** if (des.isSimple) CodeGen.storeValue(des.entry);
** else CodeGen.assign(des.type); .)
** | "++" (. if (des.isSimple) CodeGen.loadAddress(des.entry);
if (!isArith(des.type))
SemError("arithmetic type needed");
CodeGen.increment(des.type); .)
** | "--" (. if (des.isSimple) CodeGen.loadAddress(des.entry);
if (!isArith(des.type))
SemError("arithmetic type needed");
CodeGen.decrement(des.type); .)
)
WEAK ";" .
Just for further interest, the full solution in the solution kit allows the user to choose between "optimized" and "regular" old-style code by using a pragma $O+ or command line option -o.
Only two groups seemed to try this; and one gave up the (unequal?) struggle. It's trickier than it at first appears, and may not really be worth the effort. Here is how I did it. I added another field to the Label class to record whether a label had actually been used (because my IfStatement parser allowed for the outLabel to be declared, but possibly never used, and one would have been in severe trouble fixing a list of forward references if this list had never been in fact created).
class Label {
private int memAdr; // address if this.defined, else last forward reference
private boolean defined; // true once this.memAdr is known
** private boolean used; // true once a reference has been made to this label
public Label(boolean known) {
// Constructor for label, possibly at already known location
if (known) this.memAdr = CodeGen.getCodeLength();
this.defined = known;
** this.used = false;
}
The first forward reference has to be treated as a special case:
public int address() {
// Returns memAdr if known, otherwise effectively adds to a forward reference
// chain that will be resolved if and when here() is called and returns the
// address of the most recent forward refernce
** if (!used && !defined) memAdr = CodeGen.getCodeLength(); // first forward reference
int adr = memAdr;
used = true;
if (!defined) memAdr = CodeGen.getCodeLength(); // subsequent forward references
return adr;
}
and the Label.here method does not start the CodeGen.backPatch sequence if the label was never used:
public void here() {
// Defines memAdr of this label to be at current location counter after fixing
// any outstanding forward references
if (defined) Parser.SemError("redefined label");
** else if (used) CodeGen.backPatch(memAdr); // don't touch if it was not used
memAdr = CodeGen.getCodeLength();
defined = true;
}
The CodeGen.backPatch method has to be able to detect the circular link on the last (or perhaps only) branch instruction to be repaired:
public static void backPatch(int adr) {
// Stores the current location counter as the address field of the branch or call
// instruction currently holding a forward reference to adr and repeatedly
// works through a linked list of such instructions
** int visited, nextAdr;
** do {
** visited = adr;
nextAdr = PVM.mem[adr];
PVM.mem[adr] = codeTop;
adr = nextAdr;
** } while (visited != nextAdr);
}