ch5-new自顶向下语法分析方法.ppt

1、1,任课教师：湛 燕 Email: 数学与计算机学院,编译原理,2,名 称 作 者 出版社 出版时间 编译原理 何炎祥 华中理工大学 2000.10 编译原理 陈火旺等 国防工业出版社 2000.1 编译原理 蒋立源 西北工业大学 1999.9,编译原理（第二版）. 张素琴，吕映芝，蒋维杜，戴桂兰编著，清华大学出版社，2005.2,教 材 与 参 考 书,编译原理及实践,3,第一章 编译程序概论,主要介绍编译程序的基本概念、基本结构,1.1 什么是编译程序 1.2 编译过程及编译程序结构 1.2.1 编译过程 1.2.2 编译程序的基本结构 1.3 编译技术和软件工具 1.4 程序设计语言范型

2、,4,1.1 什么是编译程序,翻译程序（translator） 编译程序（compiler） 源程序的加工过程 与编译程序相关的程序,编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统尤其是嵌入式系统和高性能体系结构都含有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。 从功能上看，一个编译程序就是一个语言翻译程序,5,翻译程序（translator,翻译程序是指这样一个程序，它把一种语言（源语言）所写的程序（源程序）翻译成与之等价的另一种语言（目标语言）的程序（目标程序,源语言：source language 源程序：source program 目标

3、语言：object or target language 目标程序：object or target program,6,编译程序（编译器compiler,如果源语言是高级语言，目标语言是低级语言，那么称这样的翻译程序为编译程序,高级语言：C、PASCAL、C+、FORTRAN、JAVA 低级语言：汇编语言、机器语言,高级语言所写程序,汇编语言或机器语言程序,7,汇编程序（Assembler,如果源语言是汇编语言，目标语言是机器语言，那么称这样的翻译程序为汇编程序,汇编语言所写程序,机器语言程序,8,源程序的加工过程,采用编译方式在计算机上执行高级语言编写的程序，一般分两大阶段，编译阶段和运行

4、阶段,9,源程序,机器语言 目标程序,结果,初始数据,运行系统,如果编译阶段生成的目标程序不是机器程序，而是汇编程序，则程序的执行需分三个阶段，编译阶段、汇编阶段和运行阶段,汇编语言 目标程序,编译程序,汇编程序,10,编译程序的发展历史,第一个编译程序Fortran编译程序（20世纪50年代） 编译程序自动生成工具（20世纪50年代末） 以任一语言的词法规则、语法规则和语义解释出发，自动产生该语言的编译程序。 LEX是一个词法分析器的自动产生系统 YACC是一个语法分析程序的自动产生器 应用自展技术构造编译程序（20世纪60年代） 自展技术就是用被编译的语言来书写该语言自身的编译程序。首先对

5、语 言的核心部分构造一个小小的编译程序，再以它为工具构造一个能够编译更多语言成分的较大的编译程序。如此继续下去，最后形成所期望的整个编译程序。这种通过一系列自展途径而形成编译程序的过程，叫做自编译过程。 并行编译技术需进一步研究的问题 处理并行语言的并行编译技术、串行程序转换成并行程序的自动并行编译技术等,11,1.2 编译过程和编译程序的结构,编译过程是一种语言的翻译过程，它的工作过程类似于外文的翻译过程,例】英文句子翻译成中文句子的大致过程是,词法分析：根据英语的词法规则，从由字母、空格字符和各种标点符号所组成的字符串中识别出一个一个的英文单词。 语法分析：根据英语的语法规则，对词法分析后

6、的单词串进行分析、识别，并做语法正确性检查，看其是否组成一个符合英语语法的句子。 语义分析：对正确的英文句子分析其含义并用汉语表示出来. 根据上下文的关系以及汉语语法的有关规则对词句作必要的修饰工作。 最后翻译成中文,12,1.2.1 编译过程概述,编译过程一般分为以下六个阶段（与自然语言翻译过程对比,词法分析 语法分析 语义分析 中间代码生成 代码优化 目标代码生成,13,对于PASCAL程序段 begin var sum,first,count:real; sum:=first+count*10 end. 通过词法分析，可识别出如下的单词符号序列： 基本字: begin,var,real,

7、end 标识符:sum,first,count 整数：10 界符：。 逗号：， 冒号： 分号：； 赋值号：:= 加号：+ 乘号：* 机内码为：id1:=id2+id3*10,1、词法分析（扫描器,任务：源程序 单词符号串 从左至右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词符号. 依据：语言的词法规则 描述词法规则的工具：正则式、正则文法、有限自动机,14,2、语法分析,例如：符号串 id1:=id2+id3*10 经过语法分析知它代表一个赋值语句,任务：单词符号串 各类语法单位 在词法分析的基础上将单词序列分解成各类语法短语.通常用语法树表示这种语法

8、短语. 依据：语言的语法规则 描述语法规则的工具：上下文无关文法、确定的下推自动机,15,对应的语法树如下,语句id1:=id2+id3*10的语法树,16,定义表达式的规则： 任何标识符是表达式。 任何常数（整常数、实常数）是表达式。 若表达式1和表达式2都是表达式，那么 表达式1+表达式2 表达式1*表达式2 （表达式1）都是表达式,程序结构（1,程序结构通常采用递归规则表示，也就是用来描述程序结构的规则,例如：定义表达式的规则、定义语句的规则,17,语句的表示： 标识符:=表达式 是语句。 while (表达式) do 语句 和if (表达式) then 语句 else 语句都是语句,程

9、序结构（2,18,3、语义分析（1,语义 定义语言的单词符号和语法单位的意义.一个语言的语义是指这样的一组规则，使用它可以定义一个程序的意义.这些规则称为语义规则. 离开语义，语言只不过是一堆符号的集合,语义分析阶段的主要任务 审查源程序有无语义错误，为代码生成阶段收集类型信息,19,3、语义分析（2,类型审查、数组下标检查、强制类型转换等,例如,增加的语义处理节点，表示整型转换成实型的一目算符,语句id1:=id2+id3*10的语义分析（类型审查）过程,20,4、中间代码产生,任务：语法单位 初步翻译、产生中间代码 中间代码：是一种结构简单含义明确的记号系统.例如，四元式、三元式、逆波兰式

10、等. 依据：语言的语义规则 设计原则：1）容易生成2）容易翻译成目标代码,在PASCAL语言中，符号串: id1:=id2+id3*10 可产生一种四元式形式的中间代码,21,5、代码优化,任务：中间代码 高效的中间代码 对中间代码进行变换或进行改造，以便生成高效的中间代码（省时间和空间）. 依据：等价变换规则 变换方法：公共子表达式的提取、循环优化、删除无用代码等,优化后的中间代码,22,6、目标代码生成,任务：中间代码依赖于机器的目标代码（汇编语言或机器语言） 涉及的主要问题： 指令的选择 内存的分配 寄存器的分配 目标代码的形式： 绝对指令代码 汇编指令代码 可重定位的指令代码,23,*

11、id310.0t1 ) ( +id2t1id1,sum := first + count * 10,MOV id3,R2 MUL#10.0,R2 MOVid2,R1 ADDR1,R2 MOVR1,id1,目标代码生成,赋值语句,中间代码四元式,目标代码,24,1.2.2 编译程序的结构,词法分析器,语法分析器,语义分析及中间代码生成器,优化器,目标代码生成器,出 错 处 理 程 序,表 格 管 理 程 序,源程序,单词符号,语法单位,中间代码,中间代码,目标代码,编译程序总框,25,表格与表格管理用途：登记源程序的各类信息和编译程序各阶段的进展情况，如符号表。管理：构造、查找、或更新。 出错处

12、理任务：发现并指出源程序中错误的性质和位置； 自动校正错误,26,遍（pass)：对源程序或源程序的中间结果从头至尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序的处理过程称为一遍。可以把一个阶段分为若干遍，也可以把多个阶段合为一遍，通常有一遍和多遍编译程序,1.2.3 编译阶段的组合,27,词法分析语法分析语义分析与中间代码生成优化目标代码生成,编译的前端与后端：前端（front end） ：由与源语言有关但与目标机无关的部分组成。后端（back end） ：包括与目标机有关的部分。而一般不依赖于源语言，只与中间代码有关的编译阶段,前端 （中间代码） 后端,28,一个语言的解释程序

13、是这样的程序： 它以该语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身,与编译程序相关的程序,解释程序（interpreter） 汇编程序（assembler） 连接程序（linker） 预处理程序（preprocessor） 编辑器（editor） 调试程序（debugger,汇编程序是用于特定计算机上的汇编语言的翻译程序。 有时编译器把汇编语言作为目标语言，然后再由汇编程序将它翻译成目标代码,连接程序将分别在不同的目标文件中编译或汇编的代码收集到一个可直接执行的文件中。 在这种情况下，目标代码（即还未被连接的机器代码）与可执行代码的机器代码之间有了区别。 连接程序还连接

14、目标程序和用于标准库函数的代码，以及连接目标程序和计算机的操作系统提供的资源(存储分配程序及IO设备,预处理程序是在真正的编译开始之前由编译器调用的独立程序。 预处理程序可以删除注释、包含其它文件以及执行宏替代,编译器通常接受由任何生成标准文件（例如ASCII）的编辑器编写的源程序。最近，编译器已与一个编辑器和其它程序捆绑进一个交互的开发环境IDE中,调试程序是可在被编译了的程序中判定执行错误的程序。 运行一个带有调试程序的程序与直接执行不同，因为调试程序保存着大多数的源代码信息,1.3.1 编译技术和软件工具,29,30,1.3.2 编译技术和软件工具（1,开发高质量与高效率的软件遵循的要求

15、： 1）软件工程中要求的规范化标准 2）先进的软件开发技术及其软件工具,语言的结构化编辑器 结构化编辑器是引导用户在语言的语法制导下编制程序，能够自动地提供关键字和与其匹配地关键字.例如，Editplus、Ultraedit、Jbuilder等,语言程序的调试工具 对算法的错误或程序未能反应算法的功能等错误进行调试,软件工具开发用到的编译技术与方法,31,语言程序的测试工具：静态分析器与动态测试器 静态分析器 在不运行程序的情况下对源程序进行静态地分析，以发现程序中潜在的错误或异常。对源程序进行语法分析并制定相应表格，检查变量定值与引用的关系。 例如：某变量未被赋值就被引用；变量定值后未被引用

16、；多余的源代码等,1.3.2 编译技术和软件工具（2,32,语言程序的测试工具：静态分析器与动态测试器 动态测试器 在源程序的适当位置插入某些信息，并用测试用例记录（显示语句或函数）程序运行时的实际路径.将运行结果与期望结果进行比较分析，帮助编程人员查找问题,1.3.2 编译技术和软件工具（3,高级语言之间的转换工具 程序格式化工具 程序理解工具 对程序进行分析，确定模块间的调用关系，记录程序数据的静态属性和结构属性，并画出控制流程图，帮助用户理解程序,33,1.4 程序设计语言范型（1,强制式语言（过程式语言） 面向动作，即一个计算过程就是一系列动作，其动作是命令驱动的，用语句形式表示.一个强制式语言程序由一系列的语句组成，每个语句的执行引起若干存储单元中的值的改变。 语法形式为： 语句 1； 语句 2； 语句 n； 例如：C、FORTRAN、Pascal、C、Ada,程序设计语言的分类方法有许多种：应用领域、按照支持的计算模式等,按照支持的计算模式，程序设计语言可以分为,34,函数式语言 注重程序所表示的功能，而不是一个语句接一个语句地执行。 程序的开发过