21 Jan 2000 00:41:31 -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: | 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.