CS 241 — Spring 2018 — Assignment 9

Assignments for CS 241
← Assignment 8 Assignment 9 Assignment 10 →
Wednesday, July 11 at 5:00pm Wednesday, July 18 at 5:00pm Wednesday, July 25
P1P2P3P4P5P6Bonus

Problem 1 — 15% (wlp4gen.rkt or wlp4gen.cc)

Extend your WLP4 compiler from the previous assignment to handle programs whose syntax is described by the production rules from that assignment as well as:

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 do any pointer comparisons other than equality (==) and 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 page.

Problem 2 — 15% (wlp4gen.rkt or wlp4gen.cc)

Extend your solution to the previous problem to handle inputs whose context-free syntax conforms to the rules for the previous problem, and in addition:

factor → NEW INT LBRACK expr RBRACK
statement → DELETE LBRACK RBRACK expr SEMI

This problem includes WLP4 programs that do dynamic memory allocation, but not pointer arithmetic or comparisons; you may continue to assume that the excluded cases from the previous problem apply here.

We provide a module alloc.merl that implements a memory allocator which you must use to implement new and delete. (If you are unable to access this file and are enrolled in the course, contact the ISA at cs241@uwaterloo.ca) This file must be linked last.

The memory allocator contains three MIPS procedures: init, new, and delete:

Click here to go back to the top of the page.

Problem 3 — 15% (wlp4gen.rkt or wlp4gen.cc)

Extend your solution to the previous problem to handle inputs whose context-free syntax conforms to the rules for the previous problem, and in addition:

expr → expr PLUS term
expr → expr MINUS term

This problem includes WLP4 programs that do pointer arithmetic but not pointer comparisons.

Click here to go back to the top of the page.

Problem 4 — 15% (wlp4gen.rkt or wlp4gen.cc)

Extend your solution to the previous problem to handle inputs whose context-free syntax conforms to the rules for the previous problem, 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 that consist of a single procedure (wain).

Click here to go back to the top of the page.

Problem 5 — 15% (wlp4gen.rkt or wlp4gen.cc)

Extend your solution to the previous problem to handle inputs whose context-free syntax conforms to the rules for the previous problem, 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 page.

Problem 6 — 25% (wlp4gen.rkt or wlp4gen.cc)

Extend your solution to the previous problem to handle the full WLP4 programming language.

Click here to go back to the top of the page.

Bonus Problem — 5% (wlp4gen.rkt or wlp4gen.cc)

Modify your WLP4 compiler to reduce the size of the MIPS program that it generates for a particular WLP4 program (the size in bytes after the assembly language program has been assembled, not the number of characters in the assembly language program itself). Although there exists a minimal MIPS program for every WLP4 program, determining that program is undecidable in general.

Submissions that generate a MIPS program containing less than 180 000 bytes will earn the bonus marks.

Special recognition

A prize will be given to the author of the best submission for the bonus problem. Honourable mention will be awarded for one or more other meritorious submissions. The judge's (i.e. the prof's) decisions are final.

A scoreboard of everyone's best submission for the bonus is available and will update roughly every 5 minutes.

Click here to go back to the top of the page.