From Finite Automata To A Lexical Analyzer

mgcadmin 10-20-2026

Lexcial analysis is the first step in any compilation pipeline, and while writing a lexical analyzer is not particularlly difficult to implement by hand, it can incredibly tedious - especially doing it more than once. It's these very properties also make lexical analyzer construction perfect for automation. Since at least the mid-1970's there have been tools for doing so. The most famous of which, the epynomously named "Lex" laid the foundation for the architecture still used by most modern Lexer-Generators. The general idea of these generators is to take a "specification file", where a list of patterns in the form of regular expressions is provided and associated actions to perform in the form of snippets of code to execute when the patterns match are used to output the finished lexical analyzer. My own lexer generator, mgclex follows this architecture as well, though i engineered it to simply return tokens instead of executing code upon matching.

In previous articles I've covered both the Aho, Sethi, Ullman Direct-to-DFA construction and Thompsons Construction for NFA along with Moores Algorithm for converting an NFA to a DFA. To get the most out of this post, you should definitely be at least familiar with the process of converting a regular expression to a Deterministic Finite Automaton. As those topics are covered both on this blog and elsewhere, I'm instead going to cover the parts of creating a lexical analyzer from automata that most people leave out. Lets get to it. 

The Role of Lexical Analyzers

Inside of a compiler the job of the lexical analyzer is to take the raw input in the form of a string, either from a REPL or code file and return a stream of <Token,String> pairs. It is the first step of the compilation pipeline and the only step which examines every single charachter of the input. It's responsible for taking input in a form like this: 

if (1+1 < 3) print 42

And break it down into a list of its individual components - its tokens. 

(IF, if)
(LPAR, ()
(NUMBER, 1)
(PLUS, +)
(NUMBER, 1)
(LESS, <)
(NUMBER, 3)
(RPAR, ))
(PRINT, print)
(NUMBER, 42)

This list of token objects is what is fed to the next stage of the compilation pipeline - the parser. Before the parser can tell if symbols are arranged correctly or not, we need to know what the symbols actually are, and determining what those symbols are is the lexers job. 

Token Pattern Rules

Before we can generate those tokens however, we need a way to specify the patterns and how to identify them. That's the job of the token pattern rules, and will serve as the input to our lexgen. 

struct TokenPattern {
    string pattern;
    string token;
    int number;
    TokenPattern(string p= "", string t = "", int n = 0) : pattern(p), token(t), number(n) { }
};

A vector of the above objects will do just fine. For Id's we use a pattern for upper or lower case letter followed by 0 or more letters or numbers. a number is one or more digit, and constants are just those words. And of course any tokens which are also regular expression operators have to be escaped.

vector<PatternTokenRule> patrules = {
                                          {"([A-Za-z][A-Za-z0-9]*)", "ID", 1},
                                          {"([0-9]+)", "NUMBER", 2}, 
                                          {"if", "IF", 3}, 
                                          {"print", "PRINT", 4}, 
                                          {"\\+","PLUS", 5}, 
                                          {"\\(","LPAR", 6}, 
                                          {"\\)","RPAR", 7}, 
                                          {"<","LESS",8} 
                                        };

Now that we have our patterns we can start building the automata.

Patterns to Individual NFAs with Thompsons Construction

Even though our ultimate goal is to have one big NFA, we need to first generate the individual automata, which we then manually stictch together using epsilon transitions. We do this so we can capture the individual accept states for the patterns before they are merged into the larger pattern.

We also combine the actual text of the individual patterns into a string representation of expression represented by the larger combined NFA. This pattern is simply the individual patterns OR'd ('|') together. We do this to simplify building the alphabet during DFA conversion.

pair<string,NFA> toNFA(vector<TokenPattern>& patrules, vector<NFAState>& acceptStates) {
    NFACompiler compiler;
    string final_expr = "("; 
    NFA final_nfa(new NFAState(1000), new NFAState(1001));
    for (auto p : patrules) {
        auto nfa = compiler.compile(p.pattern);
        nfa.accept_string = p.token;
        nfa.token_no = p.number;    
        acceptStates.push_back(make_pair(nfa.token_no, nfa.accept));
        final_nfa.start->addTransition(Transition(nfa.start));
        nfa.accept->addTransition(Transition(final_nfa.accept));
       final_expr += p.pattern + '|';
    }
    final_expr.back() = ')';
    return make_pair(final_expr, final_nfa);
}

Once the loop completes the last character of the final_expr pattern is changed from an or operator to a close paren to finish the expression. We could theoretically stop here and use the powerset construction algorithm to simulate our NFA while matching our patterns. While certainly possible it's almost never done. I'm not saying there isn't a situation where that would be preferable to converting to a DFA, there very well may be, but i sure as heck cant think of one.

With that in mind, we're ready to convert the NFA to a DFA. I'm also going to reduce it to a minimal state DFA at the same time. While not stictly necessary minimizing the DFA has the potential to reduce the size of the final automata by quite a bit when you are reducing from an NFA with epsilon transitionsm, as one built with thompsons construction is bound to be. 

Combined NFA to DFA

As I mentioned asbove, lexical analysis is the only phase of compilation that looks at every single character of input. This means we want it to do its job absolutely as fast a possible. There are alot of ways to tokenize a string, but the most efficient way speed wise is with DFA.

    DFA dfa = makeDeterministic(nfa, final_expr, acceptStates);

Conversion of an NFA to a DFA is accomplished through the powerset construction algorithm. Having just recently covered making an NFA deterministic, I wont repeat it here. A full description of it's implementation is available here.

    DFA dfa = minimize(dfa, final_expr);

Every Regular Expression has a minimal state DFA that accepts it. That minimal state DFA is the most efficient from a space perspective. The process of reducing a DFA to its minimum state form is covered in its entirety here.

Some notes on reducing to minimal state DFA

In my previous post on minimizing DFA I seperated the initial partition based on if a state was accepting or not. In that post I mentioned that if using Moores algorithm on a DFA for a lexer that you need to seperate each accepting state into its own initial group. This initial partitioning is what will ultimately allow us to identify which token was being accepted by the minimal state DFA.

vector<set<int>> initGroups(DFA& dfa, map<int,int>& in_group) {
    vector<set<int>> groups= {{}};
    set<int> seen;
    for (int i = 0; i < dfa.num_states; i++) {
       if (!dfa.states[i]->accepts) {
            groups[0].insert(i);
            seen.insert(i);
            in_group[i] = 0;
       } else {
            groups.push_back(set<int>());
            groups[i].insert(i);
            in_group[i] = groups.size()-1;
       }
    }
    return groups;
}

The other portion of the DFA minimizing scheme which needs attention is during the rebuilding phase for the minimal state DFA. Care must be taken to properly map out the individual accepting states for each token. 

   for (int i = 0; i < result.num_states; i++) {
        int rep = *groups[i].begin();
        for (char c : alphabet) {
            if (dfa.states[rep]->trans.count(c)) {
                int ndst = in_group[dfa.states[rep]->trans[c]->label];
                if (ndst != -1) {
                    result.states[i]->trans[c] = result.states[ndst];
                }
            }
        }
        for (int os : groups[i]) {
            if (dfa.states[os]->accepts > 0) {
                result.states[i]->accepts = dfa.states[os]->accepts;
                break;
            }
        }
    }

Once we have our minimal state dfa, we can either serialize it for later use like tools such as lex or Flex do, or we can use the DFA as is. Either way, its ready for use tokenizing input. 

Maximal Munch

To recognize each token we want to use the "maximal munch" algorithm, which is a method for greedily matching the longest match until failure, at which point we return the last token recognized before failing. The string being tokenized is advanced by the length of the string being returned, and in this way it "maximally munches" the string by taking the biggest bites out of it as possible.

vector<pair<int,string>> lex_string(DFA& dfa, string str) {
    vector<pair<int,string>> tokens;
    for (int i = 0; i < str.size(); ) {
        auto[id, result] = matchDFA(dfa, str.substr(i));
        if (!result.empty()) {
            tokens.push_back(make_pair(id-1,result));
            i += result.size();
        } else {
            i++;
        }
    }
    return tokens;
}

The actual Matching is rather straight forward:

pair<int,string> matchDFA(DFA& dfa, string expr) {
    DFAState* state = dfa.states[0];
    string result;
    int last = -1;
    for (int i = 0; i < expr.size(); i++) {
        DFAState* next = nullptr;
        if (state->trans.find(expr[i]) != state->trans.end()) {
            next = state->trans[expr[i]];
        }
        if (next == nullptr) {
            break;
        } else state = next;
        if (state->accepts) {
            result = expr.substr(0, i+1);
            last = state->accepts;
        }
    }
    return make_pair(last,result);
}

And to tie it all together, this is what it looks like end to end:

void test() {
    vector<PatternTokenRule> patrules = {
                                          {"([A-Za-z][A-Za-z0-9]*)", "ID", 1},
                                          {"([0-9]+)", "NUMBER", 2}, 
                                          {"if", "IF", 3}, 
                                          {"print", "PRINT", 4}, 
                                          {"\\+","PLUS", 5}, 
                                          {"\\(","LPAR", 6}, 
                                          {"\\)","RPAR", 7}, 
                                          {"<","LESS",8} 
                                        };
    vector<pair<int,NFAState*>> acceptStates;
    auto [final_expr, nfa] = toNFA(patrules, acceptStates);
    DFA dfa = makeDeterministic(nfa, final_expr, acceptStates);
    string text = "if (1+1 < 3) print 42";
    auto tokens = lex_string(dfa, text);
    for (auto [id, result] : tokens) {
        if (!result.empty()) {
            cout<<"("<<patrules[id].token<<", "<<result<<")"<<endl;
        }
    }
}

Happy Hacking!

Further Reading

Aho, Sethi, Ullman Direct-to-DFA Construction

Thompsons Construction, RE to NFA

Moore DFA Minimization

---