# size of parse table?

## bob_jenkins@burtleburtle.net21 Jan 2000 00:41:31 -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)
| List of all articles for this month |

 From: bob_jenkins@burtleburtle.net Newsgroups: comp.compilers Date: 21 Jan 2000 00:41:31 -0500 Organization: Deja.com - Before you buy. Keywords: parse, question, practice

I've read that parsers generate a table of productions, with each
state leading to several possible next states depending on the next
token. I seem to remember that this table is a bunch of labelled
states, and states are labelled such that you can add the ID for the
next token to some base determined by your current state to transition

Assuming I got that right, how big is the table compared to the total
number of (state, transition) pairs? Is the number of
(state,transition) pairs the same as the number of states?

I ask because I'm playing with a perfect hash of the form A^tab[B]
given a pair (A,B). If you define A to be the ID of the next token
and B to be the current state, generating a perfect hash looks exactly
like the problem of making a compact parse table. When (A,B) are
uniformly distributed, I can get an n-element table when there are on
average 4 As per B, and a 2n element table when there are on average
32 As per B.

- Bob Jenkins
http://burtleburtle.net/bob/hash/perfect.html

Post a followup to this message