CS 241 — Spring 2018 — Assignment 8

Assignments for CS 241
← Assignment 7 Assignment 8 Assignment 9 →
Wednesday, July 4 at 5:00pm Wednesday, July 11 at 5:00pm Wednesday, July 18 at 5:00pm
P1P2P3P4P5P6P7P8

In this assignment and the next one you will complete the WLP4 compiler for which you wrote a scanner, parser, and context-sensitive analyzer in recent assignments. For each problem, you will write a MIPS code generator for an increasingly larger subset of WLP4, culminating in a full WLP4-to-MIPS compiler by the end of the following assignment. Each code generator will be a Racket or C++ program that takes as input a .wlp4i file and, if it matches the context-sensitive specification of WLP4, produces as output a MIPS .asm file that may be assembled with cs241.binasm and then executed with mips.twoints or mips.array.

You should start with your context-sensitive analyzer from the previous assignment. However, all of the test inputs from now on will be valid WLP4 programs, and so an incomplete context-sensitive analyzer can still be built upon to create a solution for this assignment and the next one.

Testing

You must test your code generator yourself in Linux. To test your code generator, you will need .wlp4i files from a WLP4 parser. In case you do not wish to use your own parser, you can use the one that we have provided, using the command wlp4parse.

Starting from a .wlp4 source file, the complete sequence of commands to generate MIPS machine language code 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

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

This can be abbreviated significantly as:

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

and can be simplified further by writing a shell script rather than entering this manually every time you want to compile something.

Problem 1 — 5% (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 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 page.

Problem 2 — 10% (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 → LPAREN expr RPAREN

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
term → term STAR factor
term → term SLASH factor
term → term PCT factor
factor → NUM

That is, you must implement expressions with integer constants and the operators (+, -, *, /, %).

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

Problem 4 — 10% (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:

statements → statements statement
statement → PRINTLN LPAREN expr RPAREN SEMI

That is, you must implement the println statement.

You may use the provided print.merl module to implement the println statement. (If you are unable to access this file but 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

You can assemble such a file with cs241.linkasm instead of cs241.binasm. This will generate a MERL file. You should link this file with the print.merl that we provide, using the command cs241.linker. This library contains a procedure labeled 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 < yourCompilersOutput.asm > output.merl
cs241.linker output.merl print.merl > final.mips
mips.twoints final.mips

This can be slightly abbreviated to:

cs241.linkasm < yourCompilersOutput.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 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:

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 page.

Problem 6 — 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:

test → expr LT expr
statement → WHILE LPAREN test RPAREN LBRACE statements RBRACE

That is, you must implement while loops whose condition is a less than.

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

Problem 7 — 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:

test → expr EQ expr
test → expr NE expr
test → expr LE expr
test → expr GE expr
test → expr GT expr

That is, you must implement the other five comparison relations.

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

Problem 8 — 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

At this point, your compiler should support all WLP4 programs that do not involve pointers or procedures.

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