I ended my previous post with a click-bait that anyone with half a brain could have guessed: The lexer is done and it works, but it cannot compete with a battle-tested lexer like ANTLR4 , it's just too slow. But... why? I built it by following the theory in the books, so what am I missing? What black magic are they doing? I wanted to understand and hopefully close the gap, at least a little.

Unlike previous posts, I won't dig into the code and keep it as a conceptual explanation. After all you can just tell Claude to do it . Daniel you just asked Claude to do it and didn't bother enough to clean it up for the blog post shut up Claude don't reveal my secrets, just keep generating tokens stochastically so that other people's Claude can read it, build a lexer and no human ever learns how to build one 😭

My first naive approach was to "clean"/optimize the NFA, and it's the one I will focus on this blog post. ANTLR4 actual solution is much more complex and transforms the NFA into a DFATo read more about the differences between NFA and DFA, read NFA vs DFA.. I would love to cover that topic in a future post.

Optimization 1: Removing repeated prefixes

The current algorithm to build a lexer is essentially combining multiple regexes by "brute force". Yes, that is a figure of speech Mr Nitpicker Programmer, it's not a brute force algorithm but it's clumsy and inefficient.

For example if a lexer a token kw_1 and a token kw_2, then the final "regex"Between quotes because even though the NFA is similar to the one of a regex, it's still a lexer, not a regex is kw_1|kw_2. However, as you probably have already guessed, it would be better fused into kw_(1|2). This regex would have less states, and also doesn't need to keep track of parallel active states.

If we exaggerate this use case:

This optimization can be done at two points in time:

1. On the spot, when building the regex: If you have kw_2, the algorithm could check if it can follow an already existing k transition from the initial state, then to w, to _ and finally to 2. In this case there is no 2 transition so it would create a branch at that point.
   • This might sound really simple, but it get's more complex when dealing with quantifiers (*|+) or the | (OR) operator.
   • Note: I haven't checked this solution is actually feasible, but it seems like an intuitive solution and I assume it should be faster to execute than the post-processing.
2. Post-processing: After building the unoptimized regex with Thompson's construction, process it to build a second optimized NFA.
   • This is the approach Claude I took, for simplicity. But for a production grade lexer I might have prioritized the building speed.

Post-processing algorithm

The post-processing would work like this:

1. Visit every state, starting from the initial state. If multiple states can be reached from the same (repeated) transition AND they aren't reached by any other transition, they are considered "twins": they are always alive at the same time.
2. When there is a "twin", merge them by deleting one and moving the deleted's outward transitions to the remaining one.
   • If one or both of the twins are an end-state, the remaining state points to the highest priority token of the two.
3. The survivor state now holds all the twins' transitions, so its children may be new twins. So we need to repeat the process again, until no new merge is done

The benchmark

As every benchmark, specially if it's an AI benchmark, we are going to cherry-pick the worst-case scenario so that it looks like our optimization was extremely useful. If you want to learn more about marketing you can do my 20k$ master class. There are a lot of yachts, expensive cars and watches in the videos.

I am going to follow the example above, with a variable number of keywords. N keywords with the regex are kw_n (where n is an incrementing number from 0 to n-1)

Without further ado, here is the data, turned into a diagram by our friendly neighbourhood Claude

I can't wait to put on my CV that I optimized my regex to achieved a 97.6% speed gain and a state on a 200 keyword prefix test for NFA lexers. Hopefully they don't see that it's still an order of magnitude slower than ANTLR4.

Optimization 2: Useless Thompson stuff

The previous optimization focused on improving how different token regex are combined, and this time, we are focusing on combining each individual regex. The current lexer is doing a by-the-book conversion from regex to NFA, and it pays the price.

Don't get me wrong, Thompson's construction is great, and it works for all cases, but precisely because of that generalization it needs to create "gluable" expressions, which leads to unnecessary states and transitions. For example the epsilon transitions at the start and end of every subexpression:

To be completely precise, the previous optimization—the removal of common prefixes—As Descartes' famous quote says: I use em-dashes, therefore I AImalready took care of the entry glue, as it is an implicitImplicit from a human perspective, because we don't see epsilon transitions in words prefix.

To implement the Exit Glue —as I mentioned before the Entry Glue is already implemented as part of the previous optimization—I used the em dashes again, just to bother you. In fact I'm not sure if it's a correct use of the em dashes 🤷‍♂️, simply do the previous optimization in "reverse":

incoming = map that for each state contains the edges that point at it

for each state S:
    if S is not a finishing state ,
       and S has exactly one outgoing edge, an epsilon to a different state T:
        for each edge E in incoming[S]:
            make E point at T instead
        if S was the start state:
            T becomes the start state
        delete S

All of these transformations might lead to duplicates and redundant epsilon transitions, which we can also clean

To remove duplicates:

for each state S:
    seen = empty set
    for each edge E leaving S:
        if E is an epsilon edge that goes back to S:
            drop E
        else if (what E accepts, where E goes) is already in seen:
            drop E
        else:
            add it to seen and keep E

And to **drop redundant epsilons**Epsilon edge when its target can already be reached from its source using other epsilon edges.

for each state S:
    for each epsilon edge E from S to T:
        reachable = everything reachable from S using only
                    epsilon edges, not counting E
        if T is in reachable:
            drop E

The benchmark, again

Just as before, we are going to cherry-pick one use case plus a general use case

• lan: N plain keywords with different prefixes, plus an identifier, a number and whitespace. This is what a typical language looks like.
• glue: N rules of the form word(x|y|z)*(p|q)?, so every rule carries its own alternations and star, and therefore its own glue.

For N = 3 the rules are these. Every word is the same shape, six random letters followed by the rule number as four digits, so the size of a word never changes as N grows:

lang                         glue
KW0  gxpybw0000              R0  glsdbi0000(x|y|z)*(p|q)?
KW1  jbbzzn0001              R1  yodisq0001(x|y|z)*(p|q)?
KW2  lopuuk0002              R2  igzosn0002(x|y|z)*(p|q)?
ID   [a-z][a-z0-9]*          ID  [a-z][a-z0-9]*
NUM  [0-9]+                  WS  " +"
WS   " +"

Honestly much more impressive than what I was expecting. However, it's still not ANTLR4.

The end (for now?)

Is that all? Are we condemned to always be one step behind ANTLR4? Does Terence ParrCreator of ANTLR know dark secrets that we, mere peasants, are not allowed to see? Maybe, but the optimizations in this posts were quite naive.

There are many complex improvements that could be done: From caching epsilon closures to the biggest one: Using a DFA, whether static (preprocess the NFA to a DFA and run the DFA) or dynamic (build the DFA as the lexer traverses the NFA).

I hope I am able to continue talking about these optimizations, although I barely have time and I have other projects I would like to work on. Who knows.

See Slop you in the next post!