# 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
to your next state.

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

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