Skip to main content
Compilers
Syllabus
Practice
Homework
Textbook
FAQ
Parser for Decaf
Start on Jun 4, 2019
Due on Jun 18, 2019
Your task for this homework is to write a parser for the Decaf programming language.
Yacc
We will be using a parser generator called Yacc to do this homework. Before you start programming for this homework it is very important you work through the Yacc practice problems first.
The programming tool is called yacc and the implementation we will be using is GNU bison.
Getting Started
You must have git and python (3.x) on your system to run the assignments. Once you’ve confirmed this, run this command:
git clone https://github.com/anoopsarkar/compilers-class-hw.git
In the decafast directory you will find various python programs which you will use to test your solution to this homework.
If you have already cloned the repository earlier you can get the new homework files by going to the directory where you cloned the repository earlier and then doing:
# go to the directory where you did a git clone earlier
git pull origin master
To get started with your homework do the following steps.
Copy over files to your repository
Assuming you have set up your repository using the instruction in HW0, clone your repository and enter that directory and copy over the files:
git clone git@csil-git1.cs.surrey.sfu.ca:YOUR_USERNAME/CMPT379-1194-YOUR_USERNAME.git
cd CMPT379-1194-YOUR_USERNAME
mkdir -p decafast
cd decafast
cp -r /your-path-to/compilers-class-hw/decafast/* .
git add *
git commit -m ‘initial commit’
git push
If you update my repository using git pull then you might have to copy over the new files into your repository. Be careful you do not clobber your own files in the answer directory.
Default solution
Your solution must be compiled in the answer directory and must be called decafast. There is an incomplete solution to this homework in the answer directory. You can create the default binary as follows:
cd your-repo-name/answer
make default
Creating Decafast
Make new copies of the following default files for decafast:
cp default.cc decafast.cc
cp default.lex decafast.lex
cp default.y decafast.y
Modify decafast.cc to replace #include “default.tab.h” with #include “decafast.tab.h”.
Modify decafast.lex to replace #include “default.tab.h” with #include “decafast.tab.h”.
Modify decafast.y to replace #include “default.cc” with #include “decafast.cc”.
Build the decafast executable by running:
make decafast
The Challenge
The goal of this homework is to write a parser for the Decaf programming language. The details of the structure of Decaf programs is given in the Decaf specification:
Decaf specification
Read the specification carefully before you attempt to write any code to solve this homework.
Your Task
Using the Decaf language specification as your guide, provide a parser for the Decaf language that produces an abstract syntax tree for valid Decaf programs.
An abstract syntax tree (AST) is a high-level representation of the program structure without the necessity of containing all the details in the source code; it can be thought of as an abstract representation of the source code.
The specification for the abstract syntax tree to be produced by your program is given below using the Zehpyr Abstract Syntax Definition Language.
— Decaf abstract syntax tree definition
— The specification of the AST nodes is specified using the Zephyr
— Abstract Syntax Definition Language (ASDL) [Wang97]
— The abstract syntax tree (AST) is a high-level representation
— of the program structure without the necessity of containing the
— source code; it can be thought of as an abstract representation of
— the source code.
— Modifiers on the argument type specify the number of values
— needed; ‘?’ means it is optional, ‘*’ means 0 or more (with commas),
— no modifier means only one value for the argument and it is required.
— For * print a singleton for one element, or multiple
— elements seperated by commas, or None for the zero element.
— ASDL’s four builtin types are identifier, int, string, object
module Decaf
{
prog = Program(extern* extern_list, package body)
extern = ExternFunction(identifier name, method_type return_type, extern_type* typelist)
decaf_type = IntType | BoolType
method_type = VoidType | decaf_type
extern_type = VarDef(StringType) | VarDef(decaf_type)
package = Package(identifier name, field_decl* field_list, method_decl* method_list)
field_decl = FieldDecl(identifier name, decaf_type type, field_size size)
| AssignGlobalVar(identifier name, decaf_type type, constant value)
field_size = Scalar | Array(int array_size)
method_decl = Method(identifier name, method_type return_type, typed_symbol* param_list, method_block block)
typed_symbol = VarDef(identifier name, decaf_type type)
method_block = MethodBlock(typed_symbol* var_decl_list, statement* statement_list)
block = Block(typed_symbol* var_decl_list, statement* statement_list)
statement = assign
| method_call
| IfStmt(expr condition, block if_block, block? else_block)
| WhileStmt(expr condition, block while_block)
| ForStmt(assign* pre_assign_list, expr condition, assign* loop_assign_list, block for_block)
| ReturnStmt(expr? return_value)
| BreakStmt
| ContinueStmt
| block
assign = AssignVar(identifier name, expr value)
| AssignArrayLoc(identifier name, expr index, expr value)
method_call = MethodCall(identifier name, method_arg* method_arg_list)
method_arg = StringConstant(string value)
| expr
expr = rvalue
| method_call
| constant
| BinaryExpr(binary_operator op, expr left_value, expr right_value)
| UnaryExpr(unary_operator op, expr value)
constant = NumberExpr(int value)
| BoolExpr(bool value)
rvalue = VariableExpr(identifier name)
| ArrayLocExpr(identifier name, expr index)
bool = True | False
binary_operator = Plus | Minus | Mult | Div | Leftshift | Rightshift | Mod | Lt | Gt | Leq | Geq | Eq | Neq | And | Or
unary_operator = UnaryMinus | Not
}
— References
— [Wang97] Daniel C. Wang, Andrew W. Appel, Jeff L. Korn, and Chris
— S. Serra. The Zephyr Abstract Syntax Description Language. In
— Proceedings of the Conference on Domain-Specific Languages, pp.
— 213–227, 1997.
view raw
Decaf.asdl hosted with ❤ by GitHub
Make sure you obey the following requirements:
1. If your program succeeds in parsing the input you should exit from your program using exit(EXIT_SUCCESS). And if your program finds an error in the input Decaf program you should exit using exit(EXIT_FAILURE). The definitions of EXIT_SUCCESS and EXIT_FAILURE are in cstdlib (for C++) and in stdlib.h (for C).
2. The abstract syntax tree produced by your program must be in the format specified above. The output specification is also available as the file Decaf.asdl in the decafast directory.
3. Do not add whitespace in your output. This might cause issues with matching your output to the reference output.
Development and upload procedure
Remember to push your solution source code to your repository:
cd answer
git add decafast.y decafast.lex # and any other files such as decafast.cc and decafast-defs.h
git commit -m ‘initial solution’
git push
Then each time you finish a component of your solution you can push it to the remote repository:
git add [source-file]
git commit -m ‘commit message’ [source-file]
git push
You have been given three helper programs to help you develop your solution to this homework.
Run your solution on testcases
Run your solution program on the testcases using the Python program zipout.py. Your solution must be compiled in the answer directory and must be called decafast. Run against all testcases as follows:
# go to the directory with the file zipout.py
python3 zipout.py
This creates a directory called output and a file output.zip which can be checked against the reference output files (see section on Check your solution below).
If you run zipout.py multiple times it will overwrite your output directory and zip file which should be fine most of the time (but be careful).
Check your solution
Check your solution accuracy using the Python program check.py. You must create an output.zip file using the above step in Run your solution on testcases. Note that the references are only available for the dev testcases. When you are graded you will be evaluated on both the dev and test testcases. output.zip contains your output for both sets of testcases.
You can use the default program provided to get an initial solution to this homework. Run python3 zipout.py -r default to get a source.zip file you can score.
python3 check.py
Correct(dev): 39 / 124
Score(dev): 39.00
Total Score: 39.00
Package your source for Coursys
You must also upload your source code to Coursys. You should prepare your source for upload using the Python program zipsrc.py.
# go to the directory with the file zipsrc.py
python3 zipsrc.py
This will create a zip file called source.zip. You should upload this file as your submission to hw2 on Coursys.
Be careful: zipsrc.py will only package files in the answer directory. Make sure you have put all your supporting files in that directory. In particular, put relevant documentation into answer/README.md.
If you add any testcases of your own please put them in the directories answer/testcases/[your-username]/ and answer/references/[your-username]/ using the same convention used by zipout.py and check.py.
Ground Rules
• You must turn in two things:
◦ Your source code from the answer directory as a zip file source.zip produced by running python3 zipsrc.py must be uploaded to the hw2 submission page on Coursys.
◦ Your output on the testcases which is the file output.zip produced by running python3 zipout.py must be uploaded to the hw2 submission page on Coursys. When we run check.py on the public testcases it should have a value higher than the output from the default program to get any marks.
• Your source code from source.zip must be on your gitlab repository. Please commit and push often in order to get feedback on your code.
• Make sure that we can run make decafast in your answer directory to create the decafast binary.
• You cannot use data or code resources outside of what is provided to you. If you use external code snippets provide citations in the answer/README.md file.
• For future homeworks, for the written description of your solution and supporting documentation, you can use plain ASCII but for math equations it is better to use kramdown. Do not use any proprietary or binary file formats such as Microsoft Word.
Grading
• Score for testcases both dev and test.
• Code review by TAs. Please check for comments on your code on gitlab.
If you have any questions or you’re confused about anything, just ask.
Last updated June 17, 2019.
Forked from the JHU MT class code on github by Matt Post and Adam Lopez.