第1章 编译原理

1、编译原理 教师：王文晶为什么要学习编译原理l 必修主干课程：操作系统和编译系统构成程序设计者与计算机之间的基本界面。l 通过学习该课程，掌握编译的基本理论、常用的编译技术，了解编译过程及编译系统结构和机理。能运用所学技术解决实际问题，能独立编写一个小型编译系统。l 此外，通过学习编译原理可以更好地理解程序语言的内部机制,从而更好地理解和运用程序设计语言。能运用编译程序构造的原理和技术完成相关软件工具的设计和开发工作。学习方法学习方法 平时（平时（30%30%） 一本教材，一本教材，认真听课认真听课：以讲义为主，板书为：以讲义为主，板书为辅辅-做适当的笔记做适当的笔记考勤（考勤（10分）分）+作

2、业（实验报告、随堂作业作业（实验报告、随堂作业 20分）分）课程特点：理论性强，算法复杂课程特点：理论性强，算法复杂补充：公共邮箱补充：公共邮箱 密码密码byylwwjbyylwwj 编译理论编译理论自动机和形式语言离散数学数据结构操作系统素材素材基础基础控制对象控制对象编译原理与其它课程关系 要求先学习以下课程要求先学习以下课程1.程序设计语言2.算法与数据结构：栈分配、堆分配、静态分配等各种存储分配方式。线性表、二叉查找树、哈希表等多种数据结构。 3.离散数学：集合论与数理逻辑是进一步学习形式语言与自动机理论的数学基础。 l 最好学习过或同时学习以下课程 1.软件工程：掌握大型程序设计以及

3、工程化的软件生产方法。 2.形式语言与自动机：相当于本课程中词法分析与语法分析的理论基础。 目目 录录第一章第一章 引言引言 学习目标学习目标l 了解和掌握高级程序设计语言与编译程序的关系了解和掌握高级程序设计语言与编译程序的关系l 了解和掌握编译程序的了解和掌握编译程序的功能功能 l 了解和掌握编译程序的体系结构了解和掌握编译程序的体系结构 l 了解和掌握编译程序的了解和掌握编译程序的工作过程工作过程 l1.1 1.1 编译程序、汇编程序、解释程序编译程序、汇编程序、解释程序l1.2 1.2 编译过程概述编译过程概述l1.3 1.3 编译程序的开发编译程序的开发目目 录录l 低级语言低级语言

4、（Low level Language)字位码、机器语言、汇编语言字位码、机器语言、汇编语言特点：与特定的机器有关，功效高，但使用复杂、繁特点：与特定的机器有关，功效高，但使用复杂、繁琐、费时、易出错琐、费时、易出错l 高级语言高级语言 - Fortran、Pascal、C 语言等语言等特点：不依赖具体机器，移植性好、对用户要求低、易特点：不依赖具体机器，移植性好、对用户要求低、易使用、易维护等。使用、易维护等。1.11.1翻译程序、编译程序、解释程序翻译程序、编译程序、解释程序源程序源程序 用汇编语言或高级语言编写的程序称为源程序目标程序（翻译后的程序）目标程序（翻译后的程序） 用目标语言所

5、表示的程序 目标语言：可以是介于源语言和机器语言之间的“中间语言”，可以是某种机器的机器语言,也可以是某机器的汇编语言。翻译程序翻译程序 将源程序转换为目标程序的程序称为翻译程序。它是指各种语言的翻译器，包括汇编程序和编译程序，是汇编程序、编译程序以及各种变换程序的总称。概念：概念：源程序、翻译程序、目标程序 三者关系：源程序翻译程序目标程序SOURCE PROGRAMTRANSLATER OBJECT PROGRAM输入输入输出输出翻译程序（翻译程序（TranslatorTranslator）是一种程序，其输入输入是某种语言某种语言的一系列语句，而其输出输出则是另一种语言另一种语言的一系列语

6、句。1.1.1 1.1.1 翻译程序翻译程序源语言程序源语言程序目标语言程序目标语言程序TranslatorTranslator输入输入输出输出如汇编程序：汇编语言翻译为机器语言。编译程序（编译程序（CompilerCompiler）是一种程序。它把用高级语言写的高级语言写的源程序源程序作为数据接收接收，经过翻译转换，产生面向机器的代面向机器的代码码作为输出输出。这当中代码还可能要由汇编程序汇编程序或装配程序装配程序作进一步加工，得出目标程序目标程序，交给计算机执行。1.1.2 1.1.2 编译程序编译程序高级语言源程序高级语言源程序面向机器代码面向机器代码CompilerCompiler目标

7、程序代码目标程序代码汇编汇编 装配装配源程序的编译和运行l 编译或汇编阶段编译或汇编阶段l 运行阶段运行阶段源程序源程序目标程序目标程序编译程序编译程序或汇编程序或汇编程序输出数据输出数据目标程序目标程序+运行子程序运行子程序输入数据输入数据l 工作过程工作过程解释程序（解释程序（Interpreter）（类似于口译，不生成目标代码）（类似于口译，不生成目标代码） 对源程序进行解释执行的程序。对源程序进行解释执行的程序。输出数据输出数据解释程序解释程序输入数据输入数据源程序源程序1.1.3 1.1.3 解释程序解释程序优点：优点：l 提供一种直接的交互调试能力，在执行用户程序时可以 修改用户程

8、序。l 对新的类型可动态地修改，如符号的意义。l 提高良好的诊断信息l 不依赖于目标机，移植性较好。 事实上，纯粹的解释程序并不多见，通常做某种程序的 结合。编译过程是指将编译过程是指将高级语言程序高级语言程序翻译为等价的翻译为等价的目标程序目标程序的过程。的过程。翻译外文资料：翻译外文资料：1、能、能识别识别出句子中的一个出句子中的一个单词单词；2、分析句子的、分析句子的语法语法结构；结构；3、根据句子的、根据句子的含义含义进行初步进行初步翻译翻译；4、对译文进行、对译文进行修饰修饰；5、写出最后的译文。、写出最后的译文。1.21.2编译过程概述编译过程概述l翻译和编译工作的比较翻译和编译工

9、作的比较翻译外文翻译外文编译程序编译程序分析分析识别识别单词单词分析分析句子句子根据语义进根据语义进行初步翻译行初步翻译词法分析词法分析语法分析语法分析语义分析、生成中间代码语义分析、生成中间代码综合综合修辞加工修辞加工写出译文写出译文代码优化代码优化目标代码生成目标代码生成符号表管理符号表管理源程序源程序目目标标代代码码生生成成目标程序目标程序出错处理出错处理词词法法分分析析优优化化语语义义分分析析语语法法分分析析编译过程编译过程1. 1. 词法分析词法分析任务任务所做转换所做转换依据依据构词规则构词规则主要理论基础主要理论基础自动机理论自动机理论源程序字符串源程序字符串单词符号单词符号输入

10、源程序；扫描、分解字符串，识别出一输入源程序；扫描、分解字符串，识别出一个个单词（定义符、标识符、运算符、界符、个个单词（定义符、标识符、运算符、界符、常数）常数）概念l单词单词token：是语言的基本语法单位l保留字保留字reserved word (有时也叫关键字有时也叫关键字) （如:if、else、while）l标识符标识符identifier（如:max、min、str）l常数常数 （如:12、6.8）l分界符和分界符和运算符运算符（如:+、-、*、/、;、（、） ）示例示例FOR K FOR K ：= 1 TO 100= 1 TO 100 M M ：= I + 10 = I + 1

11、0 * * K K N N ：= J + 10 = J + 10 * * K KNEXT KNEXT KTOTONEXTNEXTFORFOR K KN NM MI IJ JK KK KK K：= =100100：= =：= =1 110101010+ +* * *+ +关键字关键字标识符标识符分界符分界符运算符运算符 常数常数词法分析程序的结果词法分析程序的结果-二元式二元式(如：如：FOR K：=1 TO 100)单词值单词值单词类别单词类别FOR关键字关键字K标识符标识符：=分界符分界符1常数常数TO关键字关键字100常数常数.2 2 语法分析语法分析任务任务所做转换所做转换依据依据语法规

12、则语法规则主要理论基础主要理论基础上下文无关文法上下文无关文法单词符号单词符号语法单位（语法范畴）语法单位（语法范畴）在词法分析基础上，将单词符号串转化为语在词法分析基础上，将单词符号串转化为语法单位（语法范畴）（短语、子句、句子、法单位（语法范畴）（短语、子句、句子、程序段、程序），并确定整个输入串是否构程序段、程序），并确定整个输入串是否构成语法上正确的程序。成语法上正确的程序。如：This line is a longer sentence语法分析l又例：position := initial + rate * 60 ;（Pascal）规则）规则 :=“:=” :=“+” :=“*” :

13、=“(”“)” := := := 赋值语句标识符表达式表达式+表达式表达式标识符整数标识符:=表达式*id1:=id2+id3*N:=+N 60*id1 Positionid2 initialid3 rate进一步分析语法结构正确的程序是否符合源程序的上下文约束、运算相容性等规定。审查静态语义使用的变量声明了吗？允许操作的运算对象吗？类型正确吗？3 3 语义分析语义分析语义分析l 句子的结构理解了，扑捉它的“含义” 如：杰克说杰瑞把他的作业落在了家里。 “他的”是谁的？ 又：杰克说杰克把他的作业落在了家里。 几个杰克？语义分析l杰克把她的作业落在了家里。（杰克是男生）“杰克”和“她的”不一致。

14、 “杰克”和“他的”才匹配语义分析（语言的规定和实现） int arr2, c; c = arr * 10; “中间代码中间代码”是一种含义明确、便于处理的是一种含义明确、便于处理的记号系统记号系统。 如：三元式、四元式、逆波兰式。如：三元式、四元式、逆波兰式。 例：四元式（运算符，第一运算量，第二运算量，结果）例：四元式（运算符，第一运算量，第二运算量，结果） x:= ax:= a* *b+c b+c （* *， a a， b b， T T1 1） （+，T T1 1, c, T, c, T2 2 ） (:=, T(:=, T2 2 , - , -， x)x)4 4 中间代码中间代码id1:

15、= id2 + id3 * 60(1)(inttoreal,60-t1)(2)(*,id3t1t2)(3)(+,id2t2t3)(4)(:=,t3-id1)5 5 代码优化代码优化任务任务所做转换所做转换依据依据程序等价变换规则程序等价变换规则主要理论基础主要理论基础数据流方程数据流方程中间代码中间代码中间代码（优化后）中间代码（优化后）对于代码（主要是中间代码）进行加工变换，对于代码（主要是中间代码）进行加工变换，以期能够产生更为高效（省时间和空间）的以期能够产生更为高效（省时间和空间）的目标代码。目标代码。代码优化id1:= id2 + id3 * 60(1)(inttoreal60-t1

16、)(2)( * id3t1t2)(3)( +id2t2t3)(4)( :=t3-id1) 变换变换 （1） ( *id360.0t1) ( 2）（ + id2 t1id1)6 6 目标代码生成目标代码生成任务任务所做转换所做转换依据依据硬件体系结构、指令系统硬件体系结构、指令系统中间代码中间代码目标代码目标代码将中间代码变换成特定机器上的低级语言代码将中间代码变换成特定机器上的低级语言代码目标代码形式目标代码形式绝对指令、可重定位指令、汇编指令绝对指令、可重定位指令、汇编指令(*,id360.0t1)(+,id2t1id1)movfid3,R2mulf#60.0,R2movfid2,R1add

17、fR2,R1movfR1,id16.6.目标代码生成目标代码生成l 按逻辑功能不同，可将编译过程划分为五个基本阶段，与此相对应，我们将实现整个编译过程的编译程序划分为五个逻辑阶段（即五个逻辑子过程）。目标代码生成程序代码优化程序语义分析生成中间代码语法分析程序词法分析程序编译过程小结编译过程小结S.PO.P1.3 1.3 编译程序的组织及开发编译程序的组织及开发 编译程序是一个非常复杂的软件系统，虽然编译理编译程序是一个非常复杂的软件系统，虽然编译理论和技术不断发展，开发周期缩短，但研制仍需大量时论和技术不断发展，开发周期缩短，但研制仍需大量时间。追求目标过程自动化。间。追求目标过程自动化。

18、根据编译程序各部分功能，将编译程序分成根据编译程序各部分功能，将编译程序分成前端前端和和后端后端 前端前端：通常将与：通常将与源程序源程序有关的编译部分称为前端。有关的编译部分称为前端。 词法分析、语法分析、语义分析、中间代码生成词法分析、语法分析、语义分析、中间代码生成 -分析部分分析部分 特点：与特点：与源语言源语言有关有关 后端后端：与：与目标机目标机有关的部分称为后端。有关的部分称为后端。 代码优化、代码生成代码优化、代码生成-综合部分综合部分 特点：与特点：与目标机器目标机器有关有关编译程序的前端和后端编译程序的前端和后端.java java源程序文件.class 二进制字节码文件J

19、ava虚拟机（JVM)本地计算机系统编译同一前端同一前端+ +不同后端不同后端 不同机器构成同一语言的编译程序不同机器构成同一语言的编译程序例如例如JavaJava语言语言 同一前端同一前端+ +不同后端不同后端 不同机器构成同一语言的编译程序不同机器构成同一语言的编译程序例如例如.NET.NET框架框架 不同前端不同前端+ +同一后端同一后端 同一机器生成几个语言的编译程序同一机器生成几个语言的编译程序例如例如GCCGCC 第一遍 第二遍 S.P中间形式1S.P中间形式2C2C1S.PO.P对源程序（包括源程序中间形式）从头到尾扫描一次，并做有关的加工处理 ，生成新的源程序中间形式或目标程序

20、，通常称之为一遍。 遍遍上一遍的结果是下一遍的输入，最后一遍生成目标程序。一遍扫描即可完成整个编译工作的称为一遍扫描即可完成整个编译工作的称为一遍扫描编译程序一遍扫描编译程序遍的划分视具体情况而定（内存的大小、源语言的繁简、遍的划分视具体情况而定（内存的大小、源语言的繁简、目标程序质量的高低）目标程序质量的高低） 优点优点：1、减少对内存容量的要求2、编译程序结构清晰、各遍功能独立、相互联系简单缺点缺点：增加读写中间文件的次数，降低效率应用：应用：大部分软件工具的开发，都要使用大部分软件工具的开发，都要使用编译技术和方法编译技术和方法语法制导的结构化编辑器语法制导的结构化编辑器程序格式化工具程

21、序格式化工具软件测试工具软件测试工具静态分析器：不可能执行的代码、定义后未引用的变量静态分析器：不可能执行的代码、定义后未引用的变量动态测试工具：运行后与期望结果比较动态测试工具：运行后与期望结果比较程序理解工具：确定调用关系，画出流程图程序理解工具：确定调用关系，画出流程图高级语言的翻译工具高级语言的翻译工具编译技术的应用及发展编译技术的应用及发展其它应用：其它应用：v文本编辑器文本编辑器v信息检索系统信息检索系统v模式识别器模式识别器v排版、绘图系统排版、绘图系统小结小结 内容内容 1 1 什么是编译程序什么是编译程序 2 2 编译过程和编译程序的结构编译过程和编译程序的结构 3 3 为什

22、么要学习编译程序为什么要学习编译程序 重点重点 对编译程序的功能和结构做一综述对编译程序的功能和结构做一综述 难点难点 了解编译程序各个成分在编译阶段的逻辑关系了解编译程序各个成分在编译阶段的逻辑关系以及他们怎样作为一个整体完成编译任务的以及他们怎样作为一个整体完成编译任务的小结小结1.1.判断下面的陈述是否正确。判断下面的陈述是否正确。（1）编译程序的五个组成部分缺一不可。）编译程序的五个组成部分缺一不可。 （2）高级语言程序到低级语言程序的转换是基）高级语言程序到低级语言程序的转换是基于语义的等价变换。于语义的等价变换。（3）含有优化部分的编译程序的执行效率高。）含有优化部分的编译程序的执行效率高。 （4）因为编译程序和解释程序具有不同的功能，）因为编译程序和解释程序具有不同的功能，所以它们的实现技术也完全不同。所以它们的实现技术也完全不同。（5）编译程序和解释程序的根本区别在于解释）编译程序和解释程序的根本区别在于解释程序对源程序并没有真正进行翻译。程序对源程序并没有真正进行翻译。（6）无论一遍扫描的编译器还是多遍扫描的编）无论一遍扫描的编译器还是多遍扫描的编译器都要对源程序扫描一遍。译器都要对源程序扫描一遍。答案：答案：(1)(1) F F (2) (2) T T