Re: if then else shift/reduce Syndrome

| Our parser generator did fairly good table optimization so that
| similar states could share some common transition information. Don't
| know the actual numbers though. But with all the compression the size
| of the tables wasn't a problem.


Of course nowadays, 32-bit systems are fairly common. When I did the
original hacking, I was using parser generators compiled for 16-bit
systems (Data General AOS and V7 PDP-11 unix). Those systems did have
more severe limits in terms of table size (ie, before you can compress
the tables, you have to hold them uncompressed in memory). When I was
first writing the Data General C compiler, I could not write a grammar
that included all precedence levels without blowing the parser
generator's memory limit, so I punted expression handling to PL/I and
did an infix -> reverse polish conversion.


It turns out, that depending on your parser generator, this can
actually be a win if parsing time dominates your compilation. This is
because 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. I believe the DEC book
'Engineering a Compiler' or some such, probably now long out of print,
mentions this when they were contrasting their C and PL/I compilers.
--
Michael Meissner, Cygnus Support (East Coast)
Suite 105, 48 Grove Street, Somerville, MA 02144, USA
meissner@cygnus.com, 617-629-3016 (office), 617-629-3010 (fax)
--

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