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
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:
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
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.