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

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

Attached are the files for the program, and the grammar rules. These files include a header file for Lexical analysis, a lexical analysis file, a header file for the parsing, and a parser.cpp.

Here is the grammar rules:

There is an EBNF grammar for a simple language and this grammar uses tokens. It defines nine different nonterminal symbols. The start symbol for the grammar is Prog. For this assignment, you will write a recursive descent parser for this grammar. Your goal is to build a parse tree, perform some semantic checks on the tree, and generate some test output.

The lexical analyzer file has a getToken() function to read tokens, and to implement

nine functions for this parser. A skeleton implementation will be provided for you. You should

use the provided parser.h and lexer.h files. You should not change lexer.h. You may add any

other files, or change any other files that are given to you.

For this assignment, you must create a main routine that parses input, either from a file or, if no

filename is specified, from the standard input. An optional -t argument may be provided.

If the program is unable to open a file, it must print the filename followed by INVALID FILE,

and should then stop.

In all situations that require the generation of an error message, if the error message is specified

to include a filename, and if there is no filename (i.e. the standard in case), then the message

should NOT include the filename: portion of the message.

The nine 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

Semantic rules associated of this language:

1. There are only two types permitted: integer and string.

2. Variables must be declared before they are used. They are declared with Decl.

3. There is one single scope for variables.

4. Variable names must be unique; once a name has been declared, it may not be

declared again.

5. An integer constant is of type integer.

6. A string constant is of type string.

7. The type of an identifier is the type assigned when it is declared.

8. The type of an Expr or a Term is the type of the result of the operation.

9. Adding two integers results in an integer representing the sum

10. Subtracting two integers results in an integer representing the difference

11. Multiplying two integers results in an integer representing the product

12. Dividing two integers results in an integer representing the quotient

13. Adding two strings results in a string representing the concatenation

14. Multiplying an integer by a string results in a string which is the string operand repeated

integer times (i.e. 3 * hi is hihihi)

15. Dividing two strings results in an a string where the first instance of the denominator that is found in the numerator is removed.

16. ALL OTHER COMBINATIONS OF OPERATIONS ARE UNDEFINED and are an error.

17. A variable is assigned a value using a Set. The type of the variable being set must match

the type of the expression; if it does not this is an error.

18. An expression can be printed using either print or println. In both cases, the value of the Expr is printed to the standard output. In the case of println, a newline is printed to standard out at the end of the execution of the program.

If the program finds a syntax error during the parse, it should print a message in the following format: filename: linenumber: Syntax error {some message describing the error} If the program finds any errors during the parse phase, it should terminate after the parse. If the -t flag argument is specified, then the program should produce a trace of the tree. A trace is performed by doing a postorder traversal of the parse tree and printing output during the traversal, as follows:

Before following the left child in the tree, print the letter L

After following the left child in the tree, print the letter u

Before following the right child in the tree, print the letter R

After following the right child in the tree, print the letter U

To visit the node, print the letter N

All of these characters should be printed on a single line with a newline printed at the end.

Next, the program should perform tests to ensure compliance with semantic rules #2 and #4. If the input does not comply with those rules then, after printing any error messages, the program should terminate. If the semantic checks are all successful, then it should traverse the tree, gather statistics, and print a report on the statistics in the format below:

Total number of identifiers: A

Total number of set: A

Total number of +: A

Total number of *: A

Where A is the total count for, respectively, identifiers, sets, + operators, and * operators. Note that you should NOT gather these statistics by counting tokens, but rather by traversing the tree.

If semantic check #3 fails, the program should print a message in the following format:

Filename:linenumber:variable AA is used before being declared

If semantic check #7 fails, the program should print a message in the following format:

Filename:linenumber:variable AA was already declared

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

Here is the source code for the files:

1. header file for Lexical analysis

#ifndef LEXER_H_ #define LEXER_H_

#include #include using std::string; using std::istream; using std::ostream;

enum TokenType { // keywords T_INT, T_STRING, T_SET, T_PRINT, T_PRINTLN,

// an identifier T_ID,

// an integer and string constant T_ICONST, T_SCONST,

// the operators, parens and semicolon T_PLUS, T_MINUS, T_STAR, T_SLASH, T_LPAREN, T_RPAREN, T_SC,

// any error returns this token T_ERROR,

// when completed (EOF), return this token T_DONE };

class Token { TokenType tt; string lexeme; int lnum;

public: Token(TokenType tt = T_ERROR, string lexeme = "") : tt(tt), lexeme(lexeme) { extern int lineNumber; lnum = lineNumber; }

bool operator==(const TokenType tt) const { return this->tt == tt; } bool operator!=(const TokenType tt) const { return this->tt != tt; }

TokenType GetTokenType() const { return tt; } string GetLexeme() const { return lexeme; } int GetLinenum() const { return lnum; } };

extern ostream& operator<<(ostream& out, const Token& tok);

extern Token getToken(istream* br);

#endif /* LEXER_H_ */

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

2. Lexical Analyzer Code (lexicalanalyzer.cpp):

#include #include

#include "lexer.h"

static map tokenPrint = { { T_INT, "T_INT" }, { T_STRING, "T_STRING" }, { T_SET, "T_SET" }, { T_PRINT, "T_PRINT" }, { T_PRINTLN, "T_PRINTLN" },

{ T_ID, "T_ID" },

{ T_ICONST, "T_ICONST" }, { T_SCONST, "T_SCONST" },

{ T_PLUS, "T_PLUS" }, { T_MINUS, "T_MINUS" }, { T_STAR, "T_STAR" }, { T_SLASH, "T_SLASH" }, { T_LPAREN, "T_LPAREN" }, { T_RPAREN, "T_RPAREN" }, { T_SC, "T_SC" },

{ T_ERROR, "T_ERROR" },

{ T_DONE, "T_DONE" } };

ostream& operator<<(ostream& out, const Token& tok) { TokenType tt = tok.GetTokenType(); out << tokenPrint[ tt ]; if( tt == T_ID || tt == T_ICONST || tt == T_SCONST || tt == T_ERROR ) { out << "(" << tok.GetLexeme() << ")"; } return out; }

static map kwmap = { { "int", T_INT }, { "string", T_STRING }, { "set", T_SET }, { "print", T_PRINT }, { "println", T_PRINTLN }, };

Token id_or_kw(const string& lexeme) { TokenType tt = T_ID;

auto kIt = kwmap.find(lexeme); if( kIt != kwmap.end() ) tt = kIt->second;

return Token(tt, lexeme); }

Token getToken(istream* br) { enum LexState { BEGIN, INID, INSTRING, ININT, ONESLASH, INCOMMENT } lexstate = BEGIN; string lexeme;

for(;;) { int ch = br->get(); if( br->bad() || br->eof() ) break;

if( ch == ' ' ) { extern int lineNumber; ++lineNumber; }

switch( lexstate ) { case BEGIN: if( isspace(ch) ) continue;

lexeme = ch;

if( isalpha(ch) ) { lexstate = INID; } else if( ch == '"' ) { lexstate = INSTRING; } else if( isdigit(ch) ) { lexstate = ININT; } else if( ch == '/' ) { lexstate = ONESLASH; } else { TokenType tt = T_ERROR; switch( ch ) { case '+': tt = T_PLUS; break; case '-': tt = T_MINUS; break; case '*': tt = T_STAR; break; case '(': tt = T_LPAREN; break; case ')': tt = T_RPAREN; break; case ';': tt = T_SC; break; }

return Token(tt, lexeme); } break;

case INID: if( isalpha(ch) || isdigit(ch) ) { lexeme += ch; } else { br->putback(ch); return id_or_kw(lexeme); } break;

case INSTRING: lexeme += ch; if( ch == ' ' ) { return Token(T_ERROR, lexeme ); } if( ch == '"' ) { return Token(T_SCONST, lexeme ); } break;

case ININT: if( isdigit(ch) ) { lexeme += ch; } else if( isalpha(ch) ) { lexeme += ch; return Token(T_ERROR, lexeme); } else { br->putback(ch); return Token(T_ICONST, lexeme); } break;

case ONESLASH: if( ch != '/' ) { br->putback(ch); return Token(T_SLASH, lexeme ); } lexstate = INCOMMENT; break;

case INCOMMENT: if( ch == ' ' ) { lexstate = BEGIN; } break; }

} if( br->eof() ) return T_DONE; return T_ERROR; }

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

3. Header file for the parser (parser.h):

#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_ */

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

4. Parser cpp file (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; }