Reading 19: 解析器（Parsers）

目录 · ← l18 · l20 →

Reading 19: 解析器（Parsers）

说明：本讲 sp22 原版使用 TypeScript，本笔记按用户要求提供 Java 代码示例；类型/API 与 sp21（6.031 Java 版）原文保持一致。

概述

本讲要解决的问题是：如何把一串字符（character sequence）可靠地变成一个程序可以直接操作的数据值。课程给出的答案是一条三步流水线：先用一份文法（grammar）声明式地描述「合法的字符序列长什么样」，再让解析器生成器（parser generator）把文法自动编译成解析器（parser），解析器把输入匹配成一棵解析树（parse tree）；最后我们写一个跟随文法结构递归的函数，把解析树翻译成一个递归数据类型——也就是抽象语法树（abstract syntax tree, AST）。这条流水线在软件构造中的角色是「把外部世界的非结构化输入变成内部世界的结构化的、有类型的数据」，是所有编译器、配置文件读取器、协议解析器、查询语言解释器的第一道关卡。

它与三大目标的关系是直接的：Safe from bugs，文法是一种声明式的规格说明（declarative specification），比手写解析代码更简单、更直接、更不容易出错，而且文法的错误在生成阶段就能被发现；Easy to understand，一份紧凑的文法比几十行手工 substring/indexOf 代码更能说明「这个序列的形状是什么」；Ready for change，要支持新语法时，改文法再重新生成解析代码即可，不需要重写整段解析逻辑。本讲也是 Reading 17（递归数据类型）在真实工程里的第一次大规模应用：解析的终点就是递归 ADT。

核心概念与设计原则详解

解析器生成器（Parser Generator）

定义与目的：解析器生成器是一个把「文法」当作输入、把「解析器」当作输出的工具；它生成的解析器接受字符序列，并尝试把该序列与文法匹配。它服务的质量目标是安全性（自动生成的匹配逻辑比人手写的状态机更可靠）与可修改性（文法改动可重新生成）。
直观解释（”它是什么？”）：它像一台「语法翻译机」：你交给它一份「什么样的句子算合法」的说明书，它替你造出一个能把句子拆解成语法结构的工人。6.031 使用课程组自研的 ParserLib（sp21 为 Java 版），它与工业界广泛使用的 Antlr 思想相同，但接口更简单。ParserLib 采用的是自顶向下的递归下降解析器（recursive descent parser）。
关键规则与最佳实践：
- 把解析器生成器当作工具箱的常备工具：凡是「解析文本」的需求，先想「能不能用文法描述」，而不是先想「怎么写循环」。
- 文法用 ::= 定义规则，规则以分号结束，规则名即非终结符（nonterminal），习惯全小写。
- 终结符（terminal）是带引号的字面串（如 '<i>'）或正则表达式式的字符类（如 [^<>]+）；ParserLib 要求字面字符必须加引号或放进 [...]，所以 (alpha\|beta\|[c-z])* 要写成 ('alpha'\|'beta'\|[c-z])*。
- 规则中可用选择 \|、重复 * + ?、分组 (...)。
- 文法文件里的空白（引号与字符类之外的）不具意义，html::=(italic\|normal)*; 与带空格写法等价。
- 习惯把根非终结符（root / starting symbol）的规则写在最前面，方便人自顶向下阅读；真正决定根的是 compile 时传入的那个枚举常量。

根非终结符与文法的不变式（Root Nonterminal）

定义与目的：根非终结符就是「整段输入必须匹配的那个非终结符」。它决定了解析的入口，也决定了「什么算解析成功」。它保护的是安全性：一个明确的入口避免了「部分匹配」被误认为成功。
直观解释（”它是什么？”）：把文法想成一张语法地图，根非终结符是你出发的城市；解析器必须从这座城市出发走完全程，走不到终点就是解析失败。
关键规则与最佳实践：
- 根通常是语法上最外层、最概括的那个非终结符（如整数表达式文法里的 expr、HTML 文法里的 html）。
- 在 Java 中，ParserLib 用一个 enum 列出文法的全部非终结符，compile 时用 XXXGrammar.EXPR 指定根；枚举也帮助 ParserLib 检查文法里是否有拼错或漏掉的规则。
- ParserLib 对非终结符名大小写不敏感（内部统一转小写），但 Java 枚举常量按惯例全大写，两者要能在心里对上号。
- 枚举中要包含所有非终结符（包括只在 @skip 里使用的那个，如 WHITESPACE），但不包含终结符（'Fall' 不是枚举值）。

空白处理与 @skip 指令（Whitespace and @skip）

定义与目的：真实输入里到处是空格、制表符和换行，但语法结构通常「不关心」它们。@skip 让文法作者声明「某个非终结符的匹配结果应当被自动忽略」，从而把空白处理从每条规则里抽出来，提升可理解性与可修改性。
直观解释（”它是什么？”）：@skip N { ... } 相当于在块内每条规则的右侧、每个终结符/非终结符/字符类的前后，都自动插入 N*。就像排版时说「这里到那里，空白一律不计」。
关键规则与最佳实践：
- @skip 不专属于空白：任何在文法中定义过的非终结符都能被 skip，例如 @skip spacesAndComments。
- 关键设计抉择：把 number/constant 这类规则放在 @skip 块外，才能接受 42 + 2 却拒绝 4 2 + 2。若把 number 放进块内，它实际会变成 number ::= (whitespace* [0-9] whitespace*)+，于是 4 2 会被当成一个数。
- 反过来，把使用 number 的 primary 放进 @skip 块内，number 的前后就能有空白。
- 被 skip 的子树不会出现在 children() 里，因此转换函数里永远不需要处理 WHITESPACE 这一 case。
- @skip 的写法会改变节点 text() 的内容：块内规则的节点其 text() 可能包含首尾空白（例如 "Fall "），块外的不会。

解析树（Parse Tree）与遍历

定义与目的：解析树展示「文法产生式是如何展开成与输入匹配的句子的」。根节点对应文法的根非终结符，每个节点展开成一条产生式。它是解析的中间产物，也是「解析到底哪里出错」的调试依据。
直观解释（”它是什么？”）：解析树像一棵「语法的家族树」：每个内部节点是一个语法范畴（nonterminal），它的孩子是这条产生式右侧被匹配到的那些子范畴。终结符（+、(、54 里的数字字符）不单独成节点。
关键规则与最佳实践：
- 在 Java 中 ParseTree<NT> 是泛型类型，由你定义的非终结符枚举参数化：ParseTree<IntegerGrammar>。
- 四个核心方法：观察者 name()（本节点对应的非终结符）、children()（有序的孩子，不含被 skip 的子树）、text()（本子树匹配到的原始子串），以及查询方法 childrenByName(NT)（等价于对 children() 做一次 filter）。
- 遍历解析树的自然方式是递归函数，并让函数结构跟随文法结构。
- 调试时用 toString() 打印，或用 Visualizer.showInBrowser(tree) 在浏览器里可视化（打不开浏览器时会打印一个可复制的 URL）。
- 只看 children() 的节点名，就能验证「终结符没有独立节点」「孩子的名字必是该产生式右侧提到的非终结符」「@skip 的非终结符不会出现在孩子里」。

抽象语法树（AST）与具体语法树（Concrete Syntax Tree）

定义与目的：把解析树翻译成递归数据类型，就得到抽象语法树。它保留语言表达式的重要特征（分组结构与其中的数值），丢弃「这串字符具体是怎么写的」这种无关细节。这是把「文本」正式转成「有类型的值」的一步，直接服务于安全性（类型系统从此可以检查）与可修改性（后续处理只依赖 AST，不依赖书写形式）。
直观解释（”它是什么？”）：解析树（也叫具体语法树）记录「作者怎么写的」，AST 记录「意思是什么」。2+2、((2)+(2))、0002+0002 会生成三棵不同的具体语法树，但它们都对应同一个 AST 值 Plus(Number(2), Number(2))。
关键规则与最佳实践：
- 转换函数一个 case 对应一条文法规则，并显式处理每种产生式；文法重大改动时这个函数通常也要跟着改。
- 恰当使用 map/reduce（Java 中用循环或 stream()）避免手写索引，因为 childrenByName(NT) 就是一次 filter。
- 用 switch 处理 primary 这类「多选一」节点时，务必每个 case 都 return 或 throw——switch 会从匹配的 case 开始向下贯穿（fall through），忘记 return 会静默执行下一个 case 的代码。
- 文法的 n 元结构（sum ::= primary ('+' primary)*）与 AST 的二元结构（Plus(left, right)）经常不一致，需要在转换函数里显式地把 n 元折叠成二元（或改动文法使解析树本身至多二元）。
- 解析树的形状由文法决定：@skip 放在哪一层，直接决定你比较 text() 时要不要 trim()。

递归下降解析与左递归（Recursive Descent & Left Recursion）

定义与目的：ParserLib 生成的是自顶向下的递归下降解析器：它从根非终结符出发，为每条规则尝试匹配右侧的各个成分。理解这个实现方式，才能理解它为什么不能接受某些文法，从而避免在这类文法上浪费时间。
直观解释（”它是什么？”）：递归下降解析器像人照着地图走迷宫：每到一处，就按规则顺序试着走一步。左递归（left recursion）就是「第一步要求你先走到你现在所在的位置」——永远原地打转，问题规模不变小，递归无法终止。
关键规则与最佳实践：
- 左递归的定义：某非终结符的定义中，它自己出现在最左符号位置，例如 sum ::= number \| sum '+' number ;。
- 左递归可以是间接的：sum ::= number \| thing number ; thing ::= sum '+' ; 同样致命。
- 非左递归的递归是安全的：expr ::= number \| '(' expr ')' ; 每次递归前先消耗掉一个 (，问题在变小。
- 消除办法：把左递归改写成重复，sum ::= (number '+')* number ;。
- 若把左递归文法交给 ParserLib，解析时会以 UnableToParseException（sp22 中为 ParseError）失败，并列出有问题的非终结符。
- 贪婪性（greediness）：ParserLib 在每一点都尝试为当前规则匹配最长的串，因此 g ::= ab threeb ; ab ::= 'a'*'b'* ; threeb ::= 'bbb' ; 无法解析 'aaaabbb'（ab 先把整串吃掉）。这是该类解析器的固有局限，不像左递归那样容易修。

错误处理（Handling Errors）

定义与目的：解析是「外部输入」进入程序的第一道门，必须明确失败语义。ParserLib 用异常把三类失败分开，让调用者能区分「我的文法文件有问题」与「用户的输入不合法」。
直观解释（”它是什么？”）：解析错误像海关查验：要么是你的查验手册写错了（文法错误），要么是旅客的证件不合规（输入错误）。异常里给出的位置信息只是可能的位置，因为解析器并不知道你原本想写什么。
关键规则与最佳实践：
- 文法文件打不开 → compile 抛 IOException。
- 文法本身有语法错误 → compile 抛 UnableToParseException。
- 输入串无法用该文法解析 → parse 抛 UnableToParseException。
- 异常里的位置信息需要人工排查，不要期望它精确指向你心里的那一个字符。
- 在 Java 中 UnableToParseException 是受检异常（checked exception），调用处必须 try/catch 或声明 throws——编译器会强制你面对「解析可能失败」这个事实。

解析与 ADT / 递归数据类型的关系（Parsing as ADT Construction）

定义与目的：解析的终点不是树，而是值。AST 是用递归数据类型定义的 ADT，它的抽象函数（AF）把「内存里的对象图」映射为「一个数学上的表达式」。
直观解释（”它是什么？”）：解析树是「过程性的中间产物」，AST 是「结果性的抽象值」。就像做菜时案板上的半成品与端上桌的那道菜：前者记录了你切了几刀，后者才是「一道菜」本身。
关键规则与最佳实践：
- AST 类型应当在接口/抽象类里写下 datatype definition 注释，把「ADT 的取值集合」显式化，例如 IntegerExpression = Number(n:int) + Plus(left, right)。
- 产生 AST 的转换函数应当写清晰的 specs：前置条件是「该解析树由本讲文法生成」，后置条件是「返回与之对应的 AST 值」。
- 让 AST 的类型选择反映语义而不是书写形式：Number 存 int 而不是原字符串，Plus 存两个子表达式而不是 token 列表。
- 一旦有了 AST，后续所有分析（求值、优化、类型检查）都只面对这个小而清晰的数据类型，形成清晰的抽象边界。

代码示例与对比分析

场景 1：把「Fall15」这学期字符串变成有意义的数据类型——手写字符扫描 vs 文法 + 解析器生成器

❌ 错误代码

// 错误：手工按下标扫描字符串，把语法知识散落在 if 判断里
public static Semester parseSemester(String input) {
    String s = input.trim();
    int i = 0;
    while (i < s.length() && Character.isWhitespace(s.charAt(i))) i++;
    String season;
    if (s.startsWith("Fall", i)) { season = "Fall"; i += 4; }
    else if (s.startsWith("Spring", i)) { season = "Spring"; i += 6; }
    else throw new IllegalArgumentException("bad season: " + input);
    while (i < s.length() && Character.isWhitespace(s.charAt(i))) i++;
    int start = i;
    while (i < s.length() && Character.isDigit(s.charAt(i))) i++;
    String digits = s.substring(start, i);
    if (digits.length() != 2) throw new IllegalArgumentException("bad year: " + input);
    if (i != s.length()) throw new IllegalArgumentException("trailing junk: " + input);
    return new Semester(season, Integer.parseInt(digits));
}

【错误代码的问题】

规格说明被埋在代码里：合法输入的形状（season 后跟两位 year、允许空白）只能靠读代码反推，无法单独检视，违反了「清晰沟通」的目标。
极易漏掉边界：忘记检查尾部多余字符（i != s.length()）、忘记 Spring 与 Fall 之后的空白、把 [0-9] [0-9] 误写成「一或多个数字」，都可能漏检或误检。
不可修改：一旦要支持 Winter/Summer，或者要求年份恰好两位，需要重写多段索引逻辑，改动点分散。
难以测试：没有一组「这个文法的语言包含/不包含哪些串」的清单，测试用例只能靠直觉补。

✅ 正确代码

// 正确：文法独立于代码，且由解析器生成器生成匹配逻辑
// semester.g 文件内容：
//   @skip spaces {
//     semester ::= season year ;
//     season ::= 'Fall' | 'Spring' ;
//     year ::= [0-9] [0-9] ;
//   }
//   spaces ::= ' '+ ;

import edu.mit.eecs.parserlib.*;   // ParserLib（sp21 Java 版）

public enum SemesterGrammar { SEMESTER, SEASON, YEAR, SPACES }

public static Semester parseSemester(String input)
        throws IOException, UnableToParseException {
    Parser<SemesterGrammar> parser = Parser.compile(
            new File("src/semester/semester.g"), SemesterGrammar.SEMESTER);
    ParseTree<SemesterGrammar> tree = parser.parse(input);
    return convertToSemester(tree);
}

/** @param node must be a match to the semester rule
 *  @return corresponding Semester value */
private static Semester convertToSemester(ParseTree<SemesterGrammar> node) {
    if (node.name() != SemesterGrammar.SEMESTER) {
        throw new AssertionError("expected SEMESTER node");
    }
    List<ParseTree<SemesterGrammar>> seasons = node.childrenByName(SemesterGrammar.SEASON);
    List<ParseTree<SemesterGrammar>> years   = node.childrenByName(SemesterGrammar.YEAR);
    if (seasons.size() != 1 || years.size() != 1) {
        throw new AssertionError("semester should have exactly one season and one year");
    }
    return new Semester(convertToSeason(seasons.get(0)),
                        Integer.parseInt(years.get(0).text()));
}

【为什么这样更好】 文法是声明式规格：语言是什么，一眼可见，而且它就是可以被评审、被测试的文档。匹配逻辑由生成器产出，不存在手写索引漏检 trailing junk 的机会。新增 Winter 只需在文法的 season 规则里加一个选择，解析器重新生成即可。

【代码对比解说】 两种写法的真正差别不在「谁写的循环更短」，而在知识放在哪里。手写扫描把「语言的定义」拆散成若干条 if 与 i += 4，这些常量与文法知识是同一份信息的两种表示，容易不同步。文法写法把这份信息集中成一份可执行的规格。代价是必须理解一套新的工具链（.g 文件、枚举、泛型 Parser<NT>），并且文法要遵守递归下降解析器的限制（不能左递归）。在 6.031 的尺度上，这个代价是值得的。

【设计原则透视】 这是「规格说明（Reading 6）先行」的直接应用：文法即规格，转换函数即实现。转换函数还是一个典型的抽象函数：它把产生式结构（representation）映射成 Semester 这个抽象值。原子性/边界检查的思路也是 Reading 9（避免调试） 的实践——不要依赖「我小心一点」，而要让工具替你把关。

场景 2：整数表达式文法中的空白——把 number 放进 @skip 块 vs 放在块外

❌ 错误代码

// 错误：整个文法都在 @skip 块内，constant 也被跳过空白
@skip whitespace {
  expr ::= sum ;
  sum ::= primary ('+' primary)* ;
  primary ::= constant | '(' sum ')' ;
  constant ::= [0-9]+ ;
}
whitespace ::= [ \t\r\n]+ ;

// 后果：下面这行代码把 "4 2 + 2" 里的 "4 2" 错当成一个常量
ParseTree<IntegerGrammar> tree = parser.parse("4 2 + 2");
IntegerExpression expr = makeAbstractSyntaxTree(tree); // 得到 Plus(Number(4), Number(2)) ... 之后又解析出 +2

【错误代码的问题】

接受了不该接受的输入：块内的 constant 实际展开为 constant ::= (whitespace* [0-9] whitespace*)+，于是 4 2 被当成一个常量，语言边界被悄悄放宽。
缺陷极难察觉：文法「看起来」完全正常，错误只在特定输入上暴露，属于典型的「规格被悄悄改写」。
下游语义污染：AST 里出现的 Number(4)、Number(2) 与用户本意（一个叫 42 的数？还是两个数？）不符，错误会传播到求值阶段。
text() 里带空白：块内节点的 text() 会含空白，日后若要直接比较 text()，很容易写成 text() == "Fall" 之类的错误。

✅ 正确代码

// 正确：把 constant 的规则移到 @skip 块之外
@skip whitespace {
  expr ::= sum ;
  sum ::= primary ('+' primary)* ;
  primary ::= constant | '(' sum ')' ;
}
whitespace ::= [ \t\r\n]+ ;
constant ::= [0-9]+ ;

// 于是 "42 + 2" 可以解析（constant 的前后有空白由 primary 所在的块负责），
// 而 "4 2 + 2" 会被拒绝（constant 内部不允许空白）
try {
    parser.parse("42 + 2");   // OK
    parser.parse("4 2 + 2");  // 抛 UnableToParseException
} catch (UnableToParseException e) {
    // 解析失败被显式暴露，而不是产生一个语义错误的 AST
}

【为什么这样更好】 @skip 的作用范围是「块内规则右侧各成分的前后」。把 constant 移出块，就切断了「常量内部允许空白」这条被意外引入的规则，同时因为 primary 仍在块内，constant 作为一个整体仍可被空白包围——恰好是我们要的语言。

【代码对比解说】 这是一个关于抽象边界画在哪里的精彩案例。同一条 constant ::= [0-9]+，放在块内还是块外，得到的是两种不同的语言。很多学生以为 @skip 只是「美化空白的语法糖」，其实它是规格的一部分：它精确决定了哪些位置可以有空白。判断标准很简单——问自己「这个记号内部允许空白吗？」不允许，就不要把它的规则放进 @skip 块。

【设计原则透视】 对应 RI 的思想：文法是语言的表示不变量，@skip 的位置选择属于 RI 的一部分，必须与「这个语言应该长什么样」严格一致。也呼应 Reading 7（设计规格说明）：规格的强弱非常关键，过强的规格会拒绝合法输入，过弱的规格会接受非法输入——本例正是「过弱」。

场景 3：把 n 元的 sum 节点转成二叉 Plus——错误地假设孩子个数与顺序 vs 用 childrenByName 与折叠

❌ 错误代码

// 错误：假设 SUM 恰好有两个孩子，且第一个一定是数字
private static IntegerExpression makeAbstractSyntaxTree(ParseTree<IntegerGrammar> t) {
    switch (t.name()) {
        case EXPR:
            return makeAbstractSyntaxTree(t.children().get(0));
        case SUM: {
            // 文法 sum ::= primary ('+' primary)* 是 n 元的：
            // "19+23+18" 的 SUM 节点有 3 个孩子，这里只取前两个
            IntegerExpression left  = makeAbstractSyntaxTree(t.children().get(0));
            IntegerExpression right = makeAbstractSyntaxTree(t.children().get(1));
            return new Plus(left, right);
        }
        case PRIMARY:
            return makeAbstractSyntaxTree(t.children().get(0));
        case NUMBER:
            return new Number(Integer.parseInt(t.text()));
        default:
            throw new AssertionError("should never get here");
        // 注意：SUM 分支忘了 return 时，Java 会继续执行 PRIMARY 分支的代码
    }
}

【错误代码的问题】

静默丢数据："19+23+18" 的 Sum 节点有三个 Primary 孩子，这段代码只取前两个，第三个 18 被丢弃，得到错误的 AST 且不报错。
依赖孩子的个数与顺序：一旦文法改成 sum ::= primary ('+' primary)* 之外的形状，索引假设立刻失效，属于典型的表示依赖（rep exposure 的思维错误）。
switch 的贯穿风险：若某个 case 忘记 return，执行会落入下一个 case，产生难以定位的错误结果。
无法处理 n = 1 的情形：单个数字 42 的 Sum 只有一个孩子，get(1) 直接抛 IndexOutOfBoundsException。

✅ 正确代码

/**
 * Convert a parse tree into an abstract syntax tree.
 *
 * @param parseTree constructed according to the grammar in IntegerExpression.g
 * @return abstract syntax tree corresponding to parseTree
 */
private static IntegerExpression makeAbstractSyntaxTree(final ParseTree<IntegerGrammar> parseTree) {
    switch (parseTree.name()) {
        case EXPR: // expr ::= sum;
        {
            final ParseTree<IntegerGrammar> child = parseTree.children().get(0);
            return makeAbstractSyntaxTree(child);
        }

        case SUM: // sum ::= primary ('+' primary)*;
        {
            final List<ParseTree<IntegerGrammar>> children =
                    parseTree.childrenByName(IntegerGrammar.PRIMARY);
            IntegerExpression expression = makeAbstractSyntaxTree(children.get(0));
            for (int i = 1; i < children.size(); ++i) {
                expression = new Plus(expression, makeAbstractSyntaxTree(children.get(i)));
            }
            return expression;   // n 元折叠成左结合的二叉 Plus
        }

        case PRIMARY: // primary ::= number | '(' sum ')';
        {
            final ParseTree<IntegerGrammar> child = parseTree.children().get(0);
            // 检查实际匹配的是哪一个选择分支（number 还是 sum）
            switch (child.name()) {
                case NUMBER:
                    return makeAbstractSyntaxTree(child);
                case SUM:
                    return makeAbstractSyntaxTree(child); // 本例两种情形处理相同
                default:
                    throw new AssertionError("should never get here");
            }
        }

        case NUMBER: // number ::= [0-9]+;
        {
            final int n = Integer.parseInt(parseTree.text());
            return new Number(n);
        }

        default:
            throw new AssertionError("should never get here");
    }
}

【为什么这样更好】 childrenByName(PRIMARY) 直接表达「我要的是这条产生式里所有的 PRIMARY 孩子」，把 + 号这类终结符（它们本来也不出现在 children() 里）和结构性细节一起屏蔽掉；循环折叠对任意 n ≥ 1 都成立，"19+23+18" 得到左结合的 Plus(Plus(Number(19), Number(23)), Number(18))。每个分支都 return 或 throw，switch 绝不贯穿。

【代码对比解说】 关键洞察是：解析树的形状是文法的直接映射，不是你的 AST 想要的形状。文法 sum ::= primary ('+' primary)* 是 n 元的，而 Plus 是二元的（恰好左右各一）。转换函数就是这两者之间的翻译层，翻译策略（本例取左结合）必须是有意识的选择，而不是从「孩子只有两个」的错觉里无意产生的。若希望解析树本身至多二元，可以把文法改成 sum ::= primary \| primary '+' sum ;（右结合），此时 SUM 孩子最多两个——但要注意这时就不能再用 sum ::= sum '+' sum，那会引入左递归。

【设计原则透视】 这是 Reading 17（递归数据类型） 与 Reading 10（ADT） 的交汇：AST 的 datatype definition 决定了取值的集合，而转换函数必须覆盖整个取值集合。childrenByName 的使用体现了「不要暴露表示的细节给调用者」——用语义查询而非下标访问。同时注意函数里对「不可能情况」抛 AssertionError，是 RI 的外部化表达。

场景 4：从 season 节点取季节——用 == 比较字符串 vs 用 equals，并正确处理 @skip 带来的空白

❌ 错误代码

// 错误一：用 == 比较字符串内容
static Season convertToSeason(ParseTree<SemesterGrammar> node) {
    if (node.name() != SemesterGrammar.SEASON) throw new AssertionError();
    return node.text() == "Fall" ? Season.FALL : Season.SPRING;   // 永远为 false！
}

// 错误二：即使改用 equals，块外规则拿到的 text() 可能带空白
static Season convertToSeason2(ParseTree<SemesterGrammar> node) {
    return node.text().equals("Fall") ? Season.FALL : Season.SPRING;
    // 当 season 规则也在 @skip 块内时，node.text() 可能是 "Fall " 或 " Fall"，比较失败
}

【错误代码的问题】

== 比较的是引用：node.text() 返回新构造的 String，与字面量 "Fall" 不是同一对象，判断恒为 false，于是 convertToSeason 永远返回 SPRING——一个完全不报错的错误答案。
忽略 text() 的空白语义：text() 返回「本子树匹配到的原始子串」；如果这条规则在 @skip 块内，首尾的空白也在匹配范围内，equals 会失败。
失败方式恶劣：两个错误都表现为「结果错但不抛异常」，属于典型的 silent bug，测试若只覆盖一种输入就发现不了。

✅ 正确代码

/** @param node must be a match to the season rule
 *  @return corresponding Season value */
static Season convertToSeason(ParseTree<SemesterGrammar> node) {
    if (node.name() != SemesterGrammar.SEASON) {
        throw new AssertionError("expected a SEASON node");
    }
    final String text = node.text();
    // 视 season 规则是否位于 @skip 块内决定是否需要 trim
    return text.trim().equals("Fall") ? Season.FALL : Season.SPRING;
}

【为什么这样更好】 用 equals 比较内容；trim() 把「这条规则是否在 @skip 块内」这个文法细节与比较逻辑解耦，使函数在两种文法下都正确。更稳妥的做法是针对真正的语义分支写测试："Fall15"、" Spring 23 "、"Spring 9 9"（应当被拒绝）都要覆盖。

【代码对比解说】 这个例子把两讲的内容缝合在一起：== vs equals 是 Reading 15（相等性） 的核心教训，而 text() 是否含空白是本讲 @skip 语义的直接后果。学生常见的第三种错误是「看到比较失败就加 trim()」，却不理解为什么——如果 season 规则在块外，text() 本来就不含空白，trim() 只是无害的冗余；如果在块内，trim() 就是必需的。理解原因，才能在文法变化时正确判断。

【设计原则透视】 ParseTree 的规格（spec）明确说明 text() 是「原串的子串」，这不是「规范化后的记号」，调用者不能假设它已去除空白——典型的规格边界问题。而 == 的错误则说明「相等性语义」必须依规约（Reading 15 中的等价关系）来用，不能凭语法直觉。

场景 5（补充）：左递归文法 vs 用重复改写

❌ 错误代码

// 错误：左递归，递归下降解析器会陷入无限递归
sum ::= number | sum '+' number ;
number ::= [0-9]+ ;

【错误代码的问题】

解析 sum 时先要匹配 sum 本身，问题规模不缩小，递归永不终止（ParserLib 会以异常失败并指出违规的非终结符）。
间接左递归同样致命：sum ::= number \| thing number ; thing ::= sum '+' ; 依然把 sum 放在最左位置。
这类文法是自然书写顺序的产物（人写算式就是「左边再加一个数」），所以学生很容易不自觉写出来。

✅ 正确代码

// 正确：用重复 (*) 表达「若干个 number，用 + 连接」
sum ::= (number '+')* number ;
number ::= [0-9]+ ;

【为什么这样更好】 重复算子 * 由解析器生成器实现为一个循环，不再需要「先递归到自己」；同时它保留了「至少一个 number」的语义，语言集合与直觉一致。

【代码对比解说】 消除左递归的一般手法是引入尾递归/迭代；在 ParserLib 的语境下最简单的是把左递归改写成 (X op)* X 形式。注意代价：改写会改变解析树的形状，因而转换函数也要跟着改（n 元折叠的问题又回来了）。

【设计原则透视】 这是「工具的抽象代价」：声明式文法并非万能，生成器有它自己的前置条件（grammar must not be left-recursive）。程序员必须理解抽象边界之下的实现约束，才能正确使用抽象（Reading 11 的思想：抽象不隐藏它承诺之外的义务）。

与其他设计原则的关联

Reading 18（正则表达式与文法）：本讲是它的直接延续。正则表达式适合描述词法（token 的形状，如 [0-9]+），文法适合描述语法（token 如何组成结构）；@skip whitespace 就是把「词法层面的空白」从语法层剔除的机制。ParserLib 语法里「字面字符必须加引号」也是相对普通正则的一处差异。
Reading 17（递归数据类型）：AST 就是递归 ADT。IntegerExpression = Number(n:int) + Plus(left, right) 的 datatype definition 直接决定了转换函数要处理的 case 集合；本讲是递归数据类型的第一次真实应用。
Reading 10（抽象数据类型）与 Reading 11（抽象函数、表示不变量）：转换函数本质上是抽象函数：把「由文法定义的表示结构」映射为「表达式这一抽象值」。解析树的结构约束（哪些孩子可能出现、@skip 的孩子不出现）就是它的 RI。
Reading 6/7（规格说明与设计规格）：文法是文本输入的声明式规格，@skip 的位置决定规格的强弱；转换函数则需要写清前置条件（「输入是由本文法生成的解析树」）与后置条件（「返回对应的 AST」）。
Reading 15（相等性）：text().equals("Fall") 与 text() == "Fall" 的差别是本讲最常见的 bug 之一，正确处理它依赖相等性的等价关系概念。
Reading 20（回调与 GUI）与 Reading 25/21（并发）：解析器常被用在事件处理中——用户在 GUI 里输入一段表达式，回调里调用 parser.parse(...)。这时异常处理与执行时间（不要阻塞事件循环）就成为新的关注点。
Reading 26/27（Little Languages）：本讲是「解释器/小语言」项目的基础：文法 → 解析树 → AST → 求值器，正是后续课程与 psets 中反复出现的流水线。

关键要点

先写文法，再写代码：任何「解析文本」的任务都先问「这个语言是什么」，用文法把它写下来；匹配逻辑交给解析器生成器，你只负责文法与「解析树 → AST」的翻译。
@skip 的位置是规格的一部分：它决定哪些位置允许空白；记号内部不允许空白时，该记号的规则必须放在 @skip 块外。
转换函数必须跟随文法结构：一个 case 对应一条产生式，每个 case 都要 return 或 throw，并且要处理 n 元结构到二元 AST 的折叠这类形状差异。
了解你的解析器的限制：递归下降解析器不能处理左递归（包括间接左递归），用 * 改写；贪婪匹配是更根本的局限，需要靠文法设计规避。
解析的终点是有类型的值：把 ParseTree 尽早转成 AST，之后所有代码都面对小而清晰的递归数据类型，而不是面对解析树的表示细节。

常见陷阱与注意事项

把 number/constant 这类记号规则放进 @skip 块 → 记号内部允许空白，"4 2 + 2" 被错误接受，语言边界被悄悄放宽。
用 == 比较 text() 与字符串字面量 → 比较的是引用，判断恒为 false，得到静默的错误结果（永远走另一个分支）。
假设 SUM（n 元）节点恰好有两个孩子 → 对 "19+23+18" 静默丢弃第三个操作数，或对单个数字抛 IndexOutOfBoundsException。
在 switch 的某个 case 忘记 return → Java 从匹配的 case 向下贯穿，执行到下一个 case 的代码，产生看似莫名其妙的行为。
写出左递归文法（含间接左递归） → 递归下降解析器无限递归，ParserLib 以异常失败；应改写为 (X op)* X 形式。
与解析器 API 打交道时疏忽：枚举里漏掉非终结符（WHITESPACE 这类只在 @skip 中使用的也必须列出）或误把终结符写进去 → compile 报缺失规则；忘记 parse/compile 会抛受检异常（IOException、UnableToParseException）→ 代码无法编译，或用空 catch 吞掉解析失败，让非法输入以「默认值」的形式流进系统。

思考题（带答案）

问题 1：给定文法

@skip spaces {
  semester ::= season year ;
}
season ::= 'Fall' | 'Spring' ;
year ::= [0-9] [0-9] ;
spaces ::= ' '+ ;

（注意 season 与 year 的规则都在 @skip 块外）请问 " Spring 23 " 能否被匹配？如果 @skip 块把 season 和 year 也包进去，答案会改变吗？这对 convertToSeason 的实现有什么影响？

答案：@skip spaces { semester ::= season year ; } 只对 semester 这条规则右侧的成分生效，也就是说 semester 右侧的 season 与 year 的前后允许出现空格，因此 " Spring 23 " 可以被匹配（开头的空白属于 semester 之前的位置，也会被跳过）。如果 season、year 的规则本身也被移入 @skip 块，那么 season 的 text() 就可能包含首尾空白（如 "Spring "），convertToSeason 中直接 text().equals("Fall") 就会失败，必须写成 text().trim().equals("Fall")。这正是课程练习里「To every thing… there is a season」两组题目的差别：@skip 的覆盖范围改变了解析树节点 text() 的内容，从而改变了转换代码的正确写法。

问题 2：为什么 sum ::= primary ('+' primary)* 的解析树中，Sum 节点的孩子不包含 '+'，而 primary ::= constant \| '(' sum ')' 的 Primary 节点的孩子可能是 Sum 也可能是 Constant？请从「终结符/非终结符」与「产生式展开」的角度解释，并说明这对转换函数意味着什么。

答案：解析树的每个节点对应一条产生式的展开，节点的名字来自左侧的非终结符；孩子则是右侧被匹配到的成分。终结符（'+'、'('、')'）在 ParserLib 的解析树里不单独成节点，因此不会出现在 children() 中；childrenByName(PRIMARY) 恰好等价于「对 children() 做 filter，只保留名字为 PRIMARY 的孩子」。所以 Sum 的孩子只有一串 Primary，+ 的存在只能从 text() 或孩子的个数推断出来。而 Primary 的孩子是「实际匹配的那一个选择分支」对应的非终结符节点：匹配到 constant 时孩子是 Constant，匹配到 '(' sum ')' 时孩子是 Sum（括号作为终结符不出现）。对转换函数的直接后果是：处理 Primary 必须用 switch 判断孩子的 name() 来区分分支（并且每个分支都要 return 或 throw），而处理 Sum 则应当用 childrenByName 取出所有 Primary 再折叠，不能假设固定个数。

问题 3：下面的文法为什么不能让 ParserLib 正常工作？请给出两种修改方案，并说明它们会如何改变解析树的形状。

sum ::= number | sum '+' number ;
number ::= [0-9]+ ;

答案：这是左递归：sum 的一个选择分支 sum '+' number 把 sum 放在最左位置。递归下降解析器在匹配 sum 时必须依次尝试每个选择，而尝试 sum '+' number 的第一步又要匹配 sum，问题规模不缩小，递归无法终止，ParserLib 会以 UnableToParseException 失败并指出违规的非终结符。修改方案一：用重复消除左递归，sum ::= (number '+')* number ;，此时 Sum 节点是 n 元的（孩子全是 Number），解析树变「平」，转换函数需要把 n 元折叠成二叉 AST。修改方案二：改成右递归，sum ::= number \| number '+' sum ;（或等价地 sum ::= number ('+' sum)? ;），这不是左递归，可以正常工作；此时解析树是右倾的（每个 Sum 最多两个孩子），得到的 AST 天然是右结合的 Plus(Number(19), Plus(Number(23), Number(18)))，与方案一得到的左结合结果语义不同——这说明「消除左递归的方式」会同时决定结合性，必须与语言规格保持一致。

Share on

Bluesky Facebook LinkedIn Mastodon X (formerly Twitter)

Runguo Li