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 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. 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, and 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