Re: Precedence based parsing (Hans Aberg)
8 Dec 2003 00:22:17 -0500

          From comp.compilers

Related articles
Precedence based parsing (Jeff Kenton) (2003-12-03)
Re: Precedence based parsing (2003-12-08)
Re: Precedence based parsing (John McEnerney) (2003-12-08)
Re: Precedence based parsing (2003-12-08)
Re: Precedence based parsing (Andi Kleen) (2003-12-08)
Re: Precedence based parsing (2003-12-13)
Re: Precedence based parsing (Rob Thorpe) (2003-12-13)
Re: Precedence based parsing (Clint Olsen) (2003-12-20)
Re: Precedence based parsing (Steve Meyer) (2003-12-23)
Re: Precedence based parsing (Joachim Durchholz) (2003-12-27)
[2 later articles]
| List of all articles for this month |

From: (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 <> 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.

    Hans Aberg

Post a followup to this message

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