26 Sep 1998 01:46:51 -0400

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

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.