7
$\begingroup$

I am taking the Coursera class on compilers and in the lesson about lexers it is hinted that there is a time-space tradeoff between using non-deterministic finite automaton (NFA) and deterministic finite automaton (DFA) to parse regular expressions. If I understand correctly, the tradeoff is that a NFA is smaller, but is more time consuming to traverse because all possible states have to be regarded at the same time and therefore it is most of the time transformed into a DFA. Are there any lexers that use NFAs instead of DFAs in "real"-life i.e. some compiler that is used in production and not a just a proof of concept?

$\endgroup$
2
  • $\begingroup$ Instead of "... all possible states have to be regarded ...", it is that "... all possible transitions have to be regarded ...". This is exponentially harder, and can quickly grow bigger than the total number of states. $\endgroup$
    – Paresh
    Feb 12, 2013 at 21:35
  • $\begingroup$ While I am not positive on this, wouldn't the way PROLOG parses per se meet your requirements. $\endgroup$
    – Guy Coder
    Feb 13, 2013 at 1:59

4 Answers 4

4
$\begingroup$

I see only two applications of using an NFA (or rather its power automaton without writing it down) instead of a minimized DFA:

  1. Homoiconic languages, where you may want to modify your lexer frequently
  2. Strange syntax that may blow up your DFA like

    identifier := [a-z][a-z0-9_]*
    indices := [0-9_]{1,256} //up to 256 times
    var := identifier "_" indices | identifier
    

    If you take the last rule as a precedence, your lexer has to check whether an identifier contains "_" within the last 256 symbols and shorten it in this case.

$\endgroup$
2
  • 1
    $\begingroup$ If some sadist gave me the second language, I'd handle that outside the strict FA. For example, C compilers normally recognize the /* starting a comment and skip ahead to the matching */ in C code. Besides, a language containing that would be next to impossible to read for humans. $\endgroup$
    – vonbrand
    Mar 30, 2013 at 17:55
  • $\begingroup$ This wasn't meant to be a natural example, on the other hand it's not that hard to read if not heavily abused and heavy abuse of syntax is possible in C too. Handling this like comments in C (mode switch) is not so easy, because it depends on the end of a possible identifier. (+1 for the "sadist"). $\endgroup$
    – frafl
    Mar 30, 2013 at 18:24
4
$\begingroup$

Compiled lexical analyzers compile the NFA to a DFA.

Good interpreted regular expression matchers, on the other hand, use Thompson's algorithm, simulating the NFA with memoization. This is equivalent to compiling the NFA to a DFA, but you only produce DFA states on demand, if they are needed. At each step your deterministic state is a set of NFA states, then given the next input character you transition to a new set of NFA states. You cache previously seen states and their output transitions in a hash table. The hash table is flushed if it fills up, it does not grow without bound.

The reason you do it this way is that converting the NFA to DFA can take time exponential in the size of the regular expression. This is certainly not something you want to do if you are only evaluating the regular expression once.

RE2 is an example of a regex engine that (essentially) uses Thompson's algorithm. I can highly recommend the brilliant blog posts by RE2's author Russ Cox if you want to learn more (including lots of historical information and experimental comparisons of lots of different approaches to regex searching.

I can also highly recommend the "why GNU grep is fast" email chain. Lesson 1 is: the common case for regex search is simple string search, so special case your algorithm.

$\endgroup$
3
$\begingroup$

I'd be surprised if they did. The construction of the lexer is done once (hopefully), the result used millions of times (just think how many tokens there are in your medium-sized source file). So, unless there are very unusual circumstances, it pays off to make the lexer as fast (and other resource frugal) as possible, i.e., go for a minimal DFA.

$\endgroup$
1
  • 1
    $\begingroup$ The minimal DFA may very well be exponential in size; if it's too large, exploring the NFA may be more reasonable than storing the DFA. That said, I don't know that any system considers that. $\endgroup$
    – Raphael
    Apr 2, 2013 at 7:29
0
$\begingroup$

In the strict formal sense, no. Non-determinism in the theory/mathematical sense allows a machine to choose a computation path based on whether it eventually leads to an accepting state or not without looking any further ahead in the input. So in this strict sense it's a property that's only suitable for theoretical examination, and there's no such thing as a real non-deterministic machine, particular to this case you can't actually build an NFA, unless you can see into the future, in which case building a compiler with this talent is a bit of a waste! ;).

However, nondeterministic and nondeterminism are often used in a weaker sense, hazily defined. Sometimes it can mean randomised/probabilistic - the algorithm flips a coin, in a formal setting this is studied as probabilistic/randomised algorithms, and not referred to as nondeterminism. Another use is for an algorithm that doesn't necessarily produce the same output given two runs on the same input - it may not be random, but some part of its behaviour is unspecified, so there may be several valid outputs (personally I think this definition comes comes from confusing un-determined and non-deterministic.

Nonetheless, you could, in principle build a lexer that is nondeterministic in one of these weaker, informal senses, however it wouldn't be an NFA (that's a strict formal machine model) and I can't imagine it'd be a crash hot idea either - a lexer needs to be quite predictable.

The last option is that you can simulate non-determinism via backtracking or parallelism, but in this case you lose out on the apparent efficiency of non-determinism, as you're effectively turning it into a deterministic computation, so you're no better off than with a DFA.

$\endgroup$
3
  • $\begingroup$ In this particular case, it is quite possible to keep track of all possible states the NFA could be in with modest space cost, essentially doing a breadth first sweep of the computation tree in parallel. No crystal ball required. $\endgroup$
    – vonbrand
    Mar 30, 2013 at 17:58
  • $\begingroup$ @vonbrand which is what the sensible version of the power set NFA to DFA transformation does, so we're back to a DFA. $\endgroup$ Mar 31, 2013 at 5:08
  • $\begingroup$ The OP is an implementation question. In this context the difference between a DFA and an NFA is that in DFA every state has exactly one output transition for every possible input symbol. An NFA, in this context, is a state machine where each state can have 0, 1 or many output transitions per input symbol, and also permits $\epsilon$ transitions. The OP is asking whether, in practice, we (deterministically) simulate the NFA (by keeping sets of states) or whether we compile the NFA to DFA, and then run the DFA. Whether there is any "real" nondeterminism is irrelevant. $\endgroup$ May 6, 2013 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.