Re: 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.


In most parse table representations, you build an array "next_state",
such that each state is an offset into the next state array. The
distinct token types are all given sequential numbers. (The numbers
don't have to be sequential, but they usually are.) This number plus
the state are used as the index into the next state array. This can
be done with or without packing.


The packing I believe you are interested in is called "comb-vector".
In comb-vector packing, one utilizes the fact that many state-token
type combinations are impossible. Those are treated as don't cares.
Using the don't care entries in the array to hold valid entries from
other states allows one to make the states overlap in the array.
Simply overlap the don't care entries of one array with the valid
entries of the other and vice-versa. (There are also ways to increase
the number of don't care entries.)


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


Because the filling of the entries in one state follow a sharp decay
(I believe it is roughly exponential, such that half the states have 1
entry, a quarter have 2 entries, an eighth have 3, etc.) The total
table size turns out to be linear in the number of states--where twice
as many states require twice as big a table. I don't know the exact
ratio that occurs.


There is an excellent TOPLAS paper that discusses state table packing
in wonderful detail. However, I don't have the reference at hand at
the moment.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. CompuServe : 74252,1375
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)
------------------------------------------------------------------------------
Web Site in Progress: Web Site : http://world.std.com/~compres
[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]

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