|DFA, NFA space/time tradeoffs email@example.com (SoftMan) (1997-10-08)|
|Re: DFA, NFA space/time tradeoffs Peter_Eyes_Eiserloh@WSSAGW.chinalake.navy.mil (Peter P. Eiserloh) (1997-10-10)|
|Re: DFA, NFA space/time tradeoffs firstname.lastname@example.org (Henry Spencer) (1997-10-10)|
|From:||"Peter P. Eiserloh" <Peter_Eyes_Eiserloh@WSSAGW.chinalake.navy.mil>|
|Date:||10 Oct 1997 22:03:39 -0400|
|Organization:||Naval Air Warfare Center - Weapons Division|
|Posted-Date:||Wed, 8 Oct 1997 10:47:52 -0700 (PDT)|
SoftMan, email@example.com writes:
>I'm a little bit new to CC. I'd like to know what kind of finite state
>automata is used by modern compilers. And about space/time tradeoffs. IMHO
>dfa is fatser, but still I'm concerned about that DFA is fixed once
>created. On the controrary NFA can be constructed before parsing.
Yes, it is easier to build an NFA, but the DFA is much faster than
an NFA (depending upon the size of the NFA). You almost alway want
to execute a DFA. You want to build a NFA, but execute a DFA.
There are standard techniques to derive a DFA from a NFA, and from
that DFA you can generate a minimal DFA. This is the process that
lex (and flex) use to build the DFA in scanners. Most compiler books
such as the dragon book, or "Crafting a Compiler" discuss this.
: Peter "Eyes" Eiserloh firstname.lastname@example.org
Return to the
Search the comp.compilers archives again.