编译原理张晶版 第一章 概论

•高级语言
-- Fortran、Pascal、C 语言等
特点：不依赖具体机器，移植性好、对用户要求低、 易使用、易维护等。
用高级语言编制的程序，计算机不能立即执行， 必须通过一个“翻译程序”加工，转化为与其等价的 机器语言程序，机器才能执行。
这种翻译程序，称之为“编译程序”。
第一章 概论（21）
Compiler
第一章 概论（19）
1.1什么是编译程序
程序设计语言的发展
汇编语言
C7 06 0000 0002 MOV x, 2
面向用户 的语言
x =2
面向问题 的语言
低级语言
高级语言
第一章 概论（20）
•低级语言（Low level Language)
字位码、机器语言、汇编语言
特点：与特定的机器有关，功效高，但使用复杂、 繁琐、费时、易出错
•源程序
用汇编语言或高级语言编写的程序称为源程序。
• 目标程序
用目标语言所表示的程序。 目标语言：可以是介于源语言和机器语言之间的 “中间语言”，可以是某种机器的机器语言,也可以是 某机器的汇编语言。
• 翻译程序
将源程序转换为目标程序的程序称为翻译程序。 它是指各种语言的翻译器，包括汇编程序和编译程序， 是汇编程序、编译程序以及各种变换程序的总称
第一章 概论（24）
Compiler
源程序的编译和运行 •编译或汇编阶段
源程序
•运行阶段
编译程序 或
汇编程序
输入数据
目标程序 +
运行子程序
目标程序 输出数据
第一章 概论（25）
Compiler
程序设计语言的转换 • 翻译
—是指能把某种语言的源程序，在不改变语义的条件下，转换 成另一种语言程序—目标语言程序
x=V+T x=a+T x=a+T*F x=a+F*F x=a+V*F x=a+b*F
x=a+b*C x=a+b*50 最左推导 最右归约
赋值语句的语法规则： v A::=V=E v E::=T|E+T v T::=F|T*F v F::=V|(E)|C v V::=标识符 v C::=常数
第一章 概论（42）
第一章 概论（40）
最右推导
举例说明 Void jisuan( )
{int y,c,d; float x,a,b; x=a+b*50; y=c+)d*(x+b; }
赋值语句的语法规则： v A::=V=E v E::=T|E+T v T::=F|T*F v F::=V|(E)|C v V::=标识符 v C::=常数
第一章 概论（29）
Compiler
1.2 编译程序的基本结构
一段英文翻译成中文
需经下列步骤:
编
识别出句子中的单词
译
分析句子的语法结构
程
序
根据句子的含义进行 初步分析
对译文进行修饰
的 各 个 阶
段
写出最后的译文
编译程序
词法分析 语法分析 语义分析及中间代码 生成 代码优化 目标代码生成
第一章 概论（31）
第一章 概论（33）
一、词法分析
举例说明 Void jisuan( )
{int y,c,d; float x,a,b; x=a+b*50; y=c+)d*(x+b; }
Compiler
识别右边程序中的单词
•基本字：Void,int,float •标识符：a,b,c,d,x,y,jisuan •常数：50 •运算符：*,+,=,•界限符：{ } ; , ( )
2003
第一章 概论（6）
课程简介
要求:
– 提前预习,认真听课,理解基本概念,基本原理与基本 算法
– 在看书时或理解例题及习题时,一定要划出相应的细 节变化过程,通过画图来加深理解
– 作业要求独立、按时完成 – 辅导地点：静远楼 435 – 上机地点：耘慧楼112 – 学期总评 = 考试成绩占80%，平时占20%+实验成
大家好
Compiler
编译原理
第一章 概论（1）
源程序
开课目的
目标程序
可执行 程序
第一章 概论（4）
[教材和参考书]
课程简介
– 张晶，编译原理 ，哈尔滨工程大学出版社
– 吕映芝等，编译原理，清华大学出版社 – 肖军模，程序设计语言编译方法，大连理工大学出版社 – 陈火旺等,程序设计语言编译原理,国防工业出版社,2000 – 陈意云、张昱，编译原理和技术，高等教育出版社，
编译时： 2.0 + 0.8 → T1
（1) * T1 C1 T2
（2) := X1 T2
优化前的四元式：
(1) +
2.0 0.8 T1
(2) * T1 C1 T2
(3) := X1 T2
第一章 概论（52）
四、代码优化
n 试图改进中间代码，以产生执行速度较快占用内存 空间少的机器代码
第一章 概论（50）
★四元式（三地址指令）
X1:= ( 2.0 + 0.8 ) * C1
运算符 左运算对象
右运算对象 结果
(1) +
2.0
0.8
T1
(2) *
T1
C1
T2
(3) :=
X1
T2
其中T1和T2为编译程序引入的工作单元
四元式的语义为： 2.0 + 0.8 → T1
T1 * C1 → T2
第一章 概论（34）
1.词法分析
Compiler
词法分析依照词法规则，识别出正确的单词，转换成统一规 格备用
转换 —对基本字，运算符，界符的转换 —标识符的转换 —常数的转换 —转换完成后的格式（类号，内码）
描述词法规则的有效工具是正规式和有限自动机
第一章 概论（35）
二、语法分析
Compiler
• 由语法分析识别出赋值语句，语义分析首先要分 析语义上的正确性，例如要检查表达式中和赋值号 两边的类型是否一致。
• 根据赋值语句的语义，生成中间代码。 即用一种语言形式来代替另一种语言形式， 这是翻译的关键步骤。 （翻译的实质：语义的等价性）
第一章 概论（48）
position = initial + rate * 60
三、语义分析、生成中间代码
=
id1
+
id2
*
id3
60
语义分析器
符号表
1 position . . .
2 initial . . .
3 rate
...
=
id1
+
id2
*
id3 inttoreal
60
第一章 概论（49）
三、语义分析、生成中间代码
总结一下语义分析主要的任务：
完成静态语义审查和处理 上下文相关性审查 类型匹配审查 类型转换
• 编译 —专指由高级语言转换为低级语言 • 解释 —接受某高级语言的一个语句输入，进行解释并控制计算机执
行，马上得到这句的执行结果，然后再接受下一句
第一章 概论（26）
Compiler
•解释程序（Interpreter） 对源程序进行解释执行的程序。
•工作过程
源程序
输Hale Waihona Puke 数据解释程序输出数据
• 特点、与编译程序比较
• 汇编程序
高级语言 编译程序
目标程序
若源程序用汇编语言书写，经过翻译程序得到用机器语言
表示的程序，这时的翻译程序就称之为汇编程序，这种翻译过
程称为“汇编”(Assemble）
• 编译程序
若源程序是用高级语言书写，经加工后得到目标程序， 这种翻译过程称“编译”（Compile)
汇编程序与编译程序都是翻译程序，主要区别是加工对象的 不同。由于汇编语言格式简单，常与机器语言之间有一一对 应的关系，汇编程序所要做的翻译工作比编译程序简单得多。
•单词：是语言的基本语法单位，一般语言有五大 类单词
<对1于>语如言下定的义字的符关串键,词字法或分保析留程字序（将如分B析EG和IN识、别E出N9D个、单IF词）： <2>标识符 <3>常数X1 := ( 2.0 + 0.8 ) * C1 <4>分界符1 （2如3;、4（、5 ）6…7…8） 9 <5> 运算符 （如+、-、*、/……）
T2 → X1 这样所生成的四元式与原来的赋值语句在语言的 形式上不同，但语义上等价。
第一章 概论（51）
四、代码优化
Compiler
任务：目的是为了得到高质量的目标程序。
例如：前面的四元式中第一个四元式是计算常量表达式值， 该值在编译时就可以算出并存放在工作单元中，不必生成目 标指令来计算，这样四元式可优化为：
• 中间代码：一种介于源语言和目标语言之间的中间语言 形式 • 生成中间代码的目的： <1> 便于做优化处理； <2> 便于编译程序的移植。
• 中间代码的形式：编译程序设计者可以自己设计，常用的有 四元式、三元式、逆波兰表示等。
第一章 概论（47）
例： X1:= ( 2.0 + 0.8 ) * C1
语法分析过程也可以用一棵倒着的树来表示
这棵树叫语法树，比如上述程序段中的单词序列： id1=id2+id3*60经语法分析得知其是PASCAL语言的 “赋值语句”，表示成如下所示形式。
第一章 概论（44）
二、语法分析
Compiler
＝
id1 +