CS 241 — Winter 2020 — Final Assessment
Assignments for CS 241
← Assignment 8
Final Assessment
Friday, March 27th, at 5:00 pm
Monday, April 13th, at 5:00 pm
P1 • P2 • P3 • P4 • P5 • P6 • P7 • P8 • P9 • P10 • P11 • P12 • P13 • P14
In the Final Assessment you will complete the WLP4 compiler for which you wrote a scanner in Assignment 6, a parser in Assignment 7, and a context-sensitive analyzer in Assignment 8. For each problem, you will write a MIPS code generator for an increasingly larger subset of WLP4, culminating with a full WLP4-to-MIPS compiler. Each code generator will be a Racket or C++ program that takes as input a .wlp4i file and, if it conforms to the context-sensitive syntax of WLP4, produces as output a MIPS .asm file that may be assembled with cs241.binasm (or a new assembler called cs241.linkasm for Problem 4 onwards) and then executed with mips.twoints or mips.array.
For the Final Assessment, you should start with your context-sensitive analyzer from Assignment 8. However, all of the test inputs for the Final Assessment will be valid WLP4 programs. Therefore, if you did not complete Assignment 8 to reject all invalid WLP4 programs, you can still use your partial solution as a starting point for the Final Assessment. In particular, if your program passes all non-blind tests for Assignment 8 Problems 1 to 5, you should have no issues doing the Final Assessment. Even if you do not pass all non-blind tests, you may still be fine provided the tests you fail only involve invalid programs.
Additionally, for Problems 1 to 10, the only part of Assignment 8 you need is the symbol table. However, for Problem 11 and onwards you will need a working type checker.
Grading Scheme
The grading scheme for the assessment is divided into two portions: Marmoset tests and handmarking. The assessment itself is divided into four parts:
• Part 1: Returning values, arithmetic, and printing
• Part 2: Assignment statements and control structures
• Part 3: Pointers and memory allocation
• Part 4: Procedures
Each part is worth 25% of the assessment grade. Since the assessment is worth 20% of your final grade, this means each part is worth 5% of your final grade.
Marmoset Tests
The vast majority of your marks on this assessment will come from passing the tests on Marmoset.
A big difference from the assignments is that this assessment has hidden tests which do not show up on Marmoset, but will still be worth marks! To make sure you pass these hidden tests, you should develop thorough test suites for each problem. Do not rely on Marmoset to do all your testing for you.
70% of the marks for Marmoset tests come from public and release tests, while the other 30% comes from hidden tests. We will not reveal the exact breakdown per problem. The mark values listed beside each problem (and shown on Marmoset) do not include hidden test marks, but they should give you an idea of the relative weight of the non-hidden tests for each problem.
Handmarking
There will be a small amount of marks based on the design and style of your code. We will not reveal exactly how much this factors into the assessment grade, but it will be a small portion. Our advice is to simply try your best to write good code and not worry about the exact percentage this will be worth. If your grade is low enough that you are concerned that handmarking will be the deciding factor in whether you pass the course, you should do the Bonus Essay (see below).
Bonus Essay
If you do not think you can pass the course based on the above grading scheme, or you are unsure whether you will pass (for example if passing depends on how many hidden test marks or handmarking marks you get) then you have the opportunity to increase your chances of passing by submitting an essay. This essay is not worth any marks (so students who are not close to failing should not submit one) but it will be used to determine whether borderline cases pass or fail the course.
Submit by email directly to your instructor (Carmen or Mark) a 1000 word essay on how to write a compiler. We will not count words exactly but the essay should be no more than 2 pages, with 11 or 12 pt font and 0.75 inch margins all around.
Again we must stress this is only for students who are failing or close to failing. This is a measure to give students who did poorly on the midterm a chance to pass. Do not submit an essay if you are doing well in the course as it will not affect your grade.
Testing your Code Generator
You must test your code generator yourself in Linux. To test your code generator, you will need .wlp4i files as generated by the parser specified in A7P5. In case you do not wish to use your own parser, you can use one that we have provided. Invoke it using the command wlp4parse.
Starting from a .wlp4 source file, the complete sequence of commands to generate MIPS machine language and run it is:
wlp4scan < foo.wlp4 > foo.scanned
wlp4parse < foo.scanned > foo.wlp4i
racket wlp4gen.rkt < foo.wlp4i > foo.asm
cs241.binasm < foo.asm > foo.mips
mips.twoints foo.mips OR mips.array foo.mips
OR
wlp4scan < foo.wlp4 > foo.scanned
wlp4parse < foo.scanned > foo.wlp4i
./wlp4gen < foo.wlp4i > foo.asm
cs241.binasm < foo.asm > foo.mips
mips.twoints foo.mips OR mips.array foo.mips
This can be abbreviated to
cat foo.wlp4 | wlp4scan | wlp4parse | racket wlp4gen.rkt | cs241.binasm > foo.mips
mips.twoints foo.mips
OR
cat foo.wlp4 | wlp4scan | wlp4parse | ./wlp4gen | cs241.binasm > foo.mips
mips.twoints foo.mips
The above can be made much easier to do with a shell script.
Part 1: Returning values, arithmetic, and printing
Problem 1 — 8 marks (filename: wlp4gen.rkt or wlp4gen.cc)
Write a code generator for correct WLP4 programs that conform to the syntax rules:
start → BOF procedures EOF
procedures → main
main → INT WAIN LPAREN dcl COMMA dcl RPAREN LBRACE dcls statements RETURN expr SEMI RBRACE
type → INT
dcls →
dcl → type ID
statements →
expr → term
term → factor
factor → ID
You may assume that the test input is a valid WLP4 program that satisfies the context-sensitive syntax of WLP4, and whose derivation contains only the above production rules.
Note: All that a WLP4 program conforming to this syntax can do is return the value of one of its parameters. Your MIPS output should assume that the parameter values are in $1 and $2 respectively, and return the result in $3.
Click here to go back to the top of the Final Assessment.
Problem 2 — 4 marks (filename: wlp4gen.rkt or wlp4gen.cc)
Extend your solution for Problem 1 to handle inputs whose context-free syntax conforms to the rules for Problem 1, and in addition:
factor → LPAREN expr RPAREN
Click here to go back to the top of the Final Assessment.
Problem 3 — 16 marks (filename: wlp4gen.rkt or wlp4gen.cc)
Extend your WLP4 compiler to handle WLP4 programs whose syntax is described by the production rules for Problems 1 and 2, and in addition:
expr → expr PLUS term
expr → expr MINUS term
term → term STAR factor
term → term SLASH factor
term → term PCT factor
factor → NUM
That is, you are to implement expressions with integer constants and the operators {+, -, *, /, %}
You do not need to worry about integer overflow for this problem. In particular, for multiplication, you should use mflo to get the result and ignore the value in the hi register.
Click here to go back to the top of the Final Assessment.
Problem 4 — 12 marks (filename: wlp4gen.rkt or wlp4gen.cc)
Extend your WLP4 compiler to handle WLP4 programs whose syntax is described by the production rules for Problems 1 to 3, and in addition:
statements → statements statement
statement → PRINTLN LPAREN expr RPAREN SEMI
That is, you are to implement the println statement.
You may use the provided print.merl module to implement the println statement. You must download this file from the link in the previous sentence and transfer it to your Linux environment account – it is not accessed using source /u/cs241/setup. (If you are unable to access this file and you are enrolled in the course, contact the ISA at cs241@uwaterloo.ca.) The output from your compiler should now and henceforth be an assembly source file containing the line:
.import print
The .import directive lets you use a procedure from an external file via linking.
You can assemble files containing .import directives by using cs241.linkasm instead of cs241.binasm. This assembler generates MERL files (MIPS assembly language programs with extra metadata to allow for relocation and linking). You should link this file with the library print.merl that we provide, using the command cs241.linker. This library contains a procedure labelled print, which outputs a decimal representation of the number passed to it in register $1. For example, you could assemble, link, and run the output of your code generator using the following commands:
cs241.linkasm < yourCompilersAssemblyLanguageOutput.asm > output.merl
cs241.linker output.merl print.merl > final.mips
mips.twoints final.mips
Click here to go back to the top of the Final Assessment.
Part 2: Assignment statements and control structures
Problem 5 — 6 marks (filename: wlp4gen.rkt or wlp4gen.cc)
Extend your WLP4 compiler to handle variable declarations and assignment statements. Your solution should handle WLP4 programs whose syntax conforms to the rules given in Problems 1 to 4, and in addition:
dcls → dcls dcl BECOMES NUM SEMI
statement → lvalue BECOMES expr SEMI
lvalue → ID
lvalue → LPAREN lvalue RPAREN
Click here to go back to the top of the Final Assessment.
Problem 6 — 8 marks (filename: wlp4gen.rkt or wlp4gen.cc)
Extend your WLP4 compiler to handle WLP4 programs whose syntax is described by the production rules in Problems 1 to 5 and in addition:
test → expr LT expr
statement → WHILE LPAREN test RPAREN LBRACE statements RBRACE
That is, you are to implement while loops whose continuation condition is expressed with “<".
Click here to go back to the top of the Final Assessment.
Problem 7 — 10 marks (filename: wlp4gen.rkt or wlp4gen.cc)
Extend your WLP4 compiler to handle WLP4 programs whose syntax is described by the production rules in Problems 1 to 6 and in addition:
test → expr EQ expr
test → expr NE expr
test → expr LE expr
test → expr GE expr
test → expr GT expr
That is, you are to implement the other five comparison relations.
Click here to go back to the top of the Final Assessment.
Problem 8 — 6 marks (filename: wlp4gen.rkt or wlp4gen.cc)
Extend your WLP4 compiler to handle WLP4 programs whose syntax is described by the production rules in Problems 1 to 7 and in addition:
statement → IF LPAREN test RPAREN LBRACE statements RBRACE ELSE LBRACE statements RBRACE
This includes all WLP4 programs that do not involve pointers or procedures.
Click here to go back to the top of the Final Assessment.
Part 3: Pointers and memory allocation
Problem 9 — 9 marks (filename: wlp4gen.rkt or wlp4gen.cc)
Extend your WLP4 compiler to handle WLP4 programs whose syntax is described by the production rules in Problems 1 to 8, and in addition:
type → INT STAR
dcls → dcls dcl BECOMES NULL SEMI
factor → NULL
factor → AMP lvalue
factor → STAR factor
lvalue → STAR factor
For this problem and the following problem, we will not be doing any pointer comparisons other than equality (==) or inequality (!=).
This problem includes WLP4 programs that involve pointers, but do not do dynamic memory allocation, pointer arithmetic, or pointer comparison. Although the C++ standard leaves the result of dereferencing a null pointer undefined, we require that dereferencing NULL must crash the MIPS machine.
Click here to go back to the top of the Final Assessment.
Problem 10 — 8 marks (filename: wlp4gen.rkt or wlp4gen.cc)
Extend your WLP4 compiler to handle WLP4 programs whose syntax is described by the production rules in Problems 1 to 9 and in addition:
factor → NEW INT LBRACK expr RBRACK
statement → DELETE LBRACK RBRACK expr SEMI
You may continue to assume that the parse tree of the WLP4 program does not contain any of the production rules that were excluded in Problem 8.
This problem includes WLP4 programs that do dynamic memory allocation, but do not do pointer arithmetic or pointer comparison.
We provide a module alloc.merl that implements a memory allocator, which you should use to implement the new and delete statements. You must download this file from the link in the previous sentence and transfer it to your Linux environment account – it is not accessed using source /u/cs241/setup. (If you are unable to access this file and you are enrolled in the course, contact the ISA at cs241@uwaterloo.ca.) Note that alloc.merl must be linked last. Also note that Marmoset uses a modified version of this memory allocator that prints debugging information to verify that you are calling new and delete correctly, so you are unlikely to pass the tests for this problem if you write your own memory allocation code rather than using .import to import the procedures from alloc.merl.
The memory allocator contains three MIPS procedures: init, new, and delete. You must import each procedure individually (by writing .import init, .import new, and .import delete on three separate lines, rather than simply .import alloc).
The init procedure must be called once at the beginning of your generated program before any calls to new or delete.
• If the first parameter to wain is of type int* (i.e., the generated code will be passed an array), then the size of this array must be in register $2 when init is called. Note that mips.array already puts the size of the array in register $2, so you only need to make sure that your generated code does not change $2 before it calls init.
• If the first parameter to wain is of type int, then register $2 must contain the value 0 (zero) when init is called.
The new procedure produces in register $3 the address of the beginning of a contiguous sequence of n words of memory, where n is the value passed in register $1 when the procedure was called. If new fails in the allocation, it will return 0. Your generated code should return NULL if new fails, rather than 0, since 0 is a valid memory address.
The delete procedure frees for reuse the block of memory whose address is passed in register $1 when the procedure is called. The address passed to delete must be an address that was earlier returned from new, and has not since already been passed to delete. You do not need to enforce this at compile time; it is the programmer's job to make sure that they use delete properly. However, note that passing NULL to delete is valid in C++ and the result is that nothing happens (no call to delete is made); your generated code should mimic this behaviour.
Click here to go back to the top of the Final Assessment.
Problem 11 — 8 marks (filename: wlp4gen.rkt or wlp4gen.cc)
Extend your WLP4 compiler to handle WLP4 programs whose syntax is described by the production rules in Problems 1 to 10 and in addition:
expr → expr PLUS term
expr → expr MINUS term
This problem includes WLP4 programs that do pointer arithmetic but do not do pointer comparison.
Click here to go back to the top of the Final Assessment.
Problem 12 — 9 marks (filename: wlp4gen.rkt or wlp4gen.cc)
Extend your WLP4 compiler to handle WLP4 programs whose syntax is described by the production rules in Problems 1 to 11 and in addition:
statement → IF LPAREN test RPAREN LBRACE statements RBRACE ELSE LBRACE statements RBRACE
statement → WHILE LPAREN test RPAREN LBRACE statements RBRACE
test → expr EQ expr
test → expr NE expr
test → expr LT expr
test → expr LE expr
test → expr GE expr
test → expr GT expr
This problem includes all WLP4 programs consisting of only the main procedure wain.
Click here to go back to the top of the Final Assessment.
Part 4: Procedures
Problem 13 — 12 marks (filename: wlp4gen.rkt or wlp4gen.cc)
Extend your WLP4 compiler to handle WLP4 programs whose syntax is described by the production rules in Problems 1 to 12 and in addition:
procedures → procedure procedures
procedure → INT ID LPAREN params RPAREN LBRACE dcls statements RETURN expr SEMI RBRACE
params →
factor → ID LPAREN RPAREN
This problem includes all WLP4 programs in which all procedures other than wain take no arguments.
Click here to go back to the top of the Final Assessment.
Problem 14 — 24 marks (filename: wlp4gen.rkt or wlp4gen.cc)
Extend your WLP4 compiler to handle the full WLP4 language. All that remains is adding support for procedures with a non-zero number of parameters.
Click here to go back to the top of the Final Assessment.