Internals: Finite-State Machine Lexer

The first version of LIPS Scheme had regex based tokenizer. It was using a single regex to split the input string into tokens. In this article, I will show the internals of the new Lexer in LIPS Scheme.

You can still find the first version of what later become LIPS on CodePen:

• Simple Lisp interpreter in JavaScript

When I started working on version 1.0 (you can read this story in article: LIPS Scheme History), the code become more and more complex, the regular expression become dynamic, mostly because of syntax extensions that needed to update the regular expression and the tokenizer.

You can see this code on GitHub on old-version branch

function makeTokenRe() {
    var tokens = Object.keys(specials).map(escapeRegex).join('|');
    return new RegExp(`("(?:\\\\[\\S\\s]|[^"])*"|\\/(?! )[^\\/\\\\]*(?:\\\\[\\S\\s][^\\/\\\\]*)*\\/[gimy]*(?=\\s|\\(|\\)|$)|\\(|\\)|'|"(?:\\\\[\\S\\s]|[^"])+|\\n|(?:\\\\[\\S\\s]|[^"])*"|;.*|(?:[-+]?(?:(?:\\.[0-9]+|[0-9]+\\.[0-9]+)(?:[eE][-+]?[0-9]+)?)|[0-9]+\\.)[0-9]|\\.{2,}|${tokens}|[^(\\s)]+)`, 'gim');
}

At one point, I realized that I need to change my approach into parsing and tokenization, because you could not add new syntax extensions in the same file that contained the code. Because the whole code was tokenized at once.

Finite State Machine Lexer

The limitation of syntax extension lead into introducing a new Lexer and a Streaming Parser (if you're interested in this topic, I will be writing an article about this in the future).

The new Lexer is much simpler and easier to maintain, only had one bug recently related to Lexer inner working (#433).

The new Lexer is a class that have rules for the state machine (FSM), this is an example sequance of rules for a string:

Lexer.string = Symbol.for('string');
Lexer.string_escape = Symbol.for('string_escape');
...
Lexer._rules = [
    ...
    [/"/, null, null, Lexer.string, null],
    [/"/, null, null, null, Lexer.string],
    [/"/, null, null, Lexer.string_escape, Lexer.string],
    [/\\/, null, null, Lexer.string, Lexer.string_escape],
    [/./, /\\/, null, Lexer.string_escape, Lexer.string],
    ...
]

The single rule is consisted of a current character, next character, and a previous character (they can be single character strings or regular expressions). If the character is null, it can be any character. The last two elements of the array are the starting and the ending state (they are symbols, so they are unique values).

The Lexer start with null state and iterate over every rule on every character until it find a match. If a rule enters a state and the state finish with null, it means that the rule sequance was matched, and a full token is created.

If no rules match and the state is not null, then the characters are collected and will be included in a final token.

That's why in above example there are no rule like this:

[/./, null, null, Lexer.string, Lexer.string]

This rule may be added in the future to speed up the Lexer.

Example

When we have a string like this:

"foo\"bar"

It matches the second rule because the first character is a quote, so it enters Lexer.string state. The first rule doesn't match because the initial state is null. For characters foo it collects the tokens because no rule match them. When it finds slash \ it changes state from Lexer.string to Lexer.string_escape, and for the next character it enters again Lexer.string. Then it consumes a sequence of characters bar, and the last quote matches the first rule. And that's how we have the full token.

Syntax Extensions and Constants

The static rules are located in Lexer._rules, but Lexer.rules is a getter that create the final rules dynamically by adding all tokens added as syntax extensions (they are called specials in the code). This is also where other constats that starts with hash are added like: #t, #f, or #void. They are added together with syntax extension to handle the rules matching order.

As an optimization, the value of dynamic rules is cached, and the cache is invalidated when a new syntax extension is added.

The syntax extension create a lexer rule using Lexer.literal_rule that creates an array of rules that match literal characters in the token, passed as first character.

Lexer is important not only when it reads input LIPS Scheme code, it's also used when reading from I/O ports.

Conclusion

And that's it, this is the whole Lexer. As you can see reading the above, it's very simple, easy to maintain. If you want to look how it works for yourself. You can jump into the source code. And search for "class Lexer", "Lexer._rule", Object.defineProperty(Lexer, 'rules'.

The source code is in one file, so to navigate you need to use search. I've made an attempt to split the code into modules, but failed. Because of Rollup errors about circular dependencies.

This was the first part of articles about LIPS Scheme Internals.