《编译程序概论》PPT课件.ppt

1、编译原理,主讲老师：陈倩 Email: QQ:10493263 办公室：8A405 Phone课程介绍,课程内容 介绍编译器构造的一般原理和基本实现方法 介绍的理论知识：形式语言和自动机理论、语法制导的定义和属性文法等。 强调形式化描述技术。 强调对编译原理和技术的宏观理解，不把注意力分散到枝节算法，不偏向于某种源语言或目标机器。,课程介绍,学习目的 了解编译程序的实现原理和技术。 利用从本课程学习到的知识，增强编写和调试程序的能力。 学习的意义 对编程语言的设计和实现有深刻的理解，对和编程语言有关的理论（形式语言和自动机理论、类型论等）有所了解，对宏观上把握编程语言

2、来说，起一个奠基的作用。 从软件工程看，编译器是一个很好的实例，所介绍的概念和技术能应用到一般的软件设计之中。本课程的学习有助于提高对这些语言的设计水平。 大多数程序员同时是简单语言的设计者，有助于提高对这些语言的设计水平。 在软件逆向工程、程序理解和软件安全等方面有着广泛的应用。,教材和参考书,教材： 编译原理， 清华大学出版社，张素琴、吕映芝等编著。 参考书： 编译原理，陈火旺，国防工业出版社 编译原理及实践，Louden, K.C. 冯博琴，冯岚等译； 机械工业出版社 编译原理和技术， 陈意云 ， 中国科技大学出版社 编译原理，蒋立源，康慕宁主编； 西北工业大学出版社 相关习题解答,成绩

3、考核方法,平时成绩30 期末成绩70 平时成绩 出勤率10 作业10 实验成绩10,第一讲 引论,什么是编译程序 编译过程和编译程序的结构 解释程序和一些软件工具 程序设计语言范型,什么是编译程序?,语言翻译程序：把一种语言（源语言）书写的程序翻译成另一种等价的语言（目标语言）程序。 优点：计算机用户可以不用考虑与机器有关的烦琐细节，使程序员和程序设计专家独立于机器。,程序设计语言的典型处理过程,编译技术的历史,20世纪50年代早期：算术公式翻译成机器代码。 20世界50年代中期：FORTRAN等一批高级语言的出现。 20世纪50年代末：编译程序的自动生成工具。,编译程序从输入源程序到输出目标

4、程序，可由下面几个部分来组成：,源程序,词法分析器,语法分析器,语义分析器,中间代码生成,代码优化,目标代码生成器,目标代码,表格管理,出错处理,分析,综合,编译过程和编译程序的结构,编译过程概述：词法分析,输入源程序，对构成源程序的字符串从左到右一个字符一个字符地进行扫描和分解，依据词法规则(或构词规则)识别出一个个的单词(单词符号或符号)，转换成机器容易识别的内码形式。 单词：逻辑上紧密相连的一组字符，具有集体含义 内码用二元式(种别码，属性值)表示。 输入：字符串 输出：(种别码，属性值)序对 属性值单词的机内表示 是最初级的语法分析,int x,a,b; x=a+b*50;,结果：内码

5、用二元式(种别码，属性值)表示 （保留字 int） （标识符 x） （界限符 ,） （标识符 a） （界限符 ,） （标识符 b） （界限符 ; ) （标识符 x ） （运算符 = ) ( 标识符 a ) ( 运算符 + ) ( 标识符 b ) ( 运算符 * ) ( 整常数 50 ) ( 界限符 ；),单词种类： 一类是特殊的单词，如保留字、运算符、分界符等，这些都是源语言所提供的； 另一类是普通单词，如用户在源程序中定义的标识符、常数等。,编译过程概述：语法分析,根据语言的语法规则(文法规则)，把单词符号串组成各类语法单位(语法范畴)，如：表达式、语句、分程序、程序等。 输入：单词序列 输

6、出：语法单位 语法规则写成Backus-Naur-Form(BNF)式，形式如下： A:=B|C或AB|C 语法分析有两种方法： 推导(Derive)和归约(Reduce) 语法分析对说明语句填写符号表，一般语句构造 语法树,语法树： 叶子:各个单词。 内部结点:语法构造名。,注:id1,id2,id3为a,b,c的内部表示。,例如：赋值语句a=b+c*10经语法分析生成语法树,赋值语句a=b+c*10语法树的另一种形式,编译过程概述：语义分析,语义分析：审查源程序有无语义错误，为代码生成阶段收集类型信息。 任务： 分析语法成分的含义和用途， 应进行的运算和操作， 同时进行相应的语义检查。 如

7、：在说明语句中是否有矛盾的类型说明。 表达式中，类型不匹配。 过程调用中，实参和形参的配合。 依据：语义规则。,赋值语句a=b+c*10经语义分析生成语法树（考虑类型问题：a,b,c为实型）,编译过程概述：中间代码生成,根据语义规则产生一种介于源语言与目标代码之间的一种中间代码。 中间代码是不依赖于机器但是又便于生成依赖于机器的目标代码的一种结构简单、含义明确的记号系统。 中间代码的特点 简单规范 机器无关 易于优化与转换,中间代码生成例子： 四元式（运算符，运算对象1，运算对象2，结果） 例：a=b+c*10,常用的中间代码出了四元式外，还有三元式、间接三元式和逆波兰记号等等。,编译过程概述

8、：代码优化,对前阶段产生的中间代码进行加工变换，以期在最后阶段能产生更为高效(省时间和空间)的目标代码。 主要依据是等价变换规则 优化主要包括： 删除公共子表达式、合并已知量、删除无用赋值、循环优化、算符规约等等,t1 :=id3* 10.0 id1:=id3+t1,赋值语句a:=b+c*10优化,t1:=inttoreal(10); t2:=id3 * t1; t3:=id2 +t2; id1 :=t3;,编译过程概述：目标代码生成,把中间代码变换成指定机器上的绝对指令代码或可重新定位的指令代码或汇编指令代码 与硬件系统功能部件的运用，机器指令的选择，各种数据类型变量的存储空间分配，寄存器和

9、后援缓冲寄存器的调度等等有很大的关系,t1 :=id3 * 10.0 id1 := id2+t1,生成目标代码,movf id3 , r2 ; mulf #10.0 , r2 ; movf id2 , r1 ; addf r2 , r1 ; movf r1 , id1 ;,编译过程概述：表格与表格管理,编译程序在工作过程中需要保持一系列的表格，用以登记源程序的各类信息和编译各阶段的进展状况。 合理的设计和使用表格是编译程序构造的一个重要问题。 与编译的头三个阶段有关的表格有： 符号表、常数表、标号表、分程序入口表、中间代码表、过程引用表、循环特征表、等价名表、公用链表、格式表 表格的结构大体如

10、下：,编译过程概述：出错处理,错误可发生在编译的各个阶段，错误处理也是贯穿编译全过程。 词法：拼写 语法：语句结构、表达式结构 语义：类型不匹配 在编译时查出的，叫Comple-time error，在运行时表现才表现出来的错误叫Run-time error。,编译程序结构框图,编译阶段的组合,前端包括编译逻辑结构中的分析部分，即词法分析、语法分析、语义分析和中间代码生成，除此还包括符号表建造及相应分析中的错误处理以及与机器无关的优化部分。 后端包括与目标机有关的部分，即综合部分，它包括目标代码生成及生成期间对符号表的相应检索操作和错误处理操作，以及与机器相关的代码优化部分。 将编译系统划分为

11、前后端，有利于移植编译系统和利用后端为同一目标机配置不同语言的编译系统。,遍(Pass) 对源程序(或其中间形式)从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。其基本形式如下：,分遍原则 目标质量高低(高则多遍)机器内存大小(小则多遍)源语言简繁(繁则多遍)设计人员多少(多则多遍),把前端组织成一遍扫描,把前端组织成多遍扫描,多遍：上一遍的输出是下一遍的输入。,解释程序和一些软件工具,编译：高级语言翻译成二进制代码后，再运行 解释程序：解释程序是一种语言翻译程序，读入一条语句，解释一条语句，执行一条语句，边读入边执行。 Basic，lisp，SQL，Unix命令

12、语言（shell），Java的ByteCode,编译程序和解释程序的不同工作模式, b:=2; a:=b+2; write a; ,编译程序,解释程序,MOV #2.0 R1 MOV R1 b MOV b R2 ADD R1 R2 MOV R1 a,直接将4的值 输出（显示）,生成代码,编译阶段和运行阶段的存储区内容,解释程序的存储区内容,处理源程序的软件工具,语法制导的结构化编辑器 除了通常的正文编辑和修改功能外，还能对源程序进行语法分析。 程序格式化工具 用更加清晰可读的格式排版程序，如缩进，格式，注释使用专门字体等。 程序理解工具 对程序进行分析，确定模块间的调用关系，程序数据的静态属性

13、和结构属性，变量的交叉引用，程序的控制流程图等，以帮助用户理解程序。 语言调试工具 允许用户使用源程序正文和它的符号来调试，即一行一行的跟踪程序，查看变量和数据结构的变化以进行调试工作。,处理源程序的软件工具,调度软件测试工具 包括静态分析器和动态结构测试器。 静态分析器不运行程序而对程序中的潜在错误和异常进行检查。 动态分析器用一组测试数据实际执行程序，记录并分析执行路径，再与预期结果进行比较，以发现程序中的异常。 高级语言的翻译工具 一种高级语言译为另一种高级语言 数据库系统查询 脚本语言 置标语言(HTML.XML),程序设计语言范型,强制（命令）式语言（imperative language） 过程式语言（C，Fortran ，Pascal） 特点： 面向动作，一个计算过程看作是一系列动作 程序由一系列的语句组成 语句1； 语句2； 语句3； 强制性语言执行的解释与冯.诺伊曼机的体系结构相对应：顺序执行指令，通过机器状态（内存、各种寄存器和外存的内容）的改变理解指令执行的含义,程序设计语言范型,函数式语言（function language） 注重程序所