|DFA transition tables ? email@example.com (SoftMan) (1997-10-21)|
|Re: DFA transition tables ? firstname.lastname@example.org (1997-10-26)|
|Date:||21 Oct 1997 21:24:39 -0400|
|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,
Return to the
Search the comp.compilers archives again.