CS245 Lab 7: AST Classes

Change your translator so that it performs translation in the following two passes: (a) read input and build an abstract syntax tree, and (b) generate infix expressions from the AST. You are required to set up your AST type as a collection of types that are related by inheritance from a single abstract class -- you should have specialized classes of nodes for the four arithmetic operations, for "l", for constants, and for variable uses. There should be a recursive member function named "generate_infix" that returns a String giving the infix form of the expression. Note that your generate_infix function might need parameters such as a symbol table (unless your symbol table is global).

I recommend that you approach this as follows:

  1. Create an AST node superclass and change your parser to return a tree rather than output the translated code directly (to make things compile, just have each function return some kind of null tree for the time being).
  2. Change your main program to call the generate_infix function for the tree produced by the parser (note that you can't test this yet, but you should make sure it compiles ok -- it should be a pretty trivial change).
  3. Create a class for nodes representing constants (this should inherit from the superclass), change your parser to create a correct (if very simple) tree for input such as 3, and test your program with this input.
  4. Create a class for one kind of arithmetic expression (such as +), change your parser to use this for addition, and test out your program so far on expressions like (+ 2 2) or (+ (+ 1 2) 1).
  5. Add the other arithmetic expressions and test your program on more general expressions.
  6. Add a new type of node for variable use, and one for a let, and integrate the symbol table stuff into your code generator.
  7. Test your program on input with "l".

Do not let yourself get too distracted with memory management issues -- if this is taking your attention away from the definition of the AST or the use of inheritance,

Note that your final result should handle any expression that was legal in either lab 2 or 3.

You should make these changes in your translator project, and use cvs to submit your answer.