CSE5317/4305 Project #3 (Abstract Syntax)

Due Friday March 30 before midnight

Worth 15% of your project grade


For this project, you are asked to generate ASTs (Abstract Syntax Trees) for SPL. The ASTs are described in spl/src/main/scala/edu/uta/spl/AST.scala. See the calculator example calc/src/main/scala/edu/uta/calc/calc.cup to understand how ASTs are constructed based on the classes in calc/src/main/scala/edu/uta/calc/AST.scala

Your task for this project is to add actions to your spl.cup file to generate ASTs. See the "Complete Concrete Syntax" section in the SPL manual and the AST.scala classes to understand the relationship between the SPL grammar and the ASTs. You may run the solution over various test files: scala spl-solution.jar 3 tests/*.spl, to understand what AST you need to generate. For example, the AST of the SPL expression (x-2)+3 is constructed as follows::

new BinOpExp("plus",new BinOpExp("minus",new LvalExp(Var("x")),new IntConst(2)),new IntConst(3))
For example, the action for the PLUS expression is:
expr ::= expr:e1 PLUS expr:e2  {: RESULT = new BinOpExp("plus",e1,e2); :}
(Recall that spl.cup uses Java, not Scala, so you must call the case class constructors with 'new').

Directions: The most important step to do first before you add actions is to think about the types of non-terminals; if a non-terminal is going to hold one expression, then the type should be Expr if it is many expressions, it should be List<Expr>, if it contains record components, it should be List<Bind<Expr>>, etc. See the original skeleton file spl.cup. A good way to start this project is to write a test file x.spl outside your spl directory that contains 1-2 lines only, such as x=x+1;, and then run the solution on this file. That way, you can look at the AST of very simple expressions and statements and reverse-engineer the solution.

Hints: to construct lists, use:

  1. append(l,e) appends the element e at the end of the list l, ie, it returns a new list containing the list l followed by the element e
  2. append(l1,l2) appends list l2 at the end of list l1, ie, it returns a new list containing the elements from l1 followed by the elements from l2
  3. add(e,l) inserts the element e at the beginning of the list l, ie, it returns a new list containing e followed by the list l
If a type is optional and is missing, use AnyType() for the missing type. To convert a list of statements into a single statement use BlockSt.

Note that you would need to pass the final AST to the rest of the program, which must be a ProcDecl of the SPL main program. For example, the first rule may look like this:

program ::= block_content:b   {: SPL.setAST(new Program(b)); :}
which stores the AST of the source program so that the next parser phases will use this value.

You need to run your parser against all tests/*.spl files. For example:

scala lib/spl.jar 3 tests/hello.spl
You also need to compare your output with that of the solution:
scala spl-solution.jar 3 tests/hello.spl

After ensuring that your program compiles and executes correctly, cleanup your spl directory using mvn clean Then, zip the spl directory as spl.zip and submit it here:

Submit Project #3:

Last modified: 03/09/2017 by Leonidas Fegaras