A table-driven lexer is just a way of simulating a DFA. Lexer generators build DFAs from a lexical description, and then compile the DFA into the tables necessary to produce a lexical scanner.
Note that the goal is to not just identify lexemes, but to classify them by lexical type. Some lexemes have a unique spelling (like
<=); others represent classes of symbols which have the same syntactic significance but different semantics. (That would be, for example, IDENTIFIER and NUMBER, which are two lexical types, each with a potentially unlimited number of different associated tokens.)
Lexical analysis with a state machine is slightly different from using a DFA to recognise strings, because the point of lexical analysis is to divide the input into a sequence of substrings, each of which is a token. It's important that this sequence is a partitioning of the string; every character is part of some token. That means that each successive token starts exactly where the previous token finished. In particular, that means that you don't have to worry about the
if in the middle of
different, but you do have to think about the
fortunate. (All the same, it doesn't present a huge problem.)
As the Dragon book notes (and so do Cooper&Torczon IIRC), the vast majority of lexers use the "maximal munch" procedure (sometimes with a few exceptions), in which the lexeme produced at some point in the input is the longest one matchable with some lexical pattern.
In some cases, it is possible that the lexical analyser will overreach. As an example, consider lexing C, where
... are both possible lexemes, but
.. is not. If the input contains
.., the lexical analyser needs to try to match the pattern
.... If that fails, if the input contains
.. followed by something other than another
. (for example,
..345), the lexical analyser will have to backtrack. It will accept the first
. as a token, and then restart the scan with the second
. (which will turn out to lead to recognizing the number token
.345 in this case).
So the precise algorithm used by the analyser when it is asked to produce the next token is:
Run the DFA until it reaches a state in which the next character has no valid transitions.
While running the DFA, always remember the last accepting state encountered.
When the DFA cannot be advanced any further, if it is not in an accepting state, back up to the last accepting state and return the corresponding token.
It's always a good idea to try to avoid this backtracking, but it is not always possible as the above C example indicates.
We said earlier that the goal of the analyser is to identify the lexical type of the token. How does it do that? Simple. The various patterns are combined into a single DFA, using the standard NFA->DFA transformation. (That's in the Dragon Book.) In the DFA which results from that transformation each state is a set of states from the original NFA, and is an accepting state if any of the associated NFA states is accepting. We map that onto a token type by noting which of the NFAs contains the associated accepting state. If there is more than one NFA which has contributed an accepting state, then we choose one of them arbitrarily. (Usually, we've arranged the patterns in priority order so that we can simply say that the first pattern wins.)
That gives us a mapping from DFA state to pattern number, and that is the role of the Token Type table.
In case that explanation was too theoretic, I've created two graphs. The first one shows DFAs for four patterns: the token
<, the token
<=, the token
if and the token
ID (any identifier). In the transitions, please interpret "letter" as meaning "any letter other than
f", which was just too long to put on the graph. And see the paragraph below about character classification.
In the second graph, I show the DFA which results from combining these. I leave it as an exercise to construct the Token Type table.
The Transition table is simple: it just represents the DFA. It maps a pair
<state, character> to a new state. Unfortunately, there are a lot of different possible characters -- 256, if we use 8-bit characters -- and usually quite a few states, and that would make for quite a large table, since it is essentially a two-dimensional array. To make the table smaller, we note that many characters have precisely the same transitions in every state. As a simple example, most of the 256 possible input characters are only valid inside character string literals or comments, and in those contexts all of them are effectively identical.
That's what the character classification table is. We gather the possible input characters into a set of equivalence classes, where each equivalence class has exactly the same transitions in every state. Any character with a specific transition -- including the
i and the
if, for example -- will be in an equivalence class by itself. But even then, we'll find that many alphabetic characters are not present in any keyword (upper-case characters, for example). And while some digits may have specific transitions --
0 is a common case -- there are very few lexicons in which
3 have specific transitions. So we can probably reduce the number of possible transition characters from 256 to maybe 40 or 50, which is an 80% reduction in size of the transition table. In any case, if you don't want to do that, it's just an optimisation. The analyser will work fine either way.