25

I'm slowly working to finish my degree, and this semester is Compilers 101. We're using the Dragon Book. Shortly into the course and we're talking about lexical analysis and how it can be implemented via deterministic finite automata (hereafter, DFA). Set up your various lexer states, define transitions between them, etc.

But both the professor and the book propose implementing them via transition tables which amount to a giant 2d array (the various non-terminal states as one dimension, and the possible input symbols as the other) and a switch statement to handle all of the terminals as well as dispatch to the transition tables if in a non-terminal state.

The theory is all well and good, but as someone who's actually written code for decades, the implementation is vile. It's not testable, it's not maintainable, it's not readable, and it's a pain and a half to debug through. Worse yet, I can't see how it would be remotely practical if the language was UTF capable. Having a million or so transition table entries per non-terminal state gets unweildy in a hurry.

So what's the deal? Why is the definitive book on the subject saying to do it this way?

Is the overhead of function calls really that much? Is this something that works well or is necessary when the grammar isn't known ahead of time (regular expressions?)? Or perhaps something that handles all cases, even if more specific solutions will work better for more specific grammars?

(note: possible duplicate "Why use an OO approach instead of a giant switch statement?" is close, but I don't care about OO. A functional approach or even saner imperative approach with standalone functions would be fine.)

And for the sake of example, consider a language that only has identifiers, and those identifiers are [a-zA-Z]+. In the DFA implementation, you'd get something like:

private enum State
{
    Error = -1,
    Start = 0,
    IdentifierInProgress = 1,
    IdentifierDone = 2
}

private static State[][] transition = new State[][]{
    ///* Start */                  new State[]{ State.Error, State.Error (repeat until 'A'), State.IdentifierInProgress, ...
    ///* IdentifierInProgress */   new State[]{ State.IdentifierDone, State.IdentifierDone (repeat until 'A'), State.IdentifierInProgress, ...
    ///* etc. */
};

public static string NextToken(string input, int startIndex)
{
    State currentState = State.Start;
    int currentIndex = startIndex;
    while (currentIndex < input.Length)
    {
        switch (currentState)
        {
            case State.Error:
                // Whatever, example
                throw new NotImplementedException();
            case State.IdentifierDone:
                return input.Substring(startIndex, currentIndex - startIndex);
            default:
                currentState = transition[(int)currentState][input[currentIndex]];
                currentIndex++;
                break;
        }
    }

    return String.Empty;
}

(though something that would handle end of file correctly)

Compared to what I would expect:

public static string NextToken(string input, int startIndex)
{
    int currentIndex = startIndex;
    while (currentIndex < startIndex && IsLetter(input[currentIndex]))
    {
        currentIndex++;
    }

    return input.Substring(startIndex, currentIndex - startIndex);
}

public static bool IsLetter(char c)
{
    return ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'));
}

With the code in NextToken refactored out into its own function once you have multiple destinations from the start of the DFA.

15
  • 5
    a heritage of ancient (1977) Principles of Compiler Design? 40 years ago, coding style was much different – gnat Oct 1 '14 at 14:09
  • 7
    How would you implement the transitions of the DFA states? And what's this about terminals and non-terminals, "non-terminals" usually refers to production rules in the grammar, which would come after lexical analysis. – user7043 Oct 1 '14 at 14:25
  • 10
    Those tables are not meant to be readable to humans, they are meant to be usable by the compiler and to perform very quickly. It is easy to jump around a table when looking ahead in the input (e.g. to catch left recursion, although in practice most languages are built to avoid that). – user22815 Oct 1 '14 at 15:17
  • 5
    If some portion of your irritation is coming from knowing how to do a better job and lacking the ability to get any feedback or appreciation for an approach you'd prefer - as decades in industry does train us to expect feedback and at times appreciation - perhaps you should write your better implementation and post it to CodeReview.SE to get some of that for your own peace of mind. – Jimmy Hoffa Oct 1 '14 at 15:21
  • 7
    The simple answer is because the lexer is usually implemented as a finite state machine and generated automatically from the grammar -- and a state table is, not surprisingly, most easily and compactly represented as a table. As with object code, the fact that it isn't easy for humans to work with is irrelevant because humans don't work with it; they change the source and generate a new instance. – keshlam Oct 1 '14 at 22:04
7

The motivation for the particular algorithm is largely that it's a learning exercise, so it tries to stay close to the idea of a DFA, and keep states and transitions very explicit in the code. As a rule, nobody would actually manually write any of this code anyway - you would use a tool to generate code from a grammar. And that tool wouldn't care about the readability of the code because it isn't source code, it's an output based on the definition of a grammar.

Your code is cleaner for someone maintaining a hand-written DFA, but a little farther removed from the concepts being taught.

17

In practice these tables are generated from regular expressions that define the tokens of the language:

number := [digit][digit|underscore]+
reserved_word := 'if' | 'then' | 'else' | 'for' | 'while' | ...
identifier := [letter][letter|digit|underscore]*
assignment_operator := '=' | '+=' | '-=' | '*=' | '/=' 
addition_operator := '+' | '-' 
multiplication_operator := '*' | '/' | '%'
...

We have had utilities to generate lexical analyzers since 1975 when lex was written.

You are basically suggesting replacing regular expressions with procedural code. This expands a couple of characters in a regular expression into several lines of code. Handwritten procedural code for lexical analysis of any moderately interesting language tends to be both inefficient and difficult to maintain.

10
  • 4
    I'm not sure I'm suggesting that wholesale. Regular expressions will deal with arbitrary (regular) languages. Aren't there better approaches when working with specific languages? The book touches on predictive approaches but then ignores them in examples. Also, having done a naive analyzer for C# years ago I didn't find it terribly hard to maintain. Inefficient? sure, but not terribly so given my skill at the time. – Telastyn Oct 1 '14 at 16:58
  • 1
    @Telastyn: it's almost impossible to go faster than a table-driven DFA: get next character, lookup next state in transition table, change state. If the new state is terminal, emit a token. In C# or Java any approach that involves creating any temporary strings will be slower. – kevin cline Oct 1 '14 at 18:15
  • @kevincline - sure, but in my example there aren't temporary strings. Even in C it would just be an index or a pointer stepping through the string. – Telastyn Oct 1 '14 at 18:23
  • 6
    @JimmyHoffa: yes, performance is definitely relevant in compilers. Compilers are fast because they have been optimized to hell and back. Not micro-optimizations, they just don't do unnecessary work like creating and discarding unneeded temporary objects. In my experience most commercial text processing code does one-tenth the work of a modern compiler and takes ten times as long to do it. Performance is huge when you are processing a gigabyte of text. – kevin cline Oct 1 '14 at 19:30
  • 1
    @Telastyn, what "better approach" did you have in mind, and in what way would you expect it to be "better"? Given that we already have lexing tools that are well-tested, and they produce very fast parsers (as others have said, table-driven DFAs are very fast), it makes sense to use them. Why would we want to invent a new special approach for a specific language, when we could just write a lex grammar? The lex grammar is more maintainable, and the resulting parser is more likely to be correct (given how well tested lex and similar tools are). – D.W. Oct 1 '14 at 21:38
7

The inner loop of:

                currentState = transition[(int)currentState][input[currentIndex]];
                currentIndex++;
                break;

has a lot of performance advantages. There are no branches in that at all, because you do exactly the same thing for every input character. The performance of the compiler can be gated by the lexer (which must operate on a scale of every character of input). This was even more true when the Dragon Book was written.

In practice, besides CS students studying lexers, no one has to implement (or debug) that inner loop because it is part of the boilerplate that comes with the tool that builds the transition table.

5

From memory, -- it's a long time since I've read the book, and I'm pretty sure I didn't read the latest edition, I for sure don't remember something looking like Java -- that part was written with the code being intended to be a template, the table being filled with a lex like lexer generator. Still from memory, there was a section on table compression (again from memory, it was written in such a way that it was also applicable to table driven parsers, thus perhaps further in the book than what you have seen yet). Similarly, the book I remember assumed an 8-bit character set, I'd expect a section on handling bigger character set in later editions, probably as part of the table compression. I've given an alternative way to handle that as an answer to a SO question.

There is a sure performance advantage in having a tight loop data driven in modern architecture: it's quite cache friendly (if you have compressed the tables), and jump prediction is as perfect as possible (one miss at the end of the lexem, perhaps one miss for the switch dispatching to the code which depend on the symbol; that's assuming that your table decompression can be done with predictable jumps). Moving that state machine to pure code would decrease the jump prediction performance and perhaps increase the cache pressure.

2

Having worked through the Dragon Book before, the principle reason for having table driven levers and parsers is so that you can use regular expressions to generate the lexer and BNF to generate the parser. The book also covers how tools like lex and yacc work, and in order so that you know how these tools work. Furthermore, it is important for you to work through some practical examples.

Despite many of comments, it has nothing to do with the style of code that was written in the 40's, 50's, 60's ..., it has to do with gaining a practical understanding of what the tools are doing for you and what you have to do to make them work. It has everything to do with the fundamental understanding how compilers work both from a theoretical and practical standpoint.

Hopefully, your instructor will also let you use lex and yacc (unless it is a graduate level class and you get to write lex and yacc).

0

Late to the party :-) The tokens are matched against regular expressions. Since there are many of them, you have the multi regex engine, which in turn is giant DFA.

"Worse yet, I can't see how it would be remotely practical if the language was UTF capable."

It is irrelevant (or transparent). Besides UTF has nice property its entities do not overlap even partially. E.g. the byte representing character "A" (from ASCII-7 table) is not used again for any other UTF character.

So, you have single DFA (which is multi-regex) for entire lexer. How better to write it down than 2d array?

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.