《chnew自顶向下语法分析方法实用.pptx》由会员分享，可在线阅读，更多相关《chnew自顶向下语法分析方法实用.pptx（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 名名 称称 作作 者者 出版社出版社 出版时间出版时间 编译原理编译原理 何炎祥何炎祥 华中理工大学华中理工大学 2000.102000.10 编译原理编译原理 陈火旺等陈火旺等 国防工业出版社国防工业出版社 2000.12000.1 编译原理编译原理 蒋立源蒋立源 西北工业大学西北工业大学 1999.91999.9编译原理（第二版）编译原理（第二版）.张素琴，吕映芝，蒋维杜，戴桂兰编著，清华大学出版社，张素琴，吕映芝，蒋维杜，戴桂兰编著，清华大学出版社，2005.2.教教 材材 与与 参参 考考 书书编译原理及实践第1页/共35页2第一章 编译程序概论主要介绍编译程序的主要介绍编译程序的
2、基本概念基本概念基本概念基本概念、基本结构基本结构基本结构基本结构。1.1 什么是编译程序什么是编译程序1.2 编译过程及编译程序结构编译过程及编译程序结构1.2.1 编译过程编译过程1.2.2 编译程序的基本结构编译程序的基本结构1.3 编译技术和软件工具编译技术和软件工具1.4 程序设计语言范型程序设计语言范型第2页/共35页31.1 什么是编译程序vv翻译程序（翻译程序（翻译程序（翻译程序（translatortranslatortranslatortranslator）vv编译程序编译程序编译程序编译程序（compilercompiler）v源程序的加工过程源程序的加工过程v与编译程序
3、相关的程序与编译程序相关的程序 编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统尤其是嵌入式系统和高性能体系结构都含有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上看，一个编译程序就是一个语言翻译程序。第3页/共35页4源程序源程序源程序源程序翻译程序翻译程序翻译程序翻译程序目标程序目标程序目标程序目标程序翻译程序（translator）翻译程序是指这样一个程序，它把一种语言（源语言源语言）所写的程序（源程序源程序）翻译成与之等价等价的另一种语言（目标语言目标语言）的程序（目标程序目标程序）。n源语言：source languagesourc
4、e languagen源程序：source programsource programn目标语言：object or target languageobject or target languagen目标程序：object or target programobject or target program第4页/共35页5编译程序（编译器compiler）如果源语言是高级语言，目标语言是低级语言，那么称这样的翻译程序为编译编译程序程序。q高级语言：C C、PASCALPASCAL、C+C+、FORTRANFORTRAN、JAVAJAVAq低级语言：汇编语言、机器语言源程序源程序源程序源程序编译
5、程序编译程序编译程序编译程序目标程序目标程序目标程序目标程序高级语言所写程序汇编语言或机器语言程序第5页/共35页6汇编程序（Assembler）如果源语言是汇编语言，目标语言是机器语言，那么称这样的翻译程序为汇编汇编程序程序。源程序源程序源程序源程序汇编程序汇编程序汇编程序汇编程序目标程序目标程序目标程序目标程序汇编语言所写程序机器语言程序第6页/共35页7源程序的加工过程采用编译方式在计算机上执行高级语言编写的程序，一般分两大阶段，编译阶编译阶段段和运行阶段运行阶段。源程序源程序编编译译程程序序机器语言目标程序机器语言目标程序结果结果初始数据初始数据运行系统运行系统第7页/共35页8源程序
6、源程序机器语言机器语言目标程序目标程序结果结果初始数据初始数据运行系统运行系统如果编译阶段生成的目标程序不是机器程序，而是汇编程序，则程序的执行需分三个阶段，编译阶段编译阶段、汇编阶段汇编阶段和运行阶段运行阶段。汇编语言汇编语言目标程序目标程序编编译译程程序序汇汇编编程程序序第8页/共35页9编译程序的发展历史第一个编译程序第一个编译程序FortranFortran编译程序（编译程序（2020世纪世纪5050年代年代）编译程序自动生成工具（编译程序自动生成工具（2020世纪世纪5050年代末年代末）以任一语言的词法规则、语法规则和语义解释出发，自动产生该语言的编以任一语言的词法规则、语法规则和
7、语义解释出发，自动产生该语言的编译程序。译程序。LEXLEX是一个词法分析器的自动产生系统是一个词法分析器的自动产生系统 YACCYACC是一个语法分析程序的自动产生器是一个语法分析程序的自动产生器应用自展技术构造编译程序（应用自展技术构造编译程序（2020世纪世纪6060年代年代）自展技术就是用被编译的语言来书写该语言自身的编译程序。首先对语自展技术就是用被编译的语言来书写该语言自身的编译程序。首先对语言的核心部分构造一个小小的编译程序，再以它为工具构造一个能够编译更言的核心部分构造一个小小的编译程序，再以它为工具构造一个能够编译更多语言成分的较大的编译程序。如此继续下去，最后形成所期望的整
8、个编译多语言成分的较大的编译程序。如此继续下去，最后形成所期望的整个编译程序。这种通过一系列自展途径而形成编译程序的过程，叫做自编译过程。程序。这种通过一系列自展途径而形成编译程序的过程，叫做自编译过程。并行编译技术并行编译技术需进一步研究的问题需进一步研究的问题 处理并行语言的并行编译技术、串行程序转换成并行程序的自动并行编译处理并行语言的并行编译技术、串行程序转换成并行程序的自动并行编译技术等。技术等。第9页/共35页101.2 编译过程和编译程序的结构编译过程是一种语言的翻译过程，它的工作过程类似于外文的翻译过程。【例】英文句子翻译成中文句子的大致过程是：1.词法分析：根据英语的词法规则
9、，从由字母、空格字符和各词法分析：根据英语的词法规则，从由字母、空格字符和各种标点符号所组成的字符串中识别出一个一个的英文单词。种标点符号所组成的字符串中识别出一个一个的英文单词。2.语法分析：根据英语的语法规则，对词法分析后的单词串进语法分析：根据英语的语法规则，对词法分析后的单词串进行分析、识别，并做语法正确性检查，看其是否组成一个符行分析、识别，并做语法正确性检查，看其是否组成一个符合英语语法的句子。合英语语法的句子。3.语义分析：对正确的英文句子分析其含义并用汉语表示出来语义分析：对正确的英文句子分析其含义并用汉语表示出来.4.根据上下文的关系以及汉语语法的有关规则对词句作必要的根据上
10、下文的关系以及汉语语法的有关规则对词句作必要的修饰工作。修饰工作。5.最后翻译成中文。最后翻译成中文。第10页/共35页111.2.1 编译过程概述编译过程一般分为以下六个阶段（与自然语言翻译过程对比）：词法分析语法分析语义分析中间代码生成代码优化目标代码生成第11页/共35页12对于PASCAL程序段begin begin var sum,first,count:real;var sum,first,count:real;sum:=first+count*10 sum:=first+count*10 end.end.通过词法分析，可识别出如下的单词符号序列：基本字:begin,var,rea
11、l,end 标识符:sum,first,count整数：10 界符：。逗号：，冒号：分号：；赋值号：:=加号：+乘号：*机内码为：id1:=id2+id3*101、词法分析（扫描器）v任务：源程序 单词符号串 从左至右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词符号.v依据：语言的词法规则 v描述词法规则的工具：正则式、正则文法、有限自动机第12页/共35页132、语法分析例如：符号串 id1:=id2+id3*10经过语法分析知它代表一个赋值语句.v任务：单词符号串 各类语法单位 在词法分析的基础上将单词序列分解成各类语法短语.通常用语法树表示这种语
12、法短语.v依据：语言的语法规则 v描述语法规则的工具：上下文无关文法、确定的下推自动机第13页/共35页14对应的语法树如下：语句id1:=id2+id3*10的语法树第14页/共35页15定义表达式的规则：定义表达式的规则：1.1.任何标识符是表达式。任何标识符是表达式。2.2.任何常数（整常数、实常数）是表达式。任何常数（整常数、实常数）是表达式。3.3.若表达式若表达式1 1和表达式和表达式2 2都是表达式，那么都是表达式，那么 表达式表达式1+1+表达式表达式2 2 表达式表达式1*1*表达式表达式2 2 （表达式（表达式1 1）都是表达式。都是表达式。程序结构（程序结构（1）程序结构
13、通常采用递归规则表示，也就是用来描述程序结构的规则。程序结构通常采用递归规则表示，也就是用来描述程序结构的规则。例如：定义表达式的规则、定义语句的规则例如：定义表达式的规则、定义语句的规则第15页/共35页16语句的表示：语句的表示：1.标识符标识符标识符标识符:=:=表达式表达式表达式表达式 是语句。是语句。2.while(while(表达式表达式表达式表达式)do)do 语句语句语句语句 和和if(if(表达式表达式表达式表达式)then)then 语句语句语句语句 else else 语句语句语句语句都是语句。都是语句。程序结构（程序结构（2）第16页/共35页173、语义分析（1）语义
14、语义 定义语言的单词符号和语法单位的意义定义语言的单词符号和语法单位的意义.一个语言的语义是指这样的一组一个语言的语义是指这样的一组规则，使用它可以定义一个程序的意义规则，使用它可以定义一个程序的意义.这些规则称为语义规则这些规则称为语义规则.离开语义，语言只不过是一堆符号的集合离开语义，语言只不过是一堆符号的集合.语义分析阶段的主要任务语义分析阶段的主要任务审查源程序有无语义错误，为代码生成阶段收集类型信息审查源程序有无语义错误，为代码生成阶段收集类型信息.第17页/共35页183、语义分析（2）类型审查、数组下标检查、强制类型转换等类型审查、数组下标检查、强制类型转换等例如：例如：增加的语
15、义处理节点，表示整型转换成实型的一目算符语句语句id1:=id2+id3*10id1:=id2+id3*10的语义分析（类型审查）过程：的语义分析（类型审查）过程：第18页/共35页194、中间代码产生序号序号算符算符左操作数左操作数右操作数右操作数结果结果(1)inttoreal10-t1(2)*id3t1t2(3)+id2t2t3(4):=t3-id1v任务任务：语法单位：语法单位 初步翻译、产生中间代码初步翻译、产生中间代码v中间代码中间代码：是一种结构简单含义明确的记号系统：是一种结构简单含义明确的记号系统.例如，四元例如，四元式、三元式、逆波兰式等式、三元式、逆波兰式等.v依据依据：
16、语言的语义规则：语言的语义规则 v设计原则：设计原则：1）容易生成）容易生成2）容易翻译成目标代码）容易翻译成目标代码 在PASCAL语言中，符号串:id1:=id2+id3*10 可产生一种四元式形式的中间代码：第19页/共35页205、代码优化v任务：中间代码 高效的中间代码 对中间代码进行变换或进行改造，以便生成高效的中间代码（省时间和空间）.v依据：等价变换规则 v变换方法：公共子表达式的提取、循环优化、删除无用代码等序号序号算符算符左操作数左操作数右操作数右操作数结果结果(1)*id310.0t1(2)+id2t1id1优化后的中间代码：第20页/共35页216、目标代码生成v任务：
17、中间代码依赖于机器的目标代码（汇编语言或机器语言）v涉及的主要问题：指令的选择内存的分配寄存器的分配目标代码的形式：绝对指令代码汇编指令代码可重定位的指令代码第21页/共35页22(*(*id3id310.010.0t1 )t1 )(+(+id2id2t1t1id1)id1)sum:=first+count*10sum:=first+count*10MOVMOV id3,id3,R R2 2MULMUL#10.0,#10.0,R R2 2MOVMOVid2,id2,R R1 1ADDADDR R1 1,R R2 2MOVMOVR R1 1,id1id1目标代码生成目标代码生成赋值语句中间代码四
18、元式目标代码第22页/共35页231.2.2 编译程序的结构词法分析器词法分析器语法分析器语法分析器语义分析及中间代码生成器语义分析及中间代码生成器优化器优化器目标代码生成器目标代码生成器 出出 错错 处处 理理 程程 序序 表表 格格 管管 理理 程程 序序源程序源程序单词符号单词符号语法单位语法单位中间代码中间代码中间代码中间代码目标代码目标代码1.编译程序总框第23页/共35页242.2.表格与表格管理表格与表格管理用途：登记源程序的各类信息和编译程序各阶段的用途：登记源程序的各类信息和编译程序各阶段的进展情况，如符号表。进展情况，如符号表。管理：构造、查找、或更新。管理：构造、查找、或
19、更新。3.3.出错处理出错处理任务：发现并指出源程序中错误的性质和位置；任务：发现并指出源程序中错误的性质和位置；自动校正错误。自动校正错误。第24页/共35页25遍（pass)pass)：对源程序或源程序的中间结果从头至尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序的处理过程称为一遍。可以把一个阶段分为若干遍，也可以把多个阶段合为一遍，通常有一遍和多遍编译程序。1.2.3 编译阶段的组合第25页/共35页26词法分析语法分析语义分析与中间代码生成优化目标代码生成编译的前端与后端：前端（前端（front endfront endfront endfront end）：由与源语言有关
20、但与目标机无关的部分组成。后端后端（back endback endback endback end）：包括与目标机有关的部分。而一般不依赖于源语言，只与中间代码有关的编译阶段。前端前端 （中间代码）（中间代码）后端后端第26页/共35页27一个语言的解释程序解释程序是这样的程序：它以该语言写的源程序作为输入，但不产生目标程序不产生目标程序，而是边解释边解释边执行边执行源程序本身。-与编译程序相关的程序v解释程序（解释程序（interpreter）v汇编程序（汇编程序（assembler）v连接程序（连接程序（linker）v预处理程序（预处理程序（preprocessor）v编辑器（编辑器（
21、editor）v调试程序（调试程序（debugger）汇编程序是用于特定计算机上的汇编语言汇编语言的翻译程序。有时编译器把汇编语言作为目标语言，然后再由汇编程序将它翻译成目标代码。连接程序将分别在不同的目标文件中编译或汇编的代码收集到一个可直接执行的文件中。在这种情况下，目标代码（即还未被连接的机器代码）与可执行代码的机器代码之间有了区别。连接程序还连接目标程序和用于标准库函数的代码，以及连接目标程序和计算机的操作系统提供的资源(存储分配程序及IO设备)预处理程序是在真正的编译开始之前由编译器调用的独立程序。预处理程序可以删除注释注释、包含包含其它文件其它文件以及执行宏替代宏替代。编译器通常接
22、受由任何生成标准文件（例如ASCII）的编辑器编写的源程序。最近，编译器已与一个编辑器和其它程序捆绑进一个交互的开发环境IDE中。调试程序是可在被编译了的程序中判定执行错误的程序。运行一个带有调试程序的程序与直接执行不同，因为调试程序保存着大多数的源代码信息。1.3.1 编译技术和软件工具编译技术和软件工具第27页/共35页28第28页/共35页291.3.2 编译技术和软件工具（1）开发高质量与高效率的软件遵循的要求：开发高质量与高效率的软件遵循的要求：1 1）软件工程中要求的规范化标准）软件工程中要求的规范化标准2 2）先进的软件开发技术及其软件工具）先进的软件开发技术及其软件工具语言的结
23、构化编辑器语言的结构化编辑器 结构化编辑器是引导用户在语言的语法制导下编制程序，能够自动地提结构化编辑器是引导用户在语言的语法制导下编制程序，能够自动地提供关键字和与其匹配地关键字供关键字和与其匹配地关键字.例如，例如，EditplusEditplus、UltraeditUltraedit、JbuilderJbuilder等等语言程序的调试工具 对算法的错误或程序未能反应算法的功能等错误进行调试对算法的错误或程序未能反应算法的功能等错误进行调试.软件工具开发用到的编译技术与方法：软件工具开发用到的编译技术与方法：第29页/共35页30语言程序的测试工具：语言程序的测试工具：静态分析器与动态测试
24、器静态分析器与动态测试器 静态分析器静态分析器 在不运行程序的情况下对源程序进行静态地分析，在不运行程序的情况下对源程序进行静态地分析，以发现程序中潜在的错误或异常。对源程序进行语以发现程序中潜在的错误或异常。对源程序进行语法分析并制定相应表格，检查变量定值与引用的关法分析并制定相应表格，检查变量定值与引用的关系。系。例如：某变量未被赋值就被引用；变量定值后未被例如：某变量未被赋值就被引用；变量定值后未被引用；多余的源代码等引用；多余的源代码等.1.3.2 编译技术和软件工具（2）第30页/共35页31语言程序的测试工具：语言程序的测试工具：静态分析器与动态测试器静态分析器与动态测试器 动态测
25、试器动态测试器 在源程序的适当位置插入某些信息，在源程序的适当位置插入某些信息，并用测试用例记录（显示语句或函数）程序运行时并用测试用例记录（显示语句或函数）程序运行时的实际路径的实际路径.将运行结果与期望结果进行比较分析，将运行结果与期望结果进行比较分析，帮助编程人员查找问题帮助编程人员查找问题.1.3.2 编译技术和软件工具（3）高级语言之间的转换工具高级语言之间的转换工具程序格式化工具程序格式化工具程序理解工具程序理解工具 对程序进行分析，确定模块间的调用关系，记录程序数对程序进行分析，确定模块间的调用关系，记录程序数据的静态属性和结构属性，并画出控制流程图，帮助用据的静态属性和结构属性
26、，并画出控制流程图，帮助用户理解程序。户理解程序。第31页/共35页32 1.4 程序设计语言范型（程序设计语言范型（1）强制式语言（过程式语言）面面向向动动作作，即即一一个个计计算算过过程程就就是是一一系系列列动动作作，其其动动作作是是命命令令驱驱动动的的，用用语语句句形形式式表表示示.一一个个强强制制式式语语言言程程序序由由一一系系列列的的语语句句组组成，每个语句的执行引起若干存储单元中的值的改变。成，每个语句的执行引起若干存储单元中的值的改变。语法形式为：语法形式为：语句 1 1；语句 2 2；语句 n n；例如：例如：C、FORTRAN、Pascal、C、Ada程序设计语言的分类程序设
27、计语言的分类方法有许多种：应用方法有许多种：应用领域、按照支持的计领域、按照支持的计算模式等算模式等按照支持的计算模式，程序设计语言可以分为：按照支持的计算模式，程序设计语言可以分为：第32页/共35页33函数式语言函数式语言 注重程序所表示的功能，而不是一个语句接一个语句地执行。注重程序所表示的功能，而不是一个语句接一个语句地执行。程序的开发过程是从前面已有的函数出发构造出更复杂的函数，对程序的开发过程是从前面已有的函数出发构造出更复杂的函数，对初始数据集进行操作，直至最后形成的函数可以用于从初始数据计算出初始数据集进行操作，直至最后形成的函数可以用于从初始数据计算出最终结果。最终结果。语法
28、形式为：语法形式为：functionfunctionn n(functionfunction2 2(function(function1 1(data)(data)例如：例如：LISPLISP 1.4 程序设计语言范型（2）第33页/共35页34基于规则（逻辑）的语言基于规则（逻辑）的语言 检查条件，满足时则执行适当的动作。检查条件，满足时则执行适当的动作。语法形式：语法形式：条件条件 1 1 动作动作 1 1 条件条件 2 2 动作动作 2 2 条件条件 n n 动作动作 n n 例如：例如：PROLOGPROLOG面向对象语言面向对象语言 提供抽象数据类型，支持封装性、继承性和多态性提供抽象数据类型，支持封装性、继承性和多态性.例如：例如：AdaAda、C C、JavaJava 1.4 程序设计语言范型（3）第34页/共35页35感谢您的欣赏！第35页/共35页