EECS665 – Compiler Construction

Project 3

Due on September 29^th 11:59 PM (Accepted with no penalty).

Accepted late by September 30^th 11:59 PM for 1 penalty

Accepted late by October 1^st 11:59 PM for 2 penalties

Not accepted on or after October 2^nd 12:00 AM

Each penalty incurs a 15% stacking reduction on the project grade or uses 1 "penalty token". Penalty tokens are applied by course personnel to your maximum benefit.

Resources

Inheritance diagram - This diagram suggests the is-a relationship between classes that you can use to capture the abstract-syntax tree.
Collaboration diagram - This ``diagram'' suggests the has-a collaboration relationship you could use between nodes / fields in the AST.
Starter files - Files to get you started on the project, such as a skeleton bison spec to implement the parser. If you don't want to use your completed code from the previous project.
The oracle - Submit an input file (i.e. a source file in the Drewno Mars language, potentially with errors), and the oracle will say what the correct output should be for this project.

Updates

None yet!

Overview

For this assignment you will extend your Bison spec to perform a syntax-directed translation, producing an AST for the input Drewno Mars program. You will also write methods to unparse the AST built by your parser and an input file to test your parser. A main program, main.cpp, that calls the parser and then the unparser is already provided.

This project is intended to be an extension of the previous project code, but will be invoked via a new argument. Your code should be built and invoked via the command sequence

make all
./dmc <file.dm> -u <outfile.txt> 

Where file.dm is an input file to have it's syntax checked and <outfile.txt> is a file containing the output of unparsing. The only required behavior of your project is that the output file should correspond to pretty-printed Drewno Mars code. Thus, although AST classes and relationships are suggested, you can create whatever types of AST nodes make sense for you.

How We'll Grade

The goal of this project is to build an AST of the input program, and that your AST is accurate. To ensure this goal, we'll test that your compiler can "pretty-print" or "unparse" the input program in a canonical form.

Your output will need to adhere to a specific newline and indentation behavior:

Open brackets should be followed by a newline.
Lines of code should be indented by 4 spaces for each block level of nesting.

Other than newlines and indentation, your output will be considered correct if it is semantically equivalent to the input (i.e. the output program has the same meaning as the original). This means that (for one), you can add or remove parentheses/spaces to expressions as long as they don't change the meaning of the expression. Consider the input program

int v(){ return 1 + (2 * 3); }

It would be fine to print

int v(){ return 1 + 2 * 3; }

or even

int v(){ return (1 + 2 * 3); }

but NOT

int v(){ return (1 + 2) * 3; }




	
        
        Using The Starter Code
        
	

   Getting started
   Building an AST
   Unparsing
   Modifying unparse.cpp

		    	

Getting Started

You are encouraged to build upon your P2 files to complete this project.
However, "starter files" are provided here as a starting point:
p3.tgz


If you choose to use the starter code (or closely mirror the starter code's suggested
implementation), the below advice will get you on the right track. Of course,
this advice is optional. You don't need to use the same node classes provided, nor
use the same filenames or whatever. You just need to build some form of AST and 
make sure it pretty-prints.


To check on an acceptable format for unparsing output, you may consult the
P3 oracle


		
Building an Abstract-Syntax Tree

To make your parser build an abstract-syntax tree, you must 
make sure that each production has a syntax-directed definition 
in the 
drewno_mars.yy Bison spec.
You will need to decide, for each nonterminal, what
type its associated translation attribute should have.
Then you must add the appropriate nonterminal declaration to the
specification.
For most nonterminals, the value will either be some kind of tree node
(a subclass of ASTNode) or a std::list
of some kind of node. 
Use the information in the inheritance diagram for a suggested
list of AST node types and the collaboration diagram above to guide 
your decision (both of these diagrams are linked above).


Make sure that each action includes an assignment to
$$. Note that the parser will set the
ASTNode pointer to the value assigned to the production for
the root nonterminal (nonterminal program).


Unparsing

To test your Syntax-directed definition, we need to see the AST be output. As such, any 
ASTNode subclass should have an unparse function
that recursively creates a textual representation of that node. Since
the AST was derived from a textual representation, the unparsed output
should look a lot like the original input file. 


The recommended way to implement the unparse functions
is to add them to unparse.cpp (some examples are already given).
When the unparse method of the root node of the program's
abstract-syntax tree is called, it should print a nicely formatted
version of the program.
The output produced by calling unparse should be the
same as the input to the parser except that:


  There will be no comments in the output.
  The output will be "pretty printed" (a uniform style of 
	newlines and indentation will be used to make the program 
	readable);
   Expressions will be fully parenthesized to reflect the order of
       evaluation.




Note: Trying to unparse a tree will help you determine whether you have
built the tree correctly in the first place.
Besides looking at the output of your unparser, you should try
using it as the input to your parser;
if it doesn't parse, you've made a mistake either in how you built
your abstract-syntax tree or in how you've written your unparser.


Modifying unparse.cpp

We will test your program by using our unparse
functions on your abstract-syntax trees and by using your 
unparse functions on our abstract-syntax trees.
To make this work, you will need to:



Modify unparse.cpp by implementing the
unparse methods and creating new node classes in