Building a Lexer Framework Part 2

In the previous post I explained the basics of how we are going to build a lexer library, which can be grossly oversimplified in two steps:

Transforming a set of lexer rules (aka a list of regex) into a single NFA (non-deterministic finite automaton)
Implementing the executor for the NFA state machine

Yes that explanation was more compressed than a black hole, if it felt like chinese you might want to re-read the introduction

(To avoid the rage of AI bros I must remind you that this topic has nothing to do with AI. Lexer tokens are for formal languages, AI tokens are for LLMs and they follow different mechanisms)

The goal

The user of our lexer library must be able to define lexer rules in plain typescript. For simplification I'll use a list of <token type name, regex> pairs.

const lexerRules = [
    ["CONST",  "const"],
    ["EQ", "="],
    ["NUMBER", "\\d+"], 
    ["IDENTIFIER", "[a-zA-Z]\\w*"], 
    ["ADD", "[+]"],
    ["WS", " +"]  // Whitespace (for simplification I won't enter in the different types of whitespaces)
];

In case of ambiguity, the first defined rule will win, so const is a CONST not an IDENTIFIER.

You might be wondering why I didn't use a Map. The answer is extremely simple: I already used this data structure in the introduction post, even if I don't remember why. So now I have to stick with it 🤦‍♂️

Of course another option would be to give the user a fancy Domain Specific Language (DSL) to define the rules, like most lexers do. Something like:

CONST: 'const';
EQ: '=';
NUMBER: \d+;
IDENTIFIER: [a-zA-Z]\w*;
ADD: '+'; 
WS: ' '+; // Whitespace (for simplification I won't enter in the different types of whitespaces)

but for this series of posts I'll avoid it to keep the focus on the lexer. If you are interested on it, there are already a million ANTLR4 tutorials online, including my favourite one from Gabriele Tomassetti.

Internally I'll use this interface

export interface TokenRule {
    name: string;
    pattern: string;
}

Given a list of these the library will build the following state machine:

If you have read my series on the Regex Engine, you will be able to notice that this machine is simply a state q0 that is attached to the state machines generated by each regex. For example q1-q6 is the machine for the regex const. q7-q8 is just =, q10-q12 is \d+, etc

What we already have

Given that the state machine is a combination of multiple regex machines, I am going to reuse the classes and methods I developed for the Regex Engine. I'll mention the interfaces here so you can follow along, but not talk about their implementation. If you want you can always read it from the Regex Engine posts (I know I mention them every 3 paragraphs 🙈)

The state machine model

Let's start with the model for a NFA (non-deterministic finite automaton). There are different ways of modelling a state machine, but at its core is simply a set of states. In this case for convenience I will keep a record/map of the name -> State and also keep the initialState and endingStates as part of the NFA, but it would also be possible to add that information as attributes inside the State object.

export class NFA {
    states: Record<string, State>;
    initialState: string | null;
    endingStates: string[] | null;
}

The class above is the core of the NFA that I made for Regex, but for the lexer I need to add a small extra detail: The mapping final state -> token type. In the machine above this will determine that if the machine ends at q12 the token is a number, but if it ends on q23 it's a whitespace.

export class LexerNFA extends NFA {
    tokenTypeByEndState: Record<string, TokenTag>;
}

export interface TokenTag {
    name: string;
    // We need to keep track of the priority to resolve ambiguity when the same token matches two rules. For example "const" is a constant and not an identifier
    priority: number;
}

Now, a state is nothing more than the name and it's transitions. And a transition is what I've called a Matcher, which is a condition that determines if the state machine is able to follow the transition to another State by (potentially) consuming a character. There is a type of transitions, visualized $\varepsilon$ that does not consume any characters.

export class State {
    name: string;
    transitions: Array<[Matcher, State]>;
}

The regex builder

In order to transform a regex string into it's state machine I'm going to use the following already existing code. As I always say, if you aren't interested in the specifics of Regex feel free to treat this as an abstraction.

const stateNamer = createStateNamer("q"); // "q" is the prefix. States will be q0, q1, q2...
const cb = new ConversionBuilder(() => new EngineNFA(), stateNamer);
const ruleNfa = cb.regexToNFA(rule.pattern);

Note: This creates an EngineNFA which is a NFA on steroids that allows more advanced functionality for regex, like capturing groups, anchors (^ and $), etc. The executor engine, however, will not implement this functionality, since it is not relevant for lexers

Great, with the goal in mind and the pieces ready, let's build this thing!

We have the building blocks for the state machine

Building the machine

We'll begin with something as simple as creating the machine and adding the initial state q0

export function buildLexerNFA(tokenRules: TokenRule[]): LexerNFA {
    const lexerNFA = new LexerNFA();
    const stateNamer = createStateNamer("q"); // "q" is the prefix. States will be q0, q1, q2...

    const start = stateNamer.next();
    lexerNFA.addState(start);
    lexerNFA.setInitialState(start);

Great! Now we need to iterate through each of the lexer rules and:

Turn the regex into a substate machine
Connect the start of the lexerNFA (q0) to the start of the substate machine
Declare the end state of the substate machine as an end state of the lexerNFA and annotate the token type

    const cb = new ConversionBuilder(() => new EngineNFA(), stateNamer); // regex text -> regex nfa

    tokenRules.forEach((rule, priority) => {
        // 1. Get the nfa of a regex
        const ruleNfa = cb.regexToNFA(rule.pattern);

        // 2. Connect the start of the lexerNFA (`q0`) to the start of the substate machine
        lexerNFA.addTransition(start, ruleNfa.initialState as string, new CharacterMatcher(EPSILON));

        // 3.1 Declare the end state of the substate machine as an end state of the lexerNFA 
        for (const stateName in ruleNfa.states) {
            lexerNFA.states[stateName] = ruleNfa.states[stateName];
        }

        //  3.2 and annotate the token type
        for (const endState of ruleNfa.endingStates as string[]) {
            lexerNFA.tokenTypeByEndState[endState] = { name: rule.name, priority };
        }
    });

    lexerNFA.setEndingStates(Object.keys(lexerNFA.tokenTypeByEndState));
    return lexerNFA;
};

Note this code assumes that cb.regexToNFA always generates a unique state name, otherwise they would collide. The StateNamer class ensures this constraint is followed

And that's it?

Yes, it was quite easy, wasn't it? I've spent more time explaining what we wanted to do and what we already had than the actual change. Of course, there are a lot of potential improvements to be made. Some lexers rely on DFA (Deterministic Finite Automaton) that takes more space but it's faster to execute, the classical trade-off.

If you want to know more about NFA vs DFA, you guessed it, I have a post about it. It is more focused on how it affects Regex Engines, but parts of it also apply to any use of state machines.

And in the next post we'll build the code that will actually execute this machine. Can't wait!

Season 3 - Building a Lexer Framework (In Progress)