编译原理及其习题解答课件cha.ppt

《编译原理及其习题解答课件cha.ppt》由会员分享，可在线阅读，更多相关《编译原理及其习题解答课件cha.ppt（131页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理compilers principlesn学时安排上课：48学时（112周）实验：12学时（510周 周一下午）1课程内容n第一章 引论n第二章 形式语言概论n第三章 有穷自动机n第四章 词法分析n第五章 自上而下语法分析n第六章 自下而上分析和优先分析方法n第七章 自下而上的LR(k)分析方法n第八章 语法制导翻译 n代码优化 2成绩：n平时n实验n期中考查n期末考试3与课程有关的问题：n本课程的性质、目的和任务：本课程是计算机类专业的专业课，目的是使学生了解并掌握编译程序的基本理论和方法，具有分析和实现编译程序的初步能力。n本课程的基本要求 ：通过对本课程的学习，对形式语言有初步了

2、解，对编译程序的整个结构有较清楚的了解，熟悉和掌握几种主要编译方法。n课程内容的重点、深度与广度：文法和形式语言、词法分析和有穷自动机、语法分析语义分析、目标代码的生成，了解符号表的构造、存储分配与管理、代码优化和错误校正(学时所限。)41.课前预习，课后复习2.实践出真知3.力求两境界，克服一状态n境界一：原理理解马马乎乎、做题顺手n境界二：基本掌握编译原理的设计、做题讲究技巧n一状态：听课稀里糊涂、课后与己无关5参考书：n编译原理教程编译原理教程 胡元义胡元义等西安电子科大等西安电子科大n程序设计语言编译原理陈火旺、刘春林等程序设计语言编译原理陈火旺、刘春林等 国防工业出版社国防工业出版社

3、n编译原理编译原理 吕映芝等吕映芝等 清华出版社清华出版社nKenneth C Louden Compiler Construction Principles and Practice 编译原理与实践编译原理与实践,PWS Publishing Company,1997。中译本。中译本 机械工业出版社机械工业出版社 nAlfred V.Aho,Monica S.Lam,Ravi Sethi,Jeffrey D.UllmanCompilers:Principles,Techniques,and Tools(2nd Edition),Addison Wesley,2006(Dragon book，

4、龙书，龙书)nAndrew W.Appel Modern Compiler Implementation in Java,CambridgeUniversity Press,2002.2nd Ed.(Tiger Book，虎书，虎书)nMichael L.Scott Programming Language Pragmatics,Second Edition,Morgan Kaufmann,2005.(中译本中译本:程序设计程序设计语言：实践之路语言：实践之路裘宗燕，电子工业出版社裘宗燕，电子工业出版社)6第一章 引 论本节内容：n程序的翻译n编译程序的工作过程n编译程序的结构n编译程序的组织

5、方式n编译程序的构造7编译程序在计算机系统中的位置n分类软件系统软件语言处理系统操作系统编译系统裸机81.1 程序的翻译程序的翻译n1.1.1 程序设计语言程序设计语言机器语言机器语言 001110010010汇编语言汇编语言 add R1 2高级语言高级语言 begin x:=9+2 endn问题问题:计算机只能识别二进制数计算机只能识别二进制数0、1表示的表示的指令和数构成的本计算机系统的机器指令和数构成的本计算机系统的机器语言。如何让计算机执行高级语言程语言。如何让计算机执行高级语言程序呢？序呢？91.1 程序的翻译程序的翻译n1.1.2 翻译程序翻译程序 所谓翻译程序，是指这样一种程所

6、谓翻译程序，是指这样一种程序，它能将用甲语言（源语言）编写序，它能将用甲语言（源语言）编写的程序翻译成与之等价的用乙语言的程序翻译成与之等价的用乙语言（目标语言）书写的程序。（目标语言）书写的程序。n 程序的翻译通常有两种方式：一是程序的翻译通常有两种方式：一是“编译编译”方式，二是方式，二是“解释解释”方式。方式。101.1 程序的翻译程序的翻译n1.1.3 编译方式编译方式 一种分阶段进行的方式一种分阶段进行的方式1.翻译阶段：翻译阶段：高级语言或汇编语言源程序高级语言或汇编语言源程序 机器语言目标机器语言目标程序程序2.运行阶段运行阶段目标程序、运行子程序、数据目标程序、运行子程序、数据

7、 运行结果运行结果111.1 程序的翻译程序的翻译3.编译方式的特点编译方式的特点n在编译方式下，源程序的执行需要分阶段。在编译方式下，源程序的执行需要分阶段。如果目标程序是机器语言程序，如果目标程序是机器语言程序，则源程序的执则源程序的执行分为两大阶段：编译阶段和运行阶段。行分为两大阶段：编译阶段和运行阶段。如果目标程序是汇编语言程序，如果目标程序是汇编语言程序，则源程序的执则源程序的执行分为三大阶段：编译阶段、汇编阶段和运行行分为三大阶段：编译阶段、汇编阶段和运行阶段。阶段。n编译方式下，生成了目标代码，且可多次执行。编译方式下，生成了目标代码，且可多次执行。121.1 程序的翻译程序的翻

8、译4.关于编译程序的几点说明关于编译程序的几点说明编译程序生成的目标程序不一定是机器语言的编译程序生成的目标程序不一定是机器语言的程序，也有可能是汇编语言程序；程序，也有可能是汇编语言程序；编译程序编译程序与具体的机器和语言有关与具体的机器和语言有关，即任何一，即任何一个具体的编译程序都是某一特定类型的计算机个具体的编译程序都是某一特定类型的计算机系统中关于某一特定语言的编译程序；系统中关于某一特定语言的编译程序；对编译程序而言，源程序是输入数据，目标程对编译程序而言，源程序是输入数据，目标程序是输出结果。序是输出结果。131.1 程序的翻译程序的翻译n1.1.4 解释方式解释方式 完成解释工

9、作的解释程序将按源程序中语完成解释工作的解释程序将按源程序中语句的动态顺序，逐句地进行分析解释，并立即句的动态顺序，逐句地进行分析解释，并立即予以执行。予以执行。执行历程为：执行历程为：141.1 程序的翻译程序的翻译n源程序解释执行的历程源程序解释执行的历程 源程序源程序（高级语言）、初始数据（高级语言）、初始数据 解解释程序程序计计 算算 结结 果果n在解释方式下，并不生成目标代码，而在解释方式下，并不生成目标代码，而是直接执行源程序本身。这是编译方式是直接执行源程序本身。这是编译方式与解释方式的根本区别。与解释方式的根本区别。151.2 编译程序的工作过程编译程序的工作过程 n词法分析词

10、法分析n语法分析语法分析n语义分析和中间代码生成语义分析和中间代码生成n中间代码优化中间代码优化n目标代码生成目标代码生成161.2 编译程序的工作过程编译程序的工作过程 n1.2.1 词法分析词法分析 依据语言词法规则，分析由字符组成的源依据语言词法规则，分析由字符组成的源程序，把它识别为一个一个具有独立意义的最程序，把它识别为一个一个具有独立意义的最小语法单位，即小语法单位，即“单词单词”，并识别出与其相关，并识别出与其相关的属性的属性(如是标识符，是界限符，还是数，等如是标识符，是界限符，还是数，等等等)，再转换成长度上统一的标准形式，再转换成长度上统一的标准形式(这种统这种统一的标准形

11、式既刻画了单词本身，又刻画了它一的标准形式既刻画了单词本身，又刻画了它所具有的属性，称为属性字所具有的属性，称为属性字)，以供其它部分，以供其它部分使用。使用。17词法分析n读字符流的源程序、识别单词例：position =initial +rate *6018词法分析单词类型单词类型单词值单词值 标识符1(id1)position算符(赋值)=标识符2(id2)initial 算符(加)+标识符3(id3)rate 算符(乘)*整数 60 分号 ；191.2 编译程序的工作过程编译程序的工作过程 n1.2.2 语法分析语法分析 依据语法规则，逐一分析词法分析时得到依据语法规则，逐一分析词法分

12、析时得到的单词，把单词串分解成各类语法单位，即确的单词，把单词串分解成各类语法单位，即确定它们是怎样组成说明和语句，以及说明和语定它们是怎样组成说明和语句，以及说明和语句又是怎样组成程序的。分析时如发现有不合句又是怎样组成程序的。分析时如发现有不合语法规则的地方，便将出错的位置及出错性质语法规则的地方，便将出错的位置及出错性质打印报告给程序员；如无语法错误，则用另一打印报告给程序员；如无语法错误，则用另一种中间形式给出正确的语法结构，供下一阶段种中间形式给出正确的语法结构，供下一阶段分析使用。分析使用。20语法分析n功能:层次分析,把源程序的单词序列组成语法短语(表示成语法树).例:=“=”:

13、=“+”:=“*”:=“(”“)”:=:=:=21n 赋值语句标识符表达式表达式+表达式表达式标识符常数标识符=表达式*22语法分析id1=id2+id3*N=+N 60*Id1 PositionId2 initialId3 rate231.2 编译程序的工作过程编译程序的工作过程 n1.2.3 语义分析语义分析 依据语言的语义规则对语法分析得到的语依据语言的语义规则对语法分析得到的语法结构进行静态语义检查法结构进行静态语义检查(确定类型、类型和确定类型、类型和运算合法性检查、识别含义与相应的语义处理运算合法性检查、识别含义与相应的语义处理及其它一些静态语义检查及其它一些静态语义检查)，并用另

14、一种内部，并用另一种内部形式表示出来，或者直接用目标语言表示出来。形式表示出来，或者直接用目标语言表示出来。凡在编译时可以确定的内容称为凡在编译时可以确定的内容称为“静态静态”的；凡必须推迟到程序运行时才能确定的内容的；凡必须推迟到程序运行时才能确定的内容称为称为“动态动态”的。的。24语义分析n语义审查(静态语义)上下文相关性类型匹配类型转换例:Program p();Var rate:real;procedure initial;position:=initial +rate*60/*error*/*error*/*warning*/;25Program p();Var rate:real

15、;Var initial:real;Var position:real;position:=initial +rate*60 26语义分析60:=+*Id1 positionId2 initialId3 rateinttoreal27中间代码生成n源程序的内部(中间)表示三元式、四元式、P-Code、C-Code、U-Code、bytecode28中间代码生成id1=id2+id3*60(1)(inttoreal,60-t1)(2)(*,id3t1t2)(3)(+,id2t2t3)(4)(=,t3-id1)291.2 编译程序的工作过程编译程序的工作过程 n1.2.4 代码优化代码优化 依据程

16、序的等价变换规则，尽量压缩目标依据程序的等价变换规则，尽量压缩目标程序运行所需的时间和所占的存储空间，以提程序运行所需的时间和所占的存储空间，以提高目标程序的质量。高目标程序的质量。30代码优化id1=id2+id3*60(1)(inttoreal60-t1)(2)(*id3t1t2)(3)(+id2t2t3)(4)(:=t3-id1)变换变换 （1）(*id360.0t1)(2）（+id2 t1id1)311.2 编译程序的工作过程编译程序的工作过程 n1.2.5 代码生成代码生成 如果语义分析时把源程序表示成中间形式如果语义分析时把源程序表示成中间形式而不是表示成目标指令，则由本部分完成从

17、中而不是表示成目标指令，则由本部分完成从中间形式到目标指令的转换。如果语义分析时，间形式到目标指令的转换。如果语义分析时，已直接生成目标指令，则无需另外再做代码生已直接生成目标指令，则无需另外再做代码生成工作。成工作。目标指令可能是绝对指令代码，或可重新目标指令可能是绝对指令代码，或可重新定位的指令代码或汇编指令代码。该阶段的工定位的指令代码或汇编指令代码。该阶段的工作有赖于硬件系统结构和机器指令含义。作有赖于硬件系统结构和机器指令含义。32目标代码生成(*,id360.0t1)(+,id2t1id1)movfid3,R2mulf#60.0,R2movfid2,R1addfR2,R1movfR

18、1,id1331.2 编译程序的工作过程编译程序的工作过程 n1.2.6 表格管理表格管理 登记源程序中出现的每个名字以及名字的登记源程序中出现的每个名字以及名字的各种属性。有些名字的属性需要在各个阶段才各种属性。有些名字的属性需要在各个阶段才能填入。能填入。34符号表管理n记录源程序中使用的名字n收集每个名字的各种属性信息类型、作用域、分配存储信息Const1常量值：35Var1变量类型：实层次：2351.2 编译程序的工作过程编译程序的工作过程 n1.2.7 出错处理出错处理 源程序中的错误有语法错误和语义错误两种。源程序中的错误有语法错误和语义错误两种。1.语法错误：源程序中不符合语法语

19、法错误：源程序中不符合语法(或词法或词法)规则规则的错误，它们可在词法分析或语法分析时检测的错误，它们可在词法分析或语法分析时检测出来。出来。2.语义错误：源程序中不符合语义规则的错误，语义错误：源程序中不符合语义规则的错误，一般在语义分析时检测出来，有的语义错误要一般在语义分析时检测出来，有的语义错误要在运行时才能检测出来。通常包括：说明错误、在运行时才能检测出来。通常包括：说明错误、作用域错误、类型不一致等等作用域错误、类型不一致等等36出错处理n检查错误、报告出错信息、排错、恢复编译工作371.3 编译程序的结构编译程序的结构 出错处理语法分析程序语义分析程序目标代码生成程序词法分析程序

20、中间代码生成程序代码优化程序表格管理381.3 编译程序的结构编译程序的结构 391.4 编译程序的组织形式编译程序的组织形式 n1.4.1 遍遍(趟，趟程趟，趟程)所谓一趟或一遍是指一个编译程序在编译所谓一趟或一遍是指一个编译程序在编译时刻把源程序或源程序的等价物时刻把源程序或源程序的等价物(中间程序中间程序)从从头到尾扫描一遍并转换成另一紧邻的等价物的头到尾扫描一遍并转换成另一紧邻的等价物的全过程。全过程。根据编译程序在完成翻译任务的过程中需根据编译程序在完成翻译任务的过程中需要对源程序或其中间等价物扫描的遍数，可以要对源程序或其中间等价物扫描的遍数，可以把编译程序分为单遍扫描的编译程序把

21、编译程序分为单遍扫描的编译程序(只需扫只需扫描一遍描一遍)和多遍扫描的编译程序和多遍扫描的编译程序(需扫描多遍需扫描多遍)。40单遍扫描的编译程序单遍扫描的编译程序411.4 编译程序的组织形式编译程序的组织形式 n1.4.2 编译的前端和后端编译的前端和后端 前端主要由与源语言有关但与目标机器无关的那些前端主要由与源语言有关但与目标机器无关的那些部分组成，如词法分析、语法分析、语义分析与中间代部分组成，如词法分析、语法分析、语义分析与中间代码生成及部分代码优化工作。码生成及部分代码优化工作。后端主要包括编译中与目标机器有关的那些部分，后端主要包括编译中与目标机器有关的那些部分，如与目标机有关

22、的代码优化和目标代码生成等。后端不如与目标机有关的代码优化和目标代码生成等。后端不依赖于源语言而仅依赖于中间语言。依赖于源语言而仅依赖于中间语言。n可以通过改变编译程序的后端来实现编译程序的移植。可以通过改变编译程序的后端来实现编译程序的移植。421.5 编译程序的构造编译程序的构造n 1.5.1 高级语言的自编译性高级语言的自编译性构造编译程序可以用机器言语、汇编语言构造编译程序可以用机器言语、汇编语言和高级语言。和高级语言。高级语言的自编译性：一个语言可以用来高级语言的自编译性：一个语言可以用来编写自己的编译程序。编写自己的编译程序。431.5 编译程序的构造编译程序的构造n 1.5.2

23、编译的自展技术编译的自展技术通过一系列自展途径而形成编译程序通过一系列自展途径而形成编译程序的过程。的过程。先对语言的核心部分构造一个小小编译程先对语言的核心部分构造一个小小编译程序序(可用低级语言实现可用低级语言实现)，再以它为工具构造一，再以它为工具构造一个能够编译更多语言成分的较大编译程序。如个能够编译更多语言成分的较大编译程序。如此扩展下去，越滚越大，最后形成所期望的整此扩展下去，越滚越大，最后形成所期望的整个编译程序。个编译程序。441.5 编译程序的构造编译程序的构造n 1.5.3 编译的自展技术编译的自展技术将一个机器（宿主机）上的一个具有将一个机器（宿主机）上的一个具有自编译性

24、的高级语言编译程序移植到另一个机自编译性的高级语言编译程序移植到另一个机器（目标机）上。器（目标机）上。利用利用A机器上的高级语言机器上的高级语言L编写能在编写能在B机器机器上运行的高级语言上运行的高级语言L的编译程序。的编译程序。如图：如图：451.5 编译程序的构造编译程序的构造n 1.5.3 编译的自展技术编译的自展技术将一个机器（宿主机）上的一个具有自编译性的高将一个机器（宿主机）上的一个具有自编译性的高级语言编译程序移植到另一个机器（目标机）上。级语言编译程序移植到另一个机器（目标机）上。利用利用A机器上的高级语言机器上的高级语言L编写能在编写能在B机器上运行的高级机器上运行的高级语

25、言语言L的编译程序。的编译程序。46第第1章内容小结章内容小结n 什么是编译程序什么是编译程序n 编译方式的特点编译方式的特点n 解释方式的特点解释方式的特点n 编译方式与解释方式的根本区别编译方式与解释方式的根本区别n 编译程序的工作过程编译程序的工作过程n 编译程序的结构编译程序的结构n 遍与编译程序的组织形式遍与编译程序的组织形式n 编译程序的构造方法编译程序的构造方法47第二章 文法和语言 要点要点(本章是基础本章是基础)1 1、概念、概念:文法文法,推导推导,直接推导直接推导,最左最左(右右)推导推导,产生产生式式,句型句型,短语短语,直接短语直接短语,句柄句柄,语法树语法树,规范推

26、导规范推导,二二义文法等义文法等2 2、4 4种文法的定义种文法的定义、文法的构造和文法的推导文法的构造和文法的推导3 3、语法树的构造和最左（右）推导；语法树的构造和最左（右）推导；4 4、二义文法、二义性的证明；、二义文法、二义性的证明；5 5、句型分析；、句型分析；48 词法规则：自动机 语法规则：上下文无关文法49引言引言 语言包括语法和语义两方面。语法语法是一组规则，用以判断什么样的符号序列是合法的；语义语义指含义，如变量的类型、作用域是否符合正确的语法。常把程序设计语言的语义分为二类：静态语义和动态语义。静态语义静态语义是一系列限定规则，并确定哪些合乎语法的程序是合适的；动态语义动

27、态语义（或称运行语义、执行语义），表明程序要做些什么，要计算什么。阐明语法的一个工具是文法，常采用上下文无关文法作为程序设计语言语法的描述工具。50补充：文法的直观概念(1/5)描述一种语言，无非是说明这种语言的句子。如果该语言所含的句子是有限的，那么只要一一列举出即可；若是无限的，则存在如何给出有穷表示的问题。但无论如何，某语言的句子总是存在着一种组成结构，即所谓的规则（或称文法）。文法文法：描述语言的语法结构的形式规则（即语法：描述语言的语法结构的形式规则（即语法规则）。规则）。51直观文法举例(2/5)例如：简单的汉语句子的构成规则:=:=|:=我|你|他 :=王明|大学生|工人|英语:

28、=:=是|学习:=|则“我是大学生”是句子52“我是大学生”的推导过程：我 我 我是 我是 我是大学生 依次可以推导出句子“王明是大学生”、“我学习英语”等等推导过程(3/5)53程序设计语言对文法的要求(4/5)这些规则必须是准确的，易于理解的，且应当有相当强的描述能力，足以描述各种不同的结构。54文法作用(5/5)（1）定义句子的结构；（2）用适当条数的规则把语言的全部句子描述出来，以有穷集合刻划无穷集合。55 2 符号串及其运算符号串及其运算 （1）符号串：由字母表中的符号组成的任何符号串：由字母表中的符号组成的任何有穷序列有穷序列。说明说明:字母间的顺序字母间的顺序 不同顺序组成的符号

29、串是不同的；不同顺序组成的符号串是不同的；（2）符号串长度符号串长度 符号串内所含符号的个数，若符号串内所含符号的个数，若x=string,则则|x|=6;其中不含任何符号的符号串称为其中不含任何符号的符号串称为空符号串空符号串，长度长度|02.1 语言成分 1 字母表（符号表）与符号字母表（符号表）与符号 元素（或称符号）的元素（或称符号）的非空有穷非空有穷集合，用符号集合，用符号表示。表示。不同语言有不同的字母表。如汉语包括汉字、数字、标不同语言有不同的字母表。如汉语包括汉字、数字、标点符号等；点符号等；C语言包括字母、数字和保留字等等。语言包括字母、数字和保留字等等。56符号串的运算符号

30、串的运算(1/3)符号串的头尾，固有头和固有尾符号串的头尾，固有头和固有尾：设设 z=xy 是一个符号串，则是一个符号串，则x是是z的头，的头，y是是z的尾。如果的尾。如果x是是非空的，那么非空的，那么y是是固有尾；如果是是固有尾；如果y是非空的，那么是非空的，那么x是固有头。是固有头。例：例：z=abc，则则 z的头：的头：、a、ab、abc；固有头：固有头：、a、ab；z的尾：的尾：、c、bc、abc；固有尾：固有尾：、c、bc；当我们对符号当我们对符号z=xy 的头感兴趣而对其余部分不感兴趣时，的头感兴趣而对其余部分不感兴趣时，我们可以采用省略写法：我们可以采用省略写法：z=x。如果只是

31、为了强调如果只是为了强调x在符号在符号串中的某处出现，则可表示为：串中的某处出现，则可表示为：z=x；符号符号t是符号串是符号串z的的第一个符号，则表示为：第一个符号，则表示为：z=t。57(3)符号串的连接符号串的连接 设设x和和y是符号串，它们的连接是符号串，它们的连接xy是把是把y的符号写在的符号写在x的的符号之后得到的符号串。符号之后得到的符号串。例如：例如：x=abc，y=DEF，则则xy=abcDEF；若若|x|=n，|y|m，则则|xy|=n+m对任意的符号串对任意的符号串x，有有 x=x =x58（4 4）符号串集合的乘积符号串集合的乘积 设设A、B是两个符号串的集合，则是两个

32、符号串的集合，则AB表示表示A与与B的乘的乘积，定义为：积，定义为：AB=xy|xA,yB如：若如：若A=ab,c,B=d,efg,则则AB=abd,abefg,cd,cefg特别地，有：特别地，有：A=A=A 空集空集 表示不含任何元素的空集表示不含任何元素的空集。有：有：A=A=请区别：请区别：，三种表示方法的含义三种表示方法的含义59（5）符号串的方幂符号串的方幂 同一符号串的连接可以写成方幂的形式。设x是符号串，把x自身连接n次得到的符号串z，即z=xxxx，称为符号串x的方幂，记作z=xn，有：x0=x1=x x2=xx x3=xxx 当n0时，xn x xn-1=xn-1 x60（

33、6 6）符号串集合的方幂）符号串集合的方幂同一符号串集合的连接也可以写成方幂的形式。设符号串集合为A，则有：A0=A1=AA2=AAA3=AAA 当n0时，An A An-1=An-1 A例如：A=ab，c，则AA=AAA=61（7 7）符号串集合的正闭包）符号串集合的正闭包设符号串集合为A，则A的正闭包记为A+，定义为：A+=A1 A2 An 表示A上所有有穷长串的集合例如：A=ab，c，AA=，AAA=（8 8）符号串集合的自反闭包）符号串集合的自反闭包设符号串集合为A，则A的自反闭包记为A*，定义为：A*=A0 A1 A2 An 即A*=A0 A+=A+例如：A=a,b，则 A*=,a,

34、b,aa,ab,ba,bb,aaa,A+=A*A=AA*622.2 产生式文法和语言2.2.1 文法的形式定义文法的形式定义是一个四元组是一个四元组 G=（VN，VT，P，S）VN 非终结符号集，非终结符号代表的是语法范畴，也就是它是一类（或集合）的记号，而不是一个个体记号。如“表达式”、“语句”、“分程序”等等，都是表达一定的语法概念。因此，每个非终结符表示一定符号串的集合（由终结符和非终结符 组成）；(如简单汉语句子中。）VT 终结符号集合，终结符是构成语言的基本符号，也就是说，它是一个语言的不可再分的基本符号；P 产生式（或称规则,重写规则,生成式）集合。所谓产生式是定义语法范畴的一种书

35、写规则。一个产生式的形式是（或:=)，其中 “”读为“是”或“定义为”；产生式的左部 (VNVT)*且至少含有一个非终结符号，右部(VNVT)*,即由终结符或（与）非终结符组成的一符号串，允许是空字 632.2 产生式文法和语言例如：简单的汉语句子的构成规则:=:=|:=我|你|他 :=王明|大学生|工人|英语:=:=是|学习:=|则“我是大学生”是句子64文法的形式定义文法的形式定义S S 开始符号，即文法的第一个非终结符。开始符号代表了所定义的语言中我们最感兴趣的语法范畴，如在程序语言中，我们感兴趣的是“程序”注意：1、VN VT 即不含公共元素；2、产生式是有限的；3、开始符号S至少必须

36、在某个产生式的左部出现一次；4、为书写方便，若干个左部相同的产生式如：P1,P2，Pn 合并成：P1|2|n其中i称为P的一个候选式。65文法定义举例文法定义举例1 1例2.1 表示算术表达式的文法描述：G1=（VN，VT，P，S）其中VNE VT=i,+,*,(,)P=E i,E E+E,E E*E,E(E)S=E或者直接写为：G1=(E,i,+,*,(,),E i,E E+E,E E*E,E(E),E)66文法定义举例文法定义举例2 2例例2 文法文法G=（VN，VT，P，S）其中其中VN标识符，字母，数字标识符，字母，数字，VT a,b,c,x,y,z,0,1,8,9 P=|,a|b|c

37、|x|y|z,a|b|c|x|y|z,0|1|2|8|90|1|2|8|9 S=67 用文法定义语言的中心思想是：从文法的开始符号出发，反复连续使用产生式，对非终结符施行替换和展开。例如文法G：E E+E|E*E|(E)|i，其中唯一非终结符E可以看成是代表一类算术表达式。从E出发，进行一系列的推导，推出种种不同的算术表达式。如根据上述规则可推出(i+i)：E=(E)=(E+E)=(i+E)=(i+i)我们称这样的一串替换是从E推出(i+i)的一个推导一个推导，这个推导提供了一个证明，证明(i+i)是文法G所定义的一个算术表达式。2.2.2 文法的推导文法的推导68有关推导的定义有关推导的定义

38、 定义2.3 直接推导直接推导=若A直接推导出，即 A=，当且仅当A-是一个产生式，且、(VNVT)*符号=指推导一步，即推导每前进一步总是引用一条规则（产生式）定义2.4 长度为长度为n（n1）的推导的推导 若存在直接推导序列a1=a2=an，则称a1可推导出an。a1 an 表示：从a1出发经过一步或若干步，可推导出an。定义2.5 长度为长度为n（n0）的推导的推导 a1 an 表示：从a1出发经过0步（a1 an）或若干步，可推导出an。692.2.3 句型、句子、语言句型、句子、语言例1：证明终结符号串(i*i+i)是文法G：E E+E|E*E|(E)|i的一个句子证明：E=(E)=

39、(E+E)=(E*E+E)=(i*E+E)=(i*i+E)=(i*i+i)是从开始符号E到(i*i+i)的一个推导。其中E、(E)、(E+E)、(E*E+E)、(i*E+E)、(i*i+E)、(i*i+i)都是这个文法的一个句型1.句型句型：设GS是一个文法，S是它的开始符号，若S ,则称是文法GS的句型。2.句子句子：仅含终结符的句型是一个句子，即S ，VT*,则是句子。3.语言语言：文法G所产生的句子的全体是一个语言，记作L(G)L(G)=|S ,且VT*70语言的例子例2：文法G2 A：A bA|cc，证明cc、bcc、bbcc属于L(G2)。证明：A=cc，A=Ba=bcc，A=bA=

40、bbA =bbcc cc、bcc、bbcc、是属于L(G2)的例3：文法GS：(1)S0S1；(2)S01。GS的语言是什么？解：对第一个产生式使用n-1次，然后使用第二个产生式一次，得到：S=0S1=00S11=0S=0S1=00S11=0n-1n-1S1S1n-1 n-1=0=0n n1 1n n因此L(G)=0L(G)=0n n1 1n n|n|n 1 1 例4：下列文法的语言是什么？GS=（S,S-,S）GA=（A，A）712.2.4 文法的文法的等价等价 若L(G1)=L(G2)，则称文法G1和G2是等价的例1：G1=(VN,VT,P,S)，VN=S，VT=0,1，P由下列产生式组成

41、：(1)S0S1；(2)S01；G2=(VN,VT,P,A)，VN=A,R，VT=0,1，P由下列产生式组成：(1)A 0R;(2)A 01;(3)R A172什么是递归文法？1.递归规则递归规则：规则右部有与左部相同的符号 对于 U-xUy 若x=,即U-Uy，左递归；若y=,即U-xU，右递归；2.递归文法递归文法：文法G，存在U VN 若 U=U,则G为递归文法；若 U=U,则G为左递归文法；若 U=U,则G为右递归文法；734.递归文法递归文法的优点优点：可用有穷条规则，定义无穷语言 例：对于前面给出的标识符的文法是有递归文法，用y有限条规则就可以定义出所有的标识符。若不用递归文法，那

42、将要用多少条规则呢？!3.左递归文法左递归文法的缺点缺点：不能用自顶向下的方法来进行语分析,会造成死循环742.3 文法的分类2.3.1 文法分类 乔姆斯基（Chomsky)建立的形式语言对计算机科学的发展具有深刻的意义。他把文法分成四种类型：0型、1型、2型和3型。0型强于1型，1型强于2型，2型强于3型，它们的差别在于对产生式施加不同的限制差别在于对产生式施加不同的限制。75定义定义 0型文法（或称短语文法型文法（或称短语文法,phrase structure grammar,PSG）G=(VN,VT,P,S)是是0型文法是指：型文法是指：若它的每个产生式若它的每个产生式是这样一种结构是这

43、样一种结构:(VNVT)+且至少含有一个非终结符且至少含有一个非终结符，(VNVT)*。任何任何0型文法都是递归可枚举的。型文法都是递归可枚举的。0型文法的能力相当型文法的能力相当于图灵机（计算机的一种简单的理论模型）。于图灵机（计算机的一种简单的理论模型）。称称L为为递归可枚举递归可枚举的：若存在一个产生的：若存在一个产生L的过程。的过程。称称L为为递归递归的：若存在一个识别的：若存在一个识别L的算法。的算法。76定义定义 1型文法（或称上下文有关文法型文法（或称上下文有关文法,CSG Context Sensitive Grammar）如果对如果对0型文法加以以下的限制，则可得到型文法加以

44、以下的限制，则可得到1型文法。型文法。设设G=(VN,VT,P,S)为一文法，若为一文法，若G的的任何产生式任何产生式 均均满足满足|(指符号串的长度指符号串的长度)，仅仅，仅仅S 例外。例外。课本课本P24例例2.2。例：设例：设G=(VN,VT,P,S)，VN=S,B,E，VT=a,b,e，P由下列产生式组成：由下列产生式组成：(1)S aSBE；(2)S aBE;(3)EB BE;(4)aB ab;(5)bB bb;(6)bE be;(7)eE ee;求求 GS的语言是什么。的语言是什么。77接上页例子接上页例子分析：条产生式中只有第条具有递归性，其它的产生分析：条产生式中只有第条具有递

45、归性，其它的产生分析：条产生式中只有第条具有递归性，其它的产生分析：条产生式中只有第条具有递归性，其它的产生式最终都向终结符靠拢。式最终都向终结符靠拢。式最终都向终结符靠拢。式最终都向终结符靠拢。注意：注意：注意：注意：S S aSBEaSBE 与与与与S0S1S0S1的相似性，都可用同一模板来的相似性，都可用同一模板来的相似性，都可用同一模板来的相似性，都可用同一模板来表示表示表示表示S SS S 使用产生式使用产生式使用产生式使用产生式(1)(1)n-1n-1次，得推导序列：次，得推导序列：次，得推导序列：次，得推导序列：S S a an-1n-1S(BE)S(BE)n-1n-1；使用产生

46、式使用产生式使用产生式使用产生式(2)(2)一次，得到：一次，得到：一次，得到：一次，得到：S aS an n(BE)(BE)n n；使用产生式使用产生式使用产生式使用产生式(3)(3)的右部替换的右部替换的右部替换的右部替换EBEB，使最终得到的串中，所使最终得到的串中，所使最终得到的串中，所使最终得到的串中，所有的有的有的有的B B都先于所有的都先于所有的都先于所有的都先于所有的E E，即即即即S S a an nB Bn nE En n；78接上例接上例 使用产生式(4)一次，得到S an bBn1En；使用产生式(5)n-1次，得到S an bnEn；使用产生式(6)一次，得到S an

47、 bn eEn-1；使用产生式(7)n-1次，得到S an bn en；因此，L(G)=an bn en|n 1说明：上述分析中，步骤是关键一步，否则不能推导出终结符号串。例如假设n=3，S aaaBEBEBE aaaBBEEBE aaabBEEBE aaabbEEBE aaabbeEBE aaabbeeBE79 上下文有关，顾名思义就是对非终结符进行替上下文有关，顾名思义就是对非终结符进行替换时必须考虑上下文。例如，换时必须考虑上下文。例如，1型文法型文法G的产生式的产生式也可写成也可写成A，其中其中、都在都在(VNVT)*中，且中，且，A VN，则说明了非终结符，则说明了非终结符A必须必须

48、在在、这样一个上下文环境中才可以替换。这样一个上下文环境中才可以替换。上下文有关文法能生成上下文有关文法能生成anbncn类特征的语言。但类特征的语言。但它不能描述它不能描述L=c|(a|b)*类语言。类语言。对上下文有关文法的说明对上下文有关文法的说明80定义定义 2型文法（或称上下文无关文法，型文法（或称上下文无关文法，CFG Context Free Grammar）设设G=(VN,VT,P,S)为一文法，若为一文法，若G的任何产生式形似的任何产生式形似A，其中其中A VN，(VNVT)+。例：例：G=(S,A,B,a,b,P,S)，其中，其中P由下列产生式组成由下列产生式组成SaB|b

49、A Aa|aS|bAABb|bS|aBB例：例：G=(VN,VT,P,S)，VN=S，VT=0,1，P由下由下列产生式组成：列产生式组成：(1)S0S1；(2)S01；81上下文无关文法的说明上下文无关文法的说明上下文无关，顾名思义就是非终结符的替换上下文无关，顾名思义就是非终结符的替换可以不必考虑上下文。由于这种文法对程序已可以不必考虑上下文。由于这种文法对程序已基本可以描述，因此，上下文无关文法常简称基本可以描述，因此，上下文无关文法常简称为文法。为文法。上下文无关文法最多能生成上下文无关文法最多能生成anbn类特征的语类特征的语言，不能生成言，不能生成anbncn类特征的语言。类特征的语

50、言。82 设设G=(VN,VT,P,S)为一文法，若为一文法，若G的任何产生式的任何产生式A 或或A B，其中，其中A、B VN，VT*。对任何正规文法对任何正规文法G，都可以设计一个不确定的有穷自动都可以设计一个不确定的有穷自动机机NFA，它能够而且只能够识别它能够而且只能够识别G的语言。的语言。定义定义 3型文法（或称正规文法，型文法（或称正规文法，RG Regular Grammar）例：文法例：文法G=(S,A,B,0,1,P,S)，其中，其中P由下列产生式组成由下列产生式组成S 0A|1B|0A 0A|1B|0SB 1B|1|083左线性文法设G=(VN,VT,P,S)为一文法，若G