Software Systems Atlas

中文

English

中文

English

主题

5.2 手写扫描器：游标、前瞻与安全边界 ​

理论层的自动机图终于要落进源代码，阿花拿起游标，从输入缓冲区里逐个切出 token。

自动机理论给出了状态转换，工程实现还要决定源缓冲区归谁、怎样前瞻、何时提交 token，以及错误后怎样保证继续前进。本课用不可变内存缓冲区写一个 ASCII 子集扫描器，避免依赖 ungetc 和固定长度 lexeme 数组。

本课目标 ​

  • 用 peek、advance 和半开 span 组织扫描器；
  • 正确识别标识符、整数和一/二字符运算符；
  • 避免缓冲区越界与 ctype 未定义行为；
  • 为测试暴露稳定、可检查的 token 结果。

1. 游标指向下一个未消费字节 ​

c
#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;

源缓冲区使用 unsigned char，长度单独保存，所以可以安全处理内含零字节并避免把负 char 传给 ctype。此示例只定义 ASCII token；高位字节会产生错误，而不是假装完整支持 UTF-8。

2. 前瞻不消费，推进才更新位置 ​

c
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 在 EOF 返回整数常量 EOF，不会与任意 unsigned char 值冲突。advance 是唯一更新行列的函数，避免每条 token 分支各写一套位置逻辑。

3. Token 从起点快照构造 ​

c
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;
        }
    }
}

这里把 CRLF 当成两个字节，其中 \r 增加列、\n 换行。若语言要求统一换行位置，应在 advance 或解码层显式把 CRLF 作为一个换行序列处理。

4. 扫描标识符并重分类关键字 ​

c
#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;
}

关键字检查发生在整个标识符扫描完以后，所以 ifx 是一个 TOK_IDENTIFIER。真实语言的关键字很多时，可按长度和首字符分派，或使用哈希表、完美哈希等结构；先测量再优化。

5. 完整的 next_token ​

c
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);
    }
}

每个非 EOF token 至少消费一个字节。错误 token 也能让调用方继续，不会卡在同一位置。

6. 初始化与切片 ​

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

// 使用 token 前必须保证 source 仍然有效。
void print_lexeme(const Lexer *lexer, Token token) {
    size_t size = token.end - token.start;
    printf("%.*s", (int)size, lexer->source + token.start);
}

生产代码还应检查 size_t 转 int 是否超过 INT_MAX；示例省略这一层是为了聚焦扫描逻辑。更稳妥的打印可以直接使用 fwrite。

7. 注释与字符串需要 mode ​

单行注释可以消费到换行或 EOF。块注释必须识别结束序列，并在 EOF 时产生“未闭合注释”诊断。若语言允许嵌套块注释，还要维护嵌套深度。

字符串 mode 要处理：

  • 结束引号；
  • 转义后的引号和反斜杠；
  • 是否允许换行；
  • 非法转义；
  • EOF 前未闭合。

不要先用通用空白规则处理字符串内部，否则空格和换行语义会被破坏。

8. 测试边界而不是只测示例 ​

至少覆盖：

text
空输入
单字符 token
= 与 ==，! 与 !=
if、ifx、_if、int2
超长标识符
未知 ASCII 字符
高位 UTF-8 字节
文件末尾紧贴 token
连续 CRLF 和多行位置

可用属性测试验证：token span 单调不重叠；除 EOF 外长度大于零；拼接所有 token 与 trivia 后能恢复原输入。

常见误区 ​

  • 固定 char lexeme[256] 足够教学使用：不检查长度会直接造成越界写。
  • ungetc 是最长匹配的必要条件：内存缓冲区游标或带缓存 reader 更容易控制。
  • ctype 接受任意 char：除 EOF 外参数必须可表示为 unsigned char。
  • EOF 是普通字节：它是 int 范围中的特殊返回值，不能塞进 char 比较。

练习 ​

  1. 为扫描器补充 + - * / ( ) { }。
  2. 正确统一 LF 与 CRLF 的行列更新，并编写测试。
  3. 实现 // 与不嵌套的 /* ... */ 注释，报告未闭合位置。
  4. 用 AddressSanitizer 和模糊测试随机字节输入，验证不越界且总能前进。

小结 ​

手写 lexer 的主体不长，可靠性来自边界契约：不可变源缓冲区、单一游标、明确 EOF、半开 span 和错误时前进。下一课把多条 token 规则合并起来，解释最长匹配、同长优先级、lexer mode 与生成器的真实职责。

Built with VitePress | Software Systems Atlas

Copyright 2026 Steven Yang