编译原理基础¶

概述¶

编译原理是研究编译程序构造的理论和技术。编译程序将高级语言源程序翻译成等价的目标程序,是连接高级语言和机器语言的桥梁。

编译程序的结构¶

编译程序的组成

编译程序通常由多个阶段组成,每个阶段完成特定的功能。

graph LR
    A[源程序] --> B[词法分析]
    B --> C[语法分析]
    C --> D[语义分析]
    D --> E[中间代码生成]
    E --> F[代码优化]
    F --> G[目标代码生成]
    G --> H[目标程序]

词法分析¶

功能¶

词法分析(Lexical Analysis)

将源程序的字符流分解为单词流。

单词类型¶

单词类型	说明	示例
关键字	语言的保留字	if, while, for
标识符	用户定义的名称	变量名、函数名
常数	字面量	123, 3.14, "hello"
运算符	操作符号	+, -, *, /, =
界符	分隔符号	; , ( ) { }

词法分析示例¶

源程序:

C
int a = 10;

单词流:

Text Only
1 2 3 4 5	`< int, 关键字 > < a, 标识符 > < =, 运算符 > < 10, 常数 > < ;, 界符 >`

语法分析¶

功能¶

语法分析(Syntax Analysis)

根据语法规则,分析单词流是否构成合法的语法单位。

语法分析方法¶

1. 自顶向下分析¶

自顶向下分析

从文法的开始符号出发,试图推导出输入串。

方法:

递归下降分析
预测分析(LL分析)

2. 自底向上分析¶

自底向上分析

从输入串出发,试图归约到文法的开始符号。

方法:

算符优先分析
LR分析(SLR, LR(1), LALR)

语法树¶

语法树示例

表达式: a + b * c

Text Only
1 2 3 4 5	`+ / \ a * / \ b c`

语义分析¶

功能¶

语义分析(Semantic Analysis)

检查语义正确性,进行语义处理。

主要任务¶

类型检查: 检查运算符和操作数的类型是否匹配
语义一致性检查: 检查变量是否声明、是否重复定义等
作用域分析: 确定标识符的作用域
生成中间代码: 生成与机器无关的中间表示

类型检查示例¶

C
int a = 10;
float b = 3.14;
int c = a + b;  // 类型不匹配警告

中间代码生成¶

中间代码形式¶

常见中间代码形式

中间代码是源程序和目标代码之间的表示。

1. 三地址码¶

三地址码

每条指令最多包含三个地址。

示例:

Text Only
1 2 3 4 5	`表达式: a + b * c 三地址码: t1 = b * c t2 = a + t1`

2. 四元式¶

四元式

(运算符, 操作数1, 操作数2, 结果)

示例:

Text Only
1 2 3 4 5	`表达式: a + b * c 四元式: (*, b, c, t1) (+, a, t1, t2)`

3. 逆波兰表示¶

逆波兰表示(后缀表达式)

运算符在操作数之后。

示例:

Text Only
1 2	`中缀表达式: a + b * c 逆波兰表示: a b c * +`

代码优化¶

优化分类¶

代码优化

对中间代码进行等价变换,提高执行效率。

1. 局部优化¶

局部优化

在基本块内进行的优化。

优化技术:

常量合并
公共子表达式删除
死代码删除

示例:

Text Only
1 2 3 4 5 6	`优化前: t1 = 2 * 3 t2 = a + t1 优化后: t2 = a + 6`

2. 全局优化¶

全局优化

跨基本块的优化。

优化技术:

循环优化
全局公共子表达式删除
复写传播

3. 循环优化¶

循环优化

针对循环的优化。

优化技术:

代码外提: 将循环不变量移到循环外
强度削弱: 用低强度运算代替高强度运算
归纳变量删除

示例:

C
// 优化前
for (int i = 0; i < n; i++) {
    a[i] = i * 4;  // 每次都计算 i * 4
}

// 优化后
int j = 0;
for (int i = 0; i < n; i++) {
    a[i] = j;  // 用加法代替乘法
    j += 4;
}

目标代码生成¶

功能¶

目标代码生成

将中间代码翻译成目标机器的机器语言。

主要任务¶

指令选择: 选择合适的机器指令
寄存器分配: 为变量分配寄存器
指令调度: 安排指令执行顺序

目标代码示例¶

中间代码:

Text Only
1	`t1 = a + b`

目标代码(x86):

Text Only
1 2 3	`MOV EAX, [a] ; 将a装入EAX ADD EAX, [b] ; 将b加到EAX MOV [t1], EAX ; 将结果存入t1`

参考资料¶

编译原理百度百科