Editing Operator-precedence parser (section)

== Precedence climbing method ==
The precedence climbing method is a compact, efficient, and flexible algorithm for parsing expressions that was first described by Martin Richards and Colin Whitby-Strevens.<ref name="Richards1979">{{cite book |last1=Richards |first1=Martin |last2=Whitby-Strevens |first2=Colin |title=BCPL — the language and its compiler |year=1979 |publisher=Cambridge University Press |isbn=9780521219655}}</ref>

An infix-notation expression grammar in [[EBNF]] format will usually look like this:

<syntaxhighlight lang="abnf">
expression ::= equality-expression
equality-expression ::= additive-expression ( ( '==' | '!=' ) additive-expression ) *
additive-expression ::= multiplicative-expression ( ( '+' | '-' ) multiplicative-expression ) *
multiplicative-expression ::= primary ( ( '*' | '/' ) primary ) *
primary ::= '(' expression ')' | NUMBER | VARIABLE | '-' primary
</syntaxhighlight>

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.<ref name="Harwell2008"/>  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 the Dijkstra shunting yard algorithm.  It assumes that the ''primary'' nonterminal is parsed in a separate subroutine, like in a recursive descent parser.

=== Pseudocode ===

The pseudocode for the algorithm is as follows.  The parser starts at function ''parse_expression''.  Precedence levels are greater than or equal to 0.

 <u>parse_expression()</u>
     '''return''' parse_expression_1(parse_primary(), 0)

 <u>parse_expression_1(lhs, min_precedence)</u>
     ''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''<nowiki>'</nowiki>s, or a right-associative operator
                  whose precedence is equal to ''op'''s
             ''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):

<syntaxhighlight lang="abnf">
equality-expression ::= additive-expression  ( '==' | '!=' ) additive-expression
</syntaxhighlight>

the algorithm must be modified to accept only binary operators whose precedence is > ''min_precedence''.

=== Example execution of the algorithm ===

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.<br>''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.