Re: Precedence based parsing

haberg@matematik.su.se (Hans Aberg)
8 Dec 2003 00:22:17 -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)
Re: Precedence based parsing joachim.durchholz@web.de (Joachim Durchholz) (2003-12-27)
[2 later articles]
| List of all articles for this month |

From: haberg@matematik.su.se (Hans Aberg)
Newsgroups: comp.compilers
Date: 8 Dec 2003 00:22:17 -0500
Organization: Mathematics
References: 03-12-035
Keywords: parse
Posted-Date: 08 Dec 2003 00:22:17 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.


>Comments?


The book by Aho, Sethi, Ullman, "Compilers..." ("dragon book") mention it,
and it is also in the online Parsing Techniques book:
        http://www.cs.vu.nl/~dick/PTAPG.html


> Reasons to prefer other techniques?


>[Operator precedence parsing is a classic technique, but you're right, the
>recent books I looked at don't discuss it. I guess it's not as cool as
>LR(1) or Tomita. -John]


The technique of operator precedences alone is somewhat too limited.


I have made a generalization of context free grammars (CFG) which I
call constrained grammars: Together with the CFG, one can for each
argument of each rule prohibit a set of rule expansions. If one has a
suitable precedence system, that can be translated into this
constrained grammar model. Each constrained grammar can be rewritten
into a CFG. One can then directly do LR(k) parsing with respect to
this constrained grammar. The advantage of expressing operator
precedence via a constrained grammar over a token based precedence is
that it does not depend on the parsing algorithm used.


I will send you a preprint.


    Hans Aberg


Post a followup to this message

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