5.1.1. 翻译器¶

定义：

示例：

预处理程序：如果你有一种语言有 while 语句 但没有 for 语句，那么构造一种允许 for 语句的新语言，并使用预处理程序把新语言翻译成 旧语言:

for i = 1 to n do
  (stmts)
end for

i = 1
while (i <= n) do
  (stmts)
  i = i + 1
end while

5.2.1. 编译器¶

5.4.1. 词法分析（扫描器）¶

目的：逐字符读取同一个程序，把它们分成称为 记号 （token）的原子单元。

记号：

• 取决于语言和编译器编写者

• 示例：

  保留字： if 、 for

  运算符： +, -, <, =

  常量： 0, 4.89

  标点符号： (, }, [

  标识符： i, myNode

• 被视为一个二元组： token.type 和 token.value

  • token.type 是一个（助记的）整数

  • 有些记号没有 token.value

如何构建一个 扫描器？

• 从头编写

• 使用 lex

Lex 预览

• 想法：用正则表达式描述记号

• 基本语法：

  正则表达式，动作

• 基本语义：

  如果匹配正则表达式，那么执行动作。

• 示例：

除了返回记号的类型和值之外，词法分析器还可能

1. 打印错误信息

2. 在符号表中插入标识符

有时很难区分： 词法分析何时停止、分析何时开始？ 例如，考虑关键字 AND 和 OR。 它们是类型为 AND 和 OR 的记号，还是值为 AND 和 OR 的 RELOP 记号？

5.4.2. 语法分析（Parsing）¶

1. 目的：接收词法分析器生成的记号序列， 检查程序在语法上是否正确，并生成分析树。

2. 语法：由上下文无关文法正式描述。

3. 分析树

if (x <= 0) x = y + z

4. 如何构建一个 分析器？

   • 从头编写

   • 使用诸如 yacc 这样的分析器生成器

5.4.3. 1.3.3 中间代码生成器¶

1. 目的：遍历分析树，生成简单的中间代码。

2. 三地址代码：指令序列，每条指令最多有三个操作数。 （很像汇编，其中每个存储位置都可以充当寄存器）。

   指令：

   1. id := id op id

   2. goto label

   3. if condition goto label

有些编译器把语法分析和中间代码生成 合并在一起（即不生成分析树）

5.4.4. 1.3.4 中间代码生成¶

目的：把中间代码转换为"更好"的代码。

示例：

1. 代码重排

    if (x <= 0) goto L1               if (x$>$0 goto L2
    goto L2                ==>        x = y $+$ z
L1: x = y + z                     L2:
L2:

2. 冗余消除

a = w + x + y                         T1 = x + y
                           ==>        a = w + T1
b = x + y + z                         b = T1 + z

3. 强度削减

x^2                        ==>        x*x
expensive                  ==>        cheap
operator                              operator

4. 频率削减

for (i=1; i<n; i=i+1)                 T1 = sqrt(26)
  x = sqrt(26)             ==>        for (i=1; i<n; i=i+1)
}                                       x = T1
                                      }

备注：

1. 优化的主要标准是速度。

2. 优化需要时间；因此它

   • 是可选的

   • 可能并不可取（在低年级 CS 课程中）

5.4.5. 代码生成¶

目的：把中间代码转换为机器代码（汇编器）

示例： a = b + c

mov  b, R1

add  c, R1

mov  R1, a

备注

1. 完全依赖于机器，而其他阶段则不是

2. "寄存器分配"是最困难的任务

   • 想法 - 使用寄存器（访问快）来避免使用内存 （访问慢）

   • 问题 - 寄存器的数量是有限的（在中间代码 阶段，人们假设寄存器有无穷多个）

5.4.6. 符号表¶

目的：记录源程序中各个对象的信息

示例

• 过程 - 参数的个数和类型

• 简单变量 - 类型

• 数组 - 类型、大小

用途 - 在下列阶段需要这些信息

• 分析（用于类型检查）

• 代码生成（用于生成正确的操作数、分配内存）

5.4.7. 错误处理（Error Handler）¶

错误 - 所有错误都应该被

• 检测到

• 正确地检测到

• 尽快地检测到

• 在适当的位置并以有帮助的方式报告

目的

• 报告错误

• "错误恢复" - 能够继续进行后续处理

注意：错误可能发生在每个阶段

• 拼写错误的记号

• 错误的语法

• 不正确的过程调用

• 无法到达的语句