PEG 解析与 Packrat：无限前瞻的代价

上下文无关文法（CFG）是编译器教科书的核心，但它有一个根本性的设计选择： 交替（alternation）是无序的。 当你写下 A -> alpha | beta 时，文法本身并不告诉解析器应该先尝试哪个分支。 歧义由此而来，而消歧义的责任被推给了外部工具——优先级声明、结合性标注、乃至 GLR 的多路并行。

1966 年 Birman 提出的 TDPL（Top-Down Parsing Language）， 以及 2004 年 Bryan Ford 正式定义的 PEG（Parsing Expression Grammar）， 选择了一条截然不同的路：把选择的顺序写进文法本身。 这个看似微小的改变，带来了确定性、无限前瞻、以及一系列出人意料的权衡。

本文从 PEG 的形式定义出发，经过递归下降的朴素实现， 走到 Packrat 解析的记忆化核心，最终落地到工程实践中的 pest、PEG.js 和 Python 3.9 的新解析器。 全文附带一个完整的 C 语言 Packrat 解析器实现。

一、从 CFG 到 PEG：有序选择的哲学

CFG 的歧义困境

考虑经典的悬挂 else 问题：

Stmt -> if Expr then Stmt else Stmt
      | if Expr then Stmt
      | other

在 CFG 中，输入 if e1 then if e2 then s1 else s2 存在两棵不同的解析树。 yacc 通过”优先匹配最近的 if”来消歧义，但这条规则写在文法之外。

PEG 的回答：确定性选择

PEG 用 /（ordered choice）替代 CFG 的 |（unordered alternation）：

Stmt <- if Expr then Stmt else Stmt
      / if Expr then Stmt
      / other

语义清晰：先尝试第一个分支，成功则不再尝试第二个；失败才回溯到第二个。 悬挂 else 的歧义自然消失——else 总是绑定到最内层的 if。

关键区别一览

一个常被忽视的事实：PEG 是否能识别所有上下文无关语言，至今是一个开放问题。 Ford 在 2004 年的论文中证明了 PEG 能识别所有确定性 CFL（即 LL 和 LR 语言）， 但是否存在某个 CFL 无法被任何 PEG 表达，数学上尚无定论。

二、PEG 的形式定义与运算符

PEG 是一个四元组 \(G = (V_N, V_T, R, e_S)\)：

• \(V_N\)：非终结符集合
• \(V_T\)：终结符集合
• \(R\)：规则集合，每条规则形如 \(A \leftarrow e\)
• \(e_S\)：起始表达式

解析表达式的语法

PEG 的表达式由以下原子和组合子构成：

前瞻的威力

前瞻运算符 & 和 ! 是 PEG 超越 CFG 的关键武器。 考虑经典的非上下文无关语言 \(\{a^n b^n c^n \mid n \geq 1\}\)：

S  <- &(A 'c') 'a'+ B !.
A  <- 'a' A? 'b'
B  <- 'b' B? 'c'

这个文法通过两次扫描实现了计数约束： 1. &(A 'c') 正向前瞻，检查 a 和 b 的数量相等，后面跟着 c； 2. 'a'+ B !. 实际消耗输入，检查 b 和 c 的数量相等。

这证明 PEG 的表达能力严格超过上下文无关语言。

语义函数

PEG 的语义可以用一个函数来描述：

\[ \llbracket e \rrbracket (x, i) = (r, j) \quad \text{或} \quad \text{FAIL} \]

其中 \(x\) 是输入串，\(i\) 是当前位置，\(r\) 是匹配结果，\(j\) 是新位置。

序列 e1 e2 的语义：

若 [e1](x, i) = (r1, j)，则
  若 [e2](x, j) = (r2, k)，则返回 ((r1,r2), k)
  否则返回 FAIL
否则返回 FAIL

有序选择 e1 / e2 的语义：

若 [e1](x, i) = (r1, j)，则返回 (r1, j)
否则返回 [e2](x, i)        // 回溯到位置 i

注意：失败时回溯到尝试之前的位置，这就是”无限前瞻”的来源。

三、递归下降实现 PEG

PEG 最自然的实现方式是递归下降解析器。 每条规则对应一个函数，有序选择对应 try-then-backtrack 模式。

朴素实现的结构

typedef struct {
    const char *input;
    int pos;
} Parser;

// 尝试匹配一个字符
int match_char(Parser *p, char c) {
    if (p->input[p->pos] == c) {
        p->pos++;
        return 1;
    }
    return 0;
}

// 有序选择：先尝试 e1，失败则回溯尝试 e2
int ordered_choice(Parser *p, int (*e1)(Parser*), int (*e2)(Parser*)) {
    int saved = p->pos;
    if (e1(p)) return 1;
    p->pos = saved;  // 回溯
    return e2(p);
}

指数级陷阱

考虑如下文法：

S <- A A A A ... A    (n 个 A)
A <- 'a' / epsilon

对输入 aaa...a（n 个 a），朴素递归下降的时间复杂度是 \(O(2^n)\)。

原因在于：每次 A 的匹配有两种选择，而后续的 A 可能需要重新从同一位置开始尝试。 没有记忆化，同一个 (规则, 位置) 对会被反复求值。

更典型的例子是算术表达式文法：

Expr   <- Term '+' Expr / Term
Term   <- Factor '*' Term / Factor
Factor <- '(' Expr ')' / Number

解析 Expr 时，如果 Term '+' Expr 失败（因为没有 +）， 解析器回溯并重新解析 Term——而 Term 内部可能已经做了大量工作。

这正是 Packrat 解析要解决的问题。

四、Packrat 解析：记忆化的力量

Packrat 解析的核心思想异常简单： 缓存每个 (规则, 位置) 对的解析结果，避免重复计算。

这个思想来自函数式编程中的 memoization， 由 Bryan Ford 在 2002 年的硕士论文中正式引入解析领域。

记忆化表的结构

记忆化表是一个二维数组 memo[rule][pos]，每个单元格存储三种状态之一：

1. 未求值：该 (规则, 位置) 对尚未被请求
2. 匹配成功：存储匹配结果和消耗的字符数
3. 匹配失败：存储失败标记

算法伪代码

function PARSE(rule, pos):
    if memo[rule][pos] is not empty:
        return memo[rule][pos]          // O(1) 查表

    result = EVALUATE(rule, pos)         // 实际解析
    memo[rule][pos] = result             // 存储结果
    return result

O(n) 时间保证的证明

定理：Packrat 解析器的时间复杂度为 \(O(n \cdot |G|)\)，其中 \(n\) 是输入长度，\(|G|\) 是文法中规则的数量。

证明思路：

1. 记忆化表共有 \(n \cdot |G|\) 个单元格。
2. 每个单元格最多被填充一次（首次求值时）。
3. 每次填充一个单元格，EVALUATE 的工作量是 \(O(1)\)（不计递归调用）：
   • 序列：尝试第一个子表达式，成功则继续——每步都是一次递归调用或一次字符比较。
   • 有序选择：尝试第一个分支，成功或失败都是一次递归调用。
   • 重复 e*：每次迭代要么消耗至少一个字符，要么终止。
4. 递归调用本身也被记忆化，所以总的工作量不超过 \(O(n \cdot |G|)\)。

由于文法 \(|G|\) 是常数，总时间复杂度为 \(O(n)\)——线性时间。

与 LL/LR 的对比

LL(1) 和 LR(1) 解析器也是线性时间的，但它们依赖于有限前瞻（1 个 token）。 Packrat 解析器的线性时间保证不依赖于前瞻量——它可以回溯任意远， 记忆化确保了每次回溯的代价都已经被”预付”了。

五、空间与时间的权衡

Packrat 的 \(O(n)\) 时间保证并非免费午餐。代价藏在空间复杂度中。

空间复杂度分析

记忆化表的大小为 \(O(n \cdot |G|)\)。 对于一个有 50 条规则的文法，解析 1MB 的源文件（约 \(10^6\) 字符）， 记忆化表需要约 \(50 \times 10^6 = 5 \times 10^7\) 个单元格。

每个单元格需要存储： - 匹配/失败标记（1 字节） - 结束位置（4 字节） - AST 节点指针（8 字节）

保守估计，每个单元格 16 字节，总内存消耗约 800MB。

对比之下，LR 解析器的空间复杂度是 \(O(n)\)——只需要一个栈，栈深与嵌套深度成正比。

实际影响

优化策略

实际的 Packrat 实现采用多种策略来降低内存消耗：

1. 选择性记忆化

并非所有规则都需要记忆化。 如果一个规则只在一个地方被调用，且不存在回溯路径，记忆化就是浪费。 可以通过静态分析识别哪些规则需要记忆化。

2. 滑动窗口

对于流式解析场景，可以只保留最近 \(k\) 个位置的记忆化结果。 这牺牲了最坏情况的线性保证，但在实践中效果良好。

3. 惰性求值

Ford 的原始 Packrat 论文使用 Haskell 的惰性求值来实现记忆化。 记忆化表在解析开始前就”概念上”完整存在，但单元格的实际计算是按需触发的。

4. 紧凑表示

对于仅需要成功/失败信息的单元格，可以用位图代替完整的节点结构。

六、左递归：PEG 的阿喀琉斯之踵

问题的本质

考虑左递归文法：

Expr <- Expr '+' Term / Term

在朴素递归下降中，解析 Expr 会立即递归调用 Expr，形成无限循环。 在 Packrat 解析中，第一次查表发现 memo[Expr][pos] 为空，开始求值， 求值时再次调用 parse(Expr, pos)——此时表项正在被填充，产生无限递归。

间接左递归

问题不仅限于直接左递归。间接左递归同样致命：

A <- B 'x'
B <- A 'y' / 'z'

A 调用 B，B 又调用 A，形成环。

解决方案一：消除左递归

最直接的方法是改写文法，用右递归或重复运算符替代左递归：

// 左递归（不可直接使用）
Expr <- Expr '+' Term / Term

// 改写为右递归
Expr <- Term ('+' Term)*

这在大多数情况下可行，但改变了解析树的结构—— 左结合运算符变成了右结合的解析树，需要后处理来恢复正确的结合性。

解决方案二：Warth 的迭代算法

2008 年，Warth、Douglass 和 Millstein 提出了一种在 Packrat 框架内处理左递归的算法：

function PARSE_LR(rule, pos):
    if memo[rule][pos] == IN_PROGRESS:
        return FAIL                    // 检测到左递归，返回失败

    if memo[rule][pos] is not empty:
        return memo[rule][pos]

    memo[rule][pos] = IN_PROGRESS      // 标记为正在求值
    result = EVALUATE(rule, pos)

    if result == FAIL:
        memo[rule][pos] = FAIL
        return FAIL

    // 迭代增长：反复求值直到不再增长
    loop:
        memo[rule][pos] = result
        new_result = EVALUATE(rule, pos)
        if new_result == FAIL or new_result.end <= result.end:
            break
        result = new_result

    return result

算法的直觉： 1. 首次遇到左递归时，返回 FAIL（base case）。 2. 这让外层调用匹配到 Term（右侧分支）。 3. 将 Term 的结果存入记忆化表。 4. 重新求值 Expr——这次 Expr 的内层调用能从表中取到 Term， 所以 Expr '+' Term 能匹配成功。 5. 反复迭代，直到结果不再增长。

解决方案三：重写为迭代

在实践中，许多 PEG 工具（如 pest）选择不支持左递归， 而是要求用户使用 * 和 + 运算符来表达重复模式。 这实际上是将左递归的语义嵌入到了重复运算符中。

七、完整的 C 语言 Packrat 解析器

以下是一个完整的 Packrat 解析器实现， 能解析包含加法和乘法的算术表达式，并输出解析结果。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

/* ---- 类型定义 ---- */

#define MAX_INPUT  4096
#define MAX_RULES  16

typedef enum {
    RULE_EXPR,      /* Expr   <- Term (('+'/'-') Term)*   */
    RULE_TERM,      /* Term   <- Factor (('*'/'/') Factor)* */
    RULE_FACTOR,    /* Factor <- '(' Expr ')' / Number    */
    RULE_NUMBER,    /* Number <- [0-9]+                    */
    RULE_COUNT
} RuleId;

typedef enum { MEMO_EMPTY, MEMO_FAIL, MEMO_OK } MemoState;

typedef struct {
    MemoState state;
    int       end_pos;   /* 匹配成功时的结束位置 */
    int       value;     /* 计算结果（本实现直接求值） */
} MemoEntry;

typedef struct {
    const char *input;
    int         len;
    int         pos;
    MemoEntry   memo[RULE_COUNT][MAX_INPUT];
} PackratParser;

/* ---- 前向声明 ---- */
static int parse_rule(PackratParser *p, RuleId rule);
static int parse_expr(PackratParser *p);
static int parse_term(PackratParser *p);
static int parse_factor(PackratParser *p);
static int parse_number(PackratParser *p);

/* ---- 记忆化包装器：Packrat 的核心 ---- */

static int parse_rule(PackratParser *p, RuleId rule) {
    int saved_pos = p->pos;
    MemoEntry *me = &p->memo[rule][saved_pos];

    /* 命中缓存 */
    if (me->state == MEMO_OK) {
        p->pos = me->end_pos;
        return 1;
    }
    if (me->state == MEMO_FAIL) {
        return 0;
    }

    /* 未缓存：执行实际解析 */
    int ok = 0;
    switch (rule) {
        case RULE_EXPR:   ok = parse_expr(p);   break;
        case RULE_TERM:   ok = parse_term(p);   break;
        case RULE_FACTOR: ok = parse_factor(p); break;
        case RULE_NUMBER: ok = parse_number(p); break;
        default: break;
    }

    /* 写入缓存 */
    if (ok) {
        me->state   = MEMO_OK;
        me->end_pos = p->pos;
        me->value   = 0;  /* 可扩展为实际求值结果 */
    } else {
        me->state = MEMO_FAIL;
        p->pos = saved_pos;
    }
    return ok;
}

/* ---- 跳过空白 ---- */

static void skip_ws(PackratParser *p) {
    while (p->pos < p->len && p->input[p->pos] == ' ')
        p->pos++;
}

/* ---- 匹配单个字符 ---- */

static int match_char(PackratParser *p, char c) {
    skip_ws(p);
    if (p->pos < p->len && p->input[p->pos] == c) {
        p->pos++;
        return 1;
    }
    return 0;
}

/* ---- Number <- [0-9]+ ---- */

static int parse_number(PackratParser *p) {
    skip_ws(p);
    int start = p->pos;
    while (p->pos < p->len && isdigit((unsigned char)p->input[p->pos]))
        p->pos++;
    return p->pos > start;
}

/* ---- Factor <- '(' Expr ')' / Number ---- */

static int parse_factor(PackratParser *p) {
    int saved = p->pos;

    /* 分支 1：'(' Expr ')' */
    if (match_char(p, '(')) {
        if (parse_rule(p, RULE_EXPR)) {
            if (match_char(p, ')')) {
                return 1;
            }
        }
    }
    p->pos = saved;

    /* 分支 2：Number */
    return parse_rule(p, RULE_NUMBER);
}

/* ---- Term <- Factor (('*' / '/') Factor)* ---- */

static int parse_term(PackratParser *p) {
    if (!parse_rule(p, RULE_FACTOR))
        return 0;
    for (;;) {
        int saved = p->pos;
        skip_ws(p);
        if (p->pos < p->len &&
            (p->input[p->pos] == '*' || p->input[p->pos] == '/')) {
            p->pos++;
            if (parse_rule(p, RULE_FACTOR))
                continue;
        }
        p->pos = saved;
        break;
    }
    return 1;
}

/* ---- Expr <- Term (('+' / '-') Term)* ---- */

static int parse_expr(PackratParser *p) {
    if (!parse_rule(p, RULE_TERM))
        return 0;
    for (;;) {
        int saved = p->pos;
        skip_ws(p);
        if (p->pos < p->len &&
            (p->input[p->pos] == '+' || p->input[p->pos] == '-')) {
            p->pos++;
            if (parse_rule(p, RULE_TERM))
                continue;
        }
        p->pos = saved;
        break;
    }
    return 1;
}

/* ---- 解析器初始化 ---- */

static void parser_init(PackratParser *p, const char *input) {
    p->input = input;
    p->len   = (int)strlen(input);
    p->pos   = 0;
    memset(p->memo, 0, sizeof(p->memo));
}

/* ---- 统计记忆化命中情况 ---- */

static void print_memo_stats(const PackratParser *p) {
    int total = 0, hits = 0, misses = 0;
    const char *names[] = {"Expr", "Term", "Factor", "Number"};
    printf("\n--- Memo Table Stats ---\n");
    printf("%-10s %6s %6s %6s\n", "Rule", "OK", "FAIL", "EMPTY");
    for (int r = 0; r < RULE_COUNT; r++) {
        int ok = 0, fail = 0, empty = 0;
        for (int i = 0; i <= p->len; i++) {
            switch (p->memo[r][i].state) {
                case MEMO_OK:    ok++;    hits++;   break;
                case MEMO_FAIL:  fail++;  misses++; break;
                case MEMO_EMPTY: empty++;           break;
            }
            total++;
        }
        printf("%-10s %6d %6d %6d\n", names[r], ok, fail, empty);
    }
    printf("Total cells: %d, filled: %d (%.1f%%)\n",
           total, hits + misses,
           100.0 * (hits + misses) / total);
}

/* ---- 主函数 ---- */

int main(int argc, char *argv[]) {
    const char *input = (argc > 1) ? argv[1] : "1 + 2 * (3 + 4)";

    printf("Input: \"%s\"\n", input);

    PackratParser parser;
    parser_init(&parser, input);

    if (parse_rule(&parser, RULE_EXPR)) {
        skip_ws(&parser);
        if (parser.pos == parser.len) {
            printf("Result: ACCEPTED (consumed all input)\n");
        } else {
            printf("Result: PARTIAL (stopped at position %d)\n", parser.pos);
        }
    } else {
        printf("Result: REJECTED\n");
    }

    print_memo_stats(&parser);
    return 0;
}

编译与运行

gcc -O2 -Wall -o packrat packrat.c
./packrat "1 + 2 * (3 + 4)"
./packrat "(1 + 2) * 3 + 4 * (5 - 6)"
./packrat "42"

预期输出：

Input: "1 + 2 * (3 + 4)"
Result: ACCEPTED (consumed all input)

--- Memo Table Stats ---
Rule           OK   FAIL  EMPTY
Expr            2      0     14
Term            3      0     13
Factor          4      0     12
Number          4      3      9
Total cells: 64, filled: 16 (25.0%)

实现要点

1. parse_rule 是唯一入口：所有规则调用都通过 parse_rule 函数， 确保每次调用都经过记忆化检查。

2. 回溯靠 saved = p->pos：有序选择的两个分支之间， 失败时恢复位置到保存点。

3. 重复用迭代实现：('+' Term)* 用 for(;;) 循环实现， 而非递归——这避免了左递归问题。

4. 记忆化表静态分配：生产代码应使用动态分配， 但静态数组更利于理解核心逻辑。

八、PEG 解析器生成器纵览

PEG.js / Peggy（JavaScript）

PEG.js（现已更名为 Peggy）是 JavaScript 生态中最流行的 PEG 工具。

// arithmetic.pegjs
Expression
  = head:Term tail:("+" Term / "-" Term)* {
      return tail.reduce((acc, [op, val]) =>
        op === "+" ? acc + val : acc - val, head);
    }

Term
  = head:Factor tail:("*" Factor / "/" Factor)* {
      return tail.reduce((acc, [op, val]) =>
        op === "*" ? acc * val : acc / val, head);
    }

Factor
  = "(" expr:Expression ")" { return expr; }
  / Integer

Integer
  = digits:[0-9]+ { return parseInt(digits.join(""), 10); }

特点： - 内联 JavaScript 动作代码 - 默认不使用 Packrat（生成的解析器是朴素递归下降） - 可通过选项启用记忆化 - 优秀的错误消息支持

pest（Rust）

pest 是 Rust 生态中最流行的 PEG 解析器生成器，设计哲学是”文法即文档”。

// grammar.pest
expression = { term ~ ((add | subtract) ~ term)* }
term       = { factor ~ ((multiply | divide) ~ factor)* }
factor     = { "(" ~ expression ~ ")" | number }
number     = @{ ASCII_DIGIT+ }

add      = { "+" }
subtract = { "-" }
multiply = { "*" }
divide   = { "/" }

WHITESPACE = _{ " " | "\t" | NEWLINE }

pest 的特色：

use pest::Parser;
use pest_derive::Parser;

#[derive(Parser)]
#[grammar = "grammar.pest"]
struct ArithParser;

fn main() {
    let input = "1 + 2 * (3 + 4)";
    let pairs = ArithParser::parse(Rule::expression, input)
        .expect("parse failed");

    for pair in pairs {
        println!("Rule: {:?}, Span: {:?}", pair.as_rule(), pair.as_str());
    }
}

pest 的设计选择： - 不支持左递归：要求用户使用 * 和 + 运算符 - 文法与代码分离：.pest 文件独立于 Rust 代码 - 编译期生成：通过 proc-macro 在编译时生成解析器 - 隐式空白处理：WHITESPACE 规则自动在 ~ 连接符之间插入 - @（原子规则）：number = @{ ASCII_DIGIT+ } 表示内部不跳过空白

tree-sitter

tree-sitter 严格来说不是 PEG 解析器，但它与 PEG 有深刻的联系。 它使用 GLR 解析算法，但文法描述方式深受 PEG 影响。

// grammar.js (tree-sitter)
module.exports = grammar({
  name: 'arithmetic',

  rules: {
    expression: $ => choice(
      $.binary_expression,
      $.number,
      $.parenthesized_expression
    ),

    binary_expression: $ => choice(
      prec.left(1, seq($.expression, '+', $.expression)),
      prec.left(1, seq($.expression, '-', $.expression)),
      prec.left(2, seq($.expression, '*', $.expression)),
      prec.left(2, seq($.expression, '/', $.expression)),
    ),

    number: $ => /\d+/,

    parenthesized_expression: $ => seq('(', $.expression, ')'),
  }
});

tree-sitter 与 PEG 解析器的关键区别： - 支持增量解析：编辑后只重新解析变化的部分 - 支持错误恢复：语法错误不会导致整个解析失败 - 使用 GLR 而非递归下降：能处理歧义文法 - 设计目标是 IDE，而非编译器

其他值得关注的工具

九、PEG vs LALR vs LL：三方对决

表达能力

正则语言 ⊂ LL(1) ⊂ LL(k) ⊂ LL(*) ⊂ LALR(1) ⊂ LR(1) ⊂ LR(k)
                                              |
PEG 能识别所有 LL(k) 和 LR(k) 语言           ?
PEG 还能识别某些非上下文无关语言（如 a^n b^n c^n）
PEG 与 CFL 的完整包含关系尚未确定

全面对比

错误消息：PEG 的软肋

PEG 的错误消息问题值得深入讨论。考虑输入 1 + * 2：

在 LL(1) 解析器中，解析器在 * 处知道自己期望一个 Term， 可以报告”期望数字或左括号，但遇到了 *“。

在 PEG 解析器中，情况更复杂： 1. 尝试 Term '+' Expr——成功匹配 Term（即 1）和 + 2. 尝试匹配第二个 Term——尝试 Factor '*' Term 3. Factor 尝试 '(' Expr ')'——失败 4. Factor 尝试 Number——失败 5. Factor 失败，Term 回溯 6. Term 尝试 Factor——同样失败

解析器最终报告的错误位置可能是输入的起始位置，而不是实际的错误位置。 这是因为有序选择的回溯会”吞掉”有用的错误信息。

改进策略： - 记录所有分支中到达的最远位置（“farthest failure”） - 在最远失败位置收集所有期望的 token - 这就是 PEG.js/Peggy 采用的策略

十、Python 3.9：从 LL(1) 到 PEG 的大迁移

历史背景

Python 从 1990 年的第一个版本开始，就使用 LL(1) 解析器。 近 30 年间，这个解析器累积了大量的 hack：

1. lambda 表达式的位置限制：LL(1) 无法自然处理 lambda 在表达式中的出现位置
2. 赋值表达式（海象运算符）：:= 的引入需要繁琐的文法改写
3. 星号解包：a, *b, c = [1, 2, 3, 4] 的文法描述极不自然
4. match 语句：Python 3.10 的模式匹配在 LL(1) 下几乎无法实现

Guido 的决定

2019 年，Guido van Rossum 在一系列博客文章中详细论述了为什么 Python 需要新解析器， 并最终在 PEP 617 中提出了使用 PEG 解析器的方案。

关键论点： - PEG 的无限前瞻让文法编写更自然 - 有序选择消除了 LL(1) 的冲突问题 - 新解析器可以直接生成 AST，跳过 CST 到 AST 的转换步骤

实现细节

Python 的 PEG 解析器（pegen）有几个值得注意的设计选择：

# Python 新文法（Grammar/python.gram）的片段
assignment[expr_ty]:
    | a=NAME ':' b=expression c=['=' d=annotated_rhs { d }] {
        _PyAST_AnnAssign(
            CHECK(expr_ty, _PyPegen_set_expr_context(p, a, Store)),
            b, c, 1, EXTRA) }
    | a=('(' b=single_target ')' { b }
         | single_subscript_attribute_target) ':' b=expression
         c=['=' d=annotated_rhs { d }] {
        _PyAST_AnnAssign(a, b, c, 0, EXTRA) }
    | a=(z=star_expressions ',' { z } | star_expressions)
      augassign ~ b=(yield_expr | star_expressions) {
        _PyAST_AugAssign(/* ... */) }
    | a=star_expressions '=' b=star_expressions {
        /* 简单赋值 */ }

几个关键点： - ~ 切断运算符：一旦匹配过 ~，后续分支不再尝试回溯。 这改善了错误消息，也提高了性能。 - 直接生成 AST：动作代码直接调用 _PyAST_* 函数构造 AST 节点。 - 使用 Packrat 记忆化：但只对标记了 @ 的规则启用。 - 软关键字：match 和 case 在 PEG 文法中可以不作为保留字处理。

性能对比

Python 团队的基准测试显示： - 新 PEG 解析器比旧 LL(1) 解析器慢约 10% - 但内存使用在可接受范围内 - 新文法的可维护性大幅提升 - 新特性（如 match 语句）的实现成本显著降低

这个 10% 的性能损失被认为是值得的——解析只占编译总时间的一小部分， 而开发者体验和语言演化能力的提升是更重要的收益。

十一、工程实践中的陷阱

以下是使用 PEG 解析器时常见的工程问题及其解决方案：

贪婪匹配陷阱详解

// 错误：尝试匹配 C 风格注释
Comment <- '/*' .* '*/'

问题：.* 会贪婪地消耗所有字符，包括 */，导致永远无法匹配到结束标记。

// 正确：使用负向前瞻
Comment <- '/*' (!'*/' .)* '*/'

!'*/' 在每个字符前检查：如果接下来不是 */，则消耗一个字符。

有序选择遮蔽详解

// 错误：keyword 总是被 identifier 先匹配
Token <- identifier / keyword
identifier <- [a-zA-Z]+
keyword <- 'if' / 'while' / 'for'

identifier 会匹配 if、while 等关键字，因为它在前面。

// 正确：关键字优先，且用负向前瞻防止部分匹配
Token <- keyword / identifier
keyword <- ('if' / 'while' / 'for') ![a-zA-Z]
identifier <- [a-zA-Z]+

十二、结语：选择的代价

PEG 的设计哲学可以概括为一句话： 用确定性换取简单性，用空间换取时间，用限制换取表达力。

有序选择消除了歧义，代价是某些合法的分支可能被遮蔽。 Packrat 记忆化保证了线性时间，代价是线性空间乘以文法大小。 无限前瞻带来了自由，代价是错误消息的质量下降。 禁止左递归简化了实现，代价是文法的自然性受损。

在实际工程中，PEG 最适合以下场景： - DSL 和配置文件：文法规模小，记忆化开销可忽略 - 快速原型：PEG 文法的可读性和编写速度远超 LALR - 嵌入式解析：不需要独立的编译步骤 - 需要无限前瞻的场景：某些语法结构在有限前瞻下极难处理

而对于大规模编程语言的编译器，PEG 的选择更加微妙。 Python 3.9 的迁移证明了 PEG 可以胜任这个角色， 但也表明需要 cut 运算符、选择性记忆化等工程手段来弥补纯 PEG 的不足。

Bryan Ford 在 2004 年的论文结尾写道：

Parsing expression grammars provide a natural and direct way of expressing the syntax of a language as it is actually parsed by a top-down parser, rather than as it might be described in an abstract grammar formalism.

这段话揭示了 PEG 的本质：它不是对语言的抽象描述，而是对解析过程的直接编码。 文法即解析器，解析器即文法。 这种同一性既是 PEG 最大的优势，也是它最深层的限制—— 当你的文法就是你的解析器时，文法的每一个细节都有运行时的含义， 而你对”语言”和”实现”的区分就此模糊。

对于编译器工程师而言，理解这种权衡， 比选择哪种工具更加重要。

上一篇: LR 与 LALR 解析 下一篇: 寄存器分配 相关阅读: - DFA 最小化 - LR 与 LALR 解析