Lexing Overview

At the beginning of compilation, a program is only a sequence of characters:

answer := left + 22

Thinking about that program one character at a time quickly becomes inconvenient. The parser does not care about the a, n, s, w, e, and r individually. It cares that the complete word answer is an identifier.

The lexer groups and classifies the characters into a stream resembling this:

IDENTIFIER("answer")
DECLARE
IDENTIFIER("left")
PLUS
INTEGER(22)
END_OF_FILE

These groups are tokens. Typical token categories include:

  • identifiers such as answer and print;
  • keywords such as if, while, and return;
  • literals such as 42, 3.14, and "hello";
  • operators such as +, ==, and >>;
  • punctuation such as (, ), {, and ,; and
  • special tokens for the end of the source or an invalid sequence.

The lexer is not yet trying to understand the complete program. It does not know whether answer names a local variable, whether the addition is valid, or whether the declaration belongs in the current scope. Those questions require more context and belong to later stages.

Lexing is lexical analysis: recognizing relatively local patterns in text. It builds just enough structure for the parser to stop thinking in characters.

Scanning

A basic lexer needs remarkably little state:

typedef struct Lexer {
    String source;
    usize cursor;
} Lexer;

source contains the input text. cursor identifies the next character that has not been consumed.

The central operation is equally small in concept:

Token lex_token(Lexer *lexer);

Each call skips irrelevant trivia, recognizes one token beginning at the cursor, moves the cursor past it, and returns the result.

The complete process is:

source + cursor
       |
       v
 skip whitespace and comments
       |
       v
 inspect the next character
       |
       v
 consume one recognizable pattern
       |
       v
 return a classified token

You may instead tokenize the entire file into an array before parsing. That is also a perfectly reasonable design. elf produces tokens on demand, and the parser retains the previous, current, and next token. The storage decision is secondary. What matters is having one clear operation that produces the next token and can be tested independently.

The minimum token only needs a kind:

typedef enum Token_Kind {
    TOKEN_INVALID,
    TOKEN_EOF,
    TOKEN_IDENTIFIER,
    TOKEN_INTEGER,
    TOKEN_NUMBER,
    TOKEN_STRING,
    TOKEN_PLUS,
    TOKEN_PLUS_EQUAL,
    TOKEN_LEFT_PAREN,
    TOKEN_RIGHT_PAREN,
} Token_Kind;

typedef struct Token {
    Token_Kind kind;
} Token;

That is enough to recognize punctuation, but literals and identifiers carry information of their own. An integer token needs its magnitude. A number token needs its floating-point value. An identifier or string needs its text.

A discriminated union works well in C:

typedef struct Token {
    Token_Kind kind;
    Source_Site site;

    union {
        u64 integer_magnitude;
        f64 number;
        Atom *atom;
    };
} Token;

The token kind determines which payload, if any, is valid. Punctuation does not need a value. An integer uses integer_magnitude, a floating-point literal uses number, and identifiers and strings can use an interned string called an atom.

Source_Site records where the token came from. It might contain byte offsets, a pointer and length, a line number, or a combination of them. Source locations feel optional while every test program is valid. The first useful diagnostic makes them essential.

For example:

example.elf:4:17: malformed exponent
    value := 10e+
               ^

That message is only possible if the lexer preserved the relationship between the token and the original source.

elf also records whether a line break appeared before a token. That small flag is useful to the parser without forcing it to treat every newline as a token. This is a good general rule: add information because a later stage has a specific need for it, not because a token structure might theoretically contain it.

My preferred implementation is a hand-written switch. It is verbose, but the verbosity is honest: programming languages have a finite list of punctuation and operator spellings, and something has to recognize each one.

A simplified scanner begins like this:

Token lex_token(Lexer *lexer) {
    skip_trivia(lexer);

    usize start = lexer->cursor;

    if (at_end(lexer)) {
        return make_token(lexer, start, TOKEN_EOF);
    }

    char c = advance(lexer);

    if (is_identifier_start(c)) {
        return lex_identifier(lexer, start);
    }

    if (is_digit(c)) {
        return lex_number(lexer, start);
    }

    switch (c) {
    case '+': return make_token(lexer, start, TOKEN_PLUS);
    case '(': return make_token(lexer, start, TOKEN_LEFT_PAREN);
    case ')': return make_token(lexer, start, TOKEN_RIGHT_PAREN);
    default: return make_token(lexer, start, TOKEN_INVALID);
    }
}

The exact helper functions do not matter. The important control flow is visible at a glance:

  1. Skip trivia.
  2. Remember where the token begins.
  3. Inspect the first character.
  4. Dispatch to the appropriate recognizer.
  5. Return one token.

This is not a place where compactness is automatically an improvement. A large switch is predictable, easy to step through in a debugger, and easy to extend when the language gains another operator.

Identifiers and Keywords

For our small language, an identifier starts with an ASCII letter or underscore and continues through letters, underscores, or digits:

bool is_identifier_start(char c) {
    return is_letter(c) || c == '_';
}

bool is_identifier_continue(char c) {
    return is_identifier_start(c) || is_digit(c);
}

Once the first character matches, consume characters until that rule stops matching:

Token lex_identifier(Lexer *lexer, usize start) {
    while (is_identifier_continue(peek(lexer))) {
        advance(lexer);
    }

    String text = string_slice(lexer->source, start, lexer->cursor);
    return make_identifier_token(text);
}

Keywords can initially follow the same path. Recognize the complete identifier, then compare its text against the language's keyword table. If the text is while, return TOKEN_WHILE; otherwise return TOKEN_IDENTIFIER.

elf interns identifier strings in an atom table. Interning gives every distinct string one stable object, so later stages can often compare atom pointers rather than repeatedly comparing the characters. That is convenient, but you do not need atom interning to build your first lexer. A pointer and length into retained source text is enough to begin.

Numeric Literals

Number recognition begins with a digit and continues according to the literal formats the language supports. Start with decimal integers:

while (is_digit(peek(lexer))) {
    advance(lexer);
}

Then add floating-point syntax, exponents, hexadecimal, or binary only when the language actually needs them. Every extra spelling adds malformed cases that must produce errors: an exponent without digits, a hexadecimal prefix without a value, or an integer too large for its representation.

One useful boundary is to keep the minus sign out of the numeric literal. Given:

value := -42

elf emits:

MINUS
INTEGER(42)

The parser then constructs unary negation around the positive magnitude. This keeps the lexer from deciding whether - begins a negative number or represents subtraction. Compare:

left-42

At the character level, the lexer should not need to understand whether this is one literal or a binary expression. It consistently emits an identifier, a minus token, and an integer. The parser has the context required to determine the expression structure.

This also matters at the edge of a signed integer range. The magnitude of the most negative integer may not fit in the corresponding positive signed type. Keeping an unsigned magnitude until parsing avoids forcing that decision into the scanner.

Operators and Punctuation

Operators and punctuation are where the switch becomes repetitive. Write the cases out anyway.

Many operators share a prefix, so the usual rule is to choose the longest valid match. A plus may begin +, ++, or += in a language that supports all three:

case '+': {
    if (match(lexer, '+')) return token(TOKEN_INCREMENT);
    if (match(lexer, '=')) return token(TOKEN_PLUS_EQUAL);
    return token(TOKEN_PLUS);
}

The same pattern handles >, >=, >>, and perhaps >>=. elf's declaration and type punctuation provides another example: :, :=, ::, and ::= all begin with the same character.

There are clever ways to encode these tables. Most small languages do not need them. Explicit branches make the recognized spellings and their precedence in the scanner obvious.

Whitespace and Comments

Whitespace and comments are usually trivia: text that separates tokens but does not itself need to reach the parser.

skip_trivia can consume spaces, tabs, line breaks, line comments, and block comments before scanning the next token. It should also update line information for diagnostics.

Trivia is still information even when it does not become a token. A newline may affect automatic statement termination, formatting, or error messages. A comment may eventually matter to documentation tools. Decide deliberately what to discard, and retain the smallest facts that later stages require.

For elf, the parser mostly does not care about whitespace, but it sometimes needs to know that a line break preceded the next token. The lexer therefore discards the actual whitespace while retaining that single fact.

String Literals

A basic string literal scans until its closing quote while handling escapes:

message := "hello\nworld"

The lexer must decide whether it returns the raw source spelling or the decoded value. elf decodes common escapes and Unicode sequences while lexing, then stores the resulting string as an atom.

Multiline and interpolated strings introduce more state. Once an interpolation expression can contain nested braces, the scanner may need to remember whether it is currently reading string text or language code and how deeply braces are nested.

This is where the claim that every token is completely context-free stops being useful. Most ordinary tokens can be recognized from a small local pattern, but some language features create lexical modes. That does not invalidate the simple design. It means the state should be added when the feature requires it.

In fact, elf's current source contains a note questioning whether formatted strings belong entirely in the lexer. That is normal. A lexer can remain simple at its center even when one feature makes its boundary with the parser less obvious.

Do not begin with interpolation. Get identifiers, punctuation, numbers, and plain strings working first.

Testing the Token Stream

The first complete lexer test should be a tiny program that repeatedly requests tokens and prints them:

for (;;) {
    Token token = lex_token(&lexer);
    print_token(token);

    if (token.kind == TOKEN_EOF || token.kind == TOKEN_INVALID) {
        break;
    }
}

Feed it this:

answer := left + 22

Then verify the exact token stream. Test each rule separately:

  • identifiers adjacent to punctuation;
  • keywords that are prefixes of longer identifiers;
  • every one- and two-character operator;
  • decimal, hexadecimal, binary, fractional, and exponent forms;
  • valid and invalid string escapes;
  • comments and line tracking;
  • malformed input and end-of-file behavior; and
  • source locations for every returned token.

If the tokens are wrong, the parser cannot repair them. A printable token stream turns parser failures into a much easier question: did the source become wrong before parsing even began?

elf's lexer tests grew far beyond the small list above. They now cover Unicode escapes, block strings, nested interpolation, numeric overflow, malformed exponents, source ranges, and line-break tracking. Those tests were added as the language acquired the corresponding features. Your first lexer does not need the final test suite of a language that has already evolved.

Keeping the Lexer Simple

The most useful advice I can give is not to over-design this stage.

You are not solving the meaning of the program. You are finding text boundaries and assigning categories. A direct loop and switch statement are often enough. The code may become verbose, and that is fine. Verbose recognition code is usually easier to understand than a compact abstraction that hides which text the language accepts.

That does not mean the lexer will literally never change. New syntax, better diagnostics, Unicode rules, interpolation, or tooling may extend it. The point is that its central architecture can settle down very early:

skip -> inspect -> consume -> classify -> return

Avoid macros and generic machinery merely to reduce the line count. Add state only when a feature demands it. Retain source information because later stages can use it. Keep semantic decisions in the parser or later stages whenever the lexer lacks the context to make them correctly.

Lexing is the first step in reconstructing a program from source text, but it does not need to be mysterious. It transforms an inconvenient stream of characters into a convenient stream of tokens. Once that stream is correct, the parser can begin recovering the structure those tokens describe.

That is where the language starts becoming considerably more interesting.