Need a working C++ program that given grammar rules is able to build a recursive descent parser to construct a parse tree.

The program should also be able to perform a post order traversal of the parse tree and print the output during the traversal.

Attached are the files for the program, and the grammar rules. The parser is able to read various tokens in the input using a token() function.

These files included are a header file for the parsing, and a parser.cpp.

Grammar Rules:

The grammar rules are below:

Prog ::= StmtList

StmtList ::= { Stmt T_SC } { StmtList }

Stmt ::= Decl | Set | Print

Decl ::= T_INT T_ID | T_STRING T_ID

Set ::= T_SET T_ID Expr

Print ::= T_PRINT Expr | T_PRINTLN Expr

Expr ::= Term { (T_PLUS|T_MINUS) Expr }

Term ::= Primary { (T_STAR|T_SLASH) Term }

Primary ::= T_ICONST | T_SCONST | T_ID | T_LPAREN Expr T_RPAREN

---------------------------------------------------------------------

parser header file:

#ifndef PARSER_H_ #define PARSER_H_

#include using std::istream;

#include using std::string; using std::stoi;

#include "lexer.h"

extern void error(int linenum, const string& message);

enum TypeForNode { INT_TYPE, STRING_TYPE, ERROR_TYPE };

class ParseTree { int linenumber; ParseTree *left; ParseTree *right;

public: ParseTree(int n, ParseTree *l = 0, ParseTree *r = 0) : linenumber(n), left(l), right(r) {} virtual ~ParseTree() {}

ParseTree* getLeft() const { return left; } ParseTree* getRight() const { return right; } int getLineNumber() const { return linenumber; }

virtual TypeForNode GetType() const { return ERROR_TYPE; } virtual int GetIntValue() const { throw "no integer value"; } virtual string GetStringValue() const { throw "no string value"; } };

class StatementList : public ParseTree { public: StatementList(ParseTree *first, ParseTree *rest) : ParseTree(0, first, rest) {}

};

class Addition : public ParseTree { public: Addition(int line, ParseTree *op1, ParseTree *op2) : ParseTree(line, op1, op2) {}

// will need to fill in type and value; // remember type is a function of };

class Subtraction : public ParseTree { public: Subtraction(int line, ParseTree *op1, ParseTree *op2) : ParseTree(line, op1, op2) {}

// will need to fill in type and value; // remember type is a function of };

class IntegerConstant : public ParseTree { int value;

public: IntegerConstant(const Token& tok) : ParseTree(tok.GetLinenum()) { value = stoi( tok.GetLexeme() ); }

TypeForNode GetType() const { return INT_TYPE; } int GetIntValue() const { return value; } };

extern ParseTree * Prog(istream* in); extern ParseTree * StmtList(istream* in); extern ParseTree * Stmt(istream* in); extern ParseTree * Decl(istream* in); extern ParseTree * Set(istream* in); extern ParseTree * Print(istream* in); extern ParseTree * Expr(istream* in); extern ParseTree * Term(istream* in); extern ParseTree * Primary(istream* in);

#endif /* PARSER_H_ */

-------------------------------------------------------------------------

Parser.cpp:

#include using std::string;

#include "parser.h"

class ParserToken { private: Token tok; bool pushedBack;

public: ParserToken() : pushedBack(false) {}

Token getToken(istream *in) { if( pushedBack ) { pushedBack = false; return tok; }

return ::getToken(in); } void pushbackToken(const Token& t) { if( pushedBack ) { // error } tok = t; pushedBack = true; } } ParserToken;

void error(const string& msg) { return; }

ParseTree * Prog(istream* in) { return StmtList(in); }

ParseTree * StmtList(istream* in) { ParseTree *stmt = Stmt(in); if( stmt == 0 ) return 0;

return new StatementList( stmt, StmtList(in) ); }

ParseTree * Stmt(istream* in) { return 0; }

ParseTree * Decl(istream* in) { return 0; }

ParseTree * Set(istream* in) { return 0; }

ParseTree * Print(istream* in) { return 0; }

ParseTree *Expr(istream* in) { ParseTree *t1 = Term(in); if( t1 == 0 ) return 0;

for(;;) { Token op = ParserToken.getToken(in); if( op != T_PLUS && op != T_MINUS ) { ParserToken.pushbackToken(op); return t1; }

ParseTree *t2 = Expr(in); if( t2 == 0 ) { error(op.GetLinenum(), "expression required after + or - operator"); return 0; }

// combine t1 and t2 together if( op == T_PLUS ) t1 = new Addition(op.GetLinenum(), t1, t2); else t1 = new Subtraction(op.GetLinenum(), t1, t2); }

// should never get here... return 0; }

ParseTree * Term(istream* in) { return 0; }

ParseTree * Primary(istream* in) { return 0; }

---------------------------------------------------