Re: DFA, NFA space/time tradeoffs

"Peter P. Eiserloh" <Peter_Eyes_Eiserloh@WSSAGW.chinalake.navy.mil>
10 Oct 1997 22:03:39 -0400

          From comp.compilers
Related articles
DFA, NFA space/time tradeoffs softman@colba.net (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 henry@zoo.toronto.edu (Henry Spencer) (1997-10-10)
| List of all articles for this month |
From: "Peter P. Eiserloh" <Peter_Eyes_Eiserloh@WSSAGW.chinalake.navy.mil>
Newsgroups: comp.compilers
Date: 10 Oct 1997 22:03:39 -0400
Organization: Naval Air Warfare Center - Weapons Division
References: 97-10-032
Keywords: DFA, parse
Posted-Date: Wed, 8 Oct 1997 10:47:52 -0700 (PDT)

SoftMan, softman@colba.net 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 eiserloh@llab.chinalake.navy.mil
--

Post a followup to this message

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