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

资源描述

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

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

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

3、1=0,1,句子有：句子有：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、.4.闭包：闭包：n n个个.符号串的运算符号串的运算设设,为两个符号串，则为两个符号串，则：的正闭包：的正闭包：+=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 即

6、符号串符号串(集合集合)的运算的运算现在学习的是第8页，共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;

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

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

9、定义对象研究范畴中最大的定义对象)；P:规则集规则集(又称产生式集又称产生式集)；2.2形式语言是由文法定义的形式语言是由文法定义的每个元素2.2.1什么是文法什么是文法？Z-或者或者A-|注：此文法实际称为上下文无关文法注：此文法实际称为上下文无关文法描述符号描述符号：-(定义为定义为/生成生成)，|(或者是或者是)文法符号文法符号：Z,AVN，,(VN+VT)*每个规则现在学习的是第12页，共51页【注意】提供了规则集，就相当给出了一个文法：S-aAcA-bA|G(S):VT=a,b,c;Z=S;P:VN=S,A;G(Z)=(VN,VT,Z,P)2.2.1什么是文法什么是文法？【例例2.

10、7】L=abnc|n0，字母表：，字母表：=a,b,c；展开：展开：L=ac,abc,abbc,abbbc,可以用右图给出的可以用右图给出的S-aAcA-bA|文法规则文法规则来表示来表示：现在学习的是第13页，共51页2.2.2文法是怎样定义语言的？文法是怎样定义语言的？则则L(G)=x|Zx,xVT*即：一个文法所定义的即：一个文法所定义的语言语言，就是由该文法，就是由该文法开始开始设有文法设有文法G(Z)，L(G)为为G所定义的语言；所定义的语言；利用利用推导算符推导算符 =进行连续推导进行连续推导符号推导出符号推导出的所有的所有仅含终结符仅含终结符的所有的所有符号串符号串之之集合集合。

11、其中的每个符号串皆称为其中的每个符号串皆称为句子句子。=+2.1使用文法的规则进行形式语言是字母表上的符号按一定的形式语言是字母表上的符号按一定的规则规则组成的组成的所有所有符号串集合。符号串集合。现在学习的是第14页，共51页从从开始符号出发，对符号串中的出发，对符号串中的定义对象定义对象，采用，采用推导的方法（的方法（用其规则右部替换左部用其规则右部替换左部）产生新的符号串，如）产生新的符号串，如此进行，直到新符号串中不再出现定义的对象为止，则最此进行，直到新符号串中不再出现定义的对象为止，则最终的符号串就是一个终的符号串就是一个句子。S-aAcA-bA|利用利用文法规则文法规则表示

12、语言表示语言【句子产生过程】(=推导算符)S S=aAcaAc=ac=ac=ac=ac S S=aAc=aAc=abAc=abAc=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(数字

13、数字)；Z=I;P:I-A|A-A|dA|同理，同理，【无符号整数无符号整数】文法可写成：文法可写成：G(N):N-dN|d其其四元组四元组也可写成：也可写成：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正规方程式正规方程式标识符：字母开头的字母、数字序列标识符：字母开头的字母、数字

14、序列现在学习的是第17页，共51页求解求解文法文法所定义的语言所定义的语言(2)则则L(G)的求解过程的求解过程代入法代入法：Z-aAcA-bA|【例例2.9】G(Z):所以所以：L(G)=abnc|n0A=bA=bbA=bn,n0Z=aAcabnc,n0 =+Ab bn n =+即：即：Abn =+，n0即：即：Zabnc，n0 =+现在学习的是第18页，共51页则则VN=E(算术表达式算术表达式),T(项项),F(因式因式)；VT=i(变量或常数变量或常数),+,-,*,/,(,)；Z=E;P:【例例2.10】简单算术表达式文法简单算术表达式文法【注注】此文法定义了算术表达式的层次嵌套结构

15、此文法定义了算术表达式的层次嵌套结构:E-T|E+T|E-TT-F|T*F|T/FF-i|(E)令令G(Z)=(VN,VT,Z,P)(表达式表达式 )表达式表达式项项因式因式文法文法E-E+E|EE|E*E|E/E|i|(E)?现在学习的是第19页，共51页算术表达式文法应用示例：算术表达式文法应用示例：根据根据语言定义式语言定义式2.1，G(E):E-T|E+T|E-TT-F|T*F|T/FF-i|(E)证明证明i*(i+i-i)是文法是文法G(E)的一个的一个句子句子(即合法的即合法的算术表达式算术表达式):=+Ei*(i+i-i)成立吗？成立吗？E =+Ei*(i+i-i)=T=T*

16、F=T*(E)=T*(E-T)=T*(E+T-T)=F*(E+T-T)=i*(E+T-T)=观察推导过程，可以看到：一旦产生式选择错了，会导致失败！=i*(i+i-i)L(G)=x|Zx,xVT*=+合法的算术表达式是指：合法的算术表达式是指：现在学习的是第20页，共51页文法有两种基本运算：文法有两种基本运算：推导推导和和归约归约v星推导星推导():2.3各种语法成分的定义各种语法成分的定义1.直接推导直接推导(=):xAy=x y即：指用产生式的右部符号串即：指用产生式的右部符号串替换替换左部非终结符。左部非终结符。加推导算符v加推导():设设x,y(VN+VT)*，A-P =*=*（当

17、且仅当（当且仅当=1=2=）即：指一步或一步以上的直接推导运算。即：指一步或一步以上的直接推导运算。（当且仅当当且仅当=或或=1=2=)即：指零步或零步以上的直接推导运算。即：指零步或零步以上的直接推导运算。直接推导算符星推导算符 =+=+2.3.1文法的运算文法的运算现在学习的是第21页，共51页 =.+=.+2.直接归约直接归约():x yxAy =.=.（当且仅当（当且仅当 1 1 2 2 ）=.=.=.=.v星归约星归约():=.*=.*（当且仅当（当且仅当 =或或 1 1 2 2 )=.=.=.=.即：直接归约是直接推导的即：直接归约是直接推导的逆运算逆运算，用产生式的左，用产生式的

18、左部非终结符替换右部符号串。部非终结符替换右部符号串。即：指零步或零步以上的直接归约运算。即：指零步或零步以上的直接归约运算。即：指一步或一步以上的直接归约运算。即：指一步或一步以上的直接归约运算。直接归约算符加归约算符星归约算符l加归约加归约():2.3.1文法的运算文法的运算现在学习的是第22页，共51页规范推导和规范归约规范推导和规范归约实用中最常见的两种运算：l最左推导()每次推导皆最左非终结符优先；l最左归约()每次归约皆最左可归约串优先。=+=.+l最右推导也称为规范推导l最左归约也称为规范归约同一个句子可以通过不同的推导序列推导出来同一个句子可以通过不同的推导序列推导出来通常

19、只考虑两种特殊推导，即通常只考虑两种特殊推导，即最左推导和最右推导最左推导和最右推导N1=N=ND=N2=D2=1212D2N2NDNN1N1-NN-ND|DD-0|1|2 =.=.=.=.=.最左归约是最右推导的逆过程！最左归约是最右推导的逆过程！现在学习的是第23页，共51页i+i*il给定一个符号串给定一个符号串i+i*i：T-F|T*F|T/FF-i|(E)G(E):E-T|E+T|E-T文法运算示例：文法运算示例：【例例2.11】算术表达式文法：算术表达式文法：=.=.=.=.=.=.=.=.2.最左归约最左归约(从从符号串出发符号串出发)过程：过程：E=E+T=T+T=F+T=i+

20、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页即：句型是由文法开始符号加推导出的任一符号串。即：句型是由文法开始符号加推导出的任一符号串。2.3.2句型、句子和语法树句型、句子和语法树若有若有且且 VT*，则，则是句子；是句子；Z=+若有若有,则则是句型；是句型；Z=+2.句子句子即：句子是由开始符号加推导出的任一即：句子是由开始符号加推导出的任一终结终结符号串。符

21、号串。1.句型句型设有文法设有文法G(Z)=(VN,VT,Z,P)，则：，则：3.语法树语法树句型句型(句子句子)产生过程的一种树结构表示；产生过程的一种树结构表示；树根树根开始符号开始符号；树叶树叶给定的给定的句型句型(句子句子)。现在学习的是第25页，共51页 A x1 x2xn 重复步骤重复步骤，直到推导过程结束为止。，直到推导过程结束为止。置树根为开始符号；置树根为开始符号；【语法树的构造算法语法树的构造算法】若若推导推导采用了采用了产生式产生式：A-x1x2xn，则有，则有子树：子树：如此构造的语法树，其如此构造的语法树，其全体树叶全体树叶(自左至右自左至右)恰好是给定的句型恰好是给

22、定的句型(句子句子)。现在学习的是第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-TT-F|T*F|T/FF-i|(E)【证证】即：即：E(T/F+F)*i =+现在学习的是第27页，共51页句型句型(T/F+F)*i的语法树构造：的语法树构造：ETT*FF(E)E+TTT/FFiE-T

23、|E+T|E-TT-F|T*F|T/FF-i|(E)【注注】关于语法树：关于语法树：l子树：由某一结点连子树：由某一结点连同同所有分支所有分支组成的部组成的部分。分。l简单子树简单子树：仅具有：仅具有单层分支单层分支的子树。的子树。现在学习的是第28页，共51页3.句柄句柄 -一个句型的一个句型的最左简单短语最左简单短语称为该句型的称为该句型的句柄句柄。2.3.3短语、简单短语和句柄短语、简单短语和句柄设文法设文法G(Z),x y是一个句型，则是一个句型，则:则则是句型是句型x y关于关于A的短语的短语(A是是的名字的名字)；=+=+1.1.短语短语若若 Z xAy xZ xAy x

24、y y ZxAy 任一任一子树子树的的树叶全体树叶全体(具有共同具有共同祖先祖先的叶节点符号串的叶节点符号串)皆为皆为短语短语；=+2.简单短语简单短语若若 Z xAy Z xAy=x x y y则则是句型是句型x y关于关于A的简单短语的简单短语(A是是的名字的名字)；任一任一简单子树简单子树的的树叶全体树叶全体(具有共同具有共同父亲父亲的叶节点符的叶节点符号串号串)皆为皆为简单短语简单短语；现在学习的是第29页，共51页(他他)(哥哥哥哥)(喜欢喜欢)(看看)图图2.2他哥哥喜欢看书他哥哥喜欢看书的的语法树语法树(书书)2.3.3 短语、简单短语和句柄【例2.13】图2.2为一个中文

25、句型的语法树：短语-他哥哥,喜欢看,书，喜欢看书，他哥哥喜欢看书简单短语-他哥哥，喜欢看，书句柄-他哥哥（最左边的简单短语!）现在学习的是第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 EE-TE+TT*FFT/Fi图图2.3E+F-T/F*i的语法树的语法树 2.3.3 短语、简单短语和句柄现在学习的是第31页，共51页一类典型的综合例题：一类典型的综合例题：【例例2.15】G(S):S-aAcBe;A-Ab|b;B-d给定符号串给定符号串：

26、aAbcde 证明证明 =aAbcde是一个句型；是一个句型；画出句型画出句型的语法树；的语法树；指出指出中的短语、简单短语和句柄。中的短语、简单短语和句柄。【题解题解】S=aAcBe=aAbcBe=aAbcde语法树如右图：语法树如右图：短语、简单短语和句柄短语、简单短语和句柄:S S a A c B e a A c B e A b d A b d 短语短语:aAbcde,Ab,d简单短语简单短语:Ab,d句柄：句柄：Ab现在学习的是第32页，共51页G2(S):S-bS|a-直接右递归直接右递归文法。文法。2.4两种特性文法两种特性文法 2.4.1 递归文法设有文法：设有文法：G(Z

27、)=(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)：Z-aAbB|cZA-bBc|B-BbAc|aZ-cZ直接右递归性直

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

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

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

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

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

35、页删除删除产生式产生式【算法算法】1.首先构造可以推出空串的非终结符集：首先构造可以推出空串的非终结符集：V 若有若有A-;则则令令AV;若有若有B-A1An且全部且全部AiV;则令则令BV;重复步骤重复步骤，直到，直到V 不再扩大为止。不再扩大为止。2.删除删除G(Z)中的中的A-形式的产生式；形式的产生式；假定文法假定文法G(Z);L(G)3.依次改写依次改写G(Z)中的产生式中的产生式B-X1X2Xn:若有若有XiV 则用则用(Xi|)替换之替换之(一个分裂为两个一个分裂为两个)；若有若有j个个XiV，则一个产生式将分裂为则一个产生式将分裂为2j个个!现在学习的是第42页，共51页

37、科斯范式）表示法必选其中之一！例如：有例如：有A-a|a 也可写成：也可写成：A-aA；A-|【注注】此法又称此法又称提公因子法，提公因子法，利用此法可以解决：利用此法可以解决：具有相同左部的各产生式首符号不同！具有相同左部的各产生式首符号不同！基本思想基本思想：扩展文法，引进新的：扩展文法，引进新的描述符号描述符号：()圆括号；圆括号；方括号；方括号；花括号花括号可变换成可变换成:A-a(|)现在学习的是第44页，共51页也可写成：也可写成：S-S;S-|令令=或者或者 2.可选项法（方括号法）例如：例如：S-|可选也可不选！例如例如条件语句文法：条件语句文法：S-if(B)S可变换成：可变

38、换成：S-S-if(B)SelseS可变换成：可变换成：S-if(B)SelseSS(语句)，B(布尔表达式)或：或：S-if(B)SS;S-elseS|BNF（巴科斯范式）表示法（巴科斯范式）表示法现在学习的是第45页，共51页3.重复可选项法（花括号法）例如：例如：A-A|令令=或或或或或或可变换为：可变换为：A-通过递推方法，可得：通过递推方法，可得：A=A=A=A=*有有A-或或A A;A-A|也可写成：也可写成：A A;A-A|验证：验证：【注注】此方法常用来消除文法的此方法常用来消除文法的直接左递归直接左递归！BNF（巴科斯范式）表示法（巴科斯范式）表示法现在学习的是第46页，共

39、51页产生式形式为：产生式形式为：A-u 2.6形式语言的分类形式语言的分类 Chomsky把形式语言分为把形式语言分为四类四类，分别由四类文法定义；，分别由四类文法定义；四类文法的区别在于四类文法的区别在于产生式的形式不同产生式的形式不同：(2)1型语言型语言由由1型文法型文法定义定义(1)0型语言型语言由由0型文法型文法定义定义又称无限制文法！产生式形式为：产生式形式为：-(VN VT)*且至少有一个非终结符且至少有一个非终结符(VN VT)*又称上下文有关文法！A VN,(VN VT)*,u(VN VT)+A只有在只有在和和这样的上下文环境中才能换成这样的上下文环境中才能换成u现

40、在学习的是第47页，共51页2.6形式语言的分类形式语言的分类产生式形式为：产生式形式为：A-aB或或A-a产生式形式为：产生式形式为：A-(3)2型语言型语言由由2型文法型文法定义定义(4)3型语言型语言由由3型文法型文法定义定义又称上下文无关文法！编译处理中，主要应用编译处理中，主要应用后两种文法后两种文法！【注注】四类语言为四类语言为包含包含关系，且有关系，且有L0L1L2L3；A VN,(VN VT)*将将A替换成替换成时，与时，与A的上下文无关的上下文无关又称正规文法！A,B VN,a VT*产生式形式为：产生式形式为：A-Ba或或A-a右线性文法右线性文法左线性文法左线性文

41、法现在学习的是第48页，共51页主要内容总结主要内容总结文法是规则集合，四元组：G(Z)=(VN,VT,Z,P)文法所定义的语言：文法应用示例：文法应用示例：简单语言的文法构造：简单语言的文法构造：无符号整数无符号整数文法：文法：G(N):N-dN|d N-dN|d L(G)=x|Z x,xVL(G)=x|Z x,xVT T*=+I-A|A|A-A-A|dA|A|dA|求解文法所定义的语言求解文法所定义的语言(或句或句子子)方法：方法：v形式语言形式语言是是符号串集合符号串集合且由且由文法文法定义定义！正规方程组迭代求语言（如正规方程组迭代求语言（如标识符文法）标识符文法）直接由定义求解

42、句子直接由定义求解句子(如如算术表达式文法算术表达式文法)。标识符标识符文法：文法：G(G(I):):d(数字),(字母)现在学习的是第49页，共51页主要内容总结主要内容总结文法的运算：推导和归约(二者互为逆运算)推导：归约归约：v文法的文法的运算运算与主要与主要语法成分语法成分的定义的定义！主要语法成分的定义主要语法成分的定义 =+=+=.=.+=.+句型，句子，语法树，句型，句子，语法树，短语，简单短语，句柄短语，简单短语，句柄从语法树上看从语法树上看句型句型(句子句子)、短语、简单短语、短语、简单短语和和句柄：句柄：直接推导直接推导(=),(=),加推导加推导(),(),最左推

43、导最左推导();();直接归约直接归约(),(),加归约加归约(),(),最左归约最左归约();();语法树的语法树的树叶全体树叶全体-句型句型(句子句子)；语法树的语法树的子树树叶全体子树树叶全体短语短语(简单短语简单短语)；语法树的语法树的最左简单子树树叶全体最左简单子树树叶全体句柄！句柄！现在学习的是第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页

展开阅读全文