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

《《编译原理基础》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《编译原理基础》PPT课件.ppt（74页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译技术王颖本课程的地位：本课程的地位：l计算机专业的专业基础课计算机专业的专业基础课l是软件技术的基础是软件技术的基础l是计算机专业的学生必修的一门主干课是计算机专业的学生必修的一门主干课作用：作用：l编译原理是介绍如何将高级程序设计语言变换成计算机硬件所能识别的机器语言，以便计算机进行处理l它的理论基础坚实，其形式化系统不仅应用于编译技术，还大量应用于人工智能、多媒体技术及数据库等领域内容内容 介绍编译程序的工作原理与构造方法；详细介绍如何将一个用高级语言 编写的源程序翻译成机器指令程序。学习任务学习任务 掌握编译的理论基础和形式化系统 了解编译的全过程及其具体实现方法学习方法学习方法 认

2、真听讲，认真理解书中的基本概念、基认真听讲，认真理解书中的基本概念、基本原理与基本算法本原理与基本算法弄懂书中的例题与习题弄懂书中的例题与习题在看书或理解例题时，一定要画出相应的在看书或理解例题时，一定要画出相应的细节变化过程，通过画图来加深理解细节变化过程，通过画图来加深理解 在理解的基础上记忆在理解的基础上记忆理论结合实践理论结合实践学习要求学习要求 成绩考核方法成绩考核方法平时成绩占平时成绩占40%期末考试成绩占期末考试成绩占60%平时成绩为：平时成绩为：课堂点名：课堂点名：20%作业：作业：20%第一章第一章 引论引论课前思考l什么是编译程序什么是编译程序l编译过程和编译程序的结构编译

3、过程和编译程序的结构l为什么要学习编译程序为什么要学习编译程序 学习目标 明确编译程序的功能及其在计算机系统明确编译程序的功能及其在计算机系统中的作用。中的作用。了解源语言程序被编译为目标程序的整了解源语言程序被编译为目标程序的整个过程，这个过程一般划分为哪些阶段。个过程，这个过程一般划分为哪些阶段。知道编译技术可用于哪类软件的设计和知道编译技术可用于哪类软件的设计和开发。开发。学习指南l编译程序是现代计算机系统的基本组成部分编译程序是现代计算机系统的基本组成部分之一。编译程序一般由词法分析程序、语法之一。编译程序一般由词法分析程序、语法分析程序、语义分析程序、中间代码生成程分析程序、语义分析

4、程序、中间代码生成程序、目标代码生成程序、代码优化程序、表序、目标代码生成程序、代码优化程序、表格管理程序和出错处理程序等成分构成。通格管理程序和出错处理程序等成分构成。通过课程的学习应掌握各个成分的功能和设计过课程的学习应掌握各个成分的功能和设计原则，以及在编译阶段的逻辑关系。理解他原则，以及在编译阶段的逻辑关系。理解他们怎样作为一个整体完成编译任务的。们怎样作为一个整体完成编译任务的。知识结构程序设计语言与编译程序设计语言与编译l程序设计语言程序设计语言高级语言高级语言汇编语言汇编语言机器语言机器语言l在计算机上如何执行一个高级语言程序？在计算机上如何执行一个高级语言程序？把高级语言程序翻

5、译成机器语言程序把高级语言程序翻译成机器语言程序运行所得的机器语言程序求得计算结果运行所得的机器语言程序求得计算结果翻译程序：就是把一种语言翻译程序：就是把一种语言(称作源语言称作源语言)书写书写的程序，的程序，在不改变语义的条件下在不改变语义的条件下，翻译成另一，翻译成另一种语言种语言(称作目标语言称作目标语言)的的等价等价的程序。的程序。Source ProgramTranslatorTarget ProgramHigh-level LanguageLow-level LanguageCompilerAssembly LanguageMachine CodeAssemblerl编译编译专指

6、由高级语言转换为低级语言专指由高级语言转换为低级语言l解释解释接受某高级语言的一个语句输入，进行解释便接受某高级语言的一个语句输入，进行解释便控制计算机执行，马上得到这句的执行结果，控制计算机执行，马上得到这句的执行结果，然后再接受下一句然后再接受下一句编译程序和解释程序的区别：编译程序和解释程序的区别：Source ProgramTranslatorTargetProgramRunResultDateDateSource ProgramInterpreterResult（边解释边执行）b:=2;a:=b+2;write a;编译程序解释程序movf#2,bmovf b,R1addf#2,R1

7、movf R1,a直接将4的值输出（显示）l编译的转换过程编译的转换过程两阶段转换：编译两阶段转换：编译运行运行源源程程序序编编译译程程序序目目标标代代码码编译时编译时初初始始数数据据运行运行子程子程序目序目标代标代码码计计算算结结果果运行时运行时三个阶段转换：编译三个阶段转换：编译汇编汇编运行运行源源程程序序编编译译程程序序汇汇编编语语言言编译时编译时初初始始数数据据运行运行子程子程序目序目标代标代码码计计算算结结果果运行时运行时汇汇编编程程序序目目标标代代码码汇编时汇编时解释执行l以源程序作为输入，不生成目标代码，一边解释一边执行l能支持交互环境（同增量式编译系统）l优点：直观易懂，结构简

8、单，节省空间，交互方便，易于实现人机对话。l缺点：效率低。因对源程序的循环语句部分要反复解释执行。l共同点：都需进行词法、语法、语义分析。什么是编译程序什么是编译程序l编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序。对有些高级语言甚至配置了几个不同性能的编译程序。l编译程序作为一个语言翻译程序，也要在编译程序作为一个语言翻译程序，也要在翻译过程中检查源程序的语法和语义，报翻译过程中检查源程序的语法和语义，报告一些出错和警告信息，帮助程序员更正告一些出错和警告信息，帮助程序员更正源程序。源程序。l有关编译程序的术语术语编译程序的源语言(源程序)编译

9、程序的目标语言(目标程序)编译程序的实现语言l给出这些术语的英文术语的英文：编译程序-compiler源语言-source language源程序-source program目标语言-target or object language目标程序-target or object program实现语言-implementation language 编译程序在计算机系统中的所在层来自计算机百科全书的定义来自计算机百科全书的定义 l软件：计算机系统中的程序及其文档l系统软件：居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。他和具体的应用领域无关，如编译系统和操作系统等。l语

10、言处理系统：把软件语言书写的各种程序处理成可在计算机上执行的程序。l软件语言：用于书写软件的语言。它主要包括需求定义语言，功能性语言，设计性语言，程序设计语言以及文档语言。高级语言程序的处理过程l先看自然语言的翻译1.识别出句子中的一个个单词2.分析句子的语法结构3.根据句子的含义进行初步翻译4.对译文进行修饰5.写出最后译文编译过程概述编译过程概述 词法分析词法分析Scanner 任务识别单词符号，是最初级的语法分析。例：position:=initial+rate*10;标识符：position算符：:=标识符：initial算符：+标识符：rate算符：*整数：10界符：；依循的规则：语

11、言的构词规则l例：例：int a;a=a+2;单词类型单词类型 单词值单词值保留字 int标识符 a界符 ;标识符 a 算符(赋值)=标识符 a算符(加)+整数 2界符 ；识别右边程序中的单词l基本字：l标识符：l常数：l运算符：l界限符：void jisuan()int y,c,d;float x,a,b;x=a+b*50;y=c+)d*(x+b;void int floata b c d x y jisuan50+*=;,()l语法分析依照词法规则，识别出正确的单词，转换成统一规格，备用l转换对基本字、运算符、界限符的转换标识符的转换常数的转换转换完成后的格式：（类号、内码）l描述词法规则

12、的有效工具是正规式和有限自动机 语法分析语法分析Parser任务在词法分析的基础上，根据语言的语法规则，将单词符号组成各类的语法单位：短语、子句、语句、过程、程序语法规则：语言的规则：又称为文法：规定单词如何构成短语、语句、过程和程序语法规则的表示：BNF：A:=B|C 例：:=:=l赋值语句的语法规则A:=V=EE:=T|E+TT:=F|T*FF:=V|(E)|CV:=标识符C:=常数例：“id1=id2+id3*10”赋值语句l语法分析的方法推导（derive）和归约（reduce）l推导最左推导、最右推导l归约最左归约、最右归约语句id1=id2+id3*10的语法树赋值语句标识符表达式

13、表达式+表达式表达式标识符整数标识符=表达式*id1id2id310id1=id2+id3*10=+10*id1 id2id3 l例如：(1)任何标识符是表达式。(2)任何常数(整常数、实常数)是表达式。(3)若表达式1和表达式2都是表达式，那么表达式1+表达式2以及表达式1*表达式2都是表达式。依循的规则：语法规则 语义分析语义分析Semantic Analyzer 任务 完成静态语义审查和处理 上下文相关性审查 类型匹配审查 类型转换 例，int arr2,c;c=arr1*10;依循的规则：语义规则例:Program p();Var rate:real;procedure initial

14、;position:=initial +rate*10/*error*/*error*/*warning*/;Program p();Var rate:real;Var initial:real;Var position:real;position:=initial +rate*1010=+*id1 positionid2 initialid3 rateinttoreal 中间代码生成中间代码生成Intermediate Code Generator任务：从源程序的树形或其它形式，产生介于源代码和目标代码之间的一种代码。中间代码：四元式、三元式、逆波兰式例：a=b+c四元式oparg1arg2

15、 result+bcT1=T1al比如：源程序id1=id2+id3*10可生成四元式序列 l四元式(运算符，运算对象1，运算对象2，结果)常写成赋值语句的形式 结果=运算对象1 运算符 运算对象2l比如c语言的源程序a=b*c+b*d 的四元式序列为(1)t1=b*c(2)t2=b*d(3)t3=t1+t2(4)a=t3 代码优化代码优化l任务对前面产生的中间代码进行加工变换，以期在最后阶段能产生更为高效的目标代码l原则：等价变换id1=id2+id3*10(1)(inttoreal10-t1)(2)(*id3t1t2)(3)(+id2t2t3)(4)(=t3-id1)变换变换 （1）(*i

16、d310.0t1)(2）（+id2 t1id1)l主要方面公共子表达式的提取、合并已知量、删除无用语句、循环优化等t1=b*c t1=b*c t2=t1+0 t4=t1+t1t3=b*c a=t4t4=t2+t3a=t4例如将下面的语句转换成中间代码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+

17、10;k+;goto 10;目标代码生成目标代码生成Target Code Generatorl任务将经过优化的中间代码转换成特定机器上的低级语言代码。l目标代码的形式绝对指令代码：可立即执行的目标代码汇编指令代码：汇编语言程序，需要通过汇编程序汇编后才能运行可重定位指令代码：先将各目标模块连接起来，确定变量、常数在主存中的位置，装入主存后才能成为可以运行的绝对指令代码(*,id310.0t1)(+,id2t1id1)movfid3,R2mulf#10.0,R2movfid2,R1addfR2,R1movfR1,id1编译过程概述 表格管理表格管理l表格管理是一个贯穿编译全过程的工作l表格作用

18、：用来记录源程序的各种信息以及编译过程中的各种状况l与编译前四个阶段有关的表格有：符号表、常数表、标号表、分程序入口表、中间代码表等l符号表是最重要的一种表格用来登记源程序中的常量名、变量名、数组名、过程名等，记录它们的性质、定义和引用情况。l常数表与标号表l入口名表作用：登记过程的层号，分程序符号表入口等l中间代码表 出错处理出错处理Error Handlerl任务如果源程序有错误的话，编译程序应设法发现错误，并报告给用户。l完成由专门的出错处理程序来完成l错误类型：语法错误：在词法分析和语法分析阶段检测出来语义错误：一般在语义分析阶段检测在编译时查出的，叫Compile-time erro

19、r，在运行时表现才表现出来的错误叫Run-time error。编译程序结构(components)编译阶段的组合l前端、后端前端、后端l分析、综合分析、综合l遍遍前端和后端前端和后端前端包括编译逻辑结构中的分析部分，即词法分析、语法分析、语义分析和中间代码生成，除此还包括符号表建造及相应分析中的错误处理以及与机器无关的优化部分。后端包括与目标机有关的部分，即综合部分，它包括目标代码生成及生成期间对符号表的相应检索操作和错误处理操作，以及与机器相关的代码优化部分。将编译系统划分为前后端，有利于移植编译系统和利用后端为同一目标机配置不同语言的编译系统。编译阶段的两大步骤分析和综合分析步骤是指对源

20、程序的分析分析步骤是指对源程序的分析线性分析线性分析(词法分析或扫描词法分析或扫描)层次分析层次分析(语法分析语法分析)语义分析语义分析综合步骤是指后端的工作，为目标程序的综合步骤是指后端的工作，为目标程序的生成而进行的综合生成而进行的综合 遍遍(pass)对源程序(或其中间形式)从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。注：遍与阶段的含义毫无关系多遍扫描优点：节省内存空间，提高目标代码质量，使编译的逻辑结构清晰缺点：编译时间较长注：在内存许可情况下，还是遍数尽可能少些一遍扫描（以语法分析为中心）分遍原则目标质量高低(高则多遍)机器内存大小(小则多遍)源语言

21、简繁(繁则多遍)设计人员多少(多则多遍)编译程序生成l直接用机器语言编写编译程序l用汇编语言编写编译程序注：编译程序核心部分常用汇编语言编写源程序源程序目标程序目标程序编译程序编译程序汇编语言程序汇编语言程序 汇编汇编l用高级语言编写编译程序注：这是普遍采用的方法源程序源程序目标程序目标程序编译程序编译程序C语言源程序语言源程序 C语言编译器语言编译器l自编译l编译工具：LEX（词法分析）与YACC（用于自动产生LALR分析表）移植（同种语言的编译程序在不同类型的机器之间移植）编译程序构造l在某机器上为某种语言构造编译程序要掌握以下三方面：源语言目标语言编译方法本章小结l掌握编译程序与高级程序设计语言的关系l掌握编译分为哪几个阶段l了解各个阶段完成的主要功能和采用的主要方法参 考 书l吕映芝等，编译原理，清华大学出版社l陈意云等，编译原理，高等教育出版社l杜淑敏等，编译程序设计原理，北京大学出版社lAlfred V.Aho等，编译原理，机械工业出版社lTerrence W.Pratt,Marvin V.Zelkowitz Programming Languages Design and Implementation,Prentice-Hall 1996