Re: if then else shift/reduce Syndrome

Michael Meissner <meissner@cygnus.com>
21 Feb 1996 00:07:54 -0500

          From comp.compilers

Related articles
[2 earlier articles]
Re: if then else shift/reduce Syndrome tim@franck.Princeton.EDU (1996-02-13)
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: Michael Meissner <meissner@cygnus.com>
Newsgroups: comp.compilers
Date: 21 Feb 1996 00:07:54 -0500
Organization: Compilers Central
References: 96-02-123 96-02-139 96-02-192
Keywords: yacc

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


Post a followup to this message

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