Re: if then else shift/reduce Syndrome

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
--

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