5 Feb 2000 18:47:50 -0500

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

From: | Chris F Clark <world!cfc@uunet.uu.net> |

Newsgroups: | comp.compilers |

Date: | 5 Feb 2000 18:47:50 -0500 |

Organization: | The World Public Access UNIX, Brookline, MA |

References: | 00-01-086 |

Keywords: | parse, comment |

*> 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]

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.