Re: DFA transition tables ?

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

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