,高级语言,汇编语言,SOURCE PROGRAM,Assemble PROGRAM,为什么要学习编译原理,程序设计语言是计算机软件专业的重要核心 学习编程的历程： C语言汇编语言数据结构,2018年9月10日,编 译 原 理,为什么要学习编译原理,计算机软件学科理论与实践相结合的典范。在学习过程中既要注重该领域在理论上取得的完美结论，也要注重这些理论在实际中的应用。,2018年9月10日,编 译 原 理,先修课程,要求先学习以下课程 1.程序设计语言 2.算法与数据结构：栈分配、堆分配、静态分配等各种存储分配方式。线性表、二叉查找树、哈希表等多种数据结构。 3.离散数学：集合论与数理逻辑是进一步学习形式语言与自动机理论的数学基础。 最好学习过或同时学习以下课程 1.软件工程：掌握大型程序设计以及工程化的软件生产方法。 2.形式语言与自动机：相当于本课程中词法分析与语法分析的理论基础。,2018年9月10日,编 译 原 理,要求及学习方法,平时（20%） 无故旷课： 一本教材，认真听课：以讲义为主，板书为辅-做适当的笔记 认真完成课堂和课后作业,期末（80%）:闭卷笔试,课程特点：理论性强，算法复杂,2018年9月10日,编 译 原 理,第1章 编译引论,掌握编译程序中所涉及的有关名词术语2.理解编译程序总的框架，明确编译程序工作的基本过程及各阶段的基本任务,教学目标,2018年9月10日,编 译 原 理,1.1.程序的翻译 1.2. 编译程序的组成 1.3. 编译程序构造 1.4. 编译技术的应用及发展,教学内容,2018年9月10日,编 译 原 理,低级语言（Low level Language) 字位码、机器语言、汇编语言 特点：与特定的机器有关，功效高，但使用复杂、繁 琐、费时、易出错 高级语言 - Fortran、Pascal、C 语言等 特点：不依赖具体机器，移植性好、对用户要求低、易使用、易维护等。,1.1 程序的翻译,2018年9月10日,编 译 原 理,源程序用汇编语言或高级语言编写的程序称为源程序。目标程序用目标语言所表示的程序目标语言：可以是介于源语言和机器语言之间的“中间语言”，可以是某种机器的机器语言,也可以是某机器的汇编语言。,2018年9月10日,编 译 原 理,翻译程序(Translator) 将某一种语言描述的程序(源程序Source Program)翻译成等价的另一种语言描述的程序(目标程序Object Program)的程序,翻译程序,源程序,目标程序,(*.C / *.PAS/*.AS),(*.OBJ / *.EXE/*.*),2018年9月10日,编 译 原 理,源程序、翻译程序、目标程序 三者关系：,源程序,翻译程序,目标程序,SOURCE PROGRAM,TRANSLATER,OBJECT PROGRAM,即源程序是翻译程序的输入，目标程序是翻译程序的输出,2018年9月10日,编 译 原 理,源程序的编译和运行,编译或汇编阶段运行阶段,源程序,目标程序,编译程序 或汇编程序,输出数据,目标程序 + 运行子程序,输入数据,2018年9月10日,编 译 原 理,汇编程序若源程序用汇编语言书写，经过翻译程序得到用机器语言表示的程序，这时的翻译程序就称之为汇编程序，这种翻译过程称为“汇编”(Assemble）编译程序若源程序是用高级语言书写，经加工后得到目标程序，上述翻译过程称“编译”（Compile),汇编程序与编译程序都是翻译程序，主要区别是加工对象的 不同。由于汇编语言格式简单，常与机器语言之间有一一对 应的关系。汇编程序所要做的翻译工作比编译程序简单的多。,2018年9月10日,编 译 原 理,编译程序(Compiler) 高级语言程序汇编/机器语言程序,高级语言源程序,汇编/机器语言目标程序,编译程序,2018年9月10日,编 译 原 理,工作过程,解释：按源语言的定义边解释边执行 解释程序（Interpreter）对源程序进行解释执行的程序。（类似于口译，不生成目标代码）,特点：与编译系统比较，解释系统较简单、 可移植性好，易于查错，但速度慢,2018年9月10日,编 译 原 理,“编译-解释执行”系统,源程序,编译程序,源程序的中间形式,输出数据,解释程序,输入数据,2018年9月10日,编 译 原 理,例如Java语言,2018年9月10日,编 译 原 理,所谓编译过程是指将高级语言程序翻译为等价的目标程序的过程。,翻译外文资料： 1、能识别出句子中的一个单词； 2、分析句子的语法结构； 3、根据句子的含义进行初步翻译； 4、对译文进行修饰； 5、写出最后的译文。,1.2 编译程序的组成,2018年9月10日,编 译 原 理,翻译和编译工作的比较,编译过程,2018年9月10日,编 译 原 理,编译程序总体结构,目标代码生成器,代码优化器,语义分析与中间代码生成器,语法分析器,2018年9月10日,编 译 原 理,单词：是语言的基本语法单位保留字（如:if、else、while）标识符（如:max、min、str）常数 （如:12、6.8、a）分界符 算符（如:+、-、*、/、;、（、） ）,字符序列,任务：根据词法规则分析和识别单词,一、词法分析,编码形式,走向目标1：变成一个单词序列！,2018年9月10日,编 译 原 理,词法分析程序的结果-二元式,y = x + r * 6,2018年9月10日,编 译 原 理,任务：根据语法规则（即语言的文法），分析并识别出各种语法成分（如表达式、语句、函数等），并进行语法正确性检查。,二、语法分析（编译程序的核心）,关键：让系统知道“组成规则”并按照规则分析！,走向目标2：得到越来越接近要表达内容的成分！,实现“组词成句”，构造分析树，指出语法错误，指导翻译,2018年9月10日,编 译 原 理,语法分析的结果-语法树,文法 :=“=”:=“+” | “*” :=“(”“)” | | | ,2018年9月10日,编 译 原 理,任务：依据语义规则对识别出的各种语法成分分析其含义，并进行初步翻译，生成中间代码。,三、语义分析及中间代码生成,静态： 分析语法成份的含义，进行语义上的正确性检查 动态： 根据相应语义，生成中间代码（介于源语言和目标语言之间的中间语言形式）,上下文相关性检查 类型匹配检查 类型转换,2018年9月10日,编 译 原 理,生成中间代码的目的： 1、利于代码优化 2、利于目标代码的移植,中间代码的形式： 四元式、三元式、逆波兰表示,走向目标3：接近机器的表达！,2018年9月10日,编 译 原 理,四元式,其中t1、t2、t3为编译程序引入的临时工作单元,例：y = x + r * 6,2018年9月10日,编 译 原 理,任务：对中间代码进行加工变换，以得到高质量的目标代码,四、代码优化,例：y = x + r * 6,走向目标4：更高效地执行！,2018年9月10日,编 译 原 理,五、目标代码生成,任务：把中间代码变换成特定机器上的低级语言代码,走向目标5：实现目标！,2018年9月10日,编 译 原 理,编译过程小结,程序,程序,程序,程序,2018年9月10日,编 译 原 理,按逻辑功能不同，可将编译过程划分为六个基本阶段，与此相对应，我们将实现整个编译过程的编译程序划分为六个逻辑阶段（即六个逻辑子过程）。,每个阶段中都要有： 符号表管理和错误处理,2018年9月10日,编 译 原 理,诊察错误，并能报告用户错误性质和位置 出错处理能力的优劣是衡量编译程序质量好坏的一个重要指标。,填表：把源程序中的信息和编译过程中所产生的信息登记在表格中 查表：在随后的编译过程中同时又要不断的查找这些表格中的信息,1.2.2 编译程序的公共功能,2018年9月10日,编 译 原 理,管理各种符号表（常数、标号、变量、过程、结构） 查、填（登记、查找）源程序中出现的符号和编译程序生成的符号，为编译的各个阶段提供信息 辅助语法检查、语义检查 完成静态绑定、管理编译过程 Hash表、链表等各种查、填表技术,2018年9月10日,编 译 原 理,进行各种错误的检查、报告、纠正，以及相应的续编译处理（如：错误的定位与局部化） 词法：拼写、定义、 语法：语句结构、表达式结构、 语义：类型不匹配、,2018年9月10日,编 译 原 理,模块分类,编译程序8项功能对应8个模块,翻译,辅助,符号表管理 出错处理,中间代码生成 代码优化 目标代码生成,词法分析 语法分析 语义分析,分析,2018年9月10日,编 译 原 理,典型的编译程序具有7个逻辑部分,S.P,O.P,2018年9月10日,编 译 原 理,对源程序（包括源程序中间形式）从头到尾扫描一次，并做有关的加工处理 ，生成新的源程序中间形式或目标程序，通常称之为一遍。,遍,2018年9月10日,编 译 原 理,一遍扫描即可完成整个编译工作的称为一遍扫描编译程序,遍的划分视具体情况而定（内存的大小、源语言的繁简、目标程序质量的高低）,优点： 1、减少对内存容量的要求 2、编译程序结构清晰、各遍功能独立、相互联系简单,缺点： 增加读写中间文件的次数，降低效率,2018年9月10日,编 译 原 理,根据编译程序各部分功能，将编译程序分成前端和后端,前端：通常将与源程序有关的编译部分称为前端。词法分析、语法分析、语义分析、中间代码生成-分析部分特点：与源语言有关后端：与目标机有关的部分称为后端。代码优化、代码生成 -综合部分特点：与目标机有关,1.2.3 编译阶段的组合,2018年9月10日,编 译 原 理,同一前端+不同后端 不同机器构成同一语言的编译程序,例如Java语言,2018年9月10日,编 译 原 理,同一前端+不同后端 不同机器构成同一语言的编译程序,例如.NET框架,2018年9月10日,编 译 原 理,不同前端+同一后端 同一机器生成几个语言的编译程序,例如GCC,2018年9月10日,编 译 原 理,构造编译程序必须精通: 源 语 言 目标语言 编译方法,1.3 编译程序的构造,2018年9月10日,编 译 原 理, 形图,表示语言翻译的 形图,源语言,表示语言,目标语言,2018年9月10日,编 译 原 理,1）交叉编译(Cross Compiling)/移植,Q1：A机上有一个C语言编译器，是否可利用此编译器实现B机上的C语言编译器？ 条件： 机有 语言的编译程序（P1) 目的：实现 机的 语言的编译(P3),2018年9月10日,编 译 原 理,2018年9月10日,编 译 原 理,2) 本机编译器利用,Q2： A机上有一个C语言编译器，现要实现一个新语言NEW的编译器？能利用交叉编译技术么？,2018年9月10日,编 译 原 理,开发编译程序的途径: 自展法 工具法 自动生成法 移植法,2018年9月10日,编 译 原 理,自展法,2018年9月10日,编 译 原 理,应用：大部分软件工具的开发，都要使用编译技术和方法,语法制导的结构化编辑器 程序格式化工具 软件测试工具 静态分析器：不可能执行的代码、定义后未引用的变量 动态测试工具：运行后与期望结果比较 程序理解工具：确定调用关系，画出流程图 高级语言的翻译工具,1.4 编译技术的应用及发展,2018年9月10日,编 译 原 理,其它应用： 文本编辑器 信息检索系统 模式识别器 排版、绘图系统,2018年9月10日,编 译 原 理,并行编译技术 目的：提高并行计算机体系结构的性能，超大规模计算的日益增长的需求 两种实现方法 利用重构技术将串行程序并行化 直接编写并行程序 交叉编译技术,发展,2018年9月10日,编 译 原 理,