Question

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: 1. Use provided tokname function to get the name of a given token if needed. 2. Use yylval.ival to get the integer value of the INT token. How to compile the project? 1. Just build MainDriver project. . 2. 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. What to submit?  main.cpp file only Partial Sample C solution for the CFG. The functions for nonterminal factor and term is not shown. Your solution to the problem will be different,  { }  + | -  { }  *  ( ) | Number int exp(void) { //recognize non-terminal int temp = term(); //recognize term //repeat as long as the next token is ‘+’ or ‘-‘ //token is the global variable to hold the token //to be processed while ( (token == ‘+’) || (token == ‘-‘)) { switch (token) { case ‘+’: match(‘+’); temp += term(); break; case ‘-‘: match(‘-‘); temp -= term(); break; } return temp; } //match the expected token with the current one and read //next token to the global variable void match( char expectedToken) { if ( token == expectedToken) token = getchar(); //read next token else error(); //report an error }

/*
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 <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>
#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.\n";
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 )
{
   //PUT YOUR IMPLEMENTATION HERE
}

int term ( void )
{
   //PUT YOUR IMPLEMENTATION HERE
}

int factor( void )
{
   //PUT YOUR IMPLEMENTATION HERE
}

Answer 1

program code to copy

/*
  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 <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>
#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.\n";
        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) );
}


//The production for exp() contains {} indicating a 0 or more times loop which is why a while loop encloses the 2 ADDOP terminals
int exp( void )
{

        int temp = term();
        while ((nextToken == PLUS) || (nextToken == MINUS))
        {
                switch (nextToken) 
                {
                        case PLUS: match(PLUS);
                                temp += term();
                        break;
                        case MINUS: match(MINUS);
                                temp -= term();
                        break;
                }
        }
        
        return temp;
}

//term--> factor {mulop factor}
//The production for term() contains {} indicating a 0 or more times loop which is why a while loop encloses the 2 Mulop terminals
int term ( void )
{
        int temp = factor();
        while ((nextToken == DIVIDE) || (nextToken == TIMES))
        {
                switch (nextToken) 
                {
                        case TIMES:
                                match(TIMES);
                                temp *= factor();
                        break;
                        case DIVIDE:
                                match(DIVIDE);
                                temp /= factor();
                        break;
                }
        }

        return temp;
}

//factor--> ( exp ) | INT
// this production contains the choice operator indicating that there is no loop needed
// factor will either consume a '(' terminal and recurse back to exp() followed by a ')', will have parsed down to an integer value,
// or result in a syntax error which will be handled by throwing a runtime error
//it was not parsing correctly until the RPAREN check was included in LPAREN chek because it was causing the recursion to stop at the LPAREN check
//also returning exp() for LPAREN was causing it to fail at case 3 because it never was reaching base case. 
int factor( void )
{

        int temp;       

        if (nextToken == INT) 
        {
                temp = yylval.ival;
                readNextToken();
                
        }
        else if (nextToken == LPAREN) 
        {
                match(LPAREN);
                temp = exp();
                if (!match(RPAREN)) 
                {
                        throw runtime_error("Token RPAREN expected!");
                }

        }
        else
        {
                throw runtime_error("Token LPAREN or INT expected!");
        }
        
        return temp;    //returning value from if-else-stmts
}