5.2 Hand-Crafted Scanner: Cursor, Lookahead, and Safety Boundaries

The theoretical finite automaton diagram finally makes its way into source code. Ah Hua picks up the cursor and slices tokens one by one from the input buffer.

While automaton theory defines state transitions, engineering implementation must answer practical questions: who owns the source buffer, how do we perform lookahead, when do we emit a token, and how do we ensure progress after an error? In this lesson, we build an ASCII subset scanner using immutable memory buffers, avoiding reliance on ungetc and fixed-length lexeme arrays.

Learning Objectives

• Organize scanners using peek, advance, and half-open spans;
• Correctly identify identifiers, integers, and one- or two-character operators;
• Avoid buffer overflows and undefined behavior from ctype;
• Expose stable, checkable token results for testing.

1. Cursor points to the next unparsed byte

#include <ctype.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef enum {
    TOK_EOF, TOK_ERROR,
    TOK_IDENTIFIER, TOK_INTEGER,
    TOK_KW_IF, TOK_KW_INT,
    TOK_ASSIGN, TOK_EQUAL,
    TOK_BANG, TOK_NOT_EQUAL,
    TOK_SEMICOLON
} TokenKind;

typedef struct {
    TokenKind kind;
    size_t start;
    size_t end;
    size_t line;
    size_t column;
} Token;

typedef struct {
    const unsigned char *source;
    size_t length;
    size_t current;
    size_t line;
    size_t column;
} Lexer;

The source buffer uses unsigned char with its length stored separately, allowing safe handling of buffers containing null bytes and preventing the passage of a negative char to ctype. This example only defines ASCII tokens; high-order bytes will cause errors rather than pretending to support UTF-8 fully.

2. Look Ahead Without Consuming, Progress Only Updates Position

static bool at_end(const Lexer *lexer) {
    return lexer->current >= lexer->length;
}

static int peek(const Lexer *lexer) {
    return at_end(lexer) ? EOF : lexer->source[lexer->current];
}

static int advance(Lexer *lexer) {
    if (at_end(lexer)) return EOF;
    unsigned char byte = lexer->source[lexer->current++];
    if (byte == '\n') {
        lexer->line++;
        lexer->column = 1;
    } else {
        lexer->column++;
    }
    return byte;
}

static bool match(Lexer *lexer, unsigned char expected) {
    if (peek(lexer) != expected) return false;
    (void)advance(lexer);
    return true;
}

peek returns an integer constant EOF at EOF, ensuring no conflict with any unsigned char value. advance is the only function that updates row and column positions, eliminating the need for each token branch to implement its own position-tracking logic.

3. Constructing a Token from a Snapshot at the Start

static Token token(
    TokenKind kind,
    size_t start,
    size_t line,
    size_t column,
    const Lexer *lexer
) {
    return (Token){
        .kind = kind,
        .start = start,
        .end = lexer->current,
        .line = line,
        .column = column,
    };
}

static void skip_ascii_whitespace(Lexer *lexer) {
    for (;;) {
        int byte = peek(lexer);
        if (byte == ' ' || byte == '\t' || byte == '\r' || byte == '\n') {
            (void)advance(lexer);
        } else {
            return;
        }
    }
}

Treat CRLF as two bytes, where \r adds a column and \n introduces a line break. If the language requires consistent line break positioning, the behavior must be explicitly handled at the advance level or in the decoding layer by treating CRLF as a line break sequence.

4. Scan Identifiers and Reclassify Keywords

#include <string.h>

static bool ascii_identifier_start(int byte) {
    return byte == '_' || (byte >= 'A' && byte <= 'Z')
        || (byte >= 'a' && byte <= 'z');
}

static bool ascii_identifier_continue(int byte) {
    return ascii_identifier_start(byte) || (byte >= '0' && byte <= '9');
}

static bool lexeme_equals(
    const Lexer *lexer, size_t start, const char *text
) {
    size_t size = lexer->current - start;
    return strlen(text) == size
        && memcmp(lexer->source + start, text, size) == 0;
}

static TokenKind identifier_kind(const Lexer *lexer, size_t start) {
    if (lexeme_equals(lexer, start, "if")) return TOK_KW_IF;
    if (lexeme_equals(lexer, start, "int")) return TOK_KW_INT;
    return TOK_IDENTIFIER;
}

Keyword checking occurs after the entire identifier scan is complete, so ifx is an TOK_IDENTIFIER. In real programming languages, keywords can be numerous and are often distributed by length or first character, or stored in hash tables, perfect hashes, and other data structures; measure first, then optimize.

5. Complete next_token

Token next_token(Lexer *lexer) {
    skip_ascii_whitespace(lexer);

    size_t start = lexer->current;
    size_t line = lexer->line;
    size_t column = lexer->column;

    int byte = advance(lexer);
    if (byte == EOF) {
        return token(TOK_EOF, start, line, column, lexer);
    }

    if (ascii_identifier_start(byte)) {
        while (ascii_identifier_continue(peek(lexer))) {
            (void)advance(lexer);
        }
        return token(
            identifier_kind(lexer, start), start, line, column, lexer
        );
    }

    if (byte >= '0' && byte <= '9') {
        while (peek(lexer) >= '0' && peek(lexer) <= '9') {
            (void)advance(lexer);
        }
        return token(TOK_INTEGER, start, line, column, lexer);
    }

    switch (byte) {
        case '=':
            return token(
                match(lexer, '=') ? TOK_EQUAL : TOK_ASSIGN,
                start, line, column, lexer
            );
        case '!':
            return token(
                match(lexer, '=') ? TOK_NOT_EQUAL : TOK_BANG,
                start, line, column, lexer
            );
        case ';':
            return token(TOK_SEMICOLON, start, line, column, lexer);
        default:
            return token(TOK_ERROR, start, line, column, lexer);
    }
}

Every non-EOF token consumes at least one byte. Even erroneous tokens allow the caller to proceed, without getting stuck at the same position.

6. Initialization and Slicing

Lexer lexer_from_bytes(const unsigned char *source, size_t length) {
    return (Lexer){
        .source = source,
        .length = length,
        .current = 0,
        .line = 1,
        .column = 1,
    };
}

// Use token Must ensure before source Still valid.
void print_lexeme(const Lexer *lexer, Token token) {
    size_t size = token.end - token.start;
    printf("%.*s", (int)size, lexer->source + token.start);
}

Production code should also verify that the transition from size_t to int exceeds INT_MAX. The example omits this layer to focus on the scanning logic. A more robust printing approach can directly use fwrite.

7. Comments and Strings Require Mode

Single-line comments can consume newlines or EOF. Block comments must recognize terminating sequences and generate a "missing closing comment" diagnostic at EOF. If the language supports nested block comments, the parser must also track nesting depth.

String mode must handle:

• Closing quotes;
• Escaped quotes and backslashes;
• Whether line breaks are allowed;
• Invalid escapes;
• Unclosed strings before EOF.

Do not apply a general whitespace rule to internal string content first, as this would corrupt the semantics of spaces and newlines.

8. Test Boundaries Rather Than Just Example Cases

At minimum, cover:

Empty input
Single-character token
= versus ==, ! versus !=
if, ifx, _if, int2
Very long identifiers
Unknown ASCII characters
High-order UTF-8 bytes
Token adjacent to end of file
Consecutive CRLF and multi-line positions

Property-based testing can verify: token spans are monotonically non-overlapping; all lengths are positive except at EOF; concatenating all tokens and trivia reconstructs the original input.

Common Misconceptions

• Fixed char lexeme[256] is sufficient for teaching purposes: Failing to check length directly leads to buffer overflow.
• ungetc being the longest match is a necessary condition: Memory buffer cursors or buffered readers are easier to manage and control.
• ctype accepts arbitrary char: All parameters except EOF must be representable as unsigned char.
• EOF is a regular byte: It is a special return value within the int range and cannot be stored in an char comparison.

Exercise

1. Supplement the scanner with + - * / ( ) { }.
2. Correctly synchronize the row and column updates for LF and CRLF, and write corresponding tests.
3. Implement support for // and non-nested /* ... */ comments, reporting unclosed positions.
4. Use AddressSanitizer and fuzzing with random byte inputs to verify no buffer overruns and that progress is always made.

Summary

Writing the core of a lexer isn't lengthy, its reliability stems from well-defined boundary contracts: an immutable source buffer, a single cursor, a clear EOF, half-open spans, and advancing on error. The next lesson will combine multiple token rules, explaining longest match, tie-breaking for equal-length tokens, lexer modes, and the actual responsibilities of the lexer and generator.