Re: size of parse table?

grosch@cocolab.de (Josef Grosch)
15 Feb 2000 16:21:58 -0500

          From comp.compilers

Related articles
size of parse table? bob_jenkins@burtleburtle.net (2000-01-21)
Re: size of parse table? cbrtjr@ix.netcom.com (Charles E. Bortle, Jr.) (2000-02-05)
Re: size of parse table? world!cfc@uunet.uu.net (Chris F Clark) (2000-02-05)
Re: size of parse table? grosch@cocolab.de (2000-02-15)
Re: size of parse table? cbrtjr@ix.netcom.com (Charles E. Bortle, Jr.) (2000-02-16)
OOPSLA 2000 alpert@watson.ibm.com (Sherman Alpert) (2000-03-23)
| List of all articles for this month |

From: grosch@cocolab.de (Josef Grosch)
Newsgroups: comp.compilers
Date: 15 Feb 2000 16:21:58 -0500
Organization: Compilers Central
Keywords: parse, LALR, practice, comment

Our moderator wrote:


> [How important is it to pack parse tables these days? It was a hot
> topic back when your entire compiler had to fit in 64K, but now that
> PC applications routinely contain a megabyte of garbage because the
> programmer doesn't bother to delete unused templates and such, why
> bother? -John]


Packing parse tables is not important for parsers for small languages,
except in embedded systems or in antique and restricted environments.
However, it is still an issue for huge parsers, in my opinion.
Let me give a few examples:


Language COBOL PL/I C++


# terminals 783 255 169
# nonterminals 958 274 263
# symbols 1741 529 432
# rules 3347 1315 1017
# LR states 3290 1124 876 without states for LR(0) reductions
table size [MB] 11.5 1.19 0.76 without packing (two dimensional array)
table size [KB] 233 261 71 with packing (into a comb vector)
compression [%] 2.0 21.9 9.3


At least I would like to save those 11 MB in the case of our COBOL parser.




Dr. Josef Grosch


CoCoLab - Datenverarbeitung, Turenneweg 11, 77880 Sasbach, Germany
Phone: +49-7841-669144 , Fax : +49-7841-669145
Mail : grosch@cocolab.de, Web : www.cocolab.de
[Oh, right, COBOL. I agree, an 11M table is pretty big, even today. -John]


Post a followup to this message

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