In this assignment, it 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 of 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. When implementing a function for a non-terminal, you should follow the productions defined for that non-terminal. In this assignment, each function should return an integer, which is the value of the (sub)expressions to be evaluated.

//main.cpp /* Simple integer arithmetic calculator according to the following BNF exps --> exp | exp NEWLINE exps exp --> term {addop term} addop --> + | - term --> factor {mulop factor} mulop --> * | / factor --> ( exp ) | INT */ #include  #include  #include  #include  #include  #include "tokens.h" #include "FlexLexer.h" using namespace std; string toknames[] = { "INT", "LPAREN", "RPAREN", "PLUS", "MINUS", "TIMES", "DIVIDE", "NEWLINE" }; string tokname(int tok) { return tok<257 || tok>264 ? "BAD_TOKEN" : toknames[tok-257]; } yyFlexLexer lexer; YYSTYPE yylval; int nextToken; //global variable stores the token to be processed void readNextToken( void ); //read the next token into the variable nextToken void exps( void ); //process all expressions in the input int exp( void ); //returns the integer value of an expression int term ( void ); //returns the integer value of an term int factor( void ); //returns the integer value of an factor //If the next token matches expectedToken, read the next token and return true //otherwise, print an error message and return false bool match( int expectedToken ); //print the error message void error( string errorMsg ); //skip the rest of the line void skipline( void ); int main(int argc, char **argv) { ifstream ifs; if (argc!=2) { cerr << "usage: " << argv[0] << " filename" << endl; return 1; } ifs.open( argv[1] ); if( !ifs ) { cerr << "Input file cannot be opened. "; return 0; } cout << "Lexcial Analysis of the file " << argv[1] << endl; lexer.switch_streams(&ifs, NULL); readNextToken(); exps(); return 0; } //print the error message, and //terminate the program void error( string errorMsg ) { cout << errorMsg << endl; exit(1); } //skip the rest of the line void skipline( void ) { while( nextToken != NEWLINE && nextToken != 0 ) readNextToken(); } //read the next token into the variable nextToken void readNextToken( void ) { nextToken = lexer.yylex(); } //If the next token is expectedToken, call readNextToken and return true, //otherwise, print an error message and return false bool match( int expectedToken ) { if ( expectedToken == nextToken ) { readNextToken(); return true; } else return false; } void exps( void ) { int count = 1; int value; do { try { value = exp(); cout << "expression " << count << " : " << value << endl; } catch(runtime_error e) { skipline(); cout << "expression " << count << " : wrong syntax -- " << e.what() << endl; } count ++; } while ( match(NEWLINE) ); } //returns the integer value of an expression int exp( void ) { term(); while(nextToken == '+' || nextToken == '-') { match(PLUS); match(MINUS); term(); } } int term ( void ) { factor(); while(nextToken == '*' || nextToken == '/') { match(TIMES); match(DIVIDE); factor(); } } int factor( void ) { if(nextToken == 'id' || nextToken == 'int_constant') match(INT); else { if(nextToken == '(' ) { match(LPAREN); exps(); if(nextToken == ')') match(RPAREN); else throw runtime_error("Error: Token LPAREN or INT expected!"); } else throw runtime_error("Error: Token LPAREN or INT expected!"); } }

//test0.txt.bak 10 - 5 - 20 / 3 -5 (10 + 5) / 3 (10 - 5 * 3) - 10 / 20 - 0 (10 - 5 * 3 - 10 / 20 - 0 10 + 5 * 3 / 2 - 9

Lexcial Analysis of the file test0.txt expression 1 : wrong syntax -- Error: Token LPAREN or INT expected! expression 2 : wrong syntax -- Error: Token LPAREN or INT expected! expression 3 : wrong syntax -- Error: Token LPAREN or INT expected! expression 4 : wrong syntax -- Error: Token LPAREN or INT expected! expression 5 : wrong syntax -- Error: Token LPAREN or INT expected! expression 6 : wrong syntax -- Error: Token LPAREN or INT expected!

I didn't print correctly

//This is what the output supposed to look like Lexcial Analysis of the file test0.txt expression 1 : -1 expression 2 : wrong syntax -- Error: Token LPAREN or INT expected! expression 3 : 5 expression 4 : -5 expression 5 : wrong syntax -- Error: Token RPAREN expected! expression 6 : 8

Can you help me with a recursive descent parser in C++?