第二章形式语言与文法1

1、编编 译译 原原 理理第二章 形式语言与文法主要内容:v1 语言的形式描述.v2 语言与文法的形式定义.v3 文法的分类.v4 语法树及句型分析. 主要问题：v已知给定的文法求该文法表示的语言v已知语言求描述该语言的文法v求给定语句的短语、简单短语和句柄 1.符号串 符号串是形式语言中最基本的名词.一, 字母表与符号串v 1,字母表v 定义:元素的非空有穷集合v例:=a, b, c (a, b, c字母表)v =0, 1 (二进制数字字母表)v =汉字,数字,标点符号, (汉字组成的字母表)v 注:元素可是字母、数字或其他符号.v 字母表中至少有一个元素.2. 符号(字符) 定义：字母表中的元

2、素. 注:符号是字母表中不可再分解的最小单位. 3. 符号串定义：字母表中的符号组成的有穷序列. 例:=a, b, c 符 号:a, b, c 符号串:a, b, c, ab, ac, aa, ba, ca, abc, 例;设字母表A=0, 1 A中的符号:0, 1 A中的符串:0,1,01,10,00,11,001,010, ,01000, 显然:字母表上的符号串可形成一个集合(可数无穷)注: 1.符号串的组成是有序的.如:0110,abba 2.空符号串为不包含任何符号的符号串,记为: 3.符号串的长度:符号串所含符号的个数.设符号串为x,则x的 长度为 x 。 例: a =1 abc =

3、3 特别：| |0即空符号串的长度为零二符号串的运算连接运算定义：设x和y为符号串，则xy被称为x与y的连接设xabc，y10a则xyabc10a；yx10aabc符号串的方幂设有符号串x，则x的n次连接称为x的n次方幂，记为:x例：x （注:x ）xxx xxx x xxx xxxxxxxxxxxn次连接例:xabc则x ，x abc，x abcabc即x，x，xn0012322nn1n1011022符号串集合的乘积设ABxyx，y即:AB是x,且y的所有符号串xy构成的集合 例:设Aa，b，Bc，d则ABac，ad，bc，bd注： A=A=A A=A =A (其中 为空集) = 注: 不属

4、于 ， 即空符号串并不属于空集 4.符号串集合的方幂 设A为符号串集合,则定义 A= A=A A=AA A=AA=AA=AAA A=A A=AA =AAA (n个) 例:设A=a,b A= A=a,b A=aa,ab,ba,bb (A共有2 =4个长度为2的元素) A=AA=aa,ab,ba,bba,b =aaa,aba,baa,bba,aab,abb,bab,bbb (A共有2 =8个长度为3的元素)012322nn1n1012322335.符号串集合的正闭包A和闭包A .符号串集合的正闭包A 设A为符号串集合,则A定义为: A=A UA UA UUA U 例 设A=a,b则 A = a,b

5、 =a,b U aa,ab,ba,bb U =a,b,aa,ab,ba,bb,aaa,bbb, 即:A包括了由A上的元素a,b构成的所有符号串. .符号串集合A的闭包A. A =A U A U A UU A U (A =A U A ) 即A = U A = A U (A = A)123n012n0+例 设A =a,b 则 A = a,b =,a,b,aa,ab,ba,bb,aaa,bbb, 显然:对于所有的A,有A注意：闭包A 中包含着； A 中不包含着2.文法和语言的形式定义一.文法与语言的关系 语言:由定义在该语言字母表上,且按一定组成规则所构成的句子的集合. 即:字母表 字符串(句子)

6、(语言) 语言的描述 .当语言为有穷个句子的集合时,可用枚举的方法表示语言. .当语言为无穷个句子的集合时,则用有穷的语法规则(文法)描述无穷的句子的结构.语法规则例:汉语:人们无法列出全部的句子.但人们可以给出一些规则,用这些规则来说明(或定义)句子的组成结构. 如:汉语句子结构： = = =我你他 =王明大学生工人英语 = =是 学习 = 利用以上规则(文法)推导句子:我是大学生. 我 我 我是 我是 我是大学生利用上列文法:可以产生的句子:我学习英语,他学习,语,他是工人,.(很多句子) 利用上列文法不可产生“我大学生是”.它不符合以上规则. 文法的作用:不仅严格定义句子的结构,也是为了

7、用有限的规则把语言的全部句子描述出来。它是用有穷的集合刻画无穷集合的工具. 文法:语言的语法规则的有穷表示.(文法又称元语言)注: 1.有穷的文法通过推导的方法,可以推导出给定字母表上的所有句子. 2.描述文法的所有字符构成了语言的字母表. 3.通过文法在推导合法句子过程中会有多个句型产生. 4.合法的句型和句子是用字符串表示的.二. 文法的形式定义1. 规则(产生式,生成式,重写规则)是一个符号与一个符号串的有序对(A, ) 常写成:A = 或 A 其中:A是产生式的左部.它是某个字母表的正闭包中的一个符号.即A. 是产生式的右部.它是中一个符号串.(包括)2. 文法的形式定义 定义:文法G

8、是一个四元组,它是规则的非空有穷集合. G=(V ,V ,P,S) 其中:V 是文法产生式中的非终结符号集. V 是文法产生式中的终结符号集.NTNTV V =P是文法的产生式集。S是文法的开始符号（识别符号）。SVv非终结符号：出现在产生式的左边 ，能派生出符号和符号串的符号,常用大写字母表示，即，每一个非终结符号表示一定的符号串。它至少要在产生式左边出现一次。v终结符号：不能派生出符号串的符号，它是组成语言不可再分的基本符号，一般用小写字母表示。NTN例：文法G = (V ,V ,P,S)v其中 VN=S VT =0,1 P =S0S1,S 01一般约定: 1.只写出文法的产生式 2.第一

9、条产生式的左部是开始符号，且习惯用G开始符号表示。上例文法可写成：GS: S:=0S1 S:=01NT该文法G所描述的语言的字母表：V=VN VT=S，0, 1例：G:=| | := a|b|c|z := 0|1|2|9 v其中：VN= ， ， S = VT =a,b,c,z, 0,1,2,9 字母表：V=VN VT = , , ,a,b,c,z, 0,1,2,9 3.推导v有了文法，怎样由文法推导出与该文法相应的语言？为此引入了“推导”等概念。v直接推导v 设x,y是V*中任意符号串，若用一次产生式可以从x推出y，则称y是x的直接推导，记为：x y。（或称符号串x直接产生了符号串y，或称y直

10、接归约到x）例：设GS: S:=0S1|01则有如下一些直接推导：vS 01 （利用S:=01 ）vS 0S1 （利用S:=0S1 ）v0S1 0011 （利用S:=01 ）v0S1 00S11 （利用S:=0S1 ）v推导（推导）v若使用若干次规则式可以从x推出y，则称y为x的推导，记为：x y（或称x产生y，或称y规约到x），或记为：x yv例：上例：v0S1 00S11 000S111 00001111v 0S1 + 00001111v （推导长度为3）v广义推导（推导）v若x y或者xy（表示0步推导），则写为x y （反之亦然，即：x y，当且仅当x y或者xy ）v例，上例中：v0

11、S1 +00001111也可记为：0S1 *00001111v注：直接推导、推导、广义推导的区别：v推导长度n不同：v直接推导：n1v推导：n 1v广义推导：n 0 (0步推导：如Ss) 包涵 包涵4.句型和句子v设有文法GS,若有S x,则称符号串x为文法GS的句型。v换句话说：凡是由识别符号推导出来的任意符号串称为句型。v句子：仅有终结符号组成的句型称为句子。v区别：符号串x(VNVT)*;x称为句型，符号串xVT*;x称为句子。v例：GS: S:=01|0S1 S 01 S 0S1 00S11 000111可见：01,0S1,00S11,000111均为文法GS的句型。其中：01，000

12、111为句子（说明句型包含了句子，句子是特殊的句型）但是：符号串000S11,0000111都不是文法GS的句型。v例：已知文法GE： E:=E+E|E*E|(E)|i(其中:VN =E VT=+,*,i,(,) ) 试证明:符号串(i*i+i)是文法GE的一个句子。v证明：只要证明(i*i+i)是文法GE的一个存在的推导）(需从开始符号出发 )E=(E) =(E+E) =(E*E+E) =(i*E+E) =(i*i+E) =(i*i+i)即：E= (i*i+ i)所以,符号串(i*i+i)是文法GE的一个句子。三、语言的形式定义：三、语言的形式定义：v定义：由文法GS产生的所有句子的集合。即

13、：L(GS) = x|S=x,且xV*v注：v一旦文法给定，语言就确定。v语言L(G)是V*的子集。（语言是字母表中终结符号串闭包的子集）即：属于L(G)的句子一定属于V*反之,属于V*的符号串x不一定属于L(G)。TTTT+v例：已知文法GS：S:=0S1|01v求:L(G)=?v解：分析：S=0S1=00S11=000S111=0n-1S1n-1=0n1n即：S=0n1nG描述的语言：L(GS) = 0n1n | n1 语言句子：由0和1组成，且0在1的前面，0和1个数相等。但： VT0,1,00,01,10,11,000,111,0000,0011,1111,，可见L(G)仅是VT的真子

14、集。1.已知文法求语言已知文法求语言方法：推导法 （1）利用文法产生式，从文法开始符号开始推导出每个句子； （2）观察组成句子结构的规律，用通式写出。例：已知文法：GS: S0S|1S|,求L(G)=?解：S S=0S=0 00，000，0000，. S=1S=1 11，111，1111，. S=0S=01S=01 S=0S=01S=011S=011 , . 以一个0开头，后面是若干个1组成的句子。 S=0S=00S=001 ， . 以两个0开头，后面是若干个1组成的句子。 以若干0开头，后面是若干个1组成的句子。 以若干1开头，后面是若干个0组成的句子。 以若干0或1开头，中间任意个（包括没

15、有）0或1，最后0或1结尾的所有句子。L(GS) = ,0,1,01,11,00,10,011,110,101, = x | x0,1* 例：已知GS： S =aB|bA A =a|aS|bAA B =b|bS|aBB求：L(GS)？解： S=aB=abS=aB=abS=abaB=ababS=aB=aaBB=aabB=aabb又S=bA=baS=bA=baS=babA=babaS=bA=bbAA=bbaA=bbaaL(GS) = x|xa,b,且x中a，b个数相同反过来，给定语言L(G)后，若要写出能正确描述此语言的文法，是有一定难度的。+例：试对语言L(G) = (n)n|n=0,1,2,构

16、造相应的文法G。解：（1）首先分析L是由怎样的符号串x组成的。当n=0时，x=当n=1时，x=()当n=2时，x=()当n=3时，x=()L(G) = ,(),(),(),2.已知语言求文法已知语言求文法(2) 归纳集合L(G)的组成特点：vL(G)中每个符号串呈对称形式，即 ( 和 )成对出现。vL(G)为无穷集合，因此描述出的规则中必然含有递归定义。vL(G)中的终结符号只有两个:( 和 )。(3) 写出规则：S =(S)| 即，定义此语言L(G)的文法：G: VT = (,), VN = S,S为开始符号，产生式： P： S =(S)| 设计文法的思考方法：设计文法的思考方法： a.搞清

17、楚语言句子组成的规律： 有哪些终结符构成、终结符之间的次序怎样、个数及初始值如何 ； b. 用非终结符表示多个相同的终结符结构的递归形式； c. 定义多个非终结符的 之间的结构关系。用产生式形式写出。 例：给出语言L(G) anbncm|n1,m0的对应文法解：分析： 将anbn看成一个整体用一个非终结符号A来表示，cm看成另一个整体用非终结符B来表示。 设S为G的识别符号，则有S =AB，而由A推出anbn，B推出cm 。 保证anbn成立，即a,b个数相等，且大于等于1。 所以可以用产生式：A =aAb|ab 又因为m可以为0 ,所以 S:=AB改写为S:=AB|A;又由于A =aAb|a

18、b，则对B容易看出B =cB|c S =AB|AS =ABA =aAb|ab或者：A =aAb|abB =cB|cB =cB|例：设字母表a,b,试设计一个文法，描述语言La ,b | n1解：分析语言由怎样的符号串组成。当n=1时，L=aa,bb当n=2时，L=aaaa,bbbb当n=3时，L=aaaaaa,bbbbbbL=aa,bb,aaaa,bbbb,aaaaaa,bbbbbb,即：语言由偶数个a和偶数个b的符号串组成。所以，描述语言的文法：GA:A =aa|aaB|bb|bbDB =aa|aaBD =bb|bbD2n2n可以写出另一个文法：G1A: A =B|D B =aa|aBa D

19、 =bb|bDb可见，对于给定语言，描述该语言的文法不是唯一的。注： 描述一个语言的文法不是唯一的 若不同的文法产生相同的语言，则称这些文法是等价的。例：设有文法 G1=VN,VT,P,A其中：VN=AVT=a,bP=A:=ab显然：L(G1)=ab文法G2=VN,VT,P,A其中： VN =A,B VT =a,bP=A:=Bb,B:=a显然： L(G2 )=ab即：L(G1)=L(G2)，且G1= G2若语言在语法上等价，并不一定意味着语义上等价。若语言在语法上等价，并不一定意味着语义上等价。例：G3S和G4S它们的VN和VT相同：VN =S,A, VT =a,b,c而, G3S的P为：S:

20、=A|S-AA:=a|b|c G4S的P为：S:=A|A-SA:=a|b|c显然：G3 S和G4 S等价（语法），因为它们都产生相同的句子：a,b,c,a-b-c,a-b-b-c,但：句子的含义（语义）不一定相同：例如：由G3S推导出的句子：a-b-c其含义为(a-b)-c 由G4S推导出的句子：a-b-c其含义为a-(b-c)文法应该能准确地描述语言，不能扩大或缩小。例：设计一个表示所有标识符的文法。解：分析：标识符：字母|字母开头的字母数字串,用B表示标识符；L-字母；D-数字：则GB的产生式P: B:=L|BL|BDL:=a|b|c|x|y|zD:=0|1|2|9 可以表示a1b2c3若

21、将产生式设计成P1：B:=L|BDL:=a|b|c|x|y|zD:=0|1|2|9表示：字母开头，后面全是数字：abc1，不能表示a1b2c3显然：P1 缩小了标识符的表示，比P描述的范围缩小了若将产生式设计成P2：B:=L|BL|BD|DL:=a|b|c|x|y|zD:=0|1|2|9显然: P2也不能准确地描述，扩大了P的描述范围3 与语法分析有关的概念与语法分析有关的概念 一、短语、简单短语与句柄一、短语、简单短语与句柄v短语：设有文法GS，W=是G的一个句型。若有识别符号S A,且A +,则称是相对非终结符A的句型w的短语。 注意：是句型W的短语条件是： 由A多步推出（推导次数2）；

22、是句型W的子串。特别，如果上式A=+为： A （ 由A一步推出）则称为句型w的简单短语（直接短语）例：设有文法G=(S,A,B,a,b,P,S)其中P为：1. S:=AB2. A:=Aa3. A:=bB4. B:=a5. B:=Sb试求句型baSb,bBABb和baabaab全部短语，简单短语。解：先讨论句型w=baSb,其中子串b,a,S,ba,aS,Sb,baS,aSb.baSb是句型w的短语吗？ 根据短语定义，可由句型的推导中找到全部短语及简单短语。最左推导：1345S=AB=bBB=baB=baSbbBabaSbbaSbbB不是W的子串由此可见，下式成立： S=*S,且S=+baSb

23、baSb是短语(句型本身是短语) (注意:主要求异于句型本身的短语). 又 S=*AB,且B=Sb 句型baSb中子串Sb也该句型（相对于B）的短语,且是简单短语。 又 S=*bBSb,且B=a 句型baSb中子串a也该句型（相对于B）的短语,且是简单短语。 又 S=*ASb,且A=+ba 句型baSb中子串ba也该句型（相对于A）的短语.注:短语是句型中的子串,在推导中不是句型中的子串不能作短语。 如:S=*ASb ,A=bB;则由于bB不是句型baSb中子串,所以他不是该句型的短语.sb，a，ba是句型baSb异于自身的短语(句型本身是短语),其中Sb,a是简单短语。最右推导： 同样可求出

24、同上的该句型的短语,同学们可自求. 可用同样的方法分析句型bBABb和baabaab的全部短语和简单短语（略）同学们也可自求。v句柄：句型的最左简单短语 特征：句柄至少是简单短语（某规则的右部），且为最左简单短语（具有最左性）。 例如：上例中a是最左简单短语句柄。1534S=AB=ASb=bBSb=baSb 注注:短语、简单短语与句柄的关系短语、简单短语与句柄的关系: 它们都是针对某个句型而言的,离开了句型来谈短语、简单短语与句柄,是毫无意义的. 句柄一定是简单短语和短语,反之不成立. 简单短语和句柄一定是某个产生式的右部符号串,短语不是(他作为我们寻找和判断句型的简单短语的依据);但文法中产

25、生式的右部符号串不见得都是简单短语或句柄.二、最右（左）推导，规范推导和规范规约，规范句型二、最右（左）推导，规范推导和规范规约，规范句型(1) 最右（左）推导：在推导过程中，任何一步=都是对中最右（左）非终结符进行替换。称为最右（左）推导。v特别：最右推导称为规范推导。得到的句型称为规范句型。例：设有文法G的规则集P为：S:=ABA:=Aa|bBB:=a|Sb给出babaab的最右（左）推导解：最右推导：S=AB=ASb=AABb=AAab=AbBab=Abaab=bBbaab=babaab规范推导。 最左推导：S=AB=bBB=baB=baSb=baABb=babBBb=babaBb=ba

26、baab忽左忽右推导： S=AB=ASb=bBSb=baSb右左左v归约：归约：将句型中某一个子串用一个非终结符替换的过程。将句型中某一个子串用一个非终结符替换的过程。若有A:= ,则xAy=xy，有：xy=xAy规约(2) 规范归约（又称最左规约） ：规范推导（最右推导）的逆过程。例：GN1: N1:=NN:=ND|DD:=0|1|2 最右推导：N1=N=ND=N2=D2=12 最左规约： 12=D2=N2=ND=N= N1归约：从句子最左符号开始，若是产生式右边符号串，用左边的非终结符替换，直至归约到文法的开始符号。三、文法的递归三、文法的递归1递归规则递归规则v若文法中有形如规则:A:=

27、A，称为规则左递归。v若文法中有形如规则:A:=A，称为规则右递归。v若文法中有形如规则:A:=A，称为规则递归。（规则递归称为直接递归）文法的递归性文法的递归性v如果有推导A=A，称文法左递归v如果有推导A=A，称文法右递归v如果有推导A=A，称文法递归（文法递归称为间接递归）+例：GN1: N1:=NN:=ND （规则左递归：直接递归）例：GU:U:=VxV:= U y|aU=Vx= U yx (左递归文法:间接递归)GU的规则中无规则左递归，但在推导过程中存在左递归，所以GU是左递归文法。作用：用递归规则可以定义无穷集合的语言。例：GA:A:=BB:=D|DD|DDD|，D:=0|1|2

28、|结论：若语言为无穷集合，描述语言的文法一定是递归的。可用 A:=AD|D替代四、语法树与文法的二义性四、语法树与文法的二义性v句型的语法树句型的语法树(1) 作用：作用：直观地求出一个句型的短语，简单短语和句柄。直观地表示一个句型（或句子）的推导或归约过程，即它是语法分析的工具。1.可以判断一个文法的二义性问题。 (2) 句型推导的语法树表示句型推导的语法树表示用树型结构直观地表示一个句型的推导过程，称为该句型的一棵语法树（又称推导树）语法树的构成： v树的根为文法的识别符号；v树的中间结点是文法的非终结符；v叶子结点为文法的终结符号或非终结符号。v若一个标记为U的结点，它有标记依次为x1x

29、2x3xn 的直接后继结点，即U:=x1x2x3xn 必定是文法G的一条规则。一个句型的推导过程用语法树表示：例：设有文法GE：E:=E+T|E-T|TT:=T*F|T/F|FF:=(E)|i根据推导，画出句型（T+i)i-F的语法树： 第一步写出推导，第二步画树。最右推导：E=E-T=E-F=T-F=T*F-F=T*i-F=F*i-F=(E)*i-F=(E+T)*i-F =(E+F)*i-F =(E+i)*i-F =(T+i)*i-F E T T T * F F i ( E ) - F E + T T F i 先画右子树，然后从右向左画其它子树 从左向右将叶子结点的符号串连接起来构成了所求的

30、句型 E 最左推导：从左向右画子树。子树：由某一结点连同所有分支组成的部分。简单子树：包括叶子在内的单层单层子树。(3) 语法语法树中的短语，简单短语和句柄的概念中的短语，简单短语和句柄的概念短语：子树的末端结点形成的符号串是相对子树根的短语。简单短语：简单子树末端结点形成的符号串是相对于简单子树根的简单短语。句柄：最左简单子树的末端结点形成的符号串是句柄。利用语法树求句型的短语，简单短语和句柄：利用语法树求句型的短语，简单短语和句柄：例：设有文法GE：E:=E+T|E-T|TT:=T*F|T/F|FF:=(E)|i求 (T+i)*i F的短语，简单短语和句柄。（前面的树） (T+i)*i F

31、为句型的相对根E的短语。 (T+i)*i 为句型的相对于以T为根的子树的短语。 (T+i)为句型的相对于以F为根的子树的短语。 T+i为句型的相对于以E为根的子树的短语。 T为句型的相对于以E为根的子树的短语，且为简单短语。第一个i为句型的相对于以F为根的子树的短语，且为简单短语。第二个i为句型的相对于以F为根的子树的短语，且为简单短语。F为句型的相对于以T为根的子树的短语，且为简单短语。 在四个简单短语T，i，i，F中，T为句型的句柄例：设有文法GS：S:=(T)|a|T:=T,S|S求句子（a,(a,a)）最右推导的逆过程（最左归约）每一步的句柄。最右推导：S=(T)句柄:（T）=(T,S

32、)句柄:T,S=(T,(T)句柄:(T)=(T,(T,S) 句柄:T,S=(T,(T,a) 句柄:第三个a=(T,(S,a) 句柄:S=(T,(a,a) 句柄:第二个a=(S,(a,a) 句柄:S=(a,(a,a) 句柄:第一个a利用语法树求归约中的句柄 S ( ) T , S ( T ) T S T , S a 由下向上，自左向右 剪枝求最左规约的句柄。 （句柄是自底向上语法分析的规约依据） S a a v文法的二义性文法的二义性v所谓文法的二义性是指文法存在的某个句子对应两棵不同的语法树（或说存在两个不同的最左（右）推导）。例：文法GE：E:=E+E|E*E|(E)|i 句子i*i+i有两

33、个不同的语法树（最左推导）E =E+E=E*E+E =i*E+E =i*i+E =i*i+i E E E E * i i + E i 利用语法树判断文法的二义性E=E*E=i*E=i*E+E=i*i+E=i*i+iGE具有二义性v文法的二义性会导致对二义性文法的句子结构产生多种不同的理解，造成语法分析和语义理解的不确定性。希望描述语言的文法是无二义性的。 E E E E + i i * E i v文法二义性的消除文法二义性的消除(1) 不改变文法中原有的语法规则，仅加进一些语法的非形式规定。v例如，对于上例文法GE,不改变已有的4条规则，仅加入运算符的优先顺序和结合规则；即*优先于+；+,*服

34、从左结合。这样，句子i*i+i只有唯一的一棵语法树（如上例的第一个图）。(2) 改写文法。把排除二义性的规则合并到原文法中，构造一个等价的无二义性的文法。v例如，对于上例文法GE,将运算符的优先顺序及结合规则（*优先于+；+,*服从左结合）加到原文法中：E:=E+T|TT:=T*F|FF:=(E)|i 则句子i*i+i只有唯一的语法树可见：对于有二义性文法描述的语言，有时可以找到等价的无二义性文法来描述它。 E E T T * F F + F i i i 例：某语言的条件语句的文法G为：S:=if b S|if b S else S |A (A为其它语句)证明G具有二义性，并消除之。分析：该文

35、法的句子if b if b A else A对应的两棵不同的语法树 S if S S else A b S A b if S if S if b A b S A else S A (a) (b) 所以G是具有二义性的文法。消除二义性： (1).不改变已有规则，仅加入一项非形式语法规定：else与前面最接近的if配对。这时句子if b if b A else A只唯一对应语法树(a).(2).改造文法G为G:S:=S1|S2S1:=if b S1else S1 |AS2:=if b S|if b S1 else S2 S if S S1 else A b S1 A b if S1 S2 注：v文

36、法的二义性和语言的二义性是两个不同的概念。通常只说文法的二义性，而且不说语言的二义性，因为描述语言的文法不唯一，可能存在一个文法G有二义性，一个文法G无二义性：使L(G)=L(G)v如果语言是二义性的，则它不存在无二义性的文法，这样的语言称为先天二义性语言。v 如：L=a b c | i=j或jk,i,j,k1便是这种语言。v已证明，不存在一个算法，它能在有限步骤内确切地判定任意给定一个上下文无关文法是否为二义性文法，或它是否会产生一个先天二义性的上下文无关语言。（只能用画树方法说明是否二义性问题。）i jk4 文法与语言的分类文法与语言的分类v分类的依据：将文法中的规则施加不同的限制。v文法

37、被划分为4类：03型文法一、一、0型文法（短语文法）型文法（短语文法）若文法G的规则式具有形式：:=(其中(VNVT)+,(VNVT)*)即，都是符号串对它们没有作任何限制。（也可以|）v由0型文法产生的语言称为0型语言v0型文法的能力相当于图灵机。例：有产生式P：S:=0AB1B:=0B:=SA|01A1:=SB1A0:=S0Bv|为0型文法v该文法推不出任何句子：L= 二、二、1型文法（上下文有关文法）型文法（上下文有关文法）若文法G中规则呈现下列的形式：A:= u其中：AVN，u (VNVT)+, , (VNVT)*则称G为1型文法，所产生的语言为1型语言。由于利用规则将A替换为u时，必

38、须考虑A在上下文中出现的情况，即与上下文有关，故又称为下文有关文法。v特点：每个规则式：|左边|右边|；规则右部符号个数至少与左部符号个数一样多。例：设有G=(VN ， VT ，P，S)VN=S,B,CVT=a,b,cP:S:=aSBCS:=aBCCB:=BCaB:=abbB:=bbbC:=bccC:=cc这是一个1型文法，它描述了如下语言L(G)=an bn cn |n1三、三、2型文法（上下文无关文法）型文法（上下文无关文法）若文法G中规则呈现如下形式：A:= 其中，AVN， （VNVT）*则称G为2型文法，由它产生的语言称2型语言。由于利用规则将A替换成时与其上下文无关，即与A在上下文出

39、现的情况无关，所以又称这种文法为上下文无关文法。例：文法G的产生式P：E:=E+E|E*E|(E)|i 属于2型文法。v特点：2型文法产生式的左部是单个的非终结符，右部为终结符和非终结符组成的符号串。v注：上下文无关文法可以描述当今的程序语言 四、四、3型文法（正规文法）型文法（正规文法）如果对2型文法的产生式作进一步的限制，限制产生式的右部是单一终结符或单一终结符和单一非终结符组成。若文法G中的规则式，呈现如下形式：右线性文法 A:= aBA:= a 或左线性文法 A:= BaA:= a其中：A，BVN，aVT称G为3型文法。或称正规（正则）文法，由它产生的语言为3型语言或正规语言。+例：设

40、有G=( V ,V ,P,S)P:S:=A0|B1A:=0|1B:=0|1左线性文法注：文法类型是由产生式的形式来划分：NT即：G0 G1 G2 G3表格：文法类型与产生式文法类型文法类型产生式限制产生式限制0:=(|0, |)：无限制文法1:= (1|):上下文有关文法2A:=(（VNVT)+) : 上下文无关文法3A:=a A:=aA:=aB 或 A:=Ba :正则（规）文法或左（右）线性文法文法的分类对于程序设计语言的编译程序有重要的意义。v程序语言的词法规则属于正则文法编译程序词法扫描器采用正则文法识别技术。v程序语言的语法和语义部分的规则属于上下文有关文法。但考虑高功效而采用上下文无

41、关文法定义语法编译程序语法分析器采用上下文无关文法识别技术。 描述程序语言结构的文法描述程序语言结构的文法：v程序语言的词法由正则文法描述词法由正则文法描述。v程序语言中的局部语法由上下文无关文法描述语法由上下文无关文法描述。v程序语言中的语义由属性文法描述语义由属性文法描述。5 文法的实用限制在实际使用中，对文法要作一些假定或限制。例如限制文法不含有有害规则或多余的规则。一、文法中不能含有有害规则一、文法中不能含有有害规则U:=Uv这样的规则显然没有必要，而且会引起二义性。v例如，文法GS: S:=0S1|01是无二义性的，若将规则写成：S:=0S1|01|S则文法G不再是无二义性的。就句子

42、0011而言，可画出多棵语法树。二、文法中不能含有多余的规则二、文法中不能含有多余的规则v文法的规则中不含有无用的非终结符和不可到达的符号。1.无用的非终结符号（不可终止符号）无用的非终结符号（不可终止符号） 如果从文法中某个非终结符推不出终结符号串，则称该非终结符号为无用的非终结符2.不可到达的符号不可到达的符号 如果文法规则中的一个非终结符（不是识别符号），不出现在文法的任何一条产生式的右部，则称该非终结符为不可到达的符号.例：已知文法G=( VN，VT，P，Z)其中， VN=Z,A,B,C,D,VT=e,fP: Z:=BeA:=Ae|eB:=Ce|AfC:=CfD:=fC为无用的非终结符

43、，因为C在推导中没有终结符号替换。C:=cf 和B:=Ce多余应该删去。D为不可到达的符号，即D:=f在推导中不起作用，应该删去。 删除多余的规则后的文法为：Z:=BeA:=Ae|eB:=Afv文法中不含多余规则的充要条件：U(UVN)必须出现在某个推导的句型中，即：Z=xy。（U为文法的非终结符）能从U推出终结符号串，即：U=+t(tVT)满足上述条件的文法称为压缩过的或化简了的。v对文法的限制还有：文法中不含有左递归规则U:=U。（消除左递归在后面会讲到）对于上下文无关文法，限制U:= ，即不含有空规则。（可以变换消除）等等6小结小结本章主要解决的问题：v已知文法，确定该文法描述的语言v已

44、知语言，设计描述该语言的文法v求句型的短语，简单短语及句柄v文法二义性的判断一、已知文法，确定该文法描述的语言一、已知文法，确定该文法描述的语言1.语言的定义：文法G产生句子的全体。即L(GS)=x|S=+x,且xVT*2.语言的描述：用自然语言：L=x|xa,b+,且x中a，b个数相同用式子：L=a2nbb|n0用正规式：L=bna| n0，可用：L=b*a来描述。3.求法：根据给定文法，从文法的识别符号开始，推导出所有的句子，然后归纳写出语言描述的三种形式之一。例：有如下文法GS：S:=ABA:=aAb|abB:=Bc|求：L(GS)=?解：S=AB=abB=abS=AB=abB=abBc

45、=abcS=AB=aAbB=aabbB=aabbS=AB=aAbB=aabbB=aabbBc=aabbcL(GS)=anbnc | n1, m0m例：已知文法GS为：S:=dABA:=aA|aB:=Bb|GS产生的语言是什么？GS能否改写为等价的正规文法？解：首先分析GS产生的语言：语言的句子都是d开头，后跟a或b，且a，b个数不等。L(GS)=danbm| n1, m0 根据语言的特点：a,b的个数n与m没有相互制约的关系，所以将an与bm分别构造，得到正规文法：GS：S:=dA A:=aA|aB|a B:=bB|b二、已知语言，设计描述该语言的文法二、已知语言，设计描述该语言的文法文法的形

46、式定义：四元组GS=( VN,VT,P,S)，主要求产生式P。分析已知语言句子的结构特征，设计相应的产生式，但求出的文法不唯一。设计出的文法必须能准确地定义已知的语言，不能超出或缩小所定义的语言范围。1.若语言是句子的无穷集合，则设计的文法一定是递归的。例：例：已知L=x| xa,b,c*, 且x中符号的排列是对称的。（例如：aabcbaa或aabbaa等） 试写出产生该语言的文法。解：解：句子x中符号有多个，所以有递归产生式存在。又因为句子x中符号是对称的，保证对称的推导出每个符号就可以了。 GZ: Z:=aZa|bZb|cZc|a|b|c|例：例：给出描述：L=a2m+1bm+1|m0a2mbm+2|m0的文法。解：解：将句子的描述变形： a2mabbm和a2mbbbm发现句子中前后的a和b的个数有倍数关系于是：GZ: Z:=aaZb|ab|bb例：例：写一文法，使其语言是偶整数的集合（不允许0