「语法分析与 AST 构建」

1. 语法分析概述

一句话总结： 语法分析器消费词法分析产生的 token 流，依据文法识别短语结构并构建抽象语法树。

语法分析是编译器前端的第二站，输入是词法分析器产出的 token 序列，输出是抽象语法树（AST）。AST 省略掉括号、分隔符等仅用于表达的细节，保留运算结构与语义要点，是后续语义分析、中间表示与代码生成的共同输入。语法分析器的两大技术流派是自顶向下的递归下降和自底向上的 LR 分析。

token 流:  <id:a> <op:=> <num:10> <op:+> <id:b>

AST:
       =
      / \
     a   +
        / \
       10  b

语法分析的难点在于歧义与优先级。运算符 1 + 2 * 3 若不加处理可归约出两种语法树，分别对应 (1+2)*3 与 1+(2*3)。解决歧义的手段包括改写文法消除左递归、为优先级引入分层非终结符，以及使用运算符优先级表指导归约。

2. 上下文无关文法与推导

一句话总结： 上下文无关文法用产生式描述语言的嵌套结构，推导序列刻画语法树的生长过程。

一个上下文无关文法由终结符、非终结符、开始符号与产生式集合组成。产生式的左边是单个非终结符，右边是由终结符与非终结符组成的串。最左推导每次替换最左边的非终结符，语法树与最左推导一一对应；若同一句型存在两棵不同的语法树，文法就是歧义的。

文法 G:
  E  -> E + T | T
  T  -> T * F | F
  F  -> ( E ) | id

最左推导 id + id * id:
  E
  => E + T
  => T + T
  => F + T
  => id + T
  => id + T * F
  => id + F * F
  => id + id * F
  => id + id * id

消除左递归是递归下降的前提。E -> E + T 这种直接左递归会令递归下降函数无限循环，改写为 E -> T E' 与 E' -> + T E' | ε 后仍表达同样的语言。间接左递归与公共前缀引起的回溯也要处理，必要时做提取左因子，把选择推迟到看到足够前瞻 token 之后。

3. 递归下降解析器

一句话总结： 递归下降解析器把每个非终结符映射为一个函数，用调用与返回模拟语法树的展开过程。

递归下降是最易手写的语法分析方式：文法里每个非终结符对应一个解析函数，函数按产生式右侧逐 token 消费，遇到非终结符就递归调用对应函数，遇到终结符就匹配当前 token 并推进。为避免回溯，每个产生式分支需要能靠 lookahead 区分，这通常通过前瞻一个或几个 token 实现。

class RecursiveDescentParser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    def peek(self):
        return self.tokens[self.pos]

    def consume(self, kind):
        tok = self.tokens[self.pos]
        if tok.kind != kind:
            raise ParseError(
                f"expected {kind}, got {tok.kind} at {tok.pos}")
        self.pos += 1
        return tok

    def parse_expr(self):
        node = self.parse_term()
        while self.peek().kind in ("OP_PLUS", "OP_MINUS"):
            op = self.consume(self.peek().kind)
            right = self.parse_term()
            node = BinOp(op, node, right)
        return node

    def parse_term(self):
        node = self.parse_factor()
        while self.peek().kind in ("OP_MUL", "OP_DIV"):
            op = self.consume(self.peek().kind)
            right = self.parse_factor()
            node = BinOp(op, node, right)
        return node

递归下降解析器配合循环而非递归处理左递归运算符，可自然表达左结合。前瞻失败时抛出 ParseError 并携带 token 位置，便于上层错误恢复。大量生产语言（Go、Rust、Java 的早期实现）都采用递归下降，因为手写代码便于加入表达式层级、错误恢复与语法糖特判。

4. LL 分析与 FIRST/FOLLOW

一句话总结： LL 分析用前瞻 token 决定产生式选择，FIRST 与 FOLLOW 集合给出可解析性的判定条件。

LL(k) 分析从左到右扫描输入、产生最左推导、使用 k 个前瞻 token。FIRST 集合收集一个产生式右部可能打头的终结符，FOLLOW 集合收集某非终结符之后可能出现的终结符。当每个非终结符的各产生式 FIRST 集合两两不相交时，文法属于 LL(1)，可以用一个 token 前瞻无回溯地解析。

def compute_first(nonterm, rules):
    first = set()
    for rhs in rules[nonterm]:
        if is_terminal(rhs[0]):
            first.add(rhs[0])
        else:
            first |= compute_first(rhs[0], rules)
            if rhs[0] derives_empty():
                first |= compute_first(nonterm, rules)
    return first

def build_ll1_table(nonterms, rules):
    table = {}
    for nt in nonterms:
        for rhs in rules[nt]:
            for t in first_of(rhs):
                table[(nt, t)] = rhs
            if derives_empty(rhs):
                for t in follow(nt):
                    table[(nt, t)] = rhs
    return table

LL(1) 分析表构造时若某单元格被填入多条产生式，说明文法不是 LL(1)。悬挂 else 是经典歧义：if c1 then if c2 then s1 else s2 中的 else 既可归属外层也可归属内层，多数语言选择就近匹配内层，生成器需显式消歧。

5. LR 分析与冲突消解

一句话总结： LR 分析用状态栈自底向上归约，能处理比 LL 更广的文法，冲突集中在移进与归约的抉择上。

LR 分析维护一个状态栈，读入 token 后依据动作表决定移进（shift）或归约（reduce）。构建 SLR/LALR/LR(1) 分析表时，核心是构造规范族状态集合并计算项目集。项目是带圆点的产生式，圆点位置表示已识别与待识别的边界。状态转移依据项目集闭包推进，归约依据 lookahead 集合触发。

状态 0 的项目集:
  E' -> . E
  E  -> . E + T
  E  -> . T
  T  -> . T * F
  T  -> . F
  F  -> . ( E )
  F  -> . id

读入 id 后转移到状态 5:
  F -> id .     ← 可归约项目

yacc/bison 通过为 token 声明优先级与结合性消解移进归约冲突：移进优先于归约，同优先级按结合性处理。用优先级声明的文法比改写文法的分析表更小、更易维护。LR 分析器的错误处理没有递归下降那么天然，一般依赖显式错误产生式或 panic 模式：遇到错误 token 时丢弃输入直到能重新同步。

6. 运算符优先级与 Pratt 解析

一句话总结： Pratt 解析把运算符优先级编码进数字，用钳制函数实现优先级驱动的表达式解析，适合嵌入式脚本。

Pratt 解析（优先级爬升）是表达式解析的高效方案。每个 token 关联一个左绑定力（left binding power）与一个 nud/led 处理函数：nud 处理前缀位置，led 处理中缀位置。解析时递归比较绑定力，绑定力小的运算符会被外层钳制住，从而让优先级高的运算符先聚合成子表达式。

def parse_expression(min_bp=0):
    tok = peek()
    left = nud(tok)          # 处理前缀与字面量
    while True:
        op = peek()
        lbp = infix_binding_power(op)
        if lbp < min_bp:
            break
        consume(op)
        rbp = lbp if left_assoc(op) else lbp - 1
        right = parse_expression(rbp)
        left = BinOp(op, left, right)
    return left

# 绑定力表
BINDING = {"=": 10, "+": 50, "-": 50,
           "*": 60, "/": 60, "**": 70,
           "(": 80, ".": 90, "[": 90}

右结合运算如幂与赋值在 led 中把右结合力减一传入递归，使其更紧密地嵌套右侧。Pratt 解析天然处理一元负号（nud）、下标、方法调用与条件表达式，且无需单独的优先级文法层级。它是 CPython、许多脚本语言与 lisp 方言解析器的通用选择。

7. AST 构建与错误恢复

一句话总结： 语法树应精简为语义友好的 AST，错误恢复策略决定一次编译能报告多少个错误。

语法树到 AST 的转化要点是丢弃纯语法信息：括号、逗号分隔符、分号等 token 不再出现在树中；运算符直接成为节点类型；while 语句的圆括号隐去后仅保留条件与循环体。AST 节点的设计要便于遍历：统一的 Node 基类、可比较的 kind、以及指向源码位置（行号列号）的字段，供后端报错使用。

class Node:
    __slots__ = ("kind", "loc", "children")
    def __init__(self, kind, loc, children=None):
        self.kind = kind
        self.loc = loc
        self.children = children or []

def parse_with_recovery(parser):
    errors = []
    def sync():
        while parser.peek().kind not in SYNC_SET:
            parser.advance()
    try:
        return parser.parse_program()
    except ParseError as e:
        errors.append(e)
        sync()
        # 跳过错误后继续解析语句级成分
        return parse_program_with_errors(parser, errors)

错误恢复的目标是报告有意义的错误并继续解析，尽量不让单个语法错误淹没后续代码。Rust 的 rustc 在语法错误后仍尽力构造 AST 以便类型检查报告更多问题。AST 的构建顺序要保证每个节点在创建时就绑定 loc，否则后续多层报告错误时定位会非常困难。

7.1 位置信息与工具链集成

AST 节点携带的行列信息不仅服务于语法报错，还贯穿语义检查、代码生成与 IDE 的跳转定义、语法高亮与格式化。解析器创建节点时应从当前 token 快照复制 loc，后续变换保留 loc 引用。折叠与重写产生的合成节点要标注来源范围，供工具链区分原始代码与派生物。

8. 总结

语法分析把扁平的 token 序列还原为嵌套结构，是连接词法层与语义层的枢纽。文法设计、冲突消解与错误恢复三者相互制约，工程上往往要在文法的纯粹性与可维护性之间取舍。下一站将由语义分析把结构化为意义。

延伸阅读

• 词法分析器实现
• 语义分析与中间表示
• 中间代码优化
• 目标代码生成
• 解释器与 JIT 编译