← 解析器 · 各路引擎、一门文法与编辑器要的那半边 / 缩进也是词法问题：off-side rule 待审核 3 / 25
INDENT / DEDENT · 缩进栈 · 最长匹配

缩进也是词法问题：off-side rule

词法分析通常是无状态的：见到什么切什么，当前位置的判断不依赖此前切出过什么。这条性质让 lexer 可以是一台有限状态机，也是「词法用正则、语法用文法」这一分工的基础。

有一族语言破坏了这条性质。Python 的块结构、Haskell 的 where 布局、YAML 的嵌套映射都由缩进表达，源码里没有 { 与 }。这时 lexer 不得不替语法层干活：记住当前的缩进层级，并在层级变化处生成源码中并不存在的 token。这条规则由 Peter Landin 在 1966 年命名为 off-side rule。

1 · 缩进承载块结构

约定很短：一行的行首缩进比上一层深，表示开启一个新块；比上一层浅，表示关闭若干个块；相等则表示是同一块里的下一条语句。

定义 1.1（off-side rule） 在缩进敏感的语言里，一个块由「首行的缩进列」界定：该块包含随后所有缩进严格大于该列的行，遇到缩进不大于该列的行即结束。块的边界完全由排版决定，无须成对的定界符。

词法层要把这条约定翻译成下游可用的形式，办法是维护一个缩进栈，并在层级变化处发出 INDENT 与 DEDENT 两种结构标记。parser 拿到的因此是一门普通的括号语言，它对待 INDENT 与对待 { 毫无区别。

图 1-1 · 同一段源码的三种视图：原文（缩进承载结构）、逐行的缩进栈与其生成的结构标记、以及把标记回填成花括号后的等价代码。词法分析由 @vega/parsing/offside 的真实 lex 驱动。可切换 tab stop 观察制表符如何折算成列宽，或选取缩进对不齐的示例观察词法阶段的失败。

2 · 缩进栈

栈初始为 [0][0]。对每个逻辑行的行首缩进宽度 ww：

  1. ww 大于栈顶：压入 ww，发一个 INDENT；
  2. ww 小于栈顶：反复弹出直到栈顶不大于 ww，每弹一次发一个 DEDENT；
  3. 弹完之后 ww 若仍不等于栈顶，说明这个缩进对不齐任何已知层级，报错；
  4. 输入结束时把栈清空到只剩 0{0}，为每次弹出补一个 DEDENT。

空行与纯注释行不参与上述判断：它们的缩进没有结构含义，跳过即可。规则 4 保证了一条可测试的不变量：任何合法输入产出的 INDENT 与 DEDENT 数量恒相等。这类平衡性质是这类 lexer 最有效的验收条件，比逐例对照期望 token 串更能覆盖边界情形。

规则 3 对应 Python 的 IndentationError。它说明缩进的合法性判断是上下文相关的：同一个「缩进 2 列」的行，在某个栈状态下合法，在另一个栈状态下就是错误。

3 · 括号内的隐式续行

括号未闭合时，换行不应结束语句：

total = sum(
    a,
        b,
)

第 2、3 行的缩进不同，但它们不构成任何块。规则是 lexer 自行跟踪括号深度：深度大于零时，换行不发 NEWLINE，行首也不量缩进。Python 称之为隐式续行，反斜杠续行则是显式版本。

这件事必须在词法层做。若把它推给 parser，就要求 parser 在收到 INDENT 时能判断「这个 INDENT 应当忽略」，而判断依据是括号是否配对——那是语法层的信息，却要用来修正已经发生的词法决策。让 lexer 自己数一个深度计数器要简单得多。

4 · 最长匹配

第二条需要状态的规则与缩进无关，但同属「扫描即切做不到」的一类：>= 应当切成一个运算符而非 > 与 =，** 与 // 同理。规则叫最长匹配（maximal munch）：在当前位置，从候选中取能匹配最长的那个。

最长匹配的实现只需有界前瞻（候选运算符里最长者的长度），仍不需要回溯。它与缩进栈的区别在于：最长匹配是局部的，只看当前位置往后几个字符；缩进栈是全局的，依赖此前所有行留下的状态。

注 · 最长匹配也有代价。C 语言里 a+++++b 被切成 a ++ ++ + b 而非语义上唯一可行的 a ++ + ++ b，编译由此失败。词法层做的是纯局部的贪心决策，不会为了让语法层通过而回头改口。

5 · 词法阶段已超出正则

缩进栈是一个栈，而栈意味着计数能力。这一点有直接的理论后果。

定理 5.1 缩进敏感语言的 token 序列约束不是正则的。

证明 规则 4 要求 INDENT 与 DEDENT 数量相等且嵌套配对，即产出的结构标记序列构成 Dyck 语言（配对括号语言）。而 Dyck 语言不是正则语言：若它正则，则由泵引理，存在可重复段使 INDENTn DEDENTn\text{INDENT}^n\,\text{DEDENT}^n 被泵成数量不等的串，与配对要求矛盾。故词法阶段的输出约束已越出正则。∎

「词法用有限状态机、语法用下推自动机」这条经典分工在缩进语言里于是并不成立：词法阶段自己就带了一个栈。这并不矛盾，只说明词法与语法的边界是工程约定而非理论必然，把哪些判断划给哪一层，取决于哪种切法让两边的实现都更简单。有限状态机能表达什么、栈又多给了什么，见 有限自动机系列。

6 · 制表符与排版的不确定性

缩进宽度的计算需要一个约定：制表符占几列。CPython 的 tokenizer 把它折算到下一个 tab stop（默认 8 列的整数倍），这也是本模块的默认。

由此产生的第一条教训是：同一份文件混用制表符与空格时，「视觉上的对齐」与「按 tab stop 折算后的宽度」可能不一致，缩进层级由此依赖编辑器设置。Python 3 的对策是直接禁止：混用到会产生歧义的程度即抛 TabError，这是从 Python 2 的实践中吸取的结果。第二条更彻底：YAML 规范干脆禁止用制表符缩进。

本模块只做了折算，没做这层禁止，两者的差别可以直接量出来。一个用八个空格缩进、下一个用单个制表符缩进的兄弟行，折算后宽度都是 8，lex 把它们判为同一层级并正常返回；同一段源码交给 CPython 3 会抛 TabError。折算宽度相等而字节不同这件事，在编辑器里的表现是两行看起来对齐或不对齐取决于当前的 tab 宽设置，而语法层已经把它们当成了同一层。选项名是 tabWidth（默认 8，与 CPython 的 tab stop 一致）；写成 tabStop 不会报错，也不会生效，四个宽度下都会得到默认折算的结果。

两条教训指向同一件事：当排版承担了语法责任，排版的每一处不确定性都会变成语法的不确定性。

7 · 参考文献

  1. Landin, P. J. (1966). The next 700 programming languages. Communications of the ACM, 9(3), 157–166.
  2. Python Software Foundation. The Python Language Reference, §2.1.8 Indentation.
  3. Ben-Kiki, O., Evans, C., & döt Net, I. (2021). YAML Ain't Markup Language (YAML) Version 1.2 (Revision 1.2.2), §6.1 Indentation Spaces.