Re: DFA, NFA space/time tradeoffs

SoftMan <softman@colba.net> wrote:
>I'm a little bit new to CC. I'd like to know what kind of finite state
>automata is used by modern compilers...


If you mean in their scanners, it's almost always a DFA or hand-coded
equivalent, for speed. Later phases of the compiler can deal with the
input in a higher-level form, but the scanner necessarily has to paw
through every character, so speed is of some importance there.


>And about space/time tradeoffs...


They're actually minor in this application. An NFA scanner for a
typical programming language is almost a DFA already. Most
programming-language constructs are designed to be easy to scan; the
pathological cases which greatly increase DFA space consumption and
DFA creation time are seldom present. The extra space needed for a
full DFA is not great, and the processing time needed to create one is
typically greatly outweighed by the better performance of the result.


>dfa is fatser, but still I'm concerned about that DFA is fixed once
>created. On the controrary NFA can be constructed before parsing.


Either one can be built just before processing starts, although it's
usually better to build it when the compiler is being generated.
(That may not be possible if the language has flexible syntax or the
details of the character set are not known until run time.) An NFA is
easier to alter dynamically, but that's rarely required in a compiler
for a modern language.
--
| Henry Spencer
| henry@zoo.toronto.edu
--

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