Goal: To know how to construct a recursive descent parser.
Description:
In this assignment, you need to implement a recursive descent parser in C++ for the following CFG:
1. exps
-- exp |
exp NEWLINE exps
2. exp
-- term {addop term}
3. addop
--+|-
4. term
-- factor {mulop factor}
5. mulop
--*|/
6. factor
-- ( exp ) | INT
The 1st production defines exps as an individual expression, or a sequence expressions separated by NEWLINE token.
The 2nd production describes an expression as a term followed by addop term zero, one, or more times, i.e. exp can be: term, or term addop term, or term addop term addop term, or term addop term addop term addop term, …
The 4th production describes the definition of term, which is pretty much similar to 2nd production.
The 6th production defines a factor either as an expression enclosed by a pair of parentheses or an integer.
In recursive descent parsing, a function is defined for each non-terminal, i.e. exps, exp, term, and factor in our case. The non-terminals addop and mulop are too simple so that we will process them directly in functions of exp and term respectively. All functions for non-terminals should return the integers, which are the values of (sub)expressions to be evaluated.
For you convenience, a partial C sample solution is provided for the CFG at the end of this document. This sample is only for your reference. A java solution to the similar problem can also be found here: http://web.cse.ohio-state.edu/software/2231/web-sw2/extras/slides/27.Recursive-Descent-Parsing.pdf.
Tips:
Use provided tokname function to get the name of a given token if needed.
Use yylval.ival to get the integer value of the INT token.
How to compile the project?
Just build MainDriver project. .
Then, you should be able to run the program. Remember, the program read expressions from test0.txt.
What to do in this project?
You only need to work on main.cpp file by providing implementation of three functions: exp, term, and factor. Each function returns an integer as the value of sub-expression that has been parsed/evaluated so far.
If there is a syntax error detected, please throw a runtime exception so that function exps can skip the rest of the expressions and continue the parsing of next expressions. The syntax of throwing a runtime exception is given below:
throw runtime_error( a string of error information ); In this CFG, you typically can detect errors in factor function.
How to submit?
Copy the rubric3.doc and your work to a working copy of your repository. Edit the file rubric3.doc to put your name.
Commit the whole working copy to the server.
Any commit of the project after the deadline is considered as cheating. If this happens, the latest version before the deadline will be graded, and you may receive up to 50 points deduction.
No hard copy needed
Partial Sample C solution for the CFG. The functions for nonterminal factor and term
