Due: Wednesday, Nov 18th by 11:59 PM

Getting Started

Download CS340_Assign07.zip.

If you are using Counterclockwise under Eclipse, you can import the zipfile as an Eclipse project.

You should copy your parser2.clj file from Assignment 6 into the src/minilang directory.

Your task

Your task is to transform the parse trees produced by your parser into abstract syntax trees. Do this by implementing the build-ast function in astbuilder.clj.

There are three things that your build-ast function should do:

Statements

In addition to the rules mentioned above, you should also eliminate :statement nodes. Each type of statement should have a distinct symbol.

Make the following changes to your parser. First, eliminate the following productions:

statement → if ( expression ) { statement_list }

statement → while ( expression ) { statement_list }

Add the following productions:

statement → if_statement

statement → while_statement

if_statement → if ( expression ) { statement_list }

while_statement → while ( expression ) { statement_list }

In your parse-statement function, just apply the statement → if_statement production if the lookahead token is :if, and apply the statement → while_statement production if the lookahead token is :while.

Making these changes will make it easy to create AST nodes for :statement parse nodes: all that will be required is constructing an AST node from the single child of the :statement node (since all statement nodes will now have a single child.)

Hints

In general, building an AST will involve recursively converting child parse trees into ASTs. Of course, there will be some base cases where a parse node is already in the form of an AST. (For example, identifiers, int literals, and string literals can be considered to already be ASTs.)

You will need to think carefully about the structure of the parse nodes you will encounter, and how to transform them into equivalent AST nodes.

There are several helper functions that you may find useful.

The make-node function provides a convenient way to create a new AST node. It takes a symbol and a vector of child nodes as parameters.

The children function takes a parse node as a parameter and returns a vector containing the children of the parse node. (It will throw an exception if passed a terminal node.)

The get-child function takes a parse node and an integer n, and returns the nth child of the parse node.

The recur-on-children takes a parse node as a parameter, and returns an AST node whose symbol is the same as the parse node, and whose children are ASTs constructed from the children of the parse node. (Hint: this should be useful for nodes representing binary operators.)

:primary nodes representing parenthesized expressions will require special handling: specifically, the second child should be recursively turned into an AST, rather than the first child (which is the correct approach for the other kinds of primary expressions.)

Testing

You can test your build-ast function by changing the definition of the testprog variable (defined towards the bottom of astbuilder.clj. The value of this variable is parsed, an AST is constructed from the resulting parse tree, build-ast is called to convert the parse tree to an AST, and the AST is assigned to the variable prog.

In a REPL, you can evaluate

(pp/pretty-print ast)

to print the AST.

Here are some example inputs and the expected ASTs:

Example input:

var a; a := 3*4;

Expected AST:

:unit
+--:statement_list
   +--:var_decl_statement
   |  +--:identifier["a"]
   +--:expression_statement
      +--:op_assign
         +--:identifier["a"]
         +--:op_mul
            +--:int_literal["3"]
            +--:int_literal["4"]

Example input:

a * (b + 3);

Expected AST:

:unit
+--:statement_list
   +--:expression_statement
      +--:op_mul
         +--:identifier["a"]
         +--:op_plus
            +--:identifier["b"]
            +--:int_literal["3"]

Example input:

while (a + b) { c; d*e*4; }

Expected AST:

:unit
+--:statement_list
   +--:while_statement
      +--:op_plus
      |  +--:identifier["a"]
      |  +--:identifier["b"]
      +--:statement_list
         +--:expression_statement
         |  +--:identifier["c"]
         +--:expression_statement
            +--:op_mul
               +--:op_mul
               |  +--:identifier["d"]
               |  +--:identifier["e"]
               +--:int_literal["4"]

Grading

Your assignment grade will be determined as follows:

Submitting

When you are done, submit the lab to the Marmoset server using either of the methods below.

Important: after you submit, log into the submission server and verify that the correct files were uploaded. You are responsible for ensuring that you upload the correct files. I may assign a grade of 0 for an incorrectly submitted assignment.

From Eclipse

If you have the Simple Marmoset Uploader Plugin installed, select the project (CS340_Assign07) in the package explorer and then press the blue up arrow button in the toolbar. Enter your Marmoset username and password when prompted.

From a web browser

Create a zip file containing your completed project. (If you are in Eclipse, you can use File → Export... → General → Archive File.)

Upload the saved zip file to the Marmoset server as assign07. The server URL is

https://cs.ycp.edu/marmoset/

From the command line

From the command line, run the command

make submit

Type your Marmoset username and password when prompted.