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

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

本课目标

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

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

本例针对使用 8 位字节与 ASCII 兼容字符编码的常见平台。把下面各 C 代码块按顺序放入同一个 lexer.c，最后附上第 6 节的 main：

#include <stdbool.h>
#include <stddef.h>
#include <stdio.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，长度单独保存，内含零字节也不会被当作输入结束。此实现用显式 ASCII 范围检查，没有调用受 locale 影响的 ctype；若以后改用它，也不能传入负的普通 char 值。此示例只定义 ASCII token；高位字节会产生错误，而不是假装完整支持 UTF-8。

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

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 从起点快照构造

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

这里的列号按字节计数，从 1 开始；Tab 增加一列，不计算显示宽度。只把空格、Tab、CR 和 LF 视为可跳过空白。CRLF 占两个源字节，其中 \r 增加列、\n 换行，单独 CR 暂不增加行号。若语言要求统一换行位置，应在 advance 或解码层显式把 CRLF 作为一个换行序列处理。

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

#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`

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. 初始化与切片

调用方必须保证 source 指向至少 length 字节的可读缓冲区，并在扫描期间保持有效且不变；source == NULL 只允许与零长度一起使用。

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 仍然有效。
bool print_lexeme(FILE *out, const Lexer *lexer, Token token) {
    if (token.start > token.end || token.end > lexer->length) return false;
    size_t size = token.end - token.start;
    if (size == 0) return true;
    return fwrite(lexer->source + token.start, 1, size, out) == size;
}

fwrite 按字节数输出，不把 size_t 缩成 int，也不会在内嵌 NUL 处停止。零长度跨度直接返回，避免对空源指针做算术。返回值让调用方发现输出失败；非法跨度也会被拒绝。

用这个入口检查位置与原文：

int main(void) {
    const unsigned char source[] = "ifx == 12;";
    Lexer lexer = lexer_from_bytes(source, sizeof source - 1);
    Token current;
    while ((current = next_token(&lexer)).kind != TOK_EOF) {
        if (printf("%zu:%zu [%zu,%zu) ", current.line, current.column,
                   current.start, current.end) < 0
                || !print_lexeme(stdout, &lexer, current)
                || putchar('\n') == EOF) return 1;
    }
    return 0;
}

bash

cc -std=c17 -Wall -Wextra -Werror lexer.c -o lexer
./lexer

预期输出：

text

1:1 [0,3) ifx
1:5 [4,6) ==
1:8 [7,9) 12
1:10 [9,10) ;

7. 注释与字符串需要 mode

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

字符串 mode 要处理：

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

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

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

至少覆盖：

text

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

可用属性测试查找以下不变量的反例：token span 单调不重叠，除 EOF 外长度大于零；原始缓冲区中相邻跨度之间的空白就是本实现跳过的 trivia，把它们补回后应恢复原输入。若需要保真 token 流，还应显式保留这些 trivia。

常见误区

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

练习

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

小结

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

第1章逻辑

第2章集合论

第3章证明方法

第4章递归、归纳与递推

第5章关系与函数

第6章组合数学

第7章图论

第8章概率与统计

第9章数论

第10章线性代数

第11章微积分与优化

第12章信息论与数值计算