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:

    “It is difficult to separate the tapestry
    From the room or loom which takes precedence over it.”
    —John Ashbery (b. 1927)

    “One who pressed forward incessantly and never rested from his labors, who grew fast and made infinite demands on life, would always find himself in a new country or wilderness, and surrounded by the raw material of life. He would be climbing over the prostrate stems of primitive forest-trees.”
    —Henry David Thoreau (1817–1862)

    “It is to be lamented that the principle of national has had very little nourishment in our country, and, instead, has given place to sectional or state partialities. What more promising method for remedying this defect than by uniting American women of every state and every section in a common effort for our whole country.”
    —Catherine E. Beecher (1800–1878)