Operator Precedence Parsing

While ad-hoc methods are sometimes used for parsing expressions, a more formal technique using operator precedence simplifies the task. For example an expression such as

(x*x + y*y)^.5

is easily parsed. Operator precedence parsing is based on bottom-up parsing techniques and uses a precedence table to determine the next action. The table is easy to construct and is typically hand-coded. This method is ideal for applications that require a parser for expressions and where embedding compiler technology, such as yacc, would be overkill. The presentation is intuitive with examples coded in ANSI-C, Visual Basic, and K. Thanks to David O'Neil for a C++ version, and Stevan Apter and for a version in K. In addition, Marcus Zibrowius has coded a clever Javascript parser that traces each step in the shift-reduce parser. The example in ANSI-C was coded by the author and contains the latest updates.

An excellent and more theoretical treatment may be found in Compilers, Principles, Techniques and Tools by Aho, Sethi, and Ullman. Right-click on the following links for additional downloads:

Permission to reproduce portions of this document is given provided the web site listed below is referenced. No additional restrictions apply. Source code, when part of a software project, may be used freely without reference to the author.

Tom Niemann
Portland, Oregon
epaperpress.com