ch3 文法和语言.ppt

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

1、1文法和语言的形式定义文法和语言的形式定义文法的类型文法的类型上下文无关文法及其语法树上下文无关文法及其语法树上下文无关文法上下文无关文法的句型分析的句型分析有关文法实用中的一些说明有关文法实用中的一些说明第三章第三章文法和语言文法和语言语言的词法和语法描述工具，用有穷规则语言的词法和语法描述工具，用有穷规则描述语言的无穷句子。描述语言的无穷句子。3.1 文法的直观概念文法的直观概念z采用巴克斯范式BNF，规则的集合来描述z元符号:=,|,|,z例子例子p32p32 :=:=2v高级语言都是由句子(程序)的集合组成v语言是字母表上定义的，按照一定规则构成的字母表上基本符号串(源程序)的集合。v

2、字母表：是某语言基本符号的集合，如if是字母表中的一个元素，保留关键字、标示符、运算符、字母、数字和一些专用符号，如/*，；等。描述单词和语法的字母表不同。v符号串：字母表中符号组成的任何有穷序列。如字母表=0,1上的符号串0011003.2 符号和符号串符号和符号串z符号串的头尾符号串的头尾 z=xy是符号串，x是z的头，y是z的尾。x非空，y是固有尾；y非空，x是固有头固有头 例子z=abc,头,a,ab,abc z符号串的方幂符号串的方幂 x是符号串，将自身链接n次的符号串z=xxx=xn,设x=ab,则x0=,x1=ab,x2=abab,xn=xn-1xz符号串的集合符号串的集合 若集

3、合A中所有元素都是某字母表上字符串。z符号串集合的乘积符号串集合的乘积-笛卡尔乘积笛卡尔乘积4z符号串集合的乘积符号串集合的乘积-笛卡尔乘积笛卡尔乘积 集合集合A和和B的乘积的乘积AB=xy|x A,y B A=a,b,B=c,d,AB=ac,ad,bc,bd,A=A=Az字母表集合的闭包字母表集合的闭包*定义在字母表定义在字母表上的所有有穷长字符串的集合。*=0 1 2 n=0+正闭包+=1 2 n=*例子：例子：=0,1，*=,0,1,00,01,10,11,000,无穷 +=0,1,00,01,10,11,000,563.3文法和语言的形式定义文法和语言的形式定义如何来描述一种语言？如何

4、来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示将句子逐一列出来表示.如果语言是无穷的，找出语言的有穷表示。语言的如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：有穷表示有两个途经：生成方式生成方式(文法文法)：语言中的每个句子可以用严格：语言中的每个句子可以用严格定定义的规则来构造。义的规则来构造。识别方式识别方式(自动机自动机)：用一个过程，当输入的一任意：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并串属于语言时，该过程经有限次计算后就会停止并回答回答“是是”，若不属于，要

5、么能停止并回答，若不属于，要么能停止并回答“不是不是”，要么永远继续下去。，要么永远继续下去。(自动机与文法等价自动机与文法等价)7语言中的每个句子可以用严格定义的规则语言中的每个句子可以用严格定义的规则来构造。来构造。z规则：规则：也称重写规则重写规则、产生式产生式或生成式生成式，是形如或=的(，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称作规则的右部。z文法的定义文法的定义z推导的概念推导的概念z句型、句子和语言的定义句型、句子和语言的定义8文法定义文法定义文法G定义为四元组(VN，VT，P，S)其中VN:非终结符号(或语法实体，或变量)集；VT

6、:终结符号集；P:规则的集合；VN，VT和P是 非空有穷集。S:称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现。VN和VT不含公共的元素，即VN VT=用V表示VN VT，称为文法G的字母表或字汇表9文法的定义文法的定义例例 文法文法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 00 99 S=11 文法的写法文法的写法 元元符号:,=,|,=,|,习惯习惯 大写字母表示非终结符大写字母

7、表示非终结符 小写字母表示终结符小写字母表示终结符(1)(1)GS:GS:SaA SaAb Aab Aab AaA AaAb A A (2)GS:(2)GS:Aab|aA Aab|aAb|SaASaAb描述文法的规则成为巴克斯范式描述文法的规则成为巴克斯范式BNFBNF。也可以用。也可以用语法图来表示。模仿第语法图来表示。模仿第2 2章章p13-15p13-15写出上例的语写出上例的语法图法图.12推导的定义推导的定义直接推导直接推导“”是文法是文法G G的产生式，若有的产生式，若有v,wv,w满足：满足：v=,w=,v=,w=,其中其中VV*,V,V*则称则称v v直接直接推导推导到到w,w

8、,记作记作 v v w w 也称也称w w直接直接归约归约到到v v例：例：G G：S0S1，S01 0S100S1100S11000S111000S11100001111 S 0S113推导推导.(.).()VAR;BEGINREAD()END.VARA;BEGINREAD()END.(A)VARA;BEGINREAD()END.VARA;BEGINREAD(A)END.(A)14推导的定义推导的定义若存在若存在v=w0w1.wn=w,(n0)则记为则记为v=+w，称作，称作v推导出推导出w，或，或w归约归约到到v若有若有v=+w或或v=w，则记为则记为v=*w15例：例：G G：S0S1，

9、S010S100S1100S11000S111000S11100001111 S 0S100S11000S11100001111 S=+00001111 00S11=*00S1116句型、句子的定义句型、句子的定义z句型句型有文法有文法GS，若，若S=*x，则称，则称x是文法是文法G的句型。的句型。z句子句子有文法有文法GS，若，若S=*x，且，且xVVT T*，则称，则称x是文法是文法G的句子。的句子。例：例：GSGS：S0S1，S01S 0S1 00S11 000S111 00001111G的句型S,0S1,00S11,000S111,00001111G的句子00001111,0117句型

10、、句子句型、句子例：例：GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|aE EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a句子：用符号句子：用符号a，+，*，(和和)构成的算术表达式构成的算术表达式18(文法生成的文法生成的)语言的定义语言的定义由文法由文法G生成的语言记为生成的语言记为L(G),它是文法它是文法G的的一切句子的集合一切句子的集合:L(G)=x|S=*x，其中，其中S为文法的开始为文法的开始符号，且符号，且x VVT T*例：例：G G：S0S1，S01 L(G)=0n1n|n1例例 文法文法GS：（1）SaSBE（

11、2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEeeL（G）=anbnen|n1 G生成的每个串都在生成的每个串都在L(G)中中L(G)中的每个串确实能被中的每个串确实能被G生成生成20文法的等价文法的等价z若若L（G1）=L（G2），则称文法），则称文法G1和和G2是是等价的。等价的。如文法如文法G G1AA：ADB ADB 与与G G2SS：S0S1 S0S1 等价等价 ADE S01 ADE S01 EAB EAB D0 D0 B1 B1213.4文法的类型文法的类型 通过对产生式施加不同的限制通过对产生式施加不同的限制，Chomsky将文法分为将文法分为四

12、种类型四种类型：0型文法：对任一产生式型文法：对任一产生式，都有，都有(V(VN NVVT T)+，(V(VN NVVT T)*1 1型文法：型文法：对任一产生式对任一产生式，都有，都有|，仅仅仅仅 SS除外除外2 2型文法：型文法：对任一产生式对任一产生式，都有，都有VVN N 3 3型文法：型文法：任一产生式任一产生式的形式都为的形式都为AaBAaB或或AaAa，其中，其中AVAVN N ，BVBVN N ，aVaVT T*22文法的类型文法的类型例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GSGS：SCDSCDAbbAAbbA CaCA CaCABaaBBaaB Cb

13、CB CbCBBbbBBbbBADaDADaD Ca CaBDbDBDbD Db DbAabDAabD23文法的类型文法的类型例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SABABABS|0BS|0BSA|1SA|1243 3型文法型文法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 d25文法的类型文法的类型2型文法型文法1型文法型文法0型文法型文法四类四类文法文法之间之间的的逐级逐级“包含包含”关系关系3型文法型文法26文法和语言文法和语言0

14、型文法产生的语言称为型文法产生的语言称为0型语言型语言1 1型文法或上下文有关文法（型文法或上下文有关文法（CSG ）产生的语言产生的语言称为称为1 1型语言型语言或上下文有关或上下文有关语言（语言（CSL）2 2型文法或上下文无关文法（型文法或上下文无关文法（CFG ）产生的语言产生的语言称为称为2型语言型语言或上下文无关或上下文无关语言（语言（CF L）3 3型文法或正则（正规）文法（型文法或正则（正规）文法（RG）产生的语言产生的语言称为称为3型语言型语言正则（正规）正则（正规）语言（语言（RL）27文法和语言文法和语言 四种文法之间的关系四种文法之间的关系 是将产生式做进一步是将产生式

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

16、型文法（上下文有关文法）：产生式的形式为式为1 1AA2 21 12 2，即只有，即只有A A出现在出现在1 1和和2 2的上下文中时，才允许的上下文中时，才允许取代取代A A。其识。其识别系统是线性界限自动机。别系统是线性界限自动机。29 2型文法（上下文无关文法型文法（上下文无关文法CFG）：）：产生式产生式的形式为的形式为AA，取代取代A A时与时与A A的上下文无关。其的上下文无关。其识别系统是不确定的下推自动机。识别系统是不确定的下推自动机。描述语法的构成。描述语法的构成。3型文法（正规文法型文法（正规文法RG）：）：文法文法G=(VN,VT,P,S),其中P中的产生式的形式为产生式

17、的形式为AA B B或或者者AA，其中，其中A A和和B B是非终结符号，是非终结符号，V VT T*。产生的语言是有穷自动机（产生的语言是有穷自动机（FA）所接受的集合。）所接受的集合。复习复习z规则、文法、推导、句型、句子、语言规则、文法、推导、句型、句子、语言z文法的等价性文法的等价性z文法分类文法分类z有用文法是上下文无关文法和正规文法有用文法是上下文无关文法和正规文法3031 3型型(正规正规)文法产生的语言是有穷自动机文法产生的语言是有穷自动机(FA)所接受所接受的字符串的字符串(句子句子)集合集合.单词都是用单词都是用3型文法定义。型文法定义。定理定理 设设G=（VN，VT，P，

18、S）是3 3型文法，则存在一个非确定型文法，则存在一个非确定有穷自动机有穷自动机 M=(K,f,A,Z)M=(K,f,A,Z)，使得，使得L(M)=L(G)L(M)=L(G)非确定有穷自动机非确定有穷自动机NFA MNFA M五元组构造如下：五元组构造如下：=VT K=K=VN N,NN,N为新状态为新状态,它不在它不在VN中 A=S A=S Z=N Z=N 对对G G中的形如中的形如 DtBDtB的产生式的产生式,t,t为终结符或为终结符或,有有f(D,t)=Bf(D,t)=B；对对G G中形如中形如DtDt的产生式，的产生式，t t为终结符或为终结符或,有有f(D,t)=N;f(D,t)=

19、N;对对VT中的每一个a,有有f(N,a)=f(N,a)=有穷有穷自动机自动机(FA)是描述是描述3型文法的数学工具型文法的数学工具323型文法型文法 和 有穷自动机（有穷自动机（FA）G：SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|bBASaaabbba,bDZabab333型文法型文法 和 有穷自动机（有穷自动机（FA）定理定理 已知一有穷自动机NFA M=(K,f,A,Z),存在有一个3型文法G=（VN，VT，P，S）,使得L(G)=L(M)G 的定义：VT=VN=K S=A 若 f(D,t)=B，则DtB在P中 若 f(D,t)=B，且B在Z中，则Dt在P中34

20、3型文法型文法 和 有穷自动机（有穷自动机（FA）G：SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|bDBASaaabba,bb正规式（定义见教科书正规式（定义见教科书p52）3536正规文法和正规式（定义见教科书正规式（定义见教科书p52）对上的正规式r,存在一个文法G=(VN,VT,P,S)：L(G)=L(r)初始，VT=,S VN，生成正规产生式 Sr (R.1)对形如 Ar1r2的正规产生式：Ar1B Br2 BVN (R.2)对形如Arr1的正规产生式：ArB Ar1 BrB Br1 BVN (R.3)对形如Ar1r2的正规产生式:Ar1 A r2 不断应用(R

21、.x)做变换，直到每个产生式右端至多有一个VN37例 r=a(ad)(1)Sa(ad)(2)SaA A(ad)(3)A(ad)B A B(ad)B B Gs:SaA A VT=a,d AaBVN=S,A,B AdB BaB BdB B38正规文法和正规式正规式 对正规文法G=(VN,VT,P,S),存在一个=VT上的正规式r:L(r)=L(G)AxB,By 形成正规式 A=xy AxAy 形成正规式 A=xy Axy 形成正规式 A=xy39正规文法和正规式Gs:SaA|a AaAadAd A(ad)A(ad)A(ad)(ad)S=a(ad)(ad)a=a(ad)(ad)=a(ad)R=a(a

22、d)403.5上下文无关文法及其语法树上下文无关文法及其语法树上下文无关文法上下文无关文法(2型文法型文法)有足够的能力描述程序有足够的能力描述程序设计语言的语法结构。设计语言的语法结构。语法树语法树-句型推导句型推导的的直观表示。直观表示。41语法树语法树-句型推导句型推导的的直观表示直观表示GE E：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|aE EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*aE EE+TE+T*FE+T*aE+F*aE+a*aT+a*aF+a*aa+a*aE EE+TT+TT+T*FF+T*FF+F*Fa+F*Fa+

23、F*aa+a*a42规范推导规范推导规范句型规范句型最左（最右）推导：在推导的任何一步最左（最右）推导：在推导的任何一步，其中，其中、是句型，都是对是句型，都是对中中的最左（右）非终结符进行替换的最左（右）非终结符进行替换最右推导被称为规范推导。最右推导被称为规范推导。由规范推导所得的句型称为规范句型由规范推导所得的句型称为规范句型43语法树语法树设G=(VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）：1.每个结点都有一个标记，此标记是V的一个符号2.根的标记是S3.若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN4.如果结点

24、n有标记A,其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式语法树的结果：语法树的结果：从左到右读出叶子的标记而构成句型从左到右读出叶子的标记而构成句型。树称为该句型的语法树。44上下文无关文法的语法树上下文无关文法的语法树z句型句型aabbaa的可能的可能推导推导序列和语法树序列和语法树例例:3.7文法文法GS:SaASASbAASSSaAbaSaASSbAaabaSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa45语法

25、树语法树-句型推导句型推导的的直观表示直观表示给定文法给定文法G=(VN,VT,P,S)，对于，对于G的任何句型都能的任何句型都能构造与之关联的语法树构造与之关联的语法树(推导树推导树)定理：定理：G为上下文无关文法，对于，有S=*，当且仅当文法G有以为结果的一棵语法树(推导树)46 一棵一棵语语法法树树表示了一个句型的种种可能的表示了一个句型的种种可能的(但未必是所有的但未必是所有的)不同推不同推导过导过程，包括最程，包括最左左(最右最右)推推导导。但是，一个句型是否只。但是，一个句型是否只对对应应唯一的一棵唯一的一棵语语法法树树呢呢?一个句型是否只有一个句型是否只有唯一的一个最左唯一的一个

26、最左(最右最右)推推导导呢呢?47例：例：G GE:E: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：EE+EE*E+Ei*E+Ei*i+Ei*i+i推导推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i48二义文法二义文法 若一个文法存在某个句子对应两棵不同的语法树，若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是则称这个文法是二义二义的的或者，若一个文法存

27、在某个句子有两个不同的最或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是左（右）推导，则称这个文法是二义二义的的 判定任给的一个上下文无关文法是否二义，判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件以为无二义性寻找一组充分条件 49文法的二义性和语言的二义性文法的二义性和语言的二义性文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法

28、的文法G G和和GG，其中，其中G G是二义的，但是却有是二义的，但是却有L(G)=L(G)L(G)=L(G)，也就是说，也就是说，这两个文法所产生的语言是相同的。这两个文法所产生的语言是相同的。二义文法改造为无二义文法二义文法改造为无二义文法G GE:E i GEE:E i GE：E T|E+TE T|E+T E E+E T F|T*F E E+E T F|T*F E E*E F E E*E F （E E）|i|i E (E)E (E)引入非终结符引入非终结符 规定算符优先性和结合性规定算符优先性和结合性 如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先如果产生上下文无关语言的每

29、一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。的，因为希望对它的每个语句的分析是唯一的。503.6（上下文无关文法）上下文无关文法）句型的分析句型的分析 句型分析句型分析就是就是识别识别一个符号串是否为某文法一个符号串是否为某文法的的句型句型，是某个，是某个推导推导的构造过程。的构造过程。在语言的编译实现中，把在语言的编译实现中，把完成句型分析完成句型分析的的程序程序称为称为分析程序分析程序或或识别程序识别程序。分析算法。分析算法又称又称识别算法

30、识别算法。从左到右的分析算法从左到右的分析算法，即，即总是从总是从左左到到右右地地识别输入符号串识别输入符号串，首先识别符号串中的，首先识别符号串中的最最左左符号，进而符号，进而依次识别右边依次识别右边的一个符号，的一个符号，直到分析结束直到分析结束。51句型的句型的分析算法分类分析算法分类分析算法可分为：分析算法可分为：自上而下分析法自上而下分析法：从文法的开始符号出发从文法的开始符号出发，反复使用文法的，反复使用文法的产生式，产生式，寻找寻找与与输入符号串输入符号串匹配匹配的的推导，推导，或者说，为输入串寻找一个最左推导。或者说，为输入串寻找一个最左推导。自下而上分析法自下而上分析法：从从

31、输入符号串输入符号串开始开始，逐步进行逐步进行归约归约，直至，直至归约归约到到文法的文法的开始符号开始符号。52两种方法反映了两种语法树的构造过程两种方法反映了两种语法树的构造过程自上而下方法自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串。自下而上方法自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树。53自上而下的语法分析自上而下的语法分析例：文法例：文法G：S cAdA abA a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子SSScAdcAdab推导过程：推导过程：ScAdcAdcabd

32、54自下而上的语法分析自下而上的语法分析例：文法例：文法G：S cAdA abA a识别输入串识别输入串w=cabd是否该文法的是否该文法的句子句子SAAcabdcabdcabd规约规约过程构造的推导：过程构造的推导：cAdcabdScAd55自上而下的语法分析自上而下的语法分析(1)ScAd(2)A ab(3)A a识别输入串识别输入串w=cad是否为该文法的是否为该文法的句子句子若S cAd 后选择(2)扩展A，S cAd cabd那将会？w的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配？宣告分析失败（其意味着，识别程序不能为串cad构造语法树，即cad不是句

33、子）-显然是错误的结论。导致失败的原因是在分析中对A的选择不是正确的。S c A d a b 这时应该回朔回朔，把A为根的子树剪掉，扫描过的输入串中的a吐出来,再试探用产生式（3）56自下而上的语法分析自下而上的语法分析(1)S cAd(2)A ab(3)A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子 对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么在c A b d 中无法找到一个可归约串了，最终就达不到归约到S的结果，因而也无从知道cabd是一个句子。c a b d c A b d a57句型分析的有关问题句型分析

34、的有关问题1)在自上而下的分析方法中在自上而下的分析方法中如何如何选择选择使用使用哪个哪个产产生式进行推导生式进行推导？假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是B，且有，且有n条条规则：规则：BA1|A2|An，那么如何确定用哪个右，那么如何确定用哪个右部去替代部去替代B？LL(1)文法不用回溯。确定和不确定？文法不用回溯。确定和不确定？2)自下而上的分析方法中自下而上的分析方法中如何如何识别可归约的串识别可归约的串？在分析程序工作的每一步，都是从当前串中在分析程序工作的每一步，都是从当前串中选择选择一个一个子串子串，将它，将它归约归约到到某个非终结符号某个非终结符号，该子

35、串，该子串称为称为“可归约串可归约串”刻画刻画“可归约串可归约串”-句柄、素短语句柄、素短语文法文法GS句型的短语句型的短语S *A且且 A +，则称则称是是句型句型相对相对于非终结符于非终结符A的的短语短语句型的直接短语句型的直接短语若有若有A ，则称则称是句型是句型相对于非终结符相对于非终结符A 的的直接短语直接短语句型的句柄句型的句柄一个句型的一个句型的最左直接短语最左直接短语称为称为该句型该句型的的句柄句柄最左素短语最左素短语：至少含有一个终结符的最左边的短语，且：至少含有一个终结符的最左边的短语，且这个短语不包含别的短语。这个短语不包含别的短语。例例 ：i*i+i i*i+i 的短语

36、、直接短语和句柄的短语、直接短语和句柄 E E +T T FT *F 短语是句型的字串 i3 短语短语：i1*i2+i3，i1*i2，F i2 i1，i2，i3。i1 直接短语直接短语：i1，i2，i3。句柄句柄：i1 最左素短语：最左素短语：i1GEGE：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|i F(E)|i句型：句型：i*i+ii*i+i 自下而上的语法分析自下而上的语法分析在分析程序工作的每一步，都是从当前串中在分析程序工作的每一步，都是从当前串中选择一选择一个个子串子串，将它，将它归约归约到到某个非终结符号某个非终结符号，该子串称为，该子串称为“可归约串可归约

37、串”z选择选择“可归约串可归约串”是最左素短语（至少是最左素短语（至少含有一个终结符的最左边的短语，且这含有一个终结符的最左边的短语，且这个短语不包含别的短语）个短语不包含别的短语）z选择选择“可归约串可归约串”是句型的句柄称为规是句型的句柄称为规范归约范归约GE：EE+T|T TT*F|F F(E)|iz句型句型 i*i+i 的自下而上分析，的自下而上分析，总是归约当前句型的句柄形成的规范推总是归约当前句型的句柄形成的规范推导序列：导序列：EE+TE+FE+iT+iT*F+iT*i+iF*i+i i*i+iz句型句型 i*i+i 的自下而上分析的自下而上分析总是归约当前句型的最左素短语形成的

38、推总是归约当前句型的最左素短语形成的推导：导：ET+FT+iF*F+iF*i+i i*i+iGE：EE+T|T TT*F|F F(E)|i E E +T T FT *F i3 F i2 句型句型F*i2+i3的的最左素短语：最左素短语：i2 归约为归约为F句型句型F*F+i3的的最左素短语：最左素短语：F+F归约为归约为T句型句型T+i最左素短语最左素短语i3归约为归约为F;句型句型T+F最左素短语最左素短语T+F归约为归约为E633.7文法实用中的一些说明文法实用中的一些说明3.7.1有关文法的实用限制有关文法的实用限制-化简文法文法中文法中不含有不含有有害规则有害规则和和多余规则多余规则有

39、害规则有害规则：形如：形如UU的产生式。会的产生式。会引起引起文法的文法的二义性二义性多余规则多余规则：指文法中：指文法中任何句子的推导任何句子的推导都都不会用到的规则不会用到的规则文法中文法中不含有不含有不可到达和不可终止的不可到达和不可终止的非终结符非终结符1）文法中某些）文法中某些非终结符不在任何规则的右部出现非终结符不在任何规则的右部出现，该非终，该非终结符称为结符称为不可到达不可到达。2）文法中某些）文法中某些非终结符非终结符，由它，由它不能推出终结符号串不能推出终结符号串，该非，该非终结符称终结符称为为不可终止不可终止。64对于文法对于文法GS，为了保证任一非终结符，为了保证任一非

40、终结符A在在句子句子推导中出现，必须满足如下两个条件：推导中出现，必须满足如下两个条件：1.A必须在某句型中出现必须在某句型中出现即有即有S=*A，其中，其中，属于属于V V*2.必须能够从必须能够从A推出终结符号串推出终结符号串t来来即即A=*t，其中，其中tVT*65化简文法z例：例：GS：1)SBe2)BCeD为不可到达为不可到达3)BAfC为不可终止为不可终止4)AAe5)Ae6)CCf7)Df产生式产生式2），），6），），7）为）为多余规则多余规则应去应去掉。掉。663.7.2上下文无关文法中的上下文无关文法中的规则规则上下文无关文法中某些规则可具有形式上下文无关文法中某些规则可具

41、有形式A，称这，称这种规则为种规则为规则规则因为因为规则会使得有关文法的一些讨论和证明变得复规则会使得有关文法的一些讨论和证明变得复杂杂,有时会限制这种规则的出现有时会限制这种规则的出现两种定义的唯一差别是两种定义的唯一差别是句子在不在语言中句子在不在语言中文法构思的启示是要找出语言的有穷描述，而如果文法构思的启示是要找出语言的有穷描述，而如果语言语言L有一个有穷的描述，则有一个有穷的描述，则L1=L也同样也同样有一个有穷的描述，并且可以证明，若有一个有穷的描述，并且可以证明，若L是上下文是上下文有关语言、上下文无关语言或正规语言，则有关语言、上下文无关语言或正规语言，则L和和L-分别是上下文

42、有关语言、上下分别是上下文有关语言、上下文无关语言和正规语言。文无关语言和正规语言。67练习练习 1.写一文法，使其语言是偶正整数的集合。要求：(1)允许0打头 (2)不允许0打头2.证明下述文法G表达式是二义的。表达式=a|(表达式)|表达式运算符表达式运算符=+|-|*|/3.令文法GE为：ET|E+T|E-TTF|T*F|T/FF(E)|i证明E+T*F是它的一个句型68练习练习4.请 给出生成下述语言的上下文无关文法：（1）anbnambm|n，m=0(2)1n0m1m0n|n，m=0 5.请 给出生成下述语言的三型文法：(1)anbm|n,m=1(2)anbmck|n,m,k=06.请 给出下述文法所对应的正规式：S0A|1BA1S|1B0S|0