1
编译原理上海交通大学张冬茉
Email:
zhang-dm@cs.sjtu.edu.cn
2004年 2月
2
课程目的编译原理是计算机专业设置的一门重要的专业课程。虽然只有少数人从事编译方面的工作，但是这门课在理论、技术、方法上都对学生提供了系统而有效的训练，有利于提高软件人员的素质和能力。
3
第一章 引 论
§ 1.1 编译程序是一种特定的翻译程序
计算 （ computing）,描述 "计算 "（ computing） 过程通常借助于一种程序设计语言,这种 "计算 "过程包含了从初始状态转变为终止状态的一系列的操作 。
翻译 （ translation） 和翻译程序 (translator),描述算法的语言可有很多种,将一种语言写的程序转换成另一种语言写的程序,这就是翻译 （ translation）,实现这种功能的程序便是翻译程序 (translator),显然翻译前的程序与翻译后的程序两者应等价 。
4
源程序 (source code)和目标程序 (object code)：翻译前的程序为源语言程序,简称源程序 (source code),翻译后的程序为目标语言程序,简称目标程序 (object code)。
汇编程序：将可直接执行的机器语言的指令系统符号化,
这便是汇编语言,当然汇编语言程序也必须转换成机器语言程序才能执行,这种转换程序便是汇编程序 (assembly
program)。 汇编程序也是一种翻译程序 。
编译程序 (compiler)：将高级语言程序翻译成低级语言程序,这种翻译程序,便是编译程序 (compiler)。 显然编译程序是翻译程序中的一类 。
解释程序 (interpreter)：解释执行是将源程序中的语句按动态顺序,逐句逐段翻译成可执行代码,一旦具备执行条件 (获得必要的初始数据等 )立即将这一段代码执行得到部分结果 。 完成这样功能的程序称为解释程序 (interpreter)
5
源程序 S
（以高级语言写）
）
目标程序 T
（以机器语言写）
）计算机编译程序 C
编译阶段初始数据 计算结果计算机目标程序 T
运行阶段运行系统图 1.1 程序的编译执行目标程序 T’
（以汇编语言写）
）
目标程序 T
（以机器语言写）
）计算机汇编程序 A
图 1.2 汇编阶段源程序 S
（以高级语言写）
） 计算结果计算机解释程序 I
图 1.3 程序的解释执行初始数据
6
如果我们把源程序记为 S,目标程序记为 T,编译程序记为 C,那么可以将编译看成一个函数,一种映射,
T=C(S)
7
§ 1.2 编译程序的结构编译程序将源程序变换成目标程序,这是个复杂的过程,通常分成五个阶段和两个附加部分：
一,词法分析阶段对组成源程序的字符串进行扫描和识别,识别出一个个具独立意义的单词 (或称符号 ),如基本字 (if,for,begin等 ),标识符,常数,运算符,界符 (括号,=,；等 ),将识别出的单词用统一长度的标准形式 (也可称为内部码 )来表示,对以后的变换来说,这种标准形式对区分单词和单词的属性应是十分方便的 。 因此词法分析是将字符串变换成单词符号流 。
二,语法分析阶段在词法分析输出的单词流基础上,根据源语言的语法规则分析这种单词流是否正确地组成了各类语法单位,如短语,子句,程序段和程序等 。 例如 2*3.1416*R*R是表达式,单词符号,=后应跟着一个表达式作为赋值语句的右部等 。
8
三,语义分析,中间代码生成阶段经过语法分析的单词流若在语法结构上是正确的,就可以在这个基础上做实质性的翻译工作,虽然可以直接翻译成可执行代码 (机器语言或汇编语言程序 ),但通常是将单词流翻译成在语义上等价的中间语言程序 。 中间语言是介于高级语言和低级语言之间,但并不面向具体机器,
语言结构又十分接近低级语言的一种中间代码形式 。 中间语言相对于低级语言而言,既有一定程度的抽象,又有一定程度的对应 。 中间语言程序到目标语言的转换是容易的,因此语义上的等价变换主要在语义分析阶段进行 。 其任务是根据语言的语义规则,将语法单位逐一翻译成中间语言代码,这通常称为是语法制导翻译 。
9
四,优化阶段前一阶段产生的中间代码是以语法单位这样的局部区间为单位而产生的,不能保证效率是高的,有必要进行等价变换,使程序占用空间少,运行时间短 。 常用的优化措施有删除冗余运算,删除无用赋值,合并已知量,循环优化等,有些优化措施效果很明显,例如循环中参于运算的运算量,如其值并不随着循环而发生变化,这类运算称为循环不变运算,它完全不必每次循环都计算一次,将它们提到进入循环前计算一次即可 。
10
五,目标代码生成阶段将中间代码转换成机器语言程序或汇编语言程序,最后完成了翻译,这阶段的工作因为目标语言的关系而十分依赖于硬件系统,如何充分利用寄存器,合理选择指令,生成尽可能短而有效的目标代码,都与目标机的结构有关 。
生成的目标代码如果是汇编语言程序,则需经由汇编程序汇编后才能执行 。 生成的目标代码如果是绝对指令代码,
则已可直接投入运行 。 如果是可重定位的指令代码,那么目标代码只是一个代码模块,必须由连接装配程序,将输入 /输出模块,标准函数等系统模块与目标代码模块连接在一起,确定数据对象和各程序点的位置 (即代真 )才可能形成一个绝对指令代码程序供运行 。
11
以上五个阶段反映了编译程序的动态特征,但编译的实现还有赖于符号表管理和出错管理 。
六,符号表管理源程序中的有关数据对象的信息和程序信息是编译各阶段要经常使用的,因此编译程序中还应包括一个符号表管理程序,它涉及到符号表的构造,查询和更新等各种操作,
提供用户命名的标识符的各种属性,存储位置,类型,作用域等信息,对这些信息的操作,是频繁的,占了编译时间的很大一个比例,因此符号表的结构,符号表上各种操作的算法必须精心设计 。
12
七,出错管理程序编译的各个阶段都可能遇到错误。出错管理程序应在发现错误后，将错误的有关信息如错误类型、错误地点向用户报告。为了尽可能多地发现错误，在发现了错误后还应继续编译下去，因此要设法将错误造成的影响限制在尽可能小的范围中，发现错误后能自动校正错误当然最好，只是在大部分情况下，校正的代价太大，而且效果也未必尽如人意。
13
符号表管理器词法分析器语法分析器语义分析、中间代码生成器优化目标代码生成器出错管理器单词流语法单位中间代码序列中间代码序列目标程序源程序字符串图 1.4 编译程序总框图
14
编译阶段的前端和后端编译的前三个阶段 (词法分析,语法分析,语义分析和中间代码生成 )称为编译的前端 。 它其实还可分成分析
(词法分析,语法分析,语义分析 )和综合 (代码生成 )两个过程 。 而目标代码生成则是编译的后端 。 中间代码的优化可归入前端 。 很明显编译后端是面向目标语言的,
而编译前端则不是,它几乎独立目标语言 。
遍在编译过程中,从头至尾地扫描一个输入文件,经过程序变换形成一个输出文件,这个过程称为编译的一遍 。
编译过程一般可用两遍或三遍完成 。
15
§ 1.3 编译程序的生成一个编译系统的构造并非易事,现在有各个层次的生成工具：
lex、
yacc、
make
要构造一个完全独立的全新的编译器可能性很小,大部分可在现有编译器的基础上扩展：
自展的方式,
移植的方式 。
16
自展一个编译程序一般涉及三种语言：
语言 I,称它为编译的实现语言
源语言 S，
目标语言 T
对一个相当规模的语言 L,想用目标语言在目标机 A上构造一个编译程序是十分困难的 。 为此,我们首先可以选择 L的一个子集 S,子集的规模只要达到具有足够的描述能力即可 。 相对而言于 L而言,S的编译程序就容易写得多,不妨认为它可以用手工完成 。
17
第二步，我们可以用 S语言来写一个 L? A的编译程序，相对于 A语言来说，用 S语言写这样的编译程序也会容易得多。然后将这个 S语言的程序作为 S? A的编译程序的输入。
其输出当然是 A语言的程序，并且由于保证这种变换的等价性，因此输出程序将保持输入程序的功能，即将 L语言程序等价变换成 A语言程序，故输出程序是一个 A语言书写的程序，其功能为将 L语言程序等价变换成 A语言的程序，即 L? A的编译程序，这便是我们所要求的
18
移植已有 L语言在 A机器上的编译器,想借助于它,得到 L
语言在 B机器上的编译器,这便是移植 。 也即将 A机器上的 L语言的编译移植到 B机器上 。
做法是：首先用 L语言写一个 L? B的编译程序,将这个 L语言程序作为 L语言在 A机器上的编译器的输入,
输出为用 A语言写的将 L语言翻译成 B语言上的编译器这种在 A机器上生成 B机器的目标代码的编译称为交叉编译 。
第二步将用 L语言写一个 L? B的编译程序作为交叉编译的输入,其输出即为所求 。
编译原理上海交通大学张冬茉
Email:
zhang-dm@cs.sjtu.edu.cn
2004年 2月
2
课程目的编译原理是计算机专业设置的一门重要的专业课程。虽然只有少数人从事编译方面的工作，但是这门课在理论、技术、方法上都对学生提供了系统而有效的训练，有利于提高软件人员的素质和能力。
3
第一章 引 论
§ 1.1 编译程序是一种特定的翻译程序
计算 （ computing）,描述 "计算 "（ computing） 过程通常借助于一种程序设计语言,这种 "计算 "过程包含了从初始状态转变为终止状态的一系列的操作 。
翻译 （ translation） 和翻译程序 (translator),描述算法的语言可有很多种,将一种语言写的程序转换成另一种语言写的程序,这就是翻译 （ translation）,实现这种功能的程序便是翻译程序 (translator),显然翻译前的程序与翻译后的程序两者应等价 。
4
源程序 (source code)和目标程序 (object code)：翻译前的程序为源语言程序,简称源程序 (source code),翻译后的程序为目标语言程序,简称目标程序 (object code)。
汇编程序：将可直接执行的机器语言的指令系统符号化,
这便是汇编语言,当然汇编语言程序也必须转换成机器语言程序才能执行,这种转换程序便是汇编程序 (assembly
program)。 汇编程序也是一种翻译程序 。
编译程序 (compiler)：将高级语言程序翻译成低级语言程序,这种翻译程序,便是编译程序 (compiler)。 显然编译程序是翻译程序中的一类 。
解释程序 (interpreter)：解释执行是将源程序中的语句按动态顺序,逐句逐段翻译成可执行代码,一旦具备执行条件 (获得必要的初始数据等 )立即将这一段代码执行得到部分结果 。 完成这样功能的程序称为解释程序 (interpreter)
5
源程序 S
（以高级语言写）
）
目标程序 T
（以机器语言写）
）计算机编译程序 C
编译阶段初始数据 计算结果计算机目标程序 T
运行阶段运行系统图 1.1 程序的编译执行目标程序 T’
（以汇编语言写）
）
目标程序 T
（以机器语言写）
）计算机汇编程序 A
图 1.2 汇编阶段源程序 S
（以高级语言写）
） 计算结果计算机解释程序 I
图 1.3 程序的解释执行初始数据
6
如果我们把源程序记为 S,目标程序记为 T,编译程序记为 C,那么可以将编译看成一个函数,一种映射,
T=C(S)
7
§ 1.2 编译程序的结构编译程序将源程序变换成目标程序,这是个复杂的过程,通常分成五个阶段和两个附加部分：
一,词法分析阶段对组成源程序的字符串进行扫描和识别,识别出一个个具独立意义的单词 (或称符号 ),如基本字 (if,for,begin等 ),标识符,常数,运算符,界符 (括号,=,；等 ),将识别出的单词用统一长度的标准形式 (也可称为内部码 )来表示,对以后的变换来说,这种标准形式对区分单词和单词的属性应是十分方便的 。 因此词法分析是将字符串变换成单词符号流 。
二,语法分析阶段在词法分析输出的单词流基础上,根据源语言的语法规则分析这种单词流是否正确地组成了各类语法单位,如短语,子句,程序段和程序等 。 例如 2*3.1416*R*R是表达式,单词符号,=后应跟着一个表达式作为赋值语句的右部等 。
8
三,语义分析,中间代码生成阶段经过语法分析的单词流若在语法结构上是正确的,就可以在这个基础上做实质性的翻译工作,虽然可以直接翻译成可执行代码 (机器语言或汇编语言程序 ),但通常是将单词流翻译成在语义上等价的中间语言程序 。 中间语言是介于高级语言和低级语言之间,但并不面向具体机器,
语言结构又十分接近低级语言的一种中间代码形式 。 中间语言相对于低级语言而言,既有一定程度的抽象,又有一定程度的对应 。 中间语言程序到目标语言的转换是容易的,因此语义上的等价变换主要在语义分析阶段进行 。 其任务是根据语言的语义规则,将语法单位逐一翻译成中间语言代码,这通常称为是语法制导翻译 。
9
四,优化阶段前一阶段产生的中间代码是以语法单位这样的局部区间为单位而产生的,不能保证效率是高的,有必要进行等价变换,使程序占用空间少,运行时间短 。 常用的优化措施有删除冗余运算,删除无用赋值,合并已知量,循环优化等,有些优化措施效果很明显,例如循环中参于运算的运算量,如其值并不随着循环而发生变化,这类运算称为循环不变运算,它完全不必每次循环都计算一次,将它们提到进入循环前计算一次即可 。
10
五,目标代码生成阶段将中间代码转换成机器语言程序或汇编语言程序,最后完成了翻译,这阶段的工作因为目标语言的关系而十分依赖于硬件系统,如何充分利用寄存器,合理选择指令,生成尽可能短而有效的目标代码,都与目标机的结构有关 。
生成的目标代码如果是汇编语言程序,则需经由汇编程序汇编后才能执行 。 生成的目标代码如果是绝对指令代码,
则已可直接投入运行 。 如果是可重定位的指令代码,那么目标代码只是一个代码模块,必须由连接装配程序,将输入 /输出模块,标准函数等系统模块与目标代码模块连接在一起,确定数据对象和各程序点的位置 (即代真 )才可能形成一个绝对指令代码程序供运行 。
11
以上五个阶段反映了编译程序的动态特征,但编译的实现还有赖于符号表管理和出错管理 。
六,符号表管理源程序中的有关数据对象的信息和程序信息是编译各阶段要经常使用的,因此编译程序中还应包括一个符号表管理程序,它涉及到符号表的构造,查询和更新等各种操作,
提供用户命名的标识符的各种属性,存储位置,类型,作用域等信息,对这些信息的操作,是频繁的,占了编译时间的很大一个比例,因此符号表的结构,符号表上各种操作的算法必须精心设计 。
12
七,出错管理程序编译的各个阶段都可能遇到错误。出错管理程序应在发现错误后，将错误的有关信息如错误类型、错误地点向用户报告。为了尽可能多地发现错误，在发现了错误后还应继续编译下去，因此要设法将错误造成的影响限制在尽可能小的范围中，发现错误后能自动校正错误当然最好，只是在大部分情况下，校正的代价太大，而且效果也未必尽如人意。
13
符号表管理器词法分析器语法分析器语义分析、中间代码生成器优化目标代码生成器出错管理器单词流语法单位中间代码序列中间代码序列目标程序源程序字符串图 1.4 编译程序总框图
14
编译阶段的前端和后端编译的前三个阶段 (词法分析,语法分析,语义分析和中间代码生成 )称为编译的前端 。 它其实还可分成分析
(词法分析,语法分析,语义分析 )和综合 (代码生成 )两个过程 。 而目标代码生成则是编译的后端 。 中间代码的优化可归入前端 。 很明显编译后端是面向目标语言的,
而编译前端则不是,它几乎独立目标语言 。
遍在编译过程中,从头至尾地扫描一个输入文件,经过程序变换形成一个输出文件,这个过程称为编译的一遍 。
编译过程一般可用两遍或三遍完成 。
15
§ 1.3 编译程序的生成一个编译系统的构造并非易事,现在有各个层次的生成工具：
lex、
yacc、
make
要构造一个完全独立的全新的编译器可能性很小,大部分可在现有编译器的基础上扩展：
自展的方式,
移植的方式 。
16
自展一个编译程序一般涉及三种语言：
语言 I,称它为编译的实现语言
源语言 S，
目标语言 T
对一个相当规模的语言 L,想用目标语言在目标机 A上构造一个编译程序是十分困难的 。 为此,我们首先可以选择 L的一个子集 S,子集的规模只要达到具有足够的描述能力即可 。 相对而言于 L而言,S的编译程序就容易写得多,不妨认为它可以用手工完成 。
17
第二步，我们可以用 S语言来写一个 L? A的编译程序，相对于 A语言来说，用 S语言写这样的编译程序也会容易得多。然后将这个 S语言的程序作为 S? A的编译程序的输入。
其输出当然是 A语言的程序，并且由于保证这种变换的等价性，因此输出程序将保持输入程序的功能，即将 L语言程序等价变换成 A语言程序，故输出程序是一个 A语言书写的程序，其功能为将 L语言程序等价变换成 A语言的程序，即 L? A的编译程序，这便是我们所要求的
18
移植已有 L语言在 A机器上的编译器,想借助于它,得到 L
语言在 B机器上的编译器,这便是移植 。 也即将 A机器上的 L语言的编译移植到 B机器上 。
做法是：首先用 L语言写一个 L? B的编译程序,将这个 L语言程序作为 L语言在 A机器上的编译器的输入,
输出为用 A语言写的将 L语言翻译成 B语言上的编译器这种在 A机器上生成 B机器的目标代码的编译称为交叉编译 。
第二步将用 L语言写一个 L? B的编译程序作为交叉编译的输入,其输出即为所求 。
