词法器设计

词法器把源码切成供语法分析使用的 token，同时保留足够的信息支持报错、格式化和编辑。设计的重点是明确输入编码、规则优先级、位置单位、错误行为，以及谁拥有被引用的源码。

Token：分类、原文与位置分工

一种适合不可变源码快照的表示如下。示例中的整数是十进制数字串，运算符只列出两种；实际语言可继续扩展。

#[derive(Clone, Copy)]
struct Span {
    file: u32,
    revision: u64,
    start: usize,
    end: usize, // UTF-8 字节偏移，半开区间
}

enum Operator { Add, Subtract }
enum TokenKind {
    Identifier,
    Integer,
    Operator(Operator),
    Eof,
    Invalid,
}
struct Token {
    kind: TokenKind,
    span: Span,
}

原文可以通过 span 从仍存活的快照切片，无须每个 token 再存一份字符串。也可以直接借用文本，或把标识符驻留为 SymbolId；要保证引用不超出源缓冲生命周期。字符串的原始拼写与转义后的值应区分，数值的语法识别与目标类型溢出检查也可以分阶段。

parser 能通过 Operator(Add) 判断加号，并不要求每种运算符必须是顶层枚举变体。粒度应服务于使用方，不能由某个 DFA 状态数量反推唯一表示。

匹配规则：关键字只是分类策略之一

优先取最长匹配，再解决等长冲突。ifx 应作为完整标识符，不能先切成关键字 if 和 x。

关键字既可以直接写入生成器规则，也可以先识别标识符，再查关键字表。前者由自动机共享公共前缀，后者方便集中管理语言版本和保留字。普通哈希表、完美哈希、排序表或按长度分支都有适用场景；少量关键字不意味着必然状态爆炸。

上下文关键字可能先保留为 Identifier，再由 parser 判断其位置是否合法。原始标识符、字符串插值、缩进 token 和嵌套注释则可能要求词法状态、状态栈或计数器。lexer 与 parser 的边界是语言设计和实现的选择，并非所有规则都能单靠一个正则完成。

Span：绑定快照，使用半开区间

[start, end) 方便计算长度和切片，空区间也能表示缺失 token 的插入位置。字节偏移只在所属源码版本中有效：在前面插入一个字符，后面的偏移会变化。IDE 必须用新快照重新解析，或通过编辑映射换算，不能把旧 offset 当成跨版本稳定身份。

行首表存每一行开始的字节偏移，通常以 0 开头。查询位置 offset 所在行，应找最后一个不大于 offset 的行首，而不是要求 offset 恰好命中某个行首。

from bisect import bisect_right

def byte_line_column(line_starts, offset):
    # 前置条件：表属于同一快照，且 0 <= offset <= 文件字节数
    row = bisect_right(line_starts, offset) - 1
    return row + 1, offset - line_starts[row] + 1

assert byte_line_column([0, 6], 4) == (1, 5)
assert byte_line_column([0, 6], 6) == (2, 1)

这是字节列，不是 Unicode 码位列、UTF-16 列或屏幕列。制表符、组合字符和宽字符还会影响显示宽度。与编辑器协议交换位置时，应按协商编码转换；LSP 的相关约定见 语言服务器协议。CRLF 如何计为一次换行、文件末尾空行如何表示，也要在源文件管理层统一。

迭代接口与前瞻缓存

基础接口可以只是 next_token()。parser 的 token 缓冲层再提供 peek、advance 和 expect。首次 peek 可以触发扫描，后续 peek 复用缓存；无须为了宣称 peek 为 O(1)，强制所有扫描都提前发生。

固定 k 个 token 的前瞻可以使用小队列。支持试探解析时，checkpoint 应覆盖 token 游标和相关 parser 状态；如果 lexer 会被 parser 切换模式，回退还需恢复模式或保证缓存兼容。不能只退一个字节游标就认为全部状态已还原。

EOF 应是稳定的终止状态。上层在 EOF 反复 peek 不应触发越界；恢复循环也不能把重复收到 EOF 误当作取得进展。

输入管理：整个文件与流式窗口都合理

普通源文件常直接读入不可变缓冲，便于 span 切片、多次分析与诊断。读取整个文件是有效设计，是否占用过多内存取决于项目规模、并发文件数和保留策略。

流式扫描可减少常驻输入，但 token 完全可能跨缓冲边界。实现必须保留未完成 token 和回退区间，必要时扩容、搬移或复制；长字符串不能因为超过 4 KiB 就天然失去合法性。

双缓冲也不自动意味着 I/O 与扫描并行，并行需要明确的异步或线程机制。mmap 提供按需映射，但不免除文件生命周期、映射失效与随机访存成本的考虑。re2c 将缓冲补充与边界检查留给集成代码配置。re2c 输入处理

输入块结束不是 token 结束，也不一定是字符结束

假设输入第一块恰好是 if。现在不能立即输出关键字，因为下一块可能以 x 开头，使完整 token 成为 ifx。输入块也可能停在中这个字符的三个 UTF-8 字节之间；解码器需要等待续字节，词法器则需要等待足以确定 token 边界的字符，两层状态各有职责。

下面实现很小的批量 feed 接口：标识符限定 ASCII，关键字只有 if，整数只接受十进制数字；运算符为 = 和 ==，空白仅空格/制表/CR/LF。其他合法 Unicode 码点产出 Invalid，非法 UTF-8 则终止并抛出解码错误。不是把中或 emoji 当作“非法 UTF-8”。

import codecs
import re

class StreamingLexer:
    def __init__(self):
        self.decoder = codecs.getincrementaldecoder("utf-8")("strict")
        self.pending = ""
        self.offset = 0
        self.closed = False

    def feed(self, data, final=False):
        if self.closed:
            raise ValueError("input already finalized")
        self.pending += self.decoder.decode(data, final=final)
        result = []
        while self.pending:
            first = self.pending[0]
            match = re.match(r"[A-Za-z_][A-Za-z_0-9]*|[0-9]+", self.pending)
            if match:
                text = match.group()
                if len(text) == len(self.pending) and not final:
                    break  # 可能还有后续标识符/数字字符
                kind = "If" if text == "if" else "Integer" if text[0].isdigit() else "Identifier"
            elif first == "=":
                if len(self.pending) == 1 and not final:
                    break  # 下一块可能把 = 延长为 ==
                text = "==" if self.pending.startswith("==") else "="
                kind = "Equal" if text == "==" else "Assign"
            else:
                text = first
                kind = "Whitespace" if first in " \t\r\n" else "Invalid"
            end = self.offset + len(text.encode("utf-8"))
            if kind != "Whitespace":
                result.append((kind, text, self.offset, end))
            self.offset = end
            self.pending = self.pending[len(text):]
        if final:
            self.closed = True
            result.append(("Eof", "", self.offset, self.offset))
        return result


def lex_chunks(chunks):
    lexer, result = StreamingLexer(), []
    for chunk in chunks:
        result.extend(lexer.feed(chunk))
    return result + lexer.feed(b"", final=True)

raw = "ifx == 中 😀 if 12".encode("utf-8")
expected = lex_chunks([raw])
assert [(kind, text) for kind, text, start, end in expected] == [
    ("Identifier", "ifx"), ("Equal", "=="), ("Invalid", "中"),
    ("Invalid", "😀"), ("If", "if"), ("Integer", "12"), ("Eof", "")]
for cut in range(len(raw) + 1):
    assert lex_chunks([raw[:cut], raw[cut:]]) == expected
assert lex_chunks([bytes([b]) for b in raw]) == expected
for kind, text, start, end in expected:
    assert raw[start:end].decode("utf-8") == text
for invalid in (b"\xff", b"\xe4\xb8", b"\xc0\xaf"):
    try:
        lex_chunks([invalid])
    except UnicodeDecodeError:
        pass
    else:
        raise AssertionError("invalid UTF-8 accepted")

把每个可能的字节切点都试一次，会同时覆盖 if/x、=/= 以及中和 emoji 内部的切分。输出 token 的原文和字节区间应完全一致，不随 I/O 分块变化。结尾的 final=True 很重要：它既让待定 if 被分类为关键字，也要求解码器报告未完成的 UTF-8 序列。Python 增量解码接口

这个教学实现会复制 pending 字符串，并从头重复匹配尚未结束的长 token，因此没有线性时间或固定内存保证；真实流式词法器应保存扫描状态与游标，设置合理资源预算。它也跳过空白，没有构成无损 token 流。feed 关闭后拒绝继续提交数据；面向 parser 的 peek/next 包装层可以缓存最后的 Eof，实现稳定的终止查询。

字节到了，字符和 token 就都完整了吗？

接收进度不能直接当作扫描完成进度。下面故意把滑杆停在 if 后、单个等号后、中文字节中间和 emoji 字节中间：这些位置分别缺少 token 边界证据或完整字符。已确认 token 使用原始字节区间；尚未解码的字节不会被伪装成非法 Unicode 字符。EOF 是额外事实，提前宣告 EOF 可能得到合法短输入，也可能得到截断错误。

Unicode：解码规则与标识符规则分开

UTF-8 解码需要检查续字节、过长编码、代理码位及码位上限，不能只根据首字节判断长度后盲目跳过。若输入类型已经保证是有效 UTF-8，可利用标准库迭代边界；否则先决定非法字节的诊断与恢复策略。

解码得到码位后，还要依据语言规范判断标识符是否合法。Rust 使用 XID_Start、XID_Continue 相关规则，允许下划线参与，并规定 NFC 规范化等要求；单独下划线与原始标识符还有额外规则。\w 不是通用的语言标识符规范。Rust 标识符

规范化后的符号比较与原始源码拼写可以同时保留：名字解析使用规范形式，诊断仍高亮用户输入。Unicode 版本也是语言兼容性的一部分。

错误恢复：消费策略必须符合当前状态

非法字符可以生成 Invalid token 并消费一个有效码位；非法 UTF-8 则按既定字节恢复策略推进。未闭合字符串、注释或插值需要各自的终止条件，不能统一“跳过一个字符”。多行字符串合法时，换行当然不是错误边界。

一次恢复应消费输入、改变状态并保证下一步能够推进，或明确在 EOF 停止。生成占位 token 但留在原位置反复报同一错误，会导致死循环。诊断可以与 token 分开返回，让 parser 知道错误区间而不必重复报告同一个词法问题。

手写还是生成器

选择应由语言规则和测量结果支持。两者都要验证最长匹配、跨缓冲 token、Unicode 边界、EOF 和恢复进度。后续如何把 token 组成保留错误信息的树，见 AST 设计与错误恢复。

Keywords: lexer, token, span, source snapshot, maximal munch, lookahead, Unicode, UTF-8, line table, recovery, re2c