|Precedence based parsing Jeffrey.Kenton@comcast.net (Jeff Kenton) (2003-12-03)|
|Re: Precedence based parsing firstname.lastname@example.org (2003-12-08)|
|Re: Precedence based parsing email@example.com (John McEnerney) (2003-12-08)|
|Re: Precedence based parsing firstname.lastname@example.org (2003-12-08)|
|Re: Precedence based parsing email@example.com (Andi Kleen) (2003-12-08)|
|Re: Precedence based parsing firstname.lastname@example.org (2003-12-13)|
|Re: Precedence based parsing email@example.com (Rob Thorpe) (2003-12-13)|
|Re: Precedence based parsing firstname.lastname@example.org (Clint Olsen) (2003-12-20)|
|Re: Precedence based parsing email@example.com (Steve Meyer) (2003-12-23)|
|[3 later articles]|
|From:||John McEnerney <firstname.lastname@example.org>|
|Date:||8 Dec 2003 00:21:39 -0500|
|Organization:||Road Runner - Texas|
|Posted-Date:||08 Dec 2003 00:21:39 EST|
"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
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
Search the comp.compilers archives again.