1、高级语言汇编语言SOURCE PROGRAMAssemble PROGRAM？翻译程序？翻译程序？TRANSLATER 程序设计语言是计算机软件专业的重要核心程序设计语言是计算机软件专业的重要核心 学习编程的历程：学习编程的历程：C C语言汇编语言数据结构语言汇编语言数据结构 编编 译译 原原 理理第1页，共57页。必修主干课程必修主干课程，操作系统和编译系统构成程序设，操作系统和编译系统构成程序设计者与计算机之间的基本界面。计者与计算机之间的基本界面。通过学习该课程，掌握编译的基本理论、常用的通过学习该课程，掌握编译的基本理论、常用的编译技术，了解编译过程及编译系统结构和机理编译技术，了解编
2、译过程及编译系统结构和机理。能运用所学技术解决实际问题，能。能运用所学技术解决实际问题，能独立编写一独立编写一个小型编译系统个小型编译系统。此外，通过学习编译原理可以更好地理解程序语言此外，通过学习编译原理可以更好地理解程序语言的内部机制的内部机制,从而更好地理解和运用程序设计语言。从而更好地理解和运用程序设计语言。能运用编译程序构造的原理和技术完成能运用编译程序构造的原理和技术完成相关软件工相关软件工具的设计和开发具的设计和开发工作。工作。编编 译译 原原 理理第2页，共57页。计算机软件学科计算机软件学科理论与实践相结合理论与实践相结合的典范。的典范。在学习过程中既要注重该领域在理论上取得
3、在学习过程中既要注重该领域在理论上取得的完美结论，也要注重这些理论在实际中的的完美结论，也要注重这些理论在实际中的应用。应用。编编 译译 原原 理理第3页，共57页。要求先学习以下课程要求先学习以下课程1.程序设计语言程序设计语言2.算法与数据结构算法与数据结构：栈分配、堆分配、静态分配等各种存：栈分配、堆分配、静态分配等各种存储分配方式。线性表、二叉查找树、哈希表等多种数据结储分配方式。线性表、二叉查找树、哈希表等多种数据结构。构。3.离散数学离散数学：集合论与数理逻辑是进一步学习形式语言：集合论与数理逻辑是进一步学习形式语言与自动机理论的数学基础。与自动机理论的数学基础。最好学习过或同时学
4、习以下课程最好学习过或同时学习以下课程1.软件工程软件工程：掌握大型程序设计以及工程化的软件生产方：掌握大型程序设计以及工程化的软件生产方法。法。2.形式语言与自动机形式语言与自动机：相当于本课程中词法分析与语法分析：相当于本课程中词法分析与语法分析的理论基础。的理论基础。编编 译译 原原 理理第4页，共57页。李冬梅，施海虎，李冬梅，施海虎，编译原理编译原理，人民邮电出版社，人民邮电出版社教材教材参考书参考书 李建中译，李建中译，编译原理编译原理（龙书）（龙书），机械工业出版社，机械工业出版社 陈火旺陈火旺 刘春林等，刘春林等，程序设计语言编译原理程序设计语言编译原理，国，国防工业出版社防工
5、业出版社 吕映芝，张素琴等，吕映芝，张素琴等，编译原理编译原理，清华大学出版社，清华大学出版社 编编 译译 原原 理理第5页，共57页。平时（平时（30%30%）无故旷课：无故旷课：一本教材，一本教材，认真听课认真听课：以讲义为主，板书为辅：以讲义为主，板书为辅-做适当的笔记做适当的笔记 认真完成课堂和课后认真完成课堂和课后作业作业 完成要求的完成要求的课外实验课外实验内容内容 期末（期末（70%70%）:闭卷笔试闭卷笔试课程特点：理论性强，算法复杂课程特点：理论性强，算法复杂 编编 译译 原原 理理第6页，共57页。第第1 1章章编译概述编译概述 掌握编译程序中所涉及的有关名词术语掌握编译程
6、序中所涉及的有关名词术语2.2.理解编译程序总的框架，明确编译程序工作理解编译程序总的框架，明确编译程序工作的基本过程及各阶段的基本任务的基本过程及各阶段的基本任务教学目标教学目标 编编 译译 原原 理理第7页，共57页。1.1.程序的翻译程序的翻译1.2.编译程序的组成编译程序的组成1.3.编译程序构造编译程序构造 1.4.编译技术的应用及发展编译技术的应用及发展教学内容教学内容 编编 译译 原原 理理第8页，共57页。低级语言低级语言（Low level Language)字位码、机器语言、汇编语言字位码、机器语言、汇编语言特点：与特定的机器有关，功效高，但使用复杂、繁特点：与特定的机器有
7、关，功效高，但使用复杂、繁琐、费时、易出错琐、费时、易出错 高级语言高级语言 -Fortran、Pascal、C 语言等语言等特点：不依赖具体机器，移植性好、对用户要求低、易使特点：不依赖具体机器，移植性好、对用户要求低、易使用、易维护等。用、易维护等。1.11.1程序的翻译程序的翻译 编编 译译 原原 理理第9页，共57页。源程序源程序 用汇编语言或高级语言编写的程序称为源程序目标程序目标程序 用目标语言所表示的程序 目标语言：可以是介于源语言和机器语言之间的“中间语言”，可以是某种机器的机器语言,也可以是某机器的汇编语言。翻译程序翻译程序 将源程序转换为目标程序的程序称为翻译程序。它是指各
8、种语言的翻译器，包括汇编程序和编译程序，是汇编程序、编译程序以及各种变换程序的总称。编编 译译 原原 理理第10页，共57页。源程序、翻译程序、目标程序 三者关系：源程序翻译程序目标程序SOURCE PROGRAMTRANSLATER OBJECT PROGRAM即源程序是翻译程序的输入，目标程序是翻译程序的输出S OI 编编 译译 原原 理理第11页，共57页。汇编程序汇编程序 若源程序用汇编语言书写，经过翻译程序得到用机器语言表示的程序，这时的翻译程序就称之为汇编程序，这种翻译过程称为“汇编”(Assemble）编译程序编译程序 若源程序是用高级语言书写，经加工后得到目标程序，上述翻译过程
9、称“编译”（Compile)汇编程序与编译程序都是翻译程序，主要区别是加工对象的不同。由于汇编语言格式简单，常与机器语言之间有一一对应的关系。汇编程序所要做的翻译工作比编译程序简单的多。编编 译译 原原 理理第12页，共57页。编译或汇编阶段编译或汇编阶段 运行阶段运行阶段源程序源程序目标程序目标程序编译程序编译程序或汇编程序或汇编程序输出数据输出数据目标程序目标程序+运行子程序运行子程序输入数据输入数据 编编 译译 原原 理理第13页，共57页。工作过程工作过程解释程序（解释程序（Interpreter）（类似于口译，不生成目标代码）（类似于口译，不生成目标代码）对源程序进行解释执行的程序。
10、对源程序进行解释执行的程序。输出数据输出数据解释程序解释程序输入数据输入数据源程序源程序 特点：与编译系统比较，解释系统较简单、特点：与编译系统比较，解释系统较简单、可移植性好，易于查错，但速度慢可移植性好，易于查错，但速度慢 编编 译译 原原 理理第14页，共57页。源程序源程序编译程序编译程序源程序的中间形式输出数据输出数据解释程序解释程序输入数据输入数据 编编 译译 原原 理理第15页，共57页。.java java源程序文件.class 二进制字节码文件Java虚拟机（JVM)本地计算机系统编译例如例如JavaJava语言语言 编编 译译 原原 理理第16页，共57页。所谓编译过程是指
11、将所谓编译过程是指将高级语言程序高级语言程序翻译为等价的翻译为等价的目标程序目标程序的的过程。过程。翻译外文资料：翻译外文资料：1、能识别出句子中的一个单词；、能识别出句子中的一个单词；2、分析句子的语法结构；、分析句子的语法结构；3、根据句子的含义进行初步翻译；、根据句子的含义进行初步翻译；4、对译文进行修饰；、对译文进行修饰；5、写出最后的译文。、写出最后的译文。1.21.2编译程序的组成编译程序的组成 编编 译译 原原 理理第17页，共57页。翻译和编译工作的比较翻译和编译工作的比较翻译外文翻译外文编译程序编译程序分析分析识别单词识别单词分析句子分析句子根据语义进根据语义进行初步翻译行初
12、步翻译词法分析词法分析语法分析语法分析语义分析、生成中间代码语义分析、生成中间代码综合综合修辞加工修辞加工写出译文写出译文代码优化代码优化目标代码生成目标代码生成编译过程编译过程 编编 译译 原原 理理第18页，共57页。词法分析词法分析语法分析语法分析语义分析及中间代码生成语义分析及中间代码生成代码优化代码优化目标代码生成目标代码生成习惯上是将编译过程划分为习惯上是将编译过程划分为5 5个基本阶段个基本阶段：编译过程编译过程 编编 译译 原原 理理第19页，共57页。单词单词：是语言的基本语法单位 保留字保留字（如:if、else、while）标识符标识符（如:max、min、str）常数常
13、数 （如:12、6.8、a）分界符分界符（如:+、-、*、/、;、（、）字符序列字符序列任务：根据词法规则分析和识别单词一、词法分析一、词法分析编码形式编码形式 编编 译译 原原 理理第20页，共57页。词法分析程序的结果词法分析程序的结果-二元式二元式y=x+r*6单词值单词值单词类别单词类别y标识符标识符=分界符（赋值）分界符（赋值）x标识符标识符+分界符（加号）分界符（加号）r标识符标识符*分界符（乘号）分界符（乘号）6常数常数 编编 译译 原原 理理第21页，共57页。词法分析词法分析(lexical analysis or scanning)(lexical analysis or
14、scanning)-The stream of characters making up a-The stream of characters making up a source program is read from left to right source program is read from left to right and grouped into tokens,which are sequences and grouped into tokens,which are sequences of characters that have a collective of char
15、acters that have a collective meaning.meaning.单词单词-token-token 保留字保留字-reserved word-reserved word 标识符标识符 -identifier(user-defined name)-identifier(user-defined name)编编 译译 原原 理理第22页，共57页。任务：任务：根据根据语法规则语法规则（即语言的文法），分析并识别出（即语言的文法），分析并识别出各种各种语法成分语法成分（如表达式、语句、函数等），并进行（如表达式、语句、函数等），并进行语法语法正确性检查正确性检查。二二、语法
16、分语法分析（编译程序的核心）析（编译程序的核心）文法文法:=“=”:=“+”|“*”:=“(”“)”|编编 译译 原原 理理第23页，共57页。赋值语句赋值语句标识符标识符标识符标识符整数整数标识符标识符表达式表达式=yx表达式表达式表达式表达式+r6表达式表达式表达式表达式*:=“=”:=“+”|“*”:=“(”“)”|y =x+r*6 编编 译译 原原 理理第24页，共57页。赋值语句赋值语句标识符标识符表达式表达式表达式表达式表达式表达式表达式表达式标识符标识符整数整数标识符标识符表达式表达式y=x+r*6语法分析的结果语法分析的结果-语法树语法树 编编 译译 原原 理理第25页，共57
17、页。有关术语有关术语 语法分析语法分析(syntax analysis or parsing)The purpose of syntax analysis is to determine the source programs phrase structure.This process is also called parsing.The source program is parsed to check whether it conforms to the source languages syntax,and to construct a suitable representation o
18、f its phrase structure.编编 译译 原原 理理第26页，共57页。任务：依据语义规则对识别出的各种语法成分析其含义，并进行初步翻译，生成中间代码。三、语义分析及中间代码生成三、语义分析及中间代码生成静态：静态：分析语法成份的含义，进行语义上的正确性检查分析语法成份的含义，进行语义上的正确性检查动态：动态：根据相应语义，生成根据相应语义，生成中间代码（中间代码（介于源语言和目标语言介于源语言和目标语言之间的中间语言形式）之间的中间语言形式）编编 译译 原原 理理第27页，共57页。生成中间代码的目的：生成中间代码的目的：1、利于代码优化、利于代码优化2、利于目标代码的移植、
19、利于目标代码的移植中间代码的形式：中间代码的形式：四元式、三元式、逆波兰表示四元式、三元式、逆波兰表示 编编 译译 原原 理理第28页，共57页。四元式四元式其中t1、t2、t3为编译程序引入的临时工作单元例：y =x+r*6运算符左运算对象 右运算对象 结果(1)inttoreal 6-t1(2)*rt1t2(3)+t2xt3(4)=t3y 编编 译译 原原 理理第29页，共57页。有关术语有关术语 语义分析语义分析(semantic analysis)The parsed program is further analyzed to determine whether it conform
20、s to the source languages contextual constraints:scope rules,type rulese.g.To relate each applied occurrence of an identifier in the source program to the corresponding declaration.编编 译译 原原 理理第30页，共57页。有关术语有关术语 中间代码生成中间代码生成(intermediate code generation)This is where the intermediate representation o
21、f the source program is created.We want this representation to be easy to generate,and easy to translate into the target program.The representation can have a variety of forms,but a common one is called three-address code or 4-tuple code.编编 译译 原原 理理第31页，共57页。任务：任务：对中间代码进行加工变换加工变换，以得到高质量的目标代码四、代码优化四、
22、代码优化运算符左运算对象 右运算对象 结果(1)Inttoreal6-t1(2)*rt1t2(3)+t2xt3(4)=t3y运算符左运算对象右运算对象结果(1)*r6.0t1(2)+t1xy(1)inttoreal6-t1(4)=t3y例：y =x+r*6 编编 译译 原原 理理第32页，共57页。有关术语有关术语 代码优化代码优化(Intermediate code optimization)The optimizer accepts input in the intermediate representation and output a version still in the inte
23、rmediate representation.In this phase,the compiler attempts to produce the smallest,fastest and most efficient running result by applying various techniques.编编 译译 原原 理理第33页，共57页。五、目标代码生成五、目标代码生成任务：任务：把中间代码变换成特定机器上的低级语言代码低级语言代码movr,R1mul#6.0,R1movx,R2addR1,R2movR2,y运算符左运算对象右运算对象结果(1)*r6.0t1(2)+t1xy 编
24、编 译译 原原 理理第34页，共57页。目标代码生成程序代码优化程序语义分析生成中间代码语法分析程序词法分析程序编译过程小结编译过程小结S.PO.P 编编 译译 原原 理理第35页，共57页。按逻辑功能不同，可将编译过程划分为五个基本阶 段，与此相对应，我们将实现整个编译过程的编译程序划 分为五个逻辑阶段（即五个逻辑子过程）。每个阶段中都要有：符号表管理符号表管理和错误处理错误处理 编编 译译 原原 理理第36页，共57页。诊察错误，并能报告用户错误性质和位置出错处理能力的优劣是衡量编译程序质量好坏的一个重要指标。填表：把源程序中的信息和编译过程中所产生的信息登记在表格中查表：在随后的编译过程
25、中同时又要不断的查找这些表格中的信息符号表管理符号表管理错误处理错误处理编译程序的逻辑结构编译程序的逻辑结构 编编 译译 原原 理理第37页，共57页。典型的编译程序具有典型的编译程序具有7个逻辑部分个逻辑部分S.PO.P语义分析及语义分析及生成中间代码生成中间代码程序程序代码生成程序代码生成程序代码优化代码优化程序程序语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管管理理 编编 译译 原原 理理第38页，共57页。根据编译程序各部分功能，将编译程序分成根据编译程序各部分功能，将编译程序分成前端前端和和后端后端 前端前端：通常将与源程序有关的编译部分称为前端。：通
26、常将与源程序有关的编译部分称为前端。词法分析、语法分析、语义分析、中间代码生成词法分析、语法分析、语义分析、中间代码生成 -分析部分分析部分 特点：与特点：与源语言源语言有关有关 后端后端：与目标机有关的部分称为后端。：与目标机有关的部分称为后端。代码优化、代码生成代码优化、代码生成-综合部分综合部分 特点：与特点：与目标机目标机有关有关编译程序的前端和后端编译程序的前端和后端 编编 译译 原原 理理第39页，共57页。.java java源程序文件.class 二进制字节码文件Java虚拟机（JVM)本地计算机系统编译同一前端同一前端+不同后端不同后端 不同机器构成同一语言的编译程序不同机器
27、构成同一语言的编译程序例如例如JavaJava语言语言 编编 译译 原原 理理第40页，共57页。同一前端同一前端+不同后端不同后端 不同机器构成同一语言的编译程序不同机器构成同一语言的编译程序例如例如.NET.NET框架框架 编编 译译 原原 理理第41页，共57页。不同前端不同前端+同一后端同一后端 同一机器生成几个语言的编译程序同一机器生成几个语言的编译程序例如例如GCCGCC 编编 译译 原原 理理第42页，共57页。第一遍 第二遍 S.P中间形式1S.P中间形式2C2C1S.PO.P 上一遍的结果是下一遍的输入，最后一遍生成目标程序。对源程序（包括源程序中间形式）从头到尾扫描一次，并
28、做有关的加工处理 ，生成新的源程序中间形式或目标程序，通常称之为一遍。遍遍 编编 译译 原原 理理第43页，共57页。一遍扫描即可完成整个编译工作的称为一遍扫描即可完成整个编译工作的称为一遍扫描编译程序一遍扫描编译程序遍的划分视具体情况而定（内存的大小、源语言的繁简遍的划分视具体情况而定（内存的大小、源语言的繁简、目标程序质量的高低）、目标程序质量的高低）优点优点：1、减少对内存容量的要求2、编译程序结构清晰、各遍功能独立、相互联系简单缺点缺点：增加读写中间文件的次数，降低效率 编编 译译 原原 理理第44页，共57页。构造编译程序必须精通构造编译程序必须精通:源源 语语 言言 目标语言目标语
29、言 编译方法编译方法1.31.3编译程序的构造编译程序的构造 编编 译译 原原 理理第45页，共57页。开发编译程序的途径开发编译程序的途径:自展法自展法 工具法工具法 自动生成法自动生成法 移植法移植法 编编 译译 原原 理理第46页，共57页。自展法自展法 编编 译译 原原 理理第47页，共57页。应用：应用：大部分软件工具的开发，都要使用编译大部分软件工具的开发，都要使用编译技术和方法技术和方法语法制导的结构化编辑器语法制导的结构化编辑器程序格式化工具程序格式化工具软件测试工具软件测试工具静态分析器：不可能执行的代码、定义后未引用的变量静态分析器：不可能执行的代码、定义后未引用的变量动态
30、测试工具：运行后与期望结果比较动态测试工具：运行后与期望结果比较程序理解工具：确定调用关系，画出流程图程序理解工具：确定调用关系，画出流程图高级语言的翻译工具高级语言的翻译工具1.41.4编译技术的应用及发展编译技术的应用及发展 编编 译译 原原 理理第48页，共57页。其它应用：其它应用：v文本编辑器文本编辑器v信息检索系统信息检索系统v模式识别器模式识别器v排版、绘图系统排版、绘图系统 编编 译译 原原 理理第49页，共57页。并行编译技术并行编译技术 目的：提高并行计算机体系结构的性能，超目的：提高并行计算机体系结构的性能，超大规模计算的日益增长的需求大规模计算的日益增长的需求 两种实现
31、方法两种实现方法 利用重构技术将串行程序并行化利用重构技术将串行程序并行化 直接编写并行程序直接编写并行程序交叉编译技术交叉编译技术发展发展 编编 译译 原原 理理第50页，共57页。交叉编译器由于目标机指令系统与宿主机的指令系统不同，编译时将应由于目标机指令系统与宿主机的指令系统不同，编译时将应用程序的源程序在宿主机上生成目标机代码，称为用程序的源程序在宿主机上生成目标机代码，称为交叉编交叉编译译。SOIOAB 编编 译译 原原 理理第51页，共57页。q语言开发环境中的伙伴程序语言开发环境中的伙伴程序编辑器（编辑器（editor）预处理器（预处理器（preprocessor）连接程序（连接
32、程序（linker）装配程序（装配程序（loader）调试程序（调试程序（debugger）编编 译译 原原 理理第52页，共57页。小结小结 内容内容1 1 什么是编译程序什么是编译程序2 2 编译过程和编译程序的结构编译过程和编译程序的结构3 3 为什么要学习编译程序为什么要学习编译程序 重点重点对编译程序的功能和结构做一综述对编译程序的功能和结构做一综述 难点难点了解编译程序各个成分在编译阶段的逻辑关系以及他了解编译程序各个成分在编译阶段的逻辑关系以及他们怎样作为一个整体完成编译任务的们怎样作为一个整体完成编译任务的小结小结 编编 译译 原原 理理第53页，共57页。习题习题1 1、2
33、2、3 3小结小结小结小结小结小结小结小结小结小结小结小结小结小结思考题思考题 编编 译译 原原 理理第54页，共57页。1.1.判断下面的陈述是否正确。判断下面的陈述是否正确。（1）编译程序的五个组成部分缺一不可。）编译程序的五个组成部分缺一不可。（2）高级语言程序到低级语言程序的转换是基于语）高级语言程序到低级语言程序的转换是基于语义的等价变换。义的等价变换。（3）含有优化部分的编译程序的执行效率高。）含有优化部分的编译程序的执行效率高。（4）因为编译程序和解释程序具有不同的功能，）因为编译程序和解释程序具有不同的功能，所以它们的实现技术也完全不同。所以它们的实现技术也完全不同。（5）编译
34、程序和解释程序的根本区别在于解释程序对源）编译程序和解释程序的根本区别在于解释程序对源程序并没有真正进行翻译。程序并没有真正进行翻译。（6）无论一遍扫描的编译器还是多遍扫描的编译器都）无论一遍扫描的编译器还是多遍扫描的编译器都要对源程序扫描一遍。要对源程序扫描一遍。答案：答案：(1)F (2)T (3)F (4)F (5)F(1)F (2)T (3)F (4)F (5)F (6)T (6)T 编编 译译 原原 理理第55页，共57页。2 2计算机执行用高级语言编写的程序有哪些途径？计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？它们之间的主要区别是什么？3 3画出编译程序的总体逻辑结构图，简述各部分画出编译程序的总体逻辑结构图，简述各部分的主要功能。的主要功能。编编 译译 原原 理理第56页，共57页。练习练习请指出下列错误信息是编译的哪个阶段报告的请指出下列错误信息是编译的哪个阶段报告的else没有匹配的没有匹配的if；使用的函数没有定义；使用的函数没有定义；(1)在数中出现非数字字符。在数中出现非数字字符。答案：答案：(1)(1)语法语法 (2)(2)语义语义 (3)(3)词法词法 编编 译译 原原 理理第57页，共57页。
