Re: Precedence based parsing

"Jeff Kenton" <Jeffrey.Kenton@comcast.net> wrote:


> I have been writing parsers and compilers for over 30 years, and one
> technique I have used for parsing expressions seems to have
> disappeared from recent books. It involves comparing the precedence
> of the newest operator with that of the previous operator, in order
> to decide whether to shift or reduce. To me, it seems very
> intuitive, and easy to construct a parser by hand this way (even
> with 17 levels of operator precedence), but none of the new books
> mention it, and some very experienced colleagues have never heard of
> it.


As I recall, this technique is often taught in introductory Data
Structures courses, so perhaps it will not be totally lost.


The technique is still very much in use commercially. The most recent
Sun javac compiler parses expressions very coarsely in its recursive
descent parser, and uses operator precedence to parse the binary
operators correctly. This combination of techniques seems quite
common, as it we also used it in the early versions of Symantec's
THINK C compiler, and I seem to recall it was used in the original C
compiler at Bell Labs.


We discarded the precedence parser when we switched to an LR parser,
since obviously the use of precedence to resolve conflicts during
parser construction itself leads to a faster parser of the same size.


(I hope they're still teaching -that- to the kids...)


In college I wrote a parser generator that automatically constructed
an operator precedence parser for a language, using the techniques in
the Gries compiler text. Now that stuff is -way- out of date...

Return to the comp.compilers page.
Search the comp.compilers archives again.