Operator-precedence Parser - Precedence Climbing Method

Precedence Climbing Method

The precedence climbing method is the name for an algorithm that was first described by Keith Clarke in a post to comp.compilers on May 26, 1992.

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

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

Read more about this topic:  Operator-precedence Parser

Famous quotes containing the words precedence, climbing and/or method:

    “Let not England forget her precedence of teaching nations how to live.”
    —John Milton (1608–1674)

    “An old, mad man still climbing in his ghost,
    My fathers’ ghost is climbing in the rain.”
    —Dylan Thomas (1914–1953)

    “I am not afraid of the priests in the long-run. Scientific method is the white ant which will slowly but surely destroy their fortifications. And the importance of scientific method in modern practical life—always growing and increasing—is the guarantee for the gradual emancipation of the ignorant upper and lower classes, the former of whom especially are the strength of the priests.”
    —Thomas Henry Huxley (1825–95)