## Operator precedence parsing is based on bottom-up shift-reduce parsing. As an expression is parsed tokens are shifted to a stack. At the appropriate time the stack is reduced by applying the operator to the top of the stack. This is best illustrated by example.

`opr`

, for operators, and `val`

, for values. A ' `$`

' designates the end of input or end of stack. Initially the stacks are empty, and the input contains an expression to parse. Each value, as it is encountered, is shifted to the`val`

stack. When the first operator is encountered (step 2), we shift it to the `opr`

stack. The second value is shifted to the`val`

stack in step 3. In step 4, we have a ' `*`

' in `opr`

, and a ' `+`

' input symbol. Since we want to multiply before we add (giving multiplication precedence), we'll reduce the contents of the `val`

, applying the ' `*`

' operator to the top of the `val`

. After reducing, the ' `+`

' operator will be shifted to `opr`

in step 5.This process continues until the input and

`opr`

are empty. If all went well, we should be left with the answer in the `val`

. The following table summarizes the action taken as a function of input and the top of `opr`

:When the input token is '

`+`

', and '`+`

' is on `opr`

, we reduce before shifting the new '`+`

' to `opr`

. This causes the left-most operator to execute first, and implies that addition is left-associative. If we were to shift instead, then addition would be right-associative. When the input token is '`*`

', and '`+`

' is in `opr`

, we shift '`*`

' to `opr`

. Later, when reducing, '`*`

' is popped before '`+`

', giving precedence to multiplication. By appropriately specifying shift and reduce actions, we can control the associativity and precedence of operators in an expression. When we encounter an operator in the input stream, and an operator is already on the stack, take the following action:- If the operators are different, shift to give higher precedence to the input operator.
- If the operators are the same, shift for right associativity.

Let's extend the previous example to include additional operators.

The above table incorporates the following operators:- "
`M`

", for unary minus. - "
`^`

", for exponentiation.`5 ^ 2`

yields`25`

. - "
`f`

", for factorial.`f(x)`

returns the factorial of`x`

. - "
`p`

", for permutations.`p(n,r)`

returns the number of permutations for`n`

objects taken`r`

at a time. - "
`c`

", for combinations.`c(n,r)`

returns the number of combinations for`n`

objects taken`r`

at a time.

- unary minus
- exponentiation, right-associative
- multiplication/division, left-associative
- addition/subtraction, left-associative

- error
`e1`

: missing right parenthesis - error
`e2`

: missing operator - error
`e3`

: unbalanced right parenthesis - error
`e4`

: invalid function argument

```
input action
'(' shift
')' while opr[tos] != '('
reduce
shift ')'
reduce '()'
```

On encountering a left parenthesis, we shift it to the `opr`

stack. When we input a right parenthesis, the stack is popped until the matching left parenthesis is found. Then we shift the right parenthesis, and reduce by popping both parentheses off the stack.For function calls, the function reference is shifted to the stack. Each comma-separated argument is also shifted to the stack. On encountering a comma, the operator stack is reduced until the opening parenthesis of the function call is visible, leaving the function parameter on the value stack. Then the comma is shifted to the stack, and popped on the next reduction. When the closing parenthesis of the function call is encountered, it will be shifted to the stack and reduced. This will expose the function call for subsequent reduction.

Operator classes may be used to minimize the size of the precedence table. For example, a single generic token representing a function call may be pushed on the operator stack. An ordinal, defining which function is referenced, is pushed on the value stack. For this purpose, you may wish to implement each element on the value stack as a union to allow for different datatypes.

Error-checking is not bullet-proof. For example, omitting commas between function arguments will be accepted, and work properly. Even more bizarre, reverse-polish notation, where operators follow operands, is also acceptable. This phenomenon occurs because operators are applied to the top elements of the value stack, and the order that operators and values are pushed is not significant. Major errors, such as omitting an operator, will be found by the final reduction, as the stacks will not be empty. More rigorous error-checking may be done by defining a boolean

*follow*matrix. The current and previous tokens are used as indices into the matrix to determine if one can follow the other.

The table is implemented in the next section, using

**ANSI-C**. Note that there are some differences between my solution and Aho's:

- Aho specifies three precedence relations, whereas I've only specified two (shift and reduce). You can use three if you wish; I'm the last one to stifle creativity!
- Aho uses one stack for both values and operators. I've used separate stacks, as the implementation is typically easier.

// ========================================================================================== // The following is a precedence based expression parser. It does not include variables, // but it is true OOP. It may be broken into individual files by removing the appropriate // comments and breaking where indicated. // // This code is NOT guaranteed to be free of defects, and no warranty of any kind is // given with this code. // // Original code developed by David O'Neil, 1/2/00. This code may be freely modified // and redistributed as you see fit. I do request that if you make any improvements // to this code you send me a copy. I may be reached at david@daodservices.com // Thanks, and enjoy! // // (Developed from Thomas Niemann's table based precedence parsing example available // at epaperpress.com. The table has been eliminated, and a precedence enumeration // technique has been implemented in it's place.) // ========================================================================================== //eliminate these #include and using statements if breaking this file apart #include#include using std::vector; using std::cin; using std::cout; /* ========================================================================================== // The original Stack.h file follows #ifndef Stack_h #define Stack_h #include using std::vector; */ // Class to manipulate a float vector class Stack { private: vector stack; public: void addToStack(float); void add(); void subtract(); void multiply(); void divide(); void power(); float getAnswer(); }; //#endif //Stack.h - uncomment if separating /* ========================================================================================== // The original Objects.h file follows #ifndef Objects_h #define Objects_h #include "Stack.h" */ //the order of this enumeration is critical for correct operation enum precedence_ {PrecGet, PrecEnd, PrecParen, PrecAddSub, PrecMulDiv, PrecPow, PrecVal, NoPrec }; // ========================================================================================== // Base class for various objects (ie - Numbers, Delimiters ('+', '-', '*'...)) // ========================================================================================== class Object { private: Stack *numStack; protected: Object(precedence_); public: //will make precedence private in future, but for simple test leave public precedence_ precedence; virtual void execute(); Object(); }; // ========================================================================================== // Classes derived from the base Object class // ========================================================================================== // Get class derived from base class. This object is placed on the bottom of the stack // so that the precedence checking algorithm will fetch the next object for the stack // when the stack is reduced to only having this on it class Get: public Object { public: Get(); }; // Number class derived from Base class class Number : public Object { private: void execute(); float number; Stack *numStack; public: Number(float, Stack*); float getNumber(); }; // Plus derived from Base (handles the '+' sign) class Plus : public Object { private: void execute(); Stack *numStack; public: Plus(Stack* stack); }; // Minus derived from Base (handles the '-' sign) class Minus : public Object { private: void execute(); Stack *numStack; public: Minus(Stack* stack); }; // Minus derived from Base (handles the '*' sign) class Multiply : public Object { private: void execute(); Stack *numStack; public: Multiply(Stack* stack); }; // Divide derived from Base (handles the '/' sign) class Divide : public Object { private: void execute(); Stack *numStack; public: Divide(Stack* stack); }; // Power derived from Base (handles the '^' sign) class Power : public Object { private: void execute(); Stack *numStack; public: Power(Stack* stack); }; // LParen derived from Base (handles '(' ) class LParen : public Object { private: void execute(); public: LParen(); bool isRightParen; }; // RParen derived from Base (handles ')' ) class RParen : public Object { private: void execute(); public: RParen(); bool isRightParen; }; // End derived from Base (handles the string EOL '\0') class End : public Object { public: End(); }; //#endif //Objects_h - uncomment if breaking this file up /* ========================================================================================== // The original Parser.h file follows #ifndef Parser_h #define Parser_h #include "Objects.h" #include using std::vector; */ const int MaxStr = 80; // Class to implement the parsing of the expression class Parser { private: Stack floatStack; char *str; bool getObject(); vector obStack; void showCommands(); void run(); bool isObject(char *); Object *tempOb; public: bool parse(char *str_); double answer; }; //#endif //Parser_h - reinclude if breaking file up /* ========================================================================================== // The original Parser.cpp file follows #pragma hdrstop #include #include "parser.h" #include using std::cout; using std::cin; //--------------------------------------------------------------------------- USEUNIT("parser.cpp"); //these three lines will need to be recreated USEUNIT("Stack.cpp"); //by adding these units to your project USEUNIT("Objects.cpp"); //if you break this file apart //--------------------------------------------------------------------------- #pragma argsused */ int main() { char expstr[MaxStr+1]; for (;;) { Parser parse; //scope it so ctor and dtor's get called each time cout << "Enter expression\n('Enter' to quit, ? for help): "; cin.getline(expstr, MaxStr); if (*expstr == NULL) break; if (parse.parse(expstr)) cout << "Answer is: " << parse.answer << "\n\n"; else cout << "\n\n"; } return 0; } /* ========================================================================================== // The original Parser.cpp file follows #include "Parser.h" #include using std::cout; using std::cin; */ // parse() - main entry point into parser class. Returns true if it parsed correctly. bool Parser::parse(char *str_) { Get junk; tempOb = &junk; str = str_; if (*str == '?') { showCommands(); return false; } //first, place a Get object on the stack... Get *get = new Get; obStack.push_back(get); while (tempOb->precedence != PrecEnd) { if (!getObject()) { return false; } } //now, place an End object onto the list End *end = new End; obStack.push_back(end); //now, run the list of objects: run(); //now, get the last value on the stack: answer = floatStack.getAnswer(); //now, free the space back up while (!obStack.empty()) { delete obStack.back(); obStack.pop_back(); } return true; } // getObject() - Gets the current object being pointed to by str. bool Parser::getObject() { //skip over whitespace while (isspace(*str)) ++str; //determine if at the end of the string if (!*str) { End *end = new End; tempOb = end; //if (tempOb->precedence != PrecEnd) { cout << "Oh no\n"; } obStack.push_back(end); return true; } switch (*str) { case '+': { Plus *plus = new Plus(&floatStack); tempOb = plus; obStack.push_back(plus); *str++; break; } case '-': { Minus *minus = new Minus(&floatStack); tempOb = minus; obStack.push_back(minus); *str++; break; } case '*': { Multiply *mul = new Multiply(&floatStack); tempOb = mul; obStack.push_back(mul); *str++; break; } case '/': { Divide *div = new Divide(&floatStack); tempOb = div; obStack.push_back(div); *str++; break; } case '^': { Power *pow = new Power(&floatStack); tempOb = pow; obStack.push_back(pow); *str++; break; } case '(': { LParen *lparen = new LParen(); tempOb = lparen; obStack.push_back(lparen); *str++; break; } case ')': { RParen *rparen = new RParen(); tempOb = rparen; obStack.push_back(rparen); *str++; break; } default: //convert the following characters into a floating point number // floats can have 7 digits of precision, but we will allow the // user to input as much as they want. //First, check to make sure that it is indeed a number if (!isdigit(*str)) { cout << "\nunknown command\n"; return false; } char tempval[MaxStr]; int i = 0; do { tempval[i++] = *str++; } while (isdigit(*str) || *str == '.'); tempval[i] = '\0'; Number *num = new Number(atof(tempval), &floatStack); tempOb = num; //now, add the object ptr to the list: obStack.push_back(num); } return true; } // isObject() - tells if the character at str is an object bool Parser::isObject(char *tstr) { switch (*tstr) { case '+': case '-': case '*': case '/': case '^': case '(': case ')': return true; default: return false; } } // showCommands() - shows the commands available in the parser. void Parser::showCommands() { cout << "\n"; cout << "Available Commands:\n"; cout << " + - plus\n"; cout << " - - minus\n"; cout << " * - multiply\n"; cout << " / - divide\n"; cout << " ^ - power\n"; cout << "\nsimply enter expression like: 5*(4^5+2)\n"; } // run() - finally executes the list of objects void Parser::run() { int i = -1, tStackSize = 0; vector tStack; precedence_ precLast, precPrior; //first, place the first 'Get' onto the stack tStack.push_back(obStack[++i]); //now, start running the stack do { //push another object onto the stack tStack.push_back(obStack[++i]); ++tStackSize; precPrior = tStack[tStackSize-1]->precedence; //simply in for debugger inspecting precLast = tStack[tStackSize]->precedence; //to help prog'r understand workings while (precPrior >= precLast) { //check for stack reduction ( '(' and ')' objects) if (precLast == PrecParen) { if (RParen *rpar = dynamic_cast (tStack[tStackSize])) { //the last obj is a right parenthisis //if the previous obj is not parenthesis it needs to be processed if (tStack[tStackSize-1]->precedence > PrecParen) goto breakout; //that leaves the previous obj as being a parenthesis if (LParen *lpar = dynamic_cast (tStack[tStackSize-1])) { //need to pop both parenthesis off the stack tStack.pop_back(); tStack.pop_back(); tStackSize -= 2; if (tStackSize < 1) break; precPrior = tStack[tStackSize-1]->precedence; //these two lines can precLast = tStack[tStackSize]->precedence; //be elim when precLast continue; //&precPrior eliminated } //the previous object was a right parenthesis - error cout << "\n'(' not reduced - meaningless answer\n\n"; return; } //the last object must be a left parenthesis. see if prior is parenthesis if (tStack[tStackSize-1]->precedence > PrecParen) break; //now, need to check for prior object being left parenthesis if (LParen *lpar = dynamic_cast (tStack[tStackSize-1])) { //get the next tStack.push_back(obStack[++i]); //stack item ++tStackSize; precPrior = tStack[tStackSize-1]->precedence; precLast = tStack[tStackSize]->precedence; continue; } //big problem if it reaches here. Last item = '(' and prior = ')' cout << "\nbad reduction. reduced to ')('\n\n"; return; } breakout: tStack[tStackSize-1]->execute(); tStack[tStackSize-1] = tStack[tStackSize]; tStack.pop_back(); tStackSize--; precPrior = tStack[tStackSize-1]->precedence; precLast = tStack[tStackSize]->precedence; } } while (tStack[tStackSize]->precedence != PrecEnd); } /* ========================================================================================== // The original Objects.cpp file follows #include "Objects.h" #include using std::cout; */ // ========================================================================================== // Class implementations of Base objects (Numbers, Add, Subtract, Multiply, Divide) // ========================================================================================== // Object::(functions) *********************************** Object::Object() : precedence(NoPrec), numStack(NULL) { } Object::Object(precedence_ prec) : precedence(prec) { } //virtual function - give programmer clue... void Object::execute() { cout << "\nUndefined Operator\nMeaningless answer\n\n"; } // ========================================================================================== // End of virtual base class definition, now on to the derived objects... // ========================================================================================== // Number::(functions) *********************************** Number::Number(float num, Stack *stackToUse) : number(num), numStack(stackToUse), Object(PrecVal) { } //virtual override void Number::execute() { numStack->addToStack(number); } //public access... float Number::getNumber() { return number; } // Get::() *********************************** Get::Get() : Object(PrecGet) { } // Plus::() *********************************** Plus::Plus(Stack* stack) : numStack(stack), Object(PrecAddSub) { } void Plus::execute() { numStack->add(); } // Minus::() *********************************** Minus::Minus(Stack* stack) : numStack(stack), Object(PrecAddSub) { } void Minus::execute() { numStack->subtract(); } // Multiply::() *********************************** Multiply::Multiply(Stack* stack) : numStack(stack), Object(PrecMulDiv) { } void Multiply::execute() { numStack->multiply(); } // Divide::() *********************************** Divide::Divide(Stack* stack) : numStack(stack), Object(PrecMulDiv) { } void Divide::execute() { numStack->divide(); } // Power::() *********************************** Power::Power(Stack* stack) : numStack(stack), Object(PrecPow) { } void Power::execute() { numStack->power(); } // LParen::() *********************************** LParen::LParen() : isRightParen(false), Object(PrecParen) { } void LParen::execute() { cout << "\nshift reduction incorrect\nmeaningless answer\n\n"; } // RParen::() *********************************** RParen::RParen() : isRightParen(true), Object(PrecParen) { } void RParen::execute() { cout << "\nshift reduction incorrect\nmeaningless answer\n\n"; } // End::() *********************************** End::End() : Object(PrecEnd) { } /* ========================================================================================== // The original Stack.cpp file follows #include "Stack.h" #include using std::cout; */ // add() - commands the stack to add the top two numbers void Stack::add() { int i = stack.size()-1; if (i < 1) { cout << "\nnot enough variables to add\nmeaningless answer\n\n"; return; } stack[i-1] += stack[i]; stack.pop_back(); } // subtract() - commands the stack to subtract the top two numbers void Stack::subtract() { int i = stack.size()-1; if (i < 1) { cout << "\nnot enough variables to subtract\nmeaningless answer\n\n"; return; } stack[i-1] -= stack[i]; stack.pop_back(); } // multiply() - commands the stack to multiply the top two numbers void Stack::multiply() { int i = stack.size()-1; if (i < 1) { cout << "\nnot enough variables to multiply\nmeaningless answer\n\n"; return; } stack[i-1] *= stack[i]; stack.pop_back(); } // multiply() - commands the stack to multiply the top two numbers void Stack::divide() { int i = stack.size()-1; if (i < 1) { cout << "\nnot enough variables to divide\nmeaningless answer\n\n"; return; } stack[i-1] /= stack[i]; stack.pop_back(); } // power() - commands the stack to multiply the top two numbers void Stack::power() { int i = stack.size()-1; if (i < 1) { cout << "\nnot enough variables to divide\nmeaningless answer\n\n"; return; } stack[i-1] = pow(stack[i-1], stack[i]); stack.pop_back(); } // addToStack() - public function to add a number to the stack void Stack::addToStack(float num) { stack.push_back(num); } // getAnswer() - public function to return the answer on the stack, and pop the stack down float Stack::getAnswer() { int i = stack.size(); if (i != 1) { cout << "\nstack contains too many values\n\n"; return 0.0; } float ans = stack[0]; stack.pop_back(); return ans; }