《形式语言基础》PPT课件.ppt

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

1、编译程序的设计原理与实现编译程序的设计原理与实现如何让计算机如何让计算机认识、理解认识、理解和和执行执行高级程序设计语言？高级程序设计语言？第第2章章形式语言基础形式语言基础 计算机处理语言，首先应考虑语言的形式化、规范化，使其具有可计算性和可操作性；这就是形式语言理论研究的问题。形式语言诞生于1956年，由Chomsky创立。通常，语言研究至少涉及三个方面：语法、语义和语用；形式语言的基本观点是：语言是符号串之集合！形式语言理论研究的形式语言理论研究的基本问题基本问题是：是：研究符号串集合的表示方法、结构特性研究符号串集合的表示方法、结构特性以及运算规律。以及运算规律。因此：因此：【内容提要

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

3、,10,11;字母表字母表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,两个语言两个语言!1.1.连接连接：.=如：a.b=ab 2.1.1符号串符号串(集合集合)的运算的运算3.3.方幂方幂：n n=n-1n-1=n-

4、1n-1 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.或或：|=或者或者 这是一种这是一种泛指泛指！【例【例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

5、即：即：(a|b)*=(a|b)n,n0同理：同理：(a|b)+=(a|b)n,n0 符号串运算示例符号串运算示例泛指：泛指：由由a，b组成的组成的任意符号串！任意符号串！（包括空串）（包括空串）(3)ab|cd=ab或者或者cd1.乘积乘积：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;.符号串集合的运算符号串集合的运算

6、 2.1.1符号串符号串(集合集合)的运算的运算 符号串集合运算示例符号串集合运算示例【例【例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【例【例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*就是该字母就是该字母表表 上上的所有符号串的所有符号串(包括空串包括空串)的集合。的集合。2.2形式语言是由文法定义的形式语言是由文法定义的 形式语言是符号串的集合，对形式语言的描述形式语言是符号串的集合，对形式语言的描述有两种方式：有两种方式：(1)枚举方式枚举方式：语言为有穷集合时：语言为有穷集合时设有字母表设有字母表A=a,b,c,有有L1=a,aa,ab,ac,L2=c,cc(2)使用文法使用文法：语言为无穷集合时，无法枚举：语言为无穷集合时，无法枚举 设有字母表设有字母表B=0,1,B+=

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

9、言是由文法定义的形式语言是由文法定义的每个元素每个元素2.2.1什么是文法什么是文法？Z-或者或者A-|注：此文法实际称为上下文无关文法注：此文法实际称为上下文无关文法描述符号描述符号：-(定义为定义为/生成生成)，|(或者是或者是)文法符号文法符号：Z,AVN，,(VN+VT)*每个规则每个规则 【注意】提供了规则集，就相当给出了一个文法：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.7】L=abnc|n0，字母表：，字母表：=a,b,c；展开：展开：L=ac,abc,abbc,abbbc

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

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

12、abc=abc S S=aAc=aAc=bAc=bAc=abbAc=abbAc=abbc=abbc 一个句子一个句子!又一个句子又一个句子!S abS abn nc,n0 c,n0 =+再一个句子再一个句子!非终结符号非终结符号【例【例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)得：得：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正规方程式正规方程式标识符：字母开头的字母、数字序列标识符：字母开头的字母、数字序列求解求解文法文法所定义的语言所定义的语言(2)则则L(G)的求解过程的求解过程代代入法入法：Z-aAcA-bA|【例【例2.9】G(Z):所以所以：L(G)=ab

14、nc|n0A=bA=bbA=bn,n0Z=aAcabnc,n0 =+Ab bn n =+即：即：Abn =+，n0即：即：Zabnc，n0 =+则则VN=E(算术表达式算术表达式),T(项项),F(因式因式)；VT=i(变量或常数变量或常数),+,-,*,/,(,)；Z=E;P:【例【例2.10】简单算术表达式文法】简单算术表达式文法【注】此文法定义了算术表达式的层次嵌套结构【注】此文法定义了算术表达式的层次嵌套结构: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

15、|(E)?算术表达式文法应用示例：算术表达式文法应用示例：根据根据 语言定义式语言定义式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*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

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

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

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

19、最左归约是最右推导的逆过程！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+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.最左推导最左推导(从从开始符号出发开始符号出发)过程：过程：最左非终结符最左非终结符最左可

20、归约串最左可归约串即：句型是由文法开始符号加推导出的任一符号串。即：句型是由文法开始符号加推导出的任一符号串。2.3.2句型、句子和语法树句型、句子和语法树若有若有且且 VT*，则，则 是句子；是句子；Z=+若有若有,则则 是句型；是句型；Z=+2.句子句子即：句子是由开始符号加推导出的任一即：句子是由开始符号加推导出的任一终结终结符号串。符号串。1.句型句型设有文法设有文法G(Z)=(VN,VT,Z,P)，则：，则：3.语法树语法树句型句型(句子句子)产生过程的一种树结构表示；产生过程的一种树结构表示；树根树根开始符号开始符号；树叶树叶给定的给定的句型句型(句子句子)。A x1 x2xn 重

21、复步骤重复步骤，直到推导过程结束为止。，直到推导过程结束为止。置树根为开始符号；置树根为开始符号；【语法树的构造算法】【语法树的构造算法】若若推导推导采用了采用了产生式产生式：A-x1x2xn，则有，则有子树：子树：如此构造的语法树，其如此构造的语法树，其全体树叶全体树叶(自左至右自左至右)恰好是给定的句型恰好是给定的句型(句子句子)。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是一个句型是一个句型(表达式

22、型表达式型)；(2)画出该句型的语法树。画出该句型的语法树。E-T|E+T|E-TT-F|T*F|T/FF-i|(E)【证】【证】即：即：E(T/F+F)*i =+句型句型(T/F+F)*i的语法树构造：的语法树构造：ETT*FF(E)E+TTT/FFiE-T|E+T|E-TT-F|T*F|T/FF-i|(E)【注】关于语法树：【注】关于语法树：子树：由某一结点连子树：由某一结点连同同所有分支所有分支组成的部组成的部分。分。简单子树简单子树 ：仅具有：仅具有单层分支单层分支的子树。的子树。3.句柄句柄-一个句型的一个句型的最左简单短语最左简单短语称为该句型的称为该句型的句柄句柄。2.3.3 短

23、语、简单短语和句柄设文法设文法G(Z),x y是一个句型，则是一个句型，则:则则 是句型是句型x y关于关于A的短语的短语(A是是 的名字的名字)；=+=+1.1.短语短语 若若 Z xAy x Z xAy x y y ZxAy 任一任一子树子树的的树叶全体树叶全体(具有共同具有共同祖先祖先的叶节点符号串的叶节点符号串)皆为皆为短语短语；=+2.简单短语简单短语 若若 Z xAy Z xAy=x x y y则则 是句型是句型x y关于关于A的简单短语的简单短语(A是是 的名字的名字)；任一任一简单子树简单子树的的树叶全体树叶全体(具有共同具有共同父亲父亲的叶节点符的叶节点符号串号串)皆为皆为简

24、单短语简单短语；(他他)(哥哥哥哥)(喜欢喜欢)(看看)图图2.2他哥哥喜欢看书他哥哥喜欢看书的的语法树语法树(书书)2.3.3 短语、简单短语和句柄【例2.13】图2.2为一个中文句型的语法树：短 语-他哥哥,喜欢看,书，喜欢看书，他哥哥喜欢看书简单短语-他哥哥，喜欢看，书句 柄-他哥哥（最左边的简单短语!）【例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 短语、简单短语和句柄 一类

25、典型的综合例题：一类典型的综合例题：【例【例2.15】G(S):S-aAcBe;A-Ab|b;B-d给定符号串给定符号串：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句柄：句柄：AbG2(S):S-bS|a-直接右递归直接右

26、递归文法。文法。2.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-直接左递归直接左递归文法；文法；递归文法示例递归文法示例【例【例2.16】G(Z)

27、：Z-aAbB|cZA-bBc|B-BbAc|aZ-cZ直接右递归性直接右递归性；B-BbAc直接左递归性直接左递归性；A=bBc=bBbAcc即即A A 具有递归性具有递归性(且且 又称为又称为A具有自嵌套性具有自嵌套性)可以统称文法可以统称文法G(Z)具有递归性。具有递归性。=+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 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 二义性文法会引起歧义，二义性文法会引起歧义，应尽量避免之！应尽量避免之！文法二义性的消除文法二义性的消除【方法【方法1 1】不改变文法的原有规则】不改变文法的原有规则,加进一些非形加进一些非形 式的规定。式的规定。【方法【方法2 2】构造一个】构造一个等价的无二义性文法等价的无二义性文法，将排除，将排除 二义性的规则合并到文法中二义性的规则合并到文法中加进运算符的优

29、先顺序和结合规则加进运算符的优先顺序和结合规则对对G(E)，规定，规定*优于优于+，*和和+服从左结合服从左结合G(E)-G(E):E-E+T|TT-T*F|FF-(E)|i;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

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

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

32、非终结符(连同其产生式连同其产生式)。删除删除不可用不可用产生式算法：产生式算法：(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不再扩大为止。不再扩大为止。=+文法的化简文法的化简 文法化简示例文法化简示例l化简步骤：G(S):S-Be|Ec G(

33、S):S-Be|Ec A-Ae|e|A A-Ae|e|A B-C e|AfB-C e|AfC-Cf;D-f;G-bC-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 删除删除 产生式产生式【算法】【算法】1.首先构造可以推出空串的非终结符集：首先构造可以推出空串的非终

34、结符集：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个个!删除删除 产生式示例：产生式示例：(1)求解求解V=A,B(2)删除删除 产生式产生式得：得：S-aAbc|bS；A-dABe；B-A

35、|b(3)改写改写右部含有右部含有V 中元素的产生式：中元素的产生式：S-a(A|)bcS-aAbc|abcA-d(A|)(B|)eA-dABe|dBe|dAe|deB-(A|)B-A含有含有V 元素元素的产生式的产生式综合综合G(S)：S-aAbc|abc|bSA-dABe|dBe|dAe|deB-A|b【例【例2.20】G(S):S-aAbc|bSA-dABe|;B-A|b令令(|)=或者或者 1.必选项法（圆括号法）BNF（巴科斯范式巴科斯范式）表示法）表示法必选其中之一！必选其中之一！例如：有例如：有A-a|a 也可写成：也可写成：A-aA；A-|【注】此法又称【注】此法又称提公因子法

36、，提公因子法，利用此法可以解决：利用此法可以解决：具有相同左部的各产生式首符号不同！具有相同左部的各产生式首符号不同！基本思想基本思想：扩展文法，引进新的：扩展文法，引进新的描述符号描述符号：()圆括号；圆括号；方括号；方括号；花括号花括号可变换成可变换成:A-a(|)也可写成：也可写成：S-S;S-|令令=或者或者 2.可选项法（方括号法）例如：例如：S-|可选也可不选！可选也可不选！例如例如条件语句文法：条件语句文法：S-if(B)S可变换成：可变换成：S-S-if(B)SelseS可变换成：可变换成：S-if(B)SelseSS(语句语句)，B(布布尔表达式尔表达式)或：或：S-if(B

37、)SS;S-elseS|BNF（巴科斯范式巴科斯范式）表示法）表示法3.重复可选项法（花括号法）例如：例如：A-A|令令=或或 或或或或可变换为：可变换为：A-通过递推方法，可得：通过递推方法，可得：A=A=A=A=*有有A-或或A A;A-A|也可写成：也可写成：A A;A-A|验证：验证：【注】此方法常用来消除文法的【注】此方法常用来消除文法的直接左递归直接左递归！BNF（巴科斯范式巴科斯范式）表示法）表示法产生式形式为：产生式形式为：A-u 2.6形式语言的分类形式语言的分类 Chomsky把形式语言分为把形式语言分为四类四类，分别由四类文，分别由四类文法定义；四类文法的区别在于法定义；

38、四类文法的区别在于产生式的形式不同产生式的形式不同：(2)1型语言型语言由由1型文法型文法定义定义(1)0型语言型语言由由0型文法型文法定义定义又称又称无限制文法无限制文法！产生式形式为：产生式形式为：-(VN VT)*且至少有一个非终结符且至少有一个非终结符(VN VT)*又称又称上下文有关文法上下文有关文法！A VN,(VN VT)*,u(VN VT)+A只有在只有在 和和 这样的上下文环境中才能换成这样的上下文环境中才能换成u2.6形式语言的分类形式语言的分类 产生式形式为：产生式形式为：A-aB或或A-a产生式形式为：产生式形式为：A-(3)2型语言型语言由由2型文法型文法定义定义(4

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

40、的文法构造：无符号整数无符号整数文法：文法：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形式语言形式语言是是符号串集合符号串集合且由且由文法文法定义定义！正规方程组迭代求语言（如正规方程组迭代求语言（如标识符文法）标识符文法）直接由定义求解句子直接由定义求解句子(如如算术表达式文法算术表达式文法)。标识符标识符文法：文法：G(G(I):):d(d(数字数字),),(字字母母)主要内容总结主要内容总结 文法的运算：推导和归约(二者

41、互为逆运算)推导：归约归约 ：v文法的文法的运算运算与主要与主要语法成分语法成分的定义的定义！主要语法成分的定义主要语法成分的定义 =+=+=.=.+=.+句型，句子，语法树，句型，句子，语法树，短语，简单短语，句柄短语，简单短语，句柄从语法树上看从语法树上看 句型句型(句子句子)、短语、简单短语、短语、简单短语和和句柄：句柄：直接推导直接推导(=),(=),加推导加推导(),(),最左推导最左推导();();直接归约直接归约(),(),加归约加归约(),(),最左归约最左归约(););语法树的语法树的树叶全体树叶全体-句型句型(句子句子)；语法树的语法树的子树树叶全体子树树叶全体短短语语(简

42、单短语简单短语)；语法树的语法树的最左简单子树树叶全体最左简单子树树叶全体 句柄！句柄！课后习题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)