《编译原理基础》PPT课件.ppt

编译技术,王颖,本课程的地位：,计算机专业的专业基础课 是软件技术的基础 是计算机专业的学生必修的一门主干课,作用：,编译原理是介绍如何将高级程序设计语言变换成计算机硬件所能识别的机器语言，以便计算机进行处理 它的理论基础坚实，其形式化系统不仅应用于编译技术，还大量应用于人工智能、多媒体技术及数据库等领域,内容,介绍编译程序的工作原理与构造方法； 详细介绍如何将一个用高级语言 编写的源程序翻译成机器指令程序。,学习任务,掌握编译的理论基础和形式化系统 了解编译的全过程及其具体实现方法,学习方法,认真听讲，认真理解书中的基本概念、基本原理与基本算法 弄懂书中的例题与习题 在看书或理解例题时，一定要画出相应的细节变化过程，通过画图来加深理解 在理解的基础上记忆 理论结合实践,学习要求,成绩考核方法 平时成绩占40% 期末考试成绩占60% 平时成绩为： 课堂点名：20% 作业：20%,第一章 引论,课前思考,什么是编译程序 编译过程和编译程序的结构 为什么要学习编译程序,学习目标, 明确编译程序的功能及其在计算机系统中的作用。 了解源语言程序被编译为目标程序的整个过程，这个过程一般划分为哪些阶段。 知道编译技术可用于哪类软件的设计和开发。,学习指南,编译程序是现代计算机系统的基本组成部分之一。编译程序一般由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、目标代码生成程序、代码优化程序、表格管理程序和出错处理程序等成分构成。通过课程的学习应掌握各个成分的功能和设计原则，以及在编译阶段的逻辑关系。理解他们怎样作为一个整体完成编译任务的。,知识结构,程序设计语言与编译,程序设计语言 高级语言 汇编语言 机器语言 在计算机上如何执行一个高级语言程序？ 把高级语言程序翻译成机器语言程序 运行所得的机器语言程序求得计算结果,翻译程序：就是把一种语言(称作源语言)书写的程序，在不改变语义的条件下，翻译成另一种语言(称作目标语言)的等价的程序。,编译 专指由高级语言转换为低级语言 解释 接受某高级语言的一个语句输入，进行解释便控制计算机执行，马上得到这句的执行结果，然后再接受下一句,编译程序和解释程序的区别：,Date,Date,（边解释边执行）, b:=2; a:=b+2; write a; ,编译程序,解释程序,movf #2, b movf b , R1 addf #2, R1 movf R1, a,直接将4的值输出（显示）,编译的转换过程 两阶段转换：编译运行,三个阶段转换：编译汇编运行,解释执行,以源程序作为输入，不生成目标代码，一边解释一边执行 能支持交互环境（同增量式编译系统） 优点：直观易懂，结构简单，节省空间，交互方便，易于实现人机对话 。 缺点：效率低。因对源程序的循环语句部分要反复解释执行。 共同点：都需进行词法、语法、语义分析。,什么是编译程序,编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序。对有些高级语言甚至配置了几个不同性能的编译程序。,编译程序作为一个语言翻译程序，也要在翻译过程中检查源程序的语法和语义，报告一些出错和警告信息，帮助程序员更正源程序。,有关编译程序的术语 编译程序的源语言(源程序) 编译程序的目标语言(目标程序) 编译程序的实现语言 给出这些术语的英文： 编译程序-compiler 源语言-source language 源程序-source program 目标语言-target or object language 目标程序-target or object program 实现语言-implementation language,编译程序在计算机系统中的所在层,来自计算机百科全书的定义,软件：计算机系统中的程序及其文档 系统软件：居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。他和具体的应用领域无关，如编译系统和操作系统等。 语言处理系统：把软件语言书写的各种程序处理成可在计算机上执行的程序。 软件语言：用于书写软件的语言。它主要包括需求定义语言，功能性语言，设计性语言，程序设计语言以及文档语言。,高级语言程序的处理过程,先看自然语言的翻译 1.识别出句子中的一个个单词 2.分析句子的语法结构 3.根据句子的含义进行初步翻译 4.对译文进行修饰 5.写出最后译文,编译过程概述,编译过程概述, 词法分析Scanner,任务识别单词符号，是最初级的语法分析。,例：position:=initial+rate*10;,标识符：position 算符：:= 标识符：initial 算符：+ 标识符：rate 算符：* 整数：10 界符：；,依循的规则：语言的构词规则,例： int a; a=a+2;,单词类型 单词值 保留字 int 标识符 a 界符 ; 标识符 a 算符(赋值) = 标识符 a 算符(加) + 整数 2 界符 ；,识别右边程序中的单词,基本字： 标识符： 常数： 运算符： 界限符：,void jisuan() int y,c,d; float x,a,b; x=a+b*50; y=c+)d*(x+b; ,void int float,a b c d x y jisuan,50,+ * =, ; , ( ),语法分析依照词法规则，识别出正确的单词，转换成统一规格，备用 转换 对基本字、运算符、界限符的转换 标识符的转换 常数的转换 转换完成后的格式：（类号、内码） 描述词法规则的有效工具是正规式和有限自动机, 语法分析Parser,任务 在词法分析的基础上，根据语言的语法规则，将单词符号组成各类的语法单位：短语、子句、语句、过程、程序 语法规则： 语言的规则：又称为文法：规定单词如何构成短语、语句、过程和程序 语法规则的表示： BNF：A:=B|C 例：:= :=,赋值语句的语法规则 A:=V=E E:=T|E+T T:=F|T*F F:=V|(E)|C V:=标识符 C:=常数,例：“id1=id2+id3*10” 赋值语句,语法分析的方法 推导（derive）和归约（reduce） 推导 最左推导、最右推导 归约 最左归约、最右归约,语句id1=id2+id3*10的语法树,id1=id2+id3*10,例如： (1) 任何标识符是表达式。 (2) 任何常数(整常数、实常数)是表达式。 (3) 若表达式1和表达式2都是表达式， 那么表达式1+表达式2以及表达式1 * 表达式2都是表达式。,依循的规则：语法规则, 语义分析Semantic Analyzer,任务 完成静态语义审查和处理 上下文相关性审查 类型匹配审查 类型转换,例，int arr2,c; c = arr1 * 10 ;,依循的规则：语义规则,例: Program p(); Var rate:real; procedure initial; position := initial + rate * 10 /* error */ /* error */ /* warning */; ,Program p(); Var rate :real; Var initial :real; Var position :real ; position := initial + rate * 10, 中间代码生成 Intermediate Code Generator,任务：从源程序的树形或其它形式，产生介于源代码和目标代码之间的一种代码。 中间代码：四元式、三元式、逆波兰式,例：a=b+c,四元式,op,arg1,arg2,result,+,b,c,T1,=,T1,a,比如：源程序id1 = id2 + id3 * 10可生成四元式序列,四元式(运算符，运算对象1，运算对象2，结果)常写成赋值语句的形式 结果=运算对象1 运算符 运算对象2 比如c语言的源程序a = b * c + b * d 的四元式序列为 (1) t1 = b * c (2) t2 = b * d (3) t3 = t1 + t2 (4) a = t3, 代码优化,任务 对前面产生的中间代码进行加工变换，以期在最后阶段能产生更为高效的目标代码 原则：等价变换,id1= id2 + id3 * 10 (1) (inttoreal 10 - t1 ) (2) ( * id3 t1 t2 ) (3) ( + id2 t2 t3 ) (4) ( = t3 - id1 ) 变换 （1） ( * id3 10.0 t1 ) ( 2）（ + id2 t1 id1 ),主要方面 公共子表达式的提取、合并已知量、删除无用语句、循环优化等,例如将下面的语句转换成中间代码 for(k=1; k=100;k+) m=i+10*k; n=j+10*k; ,k=1; 10 if k=100 then m=i+10*k; n=j+10*k; k+; goto 10;,k=1; 10 if k=100 then m=i+10*k; n=j+10*k; k+; goto 10;,k=1; m=i; n=j; 10 if k=100 then m=m+10; n=n+10; k+; goto 10;, 目标代码生成 Target Code Generator,任务 将经过优化的中间代码转换成特定机器上的低级语言代码。 目标代码的形式 绝对指令代码：可立即执行的目标代码 汇编指令代码：汇编语言程序，需要通过汇编程序汇编后才能运行 可重定位指令代码：先将各目标模块连接起来，确定变量、常数在主存中的位置，装入主存后才能成为可以运行的绝对指令代码,(* , id3 10.0 t1 ) (+ , id2 t1 id1 ),movf id3,R2 mulf #10.0,R2 movf id2,R1 addf R2,R1 movf R1,id1,编译过程概述, 表格管理,表格管理是一个贯穿编译全过程的工作 表格作用： 用来记录源程序的各种信息以及编译过程中的各种状况 与编译前四个阶段有关的表格有： 符号表、常数表、标号表、分程序入口表、中间代码表等,符号表 是最重要的一种表格 用来登记源程序中的常量名、变量名、数组名、过程名等，记录它们的性质、定义和引用情况。,常数表与标号表,入口名表 作用：登记过程的层号，分程序符号表入口等,中间代码表, 出错处理Error Handler,任务 如果源程序有错误的话，编译程序应设法发现错误，并报告给用户。 完成 由专门的出错处理程序来完成 错误类型： 语法错误：在词法分析和语法分析阶段检测出来 语义错误：一般在语义分析阶段检测 在编译时查出的，叫Compile-time error，在运行时表现才表现出来的错误叫Run-time error。,编译程序结构(components),编译阶段的组合,前端、后端 分析、综合 遍,前端和后端,前端包括编译逻辑结构中的分析部分，即词法分析、语法分析、语义分析和中间代码生成，除此还包括符号表建造及相应分析中的错误处理以及与机器无关的优化部分。 后端包括与目标机有关的部分，即综合部分，它包括目标代码生成及生成期间对符号表的相应检索操作和错误处理操作，以及与机器相关的代码优化部分。 将编译系统划分为前后端，有利于移植编译系统和利用后端为同一目标机配置不同语言的编译系统。,编译阶段的两大步骤分析和综合,分析步骤是指对源程序的分析 线性分析(词法分析或扫描) 层次分析(语法分析) 语义分析 综合步骤是指后端的工作，为目标程序的生成而进行的综合,遍(pass),对源程序(或其中间形式)从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。 注：遍与阶段的含义毫无关系 多遍扫描 优点：节省内存空间，提高目标代码质量，使编译的逻辑结构清晰 缺点：编译时间较长 注：在内存许可情况下，还是遍数尽可能少些,一遍扫描（以语法分析为中心）,分遍原则 目标质量高低(高则多遍) 机器内存大小(小则多遍) 源语言简繁(繁则多遍) 设计人员多少(多则多遍),编译程序生成,直接用机器语言编写编译程序 用汇编语言编写编译程序 注：编译程序核心部分常用汇编语言编写,用高级语言编写编译程序 注：这是普遍采用的方法,自编译 编译工具： LEX（词法分析）与YACC（用于自动产生LALR分析表） 移植（同种语言的编译程序在不同类型的机器之间移植）,编译程序构造,在某机器上为某种语言构造编译程序要掌握以下