# 编译原理1-引论&概述

1.1程序设计语言与编译

（1）程序设计语言

• 高级语言

• 汇编语言

• 机器语言

在计算机上如何执行一个高级语言程序？

• 把高级语言程序翻译成机器语言程序
• 运行所得的机器语言程序求得计算结果

（2）程序设计语言的转换

翻译：是指能把某种语言的源程序，在不改变语义的条件下，转换成另一种语言程序——目标语言程序。

编译：专指由高级语言转换为低级语言

解释：接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果， 然后再接受下一句。

解释的特点

– 以源程序作为输入，不产生目标程序，一边解释一边执行。

– 优点：直观易懂，结构简单，易于实现人机对话

– 缺点：效率低

编译的转换过程

• 两阶段转换：编译->运行
• 三阶段转换：编译->汇编->运行

(二者除红框内不一样外其他都一样)

1.2编译程序概述

编译程序的工作

可类比自然语言的翻译（识别单词、分析语法、分析语句含义、修饰译文、得出终稿）

对应过程如下：

1.2.1 词法分析

• 任务：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。

• 单词：是高级语言中有实在意义的最小语法单位， 它由字符构成。

词法分析依照词法规则，识别出正确的单词，转换成统一规格，备用。

• 转换：对基本字、运算符、界限符、标识符和常数的转换

转换完成后的格式：（类号、内码）

• 描述词法规则的有效工具是正规式和有限自动机

1.2.2 语法分析

• 任务：在词法分析的基础上，根据语言的语法规则， 把单词符号组成各类的语法单位：短语、子句、语句、过程、程序。

• 语法规则：即语言的规则，又称为文法；规定单词如何构成短语、语句、过程和程序。

• 语法规则的表示 - BNF：A:: =B | C

赋值语句的语法规则

• A:: =V=E

• E:: =T | E+T

• T:: =F | T*F

• F:: =V | (E) | C

• V::= 标识符

• C::= 常数

• 语法分析的方法 - 推导 (derive) 和归约 (reduce)

推导：最左推导、最右推导（规范推导）

归约：最右归约、最左归约（规范规约）

例：

最右推导&最左归约：

最左推导&最右归约：

推导时，最哪边推导则最先推导哪边的变量。归约同理。

规范推导的逆过程即规范规约。

如果推不出则说明该语句的语法错误。

语法分析过程也可以用一棵倒着的树来表示，这棵树叫做语法树。

例如：x=a+b*50的语法树

1.2.3 语义分析和中间代码生成

• 任务：对语法分析识别出的各类语法范畴，分析其含义， 进行和初步翻译，产生介于源代码和目标代码之间 的一种代码。

• 分为两阶段工作：

– 对每种语法范畴进行静态语义检查

– 若语义正确，就进行中间代码的翻译

• 中间代码形式：四元式、三元式、逆波兰式

例如将x=a+b*50变成中间代码

序号	算符	左操作数	右操作数	结果
（1）	将整常数50转换为实常数			T1
（2）	*	b	T1	T2
（3）	+	a	T2	T3
（4）	=	T3		x

1.2.4 代码优化

• 任务：对前面产生的中间代码进行加工变换，以期在最后阶段能产生更为高效的目标代码。

• 原则：等价变换

• 主要方面：公共子表达式的提取、合并已知量、删除无用语句、循环优化等。

例如

将下面的语句转换成中间代码：

for (k=1;k<=100;k++)

{m=i+10*k;

n=j+10*k;}

中间代码：

K=1;

10 If k<=100 then

{m=i+10*k;

n=j+10*k;

k++;

goto 10;}

序号	OP	ARG1	ARG2	RESULT
(1)	＝	1		K
(2)	j<	100	K	(9)
(3)	*	10	K	T1
(4)	+	i	T1	M
(5)	*	10	K	T2
(6)	+	j	T2	N
(7)	+	k	1	K
(8)	j			(2)
(9)

优化后

序号	OP	ARG1	ARG2	RESULT
（1）	＝	i		m
（2）	=	j		n
（3）	=	1		k
（4）	J<	100	k	(9)
（5）	+	m	10	m
（6）	+	n	10	n
（7）	+	k	1	k
（8）	j			(4)
（9）

1.2.5 目标代码生成

• 任务：把经过优化的中间代码转化成特定机器上的低级语言代码。

• 目标代码的形式：

– 绝对指令代码: 可立即执行的目标代码。

– 汇编指令代码：汇编语言程序，需要通过汇编程序汇编后才能运行。

– 可重定位指令代码：先将各目标模块连接起来， 确定变量、常数在主存中的位置，装入主存后才能成为可以运行的绝对指令代码。

1.2.6 表格管理

• 表格作用：用来记录源程序的各种信息以及编译过程中的各种状况。

• 与编译前三阶段有关的表格有：符号表、常数表、标号表、分程序入口表、中间代码表等。

1.2.7 出错处理

• 任务：如果源程序有错误，编译程序应设法发现错误， 并报告给用户。

• 完成：由专门的出错处理程序来完成

• 错误类型:

– 语法错误：在词法分析和语法分析阶段检测出来。

– 语义错误：一般在语义分析阶段检测。

1.2.8 遍

• 遍：指对源程序或源程序的中间结果从头到尾扫描一次，并做有关的加工处理，生成新的中间结果或目标代码的过程。

注：遍与阶段的含义毫无关系。

可分为一遍扫描和多遍扫描。

• 多遍扫描的优缺点：

– 优点：节省内存空间，提高目标代码质量，使编译的逻辑结构清晰。

– 缺点：编译时间较长。

注：在内存许可情况下，还是遍数尽可能少些为好。

思维导图：