第3章 解析表达式（Parsing Expressions: Tokens to Syntax Trees）
一、导读
语法分析（Parsing）负责将 Token 序列组织成语法树结构。本章介绍递归下降解析方法（Recursive Descent Parsing），从最简单的表达式开始，逐步处理运算符优先级和结合性，构建出能够正确表示程序结构的抽象语法树（Abstract Syntax Tree, AST）。
学习目标：理解上下文无关文法（Context-Free Grammar）的基本概念，掌握递归下降解析的实现方法，学会处理运算符优先级和结合性，能够构建正确的抽象语法树。
重要性：语法分析是语言处理的核心环节，它将线性的 Token 序列转换为层次化的树结构，为后续的语义分析和代码生成奠定基础。理解语法分析的原理，能帮助你设计更清晰的语言语法，也能让你更好地理解和调试解析错误。
核心问题：如何将扁平的 Token 流转换为树形结构？如何正确处理运算符优先级（如乘法优先于加法）？如何处理结合性（如减法是左结合）？如何检测和报告语法错误？
二、核心概念详解
2.1 上下文无关文法
上下文无关文法（CFG）用一组产生式规则来描述语言的语法结构。每个规则由一个非终结符（Non-terminal）和一个由终结符（Terminal）与非终结符组成的右部构成。例如，Lox 的表达式文法可以表示为：
expression -> literal | unary | binary | grouping
literal -> NUMBER | STRING | "true" | "false" | "nil"
grouping -> "(" expression ")"
unary -> ( "-" | "!" ) expression
binary -> expression operator expression
operator -> "+" | "-" | "*" | "/" | "==" | "!=" | "<" | ">" | "<=" | ">="文法是递归下降解析器的理论基础，每条产生式规则对应解析器中的一个函数。
2.2 递归下降解析的基本思想
递归下降是一种自顶向下（Top-Down）的解析方法。它为文法中的每个非终结符编写一个递归函数，通过函数调用来模拟推导过程。例如，解析 expression 的函数会依次尝试匹配 literal、unary、binary、grouping 等规则。当遇到非终结符时，调用对应的解析函数；当遇到终结符时，检查当前 Token 是否匹配。这种方法的实现直观且易于理解，是最常用的手工解析技术。
2.3 运算符优先级的处理
表达式中不同运算符有不同的优先级。例如，在 1 + 2 * 3 中，乘法应该优先于加法执行，结果为 7 而非 9。解析器需要通过分层产生式来确保高优先级的运算符先生成子树。Lox 的优先级层次从低到高为：赋值 < 逻辑或 < 逻辑与 < 相等 < 比较 < 加法 < 乘法 < 一元 < 调用。每一层只处理对应优先级的运算符，高优先级的运算通过递归调用低层的解析函数来处理。
expression -> assignment
assignment -> IDENTIFIER "=" assignment | logic_or
logic_or -> logic_and ( "or" logic_and )*
logic_and -> equality ( "and" equality )*
equality -> comparison ( ( "!=" | "==" ) comparison )*
comparison -> term ( ( ">" | ">=" | "<" | "<=" ) term )*
term -> factor ( ( "-" | "+" ) factor )*
factor -> unary ( ( "/" | "*" ) unary )*
unary -> ( "!" | "-" ) unary | call
call -> primary ( "(" arguments? ")" )*
primary -> NUMBER | STRING | "true" | "false" | "nil" | "(" expression ")"2.4 结合性的规则应用
当相同优先级的运算符连续出现时，结合性（Associativity）决定了运算的顺序。左结合（Left-Associative）运算符从左到右计算，如 5 - 3 - 2 等价于 (5 - 3) - 2 = 0。右结合（Right-Associative）运算符从右到左计算，如赋值运算符 a = b = c 等价于 a = (b = c)。在递归下降解析器中，左结合通过循环（while 或 *）实现，右结合通过递归调用自身实现。
2.5 抽象语法树的设计
抽象语法树（AST）是去除语法细节（如括号、分号）后的程序结构表示。每种表达式对应一个 AST 节点类型。例如，二元表达式节点包含左操作数、运算符和右操作数；字面量节点包含具体的值；一元表达式节点包含运算符和操作数。AST 的设计应该简洁且信息完整，既能正确表达程序的语义，又便于后续的遍历和处理。
三、深入分析
3.1 递归下降与回溯
基本的递归下降解析器是确定性（Deterministic）的，不需要回溯。这要求文法是 LL(1) 的，即从左到右扫描、最左推导、只需前瞻一个 Token 就能做出解析决策。当文法不满足 LL(1) 条件时，可能需要回溯或改写文法。在实践中，大多数编程语言的表达式文法都可以改写为 LL(1) 形式，因此递归下降是一种实用的解析方法。
3.2 错误恢复策略
当解析器遇到语法错误时，需要能够恢复并继续解析以发现更多错误。常见的错误恢复策略包括：恐慌模式（Panic Mode），即跳过 Token 直到遇到同步点（如语句结尾的分号）；短语级恢复（Phrase-Level Recovery），即在当前位置插入预期的 Token 继续解析。良好的错误恢复能提供更有用的错误信息，提升开发体验。
3.3 Pratt 解析：一种替代方案
除了递归下降，Pratt 解析（也称为自顶向下运算符优先级解析）是另一种处理表达式的有效方法。它将运算符的优先级和结合性编码为数值（绑定力），通过比较当前运算符和前一个运算符的绑定力来决定解析顺序。Pratt 解析的代码更简洁，特别适合处理运算符优先级层次较多的语言，Rust 和 JavaScript 引擎（如 SpiderMonkey）的表达式解析器都采用了这种方法。
四、实践案例
4.1 案例一：解析算术表达式
考虑表达式 3 + 4 * 2，解析过程如下：
term() 调用 factor() 解析 3，返回 Literal(3)
term() 遇到 +，进入循环，调用 factor() 解析右侧
factor() 调用 unary() -> call() -> primary() 解析 4，返回 Literal(4)
factor() 遇到 *，进入循环，调用 unary() -> call() -> primary() 解析 2，返回 Literal(2)
factor() 构建 Binary(Literal(4), *, Literal(2))
term() 构建 Binary(Literal(3), +, Binary(Literal(4), *, Literal(2)))
最终的 AST 正确反映了乘法优先于加法的语义。
4.2 案例二：解析嵌套括号表达式
考虑表达式 (1 + 2) * (3 - 4)，解析过程如下：
factor() 调用 primary()，遇到 (，递归调用 expression()
内层 expression() 解析 1 + 2 为 Binary(Literal(1), +, Literal(2))
匹配 )，返回括号内的表达式
factor() 遇到 *，继续解析右侧
右侧 (3 - 4) 类似地解析为 Binary(Literal(3), -, Literal(4))
最终构建 Binary(Binary(1,+,2), *, Binary(3,-,4))
括号通过递归调用改变了默认的优先级顺序，确保括号内的表达式先被求值。
五、常见误区
5.1 误区一：递归下降只能处理简单文法
递归下降可以处理相当复杂的文法，包括大多数编程语言的表达式语法。只要文法是 LL(k) 的（前瞻 k 个 Token 可确定解析决策），递归下降就能处理。对于更复杂的文法，可以通过改写使其满足 LL(1) 条件。
5.2 误区二：AST 应该保留所有语法细节
AST 的设计原则是去除不必要的语法细节（如括号、分号、关键字），只保留语义信息。括号的作用已经在树结构中通过层次关系体现，不需要作为节点保留。过度保留语法细节会增加后续处理的复杂性。
5.3 误区三：优先级层次越多解析器越复杂
实际上，优先级层次多只是意味着解析函数多，但每个函数的逻辑都很简单（一个循环加一个递归调用）。层次分明反而使代码更清晰、更易于维护。将多个优先级混在一个函数中处理会导致复杂的条件判断。
5.4 误区四：解析器不需要考虑错误恢复
一个遇到错误就停止的解析器在实际使用中体验很差。用户修复一个错误后可能又出现新的错误，反复编译-修复的循环效率很低。良好的错误恢复能一次报告多个错误，显著提升开发效率。
六、本章小结
本章讲解了如何使用递归下降方法解析表达式。通过分层处理不同优先级的运算符，正确处理结合性规则，解析器能够构建出语义正确的抽象语法树。递归下降方法实现简单、代码清晰，适合手工编写解析器。理解文法与解析器之间的对应关系，是掌握语法分析技术的关键。
七、扩展知识：解析器生成工具
在实际工程中，许多项目使用解析器生成工具而非手工编写解析器。常见的工具包括：ANTLR（支持 LL(*) 解析，生成 Java/C++/Python 等代码）、Bison/Yacc（LALR(1) 解析，生成 C/C++ 代码）、PEG.js（基于解析表达文法，生成 JavaScript 代码）。这些工具接受文法定义文件，自动生成解析器代码，大幅减少了开发工作量。然而，手工编写的解析器在错误处理、性能优化和代码可读性方面通常更优。Rust 编译器（rustc）、Go 编译器和 V8 JavaScript 引擎都使用手工编写的解析器。选择手工还是工具生成取决于项目规模、团队经验和性能需求。
八、思考题
请为 Lox 语言添加幂运算符 **（右结合，优先级高于乘法但低于一元运算符），写出修改后的文法规则和对应的解析函数。
如果将 + 运算符改为右结合，1 + 2 + 3 + 4 的 AST 结构会发生什么变化？请画出两种结合性对应的 AST。
请设计一个恐慌模式的错误恢复策略：当解析器在 primary() 中遇到非预期的 Token 时，如何跳过错误并继续解析？
比较递归下降和 Pratt 解析在处理表达式时的优劣，分别说明它们适合的场景。
为什么大多数编程语言将赋值运算符设计为右结合？请从语义和实现两个角度分析。
请为 Lox 语言添加三元条件运算符 ?:（如 x > 0 ? "positive" : "non-positive"），说明其优先级和结合性，并写出文法规则。