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 | '-' primaryWith 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)
“There is, however, this consolation to the most way-worn traveler, upon the dustiest road, that the path his feet describe is so perfectly symbolical of human life,—now climbing the hills, now descending into the vales. From the summits he beholds the heavens and the horizon, from the vales he looks up to the heights again. He is treading his old lessons still, and though he may be very weary and travel-worn, it is yet sincere experience.”
—Henry David Thoreau (1817–1862)
“A method of child-rearing is not—or should not be—a whim, a fashion or a shibboleth. It should derive from an understanding of the developing child, of his physical and mental equipment at any given stage, and, therefore, his readiness at any given stage to adapt, to learn, to regulate his behavior according to parental expectations.”
—Selma H. Fraiberg (20th century)