The assignment will create a recursive descent parser for a little language for polynomials, and will implement an interpreter for the language.

The grammar for our language is as follows:

Prog := Stmt | Stmt Prog

Stmt := Set ID Expr SC | PRINT Expr SC

Expr := Term { (+|-) Expr }

Term := Primary { * Term }

Primary := ICONST | FCONST | STRING | ( Expr ) | Poly

Poly := LBR Coeffs RBR { EvalAt } | ID { EvalAt }

Coeffs := Coeff { , Coeff } Coeff := ICONST | FCONST

EvalAt := LSQ Expr RSQ

Note that there are 9 rules so there may be 9 functions, one per rule; you may decide that you want to combine some rules together for ease of implementation. Some examples:

set f { 1, 2, 4 }; # f is x^2 + 2x + 4

print f[0] ; # should print 4

set f { 2,0,0,1 }; # 2x^3 + 1

set g { 1,0, 0 }; # x^2 set x 2;

set gofx g[x]; ## should be 4 (2^2)

set fofgofx f[ gofx ]; ### should be 129

print {1,1,1,1}[2]; ## should print 2^3 + 2^2 + 2 + 1 or 15

print {1,1,1}*2; ## should print {2,2,2} print 3 + 4*5; ## should print 23 0

Every error detected in the parse phase must be printed on its own line with the first words as PARSE ERROR: A runtime error should be printed on its own line with the first words RUNTIME ERROR: There are four operations: addition, subtraction, multiplication, and polynomial evaluation. The language has the following semantic rules:

1. An identifier must be set before it can be used

2. Addition, subtraction and multiplication associate left to right

3. All binary operators are commutative; if we specify the behavior of integer op float, then that behavior applies to float op integer

4. Addition is defined between the following like types: two integers, two floating point numbers, two strings, or two polynomials.

5. String addition is concatenation

6. A mixed mode expression of integer + float causes the integer to be converted to a float

7. A mixed mode expression of either integer or float + poly causes the integer or float to be converted to a poly

8. Subtraction is defined between the following like types: two integers, two floating point numbers, or two polynomials. Note: string subtraction is not defined.

9. A mixed mode expression of integer - float causes the integer to be converted to a float

10. A mixed mode expression of either integer or float - poly causes the integer or float to be converted to a poly

11. Multiplication is defined between the following like types: two integers, two floating point numbers, or two polynomials. Note: multiplying a string by another string is not defined.

12. A mixed mode expression of integer * float causes the integer to be converted to a float

13. A mixed mode expression of either integer or float * poly causes the integer or float to be converted to a poly

14. A mixed mode expression of string * int results in a string that is repeated int times

15. Polynomials can only be evaluated at integer or float values

16. ALL OTHER COMBINATIONS OF OPERATORS AND TYPES ARE ERRORS

17. EvalAt means calculating the value of a polynomial for a particular value

18. Set evaluates the expression and binds the value to the variable named in the set statement

19. Print evaluates the expression and prints its value

20. When asked to print a polynomial, the Print statement prints a curly-brace enclosed, comma-separated list of coefficients

21. Strings are printed without their quotation marks.

Code to use:

#include "ParseNode.h" // We want to use our getToken routine unchanged... BUT we want to have the ability // to push back a token if we read one too many; this is our "lookahead" // so we implement a "wrapper" around getToken static bool pushedBack = false; static Token pushedToken; Token GetToken(istream& in) { if( pushedBack ) { pushedBack = false; return pushedToken; } return getToken(in); } void PutBackToken(Token& t) { if( pushedBack ) { cout << "You can only push back one token!" << endl; exit(0); } pushedBack = true; pushedToken = t; } // handy function to print out errors void error(string s) { cout << currentLine << s << endl; ++globalErrorCount; } // Prog := Stmt | Stmt Prog ParseNode *Prog(istream& in) { ParseNode *stmt = Stmt(in); if( stmt != 0 ) return new StatementList(stmt, Prog(in)); return 0; } // Stmt := Set ID Expr SC | PRINT Expr SC ParseNode *Stmt(istream& in) { Token cmd = GetToken(in); if( cmd == SET ) { Token idTok = GetToken(in); if( idTok != ID ) { error("Identifier required after set"); return 0; } ParseNode *exp = Expr(in); if( exp == 0 ) { error("expression required after id in set"); return 0; } if( GetToken(in) != SC ) { error("semicolon required"); return 0; } return new SetStatement(idTok.getLexeme(), exp); } else if( cmd == PRINT ) { ParseNode *exp = Expr(in); if( exp == 0 ) { error("expression required after id in print"); return 0; } if( GetToken(in) != SC ) { error("semicolon required"); return 0; } return new PrintStatement(exp); } else PutBackToken(cmd); return 0; } ParseNode *Expr(istream& in) { return 0; } ParseNode *Term(istream& in) { return 0; } // Primary := ICONST | FCONST | STRING | ( Expr ) | Poly ParseNode *Primary(istream& in) { // check tokens... or call Poly return 0; } // Poly := LCURLY Coeffs RCURLY { EvalAt } | ID { EvalAt } ParseNode *Poly(istream& in) { // note EvalAt is optional return 0; } // notice we don't need a separate rule for ICONST | FCONST // this rule checks for a list of length at least one ParseNode *Coeffs(istream& in) { return 0; } ParseNode *EvalAt(istream& in) { return 0; } 

#ifndef PARSENODE_H_ #define PARSENODE_H_ #include #include using std::istream; using std::cout; using std::endl; using std::string; #include "polylex.h" extern int globalErrorCount; // objects in the language have one of these types enum Type { INTEGERVAL, FLOATVAL, STRINGVAL, UNKNOWNVAL, }; // this class will be used in the future to hold results of evaluations class Value { int i; float f; string s; Type t; public: Value(int i) : i(i), f(0), t(INTEGERVAL) {} Value(float f) : i(0), f(f), t(FLOATVAL) {} Value(string s) : i(0), f(0), s(s), t(STRINGVAL) {} Type GetType() { return t; } int GetIntValue(); float GetFloatValue(); string GetStringValue(); }; // every node in the parse tree is going to be a subclass of this node class ParseNode { ParseNode *left; ParseNode *right; public: ParseNode(ParseNode *left = 0, ParseNode *right = 0) : left(left), right(right) {} virtual ~ParseNode() {} virtual Type GetType() { return UNKNOWNVAL; } }; // a list of statements is represented by a statement to the left, and a list of statments to the right class StatementList : public ParseNode { public: StatementList(ParseNode *l, ParseNode *r) : ParseNode(l,r) {} }; // a SetStatement represents the idea of setting id to the value of the Expr pointed to by the left node class SetStatement : public ParseNode { string id; public: SetStatement(string id, ParseNode* exp) : id(id), ParseNode(exp) {} }; // a PrintStatement represents the idea of printing the value of the Expr pointed to by the left node class PrintStatement : public ParseNode { public: PrintStatement(ParseNode* exp) : ParseNode(exp) {} }; // represents adding, or subtracting, the two child expressions class PlusMinusOp : public ParseNode { public: PlusMinusOp(ParseNode *l, ParseNode *r) : ParseNode(l,r) {} }; // represents multiplying the two child expressions class TimesOp : public ParseNode { public: TimesOp(ParseNode *l, ParseNode *r) : ParseNode(l,r) {} }; // a representation of a list of coefficients must be developed class Coefficients : public ParseNode { public: }; // leaves of the parse tree // notice that the parent constructors take no arguments // that means this is a leaf class Iconst : public ParseNode { int iValue; public: Iconst(int iValue) : iValue(iValue), ParseNode() {} Type GetType() { return INTEGERVAL; } }; class Fconst : public ParseNode { float fValue; public: Fconst(float fValue) : fValue(fValue), ParseNode() {} Type GetType() { return FLOATVAL; } }; class Sconst : public ParseNode { string sValue; public: Sconst(string sValue) : sValue(sValue), ParseNode() {} Type GetType() { return STRINGVAL; } }; class Ident : public ParseNode { string id; public: Ident(string id) : id(id), ParseNode() {} Type GetType(); // not known until run time! }; extern ParseNode *Prog(istream& in); extern ParseNode *Stmt(istream& in); extern ParseNode *Expr(istream& in); extern ParseNode *Term(istream& in); extern ParseNode *Primary(istream& in); extern ParseNode *Poly(istream& in); extern ParseNode *Coeffs(istream& in); extern ParseNode *EvalAt(istream& in); #endif /* PARSENODE_H_ */ 

#include #include #include using namespace std; #include "ParseNode.h" int currentLine = 0; int globalErrorCount = 0; int main(int argc, char *argv[]) { ifstream file; bool use_stdin = true; for( int i=1; i 0 ) { cout << "Program failed!" << endl; return 1; } // need to look at the parse here return 0; } 

#ifndef POLYLEX_H_ #define POLYLEX_H_

#include #include

extern int currentLine; // in ONE PLACE in your program, you must have the following line: // int currentLine = 0; // each time you see a ' ', add one to currentLine

enum TokenTypes { ID, ICONST, FCONST, STRING, PRINT, SET, PLUS, MINUS, STAR, COMMA, LBR, RBR, LSQ, RSQ, LPAREN, RPAREN, SC, ERR, DONE };

class Token { private: TokenTypes t; std::string lexeme; int line;

public: Token(TokenTypes t=ERR, std::string lexeme="") { this->t = t; this->lexeme = lexeme; this->line = currentLine; }

TokenTypes getType() const { return t; } std::string getLexeme() const { return lexeme; } int getLine() const { return line; }

bool operator==(const TokenTypes& tt) { return t == tt; } bool operator!=(const TokenTypes& tt) { return t != tt; } };

extern Token getToken(std::istream& source);

#endif /* POLYLEX_H_ */

Question: Develop a parser that can solve polynomials (Example: x^2 +2x +4) and follows the rules listed above(can solve the examples listed above). The code provided are optional meaning that you do not have to use it.