Writing a Lexer: From Characters to Tokens with a Bookstore Filter Language in C#

Version note: The code in this post was built with .NET 10 (SDK 10.0.404) and verified with xUnit v3 4.0.3 tests; the Roslyn sample was run with Microsoft.CodeAnalysis.CSharp 5.12.0.

Guess First

We are building the first stage of the filter language we write for Bookstore, the online bookstore used as the shared example across this site's series. Two questions. First: the text price<=300 has no spaces at all. How many tokens does the lexer split it into; do < and = come out separately, or as a single <=?

Second: to make keywords case-insensitive, the lexer lowercases the word with ToLower() and compares it with "contains". The application runs on Turkish Windows, with the tr-TR culture. When a user types TITLE CONTAINS "Dune", is CONTAINS recognized as a keyword?

Tokens, Lexemes and Token Kinds

A lexer's job is to split a sequence of characters into meaningful pieces. Each piece has two faces. The lexeme is the characters as they were written in the source: "Jane Austen", quotes included. The token is that lexeme's kind and value: a token of kind String whose value is Jane Austen. The parser works with token kinds, not lexemes; to the parser, 300 and 49.90 are the same thing, both a Number.

In our language the token kinds fall into four groups: identifiers (field names), literals (numbers, strings, true/false), keywords (and, or, not, contains) and operators or punctuation (<=, (). We add two special kinds: EndOfInput, which says the input is over, and Bad, for characters that cannot be recognized.

namespace Bookstore.Filter.Syntax;

public enum TokenKind
{
    EndOfInput,
    Bad,

    Identifier,
    Number,
    String,

    // keywords
    And,
    Or,
    Not,
    Contains,
    True,
    False,

    // operators and punctuation
    Equal,
    NotEqual,
    Less,
    LessOrEqual,
    Greater,
    GreaterOrEqual,
    OpenParen,
    CloseParen,
}

namespace Bookstore.Filter.Syntax;

public readonly record struct SourcePosition(int Line, int Column)
{
    public override string ToString() => $"{Line}:{Column}";
}

// Text is the lexeme exactly as written; Value is the parsed literal (decimal, string, bool) or null.
public readonly record struct Token(TokenKind Kind, string Text, object? Value, SourcePosition Position);

public sealed record Diagnostic(SourcePosition Position, string Message)
{
    public override string ToString() => $"error at {Position}: {Message}";
}

Every token carries its position (line and column). The cost is small and the payoff is large: the parser, the type checker and even a problem found while generating SQL can only tell the user "at this column" because of it. Instead of throwing errors as exceptions, we collect them in a Diagnostic list, so a single pass can report several errors.

A Lexer Is a State Machine

Thinking of the lexer as a state machine that moves one character at a time makes the job easier. In the start state you look at the next character: a letter takes you to the "reading an identifier" state, a digit to "reading a number", a quote to "reading a string". Inside the string state a backslash opens a sub-state (the escape). When the character that leaves the state arrives, the token is done and you go back to the start. In a hand-written lexer, these states become separate methods:

public ref struct Lexer
{
    private static readonly FrozenDictionary<string, TokenKind> Keywords =
        new Dictionary<string, TokenKind>
        {
            ["and"] = TokenKind.And,
            ["or"] = TokenKind.Or,
            ["not"] = TokenKind.Not,
            ["contains"] = TokenKind.Contains,
            ["true"] = TokenKind.True,
            ["false"] = TokenKind.False,
        }.ToFrozenDictionary(StringComparer.OrdinalIgnoreCase);

    private static readonly FrozenDictionary<string, TokenKind>.AlternateLookup<ReadOnlySpan<char>> KeywordLookup =
        Keywords.GetAlternateLookup<ReadOnlySpan<char>>();

    private readonly ReadOnlySpan<char> _text;
    private readonly List<Diagnostic> _diagnostics;
    private int _pos;
    private int _line = 1;
    private int _lineStart;

    public Lexer(ReadOnlySpan<char> text, List<Diagnostic> diagnostics)
    {
        _text = text;
        _diagnostics = diagnostics;
    }

    public Token Next()
    {
        SkipWhitespaceAndComments();
        int start = _pos;
        SourcePosition position = Position(start);
        if (_pos >= _text.Length)
            return new Token(TokenKind.EndOfInput, "", null, position);

        char c = _text[_pos];
        switch (c)
        {
            case '(': return Take(1, TokenKind.OpenParen, start, position);
            case ')': return Take(1, TokenKind.CloseParen, start, position);
            case '=': return Take(1, TokenKind.Equal, start, position);
            // maximal munch: the longer operator is tried first
            case '<' when Peek(1) == '=': return Take(2, TokenKind.LessOrEqual, start, position);
            case '<': return Take(1, TokenKind.Less, start, position);
            case '>' when Peek(1) == '=': return Take(2, TokenKind.GreaterOrEqual, start, position);
            case '>': return Take(1, TokenKind.Greater, start, position);
            case '!' when Peek(1) == '=': return Take(2, TokenKind.NotEqual, start, position);
            case '"': return ReadString(start, position);
        }

        if (char.IsAsciiDigit(c))
            return ReadNumber(start, position);
        Rune.DecodeFromUtf16(_text[_pos..], out Rune rune, out int consumed);
        if (Rune.IsLetter(rune) || c == '_')
            return ReadIdentifierOrKeyword(start, position);

        // unknown character: report it and skip the whole code point, so recovery always makes progress
        _pos += Math.Max(consumed, 1);
        string hint = c == '!' ? " (did you mean '!='?)" : "";
        Error(position, $"unexpected character '{rune}' (U+{rune.Value:X4}){hint}");
        return Make(TokenKind.Bad, start, position);
    }
}

The lexer is a ref struct and holds the text as a ReadOnlySpan<char>. It moves left to right in a single pass, never goes back and looks ahead at most one character (Peek(1)). It reads parts of the source through slices without copying them into separate strings; it converts to a string only once, for the token's Text. We do not even create a string to find a keyword: GetAlternateLookup<ReadOnlySpan<char>>(), added in .NET 9, searches the FrozenDictionary with the span directly.

The answer to the first guess is in the switch. When we see < we first look at the next character; if it is = we take both characters and produce LessOrEqual. This rule is called maximal munch: the lexer always takes the longest token that can match. price<=300 is three tokens; < and = are not separate. The same rule applies to identifiers: the word android starts with the keyword and, but since the lexer reads to the end of the word it comes out as a single identifier.

Identifiers, Keywords and Unicode

private Token ReadIdentifierOrKeyword(int start, SourcePosition position)
{
    bool asciiOnly = true;
    while (_pos < _text.Length)
    {
        // decode a whole code point: a letter outside the BMP is two chars (a surrogate pair)
        Rune.DecodeFromUtf16(_text[_pos..], out Rune rune, out int consumed);
        if (!Rune.IsLetterOrDigit(rune) && rune.Value != '_')
            break;
        asciiOnly &= rune.IsAscii;
        _pos += consumed;
    }

    ReadOnlySpan<char> word = _text[start.._pos];
    if (!asciiOnly)
    {
        Error(position, $"field name '{word}' must use ASCII letters only");
        return Make(TokenKind.Bad, start, position);
    }
    if (!KeywordLookup.TryGetValue(word, out TokenKind kind))
        return Make(TokenKind.Identifier, start, position);

    object? value = kind switch
    {
        TokenKind.True => true,
        TokenKind.False => false,
        _ => null,
    };
    return new Token(kind, word.ToString(), value, position);
}

Our field names are English and ASCII. So what should happen when a user types başlık, Turkish for "title"? The first version of the lexer treated only ASCII letters as identifiers and produced this:

$ dotnet run --project src/Bookstore.Filter.Cli -- tokens 'başlık = "Dune'
1:1    Identifier      ba
1:3    Bad             ş
1:4    Identifier      l
1:5    Bad             ı
1:6    Identifier      k
1:8    Equal           =
1:10   String          "Dune            "Dune"
1:15   EndOfInput
error at 1:3: unexpected character 'ş' (U+015F)
error at 1:5: unexpected character 'ı' (U+0131)
error at 1:10: unterminated string literal

Technically correct, meaningless to the user: a single word turned into five tokens and two errors. The version above reads the word to its end using Unicode letter rules and gives one clear error:

$ dotnet run --project src/Bookstore.Filter.Cli -- tokens 'başlık = "Dune'
1:1    Bad             başlık
1:8    Equal           =
1:10   String          "Dune            "Dune"
1:15   EndOfInput
error at 1:1: field name 'başlık' must use ASCII letters only
error at 1:10: unterminated string literal

We read characters as Rune instead of char because of UTF-16. A char is 16 bits; some characters, such as mathematical letters or emoji, are stored as a surrogate pair of two chars. Pass half of a pair to char.IsLetter on its own and you get false, and error recovery continues from the middle of a character. Unicode and surrogate pairs are covered in detail in the "Unicode and UTF-8/UTF-16" post of the Number Systems series.

Keyword comparison uses StringComparer.OrdinalIgnoreCase, and the answer to the second guess is here. ToLower() uses the current culture, and in Turkish the lowercase of capital I is the dotless ı:

CultureInfo turkish = new("tr-TR");
Console.WriteLine("CONTAINS".ToLower(turkish));
Console.WriteLine("CONTAINS".ToLower(turkish) == "contains");

contaıns
False

A lexer written with ToLower() does not recognize CONTAINS on Turkish Windows but does on an English machine. A bug like that never shows up on the developer's machine. Ordinal comparison does not depend on the culture; in the tests we deliberately set CurrentCulture to tr-TR and verify that keywords are still recognized.

Numbers, Strings and Comments

private Token ReadNumber(int start, SourcePosition position)
{
    while (_pos < _text.Length && char.IsAsciiDigit(_text[_pos]))
        _pos++;

    if (Peek(0) == '.')
    {
        _pos++;
        if (!char.IsAsciiDigit(Peek(0)))
        {
            Error(Position(_pos), "expected a digit after '.'");
            return Make(TokenKind.Bad, start, position);
        }
        while (_pos < _text.Length && char.IsAsciiDigit(_text[_pos]))
            _pos++;
    }

    ReadOnlySpan<char> lexeme = _text[start.._pos];
    // the language always uses '.' as the decimal separator, whatever the current culture is
    if (!decimal.TryParse(lexeme, NumberStyles.AllowDecimalPoint, CultureInfo.InvariantCulture, out decimal value))
    {
        Error(position, $"number '{lexeme}' is out of range");
        return Make(TokenKind.Bad, start, position);
    }
    return new Token(TokenKind.Number, lexeme.ToString(), value, position);
}

InvariantCulture is not decoration here. In tr-TR the dot is the thousands separator; decimal.Parse("49.90", new CultureInfo("tr-TR")) returns 4990 without any error. A filter that says price < 49.90 would compare against a number a hundred times larger, and nobody would notice. The "How Floating Point Works" post of the Number Systems series covers how numbers are represented; the rule here is simple: a language's syntax cannot depend on the machine's language settings.

private Token ReadString(int start, SourcePosition position)
{
    StringBuilder value = new();
    _pos++; // opening quote
    while (true)
    {
        if (_pos >= _text.Length || _text[_pos] == '\n')
        {
            Error(position, "unterminated string literal");
            return new Token(TokenKind.String, _text[start.._pos].ToString(), value.ToString(), position);
        }

        char c = _text[_pos];
        if (c == '"')
        {
            _pos++;
            return new Token(TokenKind.String, _text[start.._pos].ToString(), value.ToString(), position);
        }

        if (c == '\\')
        {
            char next = Peek(1);
            if (next is '"' or '\\')
            {
                value.Append(next);
                _pos += 2;
                continue;
            }
            if (next is '\0' or '\n')
            {
                _pos++; // the next iteration reports the unterminated string
                continue;
            }
            Error(Position(_pos), $"unknown escape sequence '\\{next}'");
            _pos += 2;
            continue;
        }

        value.Append(c);
        _pos++;
    }
}

We made two decisions while reading strings. First, a line break ends the string: an unclosed quote should not swallow the rest of the input, and the error should stay on that line. Second, we return a String token even for an unterminated string. That way the parser does not produce a second "expected a value" error; the user sees a single message pointing at the right place. The error position is the position of the opening quote, because that is where the user will fix it.

Whitespace and comments starting with # do not produce tokens. SkipWhitespaceAndComments updates the line counter while skipping them; that is where the position information comes from:

private void SkipWhitespaceAndComments()
{
    while (_pos < _text.Length)
    {
        char c = _text[_pos];
        if (c == '\n')
        {
            _pos++;
            _line++;
            _lineStart = _pos;
        }
        else if (char.IsWhiteSpace(c))
        {
            _pos++;
        }
        else if (c == '#')
        {
            // comment runs to the end of the line
            while (_pos < _text.Length && _text[_pos] != '\n')
                _pos++;
        }
        else
        {
            return;
        }
    }
}

private readonly SourcePosition Position(int index) => new(_line, index - _lineStart + 1);

Running and Testing It

$ dotnet run --project src/Bookstore.Filter.Cli -- tokens 'price <= 300 and author = "Jane Austen"'
1:1    Identifier      price
1:7    LessOrEqual     <=
1:10   Number          300              300
1:14   And             and
1:18   Identifier      author
1:25   Equal           =
1:27   String          "Jane Austen"    "Jane Austen"
1:40   EndOfInput                       

We pin the lexer's behavior down with xUnit tests. Two of them target risks specific to lexers: keywords must also be recognized under the Turkish culture, and error recovery must never loop forever on any input. The second one checks, with 1,000 randomly generated inputs, that the lexer always reaches EndOfInput and never produces more tokens than there are characters:

[Fact]
public void Tokenize_Keywords_AreCaseInsensitive_EvenUnderTurkishCulture()
{
    CultureInfo previous = CultureInfo.CurrentCulture;
    try
    {
        CultureInfo.CurrentCulture = new CultureInfo("tr-TR");
        Assert.Equal([TokenKind.Identifier, TokenKind.Contains, TokenKind.String, TokenKind.EndOfInput],
            Kinds("TITLE CONTAINS \"Dune\""));
    }
    finally
    {
        CultureInfo.CurrentCulture = previous;
    }
}

[Fact]
public void Tokenize_Garbage_AlwaysTerminates()
{
    Random random = new(42);
    for (int i = 0; i < 1_000; i++)
    {
        char[] chars = [.. Enumerable.Range(0, 50).Select(_ => (char)random.Next(0, 0xD7FF))];
        List<Token> tokens = Lexer.Tokenize(chars).Tokens;
        Assert.Equal(TokenKind.EndOfInput, tokens[^1].Kind);
        Assert.True(tokens.Count <= chars.Length + 1);
    }
}

$ dotnet test --project tests/Bookstore.Filter.Tests
Test run summary: Passed!
  total: 17
  failed: 0
  succeeded: 17
  skipped: 0
  duration: 335ms

The solution's test project uses the xUnit v3 package that runs on Microsoft Testing Platform; the "test": { "runner": "Microsoft.Testing.Platform" } line in global.json routes the dotnet test --project command to that runner.

A Lexer With a Regex: When Is It Enough?

"Couldn't we write this with a regex?" is a fair question. For simple languages you often can. A named group for each token kind, with alternation between them:

static partial class NaiveLexer
{
    [GeneratedRegex("""(?<ws>\s+)|(?<number>\d+(\.\d+)?)|(?<string>"[^"]*")|(?<op><=|>=|!=|[<>=()])|(?<word>[A-Za-z_]\w*)""")]
    public static partial Regex Token();
}

$ dotnet run --project samples/RegexLexer
price <= 300 and author = "Jane Austen"    => word:price  op:<=  number:300  word:and  word:author  op:=  string:"Jane Austen"
title = "The \"Hobbit\""                   => word:title  op:=  string:"The \"  word:Hobbit  string:""
title = "Dune                              => word:title  op:=  word:Dune

The first line is flawless; because we put <= before [<>=()] in the alternation, even maximal munch is right. On the second line the escaped quote split the string in two and produced meaningless tokens. The third line is worse: Matches silently skips characters that do not match, so the unclosed quote vanished without any error and Dune became a field name. All of these can be fixed: a more complex pattern for escapes, a check for gaps between matches to find unmatched ranges, extra code that counts line breaks for positions. Once you add them, you have a regex that is harder to read than the hand-written lexer, with a lexer around it.

The practical rule: if the input is trusted, the tokens are regular and error messages do not matter (splitting a log line, say), a regex is enough. If users type the input, if you need an error position and a clear message, or if there are rules that need context, such as string escapes and nested comments, a hand-written lexer gets correct sooner. How regexes match and what backtracking costs is covered in the Regular Expressions series.

Why Doesn't Roslyn's Lexer Throw Away Whitespace?

Our lexer throws away whitespace and comments; we do not need them to run a filter. Roslyn, the C# compiler, throws away no characters at all. It attaches whitespace, line breaks and comments to tokens as trivia: what comes before a token is leading trivia, what follows it is trailing trivia. This is easy to see with the Microsoft.CodeAnalysis.CSharp package:

string code = """
    // cheap books only
    var cheap=books.Where( b=>b.Price<300m );   /* TRY */

    """;

foreach (SyntaxToken token in SyntaxFactory.ParseTokens(code))
{
    string leading = string.Join(",", token.LeadingTrivia.Select(t => t.Kind()));
    string trailing = string.Join(",", token.TrailingTrivia.Select(t => t.Kind()));
    Console.WriteLine($"{token.Kind(),-22} {token.Text,-8} leading=[{leading}] trailing=[{trailing}]");
}

SyntaxTree tree = CSharpSyntaxTree.ParseText(code);
SyntaxNode root = tree.GetRoot();
Console.WriteLine($"round-trip equal: {root.ToFullString() == code}");
Console.WriteLine("normalized:");
Console.WriteLine(root.NormalizeWhitespace().ToFullString());

$ dotnet run --project samples/RoslynTrivia
IdentifierToken        var      leading=[SingleLineCommentTrivia,EndOfLineTrivia] trailing=[WhitespaceTrivia]
IdentifierToken        cheap    leading=[] trailing=[]
EqualsToken            =        leading=[] trailing=[]
IdentifierToken        books    leading=[] trailing=[]
DotToken               .        leading=[] trailing=[]
IdentifierToken        Where    leading=[] trailing=[]
OpenParenToken         (        leading=[] trailing=[WhitespaceTrivia]
IdentifierToken        b        leading=[] trailing=[]
EqualsGreaterThanToken =>       leading=[] trailing=[]
IdentifierToken        b        leading=[] trailing=[]
DotToken               .        leading=[] trailing=[]
IdentifierToken        Price    leading=[] trailing=[]
LessThanToken          <        leading=[] trailing=[]
NumericLiteralToken    300m     leading=[] trailing=[WhitespaceTrivia]
CloseParenToken        )        leading=[] trailing=[]
SemicolonToken         ;        leading=[] trailing=[WhitespaceTrivia,MultiLineCommentTrivia,EndOfLineTrivia]
EndOfFileToken                  leading=[] trailing=[]
round-trip equal: True
normalized:
// cheap books only
var cheap = books.Where(b => b.Price < 300m); /* TRY */

The output shows three things. First, the tree can give back the source text character for character (round-trip equal: True). That is why formatters, refactorings and code fixes can work on the Roslyn tree: a refactoring that renames a method must not touch the comments and alignment in the rest of the file. NormalizeWhitespace() formats the code by rewriting only the trivia. Second, a comment is part of a token; // cheap books only is the leading trivia of var. Third, var is an IdentifierToken. In C#, var is a contextual keyword; whether it is a type name or means "infer the type" is decided by later stages, not by the lexer. The lexer looks at words; it does not know meaning.

In Production

The lexer is the first code that touches user input; put an upper limit on the input length. Our lexer runs in linear time, but the token list it produces and the work of the later stages grow with the input. We will put that limit in front of the whole pipeline in post 04.

Error messages are an API contract. The text error at 1:9: unterminated string literal shown to users ends up in documentation, screenshots and even client-side code over time. Pin the message format down with tests and treat changing it as a breaking change.

When you report positions as line and column, decide what a column counts. Our lexer counts UTF-16 code units; a tab is one column, an emoji is two. Editors usually count differently. If the reported position and the one the user sees disagree, this is the first place to look.

Common Pitfalls

Forgetting maximal munch. A switch that checks the short operator first splits <= into < and =, and the parser then reports a meaningless "unexpected =". For multi-character operators, always try the longer one first.

Comparing keywords with ToLower() or ToUpper(). Under the Turkish culture the I and i conversions are different. Use ordinal or OrdinalIgnoreCase comparison.

Treating Unicode as char. Looking at surrogate pairs one half at a time drops error recovery into the middle of a character. Make the decision at the Rune level.

Error recovery that does not move forward. A lexer that adds an error for an unknown character but forgets to advance _pos spins on that character forever. The rule is simple: every path through Next() must either consume at least one character or return EndOfInput. A test with random input protects that rule.

A Small Experiment

★☆☆ Add support for <> next to != (as in SQL). Given maximal munch, what order should the < cases be in? Write a test for price<>300.

★★☆ Add escapes of the form \n and \u00E7 to strings. Where should the error position be for an invalid \u sequence? Show with a test that the lexer still continues from the right position after the error.

★★★ Add nested comments of the form /* ... */ (/* a /* b */ c */ should be a single comment). Explain why you cannot do this with a plain regex; add a counter to your lexer and report the opening position of an unclosed comment.

The tokens are ready, but price < 300 and author = "Jane Austen" is still a flat list. In the next post we derive a recursive descent parser from the grammar, move operator precedence into a table with Pratt parsing, build the AST with C# records and write a tree-walking interpreter that runs it directly.