Reference no: EM132460605

CSC 460/660 - Compiler Construction - University of Nevada

The Espresso Compiler Project

Phase - Parse Tree Construction

The second phase of the Espresso compiler project is concerned with adding actions to the CUP file. These actions will build a parse tree for the program being parsed. We need such a parse tree in the next 4 phases. Many checks and computations can be performed by implementing traversals of the parse tree.

If the input is syntactically correct, your compiler should build a parse tree. This is done by providing Java code to construct the tree between the {: ... :} symbols.

Work List

Question 1: Determine the types of all the non-terminals. Some are pretty obvious, like for example the if statement. Naturally the non-terminals if then statement, if then else statement, and if then else statement no short if are all of type IfStat (i.e., they create an object of the IfStat class). Once you have determine this you can use the types in the constructor of the IfStat to determine the types of the individual parts of the if statement. Start with the obvious non-terminals and work your way back like I just explained.

Question 2: Add action to your cup file. That is, add {: RESULT = ... :} to each production rule, where ... creates an object of the right type. This will always be one of the classes in the parse tree node files, or null. Keep in mind that if one right-hand-side of a production creates a sequence, then all right-hand-sides should create a sequence. For example, if we have a production like

A ::= A a
    | a
we are dealing with a repetition or a list of as. The typical action you would add looks like this:

A ::= A:lst a:e {: RESULT = lst.append(e); :}
| a:e {: RESULT = new Sequence(e); :}

As you can see, both right-hand-sides return a sequence, so the type of the entire production is Sequence. Now if we have the following production in addition to the above one:

A opt ::= A
        | ∈
then the first right-hand side will return a Sequence, so in order to type this correctly, the empty production must also return a Sequence. We solve this problem in the following way:

A opt ::= A:lst {: RESULT = lst; :}
|  {: RESULT = new Sequence(); :}

of course you only need to use this technique if the non-empty right-hand-side returns a sequence.
• Compile your compiler using the ant command.
• Run the espressoc script to test your compiler.
• Compare your results to my reference implementation.

Running the Reference Implementation

In order to check your compiler against my version of the Espresso compiler, you can use the espressocr script. That will submit your file to my reference implementation and return the output.

Pre-supplied Code and Testing

When you hand in your project we will use the build.xml file and the ant command to make your project, and the espressoc script to run your compiler. If we cannot do that we will not mark your project, i.e., you get 0 on this phase. We will do the following to test your compiler:
ant clean
ant
espressoc <testfile.java>

Attachment:- Compiler Construction.rar