Operator-precedence parser: Difference between revisions

Revision as of 14:15, 28 February 2008

Revision as of 05:20, 8 May 2008

Line 90:

== Alternatives to Dijkstra's Algorithm ==

There are alternative ways to apply operator precedence rules which do not involve the Shunting Yard algorithm.

There are alternative ways to apply operator precedence rules which do not involve the Shunting Yard algorithm. One is to build a tree of the original expression, then apply tree rewrite rules to it. Another is the algorithm used in the early FORTRAN I compiler, which is to first fully parenthesise the expression by a trivial macro replacement — inserting a number of parentheses around each operator, such that they lead to the correct precedence when parsed with a 'flat' grammar. (A hack which takes longer to explain properly than to write code for - see below!)

One is to build a tree of the original expression, then apply tree rewrite rules to it.

Such trees do not necessarily need to be implemented using data structures conventionally used for trees. Instead, tokens can be stored in flat structures, such as tables, by simultaneously building a priority list which states what elements to process in which order. As an example, such an approach is used in the ''Mathematical Formula Decomposer'' <ref>http://herbert.gandraxa.com/herbert/mfd.asp</ref>.

There are alternative ways to apply operator precedence rules which do not involve the Shunting Yard algorithm. One is to build a tree of the original expression, then apply tree rewrite rules to it. Another is the algorithm used in the early FORTRAN I compiler, which is to first fully parenthesise the expression by a trivial macro replacement — inserting a number of parentheses around each operator, such that they lead to the correct precedence when parsed with a 'flat' grammar. (A hack which takes longer to explain properly than to write code for - see below!)

<source lang="c">