Mon, 7 Oct 91 10:17:36 -0700

Related articles |
---|

NFA to DFA, minimize DFA roberto@cernvax.cern.ch (1991-10-04) |

Re: NFA to DFA, minimize DFA bburshte@pyrps5.eng.pyramid.com (1991-10-07) |

Re: NFA to DFA bburshte@pyrps5.eng.pyramid.com (1991-10-09) |

Re: NFA to DFA, minimize DFA karsten@tfl.dk (1991-10-09) |

Newsgroups: | comp.compilers |

From: | bburshte@pyrps5.eng.pyramid.com (Boris Burshteyn) |

Keywords: | lex, theory |

Organization: | Compilers Central |

References: | 91-10-015 |

Date: | Mon, 7 Oct 91 10:17:36 -0700 |

*>From roberto bagnara:*

(4 Oct 91 09:41:18)

*>Has anybody got a good (e.g. *fast*) algorithm/implementation for the*

*>problem of converting an NFA (nondeterministic finite automaton) to a DFA*

*>(deterministic finite automaton)? And for the problem of minimizing the*

*>number of states of a DFA?*

I have recently implemented conversion from NFA to DFA while developing

minimal state full LR1 parser generator. I supposed that the most time

consuming operations are:

1. comparison of two (or several) sets of objects.

2. getting union and intersection of several sets of objects.

It is possible to have all these operations implemented with the speed

o(l) where l is the maximum power of the involved sets. The technique is

to have an integer 'w' stored in each of the objects and mark that integer

with the value unique to the set. For example, if p1 points to a list of

objects, p2 points to some other list of objects, then the comparison

algorithm may look something like the following (assuming lists end with 0

link):

int compare(register object *p1, register object *p2, register int i)

{

register int c = 0;

while ( p1 )

{

p1->w = i;

p1 = p1->link;

c++;

}

while ( p2 )

{

if ( p2->w != i )

return 1; // failure, sets are not equal

p2 = p2->link;

c--;

}

if ( c )

return 1; // failure, sets are not equal

return 0; // o'k, sets have the same elements

*}*

The driving algorithm which calls functions like compare() must increment

the 'generation number' 'i' each time before calling such a function in

order to perform a number of these operations correctly.

The technique has resulted in the speed of the LR1 parser generator

(written in C++) twice as fast as YACC.

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.