In this assignment were going to extend the arithmetic expression tree presented in class to handle function calls, with a single parameter.

The grammar presented in class was simply

exp -> NUM exp -> VAR exp -> '(' exp ')' exp -> '-' exp exp -> exp OP exp 

To extend this to functions, we add an additional rule:

exp -> FNAME '(' exp ')' 

The rules for function names are similar to those for variables, except that underscore _ characters are allowed in function names but not in variable names.

You should implement the functions

vector tokenize(string s); exp* parse(vector::iterator start, vector::iterator finish, int& prec); 

Note that unlike in class, the finish parameter here represents the position one-past-the-end of the vector. That is, finish-1 is the last token in the input. Use the prec parameter to ensure that infix operators are parsed with the correct precedence.

Use an expression tree type with the following classes:

struct exp { // You will have to implement the print method on all the subclasses.  virtual void print() = 0; }; // Precedence 100 struct exp_num : public exp { int value; exp_num(int v) : value(v) { } void print(); }; // Precedence 100 struct exp_var : public exp { std::string name; exp_var(std::string n) : name(n) { } void print(); }; // Precdence 100 struct exp_paren : public exp { exp* inner; exp_paren(exp* i) : inner(i) { } void print(); }; // Precedence 100 struct exp_minus : public exp { exp* inner; exp_minus(exp* i) : inner(i) { } void print(); }; // Precedence 100 struct exp_func : public exp { std::string name; exp* arg; exp_func(std::string n, exp* a) : name(n), arg(a) { } void print(); }; // Precedence: // + 50 // - 50 // * 75 // / 75 struct exp_op : public exp { char op; exp* left; exp* right; exp_op(char o, exp* l, exp* r) : op(o), left(l), right(r) { } void print(); }; 

You will have to implement the print method on all subclasses.

(You can download assign6.hpp which includes these class definitions and the declarations for the above functions.)

The test runner assign6_test.cpp will test your tokenizer on a number of different inputs to ensure that it correctly tokenizes strings, and then it will test your parser on various token sequences. If a token sequence is valid according to the grammar, it should return the corresponding expression tree; if it is not valid is should return nullptr. Neither tokenize nor parse should ever crash for any inputs; that is, no input string should be able to cause your program to segfault or throw an exception.

As an aide to testing your code, the test runner has an interactive mode. If you run

./assign6_test 

it will run in non-interactive mode, running through the preprogrammed tests. If you run

./assign6_test interactive 

it will go into a read-parse loop, reading strings from the input, parsing them into expression trees, and then print-ing the resulting trees. (The print method is also used in the test code to print trees, so you should make it do something useful.)

----------------------------------------------------- CODE FOR TEST RUNNER -----------------------------------------------------------------------------------------------

/* * assign6_test.cpp * Assignment 6 test runner */ #include #include #include #include "assign6.hpp" using std::string; using std::vector; using std::cout; using std::endl; template void print(const std::vector& vs) { for(auto v : vs) cout << v << ","; } bool test_tokenize() { cout << "Testing tokenization... "; // Tokenize empty string (into no tokens) auto t1 = tokenize(""); if(!t1.empty()) { cout << "FAILED: tokenize(\"\") should result in 0 tokens. "; return false; } // Tokenize each token type by itself, with some spaces thrown in. vector single_tokens = { "a_c", "a_c ", " a_c", " a_c ", "123", " 123", "123 ", " 123 ", " + ", " * ", " / ", " - ", " ( ", " ) " }; for(auto t : single_tokens) { auto t2 = tokenize(t); if(t2.size() != 1) { cout << "FAILED: \"" << t << "\" should tokenize into one token. "; print(t2); cout << endl; return false; } } // Test all possible pairs of tokens vector tokens = {"a_b", "123", "+", "*", "-", "/", "-", "(", ")"}; for(auto tok1 : tokens) { for(auto tok2 : tokens) { // Don't test any token type with itself if(tok1 == tok2) continue; auto ts = tokenize(tok1 + tok2); if(ts.size() != 2) { cout << "FAILED: \"" << tok1 << tok2 << "\" should tokenize into two tokens. "; print(ts); cout << endl; return false; } if(ts.front() != tok1) { cout << "FAILED: First token of \"" << tok1 << tok2 << "\" should be " << "\"" << tok1 << "\" "; print(ts); cout << endl; return false; } if(ts.back() != tok2) { cout << "FAILED: Second token of \"" << tok1 << tok2 << "\" should be " << "\"" << tok2 << "\" "; print(ts); cout << endl; return false; } } } return true; } enum class tree_type { NUM, VAR, PAREN, MINUS, FUNC, OPERATOR, ERROR }; tree_type get_type(exp* a) { if(dynamic_cast(a)) return tree_type::NUM; else if(dynamic_cast(a)) return tree_type::VAR; else if(dynamic_cast(a)) return tree_type::PAREN; else if(dynamic_cast(a)) return tree_type::MINUS; else if(dynamic_cast(a)) return tree_type::FUNC; else if(dynamic_cast(a)) return tree_type::OPERATOR; else return tree_type::ERROR; } /* compare_trees(a,b) Compares expression trees for equality. */ bool compare_trees(exp* a, exp* b) { if(get_type(a) != get_type(b)) return false; else { exp_func* af; exp_func* bf; exp_op* ao; exp_op* bo; switch(get_type(a)) { case tree_type::NUM: return dynamic_cast(a)->value == dynamic_cast(b)->value; case tree_type::VAR: return dynamic_cast(a)->name == dynamic_cast(b)->name; case tree_type::PAREN: return compare_trees(dynamic_cast(a)->inner, dynamic_cast(b)->inner); case tree_type::MINUS: return compare_trees(dynamic_cast(a)->inner, dynamic_cast(b)->inner); case tree_type::FUNC: af = dynamic_cast(a); bf = dynamic_cast(b); return af->name == bf->name && compare_trees(af->arg, bf->arg); case (tree_type::OPERATOR): ao = dynamic_cast(a); bo = dynamic_cast(b); return ao->op == bo->op && compare_trees(ao->left,bo->left) && compare_trees(ao->right,bo->right); default: return false; } } } exp* parse(std::string s) { std::vector tokens = tokenize(s); int prec = 0; return parse(tokens.begin(), tokens.end(), prec); } bool test_parse() { cout << "Testing parsing (invalid expressions...) "; vector bad_exps = { "", "a 1", "1 1", "a b", "a + + 2", "a_b + 3", // Variable names cannot include _ "()", "a + ", "- + a", "sin(1 +)", "sin()" }; for(string s : bad_exps) if(parse(s) != nullptr) { cout << "FAILED: '" << s << "' should not parse to a tree. "; return false; } cout << " (valid expressions...) "; // Test some simple expression to make sure the tree root is of the // correct sub-class. vector root_exp = { "1", // num "a", // var "(1)", // paren "-a", // minus "f(a)", // function }; vector root_types = { tree_type::NUM, tree_type::VAR, tree_type::PAREN, tree_type::MINUS, tree_type::FUNC }; vector root_trees = { new exp_num(1), new exp_var("a"), new exp_paren(new exp_num(1)), new exp_minus(new exp_var("a")), new exp_func("f", new exp_var("a")) }; for(unsigned i = 0; i < root_exp.size(); ++i) { exp* e = parse(root_exp.at(i)); if(e == nullptr) { cout << "FAILED: '" << root_exp.at(i) << "' did not parse to an expression tree. "; return false; } if(root_types.at(i) != get_type(e)) { cout << "FAILED: '" << root_exp.at(i) << "'s parse tree has the wrong root node type. "; return false; } if(!compare_trees(e, root_trees.at(i))) { cout << "FAILED: got the wrong tree for '" << root_exp.at(i) << "'. "; cout << " expected: "; root_trees.at(i)->print(); cout << " got "; e->print(); cout << endl; return false; } } // Test some compound expressions vector cmp_str = { "1 + 2", "-a", "-1 - 2", "(a * b)", "sin(2 * x)", "1 + 2 * 3", "1 / 2 - 3" }; vector cmp_exps = { new exp_op('+', new exp_num(1), new exp_num(2)), new exp_minus(new exp_var("a")), new exp_op('-', new exp_minus(new exp_num(1)), new exp_num(2)), new exp_paren(new exp_op('*', new exp_var("a"), new exp_var("b"))), new exp_func("sin", new exp_op('*', new exp_num(2), new exp_var("x"))), new exp_op('+', new exp_num(1), new exp_op('*', new exp_num(2), new exp_num(3))), new exp_op('-', new exp_op('/', new exp_num(1), new exp_num(2)), new exp_num(3)) }; for(unsigned i = 0; i < cmp_str.size(); ++i) { exp* e = parse(cmp_str.at(i)); if(!e) { cout << "FAILED: " << cmp_str.at(i) << " should parse. "; return false; } if(!compare_trees(e, cmp_exps.at(i))) { cout << "FAILED: " << cmp_str.at(i) << " did not parse correctly. "; cout << " expected "; cmp_exps.at(i)->print(); cout << endl; cout << " found: "; e->print(); cout << endl; return false; } } return true; } int main(int argc, char**) { if(argc > 1) { while(true) { // Interactive mode string input; cout << "> "; std::getline(std::cin, input); exp* e = parse(input); if(e) { cout << "= "; e->print(); cout << endl; } else cout << " (could not parse) "; } } else { // Run tests as usual std::cout << "--- Starting tests --- "; if(test_tokenize() && test_parse()) { cout << "--- All tests completed successfully! --- "; return 0; } else return 1; } } 

------------------------------------------------END OF TEST RUNNER CODE-----------------------------------------------------------------------------------------