CSE5317/4305 Project #3 (Abstract Syntax)

Due Thursday March 20 before midnight

Worth 14% of your project grade


For this project, you are asked to generate ASTs (Abstract Syntax Trees) for PCAT. First you need to learn how to use the generic abstract syntax trees (Gen) used in the calculator example: Study the Gen manual very carefully and then see how it is used in calc.gen.

You need to put actions to your pcat.gen file to generate ASTs.

Your AST when printed should follow the following syntax, where { expression } means zero, one, or more expressions separated by commas (eg, expression1 ',' expression2 ',' expression3) and {',' expression } is equal to ',' { expression } for one or more expressions and equal to empty for zero expressions:

program         -> ProcDecs '(' ProcDec '(' main ',' NoTyp '()' ',' body ')' ')'
body            -> BodyDef '('  { declarations } ',' statement ')'
declarations    -> VarDecs '(' { var-dec } ')'
                -> TypeDecs '(' { type-dec } ')'
                -> ProcDecs '(' { proc-dec } ')'
var-dec         -> VarDec '(' ID ',' type ',' expression ')'
type-dec        -> TypeDec '(' ID ',' type ')' 
proc-dec        -> ProcDec '(' ID ',' type  {',' formal-param } ',' body ')' 
type            -> NamedTyp '(' ID ')'
                -> ArrayTyp '(' type ')'
                -> RecordTyp '(' { component } ')'
                -> NoTyp '()'
                -> AnyTyp '()'
component       -> Comp '(' ID ',' type ')'
formal-param    -> Param '(' ID ',' type ')'
statement       -> AssignSt '(' lvalue ',' expression ')'
                -> CallSt '(' ID {',' expression } ')'
                -> ReadSt '(' { lvalue } ')'
                -> WriteSt '(' { expression } ')'
                -> IfSt '(' expression ',' statement ',' statement ')'
                -> WhileSt '(' expression ',' statement ')'
                -> LoopSt '(' statement ')'
                -> ForSt '(' ID ',' expression ',' expression ',' expression ',' statement ')'
                -> ExitSt '(' ')'
                -> RetSt '(' [ expression ] ')'
                -> SeqSt '(' { statement } ')'
expression      -> BinOpExp '(' binop ',' expression ',' expression ')'
                -> UnOpExp '(' unop ',' expression ')'
                -> LvalExp '(' lvalue ')'
                -> CallExp '(' ID {',' expression } ')'
                -> RecordExp '(' ID {',' record-init } ')'
                -> ArrayExp '(' ID {',' array-init } ')'
                -> IntConst '(' INTEGER_LITERAL ')'
                -> RealConst '(' REAL_LITERAL ')'
                -> StringConst '(' STRING_LITERAL ')'
record-init     -> RecordInit '(' ID ',' expression ')'
array-init      -> ArrayInit '(' expression ',' expression ')'      
lvalue          -> Var '(' ID ')'
                -> ArrayDeref '(' lvalue ',' expression ')'
                -> RecordDeref '(' lvalue ',' ID ')'
binop           -> gt | lt | eq | geq | leq | neq | plus | minus | times | slash | div | mod | and | or 
unop            -> minus | not
where the binop and unop names are names of operators.

See the "Complete Concrete Syntax" section in the PCAT manual to understand the relationship between the PCAT grammar and this output syntax. For example, the AST of the PCAT expression (x-2)+3 is constructed using Gen as follows::

#<BinOpExp(plus,BinOpExp(minus,LvalExp(Var(x)),IntConst(2)),IntConst(3))>

Hints: If a type is optional, return NoTyp() if missing. NIL has type AnyTyp(). 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 to generate one VarDec for each VAR ID. Need to improvise for defaults: eg, if the first expression of 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. For example, the first rule may look like:

program ::= PROGRAM IS body:b SEMI    {: PcatParser.program_ast = #<ProcDecs(ProcDec(main,NoTyp(),`b))>; :}

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

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

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: 02/25/14 by Leonidas Fegaras