In assignments 9 and 10 you will complete the WL compiler for which you wrote a scanner in assignment 6 and a parser in assignment 8. For each problem, you will write a MIPS code generator for an increasingly larger subset of WL, culminating with a full WL-to-MIPS compiler. Each code generator will be a Java or Scheme or C program that takes as input a .wli file and, if it conforms to the context-sensitive syntax of WL, produces as output a MIPS .asm file that may be assembled with cs241.binasm and then executed with mips.twoints. Each code generator may assume that the .wli file is well formed, but must output an informative message containing "ERROR" to Standard Error for any input that does not conform to the WL context-sensitive syntax.
In assignment 11, you will repeat the subtasks listed on this assignment for a slightly larger language (WLPP).
You must test your code generator yourself in Unix. To test your code generator, you will need .wli files as generated by the parser specified in A8P4. In case you do not wish to use your own parser, you can use one that we have provided. Invoke it using the command java cs241.WLParse.
Starting from a .wl source file, the complete sequence of commands to generate MIPS machine language and run it is:
java cs241.WLScan < foo.wl > foo.scanned java cs241.WLParse < foo.scanned > foo.wli java WLGen < foo.wli > foo.asm java cs241.binasm < foo.asm > foo.mips java mips.twoints foo.mips
OR
java cs241.WLScan < foo.wl > foo.scanned java cs241.WLParse < foo.scanned > foo.wli mzscheme wlgen.ss < foo.wli > foo.asm java cs241.binasm < foo.asm > foo.mips java mips.twoints foo.mips
OR
java cs241.WLScan < foo.wl > foo.scanned java cs241.WLParse < foo.scanned > foo.wli ./wlgen < foo.wli > foo.asm java cs241.binasm < foo.asm > foo.mips java mips.twoints foo.mips
This can be abbreviated to
cat foo.wl | java cs241.WLScan | java cs241.WLParse | java WLGen | java cs241.binasm > foo.mips java mips.twoints foo.mips
OR
cat foo.wl | java cs241.WLScan | java cs241.WLParse | mzscheme wlgen.ss | java cs241.binasm > foo.mips java mips.twoints foo.mips
OR
cat foo.wl | java cs241.WLScan | java cs241.WLParse | wlgen | java cs241.binasm > foo.mips java mips.twoints foo.mips
The above can be made much easier to do with a shell script.
Assignment 9: Monday, March 22, 2010 at 5:00 pm
Assignment 10: Monday, March 29, 2010 at 5:00 pm
You are given a starter program that works for correct WL programs conforming to the syntax rules
procedure → INT WAIN LPAREN dcl COMMA dcl RPAREN LBRACE dcls statements RETURN expr SEMI RBRACE
dcls →
dcl → INT ID
statements →
expr → term
term → factor
factor → ID
namely one of
Modify the program so that it outputs ERROR on stderr if the input conforms to the syntax rules above but violates the context-sensitive syntax of WL.
Note: All a WL 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.
Extend your solution for problem 1 to handle inputs whose context-free syntax conforms to the rules for A9P1, and in addition:
factor → LPAREN expr RPAREN
Extend your WL compiler to handle WL programs whose syntax is described by the production rules for A9P1 and A9P2, 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 {+, -, *, /, %}
Extend your WL compiler to handle WL programs whose syntax is described by the production rules for A9P1, A9P2, A9P3, and in addition:
statements → statements statement statement → PRINTLN LPAREN expr RPAREN SEMI
That is, you are to implement the println statement.
The output from your compiler should now and henceforth be an assembly source file in MERL format, with a patch table containing an ESR for 'print'. After assembly you should then link your compiler's output with print.merl to produce an executable program using the CS 241 tool
java cs241.linkasm < yourCompilersAssemblyLanguageOutput.asm > userCode.merl
linker userCode.merl print.merl > program.merl
(Marmoset will link but not relocate userCode.merl. Hence its patch table is not required to contain REL entries, although generating them is not difficult.)
Extend your WL compiler to handle variable declarations and assignment statements. Your solution should handle WL programs whose syntax conforms to the rules given in A9P1, A9P2, A9P3, A9P4, and in addition:
dcls → dcls dcl BECOMES NUM SEMI statement → ID BECOMES expr SEMI
Extend your WL compiler to handle WL programs whose syntax is described by the production rules in A9P1, A9P2, A9P3, A9P4, A10P1 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 "<".
Extend your WL compiler to handle WL programs whose syntax is described by the production rules in A9P1, A9P2, A9P3, A9P4, A10P1, A10P2 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.
Extend your WL compiler to handle all WL programs. That is, you should handle WL programs whose syntax is described by the production rules in A9P1, A9P2, A9P3, A9P4, A10P1, A10P2, A10P3 and in addition:
statement → IF LPAREN test RPAREN LBRACE statements RBRACE ELSE LBRACE statements RBRACE
Modify your WL compiler to reduce the size of the MIPS program that it generates for a particular WL program (that is, the size of the binary MIPS program after it is assembled, not the number of lines or number of bytes in the assembly code that your compiler outputs). Although there exists a minimal MIPS program for a given WL program, determining such a program is in general an undecidable problem.
Special recognition will be given to the author of the best submission for the Bonus. Honourable mention will be awarded for one or more other meritorious submissions. The judge's (i.e. the prof's) decision will be final.
There will be 3 bonus marks for those submissions that generate less than 85000 bytes of code.