第3章：词法与语法分析（Lexical and Syntax Analysis）

一、导读

1.1 学习目标

本章深入探讨编译器前端的两个核心处理阶段：词法分析和语法分析。通过本章学习，读者应当能够：理解词法分析的工作原理及其与正则表达式的关系；掌握有限自动机在词法分析中的应用方法；了解上下文无关文法与语法分析的理论联系；掌握递归下降和LR解析等主流解析算法的基本思想；认识词法分析与语法分析的协作机制及其工程实现。

1.2 编译器前端的核心任务

编译器的前端负责将人类可读的源代码转换为机器可处理的内部表示。这个过程分为三个主要阶段：词法分析将字符流切分为有意义的词法单元（Token），语法分析将词法单元序列组织为语法树（Parse Tree），语义分析则为语法树添加类型信息和语义约束检查。本章聚焦于前两个阶段，它们是编译器理解程序结构的基础。

1.3 为什么分离词法与语法分析

将编译过程分为词法分析和语法分析两个阶段，是出于工程实用性的考虑。词法分析处理字符级别的低层细节（如空白符处理、注释过滤、字符串解析），语法分析则专注于程序结构的高层组织。这种分离简化了语法分析器的设计，使其不必处理字符流的复杂性，同时也使得词法规则可以用更简单的正则表达式来描述，而非更复杂的上下文无关文法。

二、核心概念详解

2.1 词法分析的基本原理

词法分析（Lexical Analysis）是编译的第一个阶段，其任务是将源程序的字符流转换为词法单元（Token）序列。每个词法单元由一个类型（如关键字、标识符、运算符、字面量）和一个可选的属性值（如标识符的名称、数字的字面值）组成。

词法分析器的工作可以用正则表达式来精确描述。例如：

• 关键字：if|else|while|for|return|int|float
• 标识符：[a-zA-Z_][a-zA-Z0-9_]*
• 整数常量：[0-9]+
• 浮点常量：[0-9]+\.[0-9]+([eE][+-]?[0-9]+)?
• 运算符：\+|-|\*|/|==|!=|<=|>=|&&|\|\|

词法分析器在识别词法单元时，还需要处理空白符（空格、制表符、换行符）和注释的过滤。这些字符在词法分析阶段被跳过，不参与语法分析。

2.2 有限自动机与词法分析

有限自动机（Finite Automaton）是实现词法分析器的数学模型。它是一种具有有限个状态的计算模型，根据输入字符在状态之间进行转移。有限自动机分为两种：

确定性有限自动机（DFA, Deterministic Finite Automaton） 在每个状态下，对于每个输入字符，最多只有一个确定的状态转移。DFA的执行效率高，每个字符只需检查一次，是词法分析器实现的理想选择。

非确定性有限自动机（NFA, Non-deterministic Finite Automaton） 允许在同一状态下对同一输入字符有多个可能的转移，也允许空转移（epsilon transition）。NFA更容易从正则表达式构造，但执行时需要跟踪多个可能的状态路径。

从正则表达式到词法分析器的实现路径是：正则表达式 → NFA → DFA → 最小化DFA → 词法分析器代码。工具如Lex和Flex可以自动完成这一转换过程，程序员只需提供正则表达式规则，工具就会生成高效的词法分析器代码。

2.3 上下文无关文法与语法分析

语法分析（Syntax Analysis / Parsing）根据上下文无关文法（Context-Free Grammar, CFG）的规则，将词法单元序列组织成语法树结构。语法分析验证源程序是否符合语言的语法规则，并为后续的语义分析提供结构化的输入。

上下文无关文法由四个组成部分：终结符集合（词法单元）、非终结符集合（语法结构名称）、产生式集合（规则）和开始符号。文法定义了语言的语法结构，每一个合法的程序都对应至少一棵语法分析树。

语法分析算法分为两大类：

自顶向下解析（Top-Down Parsing） 从文法的开始符号出发，尝试构造一棵以开始符号为根的语法树，使得叶节点从左到右恰好构成输入的词法单元序列。递归下降解析器是自顶向下解析的直观实现，每个非终结符对应一个递归函数。LL(1)解析器是一种重要的自顶向下解析方法，它使用一个前看符号来决定使用哪条产生式规则。

自底向上解析（Bottom-Up Parsing） 从输入的词法单元序列出发，逐步将子串归约为非终结符，直到归约为开始符号。LR解析器是自底向上解析的主流方法，包括SLR、LALR和LR(1)等变体。LR解析器的解析能力最强，能够处理几乎所有 programming language 的语法结构。Yacc和Bison是生成LR解析器的经典工具。

2.4 递归下降解析器的实现

递归下降（Recursive Descent）解析器是自顶向下解析的最直观实现。对于文法中的每个非终结符，编写一个对应的递归函数。函数的任务是根据当前输入词法单元选择正确的产生式，并递归调用其他非终结符对应的函数。

考虑以下算术表达式文法：

expr   → term (('+' | '-') term)*
term   → factor (('*' | '/') factor)*
factor → NUMBER | '(' expr ')'

对应的递归下降解析器伪代码为：

function expr():
    term()
    while lookahead in ['+', '-']:
        match(lookahead)
        term()

function term():
    factor()
    while lookahead in ['*', '/']:
        match(lookahead)
        factor()

function factor():
    if lookahead == NUMBER:
        match(NUMBER)
    elif lookahead == '(':
        match('(')
        expr()
        match(')')
    else:
        error("unexpected token")

递归下降解析器易于理解和实现，但要求文法不能含有左递归。左递归是指非终结符直接或间接地推导出以自身开头的产生式，这会导致递归下降解析器无限递归。消除左递归是应用递归下降解析的前提条件。

2.5 LR解析算法

LR解析（LR Parsing）是最强大的自底向上解析方法。"L"表示从左到右扫描输入，"R"表示构造最右推导的逆过程。LR解析器使用一个状态栈和一个分析表来驱动解析过程，包含移进（Shift）和归约（Reduce）两种基本操作。

LR解析的核心思想是维护一个"句柄"（Handle）——即最左边的可以直接归约的子串。当栈顶形成某个产生式的右部时，将其归约为对应的非终结符。当栈顶无法归约时，将下一个输入词法单元移进栈中。

LR解析器的家族包括：SLR(1)（简单LR）解析能力最弱但分析表最小；LALR(1)（向前LR）在SLR和LR(1)之间取得平衡，是Yacc/Bison的默认选择；LR(1)解析能力最强但分析表可能非常大。大多数编程语言的语法都可以用LALR(1)文法来描述。

三、深入分析

3.1 错误恢复策略

在实际编译过程中，源程序往往包含语法错误。编译器不仅需要检测错误，还需要从错误中恢复，以便继续解析后续代码并报告尽可能多的错误。常见的错误恢复策略包括：

恐慌模式（Pactic Mode） 在检测到错误时，跳过若干词法单元直到遇到一个同步词法单元（如分号或关键字），然后从该点继续解析。这种方法简单但可能遗漏紧跟在错误之后的真正错误。

短语层次恢复（Phrase-Level Recovery） 在局部进行词法单元的插入、删除或替换，试图纠正错误并继续解析。这种方法可以恢复更多错误，但实现复杂且可能陷入无限循环。

错误产生式（Error Productions） 在文法中增加专门的错误产生式，使解析器能够在识别错误的同时继续构建部分语法树。这种方法需要预先了解常见的错误模式。

3.2 解析器生成工具

手动实现解析器是一项繁琐且容易出错的工作。解析器生成工具能够根据形式化的文法描述自动生成解析器代码，大大提高了编译器前端的开发效率。

Lex/Flex 是词法分析器生成工具。用户提供正则表达式规则和对应的动作代码，工具自动生成基于DFA的高效词法分析器。Flex是Lex的改进版本，生成更快更小的代码。

Yacc/Bison 是语法分析器生成工具。用户提供上下文无关文法规则和语义动作代码，工具自动生成LALR(1)解析器。Bison是Yacc的GNU版本，兼容Yacc格式并增加了许多实用特性。

ANTLR 是一个现代的解析器生成工具，支持LL(*)解析算法。ANTLR能够自动处理左递归，生成多种目标语言的解析器代码，并提供丰富的错误报告功能。它在工业界得到了广泛应用，如Elasticsearch、Hibernate和Apache Spark等项目都使用ANTLR来解析查询语言。

四、实践案例

4.1 案例一：实现一个简单的表达式计算器

结合词法分析和语法分析，可以实现一个能够计算算术表达式值的程序。词法分析器负责识别数字和运算符，语法分析器使用递归下降方法构建表达式的层次结构，并在解析过程中直接计算表达式的值。

function parseExpr():
    result = parseTerm()
    while lookahead in ['+', '-']:
        op = lookahead
        match(op)
        right = parseTerm()
        if op == '+': result = result + right
        else: result = result - right
    return result

function parseTerm():
    result = parseFactor()
    while lookahead in ['*', '/']:
        op = lookahead
        match(op)
        right = parseFactor()
        if op == '*': result = result * right
        else: result = result / right
    return result

function parseFactor():
    if lookahead == NUMBER:
        value = lookahead.value
        match(NUMBER)
        return value
    elif lookahead == '(':
        match('(')
        value = parseExpr()
        match(')')
        return value

这个计算器正确处理了运算符优先级（乘除优先于加减）和结合性（从左到右），展示了词法分析和语法分析如何协同工作来完成一个简单的语言处理任务。

4.2 案例二：JSON解析器的设计

JSON解析器是词法与语法分析的经典应用。JSON的词法规则相对简单，包括字符串、数字、布尔值、null和结构字符（花括号、方括号、冒号、逗号）。语法分析器则根据JSON的文法规则，将词法单元序列组织为JSON对象和数组的嵌套结构。

一个完整的JSON解析器需要处理多种边界情况：Unicode转义序列（\uXXXX）、嵌套深度限制、大数字精度、重复键检测等。这些细节展示了词法分析和语法分析在实际工程中需要考虑的复杂性。许多编程语言的标准库都内置了JSON解析器，其核心实现正是基于本章介绍的词法与语法分析技术。

五、常见误区

5.1 误区一：正则表达式可以描述所有语法规则

正则表达式只能描述正则语言，而编程语言的语法结构（如嵌套的括号、匹配的if-else）属于上下文无关语言，超出了正则表达式的描述能力。这就是为什么词法分析使用正则表达式，而语法分析需要使用更强大的上下文无关文法。试图用正则表达式解析嵌套结构是常见的错误做法。

5.2 误区二：递归下降可以处理任何文法

递归下降解析器无法处理含有左递归的文法。左递归会导致解析函数无限递归调用自身。此外，当多个产生式具有相同的前缀时，递归下降解析器可能需要大量的回溯来尝试不同的选择，导致解析效率低下。LL(1)文法通过限制产生式的形式来避免这些问题，但也因此限制了可描述的语法范围。

5.3 误区三：解析器只关心语法不关心语义

虽然解析器的主要任务是语法分析，但在实际实现中，解析器通常需要同时执行一些语义相关的操作。例如，在解析变量声明时，解析器需要将变量名插入符号表；在解析类型注解时，解析器需要检查类型的合法性。纯粹的语法分析和语义分析之间的界限在实践中往往是模糊的。

5.4 误区四：词法分析只是简单的字符串分割

词法分析远非简单的字符串分割。它需要处理复杂的模式匹配（如区分关键字和标识符）、多字符运算符的识别（如 == 与 = 的区分）、字符串字面量中的转义序列、多行注释的过滤、以及预处理指令的处理等。一个健壮的词法分析器需要仔细处理各种边界情况。

5.5 误区五：自动生成的解析器一定比手写的差

解析器生成工具生成的代码在性能和可读性上可能不如精心手写代码，但在正确性和维护性上通常更优。自动生成的解析器严格遵循形式化文法，减少了人为错误；当语法发生变化时，只需修改文法描述并重新生成，无需手动调整复杂的解析逻辑。在现代开发中，除非有极端的性能要求，使用解析器生成工具是更合理的选择。

六、本章小结

本章系统讲解了编译器前端的词法分析和语法分析技术。词法分析通过有限自动机识别源程序中的基本词汇单元，将字符流转换为词法单元序列；语法分析借助上下文无关文法将这些单元组织成语法树结构，验证程序的语法合法性。递归下降和LR解析等算法为语法分析提供了具体的实现手段，而解析器生成工具则大幅降低了编译器前端的开发成本。错误恢复策略确保编译器能够在存在语法错误的情况下继续工作，提供有价值的诊断信息。理解这些编译器基础知识有助于我们深入认识程序从源代码到可执行形式的转换过程，为后续学习语义分析、代码优化和运行时系统设计奠定基础。

七、思考题

请为一门简单的编程语言设计词法规则（使用正则表达式）和语法规则（使用BNF），并说明你如何处理关键字和标识符之间的歧义。

比较递归下降解析和LR解析的优缺点。在什么场景下你会选择其中一种而非另一种？

什么是左递归？为什么递归下降解析器不能处理左递归？请给出一种消除左递归的方法。

设计一种错误恢复策略来处理以下常见的语法错误：缺少分号、缺少右括号、拼写错误的关键字。分析你的策略在什么情况下可能失效。

为什么现代编程语言（如Python、Go）倾向于使用比LALR更简单的语法？这种设计选择带来了哪些好处和限制？