Operator-precedence parser

In computer science, an operator-precedence parser is a bottom-up parser that interprets an operator-precedence grammar. For example, most calculators use operator-precedence parsers to convert from the human-readable infix notation relying on order of operations to a format that is optimized for evaluation such as Reverse Polish notation (RPN). Edsger Dijkstra's shunting yard algorithm is commonly used to implement operator-precedence parsers.

In computer science, an operator-precedence parser is a bottom-up parser that interprets an operator-precedence grammar. For example, most calculators use operator-precedence parsers to convert from the human-readable infix notation relying on order of operations to a format that is optimized for evaluation such as Reverse Polish notation (RPN). Edsger Dijkstra's shunting yard algorithm is commonly used to implement operator-precedence parsers. expression ::= equality-expression equality-expression ::= additive-expression ( ( '==' | '!=' ) additive-expression ) * additive-expression ::= multiplicative-expression ( ( '+' | '-' ) multiplicative-expression ) * multiplicative-expression ::= primary ( ( '*' | '/' ) primary ) * primary ::= '(' expression ')' | NUMBER | VARIABLE | '-' primary With many levels of precedence, implementing this grammar with a predictive recursive-descent parser can become inefficient. Parsing a number, for example, can require five function calls: one for each non-terminal in the grammar until reaching primary. An operator-precedence parser can do the same more efficiently. The idea is that we can left associate the arithmetic operations as long as we find operators with the same precedence, but we have to save a temporary result to evaluate higher precedence operators. The algorithm that is presented here does not need an explicit stack; instead, it uses recursive calls to implement the stack. The algorithm is not a pure operator-precedence parser like Edsger Dijkstra's shunting yard algorithm. It assumes that the primary nonterminal is parsed in a separate subroutine, like in a recursive descent parser. lookahead := peek next token while lookahead is a binary operator whose precedence is >= min_precedence op := lookahead advance to next token rhs := parse_primary () lookahead := peek next token while lookahead is a binary operator whose precedence is greater than op ' s, or a right-associative operator whose precedence is equal to ops rhs := parse_expression_1 (rhs, precedence of op + (1 if lookahead precedence is greater, else 0)) lookahead := peek next token lhs := the result of applying op with operands lhs and rhs return lhs Note that in the case of a production rule like this (where the operator can only appear once): equality-expression ::= additive-expression ( '==' | '!=' ) additive-expression the algorithm must be modified to accept only binary operators whose precedence is > min_precedence. An example execution on the expression 2 + 3 * 4 + 5 == 19 is as follows. We give precedence 0 to equality expressions, 1 to additive expressions, 2 to multiplicative expressions. parse_expression_1 (lhs = 2, min_precedence = 0) the lookahead token is +, with precedence 1. the outer while loop is entered. op is + (precedence 1) and the input is advanced rhs is 3 the lookahead token is *, with precedence 2. the inner while loop is entered. parse_expression_1 (lhs = 3, min_precedence = 2) the lookahead token is *, with precedence 2. the outer while loop is entered. op is * (precedence 2) and the input is advanced rhs is 4 the next token is +, with precedence 1. the inner while loop is not entered. lhs is assigned 3*4 = 12 the next token is +, with precedence 1. the outer while loop is left. 12 is returned. the lookahead token is +, with precedence 1. the inner while loop is not entered. lhs is assigned 2+12 = 14 the lookahead token is +, with precedence 1. the outer while loop is not left. op is + (precedence 1) and the input is advanced rhs is 5 the next token is ==, with precedence 0. the inner while loop is not entered. lhs is assigned 14+5 = 19 the next token is

, with precedence 0. the outer while loop is not left. op is

(precedence 0) and the input is advanced rhs is 19 the next token is end-of-line, which is not an operator. the inner while loop is not entered. lhs is assigned the result of evaluating 19 == 19, for example 1 (as in the C standard). the next token is end-of-line, which is not an operator. the outer while loop is left. 1 is returned. include include // The command-line argument boundary is our lexer. int main(int argc, char *argv[]) { int i; printf("(((("); for (i=1; i!=argc; i++) { // strlen(argv[i]) == 2 if (argv[i] && !argv[i][1]) { switch (*argv[i]) { case '(': printf("(((("); continue; case ')': printf("))))"); continue; case '^': printf(")^("); continue; case '*': printf("))*(("); continue; case '/': printf("))/(("); continue; case '+': // unary check: either first or had an operator expecting secondary argument if (i

1 || strchr("(^*/+-", *argv[i-1])) printf("+"); else printf(")))+((("); continue; case '-': if (i

1 || strchr("(^*/+-", *argv[i-1])) printf("-"); else printf(")))-((("); continue; } } printf("%s", argv[i]); } printf("))))\n"); return 0; } For example, running with input a * b + c ^ d / e produces ((((a))*((b)))+(((c)^(d))/((e)))) as output. A limitation to this strategy is that unary operators must all have higher precedence than infix operators. The "negative" operator in the above code has a higher precedence than exponentiation. Running the program with this input - a ^ 2 produces this output ((((-a)^(2)))) which is probably not what is intended.

References

External links

Example C++ code by Keith Clarke for parsing infix expressions using the precedence climbing method Parser for expression with infix notation using precedence lists

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378374188 under CC BY-SA 4.0; modifications have been made.