编译原理 上海交通大学 张冬茉 Emails Zhang-dm acs sjtu. edu.cn 2004年2月
1 编译原理 上海交通大学 张冬茉 Email: zhang-dm@cs.sjtu.edu.cn 2004年2月
课程目的 编译原理是计算机专业设置的一门 重要的专业课程。虽然只有少数人 从事编译方面的工作,但是这门课 在理论、技术、方法上都对学生提 供了系统而有效的训练,有利于提 高软件人员的素质和能力
2 课程目的 编译原理是计算机专业设置的一门 重要的专业课程。虽然只有少数人 从事编译方面的工作，但是这门课 在理论、技术、方法上都对学生提 供了系统而有效的训练，有利于提 高软件人员的素质和能力
第一章引论 §1.1编译程序是一种特定的翻译程序 计算( computing):描述"计算"( computing)过程通常借 助于一种程序设计语言,这种"计算过程包含了从初始状态转 变为终止状态的一系列的操作。 翻译( translation)和翻译程序( translator):描述算法的语 言可有很多种,将一种语言写的程序转换成另一种语言写的程 序,这就是翻译( translation),实现这种功能的程序便是翻 译程序 translator),显然翻译前的程序与翻译后的程序两者应 等价。 3
3 第一章 引 论 §1.1 编译程序是一种特定的翻译程序 •计算（computing）：描述"计算"（computing）过程通常借 助于一种程序设计语言，这种"计算"过程包含了从初始状态转 变为终止状态的一系列的操作。 •翻译（translation）和翻译程序(translator) ：描述算法的语 言可有很多种，将一种语言写的程序转换成另一种语言写的程 序，这就是翻译（translation），实现这种功能的程序便是翻 译程序(translator)，显然翻译前的程序与翻译后的程序两者应 等价
源程序( source code)和目标程序( object code):翻译前的程 序为源语言程序,简称源程序( (source code),翻译后的程序 为目标语言程序,简称目标程序( object code) 汇编程序:将可直接执行的机器语言的指令系统符号化, 这便是汇编语言,当然汇编语言程序也必须转换成机器语 言程序才能执行,这种转换程序便是汇编程序( assembly program)。汇编程序也是一种翻译程序 编译程序( compiler):将高级语言程序翻译成低级语言程 序,这种翻译程序,便是编译程序( compiler)。显然编译程 序是翻译程序中的一类。 解释程序( interpreter):解释执行是将源程序中的语句按 动态顺序,逐句逐段翻译成可执行代码,一旦具备执行条 件(获得必要的初始数据等)立即将这一段代码执行得到部 分结果。完成这样功能的程序称为解释程序( interpreter) 4
4 •源程序(source code)和目标程序(object code)：翻译前的程 序为源语言程序，简称源程序(source code)，翻译后的程序 为目标语言程序，简称目标程序(object code)。 •汇编程序：将可直接执行的机器语言的指令系统符号化， 这便是汇编语言，当然汇编语言程序也必须转换成机器语 言程序才能执行，这种转换程序便是汇编程序(assembly program)。汇编程序也是一种翻译程序。 •编译程序(compiler)：将高级语言程序翻译成低级语言程 序，这种翻译程序，便是编译程序(compiler)。显然编译程 序是翻译程序中的一类。 •解释程序(interpreter)：解释执行是将源程序中的语句按 动态顺序，逐句逐段翻译成可执行代码，一旦具备执行条 件(获得必要的初始数据等)立即将这一段代码执行得到部 分结果。完成这样功能的程序称为解释程序(interpreter)
源程序S 译程序C 目标程序T (以高级语言写) (以机器语言 编译阶段 初始数据 计算结果 杨运行系统 运行阶段 图1.1程序的编译执行 目标程序T 汇编程序A 日标程序T (以汇编语言写) (以机器语言写) 图12汇编阶段 源程序S (以高级语言写) 解释程序 计算结果 初始数据 图1.3程序的解释执行
5 源程序 S （以高级语言写） ） 目标程序 T （以机器语言写） ） 计算机 编译程序 C 编译阶段 初始数据 计算结果 计算机 目标程序 T 运行阶段 运行系统 图1.1 程序的编译执行 目标程序T’ （以汇编语言写） ） 目标程序 T （以机器语言写） ） 计算机 汇编程序 A 图1.2 汇编阶段 源程序 S （以高级语言写） ） 计算机 计算结果 解释程序I 图1.3 程序的解释执行 初始数据
如果我们把源程序记为S,目标程序记为T,编译程序记 为C,那么可以将编译看成一个函数,种映射: T=C(S) 6
6 如果我们把源程序记为S，目标程序记为T，编译程序记 为C，那么可以将编译看成一个函数,一种映射: T=C(S)
812编译程序的结构 编译程序将源程序变换成目标程序,这是个复杂的过程,通 常分成五个阶段和两个附加部分: 、词法分析阶段 对组成源程序的字符串进行扫描和识别,识别出一个个具 独立意义的单词(或称符号),如基本字,o,be出的 等)、标 识符、常数、运算符、界符(括号,=,;等),将识别 单词用统一长度的标准形式(也可称为内部码)来表示,对 以后的变换来说,这种标准形式对区分单词和单词的属性 应是十分方便的。因此词法分析是将字符串变换成单词符 号流。 语法分析阶段 在词法分析输出的单词流基础上,根据源语言的语法规 则分析这种单词流是否正确地组成了各类语法单位,如 短语、子句、程序段和程序等。例如2*3.1416RR是表 达式,单词符号:=后应跟着一个表达式作为赋值语句的 右部等。 7
7 §1.2 编译程序的结构 编译程序将源程序变换成目标程序，这是个复杂的过程，通 常分成五个阶段和两个附加部分： 一、词法分析阶段 对组成源程序的字符串进行扫描和识别，识别出一个个具 独立意义的单词(或称符号)，如基本字(if, for, begin等)、标 识符、常数、运算符、界符(括号，=，；等)，将识别出的 单词用统一长度的标准形式(也可称为内部码)来表示，对 以后的变换来说，这种标准形式对区分单词和单词的属性 应是十分方便的。因此词法分析是将字符串变换成单词符 号流。 二、语法分析阶段 在词法分析输出的单词流基础上，根据源语言的语法规 则分析这种单词流是否正确地组成了各类语法单位，如 短语、子句、程序段和程序等。例如2*3.1416*R*R是表 达式，单词符号:=后应跟着一个表达式作为赋值语句的 右部等
语义分析、中间代码生成阶段 经过语法分析的单词流若在语法结构上是正确的,就可 以在这个基础上做实质性的翻译工作,虽然可以直接翻 译成可执行代码(机器语言或汇编语言程序),但通常是将 单词流翻译成在语义上等价的中间语言程序。中间语言 是介于高级语言和低级语言之间、但并不面向具体机器 语言结构又十分接近低级语言的一种中间代码形式。中 间语言相对于低级语言而言,既有一定程度的抽象,又 有一定程度的对应。中间语言程序到目标语言的转换是 容易的,因此语义上的等价变换主要在语义分析阶段进 行。其任务是根据语言的语义规则,将语法单位逐一翻 译成中间语言代码,这通常称为是语法制导翻译。 8
8 三、语义分析、中间代码生成阶段 经过语法分析的单词流若在语法结构上是正确的，就可 以在这个基础上做实质性的翻译工作，虽然可以直接翻 译成可执行代码(机器语言或汇编语言程序)，但通常是将 单词流翻译成在语义上等价的中间语言程序。中间语言 是介于高级语言和低级语言之间、但并不面向具体机器、 语言结构又十分接近低级语言的一种中间代码形式。中 间语言相对于低级语言而言，既有一定程度的抽象，又 有一定程度的对应。中间语言程序到目标语言的转换是 容易的，因此语义上的等价变换主要在语义分析阶段进 行。其任务是根据语言的语义规则，将语法单位逐一翻 译成中间语言代码，这通常称为是语法制导翻译
四、优化阶段 前一阶段产生的中间代码是以语法单位这样的局部区间 为单位而产生的,不能保证效率是高的,有必要进行等 价变换,使程序占用空间少,运行时间短。常用的优化 措施有删除冗余运算,删除无用赋值,合并已知量,循 环优化等,有些优化措施效果很明显,例如循环中参于 运算的运算量,如其值并不随着循环而发生变化,这类 运算称为循环不变运算,它完全不必每次循环都计算 次,将它们提到进入循环前计算一次即可
9 四、优化阶段 前一阶段产生的中间代码是以语法单位这样的局部区间 为单位而产生的，不能保证效率是高的，有必要进行等 价变换，使程序占用空间少，运行时间短。常用的优化 措施有删除冗余运算，删除无用赋值，合并已知量，循 环优化等，有些优化措施效果很明显，例如循环中参于 运算的运算量，如其值并不随着循环而发生变化，这类 运算称为循环不变运算，它完全不必每次循环都计算一 次，将它们提到进入循环前计算一次即可
五、目标代码生成阶段 将中间代码转换成机器语言程序或汇编语言程序,最后完 成了翻译,这阶段的工作因为目标语言的关系而十分依赖 于硬件系统,如何充分利用寄存器、合理选择指令、生成 尽可能短而有效的目标代码,都与目标机的结构有关。 生成的目标代码如果是汇编语言程序,则需经由汇编程序 汇编后才能执行。生成的目标代码如果是绝对指令代码, 则已可直接投入运行。如果是可重定位的指令代码,那么 目标代码只是一个代码模块,必须由连接装配程序,将输 入/输出模块,标准函数等系统模块与目标代码模块连接 在一起,确定数据对象和各程序点的位置(即代真)才可能 形成一个绝对指令代码程序供运行。 10
10 五、目标代码生成阶段 将中间代码转换成机器语言程序或汇编语言程序，最后完 成了翻译，这阶段的工作因为目标语言的关系而十分依赖 于硬件系统，如何充分利用寄存器、合理选择指令、生成 尽可能短而有效的目标代码，都与目标机的结构有关。 生成的目标代码如果是汇编语言程序，则需经由汇编程序 汇编后才能执行。生成的目标代码如果是绝对指令代码， 则已可直接投入运行。如果是可重定位的指令代码，那么 目标代码只是一个代码模块，必须由连接装配程序，将输 入/输出模块，标准函数等系统模块与目标代码模块连接 在一起，确定数据对象和各程序点的位置(即代真)才可能 形成一个绝对指令代码程序供运行