字符串解析 / Token 状态机

几何、扫描线、模拟与解析 · HTML

数学 / 逻辑形态

在位置 i 依据字符类别选择 token 规则；规则消费一个非空最长前缀并返回 (type,value,next_i)。

识别信号

• 输入是字符流而非已分词对象
• 空白、数字、标识符与符号规则不同
• 最长匹配影响边界
• 后续语法依赖 token 类型
• 需要报告非法字符位置

容易误判的相似信号

核心不变量

循环前 s[:i] 已被完整且无重叠地切成合法 token；下一规则从 i 消费至少一字符或明确报错。

状态、转移与处理顺序

Python 骨架

def tokenize(s):
    tokens, i = [], 0
    while i < len(s):
        ch = s[i]
        if ch.isspace():
            i += 1
        elif ch.isdigit():
            j = i + 1
            while j < len(s) and s[j].isdigit(): j += 1
            tokens.append(('INT', int(s[i:j])))
            i = j
        elif ch.isalpha() or ch == '_':
            j = i + 1
            while j < len(s) and (s[j].isalnum() or s[j] == '_'): j += 1
            tokens.append(('NAME', s[i:j]))
            i = j
        elif ch in '+-*/()':
            tokens.append((ch, ch)); i += 1
        else:
            raise ValueError(f'unexpected character at {i}: {ch!r}')
    return tokens

正确性思路

1. 每条规则只从当前 i 开始，故 token 不重叠。
2. 数字与标识符循环消费该类别的最长连续前缀。
3. 所有分支推进 i 或抛错，因此终止且不静默跳过字符。
4. 归纳得成功返回时 token 拼接（除空白）与输入一致。

复杂度

边界条件

• 空输入返回空 token
• 末尾恰结束一个多字符 token
• 一元负号通常留给 parser 判定
• Unicode 字母类别是否允许
• 引号与转义需额外状态

错误模式

选择与排除规则

• 先词法分层，再处理嵌套语法。
• 每个规则保证消费非空前缀。
• 最长匹配冲突时规定优先级。
• 错误中保留字符位置便于调试。

相关模板

原创微型例子

Recall prompts

• tokenizer 的循环不变量是什么？
• 为何一元负号不宜盲目并入数字？
• 怎样保证每轮都取得进展？

我的补充