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.


>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

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