第2章形式语言优秀PPT.ppt-淘文阁

资源描述

《第2章形式语言优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第2章形式语言优秀PPT.ppt（72页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第2章形式语言现在学习的是第1页，共72页第一章第一章引言引言第二章第二章形式语言理论基础形式语言理论基础第三章第三章自动机理论基础自动机理论基础第四章第四章词法分析词法分析第五章第五章语法分析语法分析自顶向下分析方法自顶向下分析方法第六章第六章语法分析语法分析自底向上分析方法自底向上分析方法第七章第七章语义分析及中间代码的生成语义分析及中间代码的生成第八章第八章符号表符号表第十章第十章代码优化代码优化目目录录现在学习的是第2页，共72页第二章第二章形式语言理论基础形式语言理论基础学习目标学习目标学习形式语言理论中的一些基本概念和基础知识学习形式语言理论中的一些基本概念

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

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

4、程序语言的语法描述和语法分析。程序语言的语法描述和语法分析。1956 1956年著名语言学家年著名语言学家Noam Chomsky Noam Chomsky 首先描述形式首先描述形式语言，已成为计算机科学的一个重要组成部分，是编译语言，已成为计算机科学的一个重要组成部分，是编译理论重要基础。理论重要基础。现在学习的是第5页，共72页2.1 2.1 形式语言的基本概念形式语言的基本概念2.2 2.2 文法和形式语言的定义文法和形式语言的定义2.3 2.3 语法树和二义性语法树和二义性2.4 2.4 文法的实用限制文法的实用限制2.5 2.5 文法和语言的文法和语言的ChomskyChomsky分

5、类分类目目录录现在学习的是第6页，共72页2.1 2.1 形式语言的基本概念形式语言的基本概念2.1.1 2.1.1 符号和符号串符号和符号串形式语言和编译技术中两个主要概念形式语言和编译技术中两个主要概念任何一种语言都是由该语言的基本符号组成的基本符任何一种语言都是由该语言的基本符号组成的基本符号串集合。号串集合。英文：英文：2626个字母、数字、标点符号等个字母、数字、标点符号等 PASCAL PASCAL：字母、数字、关键字、专用符号等：字母、数字、关键字、专用符号等中文：汉字、数字、标点符号等中文：汉字、数字、标点符号等现在学习的是第7页，共72页1.1.字母表：字母表：是一

6、个非空的有限集合。用是一个非空的有限集合。用表示。表示。例例 =a =a，b b，c c （a,b,ca,b,c均为字符或符号均为字符或符号,是字母表中的元素）是字母表中的元素）2.2.符号串：符号串：符号的有序序列。用小写希腊字母表示如：符号的有序序列。用小写希腊字母表示如：，a a，b b，abab，abc abc等。等。表示空字符串，不包含任何符号的符号串。表示空字符串，不包含任何符号的符号串。空格空格另外另外abbaabba3.3.符号串集合：符号串集合：字母表上若干符号串的组成集合。用字母表上若干符号串的组成集合。用大写字母表示。大写字母表示。例：例：A=aA=a，abab，bc

7、bc现在学习的是第8页，共72页 4.4.语言（形式语言）：语言（形式语言）：字母表上所有符号串组成的集合的子集字母表上所有符号串组成的集合的子集,用用 L L表示。表示。L L *，L L可抽象地看成所有句子的集合。可抽象地看成所有句子的集合。句子又可抽象看成是某个有限字母表句子又可抽象看成是某个有限字母表的符号串。的符号串。字母表上的符号串不可能都是句子。字母表上的符号串不可能都是句子。例：例：=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

8、=，0101，0011,0011,空集或者空语言，不含任何符号串的语言。空集或者空语言，不含任何符号串的语言。现在学习的是第9页，共72页2.1.2 2.1.2 符号串的运算符号串的运算1.1.符号串相等：符号串相等：同一字母表的两个符号串所有同一字母表的两个符号串所有符号依次相等。符号依次相等。如如=a=a，b b，cc =abc =abc，=abc=abc，则，则=；若若=abc=abc，=cba=cba，则，则2.2.字符串长度：字符串长度：符号串中包含的字符的个数。符号串中包含的字符的个数。记记|例例|abc|=3|abc|=3，|=0,|a|=|a|=1+|=0,|a|=|a|=1

9、+|，a a。现在学习的是第10页，共72页 3.3.符号串的连接符号串的连接:把符号串把符号串的所有符号相继写的所有符号相继写在在之后，记之后，记或或 =ab =ab，=bc=bc，则则=abbc=abbc 4.4.符号串的逆：符号串的逆：符号串符号串的倒置，记的倒置，记-1-1 如如=abc =abc 则则 -1-1=cba=cba -1-1=（-1-1）-1-1=（）-1-1=-1-1-1-1 现在学习的是第11页，共72页5.5.符号串的前缀、后缀和子串符号串的前缀、后缀和子串设设，是字母表是字母表上的字符串，则上的字符串，则为为符号符号的前缀，的前缀，为字符串为字符串的后缀，的

10、后缀，是是字符串字符串的子串。的子串。前缀和后缀都是子串，但子串不一定是前缀或者后缀。前缀和后缀都是子串，但子串不一定是前缀或者后缀。前缀和后缀都是子串，但子串不一定是前缀或者后缀。前缀和后缀都是子串，但子串不一定是前缀或者后缀。前缀：前缀：，a a，abab，abcabc后缀：后缀：，bcbc，c c，abcabc子串：子串：，a a，b b，c c，abab，bcbc，abcabc例：例：abc abc现在学习的是第12页，共72页 6.6.符号串集合的乘积符号串集合的乘积 A AB=B=|A|A，BB 例：例：A=ab,ba B=bc,b 则则AB=abbc,abb,babc,bab

11、特别：特别：A=A=A 现在学习的是第13页，共72页7.符号串的幂符号串的幂（一个符号串与它自己的（一个符号串与它自己的n次连接）次连接）0=1=2=n=n-1例：例：=ab0=1=ab2=ababn=ababab现在学习的是第14页，共72页8 8符号串集合的幂符号串集合的幂 A0=A1=AA2=AAAn=An-1A=AAn-1(n0)例：例：A=ab,cA0=A1=ab,cA2=abc,cab,abab,cc现在学习的是第15页，共72页9.集合集合A的闭包和正闭包的闭包和正闭包A*=A0A1=正闭包正闭包A+=A1A2=A*=A0A+A+=AA*=A*A字母表字母表 *：上所有符号串的

12、集合上所有符号串的集合 +：上所有非空符号串的集合上所有非空符号串的集合例：例：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，现在学习的是第16页，共72页2.2 2.2 文法和语言的形式定义文法和语言的形式定义语言语言L：可抽象地看成是所有句子组成的集合（有限集：用枚可抽象地看成是所有句子组成的集合（有限集：用枚举；无限集：文法）举；无限集：文法）句子：句子：可抽象地看成是某个有限字母表可抽象地看成是某个有限字母表上的符号串。

13、上的符号串。例：英语例：英语=26=26个字母，数字，标点符号，个字母，数字，标点符号，文法：文法：在形式上用以描述和规定语言结构的方法，是用有限的在形式上用以描述和规定语言结构的方法，是用有限的手段描述无限的句子集合的方法之一。手段描述无限的句子集合的方法之一。L *L *现在学习的是第17页，共72页例：我爱祖国。例：我爱祖国。从结构上看符合中文文法，是中文句子。从结构上看符合中文文法，是中文句子。例：例：“The big cat ate a mouse.”“The big cat ate a mouse.”见课本见课本1212页。页。（1 1）.(10)(10)mouse mouse

14、现在学习的是第18页，共72页又如：又如：（1 1）无符号整数）无符号整数数字串数字串（2 2）数字串）数字串数字串数字数字串数字（3 3）数字串）数字串数字数字（4 4）数字）数字22 （5 5）数字）数字55 （6 6）数字）数字66 256 256是一个句子。是一个句子。现在学习的是第19页，共72页文法中必须有三部分：文法中必须有三部分：1.终结符号集终结符号集VT（句子中的字母）（句子中的字母）2.非终结符号集非终结符号集VN（大写字母，一般出现在左部，不（大写字母，一般出现在左部，不属于字母表）属于字母表）3.文法规则集合文法规则集合UX或或U:=X定义：定义：文法是一个

15、四元组文法是一个四元组G=（VN，VT，S，P）记为）记为GSV是字汇表，是字汇表，V=VTVN，SVN，VTVN=现在学习的是第20页，共72页例例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)现在学习的是第21页，共72页引进引进BNF（巴科斯范式）（巴科斯范式）IL|IL|INLa|b|cN0|1|9定义：定义：句型句型文法文法GS，G=（VN，VT，S，P）由由S推出的符号串推出的符号串X(VTVN)*称为句型。称为句型。

16、现在学习的是第22页，共72页 a.直接推导、直接归约直接推导、直接归约(长度长度=1)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归

17、约到归约到0 0 记作记作0 0 n n，n n 0 0 +现在学习的是第23页，共72页c.若若1 1 2或或1=2则称则称1广义推导广义推导2，记作，记作1 22广义归约到广义归约到1记作记作2 1长度长度00+*例：例：1.文法文法GE：EE+T|TTT*F|FE i+i*i(n=8)F(E)|i2.G推出推出256+现在学习的是第24页，共72页定义：定义：语言、句子语言、句子文法文法G=（VN，VT，S，P）所产生的语言）所产生的语言L(G)L(G)L(G)=L(G)=|S|S ,V VT T*其中其中称为句子称为句子.空语言空语言:由文法开始符号推不出任何句子由文法开始符号推不

18、出任何句子.+r+d.规范推导（最右推导，也称为最左归约）规范推导（最右推导，也称为最左归约）每次替换最右边非终结符的直接推导。记作每次替换最右边非终结符的直接推导。记作1 1 2 2结论结论:给定一个文法给定一个文法,就能从结构上唯一地确定其语言就能从结构上唯一地确定其语言.给定一个语言，能确定相应文法给定一个语言，能确定相应文法,但不唯一但不唯一.现在学习的是第25页，共72页例例:G1:S0S1S01L(G1)=0n1n|n1G2:S1S1AL(G2)=(10)n1|n0A0SG3:S1SA1L(G3)=1(01)n|n0AS0L(G2)=L(G3),所以，所以，G2和和G3为等价文法为

19、等价文法现在学习的是第26页，共72页又如：已知语言又如：已知语言L(GZ)=abna|n n1 1 则：则：G1：Z aBa G2：Z aB G 3：Z Ba B b|Bb B ba|bB B ab|Bb 例例2-3 2-3 G=（VN，VT，S，P）VN=S，B，C VT=a，b，c P P：（：（1 1）SaSBC SaSBC （5 5）bBbbbBbb （2 2）SaBC SaBC （6 6）bCbcbCbc （3 3）CBBC CBBC （7 7）cCcccCcc （4 4）aBabaBab现在学习的是第27页，共72页解：解：1)1)S S aBC aBCabCabCabcabc

20、（2 2）（4 4）（6 6）2 2）S SaSBCaSBCaaBCBCaaBCBCaabCBCaabCBCaabBCCaabBCC(1)(2)(4)(3)(1)(2)(4)(3)aabbCCaabbCCaabbcCaabbcCaabbccaabbcc 所以所以,L(G)=a,L(G)=an nb bn nc cn n|n=1|n=1，2 2，现在学习的是第28页，共72页例例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)由相同

21、个数的由相同个数的 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 0110 0110 S S 0B 0B 00BB 00BB 0011 0011 现在学习的是第29页，共72页 2.3 2.3 语法树和二义性语法树和二义性2.3.1 2.3.1 语法树和推导语法树和推导 1.1.语法树语法树：用直观方法描述句型或句子的语法结构：用直观方法描述句型或句子的语法结构.已知文法已知文法 GS,GS,

22、满足下列条件的树称为满足下列条件的树称为G G的语法树的语法树.a.a.结点：终结符结点：终结符or or 非终结符非终结符 b.b.树根树根:S:S c.c.分枝分枝:非终结符非终结符 d.d.若结点若结点A A有有B B1 1B B2 2BBn n分枝，则分枝，则ABAB1 1B B2 2BBn n是是G G的一的一个规则。个规则。现在学习的是第30页，共72页例：例：GS：SaAB S S SaAB S S ABa|a a A B a A BABa|a a A B a A BBbd B a B a b dBbd B a B a b d b d b d 现在学习的是第31页，共72页2

23、2由推导生成语法树由推导生成语法树句型句型or句子的推导用图解表示句子的推导用图解表示语法树生成语法树生成例：例：GGA：ABBBC|CC0|1|2|9推导：推导：ABBCBC6C52ABBCBCCCCC2CC25C256ABBCB6BC6B56C56256现在学习的是第32页，共72页 3.3.由语法树构造推导由语法树构造推导上一步的逆过程上一步的逆过程.由分枝建立直接推导由分枝建立直接推导,然后剪去分枝然后剪去分枝,直到无分枝可剪直到无分枝可剪.ABBCBCCCCC2CC25C256或先进行归约或先进行归约,再倒过来再倒过来.现在学习的是第33页，共72页4.子树和短语子树和短语定义定义:

24、子树子树-某个结点与它的分枝结点某个结点与它的分枝结点.BBCC5简单子树简单子树-单层分枝的子树单层分枝的子树.BCC5现在学习的是第34页，共72页定义定义:短语、简单短语、句柄短语、简单短语、句柄设设S aBc,B b,则则S aBc abcS则则b称为句型称为句型abc相对于相对于B的短语的短语.aBcb结论结论:(1)子树的末端结点组成的符号串是相对于子树的末端结点组成的符号串是相对于子树根的短语子树根的短语.(2)简单子树的末端结点组成的符号串是相简单子树的末端结点组成的符号串是相对于简单子树根的简单短语对于简单子树根的简单短语.(3)最左简单子树的末端结点组成的符号串最左简单子树

25、的末端结点组成的符号串为句柄为句柄.*+*+现在学习的是第35页，共72页例：例：E句型：句型：短语：短语：E+T简单短语：简单短语：句柄：句柄：TFiT+iT+iT+i,T,iT+i,T,iT,iT,iT T现在学习的是第36页，共72页2.3.2 2.3.2 文法的二义性文法的二义性1.1.二义性二义性定义定义:如果一个文法所定义的句子中如果一个文法所定义的句子中,有某个句子存在两棵不有某个句子存在两棵不同的语法树同的语法树,则称文法是二义性的。则称文法是二义性的。或或:若文法所定义的某个句子若文法所定义的某个句子,有两种不同的最左有两种不同的最左(or(or最右最右)推导。推导。或或

27、38页，共72页例：例：Gs：SifBthenS|ifBthenSelseS|AS：语句：语句B：布尔表达式：布尔表达式A：其它语句：其它语句句型：句型：ifBthenifBthenSelseSS ifBthenS ifBthenifBthenSelseSS ifBthenSelseS ifBthenifBthenSelseS现在学习的是第39页，共72页SSifBthenSifBthenSelseSifBthenSelseSifBthenS 现在学习的是第40页，共72页2.2.二义性解决方法二义性解决方法 (1)(1)修改编译算法修改编译算法例例:GE:GE：EE+E|E*E|(E)|I

28、EE+E|E*E|(E)|I 在编译方法中规定运算之间的优先级在编译方法中规定运算之间的优先级.如如:*,/:*,/高于高于+,-+,-同级先左后右同级先左后右现在学习的是第41页，共72页 (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|A Cif B then C else S|A Uif B then S Uif B then S 现在学习的是第42页，共7

29、2页注注:规则左部的符号在右部同时出现两次规则左部的符号在右部同时出现两次oror两次以上，两次以上，导致二义性导致二义性.先天二义性文法先天二义性文法:不存在等价的非二义性文法不存在等价的非二义性文法.二义性问题是不可判定的，即不存在一种算法在有二义性问题是不可判定的，即不存在一种算法在有限步内判断二义性限步内判断二义性.现在学习的是第43页，共72页2.4 2.4 文法的实用限制文法的实用限制2.4.1 2.4.1 有害规则有害规则定义定义:文法中凡是形如文法中凡是形如AAAA的规则，造成文法的二义性的规则，造成文法的二义性.N例例:NNNNNND|DNND0|1|9NDND现在学习的是

30、第44页，共72页2.4.2 2.4.2 多余规则多余规则定义定义:文法文法G,在某句型中出现的符号在某句型中出现的符号可推出符号可推出符号例例:GE,E,T,F,+,-,*,/,(,),i例例:SaAB|aAaAb|bS,A,B,a,b,dBdCaBf*定义定义:GS,若若AVN,存在存在,V*有有S A,则称则称A为活的非终结符为活的非终结符.例例N,D现在学习的是第45页，共72页定义定义:多余规则多余规则左部符号为左部符号为A的规则的规则,若不满足条件若不满足条件A为可推出符号为可推出符号从从A能推出句子能推出句子例例:GS:SBeD不是可推出符号不是可推出符号AAe|eDf多余多余B

31、Ce|AfBCeCCfCCf多余多余Df在程序设计语言中若包含多余规在程序设计语言中若包含多余规则则,必定有错误句子必定有错误句子.现在学习的是第46页，共72页 a.A a.A为可推出符号：即为可推出符号：即 S A ,V*；b.b.必须能从必须能从A A推出句子，即：推出句子，即：A A ,V VT T+*+定理定理1:1:如果一个文法如果一个文法GS中所有规则均满足下列两个条中所有规则均满足下列两个条件，则该文法不包含（设：件，则该文法不包含（设：A A为任一规则的左部符号）。为任一规则的左部符号）。现在学习的是第47页，共72页GS:GS:SBe SBe 多余规则多余规则 Df Df

32、AAe|e BCe AAe|e BCe BCe|Af CCf BCe|Af CCf CCf CCf Df Df现在学习的是第48页，共72页2.4.3 2.4.3 文法的实用限制文法的实用限制定义定义:文法文法GS所有规则均满足下列实用限制条件所有规则均满足下列实用限制条件:a.没有有害规则没有有害规则b.没有多余规则没有多余规则则则称称GS是是压缩压缩or化简过的化简过的.上例化简后上例化简后,GS:SBeAAe|eBAf现在学习的是第49页，共72页2.4.4 2.4.4 文法的等价变换文法的等价变换在语法分析中在语法分析中,各种分析方法都有一定的局限性，对文各种分析方法都有一定的局限性，

33、对文法进行种种限制法进行种种限制,为了使某一语言能用某一种分析方法为了使某一语言能用某一种分析方法,常常常根据限制条件对文法进行变换常根据限制条件对文法进行变换.算法算法1 1:使文法的开始符号不出现在规则的右部使文法的开始符号不出现在规则的右部.GS,GS,引进引进S,S,扩充扩充S S,GSS S,GS为为扩充文法扩充文法.例例:GN:NND|D GN:GN:NND|D GN：NNNN D0|1|9 NND|D D0|1|9 NND|D D0|1|9 D0|1|9 现在学习的是第50页，共72页算法算法2 2:使文法每个非终结符均能推导出一个终结符号串使文法每个非终结符均能推导出一个终结

37、S=D,S去掉含去掉含A,BA,B的规则的规则,G G2 2S:SadS:Sad DbD|e DbD|e 由算法由算法3.V3.VN N=S =S 不能扩充不能扩充删除左部含删除左部含D D的规则的规则于是于是G G3 3SS：S ad S ad 现在学习的是第55页，共72页算法算法4:4:消除特殊规则消除特殊规则 AB AB 第一步第一步:构造新的非终结符号集合构造新的非终结符号集合V VN N,对于对于V VN N中每个中每个非终结符非终结符(如如A),A),构造构造V VNANA=B|A B,BV=B|A B,BVN N 第二步第二步:若有若有A B,GA B,G中有中有BB,则

38、在则在GG中扩充中扩充A A 第三步第三步:删除特殊规则删除特殊规则ABAB和无用规则和无用规则.例例:GA:AB|d E:GA:AB|d E BA|D|b BA|D|b DB|d DB|d Ee|E a Ee|E a+现在学习的是第56页，共72页 +第一步第一步:A A dE A A dE 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 Bb Bb 扩充充AbAb Dd Ad Dd Ad 对B AdE B AdE 扩充充BdEBdE Dd

39、Bd Dd Bd 对D AdE D AdE 扩充充DdEDdE Bb Db Bb Db现在学习的是第57页，共72页第三步第三步:删去特殊规则删去特殊规则.于是得到于是得到 A dE|b|d A dE|b|d B dE|b|d B dE|b|d D dE|b|d D dE|b|d E e|Ea E e|Ea 由算法由算法3,B,D3,B,D不在任何句型中出现不在任何句型中出现,删去删去,得到得到 A dE|b|d A dE|b|d E e|Ea E e|Ea现在学习的是第58页，共72页算法5.消去空规则消去空规则 A A 第一步第一步:构造新的非终结符号集构造新的非终结符号集V VN N V

40、 VN N=A|A=A|APP 递归扩充递归扩充V VN N=V=VN NUB|B xP,xVUB|B xP,xVN N+第二步第二步:从从G G中删去空规则中删去空规则第三步第三步:从规则中删去只能导出空串的非终结符从规则中删去只能导出空串的非终结符第四步第四步:扩充新规则扩充新规则对于对于AAB BD,B,DVD,B,DVN N,(V-V(V-VN N)*扩充扩充AA|D|D|B B|B BD D现在学习的是第59页，共72页例例:GA:AaBbD BDD Db|:GA:AaBbD BDD Db|第一步第一步:V:VN N=D=D P=DP=D V VN N=V=VN NUB|BDD

41、P,DDVUB|BDDP,DDVN N+=D,B=D,B第二步第二步:删去去DD 第三步第三步:无无第四步第四步:扩充新充新规则，对于于AaBbD B,DVAaBbD B,DVN N Aab|abD|aBb Aab|abD|aBb 对于于BDD,DVBDD,DVN N BD BD于是于是GA:A ab|abD|aBb|aBbDGA:A ab|abD|aBb|aBbD B D|DD B D|DD D b D b现在学习的是第60页，共72页算法算法6 6.消除左递归消除左递归GS中有中有:AAA|,其中其中,V V*,不以不以A A开开头修改修改为:A :A AA A A A|A|例例:E E

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

43、DDND|D N DD D 0|1|9 D 0|1|9 D 0|1|9 D 0|1|9例例:GE:E T|T+E E T+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)现在学习的是第62页，共72页二二.扩充扩充BNF表示法的用途表示法的用途.消除左递归消除左递归,使文法在自顶向下分析过程中，能进行分析使文法在自顶向下分析过程中，能进行分析处理处理.例例:GE:ET+T:GE:ET+T T F*F T F*F F i|

44、(E)F i|(E)现在学习的是第63页，共72页2.5 2.5 文法和语言的文法和语言的ChomskyChomsky分类分类四类文法对应四类语言四类文法对应四类语言.2.5.1 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)现

45、在学习的是第64页，共72页例例2-5:P=SACaB,Ca aaC,CB DB2-5:P=SACaB,Ca aaC,CB DB CB E,aD Da,AD AC,CB E,aD Da,AD AC,aE Ea,AE aE Ea,AE S ACaB AaaCB AaaE S ACaB AaaCB AaaE AaEa AEaa aa,S aaaa AaEa AEaa aa,S aaaaL L0 0(G)=a(G)=a2n2n|n0|n0 尽管尽管0 0型文法不足以描述自然语言，但对程序设计语型文法不足以描述自然语言，但对程序设计语言的描述而言又太一般化言的描述而言又太一般化,所以须对规则的形式加以

46、限制所以须对规则的形式加以限制.+现在学习的是第65页，共72页2.5.2 12.5.2 1型文法与型文法与1 1型语言（线性界限自动机）型语言（线性界限自动机）定义：文法定义：文法GSGS中每个规则即为：中每个规则即为：W W,WV,WVN N，V V*,VV+则称则称G G为为1 1型文法型文法（或上下文有关文法（或上下文有关文法)CSG)CSG产生的语言称为产生的语言称为1 1型语言型语言L L1 1（G G）（或上下文有关语言，前后文有关语言）（或上下文有关语言，前后文有关语言）在自然语言中，一个句子或一个单词的语法性质往往和在自然语言中，一个句子或一个单词的语法性质往往和它所处的上下

47、文有密切的关系，所以描述自然语言的文法它所处的上下文有密切的关系，所以描述自然语言的文法一定是上下文有关文法。一定是上下文有关文法。现在学习的是第66页，共72页例：例：GS：SaSBC|aBC GSaSBC|aBC GS是是1 1型文法型文法CBDBCBDBDBDCDBDCDCBCDCBCaBabaBabbBbbbBbbbCbcbCbccCcccCccSaBCabCabcSaSBCaaBCBCaabCBCaabDBCaabDCCaabBCCaabbcCaabbccL L1 1(G)=a(G)=an nb bn nc cn n|n1|n1现在学习的是第67页，共72页2.5.3 22.5.3

48、2型文法和型文法和2 2型语言型语言（下推自动机，程序设计语言）（下推自动机，程序设计语言）定义定义:文法文法GS GS 中每一个规则形如：中每一个规则形如：A A ，AVAVN N ，V V+则称则称G G为为2 2型文法型文法（或上（或上下文无关语言）下文无关语言）L L2 2（G G）。）。注注:有些书中有些书中V V*，即允许出现，即允许出现的规则。大部的规则。大部分程序设计语言的文法近似于分程序设计语言的文法近似于2 2型文法，所以是我们型文法，所以是我们主要研究对象主要研究对象例：例：GSGS：SaSb LSaSb L2 2(G)=a(G)=an nb bn n|n1|n

49、1 Sab Sab GS:SAc|Sc L(G)=a GS:SAc|Sc L(G)=an nb bn nc cm m|n,m1|n,m1 Aab|aAb Aab|aAb 现在学习的是第68页，共72页2.5.4 32.5.4 3型文法和型文法和3 3型语言型语言定义定义:文法文法GSGS中每个规则形如中每个规则形如:ABa ABa或或AaBAaB或或Aa 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.左线性文法左

展开阅读全文