《编译原理讲》PPT课件.ppt

第一讲 编译原理,刘国秀计算机与信息工程学院,本课程的地位,计算机专业的专业基础课是软件技术基础是计算机专业的学生必修的一门主干课是本学科研究生入学考试的课程之一,作用,编译原理是介绍如何将高级程序设计语言变换成计算机硬件所能识别的机器语言，以便计算机进行处理。它的理论基础坚实，其形式化系统不仅应用于编译技术，还大量应用于人工智能、多媒体技术及数据库等领域。,学习本课程的目的和任务,加深对程序设计语言的理解，提升自身的能力。掌握编译的基本概念、基本原理及算法。将编译原理的理论和实践相结合。,学习本课程的方法,前后联系,按编译过程的五个阶段来学习。理论联系实际,通过实验来加深对理论的理解。,考核办法,平时成绩其中：平时作业及上课表现(含实验报告)：10%：实验成绩：20%期末考试：70%,参考资料,编译原理 陈火旺等 第三版 国防工业出版社编译原理 吕映芝 清华大学出版社编译原理典型题解析与实战模拟 刘春林、王挺等 国防科技大学出版社,第一讲 编译程序概述,教学目标 1.掌握什么是编译程序、编译程序组成、编译过程。2.理解编译程序的构造途径、解释程序、编译程序与程序设计环境。教学内容 2.1 什么是编译程序、编译程序组成、编译过程 2.2 编译程序的构造途径 2.3 解释程序 知识扩展,翻译程序 把某一种语言程序(称为源语言程序)转换成另一种语言程序(称为目标语言程序).,2.1 编译程序的组成,一、什么是编译程序,编译程序 把某一种高级语言程序（源程序）转换成另一种低级语言程序（目标程序）(如汇编语言或机器语言程序)的翻译程序诊断编译程序优化编译程序交叉编译程序可变目标编译程序,二、编译程序组成,编译程序由词法分析、语法分析、语义分析、中间代码生成、优化、目标代码生成、表格管理、错误诊断及处理几部分构成。(见图2.1),词法分析器,语法分析器,语义分析与中间代码生成器,优化器,表格管理,错误诊断及处理部分,目标代码生成器,图 2.1 编译程序的总框,编译过程,把英文翻译为中文 识别出句子中的一个个单词；分析句子的语法结构；根据句子的含义进行初步翻译；对译文进行修饰；写出最后的译文。,三、编译过程概述,编译程序的工作一般分为五个阶段:词法分析语法分析语义分析和中间代码生成优化目标代码产生,功能:输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号，并给出单词的类别、属性等。如基本字（begin、end、if、for、while等），标识符、常数、算符和界符（标点符号等等）。依循的原则：词法规则描述工具：正规式和有限自动机,1.词法分析,例如，用C 语言编写的程序段如下：main()float x=2,y=3,s;s=x+y*5;识别出的单词序列为表1-1所示,表1-1词法分析程序,功能:根据词法分析部分提供的单词串，判断这一串单词能否构成正确的表达式或语句等高级程序设计语言中的语法成分并最终构成一个语法上正确的高级语言程序，也就是判断输入的源程序有没有语法错误。例：上例 s=x+y*5 语法分析的任务就是识别出 x+y*5为算术表达式,识别出上述整个符号串为赋值语句倘若写成s+x=y*5就是错误的，不符合语法规则，必然报错。依循的原则：语法规则描述工具：上下文无关文法,2.语法分析,语义分析功能:根据语言的定义来确定各语言成分的含义。这一阶段有两项工作：首先对每种语法范畴进行静态语义审查(如是否定义，类型是否匹配等)，若语义正确，进行另一方面的工作,即中间代码的翻译。例：A*B(检查、类型)依循的原则：语义规则描述工具:属性文法,3.语义分析与中间代码生成,中间代码：是介于高级语言语句和低级语言语句之间的一种独立于具体硬件的记号系统，它即有一定程度的抽象，又和低级语言十分接近，因此，转换成目标代码很容易。常用中间代码：四元式、三元式、间接三元式、逆波兰记号和树形表示等。例：赋值语句Z=(X+0.418)*Y/W；翻译成四元式形式的中间代码为：算符 左操作数 右操作数 结果（+,X，0.418，T1）(*,T1,Y,T2)(/,T2 W,Z)其中，T1和T2是编译期间引进的临时工作变量；第一个四元式意味着把X的值加上0.418存放于T1中；第二个四元式指将T1的值和Y的值相乘存于T2中；第三个四元式指将T2的值除以Y的值保留结果于Z中。,功能：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。依循的原则：程序的等价变换规则优化的主要方面：公共子表达式的提取、循环优化、删除无用代码等。,4.优化,功能:根据目标机的体系结构和指令系统等属性，把中间代码(或经优化的中间代码)变换成目标机上的低级语言代码。依赖于硬件系统结构和机器指令的含义目标代码三种形式:绝对指令代码:可直接运行 可重新定位指令代码:连接装配，汇编指令代码:需要进行汇编,5.目标代码生成,例 s=x+y*5 假设机器有两个寄存器，则上述生成的汇编代码为：(1)MOVF y,R2(2)MULF#5.0,R2(3)MOVF x,R1(4)ADDF R1，R2(5)STR R2,S 解释：(1)将y送到寄存器R2中。(2)将R2中的数据乘上5，结果存储在R2中。(3)将x的数据送到寄存器R1中。(4)将寄存器R1和R2相加，结果存储在R2中。(5)将相加后的结果送到存储单元s中。,表格管理功能：是对表格提供插入、检索、删除等各种操作，以便编译程序能方便地利用表格中记录的各种信息。符号表：登记源程序中出现的每个名字以及名字的各种属性。常见的表格：符号名表，常数表，标号表，入口名表，过程引用表。,错误诊断及处理部分功能：发现源程序中的错误，把有关错误信息报告给用户，并进行适当的处理。错误类型：词法错误、语法错误及语义错误。,2.2 编译程序的构造途径,1.利用自展技术 Ln=LL1L0 图1编译系统的自展过程 自展的方法是：首先确定一个非常简单的核心语言L0，然后用汇编语言或机器语言编写它的编译程序T0；再把语言L0扩展到L1，此时有L0属于L1，并用L0编写出L1的编译程序T1，再把语言L1扩充为L2，此时L1属于L2，并用L1编写L2的编译程序T2这样不断扩展下去，直到完成所要求的编译程序为止，自展技术的使用如图1所示：,图1 编译系统的自展过程,2.利用LEX，YACC等工具 LEX是词法分析器的自动生成系统。它的输入是正规式，输出是词法分析程序（又称扫描器）。LEX的基本思想是由正规式构造有穷自动机，功能结构如下图所示：,YACC（Yet Another Compiler-Compiler）是辅助人们构造编译程序的有效工具，它可以根据用户提供的语言的文法，自动生成语言的语法分析程序。YACC接受LALR(1)文法，生成一种相应的LALR(1)分析式以及一个LALR(1)分析器，而且YACC生成的语法分析程序可以和扫描器连接，生成器如图所示：,3.利用交叉编译技术 交叉编译就是对L语言源程序在计算机A上进行编译，产生的目标程序是计算机B的机器语言程序，该目标程序能够在计算机B上直接运行，而不能在计算机A上直接运行。,4.利用GNU CC开发平台 GNU CC是一个开发交叉编译程序的良好平台。在嵌入式开发中经常用到。,2.3 解释程序,1.概念 所谓解释程序是高级语言翻译程序的一种，它将源语言(如BASIC)书写的源程序作为输入，解释一句后就提交计算机执行一句，并不形成目标程序。,四、解释程序,2.思考 编译程序与解释程序的区别？,知识扩展,1.遍 所谓“遍”就是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。阶段与遍是不同的概念。一遍可以由若干段组成，一个阶段也可以分若干遍来完成。例如，词法分析这一阶段可以单独作为一遍，但更多的时候是把它与语法分析合并为一遍；为了便于处理，语法分析和语义分析与中间代码产生又常常合为一遍。在优化要求很高时，往往还可以把优化阶段分为若干遍来实现。,知识扩展,2.编译的前端与后端编译前端：包括词法分析、语法分析、语义分析、中间代码生成和中间代码优化，主要依赖于源程序。编译后端：包括目标代码生成，依赖于计算机硬件系统和机器指令系统。优点：减少对内存容量的要求，程序逻辑结构清晰;优化更充分，有利于移植。不足:编译程序运行的效率低,前端,后端,知识扩展,3.编译程序与程序设计环境,程序设计环境 编辑程序 编译程序连接程序 调试工具 集成化的程序设计环境,作业布置 复习本节内容,预习下节。,