编译原理Chap1

1、2022-6-19第 1 页有了编译技术，计算机语言由单一的机器有了编译技术，计算机语言由单一的机器语言发展到现今的数千种高级语言。语言发展到现今的数千种高级语言。 计算机科学中最成熟的一个分支，集中体现计算机科学中最成熟的一个分支，集中体现了计算机发展的成果与精华。了计算机发展的成果与精华。 计算机软件学科理论与实践相结合的典范。计算机软件学科理论与实践相结合的典范。 编译程序使得多数计算机用户不必考虑与编译程序使得多数计算机用户不必考虑与机器有关的繁琐细节，使程序员独立于机器。机器有关的繁琐细节，使程序员独立于机器。2022-6-19第 2 页 加深对程序语言的加深对程序语言的内部机制的理

2、解内部机制的理解, , 更好地运用更好地运用程序设计语言。程序设计语言。 包括包括软件概念和技术软件概念和技术，可用于一般的软件设计。，可用于一般的软件设计。 蕴涵着蕴涵着抽象问题和解决问题的方法抽象问题和解决问题的方法，对引导科学，对引导科学思维，提高解决问题的能力有重要作用。思维，提高解决问题的能力有重要作用。必修主干课程必修主干课程，操作系统和编译系统构成，操作系统和编译系统构成程序设计者与计算机之间的基本界面。程序设计者与计算机之间的基本界面。为什么要学习编译原理为什么要学习编译原理2022-6-19第 3 页课程主要内容课程主要内容 介绍编译系统的一般构造原理、基本实现技术介绍编译系

3、统的一般构造原理、基本实现技术 形式语言基础知识、词法分析、语法分析、中间代形式语言基础知识、词法分析、语法分析、中间代码生成、代码优化、目标代码生成、符号表的构造码生成、代码优化、目标代码生成、符号表的构造和运行时存储空间的组织等。和运行时存储空间的组织等。 引入一个小型编译程序的教学模型引入一个小型编译程序的教学模型“PL/0PL/0语言的编译程序语言的编译程序”，建立起编译程序实现的整，建立起编译程序实现的整体概念。体概念。编译原理编译原理 = 形式语言理论形式语言理论 + 编译技术编译技术2022-6-19第 4 页 理论和实践要求很高理论和实践要求很高 掌握有关编译的掌握有关编译的经

4、典基础理论经典基础理论 能够运用先进的软件开发技术能够运用先进的软件开发技术构造小型编译系统构造小型编译系统学习本课程的基本要求学习本课程的基本要求 先修课程先修课程l程序设计语言程序设计语言l算法与数据结构算法与数据结构：栈分配、堆分配、静态分配：栈分配、堆分配、静态分配等存储分配方式。线性表、二叉查找树、哈希等存储分配方式。线性表、二叉查找树、哈希表等多种数据结构。表等多种数据结构。 l离散数学离散数学：集合论与数理逻辑是形式语言与自：集合论与数理逻辑是形式语言与自动机理论的数学基础。动机理论的数学基础。 2022-6-19第 5 页编译原理课程应用领域编译原理课程应用领域有穷自动机有穷自

5、动机模式识别模式识别情报检索情报检索文本编辑程序文本编辑程序上下文无关文法上下文无关文法语法制导翻译语法制导翻译建立多种文本处理程序建立多种文本处理程序代码优化技术代码优化技术由非结构化到结构化的程序转换由非结构化到结构化的程序转换程序校验程序校验2022-6-19第 6 页2022-6-19第 7 页用用C语言写的完整的语言写的完整的用每一章中学到的不同技术分块建立起来的。用每一章中学到的不同技术分块建立起来的。通过通过TINY 编译器的建立，从整体上掌握编译编译器的建立，从整体上掌握编译器构造的方法。器构造的方法。2022-6-19第 8 页编译原理课程设计编译原理课程设计2022-6-1

6、9第 9 页课程安排课程安排讲课：讲课：38学时学时实验：实验：16学时学时(词法分析、语法分析、语义分析、符号表词法分析、语法分析、语义分析、符号表) 答疑时间答疑时间周四周四 12:00-13:00 网络中心网络中心307联系方式联系方式史一民史一民 信息科学与技术学院信息科学与技术学院 计算机系计算机系E-mail：课时及答疑课时及答疑2022-6-19第 10 页第第8-15周周 周一周一3-4节节计科楼计科楼 201室室上机实验安排上机实验安排2022-6-19第 11 页课程考核标准课程考核标准2022-6-19第 12 页1.1.掌握编译程序中所涉及的有关名词术语掌握编译程序中所

7、涉及的有关名词术语2.2.理解编译程序总体框架，明确编译程序工理解编译程序总体框架，明确编译程序工作的基本过程及各阶段的基本任务作的基本过程及各阶段的基本任务教学目标教学目标第一章第一章 编译程序概述编译程序概述2022-6-19第 13 页第一章第一章 编译程序概述编译程序概述2022-6-19第 14 页1.1 什么是编译程序什么是编译程序程序设计语言程序设计语言2022-6-19第 15 页汇编程序汇编程序把汇编语言书写的程序翻译成机器语言程序。把汇编语言书写的程序翻译成机器语言程序。编译程序编译程序把高级语言书写的程序翻译成汇编或目标程序把高级语言书写的程序翻译成汇编或目标程序。翻译程

8、序翻译程序翻译程序翻译程序 将源程序转换为目标程序的程序。将源程序转换为目标程序的程序。汇编程序、编译程序以及各种变换程序的总称汇编程序、编译程序以及各种变换程序的总称。2022-6-19第 16 页一种相当复杂的程序，长度可从一种相当复杂的程序，长度可从10,00010,000行到行到1,000,0001,000,000行不等。编写甚至读懂都非易事。行不等。编写甚至读懂都非易事。大多数的计算机科学家和专业人员也从来没有编写过大多数的计算机科学家和专业人员也从来没有编写过一个完整的编译器。一个完整的编译器。任何一个与计算机打交道的专业人员都应掌握编译器任何一个与计算机打交道的专业人员都应掌握编

9、译器的基本结构和操作。的基本结构和操作。 高级语言高级语言书写的程序书写的程序 编译程序编译程序低级语言程序低级语言程序编译程序编译程序(compiler)2022-6-19第 17 页源程序的编译和运行源程序的编译和运行源程序源程序目标程序目标程序编译程序编译程序或汇编程序或汇编程序输出数据输出数据目标程序目标程序+运行子程序运行子程序输入数据输入数据2022-6-19第 18 页对源程序进行解释执行的程序。对源程序进行解释执行的程序。类似于口译，不生成目标代码类似于口译，不生成目标代码l与编译系统比较的特点：与编译系统比较的特点：l较简单较简单l可移植性好，易于查错，但速度慢。可移植性好，

10、易于查错，但速度慢。解释程序解释程序（Interpreter）2022-6-19第 19 页编译和解释程序编译和解释程序2022-6-19第 20 页解释程序和编译程序的区别解释程序和编译程序的区别是否生成目标代码是否生成目标代码u很多语言如很多语言如BASIC,LISP和和PROLOG等等最初都是解等等最初都是解释执行的，后来也都有了编译系统。释执行的，后来也都有了编译系统。uJAVA环境同时需要解释和编译系统的支持。环境同时需要解释和编译系统的支持。 2022-6-19第 21 页“编译编译- -解释执行解释执行”系统系统源程序源程序源程序的中间形式源程序的中间形式输出数据输出数据输入数据

11、输入数据解释程序解释程序编译程序编译程序2022-6-19第 22 页Java虚拟机（虚拟机（JVM)本地计算机系统本地计算机系统Java语语言言“编译编译- -解释执行解释执行”系系统统编译程序编译程序.java Java源程序文件源程序文件.class 二进制字节码文件二进制字节码文件2022-6-19第 23 页源语言源语言(源程序源程序) 目标语言目标语言(目标程序目标程序)实现语言实现语言术术 语语宿主机：宿主机：运行编译程序的计算机。运行编译程序的计算机。目标机：目标机：运行编译程序所产生的目标代码的计算机。运行编译程序所产生的目标代码的计算机。源程序源程序 编译程序编译程序目标程

12、序目标程序2022-6-19第 24 页1.2 编译过程和编译程序的结构编译过程和编译程序的结构翻译外文资料：翻译外文资料：1、识别出句子中的单词；、识别出句子中的单词；2、分析句子的语法结构；、分析句子的语法结构；3、根据句子的含义进行初步翻译；、根据句子的含义进行初步翻译；4、对译文进行修饰；、对译文进行修饰；5、写出最后的译文。、写出最后的译文。2022-6-19第 25 页综综合合分分析析编译过程编译过程词法分析词法分析语法分析语法分析语义分析及语义分析及中间代码生成中间代码生成代码优化代码优化目标代码生成目标代码生成2022-6-19第 26 页编译程序的逻辑结构编译程序的逻辑结构2

13、022-6-19第 27 页1 1、词法分析、词法分析识别识别单词单词字符序列字符序列单词序列单词序列具有独立意义的最小单位具有独立意义的最小单位2022-6-19第 28 页词法分析程序的结果词法分析程序的结果-二元组二元组y = x + r * 62022-6-19第 29 页begin var sum, first, count:real; sum:= first + count * 102022-6-19第 30 页2、语法分析、语法分析2022-6-19第 31 页2. 2. 语法分析语法分析printf(“hello”)；2022-6-19第 32 页2. 2. 语法分析语法分析赋

14、值语句赋值语句标识符标识符标识符标识符整数整数标识符标识符表达式表达式=yx表达式表达式表达式表达式+r6表达式表达式表达式表达式*:=:=+ | *:=() | | | y = x + r * 62022-6-19第 33 页3. 语义分析语义分析(Semantic Analysis)2022-6-19第 34 页语义分析任务举例语义分析任务举例表达式表达式赋值语句赋值语句确定表达式的类型确定表达式的类型自定义函数自定义函数分析赋值号左侧是否为变量分析赋值号左侧是否为变量检查实参和形参个数、类型检查实参和形参个数、类型2022-6-19第 35 页4.4.中间代码生成中间代码生成 (Inte

15、rmediate Code)Polish Notation逆波兰（后缀表示）逆波兰（后缀表示）id1id2id3 * +四元组四元组 ( (* *, ,id2,id3,T1) (+,id1 ,T1 ,T2) 2022-6-19第 36 页四元式四元式t1、t2、t3为为编译程序引入的临时工作单元编译程序引入的临时工作单元运算符运算符左运算对象左运算对象 右运算对象右运算对象 结果结果y = x + r * 62022-6-19第 37 页5. 代码优化代码优化2022-6-19第 38 页与机器无关的优化与机器无关的优化5. 代码优化代码优化2022-6-19第 39 页运算符运算符左运算对象

16、左运算对象右运算对象右运算对象结果结果(1)inttoreal6-t1(4)=t3yy = x + r * 62022-6-19第 40 页6. 目标代码生成目标代码生成movr, R1mul#6.0, R1movx, R2addR1, R2movR2, yy = x + r * 62022-6-19第 41 页7、表格管理、表格管理2022-6-19第 42 页8、错误处理、错误处理全全 最大限度发现错误最大限度发现错误准准 准确指出错误的性质和发生地点准确指出错误的性质和发生地点局部化局部化 将错误的影响限制在尽可能小的范围内将错误的影响限制在尽可能小的范围内若能若能自动校正错误自动校正错

17、误则更好，但其代价非常高则更好，但其代价非常高2022-6-19第 43 页1.3 编译阶段的组合编译阶段的组合 与源语言有关与源语言有关而与目标机无关的而与目标机无关的与目标机有关，与目标机有关，而与源语言无关的。而与源语言无关的。词法分析词法分析语法分析语法分析中间代码生成中间代码生成代码优化代码优化目标代码生成目标代码生成2022-6-19第 44 页1.3 编译阶段的组合编译阶段的组合pass：对源程序对源程序或源程序的中间结果从头或源程序的中间结果从头到尾扫描一遍，到尾扫描一遍，并作加工处理，生成新的并作加工处理，生成新的中间结果或目标程序。中间结果或目标程序。词法分析词法分析语法分

18、析语法分析中间代码生成中间代码生成代码优化代码优化目标代码生成目标代码生成一遍一遍一遍一遍 局部优化局部优化一遍一遍一遍一遍 全局优化全局优化核心核心2022-6-19第 45 页一趟扫描程序与多趟扫描程序一趟扫描程序与多趟扫描程序l功能块清晰功能块清晰l占用内存少（重叠使用内存）占用内存少（重叠使用内存）l程序紧凑程序紧凑l速度快速度快2022-6-19第 46 页1.4 编译技术的发展和应用编译技术的发展和应用 1 1 编译程序的发展编译程序的发展n第一个编译程序：第一个编译程序：20世纪世纪50年代早期年代早期u很难讲出确切的时间，大量的实验和实现是由不同很难讲出确切的时间，大量的实验和

19、实现是由不同的小组独立完成的的小组独立完成的 u早期的编译工作：将算术公式翻译成机器代码。早期的编译工作：将算术公式翻译成机器代码。n20世纪世纪50年代中期出现了年代中期出现了FORTRAN等一批高级等一批高级语言，相应的一批编译系统开发成功。语言，相应的一批编译系统开发成功。 2022-6-19第 47 页n20世纪世纪50年代末：编译程序的自动生成工具，编年代末：编译程序的自动生成工具，编译程序的编译程序译程序的编译程序 。u以任一语言的词法规则、语法规则和语义解释出发，自动产以任一语言的词法规则、语法规则和语义解释出发，自动产生该语言的编译程序生该语言的编译程序 u自动生成工具自动生成

20、工具F词法分析程序的生成系统词法分析程序的生成系统LEXLEX，语法分析程序的生成系统，语法分析程序的生成系统YACCYACC等等 n20世纪世纪60年代起：自展技术年代起：自展技术u用被编译的语言来书写该语言自身的编译程序用被编译的语言来书写该语言自身的编译程序 u1971年，年，PASCAL的编译程序用自展技术生成后，其的编译程序用自展技术生成后，其影响就越来越大。影响就越来越大。 1 1 编译程序的发展编译程序的发展2022-6-19第 48 页n处理并行语言的处理并行语言的并行编译技术，并行编译技术，将串行程序转将串行程序转换成并行程序的换成并行程序的自动并行编译技术自动并行编译技术也

21、正在深入也正在深入研究之中研究之中n嵌入式应用迅速增长的需求，推动了嵌入式应用迅速增长的需求，推动了交叉编译交叉编译技术技术的发展。的发展。n系统芯片设计方法和关键系统芯片设计方法和关键EDA技术的研究，也技术的研究，也带动了带动了专用语言专用语言VHDL等及其编译技术等及其编译技术的不断的不断深化深化 。 1 1 编译程序的发展编译程序的发展2022-6-19第 49 页n语言范型语言范型（支持的计算模式）（支持的计算模式）n计算机体系结构计算机体系结构2 2 推动编译技术发展的因素推动编译技术发展的因素 2022-6-19第 50 页3 3 研究领域研究领域2022-6-19第 51 页1

22、.5 编译程序实现的途径编译程序实现的途径开发编译程序的途径开发编译程序的途径: 预处理法预处理法 移植法移植法() 工具法工具法 理论法理论法2022-6-19第 52 页 形图形图n表示一个编译程序所涉及到的三方面表示一个编译程序所涉及到的三方面源语言源语言实现语言实现语言目标语言目标语言2022-6-19第 53 页1 交叉编译交叉编译( (Cross Compiling) )（运行编译程序的计算机（运行编译程序的计算机）2022-6-19第 54 页交叉编译交叉编译 举例举例n条件：条件： 机有机有 语言的编译程序语言的编译程序 P1P1n目的：实现目的：实现 机的机的 语言的编译语言的编译 P3P3语言语言语言语言机器机器语言语言机器机器A机器机器语言语言A机器机器机器机器2. (机的机的C编译编译P1)编译编译P0，得到在，得到在A机上可运行的机上可运行的P2(C 1. (人人)用用 语言编制语言编制B机的编译程序机的编译程序P0(C2022-6-19第 55 页语言语言语言语言机器机器语言语言机器机器3. (机的机的P2)编译编译P0，得到在，得到在B机上可运行机上可运行的的P3(C 机器机器语言语言机器机器机器机器交叉编译交叉编译 举例举例2022-6-19第 56 页2 编译程序的自展技术编译程