DFA table compression from Aho's Dragon book, need more detail

Hi,


After weeks of studying, I finally got my NFA, NFA to DFA routines to
work. But, I was stuck at Aho's table compression method in the
Dragon book (p144-146).


It is said that 4 tables: default, base, next and check are to be
constructed. But, how? I could not make sense out of the names and
descriptions.


Another question: Aho also only quickly talked about DFA minimization,
I am not sure if I got it right: only DFA's with same important states
can be combined. Thus, at the end of the e_closure routine, I get rid
of all the epsilon edge out nodes and only keep the accept states and
alphabet edge out nodes. If there is a DFA state in the DFA states
that contains the exactly the same set of states, the discard the
newly created e_closure set and refer to the old one instead.


The last question is, what is the efficient way to mark and unmark
state T in the subset construction (NFA to DFA) on p118 of the book?
I used a stack. Also it is quit slow to find out whether if a new DFA
state is already present in the Dstates.


Please help me, I don't have much background.


Thanks.
--
Name: Heng Yuan Email: heng@ag.arizona.edu
Home: http://ag.arizona.edu/~heng/
--

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