|Precedence based parsing Jeffrey.Kenton@comcast.net (Jeff Kenton) (2003-12-03)|
|Re: Precedence based parsing email@example.com (2003-12-08)|
|Re: Precedence based parsing firstname.lastname@example.org (John McEnerney) (2003-12-08)|
|Re: Precedence based parsing email@example.com (2003-12-08)|
|Re: Precedence based parsing firstname.lastname@example.org (Andi Kleen) (2003-12-08)|
|Re: Precedence based parsing email@example.com (2003-12-13)|
|Re: Precedence based parsing firstname.lastname@example.org (Rob Thorpe) (2003-12-13)|
|Re: Precedence based parsing email@example.com (Clint Olsen) (2003-12-20)|
|Re: Precedence based parsing firstname.lastname@example.org (Steve Meyer) (2003-12-23)|
|Re: Precedence based parsing email@example.com (Joachim Durchholz) (2003-12-27)|
|[2 later articles]|
|From:||firstname.lastname@example.org (Hans Aberg)|
|Date:||8 Dec 2003 00:22:17 -0500|
|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.
The book by Aho, Sethi, Ullman, "Compilers..." ("dragon book") mention it,
and it is also in the online Parsing Techniques book:
> 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.
Return to the
Search the comp.compilers archives again.