Exploration of a Simple Compiler

In this assignment, you'll implement a very simple form of language translation for arithmetic expressions. The source language consists of integers, applications of arithmetic operators to integers, and optional parentheses for grouping. The "keywords" of the language are ordinary arithmetic operators and parentheses for grouping:

+   *   (  )

Legal expressions are given by the grammar:

<exp> ::= <number> | <exp> + <exp> | <exp> * <exp>  | (<exp>)

There may be any number of spaces or line breaks between lexical elements. The usual rules of precedence apply, with multiplication binding higher than addition, and parentheses grouping the tightest of all. Note that we do not have any subtraction or division operators here. Those may be added, for optional extra credit.

Your Job

You are to write a compiler for expressions in our simple language. The target should be a corresponding expression in a postfix form, in which all expressions are rendered by giving the left hand side, then the right, then the operator, with each element separated by one or more spaces. For example, the source-level expression "(5+2*4)*(3+7) + 1" should be translated to the postfix form "5 2 4 * + 3 7 + * 1 +".

Included in this assignment is a "virtual machine" evaluator for postfix expressions, which you may use to check your work.

There is no particular constraint on how your organize your work here, so long as your compiler satisfies the following requirements:

Despite the open-ended character of these requirements, you'll likely figure out pretty quickly that certain approaches work better than others. For example, you'll almost certainly want an intermediate "tree" representation of source-level expressions. You'll have to think about how to get the precedence of multiplication over addition right, and how to support parenthesized grouping.

Extra Credit

If you tackle subtraction and division, you'll need to make sure that both are handled as left-associative operators, and that subtraction and addition have the same precedence, as do division and multiplication. For example, the expression "(5+7 * 8-5) / 4 - 2 - 1" should result in the output "5 7 8 * + 5 - 4 / 2 - 1 -", which evaluates to 11, of course. You'll likely find this quite challenging! Remember that it's only an extra credit option, so don't be afraid to try and fail.


You don't really need it to build your compiler, but if you want to "run" the "object code" produced by your compiler, you can grab a copy of this working postfix evaluator, which supports all four arithmetic operators:


Your Job

This work must be done individually. You are free to discuss any aspect of your investigation with your colleagues in the class, but the work you submit must be your own.

Turn In:

The source code for your compiler. It probably goes without saying, but just in case: you must turn in an actual program, which is to say that your work must be compilable Java code. Partially correct compilers will still receive partial credit, but code that does not compile is not code and will not receive any credit at all.

John H. E. Lasseter