语法分析（Syntax Analysis）

语法分析（Syntax Analysis） 是编译原理的第二阶段，负责根据源语言的语法规则，将词法分析输出的Token 流转换为抽象语法树（AST）。以下是语法分析的核心知识点：

一、基本概念

1. 语法规则

   • 使用**上下文无关文法（CFG）**描述，形式为 A → α（非终结符 A 可推导出符号串 α）。
   • 例如，算术表达式的 CFG：

     E → E + T | T
     T → T * F | F
     F → (E) | id

2. 抽象语法树（AST）

   • 树形结构，每个内部节点表示语法构造（如表达式、语句），叶子节点为 Token。
   • 示例：表达式 a + b * c 的 AST：

         +
        / \
       a   *
          / \
         b   c

3. 语法分析器的任务

   • 验证 Token 序列是否符合语法规则。
   • 构建 AST，为后续语义分析和代码生成提供结构化表示。

二、上下文无关文法（CFG）

1. 四元组定义

   • G = (V, T, P, S)，其中：
     • V：非终结符集合（如 E, T, F）；
     • T：终结符集合（如 id, +, *, (, )）；
     • P：产生式集合（如 E → E + T）；
     • S：开始符号（如 E）。

2. 推导与归约

   • 最左推导：每次替换最左边的非终结符。
     • 示例：E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ id + T ⇒ id + T * F ⇒ id + F * F ⇒ id + id * id。
   • 最右推导（规范推导）：每次替换最右边的非终结符。
   • 归约：推导的逆过程，用于自底向上分析。

三、语法分析的分类

根据分析方向，语法分析分为：

1. 自顶向下分析

• 核心思想：从开始符号出发，通过最左推导构造 AST。
• 典型算法：递归下降分析（Recursive Descent）、LL(1)分析。
• 适用文法：LL(k)文法（左线性，无左递归）。

LL(1)分析：

• 特点：从左到右扫描输入，最左推导，向前看 1 个 Token。
• 关键工具：预测分析表（根据当前非终结符和输入 Token 选择产生式）。
• 局限性：无法处理左递归（如 E → E + T）和左公因子（如 A → αβ | αγ）。

2. 自底向上分析

• 核心思想：从输入 Token 串开始，通过最右归约（规范归约）构造 AST。
• 典型算法：算符优先分析（Operator Precedence）、LR 分析（SLR、LR(0)、LALR、LR(1)）。
• 适用文法：LR(k)文法（右线性，表达能力强于 LL(k)）。

LR 分析：

• 特点：从左到右扫描，最右归约，向前看 k 个 Token。
• 关键组件：
  • 状态转移表（DFA，记录分析状态）；
  • 动作表（决定移进/归约）；
  • 语法分析栈（存储状态和符号）。
• 示例：SLR(1)分析 id + id 的过程：

  状态栈         符号栈         输入流         动作
  0             $             id + id $      移进
  0 5           $ id          + id $         归约 F → id
  0 3           $ F           + id $         归约 T → F
  0 1           $ E           + id $         移进
  0 1 6         $ E +         id $           移进
  0 1 6 5       $ E + id      $              归约 F → id
  ...           ...           ...            ...

四、语法分析器的实现

1. 手工实现

   • 递归下降分析器：为每个非终结符编写递归函数。
     • 示例（处理 E → T + E | T）：

       def E():
           T()
           while lookahead == '+':
               match('+')
               T()

2. 自动生成工具

   • Yacc/Bison：基于 LR 分析，输入 CFG，生成 C 语言语法分析器。
     • 示例规则：

       E : E '+' T  { $$ = $1 + $3; }
         | T        { $$ = $1; }
         ;

五、关键问题与解决方案

1. 左递归处理

   • 问题：自顶向下分析无法处理左递归（如 E → E + T 导致无限循环）。
   • 解决方案：消除左递归，转换为右递归（如 E → T E', E' → + T E' | ε）。

2. 左公因子提取

   • 问题：LL(1)分析无法处理左公因子（如 A → αβ | αγ 导致预测冲突）。
   • 解决方案：提取左公因子（如 A → α(β | γ)）。

3. 二义性处理

   • 问题：同一 Token 序列可能生成多个不同的 AST（如 if-else 悬挂问题）。
   • 解决方案：
     • 修改文法（如添加优先级规则）；
     • 使用语义规则（如规定 else 匹配最近的 if）。

六、与其他编译阶段的关系

• 输入：词法分析输出的 Token 流。
• 输出：AST，作为语义分析的输入。
• 与语义分析的协作：语法分析仅验证结构合法性，语义分析检查类型匹配、变量声明等。

七、应用场景

• 编译器开发：构建 AST 是编译的核心步骤。
• 代码静态分析：如代码检查工具（ESLint）、IDE 的语法高亮。
• 自然语言处理：句法分析（如依存句法分析）。

总结

语法分析的核心是上下文无关文法和推导/归约，通过自顶向下或自底向上的算法构建 AST。掌握语法分析对于理解编译原理、开发编程语言工具至关重要。