编译原理讲义(54).doc

编译原理
讲义

孙清

西安财经学院信息学院计算机系

2007年1月

教材：
《程序设计语言编译原理》（第3版）
陈火旺编国防工业出版社2000年1月
参考教材：
《编译原理》蒋立源康慕宁西北工业大学出版社2004年1月
《编译原理》吕映芝张素琴蒋维杜清华大学出版社2002年5月
CompilerConstructionPrinciplesandPractice,KennethC.Louden,ThomsonPress2003.2
学时：54学时分配：周3学时
章节 学时
第一章：引论 3
第二章高级语言及其语法描述 3
第三章词法分析 6
第四章语法分析----自上而下分析 6
第五章语法分析----自下而上分析 6
第六章属性文法和语法制导翻译 6
第七章语义分析和中间代码产生 6
第八章符号表3
第九章运行时存储空间组织3
第十章优化 3
第十一章目标代码生成3
第十二章并行编译基础3
总复习 3

编译原理课程在计算机科学技术中的地位
程序设计语言
离散数学
数据结构
编译原理
操作系统
系统软件
应用软件
软件工程
信息系统
电子商务
算法分析
计算基础

第一章：引论
什么是编译程序
编译过程概述
编译程序的结构
编译程序的生成
1．1什么叫编译程序
程序翻译的两种方式：
编译程序：把高级语言源程序转换成低级语言目标语言程序，并且后者与前者逻辑上是等价的，这样的程序即为编译程序。
解释程序：以源程序作为输入，但不产生目标程序，边解释边执行源程序的程序。

编译程序的分类：
诊断编译程序：专用于帮助程序开发和调试的编译程序。
优化编译程序：着重于提高目标代码效率的编译程序。
交叉编译程序：产生不同于其宿主机的机器代码的编译程序。
可变目标编译程序：不需要重写编译程序中与机器无关的部分就能改变目标机的编译程序。
1．2编译过程概述
以中英文翻译为例，翻译所需步骤：
识别出句子中的一个个单词 …. 词法分析
分析句子的语法结构 …. 语法分析
根据句子的含义进行初步翻译 …. 语义分析与中间代码产生
对译文进行修饰 …. 优化
写出最后的译文 …. 目标代码生成

词法分析
输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词。
例1.1
for(i=0;i<100;i++)a[i]=0x800000;
描述词法规则的有效工具：正规式、有限自动机
语法分析
在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位(语句、程序段、程序)。
例1.2z=x+0.618*y；
描述语法规则的有效工具：上下文无关文法
三、语义分析与中间代码产生
对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。
中间代码独立于具体的硬件，常采用四元式的形式：
算符左操作数右操作数结果例1.3
z=(x+0.418)*y/w；
序号算符左操作数右操作数结果1＋x0.418T12*T1yT23/T2wz描述语义规则的有效工具：属性文法
四、优化
对中间代码进行加工，以期产生出更高效的目标代码。如，公共表达式的提取、循环优化、删除无用代码等。
例1.4
for(k=0;k<100;k++)
{
m=i+10*k;
n=j+10*k;
}
把原表达式中的先乘后加，优化成先赋初值再只做加法，从而减少了200次乘运算。（见教材P4中的表）
五、目标代码生成
把优化后的中间代码变换成特定机器上的低级语言代码。
目标代码的形式可以是：绝对指令代码、可重定位指令代码（汇编指令代码）
1．3编译程序的结构

遍：是对源程序或源程序的中间结果从头到尾扫描一次，并做有关的加工处理，生成新的中间结果或目标程序。
前端：与源程序有关但与目标程序无关的编译程序部分。
后端：编译程序中与目标程序有关的部分，后端仅依赖于中间代码。
1．4编译程序与程序设计环境
集成化程序设计环境（IDE）：由程序设计工具和编译程序组成。
1．5编译程序的生成
编译程序的生成方式有如下六种：
(1)直接用机器语言编写编译程序、(2)用汇编语言编写编译程序、(3)用高级语言编写编译程序、(4)利用编译工具（LEX、YACC）、(5)自编译、(6)移植产生编译程序。

编译程序的T形图：
源语言
目标语言
实现语言

(3)用高级语言实现编译程序：
利用A机器上已有的用A代码编写的L1语言的编译程序，把用L1语言编写的L2语言的编译程序进行编译，得到A机器代码实现的L2语言的编译程序。表示为：
L2语言
A代码
L1语言
L1语言
A代码
A代码