0
$\begingroup$

I am studying Crafting Interpreters, and although I understand the responsibility of the Scanner (or Lexer), I still cannot understand if it is a deterministic finite automaton or non-deterministic finite automaton. The code responsible for scanning the input text in the book is:

    private void scanToken() {
        char c = advance();
        switch (c) {
            case '(': addToken(LEFT_PAREN); break;
            case ')': addToken(RIGHT_PAREN); break;
            case '{': addToken(LEFT_BRACE); break;
            case '}': addToken(RIGHT_BRACE); break;
            case ',': addToken(COMMA); break;
            case '.': addToken(DOT); break;
            case '-': addToken(MINUS); break;
            case '+': addToken(PLUS); break;
            case ';': addToken(SEMICOLON); break;
            case '*': addToken(STAR); break;
            case '!':
                addToken(match('=') ? BANG_EQUAL : BANG);
                break;
            case '=':
                addToken(match('=') ? EQUAL_EQUAL : EQUAL);
                break;
            case '<':
                addToken(match('=') ? LESS_EQUAL : LESS);
                break;
            case '>':
                addToken(match('=') ? GREATER_EQUAL : GREATER);
                break;
            case '/':
                if (match('/')) {
                    while (!isAtEnd() && peek() != '\n') {
                        advance();
                    }
                } else if (match('*')) {
                    do {
                        if (peek() == '*' && peekNext() == '/') {
                            advance();
                            advance();
                        } else {
                            advance();
                        }
                    } while (!isAtEnd());
                } else {
                    addToken(SLASH);
                }
                break;
            case ' ':
            case '\r':
            case '\t':
                // Ignore whitespace.
                break;
            case '\n':
                line++;
                break;
            case '"': string(); break;
            default:
                if (isDigit(c)) {
                    number();
                } else if (isAlpha(c)) {
                    identifier();
                } else {
                    Lox.error(line, "Unexpected character.");
                }
                break;
        }
    }

According to several sites out there, the FA definition is:

Finite Automata(FA) is the simplest machine to recognize patterns.The finite automata or finite state machine is an abstract machine which have five elements or tuple. It has a set of states and rules for moving from one state to another but it depends upon the applied input symbol. Basically it is an abstract model of digital computer. Following figure shows some essential features of a general automation.

A DFS consists of the following:

Q : Finite set of states.
Σ : set of Input Symbols.
q : Initial state.
F : set of Final States.
δ : Transition Function.

and for NFA:

Q : set of all states.
Σ : set of input symbols. ( Symbols which machine takes as input )
q : Initial state. ( Starting state of a machine )
F : set of final state.
δ : Transition Function, defined as δ : Q X Σ --> Q.

My lexer can start in any state, does that mean it is either DFA or NFA? How can I conclude if it is one or the other?

$\endgroup$
1
  • $\begingroup$ Your definition of an NFA is not correct. $\endgroup$ – ttnick Apr 23 at 18:13
1
$\begingroup$

Any piece of code can never be non-deterministic (a non-deterministic process can "multiply itself" by a constant factor every step, and obviously computers can't just multiply by their own free will).

Hence it is a DFA.


Also, your lexer will start always at the initial state $s_0$, and from it, depending on what it reads - it moves to different states.

$\endgroup$
8
  • $\begingroup$ If it can move to different states from s0, should not be an NFA then? $\endgroup$ – DDDDDD Apr 23 at 18:06
  • 2
    $\begingroup$ A DFA is a state machine that moves between states depending on what it reads. The difference between it and an NFA, is that NFA is non-deterministic, meaning it can decide to move into more than one state simultaneously (which cannot happen in the real world computer) $\endgroup$ – nir shahar Apr 23 at 18:11
  • 2
    $\begingroup$ The state in which you automaton goes to is completely determined by the current state and the current symbol. Therefore, it is deterministic. $\endgroup$ – ttnick Apr 23 at 18:12
  • $\begingroup$ @nirshahar: You can simulate an NFA with a DFA, so in a certain sense the NFA is also deterministic (in the sense that it can be deterministically executed with a piece of single-threaded code). If you were to take that as a criterion, there would be no such thing as an NFA. $\endgroup$ – rici Apr 23 at 20:53
  • $\begingroup$ Your argument beats the purpose of thinking about NFA's. Its true that any NFA can be converted into an equivalent DFA, but the size of the DFA significantly increases. This is more important when we think of $P$ and $NP$ complexity classes, for which your argument does not really help (any non-deterministic TM can be converted to a deterministic TM, but at what cost?). $\endgroup$ – nir shahar Apr 23 at 20:56
1
$\begingroup$

The difference between NFAs and DFAs is not so huge, because you can trivially convert an NFA into a DFA simply by using the elements of the power set of the states of the NFA as the states of a DFA.

Usually, not all the elements of the power set turn out to be accessible, so the DFA is not as huge as this transformation makes it sound. But there are some NFAs whose transformation into a DFA involves exponential blow-up.

It's possible to emulate an NFA reasonably efficiently by implicitly using the power-set transformation without actually computing the entire transformation matrix, and this is done by many regular expression libraries. If you represent the powerset as a binary vector, it's easy to use it as a hash table key; the hash table is used to cache particular values of the transition function. The cache is capped at a certain size in order to avoid memory exhaustion; if the traverse of the NFA requires more powerset elements than can fit in the cache, some of them will be dropped from the cache and recomputed when necessary. (The recomputation doesn't take much time; although it is theoretically $O(|Q|^2)$ where $|Q|$ is the number of states in the NFA, in practice storing state sets as bit vectors means that the set union operation can be done with a single bitwise boolean operation, or a few such operations if there are really a lot of states in the NFA.)

Lexical scanner generators often precompute the entire DFA, on the assumption that the scanner descriptions they will be handling don't involve exponential blow-up. If that assumption is wrong, the scanner generator will either take an enormous amount of time to process the scanner description, or will fail because of memory exhaustion, or both. With a little work, you can create a fairly short scanner description that flex cannot handle. But practical programming languages rarely include these kinds of lexical constructs.

The key difference between a regular expression library and a scanner generator is that the regular expression library is doing its work at runtime, and possibly using a user-supplied regular expression. So the regular expression library needs to avoid algorithms which could take exponential time, in order to prevent denial-of-service (DoS) attacks. (Or at least, the library should avoid such vulnerabilities. Not all of them do.)

The scanner generator, on the other hand, is executed once when the scanner is compiled using a lexical definition supplied by the programmer. If that definition involves exponential blow-up, the programmer will have to fix it or live with very slow compile times, just as with any other compilation issue. No runtime vulnerability is involved. (At least, that's the usual use case. There are a few applications which might call a scanner generator at runtime using a user-supplied input; putting an application like that into production would require some kind of protection against denial-of-service attacks. But that's not the context in which flex is generally used.)

The particular code you present in your question was not generated either by a scanner generator nor a regular expression library. It's mostly a very simple DFA, where the first character of the token defines the only state transition. (Identifiers and numbers involve functions which may well be implemented with slightly more complex state machines, or which might use standard library functions or some other idiosyncratic technique. But either way they have probably been precompiled into the equivalent of a DFA by a programmer.)

There is one place in the code which is visibly not emulating a finite-state automaton at all: the code to recognise comments includes a two-character lookahead and fallback, which is not how a comment would be recognised by a finite automaton (NFA or DFA). In that sense, I would agree with the commenter (to a previous version of this question, now deleted) who said that the program is neither an NFA nor a DFA; rather, it's a computer program. But it's interesting how little state is used by the program; there is only one local variable, which is the character being processed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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