Building a Lexer Framework Part 3 - Executing the state machine

In the last post we built a state machine from the lexer rules. Now we'll complete the lexer by implementing the algorithm to execute it.

The lexer vs the state machine

I have always talked as if the lexer was just the state machine, mainly because the NFA is the core of the lexer. However now that we enter into implementation, it's important to understand they work at different levels:

1. The lexer splits text into a list of tokens
2. The state machine finds a single token at the beginning of a text

So given const foo = 3, the lexer will give you ["CONST", "VAR(foo)", "EQ", "INTEGER(3)"] but the state machine will return just "CONST".

What I'm trying to explain in a really fancy way is that we need a new class for the lexer and that it will loop and call the state machine once per token.

The lexer

We'll have a class Lexer, which takes a list of token rules and calls buildLexerNFA, defined in the previous post. The class will have one method tokenize that transforms a string into a list of tokens. To do that it will call nextToken, the method that executes the NFA, passing it the full text and the position of the text in which it needs to start. Then it will store the token in the list of tokens and update the new position for the next call to nextToken.

It will keep doing this over and over until it either finishes tokenizing the text, or it finds unexpected text for the given lexer rules.

export class Lexer {
    lexerNfa: LexerNFA;

    constructor(tokenRules: TokenRule[], flags: LexerFlags = {}) {
        this.lexerNfa = buildLexerNFA(tokenRules)    
    }

    tokenize(text: string): Token[] {
        const tokens: Token[] = [];
        let pos = 0;
        while (pos < text.length) {
            const result = nextToken(this.lexerNfa, text, pos);
            // Guards against infinite loops. A regex like a* can generate an empty token, leading to an infinite loop.
            // Why an error and not just return? If pos < text.length then there is still text remaining, but if the longest token we can match is empty, 
            // then the remaining of the text is not tokenizable
            if (!result || result.endPos === pos) {
                throw new LexerError(pos, text);
            }
            tokens.push({
                type: result.token.name,
                text: text.substring(pos, result.endPos),
                start: pos,
                end: result.endPos,
            });
            pos = result.endPos;
        }
        return tokens;
    }

State Machine Execution

So let's get to the juicy part: The state machine. Unlike in regex, where we used backtracking, here it is not enough to find one path that leads to a final state. The lexer doesn't just return true or false, it needs to find the longest path that leads to a final state. You know, reverse Dijkstra... (okay not really don't kill me internet 😰)f

To understand the algorithm we need to take two important things into consideration

1. Quantic states

The state machine can be in multiple states at the same time, for example after consuming const the machine says it's both a CONST and an IDENTIFIER at the same time. The cat is dead and alive at the same time until it attempts to consume the next character, at that moment it is decided whether it's a CONST (if the next character wasn't a letter) or if it's an ID.

These tokens might not be related to AI, but they are quantic 😎

2. Epsilon Closure

As already spoiled by the image above, $\varepsilon$-transitions do not consume any characters. So if the machine is in a state like q5, that has an $\varepsilon$-transition to another state, let's say q6, then the state machine is both at q5 and q6 at the same time.

The set of states reachable from a given state by traversing $\varepsilon$-transitions is called the $\varepsilon$-closure. For example following the image above:

This property is transitive. If you have $q1 -\varepsilon-> q2 -\varepsilon-> q3$ then $\varepsilon-closure(q1) = \{q1, q2, q3\}$

This impacts the "quantic active states" in the machine. If the current active state is q16, then the machine is actually on $\varepsilon-closure(q16)$, which is q16, q17 and q18.

To calculate the $\varepsilon-closure$, we'll use this function:

export function epsilonClosure(states: Iterable<State>): Set<State> {
    const stack = [...states];
    const closure = new Set(states);
    while (stack.length) {
        const state = stack.pop() as State;
        for (const [matcher, toState] of state.transitions) {
            // Note: EPSILON is a constant defined in the matcher for epsilon transitions. 
            // To be precise "export const EPSILON = Symbol("epsilon");"
            // Symbol is used to ensure the object is unique
            if (!closure.has(toState) && matcher.matches(EPSILON)) {
                closure.add(toState);
                stack.push(toState);
            }
        }
    }
    return closure;
}

The main loop

Before entering into the main loop, we need to talk about another auxiliary function: bestAccepting. Remember that the lexer rules can be ambiguous and this ambiguity is resolved through the priority. Like most lexers, this one prioritizes the rules by the order in which they are defined.

Therefore, we need a method that resolves this ambiguity:

function bestAccepting(states: Iterable<State>, pos: number, tokenTypeByEndState: Record<string, TokenTag>): NextTokenResult | null {
    let winner: TokenTag | null = null;
    for (const state of states) {
        const tag = tokenTypeByEndState[state.name];
        if (tag && (winner === null || tag.priority < winner.priority)) {
            winner = tag;
        }
    }
    return winner ? { endPos: pos, token: winner } : null;
}

Great, now we can start the core loop. We'll start simply defining the initial state, which is simply the epsilon closure of the initial state of the NFA. We could have already precalculated this before, but for the sake of simplifying let's keep it here

export function nextToken(lexerNfa: LexerNFA, text: string, startPos: number): NextTokenResult | null {
    const { tokenTypeByEndState } = lexerNfa;

    let current = epsilonClosure([lexerNfa.states[lexerNfa.initialState]], startPos);

Then we are going to keep a variable with the best token candidate for the current states at each moment

    // We call bestAccepting already but the only case this value would be returned is if either:
    // 1. Nothing can be tokenized 
    // 2. The only thing that can be tokenized is a rule that generates an empty token
    // Both situations must end up returning an error in the lexer (in the tokenize method)
    let best = bestAccepting(current, startPos, tokenTypeByEndState);
    let pos = startPos;

And finally the loop: Given the next character try to traverse every transition of all of the current states. On each iteration update the current and the best token. Once we cannot consume any other character, return best:

  while (current.size > 0 && pos < text.length) {
        const char = text[pos];
        const nextStates = new Set<State>();
        for (const state of current) {
            for (const [matcher, toState] of state.transitions) {
                if (matcher.matches(char, pos)) {
                    nextStates.add(toState);
                }
            }
        }
        if (nextStates.size === 0) break;

        pos += 1;
        current = epsilonClosure(nextStates, pos);
        const candidate = bestAccepting(current, pos, tokenTypeByEndState);
        if (candidate) best = candidate;
    }

    return best;
}

As part of the best candidate we also need to return the position where it ended. This way, we can start the state machine again starting from that point during the next call to nextToken.

Lexer's context freedom

Since we are talking about the execution of the lexer, I want to take this opportunity to side-track and talk about backtracking, or rather why lexers do not have backtracking. Lexers follow two important properties:

1. Maximal munch: Which in layman terms means "always pick the longest token"
2. Context freedom: The lexer always splits the text in tokens following the lexer rules, without having any context of the parser wishes. If you have const 3 = 3 the lexer cannot say that the first 3 is an identifier while the second one is a number. It does not know the 3s are part of an expression, it just sees each 3 without any parser context.

This context freedom is obtained naturally by processing the text in a chain: First you tokenize, then you feed the tokens to the parser. The parser has no way to go back and say "wait can you try interpreting this in another way?".

This is on purpose and has multiple benefits, mainly a higher performance thanks to the NFA/DFA and cleaner grammars. But it also has it's drawbacks. For example, lexical ambiguities. If you have:

GREATER_THAN: '>';
RIGHT_SHIFT_BITWISE: '>>' 

Then the lexer will misinterpret situations like Java's generics: List<List<String>>. The maximal munch will cause >> to be tokenized as a right shift bitwise operator instead of two greater than symbol that is part of generics.

So how is this solved? There are two options:

1. Have only the lexer rule GREATER_THAN: '>' and keep the bitwise operator as a parser rule rightShiftBitOp: GREATER_THAN GREATER_THAN. Note that the parser usually ignores whitespaces, so it won't differentiate between 3 >> 2 and 3 > > 2, so it might require extra validations if you want to forbid the second case.
2. Break the context freedom. Yes, you heard it right, you are a free human being, programming in a turing complete language. The world is yours to take. The same way I tweaked my regex engine to turn it into a lexer engine, you can tweak the lexer engine to make it context aware.

In fact, there is a whole type of parser, called scannerless parsers, which perform tokenization and parsing in a single step. I have never used these kind of lexers but I hope to make a series of posts at some time.

So the lexer is over?

Did you really believe the answer could be yes? Oh boy. The lexer might be currently functional, but is it efficient? Well it's not horrible but it's definitively not good, specially if you compare it with ANTLR4's lexer

Here is my lexer vs ANTLR4 Claude generated comparison on several scenarios. I don't really trust Claude, but hey, it confirms what I expected so all hail the confirmation bias god.

I knew I wouldn't be able to compete against warm ANTLR4 (warm = with cached/precomputed data), but oh my god, in most cases it performed horribly even against cold ANTLR4 (cold = fresh start nothing cached).

I could explain what the scenarios explosion, keywords and epsilon mean, but that would be being a decent blogger. I need to keep you baited for those sweet sweet views (which actually don't give me money, but whatever 🤷‍♂️). I'll see you in the next post where we'll optimize the lexer and hopefully learn something in the process.