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, C++, Visual Basic, and K. Thanks to David O'Neil for a C++ version, and Stevan Apter 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 examples in ANSI-C and Visual Basic were coded by the author and contain 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:

My first year of teaching:

In 1976 I was teaching computer science at Diablo Valley College — a 2-year community college in Pleasant Hill, California. Students had access to an HP time-sharing computer connected to 20 terminals that were situated in a terminal room that was adjacent to my office. During off hours it was a gathering place for students to experiment with their own projects and a fair amount of comraderie ensued. Evesdropping, I picked up on the fact that they were all trying to write a program to parse expressions. In quick order I wrote my own program, based on the concepts presented here, and announced a challenge. In one week they were to choose their fastest parser and we would have a contest to see if it bested my efforts.
On the day of the contest I was seated next to my challenger. Surrounded by the rest of the gang we entered the same rather lengthy expression on our terminals. At the count-down we both pressed the Enter key at the same time. Well, he pressed his but I delayed for a half second before pressing mine thus giving my opponent an advantage. A roar went up from the crowd when my program finished first by a clear margin. After listing the program on the printer they were struck by how short and simple it was. Better than dozens of if statements!

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.

View PDF files with PDF Reader.

Tom Niemann
Portland, Oregon
epaperpress.com