第2章形式语言.ppt

《第2章形式语言.ppt》由会员分享，可在线阅读，更多相关《第2章形式语言.ppt（72页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理简明教程21世纪高等学校计算机学科系列教材第一章第一章 引言引言第二章第二章 形式语言理论基础形式语言理论基础第三章第三章 自动机理论基础自动机理论基础第四章第四章 词法分析词法分析第五章第五章 语法分析语法分析自顶向下分析方法自顶向下分析方法第六章第六章 语法分析语法分析自底向上分析方法自底向上分析方法第七章第七章 语义分析及中间代码的生成语义分析及中间代码的生成第八章第八章 符号表符号表第十章第十章 代码优化代码优化目目 录录第二章第二章形式语言理论基础形式语言理论基础 学习目标学习目标 学习形式语言理论中的一些基本概念和基础知识学习形式语言理论中的一些基本概念和基础知识 掌握程序

2、设计语言的语法描述方法掌握程序设计语言的语法描述方法 需要着重掌握的内容为需要着重掌握的内容为 字母表字母表 产生式、上下文无关文法产生式、上下文无关文法 推导、句型、句子、语言推导、句型、句子、语言 语法树语法树 二义性二义性 ChomskyChomsky文法分类文法分类 语法：语法：程序的结构形式程序的结构形式 语义：语义：语言所代表的含义语言所代表的含义 语用：语用：语言的实际应用语言的实际应用 例如：例如：x:=a*b+cx:=a*b+c 语法：语法：变量变量:=:=表达式表达式 v:=e v:=e 语义：语义：对对e e求值，再赋给变量求值，再赋给变量 语用：语用：计算和保存计算和保

3、存e e的值的值 以上非形式化的描述不够清晰明确。以上非形式化的描述不够清晰明确。程序设计语言程序设计语言 探讨形式化方法探讨形式化方法:用一套带有严格规定的符号体系来描用一套带有严格规定的符号体系来描 述问题的理论和方法。述问题的理论和方法。形式语言：形式语言：是一种不考虑含义的符号语言（只谈语法是一种不考虑含义的符号语言（只谈语法 不谈语义）。不谈语义）。形式语言理论：形式语言理论：主要研究组成这组符号串的集合，它主要研究组成这组符号串的集合，它 们的表示法、结构及特性，只能用于们的表示法、结构及特性，只能用于 程序语言的语法描述和语法分析。程序语言的语法描述和语法分析。19561956年

4、著名语言学家年著名语言学家Noam Chomsky Noam Chomsky 首先描述形式首先描述形式语言，已成为计算机科学的一个重要组成部分，是编译语言，已成为计算机科学的一个重要组成部分，是编译理论重要基础。理论重要基础。2.1 2.1 形式语言的基本概念形式语言的基本概念2.2 2.2 文法和形式语言的定义文法和形式语言的定义2.3 2.3 语法树和二义性语法树和二义性2.4 2.4 文法的实用限制文法的实用限制2.5 2.5 文法和语言的文法和语言的ChomskyChomsky分类分类目目 录录2.1 2.1 形式语言的基本概念形式语言的基本概念2.1.1 2.1.1 符号和符号串符号

5、和符号串 形式语言和编译技术中两个主要概念形式语言和编译技术中两个主要概念 任何一种语言都是由该语言的基本符号组成的基本符任何一种语言都是由该语言的基本符号组成的基本符 号串集合。号串集合。英文：英文：2626个字母、数字、标个字母、数字、标点点符号等符号等 PASCALPASCAL：字母、数字、关键字、专用符号等字母、数字、关键字、专用符号等 中文：汉字、数字、标中文：汉字、数字、标点点符号等符号等1.1.字母表：字母表：是一个非空的有限集合。用是一个非空的有限集合。用表示。表示。例例 =a=a，b b，c c （a,b,ca,b,c均为字符或符号均为字符或符号,是字母表中的元素）是字母表中

6、的元素）2.2.符号串：符号串：符号的有序序列。用小写希腊字母表示如：符号的有序序列。用小写希腊字母表示如：，a a，b b，abab，abcabc等。等。表示空字符串，不包含任何符号的符号串。表示空字符串，不包含任何符号的符号串。空格空格 另外另外abbaabba3.3.符号串集合：符号串集合：字母表上若干符号串的组成集合。用字母表上若干符号串的组成集合。用 大写字母表示。大写字母表示。例：例：A=aA=a，abab，bcbc 4.4.语言（形式语言）：语言（形式语言）：字母表上所有符号串组成的集合的子集字母表上所有符号串组成的集合的子集,用用 L L表示。表示。L L *，L L可抽象地看

7、成所有句子的集合。可抽象地看成所有句子的集合。句子又可抽象看成是某个有限字母表句子又可抽象看成是某个有限字母表的符号串。的符号串。字母表上的符号串不可能都是句子。字母表上的符号串不可能都是句子。例：例：=a=a，L=aL=a2k2k|k0|k0 =0 =0，11，L L1 1=(01)=(01)n n|n0=|n0=，0101，01010101，L L2 2=0=0n n1 1n n|n0=|n0=，0101，0011,0011,空集或者空语言，不含任何符号串的语言。空集或者空语言，不含任何符号串的语言。2.1.2 2.1.2 符号串的运算符号串的运算1.1.符号串相等：符号串相等：同一字母表

8、的两个符号串所有同一字母表的两个符号串所有 符号依次相等。符号依次相等。如如=a=a，b b，cc =abcabc，=abcabc，则，则=；若若=abcabc，=cbacba，则，则2.2.字符串长度：字符串长度：符号串中包含的字符的个数。符号串中包含的字符的个数。记记|例例|abcabc|=3|=3，|=0,|a|=|a|=1+|=0,|a|=|a|=1+|，aa。3.3.符号串的连接符号串的连接:把符号串把符号串的所有符号相继写的所有符号相继写 在在之后，记之后，记或或 =abab，=bcbc，则则=abbcabbc 4.4.符号串的逆：符号串的逆：符号串符号串的倒置，记的倒置，记-1-

9、1 如如 =abcabc 则则 -1-1=cbacba -1-1=（-1-1）-1-1=（）-1-1=-1-1-1-1 5.5.符号串的前缀、后缀和子串符号串的前缀、后缀和子串 设设，是字母表是字母表上的字符串，则上的字符串，则为为 符号符号的前缀，的前缀，为字符串为字符串的后缀，的后缀，是是 字符串字符串的子串。的子串。前缀和后缀都是子串，但子串不一定是前缀或者后缀。前缀和后缀都是子串，但子串不一定是前缀或者后缀。前缀和后缀都是子串，但子串不一定是前缀或者后缀。前缀和后缀都是子串，但子串不一定是前缀或者后缀。前缀：前缀：，a a，abab，abcabc后缀：后缀：，bcbc，c c，abca

10、bc子串：子串：，a a，b b，c c，abab，bcbc，abcabc例：例：abcabc 6.6.符号串集合的乘积符号串集合的乘积 A AB=B=|A|A，BB 例：例：A=ab,ba B=bc,b 则则AB=abbc,abb,babc,bab 特别：特别：A=A=A 7.符号串的幂符号串的幂（一个符号串与它自己的（一个符号串与它自己的n次连接）次连接）0=1=2=n=n-1例：例：=ab0=1=ab2=ababn=ababab8 8符号串集合的幂符号串集合的幂 A0=A1=AA2=AAAn=An-1A=AAn-1(n0)例：例：A=ab,cA0=A1=ab,cA2=abc,cab,ab

11、ab,cc9.集合集合A的闭包和正闭包的闭包和正闭包A*=A0A1=正闭包正闭包A+=A1A2=A*=A0A+A+=AA*=A*A字母表字母表 *：上所有符号串的集合上所有符号串的集合 +：上所有非空符号串的集合上所有非空符号串的集合例：例：A=0，1则则A1=0，1A0=A A2 2=00=00，0101，1010，11 11 A*=，0 0，1 1，0000，0101，1010，1111，000000，A+=0，1，00，01，10，11，000，2.2 2.2 文法和语言的形式定义文法和语言的形式定义语言语言L：可抽象地看成是所有句子组成的集合（有限集：用枚可抽象地看成是所有句子组成的集

12、合（有限集：用枚举；无限集：文法）举；无限集：文法）句子：句子：可抽象地看成是某个有限字母表可抽象地看成是某个有限字母表上的符号串。上的符号串。例：英语例：英语=26=26个字母，数字，标点符号，个字母，数字，标点符号，文法：文法：在形式上用以描述和规定语言结构的方法，是用有限的在形式上用以描述和规定语言结构的方法，是用有限的 手段描述无限的句子集合的方法之一。手段描述无限的句子集合的方法之一。L *L *例：我爱祖国。例：我爱祖国。从结构上看符合中文文法，是中文句子。从结构上看符合中文文法，是中文句子。例：例：“The big cat ate a mouse.The big cat ate

13、a mouse.”见课本见课本1212页。页。（1 1）.(10)(10)mouse mouse 又如：又如：（1 1）无符号整数无符号整数数字串数字串 （2 2）数字串数字串数字串数字串数字数字 （3 3）数字串数字串数字数字 （4 4）数字数字22 （5 5）数字数字55 （6 6）数字数字66 256 256是一个句子。是一个句子。文法中必须有三部分：文法中必须有三部分：1.终结符号集终结符号集VT（句子中的字母）句子中的字母）2.非终结符号集非终结符号集VN（大写字母，一般出现在左部，不大写字母，一般出现在左部，不属于字母表）属于字母表）3.文法规则集合文法规则集合UX或或U:=X定定

14、义义：文文法法是是一一个个四四元元组组G=（VN，VT，S，P）记记为为GSV是字汇表，是字汇表，V=VTVN，SVN，VTVN=例例2-1VN=A，VT=a，b，c，S=A，P=AaAb，Ac构成文法构成文法G=（A，a，b，c，A，P）例例2-2G=（标识符标识符，字母字母，数字数字，0，1，2，.9，a，b，c，标识符标识符，P)引进引进BNF（巴科斯范式）巴科斯范式）IL|IL|INLa|b|cN0|1|9定义：定义：句型句型 文法文法GS，G=（VN，VT，S，P）由由S推出的符号串推出的符号串X(VTVN)*称为句型。称为句型。a.直接推导、直接归约直接推导、直接归约(长度长度=1

15、)b.b.推导、归约、推导长度推导、归约、推导长度(n1)(n1)文法文法G，A是一条规则，是一条规则，1 1=1 1AA2 2 2 2=1 12 2 （其中（其中1 1，2 2，1 1，2 2（(VTVN)*）则称则称1 1直接推导出直接推导出2 2，记作，记作 反之，反之，2 2直接归约到直接归约到1 1，记作，记作 1 12 22 21 1文法文法G G，存在一直接推导序列，存在一直接推导序列，0 0 1 1 2 2 n n (0 01 1n n是句型是句型)则称则称0 0推导出推导出n n或或n n归约到归约到0 0 记作记作0 0 n n ，n n 0 0 +c.若若1 1 2或或1

16、=2则称则称1广义推导广义推导2，记作，记作1 22广义归约到广义归约到1记作记作2 1长度长度0 0+*例：例：1.文法文法GE：EE+T|TTT*F|FE i+i*i(n=8)F(E)|i2.G推出推出256+定义：定义：语言、句子语言、句子 文法文法G=（VN，VT，S，P）所产生的语言所产生的语言L(G)L(G)L(G)=L(G)=|S|S ,V VT T*其中其中称为句子称为句子.空语言空语言:由文法开始符号推不出任何句子由文法开始符号推不出任何句子.+r+d.规范推导（最右推导，也称为最左归约）规范推导（最右推导，也称为最左归约）每次替换最右边非终结符的直接推导。记作每次替换最右边

17、非终结符的直接推导。记作1 1 2 2结论结论:给定一个文法给定一个文法,就能从结构上唯一地确定其语言就能从结构上唯一地确定其语言.给定一个语言，能确定相应文法给定一个语言，能确定相应文法,但不唯一但不唯一.例例:G1:S0S1S01L(G1)=0n1n|n1G2:S1S1AL(G2)=(10)n1|n0A0SG3:S1SA1L(G3)=1(01)n|n0AS0L(G2)=L(G3),所以，所以，G2和和G3为等价文法为等价文法 又如：已知语言又如：已知语言L(GZ)=abna|n n1 1 则：则：G1：Z aBa G2：Z aB G 3：Z Ba B b|Bb B ba|bB B ab|B

18、b 例例2-3 2-3 G=（VN，VT，S，P）VN=S，B，C VT=a，b，c P P：（：（1 1）SaSBCSaSBC （5 5）bBbbbBbb （2 2）SaBCSaBC （6 6）bCbcbCbc （3 3）CBBC CBBC （7 7）cCcccCcc （4 4）aBabaBab解解：1)1)S S aBCaBCabCabCabcabc （2 2）（4 4）（6 6）2 2）S SaSBCaSBCaaBCBCaaBCBCaabCBCaabCBCaabBCCaabBCC(1)(2)(4)(3)(1)(2)(4)(3)aabbCCaabbCCaabbcCaabbcCaabbcca

19、abbcc 所以所以,L(G)=,L(G)=a an nb bn nc cn n|n|n=1=1，2 2，例例G=（VN，VT，S，P）VN=A，B，SVT=0，1P P：S0B S1AS0B S1A A0 B1 A0 B1 A0S B1S A0S B1SA1AA B0BBA1AA B0BB 所以，所以，L(G)L(G)由相同个数的由相同个数的 0 0 和和 1 1 所组成的所组成的VT+中中所有符号串的集合所有符号串的集合.解：解：S S 0B 0B 01 01 S S 1A 1A 10 10 010B 010B 0101 0101 S S 0B 0B 01S 01S 011A 011A 0

20、110 0110 S S 0B 0B 00BB 00BB 0011 0011 2.3 2.3 语法树和二义性语法树和二义性2.3.1 2.3.1 语法树和推导语法树和推导 1.1.语法树语法树：用直观方法描述句型或句子的语法结构：用直观方法描述句型或句子的语法结构.已知文法已知文法 GS,GS,满足下列条件的树称为满足下列条件的树称为G G的语法树的语法树.a.a.结点：终结符结点：终结符or or 非终结符非终结符 b.b.树根树根:S:S c.c.分枝分枝:非终结符非终结符 d.d.若结点若结点A A有有B B1 1B B2 2B Bn n分枝，则分枝，则ABAB1 1B B2 2B Bn

21、 n是是G G的一的一 个规则。个规则。例：例：GS：S SaABaAB S S S S ABa|aABa|a a A B a A B a A B a A BBbdBbd B a B a b d B a B a b d b d b d 2 2由推导生成语法树由推导生成语法树句型句型or句子的推导用图解表示句子的推导用图解表示语法树生成语法树生成例：例：GGA：ABBBC|CC0|1|2|9推导：推导：ABBCBC6C52ABBCBCCCCC2CC25C256ABBCB6BC6B56C56256 3.3.由语法树构造推导由语法树构造推导上一步的逆过程上一步的逆过程.由分枝建立直接推导由分枝建立直

22、接推导,然后剪去分枝然后剪去分枝,直到无分枝可剪直到无分枝可剪.ABBCBCCCCC2CC25C256或先进行归约或先进行归约,再倒过来再倒过来.4.子树和短语子树和短语定义定义:子树子树-某个结点与它的分枝结点某个结点与它的分枝结点.BBCC5简单子树简单子树-单层分枝的子树单层分枝的子树.BCC5定义定义:短语、简单短语、句柄短语、简单短语、句柄设设S aBc,B b,则则S aBc abcS则则b称为句型称为句型abc相对于相对于B的短语的短语.aBcb结论结论:(1)子树的末端结点组成的符号串是相对于子树的末端结点组成的符号串是相对于子树根的短语子树根的短语.(2)简单子树的末端结点组

23、成的符号串是相简单子树的末端结点组成的符号串是相对于简单子树根的简单短语对于简单子树根的简单短语.(3)最左简单子树的末端结点组成的符号串最左简单子树的末端结点组成的符号串为句柄为句柄.*+*+例：例：E句型：句型：短语：短语：E+T简单短语：简单短语：句柄：句柄：TFiT+iT+iT+i,T,iT+i,T,iT,iT,iT T2.3.2 2.3.2 文法的二义性文法的二义性1.1.二义性二义性 定义定义:如果一个文法所定义的句子中如果一个文法所定义的句子中,有某个句子存在两棵不有某个句子存在两棵不 同的语法树同的语法树,则称文法是二义性的。则称文法是二义性的。或或:若文法所定义的某个句子若文

24、法所定义的某个句子,有两种不同的最左有两种不同的最左(or(or最右最右)推导。推导。或或:若文法所定义的某个句子若文法所定义的某个句子,有两种不同的最左有两种不同的最左(or(or最右最右)归约。归约。例例:GE:GE：EE+E|E*E|(E)|iEE+E|E*E|(E)|i E E E E E +E E *E E +E E *E i E *E E +E i i E *E E +E i i i i i i i i i E E E+E|E+E*E E+E|E+E*E i+i*i i+i*i E E E*E|E+E*E E*E|E+E*E i+i*i i+i*i 文法的二义性产生句子语义上的不确

25、定性文法的二义性产生句子语义上的不确定性.+例：例：Gs：SifBthenS|ifBthenSelseS|AS：语句语句B：布尔表达式布尔表达式A：其它语句其它语句句型：句型：ifBthenifBthenSelseSS ifBthenS ifBthenifBthenSelseSS ifBthenSelseS ifBthenifBthenSelseSSSifBthenSifBthenSelseSifBthenSelseSifBthenS 2.2.二义性解决方法二义性解决方法 (1)(1)修改编译算法修改编译算法 例例:GE:GE：EE+E|E*E|(E)|IEE+E|E*E|(E)|I 在编译方

26、法中规定运算之间的优先级在编译方法中规定运算之间的优先级.如如:*,/:*,/高于高于 +,-+,-同级先左后右同级先左后右 (2)(2)修改文法修改文法 GEGE：EE+T|E-T|TEE+T|E-T|T TT*F|T/F|F TT*F|T/F|F F(E)|i F(E)|i GS GS：SC|U C:SC|U C:完全语句完全语句 U:U:不完全语句不完全语句 Cif B then C else S|ACif B then C else S|A Uif B then S Uif B then S 注注:规则左部的符号在右部同时出现两次规则左部的符号在右部同时出现两次oror两次以上，两次以

27、上，导致二义性导致二义性.先天二义性文法先天二义性文法:不存在等价的非二义性文法不存在等价的非二义性文法.二义性问题是不可判定的，即不存在一种算法在有二义性问题是不可判定的，即不存在一种算法在有 限步内判断二义性限步内判断二义性.2.4 2.4 文法的实用限制文法的实用限制2.4.1 2.4.1 有害规则有害规则定义定义:文法中凡是形如文法中凡是形如AAAA的规则，造成文法的二义性的规则，造成文法的二义性.N例例:NNNNNND|DNND0|1|9NDND2.4.2 2.4.2 多余规则多余规则定义定义:文法文法G,在某句型中出现的符号在某句型中出现的符号可推出符号可推出符号例例:GE,E,T

28、,F,+,-,*,/,(,),i例例:SaAB|aAaAb|bS,A,B,a,b,dBdCaBf*定义定义:GS,若若AVN,存在存在,V*有有S A,则称则称A为活的非终结符为活的非终结符.例例N,D定义定义:多余规则多余规则左部符号为左部符号为A的规则的规则,若不满足条件若不满足条件A为可推出符号为可推出符号从从A能推出句子能推出句子例例:GS:SBeD不是可推出符号不是可推出符号AAe|eDf多余多余BCe|AfBCeCCfCCf多余多余Df在程序设计语言中若包含多余在程序设计语言中若包含多余规则规则,必定有错误句子必定有错误句子.a.Aa.A为可推出符号：即为可推出符号：即 S A ,

29、V*；b.b.必必须须能能从从A A推推出出句句子子，即即：A A ,V VT T+*+定理定理1:1:如果一个文法如果一个文法GS中所有规则均满足下列两个条中所有规则均满足下列两个条件，则该文法不包含（设：件，则该文法不包含（设：A A为任一规则的左部符号）。为任一规则的左部符号）。GS:GS:SBe SBe 多余规则多余规则 DfDf AAe|eAAe|e BCeBCe BCe|AfBCe|Af CCfCCf CCfCCf Df Df2.4.3 2.4.3 文法的实用限制文法的实用限制定义定义:文法文法GS所有规则均满足下列实用限制条件所有规则均满足下列实用限制条件:a.没有有害规则没有有

30、害规则b.没有多余规则没有多余规则则则称称GS是是压缩压缩or化简过的化简过的.上例化简后上例化简后,GS:SBeAAe|eBAf2.4.4 2.4.4 文法的等价变换文法的等价变换在语法分析中在语法分析中,各种分析方法都有一定的局限性，各种分析方法都有一定的局限性，对文法进行种种限制对文法进行种种限制,为了使某一语言能用某一种分析为了使某一语言能用某一种分析方法方法,常常根据限制条件对文法进行变换常常根据限制条件对文法进行变换.算法算法1 1:使文法的开始符号不出现在规则的右部使文法的开始符号不出现在规则的右部.GS,GS,引进引进S S,扩充扩充S S S,G S,GSS 为为扩充文法扩充

31、文法.例例:GN:NND|D G:GN:NND|D GNN：N NNN D0|1|D0|1|9 NND|D|9 NND|D D0|1|D0|1|9|9 算法算法2 2:使文法每个非终结符均能推导出一个终结符号串使文法每个非终结符均能推导出一个终结符号串.G=G=（V VN N，V VT T，S S，P P）G G=（V VN N，V VT T，S S，P P）一、构造新的非终结符号集合一、构造新的非终结符号集合V VN N 令令V VN N=A|AP=A|AP，VVT T+递归扩充递归扩充V VN N=V=VN NB|BPB|BP，(V(VN NVVT T)+二、在二、在G G中删去左、右部含

32、有不属于中删去左、右部含有不属于V VN N中的符号的规则中的符号的规则。例：例：GSGS：SaABS|bDADdSaABS|bDADd AbAB|dSA|dDDAbAB|dSA|dDD BbAB|dSBBbAB|dSB DdS|dDdS|d 第一步：第一步：V VN N=D|DdP=D|DdP，dVdVT T+=D=D V VN N=V VN N A|AdDDPA|AdDDP，dDD(VdDD(VN N VVT T)+=D=D，AA V VN N=V VN N S|SbDADdPS|SbDADdP，bDADd(VbDADd(VN N VVT T)+=A=A，D D，SS 第二步：删去含有第二

33、步：删去含有B B的规则，得的规则，得P P:SbDADdSbDADd AdSA|dDDAdSA|dDD DdS|dDdS|d 算法算法3 3:使文法的每个非终结符均出现在某个句型中使文法的每个非终结符均出现在某个句型中 一、构造新的非终结符号集一、构造新的非终结符号集 V VN N=S=S 递归扩充递归扩充V VN N=V VN NB|ABPB|ABP，AVAVN N 即即 V VN N=B|S B=B|S B，BVBVN N，,(V,(VN NVVT T)*二、从二、从G G中删去左部不在中删去左部不在V VN N中的非终结符的规则。中的非终结符的规则。*例：例：G G1 1SS：Sad|

34、bASad|bA AdBDAdBD BaSABaSA DbD|eDbD|e 由算法由算法2.V2.VN N=D,S=D,S去掉含去掉含A,BA,B的规则的规则,G G2 2S:SadS:Sad DbD|eDbD|e 由算法由算法3.V3.VN N=S =S 不能扩充不能扩充 删除左部含删除左部含D D的规则的规则 于是于是G G3 3SS：S adS ad 算法算法4:4:消除特殊规则消除特殊规则 ABAB 第一步第一步:构造新的非终结符号集合构造新的非终结符号集合V VN N,对于对于V VN N中每个中每个 非终结符非终结符(如如A),A),构造构造V VNANA=B|A B,BV=B|A

35、 B,BVN N 第二步第二步:若有若有A B,GA B,G中有中有BB,则在则在G G中扩充中扩充A A 第三步第三步:删除特殊规则删除特殊规则ABAB和无用规则和无用规则.例例:GA:AB|d E:GA:AB|d E BA|D|bBA|D|b DB|dDB|d Ee|EEe|E a a+第一步第一步:A A A A dEdE A B b V A B b VNANA=A,B,D=A,B,D A D d A D d 同理同理,V,VNBNB=V=VNDND=A,B,D V=A,B,D VNENE=第二步第二步:对A AA A BbBb 扩充充AbAb DdDd AdAd 对B B AdEAdE

36、 扩充充BdEBdE DdDd BdBd 对D D AdEAdE 扩充充DdEDdE BbBb DbDb第三步第三步:删去特殊规则删去特殊规则.于是得到于是得到 A A dE|b|ddE|b|d B B dE|b|ddE|b|d D D dE|b|ddE|b|d E e|Ea E e|Ea 由算法由算法3,B,D3,B,D不在任何句型中出现不在任何句型中出现,删去删去,得到得到 A A dE|b|ddE|b|d E e|Ea E e|Ea算法算法5.5.消去空规则消去空规则 AA 第一步第一步:构造新的非终结符号集构造新的非终结符号集V VN N V VN N=A|A=A|APP 递归扩充递归

37、扩充V VN N=V=VN NUB|B UB|B xP,xVxP,xVN N+第二步第二步:从从G G中删去空规则中删去空规则 第三步第三步:从规则中删去只能导出空串的非终结符从规则中删去只能导出空串的非终结符 第四步第四步:扩充新规则扩充新规则 对于对于AAB BD,B,DVD,B,DVN N,(V-V(V-VN N)*扩充扩充AA|D|D|B B|B BD D例例:GA:GA:AaBbDAaBbD BDD BDD DbDb|第一步第一步:V:VN N=D=D P=DP=D V VN N=V=VN N UB|BDDP,DDVUB|BDDP,DDVN N+=D,B=D,B第二步第二步:删去去D

38、D 第三步第三步:无无第四步第四步:扩扩充新充新规则规则，对对于于AaBbDAaBbD B,DV B,DVN N Aab|abD|aBbAab|abD|aBb 对于于BDD,DVBDD,DVN N BD BD于是于是G G A:A A:A ab|abD|aBb|aBbDab|abD|aBb|aBbD B D|DD B D|DD D b D b算法算法6 6.消除左递归消除左递归GS中有中有:AAA|,其中其中,V V*,不以不以A A开开头头 修改修改为为:A :A A A A A A A|例例:E E+T|E-T|T E TE:E E+T|E-T|T E TE T T*F|T/F|F E T

39、 T*F|T/F|F E +TE +TE|-TE|-TE|F (E)|i T FT F (E)|i T FT T T *FT *FT|/FT|/FT|F (E)|i F (E)|i2.4.5 2.4.5 扩充的扩充的BNFBNF表示法表示法在在BNF上发展起来上发展起来,相同表达效力相同表达效力,结构上更简单，清晰结构上更简单，清晰.一一.专用符号专用符号t-t可重复任意次可重复任意次t-t可出现可出现0次或次或1次次()-提因子提因子例例:GN:N:GN:NND|D N DDND|D N DD D 0|1|D 0|1|9 D 0|1|9 D 0|1|9|9例例:GE:E T|T+E E T+

40、E:GE:E T|T+E E T+E T F|F*T T F*T T F|F*T T F*T F i|(E)F i|(E)F i|(E)F i|(E)例例:A :A 1 1|2 2|n n A A (1 1|2 2|n n)二二.扩充扩充BNF表示法的用途表示法的用途.消除左递归消除左递归,使文法在自顶向下分析过程中，能进使文法在自顶向下分析过程中，能进行分析处理行分析处理.例例:GE:ET+T:GE:ET+T T F*F T F*F F i|(E)F i|(E)2.5 2.5 文法和语言的文法和语言的ChomskyChomsky分类分类 四类文法对应四类语言四类文法对应四类语言.2.5.1

41、02.5.1 0型文法与型文法与0 0型语言型语言(图灵机图灵机)定义定义:文法文法GS,PGS,P中每条规则形如中每条规则形如:,V V+,V V*则称则称G G为为0 0型文法型文法(or(or短语结构文法短语结构文法oror无限制性文法无限制性文法)记记PSG.PSG.产生的语言为产生的语言为0 0型语言型语言(or(or短语结构语言短语结构语言oror无限制性语无限制性语言言)记记L L0 0(G)(G)例例2-5:P=2-5:P=SACaBSACaB,Ca ,Ca aaCaaC,CB DB,CB DB CB E,CB E,aDaD DaDa,AD AC,AD AC,aEaE Ea,A

42、E Ea,AE S S ACaBACaB AaaCBAaaCB AaaEAaaE AaEaAaEa AEaaAEaa aaaa,S ,S aaaaaaaaL L0 0(G)=a(G)=a2n2n|n0|n0 尽管尽管0 0型文法不足以描述自然语言，但对程序设计语型文法不足以描述自然语言，但对程序设计语言的描述而言又太一般化言的描述而言又太一般化,所以须对规则的形式加以限制所以须对规则的形式加以限制.+2.5.2 12.5.2 1型文法与型文法与1 1型语言（线性界限自动机）型语言（线性界限自动机）定义：文法定义：文法GSGS中每个规则即为：中每个规则即为：W W,WV,WVN N，V V*,V

43、V+则称则称G G为为1 1型文法型文法（或上下文有关文法（或上下文有关文法)CSG)CSG产生的语言称产生的语言称为为1 1型语言型语言L L1 1（G G）（）（或上下文有关语言，前后文有关或上下文有关语言，前后文有关语言）语言）在自然语言中，一个句子或一个单词的语法性质在自然语言中，一个句子或一个单词的语法性质往往和它所处的上下文有密切的关系，所以描述自然往往和它所处的上下文有密切的关系，所以描述自然语言的文法一定是上下文有关文法。语言的文法一定是上下文有关文法。例：例：GS：SaSBC|aBCaSBC|aBC GS GS是是1 1型文法型文法CBDBCBDBDBDCDBDCDCBCDC

44、BCaBabaBabbBbbbBbbbCbcbCbccCcccCccSaBCabCabcSaSBCaaBCBCaabCBCaabDBCaabDCCaabBCCaabbcCaabbccL L1 1(G)=a(G)=an nb bn nc cn n|n1|n12.5.3 22.5.3 2型文法和型文法和2 2型语言型语言 （下推自动机，程序设计语言）（下推自动机，程序设计语言）定义定义:文法文法GS GS 中每一个规则形如：中每一个规则形如：AA ，AVAVN N ，V V+则称则称G G为为2 2型文法型文法（或上（或上 下文无关语言）下文无关语言）L L2 2（G G）。）。注注:有些书中有些

45、书中V V*，即允许出现即允许出现的规则。大部的规则。大部 分程序设计语言的文法近似于分程序设计语言的文法近似于2 2型文法，所以是我们型文法，所以是我们 主要研究对象主要研究对象 例：例：GSGS：SaSbSaSb L L2 2(G)=a(G)=an nb bn n|n1|n1 SabSab GS:SAc|Sc L(G)=a GS:SAc|Sc L(G)=an nb bn nc cm m|n,m1|n,m1 Aab|aAbAab|aAb 2.5.4 32.5.4 3型文法和型文法和3 3型语言型语言定义定义:文法文法GSGS中每个规则形如中每个规则形如:ABaABa或或AaBAaB或或Aa

46、A,BVAa A,BVN N,a V,a VT T 则称则称G G为为3 3型文法型文法(或正则文法或正则文法)RG)RG 产生的语言为产生的语言为3 3型语言型语言(或正则语言或正则语言)L)L3 3(G)(G)注注:1.:1.左线性文法左线性文法 ABaABa或或AaAa 右线性文法右线性文法 AaBAaB或或AaAa 2.2.一般形式一般形式 aVaVT T*,定义中的是简单形式，可以替换定义中的是简单形式，可以替换 3.3.对于每一个左对于每一个左(右右)线性文法，都存在一个与某等价线性文法，都存在一个与某等价 的右的右(左左)线性文法线性文法.例例:GS:SBc|ScGS:SBc|S

47、c BAb|BbBAb|Bb 左线性左线性 AAa|aAAa|a L L3 3(G)=(G)=a am mb bn nc ck k|m,n,k|m,n,k 1 1 GS:SaS|aAGS:SaS|aA AbA|bBAbA|bB 右线性右线性 Bc|cBBc|cB 在程序设计语言中，与词法有关的文法在程序设计语言中，与词法有关的文法(单词的语法规单词的语法规则）一般属于则）一般属于3 3型文法型文法.例例:|2.5.5 2.5.5 四类文法的关系四类文法的关系1.01.0型型3 3型型,限制逐渐增加限制逐渐增加,描述语言的能力逐渐减弱。描述语言的能力逐渐减弱。L L0 0L L1 1L L2 2L L3 3 注注:1:1型不允许型不允许AA,但但2,32,3型允许型允许.文法文法文法名称文法名称语言语言自动机自动机0短语结构文法短语结构文法短语结构短语结构图灵机图灵机(TM)1上下文有关文法上下文有关文法上下文有关上下文有关线性界限自动机线性界限自动机(LBA)2上下文无关文法上下文无关文法上下文无关上下文无关下推自动机下推自动机(PDA)3正则文法正则文法正则语言正则语言有限自动机有限自动机(FA)2.2.四种语言可分别被四种自动机所接收四种语言可分别被四种自动机所接收.