26 Oct 1997 22:06:14 -0500

Related articles |
---|

DFA transition tables ? softman@colba.net (SoftMan) (1997-10-21) |

Re: DFA transition tables ? torbenm@diku.dk (1997-10-26) |

From: | torbenm@diku.dk (Torben AEgidius Mogensen) |

Newsgroups: | comp.compilers |

Date: | 26 Oct 1997 22:06:14 -0500 |

Organization: | Department of Computer Science, U of Copenhagen |

References: | 97-10-103 |

Keywords: | lex, DFA |

"SoftMan" <softman@colba.net> writes:

*>I need to implement very fast and efficient search for the transition*

*>out of state. There problem I have right now is efficiency and*

*>size. Space/time tradeoffs will never be easy.*

[Various suggestions deleted]

A common method of minimizing jump tables is to observe that, even

across all states, all digits select the same transition and similarly

for letters etc. Hence, characters are grouped in equivalence classes

based on identical transitions over all states. A transition first

looks up in one table to find the equivalence class and then uses a

reduced transition table that cross-indexes state and character class

to find the next state.

This method typically breaks down if keywords are encoded directly in

the DFA rather than trough a symbol table (the latter is generally a

good idea anyway, as it makes for a smaller DFA).

Another method is to hash down the character to a smaller range, and

use lists of character/transition pairs for each index in the smaller

range. A selection of different hash functions can be used to reduce

the length of the lists.

A third alternative, using renumbering, was proposed in the paper

"Design and Implementation of Jump Tables for Fast Indexing og Logic

Programs" by Dawson et al. at PLILP'95, Springer LNCS 982. Though the

method was designed for pattern matching in logic programs, section

6.2 of the paper details experiments using the method as a compression

technique for transition tables in scanners, with results close to a

fully dense table.

Torben Mogensen (torbenm@diku.dk)

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.