Computer Science

WangMC Blog

语义分析

发表于 分类于
本文字数： 3.2k 阅读时长 ≈ 3 分钟

💻 第 6 章：语义分析（知识点讲解）

语义分析 (Semantic Analysis) 是编译器在语法分析（Parsing）之后、代码生成（Code Generation）之前的一个关键阶段。

  • 语法分析（如递归下降法）只关心程序的结构是否正确（例如 if (...) ... 格式对了）。

  • 语义分析则关心程序的含义是否合理（例如 if ("hello" + 5) ...，字符串和数字相加是否“有意义”？）。

6.1 引言

本节介绍语义分析的任务和地位。

  • 承上： 依赖于语法分析器生成的语法树 (Syntax Tree)。

  • 启下： 为后续的中间代码生成和代码优化做准备。

  • 核心任务：

    1. 符号表管理 (Symbol Table)：收集有关变量、函数等标识符的信息。
    2. 类型检查 (Type Checking)：确保操作和操作数之间的类型兼容。
    3. 生成中间代码 (Intermediate Code Generation)：这是本章的重点，将语法树翻译成一种更接近机器指令但又与机器无关的表示（如三地址码或四元式）。

6.2 声明语句翻译 ★

这是符号表的核心应用。当编译器遇到一个声明（如 int a; 或 float b[10];）时：

  1. 登录符号： 将变量名（a 或 b）登记到当前作用域的符号表中。

  2. 记录属性： 存入该变量的类型（int 或 float）。

  3. 分配偏移量： 计算该变量在内存（通常是栈帧）中的相对地址（偏移量）。

  4. 处理数组： 对于数组（如 b[10]），需要额外记录维度、界限和总大小（例如，float 占 4 字节，b 就占 10 * 4 = 40 字节），并存入符号表。

6.3 赋值语句翻译 ★

这是生成中间代码的起点。对于一个简单的赋值语句，如 x = y;：

  1. 查找符号： 在符号表中查找 x 和 y 的地址（偏移量）。

  2. 类型检查： 检查 x 和 y 的类型是否兼容。如果 x 是 int，y 是 float，可能需要插入一个类型转换指令。

  3. 生成代码： 生成一条三地址码（Three-Address Code, TAC），如：

    1
    x = y

6.4 表达式翻译 ★

这是语义分析的重点之一，处理如 x = a + b * c; 这样的语句。

  • 核心： 必须按照优先级（* 优先于 +）和结合性来翻译。

  • 临时变量： 需要引入临时变量（如 t1, t2）来存储中间结果。

  • 翻译过程（三地址码）：

    1
    2
    3
    t1 = b * c      // 1. 先算乘法
    t2 = a + t1     // 2. 再算加法
    x = t2          // 3. 最后赋值

  • 类型检查： 每一步都会检查类型。例如，在 t1 = b * c 中，如果 b 是 int 而 c 是 float，则结果 t1 必须是 float。

（6.4.1 练习解答 和 6.4.2 自学方案 通常是基于语法制导翻译 (SDT)，即在语法树的节点上附加“语义动作”来递归地生成上述代码。）

6.5 - 6.8 条件语句翻译 (1, 2, 3, 小结) ★

这部分（特别是带★的）重点是处理控制流 (Control Flow)。

  • 核心工具： 使用标签 (Label) 和跳转指令 (Jump)。

  • if-then 语句：if (E) S;

    1. 翻译表达式 E。
    2. 生成一个“条件跳转”：如果 E 为假 (false)，则跳转到 S 语句之后的标签 L_end。
    3. 翻译语句 S。
    4. 放置标签 L_end。
    • 三地址码示例：
      1
      2
      3
      4
      code_for_E          // E 的代码
      if_false E goto L_end // 如果 E 为假，跳到 L_end
      code_for_S          // S 的代码
      L_end: ...

  • if-then-else 语句：if (E) S1 else S2; (这是 6.6 的重点)

    1. 翻译 E。
    2. 生成“条件跳转”：如果 E 为假，跳转到 S2 开始的标签 L_else。
    3. 翻译 S1。
    4. 生成“无条件跳转”：执行完 S1 后，跳过 S2，到达 L_end。
    5. 放置 L_else: 标签。
    6. 翻译 S2。
    7. 放置 L_end: 标签。
    • 三地址码示例：
      1
      2
      3
      4
      5
      6
      7
      code_for_E
      if_false E goto L_else
      code_for_S1
      goto L_end
      L_else:
      code_for_S2
      L_end: ...

  • （6.7.1 自学方案 和 6.8 小结 可能会介绍一种更高效的技术叫**“回填” (Backpatching)**，它允许在不知道目标标签在何处时先生成跳转指令，稍后再“填上”目标地址。）

6.9 【自学】循环语句翻译 ★

与条件语句类似，循环（如 while）也需要处理控制流。

  • while 循环：while (E) S;

    1. 放置一个“循环开始”标签 L_start:（用于重新判断条件）。
    2. 翻译表达式 E。
    3. 生成“条件跳转”：如果 E 为假，跳转到循环结束的标签 L_end。
    4. 翻译循环体 S。
    5. 生成“无条件跳转”：跳回 L_start:。
    6. 放置标签 L_end:（循环出口）。
    • 三地址码示例：
      1
      2
      3
      4
      5
      6
      L_start:
      code_for_E
      if_false E goto L_end
      code_for_S
      goto L_start
      L_end: ...

🤖 补充：递归下降法与预测分析法在 “LL” 中的使用

您补充的这几个术语都属于语法分析 (Parsing) 阶段，也就是语义分析（第6章） 的前一个阶段。

1. 什么是 “LL”？

在编译原理中，LL（或 LL(k)）是一个分析器 (Parser) 的类别。

  • 第一个 L： 从Left-to-right（从左到右）扫描输入源代码。

  • 第二个 L： 构建一个Leftmost derivation（最左推导）。

  • (k)： 在决定使用哪个语法规则时，需要“向前看” k 个输入符号。最常见的是 LL(1)。

LL 分析器是一种自顶向下 (Top-Down) 的分析器。它从语法的“开始符号”（比如 Program）出发，试图推导出用户编写的整个源代码。

2. 预测分析法 (Predictive Parsing)

预测分析法是一种实现 LL 分析器的核心策略。

  • 特点： 它是一种不需要回溯 (Backtracking) 的自顶向下分析方法。

  • “预测”的含义： 当分析器处在某个非终结符（比如 Statement）时，它会查看下一个输入符号（例如 if、while 或一个变量名），并立即、准确地“预测”出应该使用哪条语法规则（是 If_Statement 规则，还是 While_Statement 规则）。

  • 实现方式：

    1. 查表法： 使用一个“分析表 (Parsing Table)”和“分析栈 (Stack)”来驱动。
    2. 递归下降法： (见下)

3. 递归下降法 (Recursive Descent Parsing)

递归下降法是实现预测分析器的最直接、最常用的一种编程技术。它是一种手动编写分析器的方法。

  • 核心思想： 为文法中的每一个非终结符（如 Expression, Statement）编写一个对应的函数（或方法）。

  • 它如何工作？

    • 假设文法是：Statement -> If_Stmt | While_Stmt | Assign_Stmt
    • 我们就编写一个函数 parse_Statement()。
    • 在这个函数里，它会“向前看”1个符号：
      • 如果看到 if，它就调用 parse_If_Stmt() 函数。
      • 如果看到 while，它就调用 parse_While_Stmt() 函数。
      • …
    • 假设 If_Stmt 的规则是：'if' '(' Expression ')' Statement
    • 那么 parse_If_Stmt() 函数就会：
      1. 检查当前符号是否是 if（匹配）。
      2. 检查下一个符号是否是 (（匹配）。
      3. 递归调用 parse_Expression() 来解析括号内的表达式。
      4. 检查下一个符号是否是 )（匹配）。
      5. 递归调用 parse_Statement() 来解析 if 语句的主体。

  • “递归” 体现在函数（如 parse_Statement）调用其他函数（如 parse_If_Stmt），而这些函数又可能反过来调用 parse_Statement，形成相互递归。

总结：三者的关系

  1. LL 分析器 是一种自顶向下的分析器类型。

  2. 预测分析法 是实现 LL 分析器的一种策略，特点是“向前看”并且“不回溯”。

  3. 递归下降法 是实现预测分析法的一种具体的编程技术，通过为每个语法规则编写一个函数来实现。

最终的联系： 递归下降法（语法分析）会解析源代码，并（显式或隐式地）构建一棵语法树。然后，语义分析器（第6章）会遍历这棵树，执行类型检查、填充符号表，并最终生成三地址码。