Reading 18: 正则表达式与文法（Regular Expressions & Grammars）

目录 · ← l17 · l19 →

Reading 18: 正则表达式与文法（Regular Expressions & Grammars）

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

概述

本讲解决的是如何为「字符序列」写规格这一问题。很多程序模块以字节序列或字符序列作为输入或输出：存于内存时叫字符串（string），流入流出模块时叫流（stream）；具体形式可能是字符串本身、磁盘文件（此时规格叫文件格式 file format）、网络消息（规格叫线协议 wire protocol）、或用户在控制台输入的命令（规格叫命令行接口 command line interface）。课程给出的工具是文法（grammar）：它不仅能区分合法与非法序列，还能把序列解析（parse）成程序可操作的数据结构，这个数据结构往往就是 Reading 17 所讲的递归数据类型。文法的一个特殊子类叫正则表达式（regular expression, regex），它除用于规格与解析外，还是各种字符串处理任务（拆分、抽取、替换）的常用工具。

与三大目标的关系如下。Safe from bugs：文法与正则表达式是字符串和流的声明式规格（declarative specification），可以被库与工具直接使用；这种规格通常比手写的解析代码更简单、更直接、更不容易出错。Easy to understand：文法把序列的形状以比手写解析代码更容易理解的形式固定下来；但正则表达式往往不易理解，因为它把本可读的正则文法压缩成了一行。Ready for change：文法很容易修改，正则表达式则难得多，因为复杂的正则表达式晦涩难懂——这也是本讲反复强调「能用带名字的非终结符就用文法」的原因。

核心概念与设计原则详解

文法、产生式、终结符与非终结符（Grammars, Productions, Terminals, Nonterminals）

• 定义与目的：文法（grammar）是描述字符串集合的紧凑表示：它定义一组字符串，用来判断某个序列是否属于该集合，并为解析提供结构依据。
• 直观解释（”它是什么？”）：把文法想成一份「填词游戏」的规则表：一部分词是固定不能变的（终结符），另一部分是可以继续展开的（非终结符），最终展开到只剩固定词时，就得到了一条合法字符串。
• 关键规则与最佳实践：
  • 终结符（terminals）是文法中的字面字符串，之所以叫终结符是因为它们不能再被展开；书写时通常加引号，如 'http' 或 ':'。
  • 文法由一组产生式（productions）描述，每条产生式定义一个非终结符（nonterminal）。可以这样类比：非终结符像一个代表某组字符串的变量，产生式则是这个变量用其他变量（非终结符）、运算符与常量（终结符）写出的定义；在表示字符串的树中，非终结符是内部节点。
  • 产生式的形式是 非终结符 ::= 由终结符、非终结符与运算符构成的表达式。
  • 文法中要指定一个非终结符作为根（root，也叫 start，甚至直接叫 S）；文法识别的字符串集合正是匹配根非终结符的那些字符串。课程建议给根取可读的名字，如 url、html、markdown。
  • 单例文法可以只有一条产生式，右侧全是终结符：url ::= 'http://mit.edu/' 只识别这一个字符串。
  • 用法示例：url ::= 'http://' hostname '/' 与 hostname ::= 'mit.edu' \| 'stanford.edu' \| 'google.com' 合起来正好表示三个字符串 http://mit.edu/、http://google.com/、http://stanford.edu/。

三个核心运算符：重复、连接、选择（Repetition, Concatenation, Union）

• 定义与目的：产生式右侧用运算符把终结符与非终结符组合起来。最重要的三个运算符是重复 *、连接（不用符号，仅用空格）与选择 \|，它们足以表达任意正则语言。
• 直观解释（”它是什么？”）：* 是「任意多份」，连接是「一份接一份」，\| 是「二选一」。三者组合起来就像用最少的积木搭出所有形状。
• 关键规则与最佳实践：
  • 重复：x ::= y*，x 匹配零个或多个 y。
  • 连接：x ::= y z，x 匹配「y 后接 z」。
  • 选择（也叫 alternation，交替）：x ::= y \| z，x 匹配 y 或 z。
  • 优先级约定：后缀运算符（如 *）优先级最高、最先应用；连接次之；选择 \| 优先级最低、最后应用。用括号可以覆盖优先级：m ::= a (b\|c) d 匹配「a，然后 b 或 c，然后 d」；x ::= (y z \| a b)* 匹配零个或多个「yz 或 ab」对。
  • 用 * 要当心它允许零次：word ::= letter* 会让整个文法也能匹配 http://./ 这样并不合法的 URL；让单词至少一个字母的笨办法是 word ::= letter letter*。

更多文法运算符：语法糖（More Grammar Operators）

• 定义与目的：除三个核心运算符外，还有一批语法糖（syntactic sugar）——它们都等价于核心运算符的组合，只是写法更紧凑，用于精确表达「出现次数」与「字符集合」。
• 直观解释（”它是什么？”）：就像 * 的亲戚：? 是「零或一次」，+ 是「一次或多次」，{n,m} 是「区间次数」，而 [...] 是「一个字符的候选清单」。
• 关键规则与最佳实践：
  • x ::= y? 表示零或一次，等价于 x ::= \| y（注意这里有一个空串分支）。
  • x ::= y+ 表示一次或多次，等价于 x ::= y y*。
  • x ::= y{3} 等价于 x ::= y y y；x ::= y{1,3} 等价于 x ::= y \| y y \| y y y；x ::= y{,4} 等价于 x ::= \| y \| y y \| y y y \| y y y y（含空串）；x ::= y{2,} 等价于 x ::= y y y*。
  • 字符类（character class） x ::= [aeiou] 等价于 x ::= 'a'\|'e'\|'i'\|'o'\|'u'；用 - 可以写字符范围：[a-ckx-z] 等价于 'a'\|'b'\|'c'\|'k'\|'x'\|'y'\|'z'；反向字符类（inverted character class） [^a-c] 匹配不在括号中列出的单个字符（即 'd'\|'e'\|...\|'!'\|'@'\|... 等所有其他字符）。
  • 有了这些运算符，word 可以写得既紧凑又精确：word ::= [a-z]+。

文法中的递归（Recursion in Grammars）

• 定义与目的：要表达「主机名可以有多段」「可以带可选端口号」这类结构（例如 http://didit.csail.mit.edu:4949/），产生式右侧需要递归地引用自己。递归使文法能表达无界的嵌套与重复结构。
• 直观解释（”它是什么？”）：就像一棵树的画法——「主机名 = 单词 + ‘.’ + 主机名」，一直向右展开，直到用 base case「单词 + ‘.’ + 单词」收尾。
• 关键规则与最佳实践：
  • 递归写法：hostname ::= word '.' hostname \| word '.' word；其中 word '.' word 是 base case，word '.' hostname 是 递归步骤。它允许任意多段（≥2 段）的主机名。
  • 用重复运算符可以消去这种递归：hostname ::= (word '.')+ word，两者识别的语言相同，但后者没有递归。文法中的递归有时能被运算符消掉，但并非总能（HTML 的嵌套标签就不能）。
  • 完整 URL 文法：url ::= 'http://' hostname (':' port)? '/'、hostname ::= word '.' hostname \| word '.' word、port ::= [0-9]+、word ::= [a-z]+。
  • 文法通常不表达数值范围约束：port 允许任何数字串，而「端口必须在 0 到 65535（2¹⁶−1）之间」这样的约束应当在使用该文法的程序里检查，而不是写进文法。
  • 想继续推广还可以：支持更多协议（https、ftp，写法如 protocol ::= ('http' 's'?) \| 'ftp'）、把末尾的 / 推广成斜杠分隔的路径、允许主机名使用完整的合法字符集而不只是 a-z。

解析树（Parse Trees）

• 定义与目的：把文法与字符串匹配的过程记录下来，就得到解析树：它展示字符串的哪些部分对应文法中的哪些部分，是把线性字符串转成结构化数据（递归数据类型）的桥梁。
• 直观解释（”它是什么？”）：解析树像句子的语法分析图：叶子是实际写出来的字，内部节点是「这些字一起扮演了什么角色」。
• 关键规则与最佳实践：
  • 解析树的叶子标注终结符，代表被解析出的字符串片段；它们没有子节点、不能再展开；把所有叶子按顺序拼接起来就能还原原字符串。
  • 解析树的内部节点标注非终结符；某个非终结符节点的直接子节点必须符合该非终结符产生式的模式。例如主机名节点的子节点必须符合 word '.' word。
  • 递归文法会生成更深的树：递归版 hostname ::= word '.' hostname \| word '.' word 会为每个 hostname 生成一个内部节点，而非递归版 hostname ::= (word '.')+ word 只生成一个 hostname 节点（其下是若干 word 节点）。同一个字符串在两个文法下会得到不同形状的解析树，节点数也不同。
  • 解析树的结构直接对应 Reading 17 的递归数据类型，因此「每个 variant 一个 case」的实现方式可以天然地遍历它。

正则文法与正则表达式（Regular Grammars & Regular Expressions）

• 定义与目的：正则文法有一种特殊性质：把除根之外的每个非终结符都用其右侧内容替换掉，就能把它化简成只有根的一条产生式，右侧只剩终结符与运算符。这种化简后的紧凑写法就叫正则表达式。
• 直观解释（”它是什么？”）：文法像「带中间变量的多步算式」，正则表达式像「把所有中间变量代入后的最终一行」——更短，但也更难读，因为中间变量的名字（那些说明了每部分含义的非终结符）全都不见了。
• 关键规则与最佳实践：
  • 化简示例：URL 文法可以化简为 url ::= 'http://' ([a-z]+ '.')+ [a-z]+ (':' [0-9]+)? '/'；Markdown 文法可以化简为 markdown ::= ([^_]* \| '_' [^_]* '_' )*。
  • 正则表达式去掉终结符的引号、去掉终结符与运算符之间的空格，只剩下终结符字符、用于分组的括号与运算符字符：Markdown 的正则表达式就是 ([^_]*\|_[^_]*_)*。
  • 正则表达式远不如原文法可读，因为它缺少了说明各子表达式含义的非终结符名字；但许多编程语言只有正则库而没有文法库，而且正则匹配比文法匹配快得多。
  • 常见的额外元字符：. 匹配任意单个字符（视库而定可能不含换行）；\d 等价于 [0-9]；\s 匹配空白字符（空格、制表、换行）；\w 匹配单词字符（含下划线），等价于 [a-zA-Z_0-9]。
  • 反斜杠用于「转义」运算符或特殊字符使其按字面匹配：常见的需要转义的字符有 \. \( \) \* \+ \| \[ \] \\。例如 URL 正则里的 . 是终结符，必须写成 \.：http://([a-z]+\.)+[a-z]+(:[0-9]+)?/。
  • 另一种转义方式是把特殊字符放进字符类括号：用 [.] 也能匹配字面点号。在字符类内部，大多数特殊字符失去特殊含义而按字面处理；但字符类语法自身的特殊字符 [、]、^、-、\ 仍需反斜杠转义。

在实践中使用正则表达式（Regular Expressions in Practice）

• 定义与目的：正则是日常编程的必备工具；在 Java 中，字符串操作可以使用 String.split、String.matches、String.replaceAll，更需要控制力时使用 java.util.regex.Pattern 与 java.util.regex.Matcher。
• 直观解释（”它是什么？”）：Pattern 是「编译好的规格」，Matcher 是「拿着这份规格在某个具体字符串上走的匹配器」——前者可反复使用，后者记录匹配进度与捕获结果。
• 关键规则与最佳实践：
  • 把连续空格替换为单个空格：String singleSpacedString = s.replaceAll(" +", " ");（sp22 的 TypeScript 版本写作 s.replace(/ +/g, " ")，其中 g 表示全局匹配；Java 的 replaceAll 本身就是全局替换）。
  • 匹配 URL：if (s.matches("http://([a-z]+\\.)+[a-z]+(:[0-9]+)?/")) { ... }。注意这里出现了双重反斜杠：先写 \. 让正则把点号当字面量，再把反斜杠写成 \\ 以躲过 Java 字符串的转义——「频繁需要双反斜杠转义让正则更加难读」是课程的原话。
  • 抽取日期 "2020-03-18" 的各个部分：用 Pattern.compile("(?<year>\\d{4})-(?<month>\\d{2})-(?<day>\\d{2})")，再用 Matcher 的 matches() 与 group("year") 取值。(?<name>...) 是命名捕获组（named capturing group）：它匹配括号内的正则，并把匹配到的字符串赋给名字 name。注意这里的 ? 不是「零或一次」的意思——紧跟在左括号之后，它表示这组括号有特殊含义，而不仅仅是分组。
  • Matcher.group(name) 在匹配成功后返回对应片段：把上面的正则匹配到 "2025-03-18" 上，group("year") 得到 "2025"、group("month") 得到 "03"、group("day") 得到 "18"。
  • 匹配范围要明确：Matcher.matches() 要求整串与正则匹配，而 Matcher.find() 只要求在串中找到一个匹配子串；把二者混用是最常见的语义 bug 之一。
  • 字符串解析示例：Pattern.compile("[0-9]+ .* (Rd\|St\|Ave\|Ln)") 可以匹配 "77 Rose Court Ln"，把各部分改写成命名捕获组 (?<houseNumber>[0-9]+) (?<streetName>.*) (?<streetType>Rd\|St\|Ave\|Ln) 就能解析出 "77"、"Rose Court"、"Ln" 三段。要注意空格在正则中是有含义的，不能随意增删。
  • 补充说明：Pattern 是不可变且线程安全的，可以安全地声明为 static final 常量并复用；Matcher 保存匹配状态、不是线程安全的，应当每次匹配时新建。频繁使用 String.matches/String.split 会在每次调用时重新编译正则，带来不必要的开销。

上下文无关文法与正则表达式的表达能力对比（Context-Free Grammars）

• 定义与目的：用本讲的这套文法系统能表达的语言统称为上下文无关（context-free）语言。并非所有上下文无关语言都是正则的：有些文法无法化简为「单条非递归产生式」。
• 直观解释（”它是什么？”）：正则表达式像一台「没有记忆」的机器，它只能数「有多少个」，不能数「配对了几层」；而嵌套结构要求「记住已经打开了几个括号」，这就需要递归（也就是上下文无关文法）。
• 关键规则与最佳实践：
  • HTML（简化版）文法不是正则的：html ::= ( normal \| italic )*、italic ::= '<i>' html '</i>'、normal ::= text、text ::= [^<>]*。替换非终结符后得到 html ::= ( [^<>]* \| '<i>' html '</i>' )*，右侧对 html 的递归引用无法消除，也无法简单换成重复运算符。
  • 对比 Markdown：italic ::= '_' normal '_' 中的 normal 不会递归回到 markdown，因此可以化简为正则 ([^_]*\|_[^_]*_)*——也就是说，同一个「斜体」概念，Markdown 版本可有正则表达，HTML 版本不能，差别只在定界符之间匹配的是哪个非终结符。
  • 一般规律：任何具有嵌套结构的语言（嵌套括号、嵌套花括号、成对标签）都是上下文无关但非正则的。
  • 大多数编程语言的文法都是上下文无关的。课程给出的 Java statement 产生式片段就包含 '{' statement* '}'、'if' '(' expression ')' statement ('else' statement)?、'while' '(' expression ')' statement、'synchronized' '(' expression ')' '{' statement* '}'、'try' ... 等分支——它们都用「每个 variant 一行」的方式写出了语句的全部形状（sp22 的 TypeScript 版本对应地列出 '{' statement* '}'、'if' ...、'for' ...、'switch' ... 等）。
  • 决策建议：需要嵌套结构 → 用文法（配解析器，见 Reading 19）；只需要扁平的字符模式匹配/抽取/替换 → 用正则表达式。

代码示例与对比分析

场景 1：校验 URL——手写字符扫描 vs 声明式正则规格

❌ 错误代码

public class Urls {
    /**
     * @param s a string
     * @return true iff s is a legal http URL
     */
    public static boolean isHttpUrl(String s) {
        // 错误：用 startsWith/indexOf/substring 手写「解析」，规格散落在控制流里
        if (!s.startsWith("http://")) {
            return false;
        }
        int slash = s.indexOf('/', 7);
        if (slash < 0) {
            return false;
        }
        String host = s.substring(7, slash);
        return host.length() > 0;   // 只要主机名非空就算合法？
    }
}

【错误代码的问题】

1. 检查远弱于规格："http://this is not a host/"、"http://??/"、"http://A_B/" 都会被判为合法，因为它只检查了前缀、斜杠位置与主机名非空；主机名字符集、端口号格式完全没有校验。
2. 逻辑无法复用：这段代码只能回答「是/否」，无法把主机名、端口、路径抽取出来；需要解析时只能再写一遍（于是两份实现必然漂移）。
3. 规格与实现混在一起：真正的规则（主机名由若干 [a-z]+ 段用 . 连接、端口是可选的数字串、末尾是 /）只存在于 if 语句的排列中，读代码的人必须自己反推规则，修改规则时也没有单一改动点。

✅ 正确代码

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Urls {
    // 把文法/正则作为一条可读的、可复用的规格常量：
    //   url      ::= protocol '://' hostname (':' port)? '/'
    //   protocol ::= ('http' 's'?) | 'ftp'
    //   hostname ::= ([a-z]+ '.')+ [a-z]+
    //   port     ::= [0-9]+
    private static final Pattern URL = Pattern.compile(
        "(?<protocol>(?:https?|ftp))://" +
        "(?<host>(?:[a-z]+\\.)+[a-z]+)" +
        "(?::(?<port>[0-9]+))?/");

    /**
     * @param s a string
     * @return true iff the whole string matches the URL grammar above
     */
    public static boolean isHttpUrl(String s) {
        return URL.matcher(s).matches();     // matches() 要求整串匹配
    }

    /**
     * @param s a string
     * @return the host part of s, or empty if s is not a URL of that form
     */
    public static java.util.Optional<String> hostOf(String s) {
        Matcher m = URL.matcher(s);
        return m.matches() ? java.util.Optional.of(m.group("host"))
                           : java.util.Optional.empty();
    }
}

【为什么这样更好】 校验与抽取共用同一份规格：Pattern 是编译好的声明式规格，matches() 回答「是否合法」，group("host") 回答「其中主机名是什么」，两者不可能不一致。规则以命名捕获组的形式写在正则里，与课程文法逐条对应，读代码时能直接对照 url ::= protocol '://' hostname (':' port)? '/'；要放宽或收紧规则（比如允许 ftp、允许大写字母）只需改一处常量。

【代码对比解说】 手写扫描的代码是命令式的：它描述「先看前缀、再找斜杠、再取子串」，读者必须执行一遍才能知道规则是什么；正则版本是声明式的：它直接陈述「合法 URL 长什么样」。此外，手写版本的失败模式是静默的过宽匹配（把非法串判成合法），而正则版本的失败模式通常是明确的（不匹配），配合单元测试很容易覆盖。注意两组 (?:...) 是非捕获组（补充说明：Java 正则的语法扩展），用它可以避免为不想抽取的部分创建多余的捕获组；命名捕获组 (?<name>...) 中的 ? 不是量词，而是「这组括号有特殊含义」的标记。

【设计原则透视】 文法/正则在这里扮演的是 Reading 06/07 中方法规格的角色：isHttpUrl 的规格可以写成「当且仅当 s 匹配上述文法时返回 true」，规格与实现分离且可独立评审。从 Reading 17 的角度看，课程文法图中的 url、hostname、port、word 节点正是解析树的非终结符节点，而解析树的递归结构可以直接实现为一个递归数据类型；与之对应的 Java 代码则是「每个 variant 一个 case」的操作集。把 Pattern 声明为 static final 并用 matches() 判定整串，还体现了「让失败可预测」的调试友好性（Reading 09）。

场景 2：忘记转义 .——正则比规格更宽松

❌ 错误代码

import java.util.regex.Pattern;

public class Hosts {
    // 错误：本意是「若干由点号分隔的小写单词」，但 . 没有转义，
    // 它变成了「任意单个字符」的元字符
    private static final Pattern BAD =
        Pattern.compile("http://([a-z]+.)+[a-z]+");

    public static boolean looksLikeUrl(String s) {
        return BAD.matcher(s).matches();
    }
}

【错误代码的问题】

1. 语义被悄悄放宽：[a-z]+. 的含义是「一个或多个小写字母后跟任意一个字符」，因此 "http://abcXdefYghi"、"http://aaa$bbb" 都会被判为合法——规格说「点号分隔」，实现却接受任何分隔符。
2. 这类错误不会被编译器或类型检查发现，测试若只覆盖「正常 URL」就永远看不到差异；而一旦下游据此放行数据，注入类风险随之而来。
3. 因为 . 也在 [a-z]+ 之外，它还可能吞掉本应属于后续部分（如端口、斜杠）的字符，使整串匹配（matches()）的结果与预期完全不符，排错时会先怀疑「正则库有问题」。

✅ 正确代码

import java.util.regex.Pattern;

public class Hosts {
    // 正确：\. 让点号按字面匹配；Java 字符串里写成 "\\."
    private static final Pattern URL = Pattern.compile(
        "http://([a-z]+\\.)+[a-z]+(:[0-9]+)?/");

    public static boolean looksLikeUrl(String s) {
        return URL.matcher(s).matches();
    }
}

【为什么这样更好】 用 \. 明确告诉正则引擎「这里要匹配一个真正的点号」，于是非法分隔符立即被拒绝。也可以写成 [.]：在字符类括号内部，大多数特殊字符失去特殊含义，因此 [.] 与 \. 等价，而且不必写双反斜杠——这在可读性上略有优势。规格与实现的差距被消除，matches() 的判定结果与文法描述严格一致。

【代码对比解说】 这一组说明「正则表达式不是自然语言，每个字符都有含义」：[a-z]+. 与 [a-z]+\. 只差一个反斜杠，语义却从「小写字母加点号」变成「小写字母加任意字符」。Java 还叠加了第二层转义：字符串字面量里的 \ 本身要写成 \\，于是正则的 \. 在源码中必须写成 "\\."；这正是课程原文所说的「频繁需要双反斜杠转义让正则更难读」。相比之下，如果这段规格用文法写（hostname ::= (word '.')+ word），点号被引号括起来，就完全不存在转义问题——这是文法在易理解性上的直接优势。

【设计原则透视】 这组对比是「规格—实现一致性」问题的正则版本：正则表达式本身就是规格，但它是一门隐晦的规格语言，一处转义缺失就让规格与作者意图分岔，且没有任何工具会警告。从三大目标看，它伤害的是 Safe from bugs（静默放宽）与 Ready for change（难以审阅、难以修改）；而把 Pattern 作为常量集中声明、并在 Javadoc 里写出对应的文法（如 hostname ::= (word '.')+ word），可以让规格与实现互相对照，这是「文档即规格」的实践。补充说明：Pattern 线程安全，把它放进 static final 是安全且高效的；若把 Matcher 也做成共享字段，就会引入 Reading 21/23 才讨论的并发问题。

场景 3：文法写得过宽——letter* 允许空串导致匹配非法 URL

❌ 错误代码

public class Words {
    // 文法：
    //   url      ::= 'http://' hostname '/'
    //   hostname ::= word '.' word
    //   word     ::= letter*          <- 错误：允许「零个字母」
    // 对应的正则：
    private static final java.util.regex.Pattern URL =
        java.util.regex.Pattern.compile("http://[a-z]*\\.[a-z]*/");

    public static boolean isUrl(String s) {
        return URL.matcher(s).matches();
    }
}

【错误代码的问题】

1. word ::= letter* 匹配零个或多个字母，因此 hostname 可以是两个空单词加一个点号——整个文法会接受 http://./ 这样并不合法的 URL。
2. 这个 bug 完全来自「* 允许零次」这一细节，作者的本意是「单词由字母组成」，却无意中允许了「空单词」；在只测正常 URL 的测试下不会暴露。
3. 一旦这个过宽的模式被用于输入校验或路由分发，空主机名会一路传到下游（DNS 解析、HTTP 请求构造），故障点与原因相距很远。

✅ 正确代码

public class Words {
    // 文法：
    //   url      ::= 'http://' hostname '/'
    //   hostname ::= word '.' word
    //   word     ::= [a-z]+          <- 正确：至少一个字母
    //                （冗长但等价的写法：word ::= letter letter*）
    private static final java.util.regex.Pattern URL =
        java.util.regex.Pattern.compile("http://[a-z]+\\.[a-z]+/");

    public static boolean isUrl(String s) {
        return URL.matcher(s).matches();
    }
}

【为什么这样更好】 [a-z]+ 明确要求「一个或多个小写字母」，空单词被排除，http://./ 不再匹配。可以把它视为对 * 与 + 之差的显式选择：*（零或多次）适合「可以为空」的部分（如可选的路径段），+（一次或多次）适合「必须存在的成分」（如协议名、主机名的每一段、单词本身）。选择哪一个，是规格的一部分，应当有意识地决定并写进注释。

【代码对比解说】 这是「语法糖不只是糖，它带着语义」的典型例子：letter* 与 letter letter* 都等价于 + 的含义，但作者往往只想着「一个单词」，就顺手写了 *。同样的陷阱在 {n,m} 家族里也存在：y{,4} 的等价形式里含空串（至多四个），而 y{1,3} 不含空串。写文法时的自检方法是：把运算符替换成它的等价展开形式（* → 零或多次、? → 含空串分支），然后问「允许空串在这里合理吗」。若规格确实允许空串（例如 Markdown 里两段定界符之间可以为空），那就应当保留 * 并在注释中写明理由。

【设计原则透视】 文法是规格，因此它的松紧直接决定安全性：过宽 = 接受了规格本不允许的输入（违反前置条件检查的职责），过窄 = 拒绝了合法输入（同样破坏规格）。在 Reading 17 的框架里，文法定义的是解析树这一递归数据类型的合法值集合——若文法允许空单词，那么数据类型的某个 variant 就可能持有空字符串，AF/RI 若不写明（例如「word 至少含一个字符」），后续所有基于它的假设都会松动。课程给出的建议也适用于这里：把中间的非终结符保留下来（word、letter 各有名字）能让这种错误一眼可见，而压成一行正则后，* 与 + 的差别就淹没在符号里了。

场景 4：用正则解析嵌套标记——正则做不到，必须用文法

❌ 错误代码

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Italicizer {
    // 错误：企图用正则匹配「配对」的 <i>...</i>
    private static final Pattern ITALIC = Pattern.compile("<i>(.*)</i>");

    /**
     * @param s a string
     * @return the text inside the first italic element
     */
    public static String firstItalic(String s) {
        Matcher m = ITALIC.matcher(s);
        if (!m.find()) {
            throw new IllegalArgumentException("no italic in " + s);
        }
        return m.group(1);
    }
}

【错误代码的问题】

1. 贪婪量词 .* 会跨过独立的多个斜体元素：对 "a<i>b</i>c<i>d</i>e"，find() 匹配到的是 <i>b</i>c<i>d</i>，把两段斜体之间的普通文字 c 也吞了进去——结果取决于「串里还有没有另一个 <i>」，而不是规格所说的「第一个斜体元素」。
2. 改成非贪婪 .*? 也不能解决嵌套：对 "a<i>b<i>c</i>d</i>e"，find() 得到的是 <i>b<i>c</i>，既不是最内层也不是最外层，配对完全错乱。
3. 根本原因不是量词选得不好，而是正则语言无法表达配对嵌套：简化 HTML 文法 html ::= ( normal \| italic )*、italic ::= '<i>' html '</i>' 化简后右侧仍含 html 自身，无法消除，因此它不是正则文法。用正则去解析它，属于用错工具。

✅ 正确代码

import java.util.ArrayList;
import java.util.List;

/**
 * 用递归下降解析简化 HTML 的子集。文法（见注释）与 Reading 17 的递归数据类型对应：
 *   html   ::= ( normal | italic )*
 *   italic ::= '<i>' html '</i>'
 *   normal ::= text
 *   text   ::= [^<>]*
 * 返回结果使用 Reading 17 的不可变列表 ImList<E>：
 *   ImList<E> = Empty + Cons(elt:E, rest:ImList<E>)
 */
public class ItalicParser {
    /**
     * @param input a string
     * @return the contents of every italic element; an enclosing element's content
     *         precedes the contents of elements nested inside it
     * @throws IllegalArgumentException if the tags are not balanced
     */
    public static ImList<String> italicContents(String input) {
        int[] pos = { 0 };                      // 游标：与 pos[0] 共享，供递归调用推进
        ImList<String> result = parseSeq(input, pos, false);
        return result;
    }

    /** 解析 ( normal | italic )*，nested 为 true 时在遇到 "</i>" 处停下 */
    private static ImList<String> parseSeq(String s, int[] pos, boolean nested) {
        ImList<String> out = ImList.empty();
        while (pos[0] < s.length()) {
            if (nested && s.startsWith("</i>", pos[0])) {
                return out;                     // 交给调用者消费 "</i>"
            }
            if (s.startsWith("<i>", pos[0])) {
                pos[0] += 3;                    // 消费 '<i>'
                int innerStart = pos[0];
                ImList<String> inner = parseSeq(s, pos, true);   // 递归解析内部 html
                if (pos[0] >= s.length() || !s.startsWith("</i>", pos[0])) {
                    throw new IllegalArgumentException("unclosed <i> at " + innerStart);
                }
                out = inner.cons(s.substring(innerStart, pos[0]));
                pos[0] += 4;                    // 消费 '</i>'
            } else {
                pos[0]++;                       // 普通字符：属于 text ::= [^<>]*
            }
        }
        if (nested) {
            throw new IllegalArgumentException("missing </i>");
        }
        return out;
    }
}

【为什么这样更好】 递归下降解析器与文法同形：parseSeq 对应 html ::= ( normal \| italic )*，遇到 <i> 就递归调用自己并在返回后消费 </i>——配对关系由调用栈维护，因此嵌套多少层都能正确处理，而正则的有限状态无法记录「当前还差几个 </i>」。对 "a<i>b<i>c</i>d</i>e"，它会返回 ["b<i>c</i>d", "c"]：外层斜体的内容在前、嵌套在其中的内层内容在后，与规格一致；标签不配对时立刻抛出异常（fail fast）。

【代码对比解说】 这组对比的教训是「选择与语言能力相匹配的形式化工具」。正则表达式等价于有限状态自动机，注定无法处理需要计数的配对结构；而上下文无关文法（配解析栈）可以。实践中的判据很简单：如果模式里出现「成对定界符」并且它们可以互相嵌套（括号、标签、begin/end），就必须用文法；如果只是扁平的字符模式（日期、邮箱、单行日志字段），正则是更轻便的选择。注意 sp22 的 Markdown 文法之所以可以用正则，是因为它的 italic ::= '_' normal '_' 不允许嵌套（内层只能是 normal）——同一个「斜体」概念，两种语法的可表达性因此完全不同。

【设计原则透视】 这段代码同时用到 Reading 17 的两个要点：解析结果用不可变列表 ImList 表示（cons 在前端追加，O(1)），以及递归数据类型与递归文法一一对应。从 Reading 19（解析器）的角度看，这正是「解析器生成器」要自动完成的事：把文法交给工具，它会生成这样的解析器，并额外处理左递归、优先级等细节。从易理解性看，文法 + 递归下降的代码可以逐行对照文法阅读，而那个贪婪正则的 bug 却需要读者在脑中模拟回溯才能发现——这正是课程所说「正则表达式把本可读的文法压成一行，代价是可读性与可修改性」的具体体现。

场景 5：字符串解析——滥用 split 与 String.matches vs 预编译 Pattern + 命名捕获组

❌ 错误代码

public class Dates {
    /**
     * @param s a date string like "2020-03-18"
     * @return the year part of s
     */
    public static String yearOf(String s) {
        // 错误 1：没有校验格式，任何带 '-' 的串都「成功」
        // 错误 2：split 的参数是正则，每次调用都要重新编译
        // 错误 3：结构不匹配时抛 ArrayIndexOutOfBoundsException，而非规格中的失败语义
        return s.split("-")[0];
    }

    /**
     * @param s a date string
     * @return true iff s has the form YYYY-MM-DD
     */
    public static boolean isDate(String s) {
        // 错误 4：String.matches 每次调用都重新编译正则；且这里的 \d 未写成 \\d 会编译不过
        return s.matches("\\d{4}-\\d{2}-\\d{2}") || true;
    }
}

【错误代码的问题】

1. yearOf 对 "3-18" 返回 "3"、对 "not-a-date" 返回 "not"、对 "2020-3-8" 也「成功」，完全不符合「解析日期」的规格；对 "20200318" 抛 ArrayIndexOutOfBoundsException——用异常表达了一个预期之中的失败，把正常的输入校验变成了崩溃。
2. split 与 matches 的参数都是正则表达式，每次调用都会新建并编译 Pattern；在高频路径（日志解析、逐行处理）上这是可观的浪费。
3. isDate 里那个 \|\| true 使整个表达式恒为真（示例化的严重 bug），说明「把校验写成一行大表达式」时极易出现逻辑错误且难以审阅；此外正则里的反斜杠必须写成 \\d，否则 Java 编译器直接报错——这是把正则嵌进 Java 源码的常见摩擦。

✅ 正确代码

import java.util.Optional;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Dates {
    // 预编译一次，反复使用；Pattern 不可变且线程安全
    private static final Pattern DATE =
        Pattern.compile("(?<year>\\d{4})-(?<month>\\d{2})-(?<day>\\d{2})");

    /**
     * @param s a string
     * @return the year if s has the form YYYY-MM-DD, otherwise Optional.empty()
     */
    public static Optional<String> yearOf(String s) {
        Matcher m = DATE.matcher(s);
        if (!m.matches()) {          // matches() 要求整串匹配：不会漏掉多余的尾巴
            return Optional.empty();
        }
        return Optional.of(m.group("year"));   // 命名捕获组：规格与抽取共用一处定义
    }

    /**
     * @param s a string
     * @return true iff s has the form YYYY-MM-DD
     */
    public static boolean isDate(String s) {
        return DATE.matcher(s).matches();
    }
}

【为什么这样更好】 格式规则只写一次（那个 static final Pattern），校验与抽取由同一份规格驱动，不可能出现「校验通过但抽取结果不对」的不一致。失败被表达为 Optional.empty() 而不是异常，与 Reading 07 关于「用返回值表达可预期的失败、用异常表达违反前置条件」的建议一致。Matcher.matches() 的整串语义避免了 find() 那种「串里有一处像日期就通过」的漏检。用命名捕获组后，group("year") 的语义与文法中的 year 字段同名，读代码即可对照。

【代码对比解说】 三种解析路线的对比很清楚：手工 split/substring 最省事但最脆弱（隐含假设、异常语义错位、无复用）；String.matches/String.split 内联正则 稍好（声明式）但每次编译且容易被引号反斜杠搞乱；预编译 Pattern + 命名捕获组 兼顾声明式、性能与可读性，是生产代码的默认选择。还要注意 matches() 与 find() 的区别：前者等价于整串锚定，后者像「搜索」。若确实想用 find()（例如在长文本里找第一个日期），就必须自己在正则两端加锚点或检查 start()/end()，否则会得到「部分匹配」的结果。补充说明：Matcher 持有匹配状态（group、start、end 都依赖最近的匹配），不是线程安全的，不要把它放进共享字段；而 Pattern 是线程安全的，可以安全复用。

【设计原则透视】 这里体现的是 Reading 06/07 中「规格的可判定性」：一个好的规格应能让实现者明确回答「这个输入是否满足」，并让失败有明确语义。用 Optional<String> 作为返回类型把这个语义放进了类型里（Reading 12 的泛型与 Optional 协作），调用者无法忽略它；用预编译的 Pattern 常量则把「规则」从散落的控制流中提炼成一处可评审、可测试的声明式规格。从 Reading 03（测试）的角度看，围绕这条规格应覆盖的等价类是：合法输入、格式正确但数值越界（如 "2020-13-40"——文法允许，语义不许，需要在程序里另行检查，正如课程对端口范围的处理）、缺位/多位、含多余尾巴（验证 matches() 而非 find() 的语义）、空串与 null。这正是「文法管形状、程序管约束」这一分工的具体落点。

与其他设计原则的关联

本讲与 Reading 06（规格说明）、Reading 07（设计规格） 同源：文法与正则表达式就是序列的规格，只不过描述对象从「方法的输入输出」换成了「字符序列的形状」；课程所说的「文件格式」「线协议」「命令行接口」全都是规格在不同场景下的别名。Reading 17（递归数据类型）是解析的落点：解析树与语法树都是递归数据类型，因此「在接口上声明操作、在每个 variant 上递归实现」的做法可以原样搬到语法树上；本讲场景 4 的解析器就直接返回 ImList。Reading 19（解析器）紧接着本讲，讨论把文法自动翻译成解析器的工具（parser generators），从而省掉手写递归下降的工作。

向前追溯，Reading 02（Java 基础）提供的字符串与 API 基础（String.split、matches、replaceAll）是使用正则的前提；Reading 12（接口、泛型与枚举）解释了 Pattern/Matcher 这种「不可变规格 + 有状态会话」的组合为何常见，以及 Optional 为何适合表达解析失败。Reading 16（Map、Filter、Reduce）中「把项目里所有 Java/TypeScript 文件的单词抽出来」的例子用到 split(/\W+/) 与 filter(s -> s.length() > 0)，正是本讲正则的实战应用；反过来，本讲也是 Reading 16 的一个注脚——那里只用了正则最简单的一面。Reading 03（测试）要求为文法与正则设计覆盖等价类的测试（空串、最长/最短匹配、非法尾随字符）；Reading 09（避免调试）与 Reading 13（调试）提醒：正则表达式难以调试，写的时候应尽量拆分成带注释的片段或改用带名字的文法。

向后看，Reading 21（并发）与 Reading 23（互斥）解释了为什么 Pattern 可以安全共享而 Matcher 不行；Reading 25（网络）中的消息格式即「线协议」，其规格写法与本文法完全同构；Reading 26/27（小语言）把「文法 + 解析树 + 递归求值」组织成完整的解释器，本讲的 url、html、markdown 文法只是它在小规模上的预演。最后，本讲关于「正则 vs 文法」的取舍判断，本身就是课程反复训练的设计取舍能力：同一个字符串集合可以有多种规格，选择的标准是三大目标——安全性、易理解性、可修改性。

关键要点

• 文法 = 一组产生式 + 一个根非终结符：每条产生式用 ::= 定义一个非终结符，右侧由终结符（加引号、不能再展开）、非终结符与运算符组成；文法识别的正是匹配根非终结符的那些字符串。
• 三个核心运算符加优先级：重复 *（零或多次）、连接（空格）、选择 \|；后缀运算符优先级最高、连接次之、\| 最低，用括号覆盖优先级。?、+、{n,m}、[...]、[^...] 都是它们的语法糖。
• * 允许空串，+ 不允许：word ::= letter* 会让 http://./ 也合法；要「至少一个」就用 word ::= [a-z]+（或冗长的 letter letter*）。运算符的选择是规格的一部分。
• 正则 = 化简后的文法，有嵌套就必须回到文法：把非终结符逐个代入直到只剩根，去掉引号与空格，就得到正则表达式——它更快、库支持更广，但缺少说明性的名字，可读性与可修改性都差得多。HTML 的 italic ::= '<i>' html '</i>' 无法消去递归（上下文无关但非正则），Markdown 的 italic ::= '_' normal '_' 可以化简为正则；因此扁平的字符模式用正则，成对可嵌套的结构用文法 + 解析器。
• Java 中的实践要点：\\ 双层转义、matches() 整串匹配 vs find() 搜索匹配、命名捕获组 (?<name>...)、Pattern 预编译且线程安全而 Matcher 有状态。

常见陷阱与注意事项

• 忘记转义元字符：把 .、*、+、\|、(、)、[、]、\ 当作字面字符使用却不加反斜杠 → 正则悄悄匹配了远多于规格的字符串（如 [a-z]+. 接受任意分隔符），且编译器毫无提示；正确做法是 \.（或用 [.]），并在 Java 中写成 "\\."。
• * 与 + 用错导致允许空串：word ::= letter*、y{,4}（含空串）被用在「必须存在」的位置 → 文法接受了空主机名、空标签等非法输入；写完后把语法糖展开检查一遍空串是否可接受。
• 用正则解析嵌套结构，或把复杂正则当作可维护的规格：<i>(.*)</i> 或 <i>(.*?)</i> 处理 HTML/XML/括号嵌套时，贪婪会跨越多个同级元素、非贪婪会让嵌套配对错乱；而一个两百字符、改一处就崩一片的正则本身也是维护灾难 → 正则语言无法表达配对嵌套，应当先写带名字的文法（url、hostname、port、word），用解析器处理嵌套，只在模式确实扁平且简单时才把文法机械化简为正则并保留文法注释。
• 混淆 matches() 与 find()：想在整串上校验却调用 find() → 只要串中某处像日期/URL 就通过校验；反之想在长文本中搜索却用 matches() → 永远匹配失败。选择哪一个必须与规格一致。
• 每次调用都重新编译正则：把正则写在 String.matches/String.split 的实参里，或在方法体内反复 Pattern.compile → 高频路径上性能明显下降；应把 Pattern 提为 static final 常量（它是线程安全的）。同时注意不要共享 Matcher（它有状态、非线程安全）。
• 把数值范围约束写进文法：试图用文法精确表达 0 ≤ port ≤ 65535 → 文法急剧膨胀且难以维护；课程的做法是让文法只描述形状（port ::= [0-9]+），范围检查放到使用该文法的程序里。

思考题（带答案）

问题 1：下面这个文法识别哪些字符串？请判断 617、617-253、617-253-1000、---、integer-integer-integer、5--5、3-6-293-1 是否匹配，并说明 integer 扮演的角色。

root    ::= integer ('-' integer)+
integer ::= [0-9]+

答案：root 由 integer、一个至少出现一次的「'-' integer 组」构成，因此它识别的是「由两个或更多个非空数字串、用单个连字符连接」的字符串（类似美国电话号码格式）。

• 617：不匹配。('-' integer)+ 要求至少一组「连字符 + 数字」，这里一组都没有。
• 617-253：匹配（恰好一组）。
• 617-253-1000：匹配（两组）。
• ---：不匹配。integer ::= [0-9]+ 要求至少一个数字，连字符本身不是 integer。
• integer-integer-integer：不匹配。字面量单词 integer 不是数字串。
• 5--5：不匹配。[0-9]+ 在第一个 - 之前只吃到 5，随后 ('-' integer)+ 需要「连字符后紧跟数字」，而这里连字符后面又是一个连字符。
• 3-6-293-1：匹配（三组）。

integer 是一个非终结符，它把「一个或多个数字」这条子规则命名为 integer，于是 root 的产生式可以用这个名字而不是重复写 [0-9]+。这正是文法优于正则表达式的地方：名字承载了含义，读文法时能看到「整数—连字符—整数」的结构。注意 [0-9]+ 中的 + 是 [0-9][0-9]* 的语法糖，它保证每段数字非空——若误写成 [0-9]*，-- 甚至 - 都可能被接受（取决于具体写法），这正是场景 3 讨论过的空串陷阱。

问题 2：为什么简化 HTML 文法不是正则的，而简化 Markdown 文法可以化简为正则表达式？请写出两者的化简结果，并说明这对「用正则还是用文法」的实践选择意味着什么。

答案：两个文法的差别只在 italic 产生式中「定界符之间匹配哪个非终结符」：

markdown ::= ( normal | italic )*      html ::= ( normal | italic )*
italic   ::= '_' normal '_'             italic ::= '<i>' html '</i>'
normal   ::= text                       normal ::= text
text     ::= [^_]*                      text   ::= [^<>]*

Markdown 的 italic 内部只允许 normal ::= text ::= [^_]*，即「不含下划线的任意文本」，它不会回到 markdown，所以替换所有非终结符后可以得到只含终结符与运算符的单一产生式：

markdown ::= ([^_]* | '_' [^_]* '_' )*

去掉引号与空格就是正则表达式 ([^_]*\|_[^_]*_)*——Markdown 文法是正则的（它的斜体不能嵌套，a_b_c_d_e 中只有 b、d 位于 italic 内部）。

HTML 的 italic 内部是 html 自身，替换后得到：

html ::= ( [^<>]* | '<i>' html '</i>' )*

右侧对 html 的递归引用无法消除，也无法用重复运算符代替（因为需要记住「打开了几个 <i>」才能正确配对），所以 HTML 文法是上下文无关的但不是正则的。

实践含义：能否用正则取决于是否需要「配对/嵌套」的记忆。扁平模式（日期、URL、日志字段、Markdown 式不嵌套的定界符）用正则，短、快、库支持好；含成对定界符且可嵌套的结构（HTML/XML、括号、{} 代码块）必须用文法加解析器（Reading 19），正则在这里无论怎么改都无法正确处理——场景 4 中 <i>(.*)</i> 在 "a<i>b</i>c<i>d</i>e" 上跨越两个同级元素、在 "a<i>b<i>c</i>d</i>e" 上配对错乱，就是这个结论的具体证据。补充一点实践判断：如果一个「正则」已经长到需要写注释才能读懂，那它多半应该先写成文法，再机械化简；而一旦发现化简时卡在递归引用上，就等于发现「这里必须用文法」。

问题 3：下面的 Java 代码想从 "77 Rose Court Ln" 这样的地址中取出门牌号、街道名与街道类型。它有什么问题？请给出改进版本，并说明 matches() 与 find() 的区别在这段代码里为什么重要。

public static String streetTypeOf(String s) {
    return s.split(" ")[s.split(" ").length - 1];
}

答案：问题有四类。其一，没有校验：split(" ") 对任何含空格的串都「成功」，"hello world" 会被当成地址、"77-Rose-Court-Ln" 会直接返回整个串（因为没有空格，数组长度为 1）。其二，结构假设过强：它假设街道类型永远是最后一个空格分隔的词，但规格并未如此规定，一旦地址里出现楼层、单元号等后置信息就出错。其三，语义错位：split 的参数是正则表达式（这里恰好也是字面量空格），每次调用都要编译；而且连写两遍 s.split(" ") 意味着两次完整拆分，效率与可读性都差。其四，失败语义不明：空串会返回 ""（split 对空串返回长度 1 的数组），而 null 会抛 NullPointerException，规格里没有任何说明。

改进版本使用预编译的 Pattern 与命名捕获组（对应课程中 Pattern.compile("[0-9]+ .* (Rd\|St\|Ave\|Ln)") 的加命名组写法）：

import java.util.Optional;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Addresses {
    private static final Pattern ADDRESS = Pattern.compile(
        "(?<houseNumber>[0-9]+) (?<streetName>.*) (?<streetType>Rd|St|Ave|Ln)");

    /**
     * @param s a string
     * @return the street type if s is a street address of the form above
     */
    public static Optional<String> streetTypeOf(String s) {
        Matcher m = ADDRESS.matcher(s);
        if (!m.matches()) {
            return Optional.empty();
        }
        return Optional.of(m.group("streetType"));
    }
}

注意正则里的空格是有含义的（匹配字面空格），不能随意增删；(?<name>...) 中的 ? 不是「零或一次」的量词，而是「这组括号有特殊含义」的标记。

matches() 与 find() 的区别在这里很关键：matches() 要求整串与正则匹配，等价于给整个模式加上了 ^...$ 锚定，因此 "77 Rose Court Ln" 通过、"77 Rose Court Ln Apt 3" 会失败（尾部多出内容），这正是「这条串是否是这种形式的地址」这一规格的正确语义；而 find() 只要求在串中找到一个匹配子串，用它来校验就会把 "见 77 Rose Court Ln。" 这类串也判为合法地址，即「校验被降级成搜索」。反过来，如果需求真的是「在长文本里找出第一个地址」，那就应当用 find()，并通过 m.start()/m.end() 取得位置——用哪个方法取决于规格想要「整体判定」还是「搜索定位」，这也是把正则当作规格时最容易被忽视的一条细节。