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

heng@Ag.Arizona.Edu (Heng Yuan)
26 Sep 1998 01:46:51 -0400

          From comp.compilers

Related articles
DFA table compression from Aho's Dragon book, need more detail heng@Ag.Arizona.Edu (1998-09-26)
Re: DFA table compression from Aho's Dragon book, need more detail octavian@earthlink.net (1998-09-29)
Re: DFA table compression from Aho's Dragon book, need more detail lord@emf.emf.net (1998-10-04)
| List of all articles for this month |

From: heng@Ag.Arizona.Edu (Heng Yuan)
Newsgroups: comp.compilers
Date: 26 Sep 1998 01:46:51 -0400
Organization: University of Arizona, Tucson, AZ
Keywords: lex

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/
--


Post a followup to this message

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