Re: if then else shift/reduce Syndrome

Henry Spencer <henry@zoo.toronto.edu>
27 Feb 1996 16:29:20 -0500

          From comp.compilers

Related articles
[3 earlier articles]
Re: if then else shift/reduce Syndrome mab@wdl.loral.com (1996-02-14)
Re: if then else shift/reduce Syndrome theo@engr.mun.ca (1996-02-16)
Re: if then else shift/reduce Syndrome meissner@cygnus.com (Michael Meissner) (1996-02-16)
Re: if then else shift/reduce Syndrome solution@gate.net (1996-02-16)
Re: if then else shift/reduce Syndrome tarnwb@holly.colostate.edu (Tarn Burton) (1996-02-16)
Re: if then else shift/reduce Syndrome meissner@cygnus.com (Michael Meissner) (1996-02-21)
Re: if then else shift/reduce Syndrome henry@zoo.toronto.edu (Henry Spencer) (1996-02-27)
Re: if then else shift/reduce Syndrome neitzel@gaertner.de (1996-03-01)
Re: if then else shift/reduce Syndrome bakul@netcom.com (1996-03-03)
| List of all articles for this month |

From: Henry Spencer <henry@zoo.toronto.edu>
Newsgroups: comp.compilers
Date: 27 Feb 1996 16:29:20 -0500
Organization: SP Systems, Toronto
References: 96-02-139 96-02-192 96-02-243
Keywords: yacc, parse

Michael Meissner <meissner@cygnus.com> writes:
>...if you don't have features like %left, %right and/or
>%nonassoc, you need to specify separate rules for each level of
>precedence. Thus a simple statement:
> a = 1;
>Can generate 13 or more reductions in C...


Only if the grammar is naively written. Although it is significantly
more work, it *is* possible to write a grammar that is optimized for
the common cases, and doesn't do the massive recursive plunge for
simple statements. (My terminology here reflects my life-long
preference for recursive-descent parsers and their table-driven
equivalents, but I believe the same thing can be done for bottom-up
parsing.)


The way to do it is to short-circuit the common cases, and invoke the
full machinery only if (for example) that `1' is followed by an
operator. This does make things messy -- you've got to do some
backing and filling to cope with that unwelcome operator -- but if
you're patient and careful, it can be done. The resulting grammar is
not as clean and elegant as the one in the language spec, especially
for a language with many precedence levels, but it parses real
programs much more rapidly.


This trick has actually been around as folklore for some time. I
don't recall ever seeing it published, although admittedly I'm more
than slightly behind on my reading. I first ran into it in internal
documentation of the SP/k project at University of Toronto in 1977.
--
Henry Spencer, henry@zoo.toronto.edu
--


Post a followup to this message

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