Re: Precedence based parsing

John McEnerney <jmcenerney@austin.rr.com>
8 Dec 2003 00:21:39 -0500

          From comp.compilers

Related articles
Precedence based parsing Jeffrey.Kenton@comcast.net (Jeff Kenton) (2003-12-03)
Re: Precedence based parsing torbenm@diku.dk (2003-12-08)
Re: Precedence based parsing jmcenerney@austin.rr.com (John McEnerney) (2003-12-08)
Re: Precedence based parsing haberg@matematik.su.se (2003-12-08)
Re: Precedence based parsing freitag@alancoxonachip.com (Andi Kleen) (2003-12-08)
Re: Precedence based parsing toby@telegraphics.com.au (2003-12-13)
Re: Precedence based parsing robert.thorpe@antenova.com (Rob Thorpe) (2003-12-13)
Re: Precedence based parsing clint@0lsen.net (Clint Olsen) (2003-12-20)
Re: Precedence based parsing sjmeyer@www.tdl.com (Steve Meyer) (2003-12-23)
[3 later articles]
| List of all articles for this month |

From: John McEnerney <jmcenerney@austin.rr.com>
Newsgroups: comp.compilers
Date: 8 Dec 2003 00:21:39 -0500
Organization: Road Runner - Texas
References: 03-12-035
Keywords: parse
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
> 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...


Post a followup to this message

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