CSE5317/4305 Project #3 (Abstract Syntax)

Due Sunday March 29 before midnight

Worth 15% of your project grade


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

Your task for this project is to add actions to your pcat.cup file to generate ASTs. See the "Complete Concrete Syntax" section in the PCAT manual and the AST.scala classes to understand the relationship between the PCAT grammar and the ASTs. You may run the solution over various test files: solution 3 tests/*.pcat, to understand what AST you need to generate. The output of your program (as well as the solution output) is a pretty-print of the ASTs without the "new" keywords and without " in strings. For example, the AST of the PCAT expression (x-2)+3 is constructed as follows::

new BinOpExp("plus",new BinOpExp("minus",new LvalExp(new Var("x")),new IntConst(2)),new IntConst(3))
and will be pretty-printed as:
BinOpExp(plus,BinOpExp(minus,LvalExp(Var(x)),IntConst(2)),IntConst(3))
For example, the action for the PLUS expression is:
expression ::= expression:e1 PLUS expression:e2 {: RESULT = new BinOpExp("plus",e1,e2); :}
A good way to start this project is to write a test file x.pcat outside your pcat directory that contains 1-2 lines only, such as PROGRAM IS BEGIN x:=x+1; END;, 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.

Note: The Solution.jar has been compiled with Scala 2.10. If you are using Scala 2.11 (which is the latest version), the solution may not work for you. In that case, please download Solution11.jar in your pcat directory and rename it to Solution.jar.

Note: as I have said in class, on Windows you have to edit the *.bat files. For example, build.bat. if you get an error when you execute set CLASSPATH=... this may be because you can only set PATH or CLASSPATH on Windows if you are administrator. I that case, build and run your project from an administrator account.

Hints: If a type is optional, then, if it is missing, return new NamedType("NoType"). The constant NIL has type new AnyType(). To convert a list of statements into a single statement use SeqSt. To convert a VAR declaration to a VarDec with one ID only, use a loop or a map to generate one VarDec for each VAR ID. Need to improvise for defaults: eg, if the first expression of a record-init is missing, use IntConst(1). The first rule in the grammar should set the variable PcatParser.program_ast to the entire AST of the source program because the next parser phases will use this value.

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

program ::= PROGRAM IS body:b SEMI {: PcatParser.program_ast = new ProcDecl("main","NoType",nil,b); :}

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

run 3 tests/hello.pcat
You also need to compare your output with that of the solution:
solution 3 tests/hello.pcat

After ensuring that your program compiles and executes correctly, cleanup your pcat directory using clean Then, if you are using Linux/MacOS, archive your pcat directory using tar cfz pcat.tgz pcat. If you are using Windows, zip the pcat directory into the file pcat.zip. Then submit your file (pcat.tgz or pcat.zip) here:

Submit Project #3:

Last modified: 07/14/2014 by Leonidas Fegaras