DFA transition tables ?

"SoftMan" <softman@colba.net>
21 Oct 1997 21:24:39 -0400

          From comp.compilers

Related articles
DFA transition tables ? softman@colba.net (SoftMan) (1997-10-21)
Re: DFA transition tables ? torbenm@diku.dk (1997-10-26)
| List of all articles for this month |

From: "SoftMan" <softman@colba.net>
Newsgroups: comp.compilers
Date: 21 Oct 1997 21:24:39 -0400
Organization: colba.net
Keywords: lex, DFA, question


I write a small oop lexical analizer.

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.

Current transition table I have just has an array of char (not fixed)
and assosiated array of word. eg on incoming char a I look what index
a has in first array and then take word with same index from second
array. But this is not really efficient becouse I search in the
array. If there is a way to implement a direct structure. Like simply
having one array of word and useing char ascii index as index of
transition, but without blank transitions. eg there is an array
0..255 of word and only one transition out of state. 225*2 bytes not

Also I have seen an implementation of lex which has am array of the
record. Record has two fields: set of char and state: integer; but
this is 32 + 2 bytes per transition.

If anyone knows an efficient way to do this task, I'd like to hear your
With best regards,


Post a followup to this message

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