size of parse table?

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

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