第2章形式语言基础精.ppt

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

1、第2章形式语言基础第1页，本讲稿共51页第第2章章形式语言基础形式语言基础 计算机处理语言，首先应考虑语言的形式化、规范化，使其具有可计算性和可操作性；这就是形式语言理论研究的问题。形式语言诞生于1956年，由Chomsky创立。通常，语言研究至少涉及三个方面：语法、语义和语用；形式语言的基本观点是：语言是符号串之集合！形式语言理论研究的形式语言理论研究的基本问题基本问题是：是：研究符号串集合的表示方法、结构特性研究符号串集合的表示方法、结构特性以及运算规律。以及运算规律。因此：因此：第2页，本讲稿共51页【内容提要】2.1 形式语言是符号串集合 2.2 形式语言是由文法定义的 2.3 各种语

2、法成分的定义 2.4 两类特性文法 2.5 文法变换方法 2.6 形式语言的分类第第2章章形式语言基础形式语言基础第3页，本讲稿共51页 字母表-元素(符号)的非空有限集合；符号串-符号的有限序列；符号串集合-有限个或者无限个符号串组成的集合；规 则-以某种形式表达的在一定范围内共同遵守的章程和制度；这里，指符号串的组成规则。2.1形式语言是符号串集合形式语言是符号串集合 【形式语言】是字母表上的符号按一定的规则组成的所有符号串集合；其中的每个符号串称为一个句子。【名词解释名词解释】：三要素！第4页，本讲稿共51页【例例2.1】L1=00,01,10,11;字母表字母表1=0,1,句子有：句子

3、有：00,01,10,11【注注】(1)b0=（空符号串）（空符号串）,b1=b,b2=bb,b3=bbb,(2)L1为有限语言为有限语言;L2为无限语言。为无限语言。形式形式语言概念示例：言概念示例：【例例2.2】L2=abmc,bn|m0,n0字母表字母表2=a,b,c,句型句型1:abmc有句子：有句子：abc,abbc,abbbc,句型句型2:bn有句子：有句子：,b,bb,bbb,两个语言!第5页，本讲稿共51页1.1.连接连接：.=如：a.b=ab 2.1.1符号串符号串(集合集合)的运算的运算3.3.方幂方幂：n n=n-1n-1=n-1n-1 4.4.闭包：闭包：n n个个.符

4、号串的运算符号串的运算 设设,为两个符号串，则为两个符号串，则：的正闭包：的正闭包：+=1 1|2 2|n n|的星闭包：的星闭包：*=0 0|1 1|2 2|n n|0 0=(空符号串空符号串)什么符号也没有的符号串什么符号也没有的符号串 ！1 1=；2 2=；2.2.或或：|=或者或者 这是一种泛指！第6页，本讲稿共51页【例例2.3】：(2)abc.=.abc=abc(1)abc.de=abcde(4)(a|b)1=(a|b)=a|b(a|b)*=(a|b)0|(a|b)1|(a|b)2|(a|b)2=(a|b)(a|b)=aa|ab|ba|bb 即：即：(a|b)*=(a|b)n,n0

5、同理：同理：(a|b)+=(a|b)n,n0 符号串运算示例符号串运算示例泛指：由a，b组成的任意符号串！（包括空串）(3)ab|cd=ab或者或者cd第7页，本讲稿共51页1.乘积乘积：AB=xy|x A且且y B4.闭包闭包：A的正闭包的正闭包：A+=A1A2AnA的星闭包的星闭包：A*=A0A1A2An设设A和和B为两个符号串集合，则：为两个符号串集合，则：2.和和：AB=A+B=x|x A或或x B3.方幂方幂：An=AAA=AAn-1=An-1An个个A0=;A1=A;A2=AA;A3=AAA;.符号串集合的运算符号串集合的运算 2.1.1符号串符号串(集合集合)的运算的运算第8页，

6、本讲稿共51页 符号串集合运算示例符号串集合运算示例【例例2.4】设设A=a,b,B=c,d则则A+B=a,b,c,d则则AB=xy|x A,y B=ac,ad,bc,bd【例例2.5】设设A=a则则A*=A0A1A2An=+a+aa+aaa+=,a,aa,aaa,=an|n0第9页，本讲稿共51页【例例2.6】设设A=a,b，A*=?A*=A0A1A2AnA0=;A1=A=a,b;A2=AA=a,ba,b=aa,ab,ba,bb;A3=AA2=a,baa,ab,ba,bb=aaa,aab,aba,abb,baa,bab,bba,bbb;A*=x|x=(a|b)n,n0 符号串集合运算示例符号

7、串集合运算示例(续续)：推论推论：若：若A为任一字母表，则为任一字母表，则A*就是该字母就是该字母表表 上上的所有符号串的所有符号串(包括空串包括空串)的集合。的集合。第10页，本讲稿共51页2.2 形式语言是由文法定义的 形式语言是符号串的集合，对形式语言的描述形式语言是符号串的集合，对形式语言的描述有两种方式：有两种方式：(1)枚举方式枚举方式：语言为有穷集合时：语言为有穷集合时设有字母表设有字母表A=a,b,c,有有L1=a,aa,ab,ac,L2=c,cc(2)使用文法使用文法：语言为无穷集合时，无法枚举：语言为无穷集合时，无法枚举 设有字母表设有字母表B=0,1,B+=0,1,00,

8、10,11,01,000,用用A表示表示B+，可以表示为，可以表示为A-0A-1A-A0A-A1文法：用有穷的集合刻画无穷的集合的工具。文法：用有穷的集合刻画无穷的集合的工具。第11页，本讲稿共51页【定义定义】文法文法(grammar)是是规则规则的有限集，通常可以表示的有限集，通常可以表示为四元组：为四元组：G(Z)=(VN,VT,Z,P)VN:非终结符集非终结符集(定义的对象集，如：语法成分等定义的对象集，如：语法成分等)；VT:终结符集终结符集(字母表字母表)；Z:开始符号开始符号(研究范畴中最大的定义对象研究范畴中最大的定义对象)；P:规则集规则集(又称产生式集又称产生式集)；2.2

9、形式语言是由文法定义的形式语言是由文法定义的每个元素2.2.1什么是文法什么是文法？Z-或者或者A-|注：此文法实际称为上下文无关文法注：此文法实际称为上下文无关文法描述符号描述符号：-(定义为定义为/生成生成)，|(或者是或者是)文法符号文法符号：Z,AVN，,(VN+VT)*每个规则第12页，本讲稿共51页 【注意】提供了规则集，就相当给出了一个文法：S-aAc A-bA|G(S):VT=a,b,c;Z=S;P:VN=S,A;G(Z)=(VN,VT,Z,P)2.2.1 什么是文法？【例例2.7】L=abnc|n0，字母表：，字母表：=a,b,c；展开：展开：L=ac,abc,abbc,ab

10、bbc,可以用右图给出的可以用右图给出的S-aAcA-bA|文法规则文法规则来表示来表示：第13页，本讲稿共51页2.2.2 文法是怎样定义语言的？则则L(G)=x|Zx,xVT*即：一个文法所定义的即：一个文法所定义的语言语言，就是由该文法，就是由该文法开始开始设有文法设有文法G(Z)，L(G)为为G所定义的语言；所定义的语言；利用利用推导算符推导算符 =进行连续推导进行连续推导符号推导出符号推导出的所有的所有仅含终结符仅含终结符的所有的所有符号串符号串之之集合集合。其中的每个符号串皆称为其中的每个符号串皆称为句子句子。=+2.1使用文法的规则进行 形式语言是字母表上的符号按一定的形式语言是

11、字母表上的符号按一定的规则规则组成的组成的 所有所有符号串集合。符号串集合。第14页，本讲稿共51页 从从开始符号出发，对符号串中的出发，对符号串中的定义对象定义对象，采用，采用推导的方法（的方法（用其规则右部替换左部用其规则右部替换左部）产生新的符号串，如此）产生新的符号串，如此进行，直到新符号串中不再出现定义的对象为止，则最进行，直到新符号串中不再出现定义的对象为止，则最终的符号串就是一个终的符号串就是一个句子。S-aAcA-bA|利用利用文法规则文法规则表示语言表示语言 【句子产生过程】(=推导算符)S S=aAcaAc=ac=ac=ac=ac S S=aAc=aAc=abAc=abAc

12、=abc=abc=abc=abc S S=aAc=aAc=bAc=bAc=abbAc=abbAc=abbc=abbc 一个句子!又一个句子!S abS abn nc,n0 c,n0 =+再一个句子!非终结符号第15页，本讲稿共51页【例例2.8】标识符标识符的文法的文法 【标识符标识符】指字母开头的字母、数字序列。指字母开头的字母、数字序列。令令G(Z)=(VN,VT,Z,P)则则VN=I(标识符标识符),A(标识符尾标识符尾)；VT=(字母字母),d(数字数字)；Z=I;P:I-A|A-A|dA|同理，同理，【无符号整数无符号整数】文法可写成：文法可写成：G(N):N-dN|d其其四元组四元

13、组也可写成：也可写成：G(N)=(N,d,N,P)第16页，本讲稿共51页得：得：I=(|d)n,n0令：令：I=A|A=A|dA|求解求解文法文法所定义的语言所定义的语言(1)上面构造的标识符文法 属于正规文法I-A|A-A|dA|先求解先求解A:A=(|d)A,A=(|d)2A,A=(|d)nA代入代入A=得：得：A=(|d)n,n0I=A|代入代入A=(|d)n,n0正规方程式正规方程式标识符：字母开头的字母、数字序列标识符：字母开头的字母、数字序列第17页，本讲稿共51页求解求解文法文法所定义的语言所定义的语言(2)则则L(G)的求解过程的求解过程代入法代入法：Z-aAc A-bA|【

14、例例2.9】G(Z):所以所以：L(G)=abnc|n0A=bA=bbA=bn,n0Z=aAcabnc,n0 =+A bn =+即：即：Abn =+，n0即：即：Zabnc，n0 =+第18页，本讲稿共51页则则VN=E(算术表达式算术表达式),T(项项),F(因式因式)；VT=i(变量或常数变量或常数),+,-,*,/,(,)；Z=E;P:【例例2.10】简单算术表达式文法简单算术表达式文法【注注】此文法定义了算术表达式的层次嵌套结构此文法定义了算术表达式的层次嵌套结构:E-T|E+T|E-T T-F|T*F|T/F F-i|(E)令令G(Z)=(VN,VT,Z,P)(表达式表达式 )表达式

15、表达式项项因式因式文法文法E-E+E|EE|E*E|E/E|i|(E)?第19页，本讲稿共51页 算术表达式文法应用示例：算术表达式文法应用示例：根据根据 语言定义式语言定义式2.1，G(E):E-T|E+T|E-T T-F|T*F|T/F F-i|(E)证明证明i*(i+i-i)是文法是文法G(E)的一个的一个句子句子(即合法的即合法的算术表达式算术表达式):=+E i*(i+i-i)成立吗？E =+E i*(i+i-i)=T=T*F=T*(E)=T*(E-T)=T*(E+T-T)=F*(E+T-T)=i*(E+T-T)=观察推导过程，可以看到：一旦产生式选择错了，会导致失败！=i*(i+i

16、-i)L(G)=x|Zx,xVT*=+合法的算术表达式是指：合法的算术表达式是指：第20页，本讲稿共51页 文法有两种基本运算：文法有两种基本运算：推导推导和和归约归约v星推导星推导():2.3各种语法成分的定义各种语法成分的定义1.直接推导直接推导(=):xAy=x y即：指用产生式的右部符号串即：指用产生式的右部符号串替换替换左部非终结符。左部非终结符。加推导算符v加推导():设设x,y(VN+VT)*，A-P =*=*（当且仅当（当且仅当=1=2=）即：指一步或一步以上的直接推导运算。即：指一步或一步以上的直接推导运算。（当且仅当当且仅当=或或=1=2=)即：指零步或零步以上的直接推导运

17、算。即：指零步或零步以上的直接推导运算。直接推导算符星推导算符 =+=+2.3.1 文法的运算第21页，本讲稿共51页 =.+=.+2.直接归约直接归约():x yxAy =.=.（当且仅当（当且仅当 1 1 2 2 ）=.=.=.=.v星归约星归约():=.*=.*（当且仅当（当且仅当 =或或 1 1 2 2 )=.=.=.=.即：直接归约是直接推导的即：直接归约是直接推导的逆运算逆运算，用产生式的左，用产生式的左 部非终结符替换右部符号串。部非终结符替换右部符号串。即：指零步或零步以上的直接归约运算。即：指一步或一步以上的直接归约运算。直接归约算符加归约算符星归约算符l加归约加归约():2

18、.3.1 文法的运算第22页，本讲稿共51页规范推导和规范归约规范推导和规范归约 实用中最常见的两种运算：l最左推导()每次推导皆最左非终结符优先；l最左归约()每次归约皆最左可归约串优先。=+=.+l最右推导也称为规范推导l最左归约也称为规范归约同一个句子可以通过不同的推导序列推导出来同一个句子可以通过不同的推导序列推导出来通常只考虑两种特殊推导，即通常只考虑两种特殊推导，即最左推导和最右推导最左推导和最右推导N1=N=ND=N2=D2=1212D2N2NDNN1N1-NN-ND|DD-0|1|2 =.=.=.=.=.最左归约是最右推导的逆过程！最左归约是最右推导的逆过程！第23页，本讲稿共

19、51页i+i*il给定一个符号串给定一个符号串i+i*i：T-F|T*F|T/F F-i|(E)G(E):E-T|E+T|E-T文法运算示例：文法运算示例：【例例2.11】算术表达式文法：算术表达式文法：=.=.=.=.=.=.=.=.2.最左归约最左归约(从从符号串出发符号串出发)过程：过程：E=E+T=T+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*iE =+i+i*iF+i*iT+i*iE+i*iE+F*iE+T*iE+T*FE+TEi+i*i =.+E1.最左推导最左推导(从从开始符号出发开始符号出发)过程：过程：最左非终结符最左可归约串第24页，本讲稿共51页即：

20、句型是由文法开始符号加推导出的任一符号串。2.3.2句型、句子和语法树句型、句子和语法树若有若有且且 VT*，则，则 是句子；是句子；Z=+若有 ,则是句型；Z=+2.句子句子即：句子是由开始符号加推导出的任一终结符号串。1.句型句型设有文法设有文法G(Z)=(VN,VT,Z,P)，则：，则：3.语法树语法树句型(句子)产生过程的一种树结构表示；树根树根开始符号开始符号；树叶树叶给定的给定的句型句型(句子句子)。第25页，本讲稿共51页 A x1 x2xn 重复步骤重复步骤，直到推导过程结束为止。，直到推导过程结束为止。置树根为开始符号；置树根为开始符号；【语法树的构造算法】若若推导推导采用了

21、采用了产生式产生式：A-x1x2xn，则有，则有子树：子树：如此构造的语法树，其如此构造的语法树，其全体树叶全体树叶(自左至右自左至右)恰好是给定的句型恰好是给定的句型(句子句子)。第26页，本讲稿共51页E=T=T*F=F*F=(E)*F=(E+T)*F=(T+T)*F=(T/F+T)*F=(T/F+F)*F=(T/F+F)*i 句型、句子和语法树示例句型、句子和语法树示例【例2.12】算术表达式文法：(1)证明证明(T/F+F)*i是一个句型是一个句型(表达式型表达式型)；(2)画出该句型的语法树。画出该句型的语法树。E-T|E+T|E-T T-F|T*F|T/F F-i|(E)【证证】即

22、：即：E(T/F+F)*i =+第27页，本讲稿共51页句型句型(T/F+F)*i的语法树构造：的语法树构造：ETT*FF(E)E+TTT/FFiE-T|E+T|E-T T-F|T*F|T/F F-i|(E)【注注】关于语法树：关于语法树：l子树：由某一结点连子树：由某一结点连同同所有分支所有分支组成的组成的部分。部分。l简单子树简单子树 ：仅具有：仅具有单层分支单层分支的子树。的子树。第28页，本讲稿共51页3.句柄句柄 -一个句型的一个句型的最左简单短语最左简单短语称为该句型的称为该句型的句柄句柄。2.3.3短语、简单短语和句柄短语、简单短语和句柄设文法设文法G(Z),x y是一个句型，则

23、是一个句型，则:则则 是句型是句型x y关于关于A的短语的短语(A是是 的名字的名字)；=+=+1.1.短语短语 若若 Z xAy xZ xAy x y y Z x A y 任一任一子树子树的的树叶全体树叶全体(具有共同具有共同祖先祖先的叶节点符号串的叶节点符号串)皆为皆为短语短语；=+2.简单短语简单短语 若若 Z xAy Z xAy=x x y y则则 是句型是句型x y关于关于A的简单短语的简单短语(A是是 的名字的名字)；任一任一简单子树简单子树的的树叶全体树叶全体(具有共同具有共同父亲父亲的叶节点符的叶节点符号串号串)皆为皆为简单短语简单短语；第29页，本讲稿共51页 (他)(哥哥)

24、(喜欢)(看)图2.2 他哥哥喜欢看书的语法树(书)2.3.3 短语、简单短语和句柄【例2.13】图2.2为一个中文句型的语法树：短 语-他哥哥,喜欢看,书，喜欢看书，他哥哥喜欢看书简单短语-他哥哥，喜欢看，书句 柄-他哥哥（最左边的简单短语!）第30页，本讲稿共51页【例2.14】图2.3为一个算术表达式(型)的语法树：句型：E+F-T/F*i短语:E+F-T/F*i，E+F，F，T/F*i，T/F，i简单短语:F，T/F，i 句柄:F E E -T E +T T *F F T /F i 图2.3 E+F-T/F*i 的语法树 2.3.3 短语、简单短语和句柄 第31页，本讲稿共51页 一类

25、典型的综合例题：一类典型的综合例题：【例例2.15】G(S):S-aAcBe;A-Ab|b;B-d给定符号串给定符号串：aAbcde 证明证明 =aAbcde是一个句型；是一个句型；画出句型画出句型 的语法树；的语法树；指出指出 中的短语、简单短语和句柄。中的短语、简单短语和句柄。【题解题解】S=aAcBe=aAbcBe=aAbcde语法树如右图：语法树如右图：短语、简单短语和句柄短语、简单短语和句柄:S a A c B e A b d 短语短语:aAbcde,Ab,d简单短语简单短语:Ab,d句柄：句柄：Ab第32页，本讲稿共51页G2(S):S-bS|a-直接右递归直接右递归文法。文法。2

26、.4两种特性文法两种特性文法 2.4.1 递归文法 设有文法：设有文法：G(Z)=(VN,VT,Z,P)【定义定义】设设AVN，x,y(VN+VT)*，则，则;若若AxAy，称文法具有，称文法具有递归性递归性;=+特别地特别地：若若A-A，称文法具有，称文法具有直接左递归性直接左递归性；A-A，称文法具有，称文法具有直接右递归性直接右递归性。递归文法是定义无限语言的工具递归文法是定义无限语言的工具 递归文法定义的语言有无限个句子递归文法定义的语言有无限个句子如：如：G1(S):S-Sb|a-直接左递归直接左递归文法；文法；第33页，本讲稿共51页 递归文法示例递归文法示例【例例2.16】G(Z

27、)：Z-aAbB|cZA-bBc|B-BbAc|aZ-cZ直接右递归性直接右递归性；B-BbAc直接左递归性直接左递归性；A=bBc=bBbAcc即即A A 具有递归性具有递归性(且且 又称为又称为A具有自嵌套性具有自嵌套性)可以统称文法可以统称文法G(Z)具有递归性。具有递归性。=+第34页，本讲稿共51页2.4.2 二义性文法【定义定义】若文法中存在这样的句型，它具有若文法中存在这样的句型，它具有两棵两棵不同的语法树不同的语法树，则称该文法是，则称该文法是二义性二义性文法。文法。【例例2.17】算术表达式的另一种文法：算术表达式的另一种文法：句型句型i+i*i有两棵不有两棵不同的语法树同的

28、语法树(右图右图)：G(E)是二义性文法。是二义性文法。G(E)：E-E+E|E*E|(E)|i;i(变量或常数变量或常数)E E E+E E*E i E*E E+E i i i i i 二义性文法会引起歧义，应尽量避免之！第35页，本讲稿共51页文法二义性的消除文法二义性的消除【方法方法1 1】不改变文法的原有规则不改变文法的原有规则,加进一些非形加进一些非形 式的规定。式的规定。【方法方法2 2】构造一个构造一个等价的无二义性文法等价的无二义性文法，将排除，将排除 二义性的规则合并到文法中二义性的规则合并到文法中加进运算符的优先顺序和结合规则加进运算符的优先顺序和结合规则对对G(E)，规定

29、，规定*优于优于+，*和和+服从左结合服从左结合G(E)-G(E):E-E+T|TT-T*F|FF-(E)|i;第36页，本讲稿共51页2.5.1 文法的等价性 2.5文法的等价变换文法的等价变换即：文法的等价性是指它们所定义的语言是一样的。【定义定义】设设G1、G2是两个文法，若是两个文法，若L(G1)=L(G2)，则称则称G1与与G2等价，记作等价，记作G1G2。【例例2.18】G1：S-aS|aG2：S-Sa|aL(G1)=a,aa,aaa,=an|n1L(G2)=a,aa,aaa,=an|n1L(G1)=L(G2)即即G1G2【结论结论】一个语言，其描述文法并不唯一。一个语言，其描述文

30、法并不唯一。第37页，本讲稿共51页2.5.2文法变换方法文法变换方法 在实际工作中，人们总是希望定义一种语言的文法尽可能地简单。另外，某些常用的语法分析技术也会对文法提出一定的要求或限制。因此，有时需要对文法进行必要的改写。改写后的文法要与原文法等价通常称为文法变换。这里重点介绍三类变换：BNF（巴科斯范式）表示法：（巴科斯范式）表示法：删除删除产生式；产生式；必选项法；必选项法；可选项法；可选项法；重复可选项法。重复可选项法。删除无用的产生式（文法的化简）；删除无用的产生式（文法的化简）；第38页，本讲稿共51页文法的化简是指消除如下文法的化简是指消除如下无用产生式无用产生式：1.A-A形

31、式的产生式形式的产生式(自定己自定己)；2.不能从其推导出终结符号串的产生式不能从其推导出终结符号串的产生式(不终结不终结)；3.在推导中永不使用的产生式在推导中永不使用的产生式(不可用不可用)。文法的化简文法的化简删除删除不终结不终结产生式算法：产生式算法：(1)构造构造能能推导出终结符号串的非终结符集推导出终结符号串的非终结符集VVT:若有若有A-且且 VT*;则令则令AVVT；若有若有B-且且(VT+VVT)*;则令则令BVVT;重复步骤重复步骤，直到，直到VVT不再扩大为止。不再扩大为止。(2)删除不在删除不在VVT中的所有非终结符中的所有非终结符(连同其产生式连同其产生式)。第39页

32、，本讲稿共51页删除删除不可用不可用产生式算法：产生式算法：(1)构造可用构造可用的非终结符集的非终结符集VUS:首先令首先令ZVUS;(Z为文法为文法开始符号开始符号)=+(2)删除不在删除不在VUS中的所有非终结符中的所有非终结符(连同其产生式连同其产生式)。【例例2.19】化简下述文法：化简下述文法：G(S):S-Be|Ec A-Ae|e|A B-C e|AfC-Cf;D-f;G-b若有若有ZA，则，则令令AVUS;重复步骤重复步骤，直到，直到VUS不再扩大为止。不再扩大为止。=+文法的化简文法的化简第40页，本讲稿共51页 文法化简示例文法化简示例l化简步骤：G(S):S-Be|Ec

33、A-Ae|e|A B-C e|AfC-Cf;D-f;G-b删除删除A-A;2.删除删除不终结不终结产生式产生式:VVT=A,D,G,B,S;应删除应删除C,E(连同其产生式连同其产生式)得：得：G(S):S-Be;A-Ae|e;B-Af;D-f;G-b;3.删除删除不可用不可用产生式产生式:VUS=S,B,A;应删除应删除D,G(连同其产生式连同其产生式)整理后得：整理后得：G(S):A-Ae|eB-AfS-Be第41页，本讲稿共51页 删除删除 产生式产生式【算法算法】1.首先构造可以推出空串的非终结符集：首先构造可以推出空串的非终结符集：V 若有若有A-;则则令令AV;若有若有B-A1An

34、且全部且全部AiV;则令则令BV;重复步骤重复步骤，直到，直到V 不再扩大为止。不再扩大为止。2.删除删除G(Z)中的中的A-形式的产生式；形式的产生式；假定文法假定文法G(Z);L(G)3.依次改写依次改写G(Z)中的产生式中的产生式B-X1X2Xn:若有若有XiV 则用则用(Xi|)替换之替换之(一个分裂为两个一个分裂为两个)；若有若有j个个XiV，则一个产生式将分裂为则一个产生式将分裂为2j个个!第42页，本讲稿共51页 删除删除 产生式示例：产生式示例：(1)求解求解V=A,B(2)删除删除 产生式产生式得：得：S-aAbc|bS；A-dABe；B-A|b(3)改写改写右部含有右部含有

35、V 中元素的产生式：中元素的产生式：S-a(A|)bcS-aAbc|abcA-d(A|)(B|)eA-dABe|dBe|dAe|deB-(A|)B-A含有V元素的产生式综合综合G(S)：S-aAbc|abc|bS A-dABe|dBe|dAe|de B-A|b【例例2.20】G(S):S-aAbc|bSA-dABe|;B-A|b第43页，本讲稿共51页令令(|)=或者或者 1.必选项法（圆括号法）BNF（巴科斯范式）表示法（巴科斯范式）表示法必选其中之一！例如：有例如：有A-a|a 也可写成：也可写成：A-aA；A-|【注】此法又称提公因子法，利用此法可以解决：具有相同左部的各产生式首符号不同

36、！基本思想基本思想：扩展文法，引进新的：扩展文法，引进新的描述符号描述符号：()圆括号；圆括号；方括号；方括号；花括号花括号可变换成可变换成:A-a(|)第44页，本讲稿共51页也可写成：也可写成：S-S;S-|令令=或者或者 2.可选项法（方括号法）例如：例如：S-|可选也可不选！例如例如条件语句文法：条件语句文法：S-if(B)S可变换成：可变换成：S-S-if(B)SelseS可变换成：可变换成：S-if(B)SelseSS(语句)，B(布尔表达式)或：或：S-if(B)SS;S-elseS|BNF（巴科斯范式）表示法（巴科斯范式）表示法第45页，本讲稿共51页3.重复可选项法（花括号法

37、）例如：例如：A-A|令令=或或 或或或或可变换为：可变换为：A-通过递推方法，可得：通过递推方法，可得：A=A=A=A=*有有A-或或A A;A-A|也可写成：也可写成：A A;A-A|验证：验证：【注注】此方法常用来消除文法的此方法常用来消除文法的直接左递归直接左递归！BNF（巴科斯范式）表示法（巴科斯范式）表示法第46页，本讲稿共51页产生式形式为：产生式形式为：A-u 2.6形式语言的分类形式语言的分类 Chomsky把形式语言分为把形式语言分为四类四类，分别由四类文法定，分别由四类文法定义；四类文法的区别在于义；四类文法的区别在于产生式的形式不同产生式的形式不同：(2)1型语言型语言

38、由由1型文法型文法定义定义(1)0型语言型语言由由0型文法型文法定义定义又称 无限制文法！产生式形式为：产生式形式为：-(VN VT)*且至少有一个非终结符且至少有一个非终结符(VN VT)*又称 上下文有关文法！A VN,(VN VT)*,u(VN VT)+A只有在只有在 和和 这样的上下文环境中才能换成这样的上下文环境中才能换成u第47页，本讲稿共51页2.6形式语言的分类形式语言的分类 产生式形式为：产生式形式为：A-aB或或A-a产生式形式为：产生式形式为：A-(3)2型语言型语言由由2型文法型文法定义定义(4)3型语言型语言由由3型文法型文法定义定义又称 上下文无关文法！编译处理中，

39、主要应用编译处理中，主要应用后两种文法后两种文法！【注注】四类语言为四类语言为包含包含关系，且有关系，且有L0L1L2L3；A VN,(VN VT)*将将A替换成替换成 时，与时，与A的上下文无关的上下文无关又称 正规文法！A,B VN,a VT*产生式形式为：产生式形式为：A-Ba或或A-a右线性文法右线性文法左线性文法左线性文法第48页，本讲稿共51页 主要内容总结主要内容总结 文法 是规则集合，四元组：G(Z)=(VN,VT,Z,P)文法所定义的语言：文法应用示例：文法应用示例：简单语言的文法构造：简单语言的文法构造：无符号整数无符号整数文法：文法：G(N):N-dN|d N-dN|d

40、L(G)=x|Z x,xVL(G)=x|Z x,xVT T*=+I-A|A|A-A-A|dA|A|dA|求解文法所定义的语言求解文法所定义的语言(或或句子句子)方法：方法：v 形式语言是符号串集合且由文法定义！正规方程组迭代求语言（如正规方程组迭代求语言（如标识符文法）标识符文法）直接由定义求解句子(如 算术表达式文法)。标识符标识符文法：文法：G(G(I):):d(数字),(字母)第49页，本讲稿共51页 主要内容总结主要内容总结 文法的运算：推导和归约(二者互为逆运算)推导：归约归约 ：v文法的文法的运算运算与主要与主要语法成分语法成分的定义的定义！主要语法成分的定义主要语法成分的定义 =

41、+=+=.=.+=.+句型，句子，语法树，句型，句子，语法树，短语，简单短语，句柄短语，简单短语，句柄从语法树上看从语法树上看 句型句型(句子句子)、短语、简单短语、短语、简单短语和和句柄：句柄：直接推导直接推导(=),(=),加推导加推导(),(),最左推导最左推导();();直接归约直接归约(),(),加归约加归约(),(),最左归约最左归约(););语法树的语法树的树叶全体树叶全体-句型句型(句子句子)；语法树的语法树的子树树叶全体子树树叶全体短语短语(简单短语简单短语)；语法树的语法树的最左简单子树树叶全体最左简单子树树叶全体 句柄！句柄！第50页，本讲稿共51页课后习题2.2 设有文法GN:(1)GN定义的语言是什么?(2)给出句子0123和268的最左推导和最右推导 2.4 写一个文法，使其语言是奇数的集合，且每个奇 数不以0开头。2.7 下面文法生成的语言是什么？S-AB A-aA|B-bc|bBcG1：S-aA|a A-aSG2：N-D|NDD-0|1|2|3|4|5|6|7|8|92.11 已知文法GS:请找出符号串(a)和(A(SaA)(b)的短语、简单短语和句柄S-(AS)|(b)A-(SaA)|(a)第51页，本讲稿共51页