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.
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:
- All legal arithmetic expressions should be supported.
- All ill-formed expressions (e.g. " ((3 + )" ) should be rejected.
- The postfix that your code outputs should be legal input for the "virtual machine".
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.
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:
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.