Ex. 2111.6 : CODE GENERATION

DURATION 1 lab session

PURPOSE

This exercise is intended to illustrate some of the differences between creating the simple calculators in exercises 3 and 4 and creating compilers for real computers and real programming languages.

OBJECTIVES

To implement a code generator for C expressions generating MIPS code.

DESCRIPTION

You will find a makefile, starting lex (twopass_l.l) yacc (twopass_y.y) and C (twopass.c, twopass.h and [a-e].c) code, and some test data (data_1, data_2) in $CS2111/p*/ex6/*
The "twopass" files recognise expressions, build parse-trees (similarly to handout 8) and generate code from the trees using one of the 5 files a.c to e.c (similarly to handout 10). Which of the 5 files is used depends on which of the commands "make a" to "make e" you use - "make test" makes all 5 versions and runs them on the given test data.

1) This is straightforward, to help you understand how "treewalk" works: modify version a of the program to produce output identical to that for exercise 4.

Version a as given outputs code like:

	push 1
	push 2
	push 3
	mul
	add
	push 1
	push 2
	mul
	push 3
	push 4
	mul
	add

	1 2 3 * + p
	1 2 * 3 4 * + p
	q

The grammar has been changed slightly to recognise expressions like "1+2;" rather than "1+2=", and the test data has been changed to correspond. Ignore identifiers, and just deal with numerical operands.
I have added a "mode" parameter to treewalk, which distinguishes between the top of each parse tree ("top"), recursive calls ("inner"), and the end of input ("end"). I have also put the output strings for the operators into an array ("names") in the C code.
Type "make test1" to compile version a and run it against the test data (data_1).

2) Modify version b to produce MIPS assembly code. Assume you are using a version of MIPS that has instructions for multiplication and division. If you didn't do CS1031 and so don't know MIPS code, you may generate code for any computer you are familiar with, or for MU0 from CS1011 (but agree on some sensible extensions to the instruction set with me first). You will probably need to use a different version of the code generation code (e.g. version d for MU0). If you don't know any assembly language you had better discuss it with me.
I have added an "operandtype" field to operands, to distinguish between "name"s and "number"s. Assume that identifiers represent variables at some offset from a suitable register (e.g. use the name of the variable to represent the offset).
Modify the Lex, Yacc and C code to include more of the operations possible in C expressions (e.g. some of the dyadic operators "|", "&", "^", "==", "!=", "<", ">", "<=", "=>", "<<", ">>" and the monadic operators "+", "-", "++", "--", "~", "!"). You should give any operators you include the correct associativity and precedence. Modify the test data (data_2) to include examples of your operators, to show that they do have the correct associativity and precedence.
Type "make test2" to compile version b and run it against the test data (data_2).

Bonus suggestions

* Part 2: Implement more facilities of C expressions, such as assignment operators or data structures.
* Part 1: Deal with identifiers by adding constant declarations to the language.
* Part 2: Deal with variables by allocating them space and calculating proper offsets. You could add declarations to the language.
* Part 2: Run your generated code using the spim simulator

DELIVERABLES

Demonstrate your working programs to a demonstrator or lab supervisor.