第3部分文法和语言.ppt

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

1、第3部分文法和语言 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望 当我们表述一种语言时，无非是说明这种当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。穷表示的问题。以自然语言为例，人们无法列出全部句子，以自然语言为例，人们无

2、法列出全部句子，但是人们可以给出一些规则，用这些规则来说但是人们可以给出一些规则，用这些规则来说明明(或者定义或者定义)句子的组成结构，比如汉语句子句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用词和直接宾语，我们采用EBNF来表示这种句来表示这种句子的构成规则：子的构成规则：3.1 文法的直观概念 BNF范式和语法图1、巴科斯范式:EBNF|你|我|他王明|大学生|工人是|学习|带的叫非终止符,不带的叫终止符。True|False 例子：我 我 我是 我是 我是大学生“我是大学生我是大学生”的构成符合上述规则，

3、的构成符合上述规则，而而“我大学生是我大学生是”不符合上述规则，我们说不符合上述规则，我们说它不是句子。这些规则成为我们判别句子它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。种描述元语言称为文法。语言概述语言概述语言是由句子组成的集合，是由一组符号所构成语言是由句子组成的集合，是由一组符号所构成的集合。的集合。汉语汉语-所有符合汉语语法的句子的全体所有符合汉语语法的句子

4、的全体英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体程序设计语言程序设计语言-所有该语言的程序的全体所有该语言的程序的全体 每个句子构成的规律每个句子构成的规律研究语言研究语言 每个句子的含义每个句子的含义 每个句子和使用者的关系每个句子和使用者的关系研究程序设计语言研究程序设计语言 每个程序构成的规律每个程序构成的规律 每个程序的含义每个程序的含义 每个程序和使用者的关系每个程序和使用者的关系语言研究的三个方面语言研究的三个方面 语法语法 Syntax 语义语义 Semantics 语用语用 Pragmatics语法语法-表示构成语言句子的各个记号之间表示构成语言句子的各

5、个记号之间的组合规律的组合规律语义语义-表示各个记号的特定含义。（各个表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）记号和记号所表示的对象之间的关系）语用语用-表示在各个记号所出现的行为中，表示在各个记号所出现的行为中，它们的来源、使用和影响。它们的来源、使用和影响。每每种种语语言言具具有有两两个个可可识识别别的的特特性性，即即语语言言的形式和该形式相关联的意义。的形式和该形式相关联的意义。语语言言的的实实例例若若在在语语法法上上是是正正确确的的，其其相相关关联联的的意意义义可可以以从从两两个个观观点点来来看看，其其一一是是该该句句子子的的创创立立者者所所想想要要表表示示的的

6、意意义义，另另一一是是接接收收者者所所检检验验到到的的意意义义。这这两两个个意意义义并并非非总总是是一一样样的的，前前者者称称为为语语言言的的语语义义，后后者者是是其其语语用用意意义义。幽幽默默、双双关关语语和和谜谜语语就就是是利利用用这这两两方方面面意意义义间间的的差异。差异。如如果果不不考考虑虑语语义义和和语语用用，即即只只从从语语法法这这一一侧侧面面来来看看语语言言，这这种种意意义义下下的的语语言言称称作作形形式式语语言言。形形式式语语言言抽抽象象地地定定义义为为一一个个数数学学系系统统。“形形式式”是是指指这这样样的的事事实实：语语言言的的所所有有规规则则只只以以什什麽麽符符号号串串能

7、能出出现现的的方方式式来来陈陈述述。形形式式语语言言理理论论是是对对符符号号串串集集合合的的表表示示法法、结结构构及及其其特特性性的的研研究究。是是程程序序设设计计语语言言语语法法分分析研究的基础。析研究的基础。例子:整数(1)单个数字是整数 (2)整数再接上数字仍是整数用BNF范式表示:0|1|2|9|所以合起来有：|0|1|2|9 标识符:以字母开头以后由字母和数字组成的符号串。例子：的巴科斯范式 a|b|z 0|1|9例子：判定字符串a4y是 y y 4y 4y a4y2、语法图 作用：直观、形象的描述语法规则。例子：标识符的语法图表示标识符字母字母数字例子：无符号数的语法图表示 2.4

8、5E+12无符号数无符号整数数字E E无符号整数3.2 3.2 符号和符号串符号和符号串1、字母表:它是非空有穷集。例如：=a,b,c或=1,2,32、符号：字母表中的元素称为符号。3、符号串：符号的有穷序列，符号串也称为字。用来表示空符号串。例如：a,ab,abc,dsfsd4、长度：符号串的长度是指该串所包含的符号个数。用|x|表示符号串x的长度。例如：|a|=1，|abn|=35、连结：设x和y为符号串，则称xy 为他们的连结。例如：x=aa,y=bb,则xy=aabb6、空集：不含任何元素的集合,记为。7、乘积：设A和B是符号串集，则用AB表示A和B的乘积。A=a,b,B=c,d,则A

9、B=ac,ad,bc,bd8、方幂：设A为符号串集，则定义 A0=A1=A An=An-1 A 例如：A=a,b 则有：A0=A1=a,b A2=aa,ab,ba,bb9、正闭包：设A为符号串集，则用A+表示A的正闭包，其具体定义如下：A+=A1A2A3 例如：A=a,A+=a,aa,aaa,10、星闭包：设A为一集合，则定义A的星闭包为A*，其具体定义如下A*=A0A+例如：A=a,A*=,a,aa,aaa,一、引言 例子：y:=a+b*x 语法：赋值语句由变量加“:=”加表达式构成。语义：右边表达式求值与左变量结合赋值。用途：表达式的值的保存和计算。3.3 3.3 文法与语言文法与语言的形

10、式定义的形式定义 形式化方法：用一整套带有严格规定的符号体系来描述问题的理论和方法。表示文法需要一种工具，其中最常用的工具是所谓的巴克斯范式(BNF)。例子:A=an|n1 A=a2n|n1 其BNF表示有：其BNF表示有：(1)Aa|aA (1)Aaa|aaA(2)Aa|Aa (2)Aaa|Aaa例子：A=abna|n1 其BNF表示有多种如下：(1)AaBa Bb|Bb (2)AaBa Bb|bB (3)AaB Bba|bB如何来描述一种语言？如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示句子逐一列出来表示

11、如果语言是无穷的，找出语言的有穷表示。语言的有如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：穷表示有两个途经：生成方式生成方式（文法）：语言中的每个句子可以用严格（文法）：语言中的每个句子可以用严格定义的规则来构造。定义的规则来构造。识别方式识别方式（自动机）：用一个过程，当输入的一任（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止意串属于语言时，该过程经有限次计算后就会停止并回答并回答“是是”，若不属于，要麽能停止并回答，若不属于，要麽能停止并回答“不不是是”，（要麽永远继续下去。），（要麽永远继续下去。）文法即是生成方式描述语言的：语言中的

12、文法即是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造每个句子可以用严格定义的规则来构造.下面给出文法的定义下面给出文法的定义.进而在文法的定义进而在文法的定义的基础上的基础上,给出推导的概念给出推导的概念,句型、句子句型、句子和语言的定义和语言的定义.定义定义文法G定义为四元组(VN，VT，P，S)其中VN为非终结符号(或语法实体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合；VN，VT和P是非空有穷集。S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。VN和VT不含公共的元素，即VN VT=用V表示VN VT，称为文法G的字母表或字

13、汇表规则规则，也称重写规则重写规则、产生式产生式或生成式生成式，是形如或=的(，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称作规则的右部。文法的定义文法的定义例例 文法文法G=（VN，VT，P，S）VN=S,VT=0,1 P=S0S1,S01 S为开始符号为开始符号例例 文法文法G=（VN，VT，P，S）VN=标识符，字母，数字标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P=a,zz 0,0,99 S=文法的写法文法的写法 1 G 1 G：SaASaAb Aab Aab AaA AaAb A A 2 GS 2 GS：Aab AaA Aa

14、b AaAb A A SaSSaSb 3 GSGS：Aab|aAAab|aAb|SaS|SaSb二、文法和语言形式定义1、规则式，产生式例子例子：Bb|Bb Aa|A2、文法GZ：规则的非空有穷集合。Z：识别符号，开始符号。V：字母表，符号集合。例子例子：GS=S0，S，1 VS，0，1定义3.1 文法是一个四元组G(VN，VT，P，Z)。非终极符集记为VN(大写字母)终极符集记为VT(小写字母)产生式集记为P 初始符记为Z例子：自然数G1(VN,VT,P,Z)和标识符G2(VN,VT,P,I)VN=N,D VT=0,1,2,9P=ND|ND,D0|1|2|9 G1：ND|ND D0|1|2|

15、9标识符G2(VN,VT,P,I)VN=I,D,L VT=0,1,2,9,a,bzP=IL|IL|ID,La|b|z D0|1|2|9 G2：IL|IL|ID La|b|c|z D0|1|2|9定义3.21、直接推导：设x和y是符号串，若用一次产生式可从x导出y，则称y为x的直接推导，并记为xy。例子：x=Ab,y=ab,Aa,Abab2、推导：若用若干次产生式可从x串导出y串，则称y为x的推导，并记为x y。+例子：X=AB,Aa,Bb ABaBab 即：AB ab+*3、星推导:x y(当且仅当x=y或xy)。例子：ABAB 0步 ABaB 1步 AB ab 2步 即：AB ab+*+4、

16、句型：称x为句型，若有Z x，其中Z是文法的开始符。凡是由初始符推出的任意符号集合叫句型。例子：ZAB,Aa,Z aB5、句子:称x为句子，若有Z x，且x中不包含非终极符的句型。不包含非终极符的句型叫句子。*例子：GS:S0S1 S01解:S0S1 00S11 000111所以有:S=01,0011,000111 L(G)=0n1n|n16、语言:所有句子的集合称为语言。设是G给定文法，Z是开始符，则语言L(G)可描述如下：定义3.3 设G1,G2为给定文法，如果L(G1)=L(G2),则称G1和G2等价。L(G)=x|Z x,xVT*例1 已知文法求语言并判断是否等价 G1=(VN,VT,

17、P,A)G2=(VN,VT,P,Z)VN=A VN=A,B VT=a,b VT=a,b P=Aab P=ABb,BaA1ab L(G1)=abA2Bbab L(G2)=ab G1与G2是等价的。例2:G3S:SA|S-A Aa|b|c G4S:SA|A-S Aa|b|c推导过程如下：SS-ASS-AAabcS-AS-A-AA-A-Aa-b-c G3与G4等价，但G3与G4的语义不同。推导过程如下：SA-SSA-SAA-SA-A-SA-A-Aa-b-cabca-b-c和a-b-c文法的等价文法的等价若若L（G1）=L（G2），则称文法），则称文法G1和和G2是等是等价的。价的。如文法如文法G G

18、1AA：A0R A0R 与与G G2SS：S0S1 S0S1 等价等价 A01 S01 A01 S01 RA1 RA1定义3.4 F 0型文法(短语结构文法):产生式为：，其中和是符号串。F 1型文法(上下文有关文法)：产生式为：Au，其中AVN，u为非空串。F 2型文法(上下文无关文法):A，其中AVN，为非空串。3.4 3.4 文法文法的类型的类型 F 3型文法(正则文法):产生式为：Aa,AbB,其中A,BVN,#a,bVT是符号串。例子:GZ:Za ZaA Ab|bB Bb所以:GZ是3型文法 文法的类型文法的类型例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GSGS

19、：SCD SCDAbbAAbbA CaCA CaCABaaBBaaB CbCB CbCBBbbBBbbBADaDADaD C CBDbDBDbD D DAabDAabD文法的类型文法的类型例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SABABABS|0BS|0BSA|1SA|13型文法型文法GS：S0A|1B|00A|1B|0A0A|1B|0S0A|1B|0SB1B|1|01B|1|0GI：I lT lTI l lT lT lTT dT dTT l lT d d文法的类型文法的类型2型文法型文法1型文法型文法0型文法型文法四种文法之间的逐级四种文法之间的逐级“包含包含

20、”关系关系3型文法型文法文法和语言文法和语言0型文法产生的语言称为型文法产生的语言称为0型语言型语言1 1型文法或上下文有关文法（型文法或上下文有关文法（CSG ）产生的语言产生的语言称为称为1 1型语言型语言或上下文有关或上下文有关语言（语言（CSL）2 2型文法或上下文无关文法（型文法或上下文无关文法（CFG ）产生的语言产生的语言称为称为2型语言型语言或上下文无关或上下文无关语言（语言（CF L）3 3型文法或正则（正规）文法（型文法或正则（正规）文法（RG）产生的语言产生的语言称为称为3型语言型语言正则（正规）正则（正规）语言（语言（RL）文法和语言文法和语言 四种文法之间的关系四种文

21、法之间的关系 是将产生式做是将产生式做进一步限制而定义的。进一步限制而定义的。语言之间的关系依次：有不是上下语言之间的关系依次：有不是上下文有关语言的文有关语言的0型语言，有不是上下文无型语言，有不是上下文无关语言的关语言的1型语言，有不是正则语言的上型语言，有不是正则语言的上下文无关语言。下文无关语言。根据形式语言理论根据形式语言理论,文法和识别系统间有这文法和识别系统间有这样的关系样的关系 0型文法（短语结构文法）的能力相当于型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，图灵机，可以表征任何递归可枚举集，而且任何而且任何0型语言都是递归可枚举的型语言都是递归可枚举的

22、1型文法（上下文有关文法）：产生式的型文法（上下文有关文法）：产生式的形式为形式为1 1AA2 21 12 2，即只有，即只有A A出现出现在在1 1和和2 2的上下文中时，才允许的上下文中时，才允许取代取代A A。其识别系统是线性界限自动机。其识别系统是线性界限自动机。2型文法（上下文无关文法型文法（上下文无关文法CFG）：产生）：产生式的形式为式的形式为AA，取代取代A A时与时与A A的上下的上下文无关。其识别系统是不确定的下推自文无关。其识别系统是不确定的下推自动机。动机。3型文法（正规文法型文法（正规文法RG）：产生的语言是）：产生的语言是有穷自动机（有穷自动机（FA）所接受的集合）

23、所接受的集合 3型文法产生的语言是有穷自动机（型文法产生的语言是有穷自动机（FA）所接）所接受的集合受的集合.定理定理 设设G=（VN，VT，P，S）是3 3型文法，则存在一个有穷自型文法，则存在一个有穷自 动机动机 M=(K,f,A,Z)M=(K,f,A,Z)，使得，使得L(M)=L(G)L(M)=L(G)有穷自动机有穷自动机NFA M NFA M 这样构造：这样构造：=VT K=K=VN N,NN,N为一个新状态为一个新状态,它不在它不在VN中 A=S A=S Z=N Z=N 对对G G中的形如中的形如 DtB DtB的产生式的产生式,t,t为终结符或为终结符或,有有f(D,t)=Bf(D

24、,t)=B；对对G G中形如中形如DtDt的产生式，的产生式，t t为终结符或为终结符或,有有f(D,t)=N;f(D,t)=N;对对VT中的每一个a,有有f(N,a)=f(N,a)=G：SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|bBASaaabbba,bDZabab 使其右部为空字符串的产生式，称为空产生式。产生式记为A或A例子:GS:SAaB AAB|BbB|所以:GS含有空产生式定义3.5*直接左递归：若有产生式 AA*直接右递归：若有产生式 AA*左递归：若有推导式 A A*右递归：若有推导式 A A*递归：若有产推导 A A+例子：直接递归：AAa BaBB

25、左递归：SQc|c QRb|b RSa|aQRbSabQcab QQcab规范推导和句柄定义3.6 F 设xUyxuy是一直接推导。如果U是句型xUy中的最右非终极字符，则称该推导为规范直接推导并记为xUy xuy。F 如果x y中的每步都是规范直接推导，则称该推导为规范推导并记为x y。r+r+3.5 3.5 上下无关文法及其语法树上下无关文法及其语法树 F 如果每步都是最右非终极字符，则也称该规范推导为最右推导。例子：GS：SAB AAa|bB Ba|SbSABbBBbaB(最左推导)SABASbAABbAAabAbBab(最右推导)SABASbbBSbbaSb(非左非右)语法树与二义性定

26、义3.8 设G=(VN,VT,P,S)是给定文法,则称满足下面条件的树为G的一棵语法树。每个结点都标有G的一个文法符号,且根结点标有初始符S,非叶结点标有非终极符。如果一个非叶结点A有n个儿子结点(从左到右)B1,B2,Bn,则AB1B2,Bn一定是G的一个产生式。定义3.9*由某一结点及其所属分枝组成的部分树称为原树的一棵子树。*只有单层分枝的子树称为简单子树。例子：ZAB Aa BbcSABacb定义3.7 假设Z xUy，U u，则称句型xuy中的u为该句型的短语，其中Z为初始符。假设有Z xUy，Uu，则称句型xuy中的u为该句型的简单短语。最左边的简单短语称为句柄。*+*3.6 3.

27、6 句型的分析句型的分析 例子：GS：SAB AAa AbB Ba BSb 解：SAB bBB baB baSbyBSbuxUU Sb是句型baSb的短语，简单短语S baB*解：SAB ASb bBSb baSbyBauxU a是句型baSb的短语，且是简单短语。US bBSb*yuxU ba是句型baSb的短语，但不是简单短语。所以：ba,a,Sb 是句型baSb的短语 a,Sb 是句型baSb的简单短语 a 是句型baSb的句柄。US ASb*Aba 解：SABASbbBSbbaSb定理3.1 1、每个句型都有一棵语法树，每个语法树的叶组成一句型。2、每棵子树的叶组成短语，每棵简单子树的

28、叶组成简单短语，最左简单子树的叶组成句柄。3、用语法树可证明每个句子都有一规范推导。构造语法树构造语法树GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a E EE+T E +T T E E +T T FE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*aE EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*aE EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a

29、 E E E+T E+T T T*F T T*F F F a F F a a a a a 看不出句型中的符号被替看不出句型中的符号被替代的顺序代的顺序上下文无关文法的语法树的用处上下文无关文法的语法树的用处用于描述上下文无关文法用于描述上下文无关文法句型推导句型推导的的直观方法直观方法 例例:GS:SaASASbAASSSaAba S a A S S b A a a b a句型句型aabbaa的的语法树语法树（推导树）（推导树）叶子结点：树中没有子孙的结点。叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记连接成的文从左到右读出推导树的叶子标记连接成的文法符号法符号串串，为，为GS的句

30、型。也把该推导树称的句型。也把该推导树称为该句型的语法树。为该句型的语法树。上下文无关文法的语法树上下文无关文法的语法树推导过程中推导过程中施用施用产生式产生式的的顺序顺序 例例:GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa一棵一棵语语法法树树表示了一个句型的种种可能的表示了一个句型的种种可能的(但未必是所有的但未必是所有的)不同推不同推导过导过程，包括最程，包括最左左(最右最右)推推导导。但是，一个句型是否

31、只。但是，一个句型是否只对对应应唯一的一棵唯一的一棵语语法法树树呢呢?一个句型是否只一个句型是否只有唯一的一个最左有唯一的一个最左(最右最右)推推导导呢呢?例：例：GE:GE:E iE iE E+EE E+EE E*EE E*EE (E)E (E)E E E+E E+E E*E i E*E i i i i i E E E*E E*E i E+E i E+E i i i i句型句型 i*i+i 的两个不同的最左推导：的两个不同的最左推导：推导推导1：E E+E E*E+E i*E+E i*i+E i*i+i推导推导2：E E*E i*E i*E+E i*i+E i*i+i例子：GS：SAB AA

32、a|bB Ba|Sb 字符串：bBABb短语：bB,AB,ABb简单短语：bB,AB句柄：bBSABbBbSBA定义3.10如果一个文法G存在某个句子,使得它有两棵语法树,则称G为二义性文法。例子：证明 G:EE+E|E*E|(E)|i 则G是二义性文法。因为句子i+i*i具有两棵语法树分别如图所示。EEE+i*EEiiEEE+i*EEii例子：证明 GS:SIf B Then S SIf B Then S Else S是二义性文法。If B1 Then If B2 Then S2 Else S3该句子具有二义性(其中S表示语句，Sx无条件语句，Bx表示布尔变量)，分析情况如下：If B1 T

33、hen If B2 Then S2 Else S3例子：If x1 then if x2 then y:=a else y:=b解释1:If x1 then if x2 then y:=a else y:=b解释2:If x1 then if x2 then y:=a else y:=bIfBThenSElseSSIfBThenS第一种：If B1 Then If B2 Then S2 Else S3第二种：IfBThenSElseSSIfBThenSIf B1 Then If B2 Then S2 Else S3改写文法如下：SM|UMIf B Then M Else M|S1UIf B T

34、hen S|If B Then M Else U怎样排除二义性：语义上限制。改写文法。M为匹配语句，U为非匹配语句。得到语法树如下：UIfBThenSSIfBThenSElseMMS33.7 有关有关文法实用中的一些说明文法实用中的一些说明 文法中文法中不含有不含有有害规则有害规则和和多余规则多余规则有害规则有害规则：形如：形如UU的产生式。会的产生式。会引起引起文法的文法的二义二义性性多余规则多余规则：指文法中：指文法中任何句子的推导任何句子的推导都都不会用到的规不会用到的规则则文法中文法中不含有不含有不可到达和不可终止的不可到达和不可终止的非终结符非终结符1）文法中某些）文法中某些非终结符

35、不在任何规则的右部出现非终结符不在任何规则的右部出现，该非终结符称为该非终结符称为不可到达不可到达。2）文法中某些）文法中某些非终结符非终结符，由它，由它不能推出终结符号不能推出终结符号串串，该非终结符称，该非终结符称为为不可终止不可终止。1.文法中不含有AA的规则 例:S0S1|01 无二义性,可以改为:S0S1|01|S 句子0011有二义性。S0S101S0S101SS0S101S 2.文法中不包含多余规则不可到达：所有推导均不会用到此规则不可终止：推导不出终结符号串例子:文法GS：(1)SBe (5)Ae (2)BCe不可终止 (6)CCf不可终止 (3)BAf (7)Df不可达 (4

36、)AAe 对文法G=(VN,VT,S,P),为了保证其任一非终结符A在句子推导中出现,必须满足如下两个条件：1.A必须在某句型中出现。即有S A,其中,属(VTVN)*。2.必须能够从A推出终结符号串t来。即A t,其中tVT*。因此检查文法是否包含多余规则是很有必要的。*+3.9 文法的等价转变换定理3.2 对任一文法G1都可以构造文法G2使得L(G1)=L(G2)，并且G2有这样的特点，即文法的初始符不出现于产生式的右部。例子：G:EE+E|E*E|(E)|i可改写为：G:EE EE+E|E*E|(E)|i 定理3.3 对任一文法G1都可以构造文法G2使得L(G1)=L(G2)，并且G2的

37、每个非终极符出现于某句型中。定理3.4 对任一文法G1均可构造文法G2使得L(G1)=L(G2)，且在G2中没有形如AB的产生式,其中BVN。证明：我们称形如AB的产生式为特型产生式。G2的构造算法是：1、对每个AVN，求A=D|A D,DVN2、令G1中所有的非特型产生式为G2的产生式。3、若有DA，且有Dx(非特型)，则令AxG24、删除无用的产生式。*例子：GA:AB|a Bb求解如下：保留：Aa Bb扩充：AB Bb AbGA：Aa|b Bb(多余)GA:Aa|b例子：设有如下文法 G1：AB|dD BA|C|b CB|c Dd|Da AB AB BA AAAB BC AC所以A=A,

38、B,C则有：A=A,B,C B=B,A,C C=C,A,B D=令G1中的非特型产生式为G2的产生式：G2：AdD Bb Cc Dd|Da再扩充产生式：G2：Ab|c BdD|c CdD|b所以G2A:AdD Bb Cc Dd|Da Ab|c BdD|c CdD|b 其中B和C不出现在任何句型中，因此可以删去相关的产生式。得出：G2A：AdD|b|c Dd|Da定理3.5 任一文法G1,可构造文法G2,使得L(G2)=L(G1)且G2中没有产生式。证明：G2的构造算法是：1、开始令=A|AG1 2、递归扩充：=D|DxG1,x+3、从G1删除所有产生式。4、从G1删去只能导出空串的非终极符。5

39、、设=A1,A2,An，VN=B1,B2,Bn若有产生式AC1C2Cn，则Ci有三种可能：CiVT，Ci，CiVN。如果Ci，则因为删去了所有产生式，以此扩充一产生式AC1C2Cn。重复这个过程，直至不出现新的产生式为止。例子：设有文法 G:AaBbD DBB B|b解：B DBB =B,D 则有=B,D删去产生式得：AaBbD DBB Bb 再扩充下面产生式：AabD AaBb Aab DB 定理3.6 设有文法G1,则可构造文法G2,使得L(G2)=L(G1),并且G2没有直接左递归的产生式。AA|AA AA|例子：AAab|cd AcdAAabA|A一般而言：AA1|A2|.|An|1|2|m 则有:A 1A|2A|m A A1A|2A|nA|例子：考虑下面文法 EE+T|T TT*E|F F(E)|i用上述方法可以改写为：ETE E+TE|TFT T*ET|F(E)|i