COMPSCI 2000 Computer Systems - Practical Assignment 7: Recursive Descent Parser
Practical Assignment 7
Assessment Overview
Your Task
Your task for this practical assignment is to write a parser to convert high-level language programs into a parse tree that can be later converted to VM Code.
1. Complete the Parser as described and as outlined below.
· Submit your work regularly to Gradescope as you progress.
· Additional resources and help will be available during your workshop sessions.
2. Test your code.
We're know that things are tight at the end of semester, so we've kept this assignment short (and hopefully simple).
Part 1 - Recursive Descent Parser (80 points)
We've seen VM Code and how that can be translated to Assembly and Machine code, but these languages are represented as basic sequences of instructions -- how do we handle the nested and varied structures of high-level programming languages?
Using your preferred programming language (Python, C++ or Java) implement the CompilerParser as described below.
This practical assignment follows a similar approach to the Nand2Tetris Compilation Engine.
You will need to complete the methods provided in the CompilerParser class. The provided ParseTree & Token classes should not be modified.
Only submit files for 1 programming language.
Getting Started
1. Start by reviewing chapter 10 of the textbook.
2. Each of the methods listed below needs to apply the corresponding set of grammar rules to the series of tokens given.
For each set of these grammar rules:
A new parse tree is created.
The tokens are processed 1-by-1.
Tokens matching the grammar rule are added to a ParseTree for that rule.
If the rules are broken (i.e. the sequence of tokens does not match the rules), a ParseException should be thrown/raised.
Otherwise the ParseTree data structure is returned.
Some of the sets grammar rules require other sets of grammar rules.
For example, the whileStatement rule requires the rules for expression and statements.
These rule sets should be applied recursively.
3. A ParseTree data structure is returned
Tokens
Each token has a type and corresponding value. Tokens can have the following types:
identifier
We can read the type of the token with the Token.getType() method, and its value with Token.getValue()
Parse Trees
Each node in the ParseTree has a type, a value, and a list of children (parse trees nested inside this tree).
When creating a ParseTree, we set the type and value in the constructor. We can then add parse trees via the method. If needed, we can read the type of the ParseTree with the method, and its value with ParseTree.getValue() .
ParseTrees can have the following types:
keyword
symbol
integerConstant
stringConstant
class
classVarDec
subroutineDec
parameterList
subroutineBody
varDec
statements
letStatement
ifStatement
whileStatement
ParseTree.addChild(ParseTree)
ParseTree.getType()
doStatement
returnStatement
expression
term
expressionList
Which match the methods we're implementing.
They can also have the same types as listed above for Tokens (and Tokens can be added as children to ParseTrees via typecasting)
You may have noticed that elements shown in the Jack Grammar are missing from this list. These are not included as their values are covered as part of other elements, for example,
unaryOp elements are just symbols, and className elements are just identifiers.
To review the structure of a ParseTree object, it can be printed; this will output a human readable representation.
Task 1.1 - Program Structure (40 points)
Complete the program structure related methods:
compileVarDec
compileProgram
compileClass
compileClassVarDec
compileSubroutine
compileParameterList
compileSubroutineBody
Task 1.2 - Statements (40 points)
Complete the statement related methods:
compileReturn
compileStatements
compileLet
compileIf
compileWhile
compileDo
Task 1.3 - Expressions (Optional - up to 20 BONUS points)
Complete the expression related methods:
This section is optional and is worth Bonus Points
compileExpressionList
compileExpression
compileTerm
You're done!
Submit your work to Gradescope using the button below.
You may submit via file upload or GitHub.
If using GitHub, ensure your repository is private. Your files should either be:
In the root of your submission (i.e. no subdirectory) ~ or ~
In a directory named prac7
Be sure to submit all files with each submission.
Additional Resources
The session for this tool has expired. Please reload the page to access the tool again
The following resources may help you complete this assignment:
Chapter 10 of the Text Book for Compiler Implementation
Week 11 & 12 Workshops
Guide to Testing and Writing Test Cases
Figure 10.5 on page 201 of the Text Book for specification of the Jack Grammar. Further resources will be added over the coming days.
This tool needs to be loaded in a new browser window
