第二章--形式语言基础课件

编译程序的设计原理与实现编译程序的设计原理与实现如何让计算机如何让计算机认识认识、理解、理解 和和 执行执行 高级程序设计语言高级程序设计语言？第第 2 2 章章 形式语言基础形式语言基础 计算机处理语言，首先应考虑语言的形式化、规计算机处理语言，首先应考虑语言的形式化、规范化，使其具有可计算性和可操作性；这就是形式语范化，使其具有可计算性和可操作性；这就是形式语言理论研究的问题。言理论研究的问题。形式语言诞生于形式语言诞生于19561956年，由年，由chomskychomsky创立。通常，创立。通常，语言研究至少涉及三个方面：语言研究至少涉及三个方面：语法语法、语义语义和和语用语用；这里仅侧重于这里仅侧重于语法的研究语法的研究。形式语言的形式语言的基本观点基本观点是是 ：语言是符号串之集合！语言是符号串之集合！形式语言理论研究的形式语言理论研究的基本问题基本问题是：是：研究符号串集合的表示方法、结构特性研究符号串集合的表示方法、结构特性 以及运算规律。以及运算规律。【前前 言言】【内容提要内容提要】第第 2 2 章章 形式语言基础形式语言基础 2.12.1 形式语言是形式语言是符号串集合符号串集合 2.22.2 形式语言是由形式语言是由文法定义文法定义的的 2.32.3 主要主要语法成分语法成分的定义的定义 2.42.4 两类两类特性文法特性文法 2.5 2.5 文法变换文法变换方法方法 2.6 2.6 关于关于形式语言的分类形式语言的分类问题问题 字母表字母表 -元素元素(符号符号)的非空有限集合；的非空有限集合；符号串符号串 -符号的有限序列；符号的有限序列；符号串集合符号串集合 -有限个或者无限个符号串组成有限个或者无限个符号串组成的集合；的集合；规规 则则 -以某种形式表达的在一定范围内共以某种形式表达的在一定范围内共同遵守的章程和制度；这里，指符号串的组成同遵守的章程和制度；这里，指符号串的组成规则。规则。2.1 2.1 形式语言是符号串集合形式语言是符号串集合 【形式语言形式语言】是是字母表字母表上的符号，按一定的上的符号，按一定的规则规则组成的所有组成的所有符号串集合符号串集合；其中的每个符号串；其中的每个符号串称为称为句子句子。【名词解释名词解释】：三要素！三要素！【例例2.12.1】L L1 1=00,01,10,11;=00,01,10,11;字母表字母表1 1=0,1,=0,1,句子有：句子有：00,01,10,1100,01,10,11【注注】b b0 0=（空符号串）空符号串）,b,b1 1=b,b=b,b2 2=bb,b=bb,b3 3=bbbbbb,L L1 1 为有限语言为有限语言;L;L2 2 为无限语言。为无限语言。形式语言概念示例：形式语言概念示例：【例例2.22.2】L L2 2=ababm mc,bc,bn n|m0,n0|m0,n0 字母表字母表2 2=a,b,c,=a,b,c,句型句型1:1:ababm mc c,有句子：有句子：abcabc,abbcabbc,abbbcabbbc,句型句型2:2:b bn n ;有句子：有句子：,b,bb,b,bb,bbbbbb,两个语言！两个语言！1.1.连接连接：.=如如 a.b=a.b=abab 2.1.1 2.1.1 符号串符号串(集合集合)的运算的运算3.3.方幂方幂：n n=n-1n-1=n-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.1.1 2.1.1 符号串符号串(集合集合)的运算的运算(续续1)1)【例例】：ab|cdab|cd=abab（或者或者 cdcd ）abc.deabc.de=abcdeabcde(a|b)(a|b)1 1=(a|b)=a|b =(a|b)=a|b (a|b)(a|b)*=(a|b)=(a|b)0 0|(a|b)|(a|b)1 1|(a|b)|(a|b)2 2|(a|b)(a|b)2 2=(a|b)(a|b)=(a|b)(a|b)=aa|ab|ba|bbaa|ab|ba|bb 即：即：(a|b)(a|b)*=(a|b)=(a|b)n n，n0n0同理：同理：(a|b)(a|b)+=(a|b)=(a|b)n n，n n0 0 符号串运算示例符号串运算示例泛指：泛指：由由a，b组成的组成的任意符号串！任意符号串！（包括空串）（包括空串）1.1.乘积乘积：AB=AB=xyxy|x|x A A 且且 y y BB 2.1.1 2.1.1 符号串符号串(集合集合)的运算的运算(续续2)2)4.4.闭包：闭包：A A 的正闭包的正闭包：A A+=A=A1 1AA2 2AAn nA A 的星闭包的星闭包：A A*=A=A0 0AA1 1AA2 2AAn n设设 A A 和和 B B 为两个符号串集合，则：为两个符号串集合，则：2.2.和：和：AB=A+B=x|xAB=A+B=x|x A A 或或 x x BB 3.3.方幂：方幂：A An n=AAA=AA=AAA=AAn-1n-1=A=An-1n-1A An n个个 A A0 0=;A A1 1=A=A;A A2 2=AA;A=AA;A3 3=AAA;=AAA;.符号串集合的运算符号串集合的运算 符号串集合运算示例：符号串集合运算示例：【例例2.32.3】设设 A=a,b,B=c,dA=a,b,B=c,d 则则 A+B=a,b,c,d A+B=a,b,c,d 则则 ABAB=xy|xxy|x A,yA,y B B=ac,ad,bc,bdac,ad,bc,bd【例例2.42.4】设设 A=aA=a 则则 A A*=A=A0 0AA1 1AA2 2AAn n =+a+aa+aaaa+aa+aaa+=,a,aa,aaaa,aa,aaa,=a =an n|n0|n0 【例例2.52.5】设设 A=aA=a，bb，A A*=?=?A A*=A=A0 0AA1 1AA2 2AAn n A A0 0=;A A1 1=A=a=A=a，b;b;A A2 2=A.A=a=A.A=a，b.ab.a，b=b=aa,ab,ba,bbaa,ab,ba,bb;A A3 3=A.A=A.A2 2=a=a，b.aa,ab,ba,bbb.aa,ab,ba,bb =aaa,aab,aba,abb,baa,bab,bba,bbbaaa,aab,aba,abb,baa,bab,bba,bbb;A A*=x|x=(a|b)=x|x=(a|b)n n ，n0 n0 符号串集合运算示例符号串集合运算示例(续续)：推论推论：若：若 A A为任一字母表为任一字母表,则则 A A*就是该字母就是该字母表上表上的所有符号串的所有符号串(包括空串包括空串)的集合。的集合。S,A S,A 定义的对象定义的对象(S(S 句子句子,最大的定义对象，又最大的定义对象，又 称为开始符号称为开始符号;A;A为句型为句型aAcaAc的的短语短语），），a,b,c-a,b,c-为字母表为字母表中的符号中的符号;-;-空符号串。空符号串。-,|-,|-为为描述符号描述符号(-(-定义为定义为;|;|或者是）或者是）2.1.2 2.1.2 符号串集合的文法描述符号串集合的文法描述【例例2.52.5】L=L=ababn nc c|n0|n0，字母表字母表：=a,b,c=a,b,c；展开展开：L=L=ac,abc,abbc,abbbcac,abc,abbc,abbbc,右图给出的表示右图给出的表示 S-S-aAcaAc A-A-bAbA|长久以来，探讨符号串集合长久以来，探讨符号串集合(即形式语言即形式语言)的各种的各种描述方法，一直是语言计算机处理的重要任务之一。描述方法，一直是语言计算机处理的重要任务之一。方法方法-文法规则文法规则；其中：其中：从开始符号开始符号出发，对符号串中的定义对象，采用推导推导的方法（用其规则右部替换左部）产生新的符号串，如此进行，直到新符号串中不再出现定义的对象为止，则最终的符号串就是一个句子句子。S-S-aAcaAc A-A-bAbA|规则规则应用应用说明示例：说明示例：【句子产生过程句子产生过程】(=推导算符推导算符):):怎样利用上述怎样利用上述文法规则文法规则表示语言表示语言L?L?S S=aAcaAc=ac=ac=ac=ac S S=aAcaAc=abAcabAc=abcabc=abcabc S S=aAcaAc=abAcabAc=abbAcabbAc=abbcabbc 一个句子一个句子!又一个句子又一个句子!S S ababn nc c,n0 ,n0 =+再一个句子再一个句子!【定义定义】文法文法(grammar)(grammar)是规则的有限集是规则的有限集,其中的上下文无关文法可定义为四元组：其中的上下文无关文法可定义为四元组：G(Z)=(VG(Z)=(VN N,V,VT T,Z,P),Z,P)V VN N:非终结符集（定义的对象集，如：语法成分等非终结符集（定义的对象集，如：语法成分等)；V VT T:终结符集（字母表）；终结符集（字母表）；Z:Z:开始符号（研究范畴中，最大的定义对象）；开始符号（研究范畴中，最大的定义对象）；P:P:规则集（又称产生式集）；规则集（又称产生式集）；A-A-或者或者 A-A-|其中其中,描述符号描述符号 ：-(-(定义为定义为)，|(|(或者是或者是)文法符号文法符号 ：Z,AVZ,AVN N，,(V(VN N+V+VT T)*2.2 2.2 形式语言是由文法定义的形式语言是由文法定义的每个元素每个元素每个规则每个规则2.2.1 2.2.1 什麽是文法什麽是文法？2.2 2.2 形式语言是由文法定义的（续形式语言是由文法定义的（续1 1）【注意注意】提供了规则集，就相当给出了一个文法：提供了规则集，就相当给出了一个文法：S-S-aAcaAc A-A-bAbA|G(S):2.2.2 2.2.2 文法是怎样定义语言的？文法是怎样定义语言的？则则 L(G)=x|Z x,xVL(G)=x|Z x,xVT T*即：一个文法所定义的即：一个文法所定义的语言语言，就是由该文法，就是由该文法开始开始设设 有文法有文法 G(Z),L(G)G(Z),L(G)为为G G所定义的语言；所定义的语言；V VT T=a,b,c=a,b,c;Z Z=S=S;P P:V VN N=S,A=S,A；G(Z)=(VG(Z)=(VN N,V,VT T,Z,P),Z,P)利用利用 =进行连续推导之意！进行连续推导之意！符号推导出符号推导出的所有的所有仅含终结符仅含终结符的的符号串符号串之集合之集合。其中的每个符号串皆称为其中的每个符号串皆称为句子句子。=+2.1【例例2.62.6】标识符标识符的文法的文法 【标识符标识符】指字母开头的字母、数字序列。指字母开头的字母、数字序列。令令 G(Z)=(VG(Z)=(VN N,V,VT T,Z,P),Z,P)则则 V VN N=I(=I(标识符标识符),A(),A(标识符尾标识符尾)；V VT T=(字母字母),d),d(数字）数字）；Z =I;Z =I;P:P:I-A|A|A-A-A|d A|A|d A|同理，同理，【无符号整数无符号整数】文法文法 可写成：可写成：G(N):G(N):N-d N|dN-d N|d其其四元组四元组也可写成：也可写成：G(N)=(N,d,N,P )得：得：I=(|d|d)n ,n0 令：令：I=A|A|A=A=A|d A|A|d A|标识符文法标识符文法所定义的语言求解：所定义的语言求解：上面构造的上面构造的标识符文法标识符文法属于属于正规文法正规文法(定义在后定义在后)类，类，正确性检验较容易；下面给出一个正确性检验较容易；下面给出一个算法算法：I-A|A|A-A-A|d A|A|d A|求解求解 I 值步骤：值步骤：先求解先求解 A:A=(|d|d)A,A=(|d|d)2 A,A=(|d|d)n A 代入代入 A=A=得：得：A=A=(|d|d)n ,n0 I=A|A|代入代入 A=A=(|d|d)n ,n0正规方程式正规方程式标识符标识符：字母开头的字母、数字序列；：字母开头的字母、数字序列；则则 V VN N=E(=E(算术表达式算术表达式),T(),T(项项)，F(F(因式因式)；V VT T=i(=i(变量或常数变量或常数),),+,-,*,/,(,+,-,*,/,(,）；Z =E;Z =E;P:P:【例例2.72.7】简单算术表达式文法简单算术表达式文法【注注】此文法定义了算术表达式的层次嵌套结构此文法定义了算术表达式的层次嵌套结构:E-T|E+E-T|E+T|E-T|E-T T T-F|T*T-F|T*F|T/F|T/F F F-i|(E )F-i|(E )令令 G(Z)=(VG(Z)=(VN N,V,VT T,Z,P),Z,P)(表达式表达式 )表达式表达式项项因式因式 算术表达式文法应用示例：算术表达式文法应用示例：根据根据 语言定义式语言定义式2.1，G(E):E-T|E+T|E-TG(E):E-T|E+T|E-T T-F|T*T-F|T*F|T/FF|T/FF-i|(E)F-i|(E)证明证明 i*(i+i-i)i*(i+i-i)是文法是文法G(E)的一个的一个句子句子(即即 合法的合法的算术表达式算术表达式):=+E i*(i+i-i)E i*(i+i-i)成立吗？成立吗？E E =+E i*(i+i-i)E i*(i+i-i)=T=T=T*F=T*F=T*(E)=T*(E)=T*(E-T)=T*(E-T)=T*(E+T-T)=T*(E+T-T)=F*(E+T-T)=F*(E+T-T)=i*(E+T-T)=i*(E+T-T)=观察推导过程，可观察推导过程，可以看到：一旦产生式以看到：一旦产生式选择错了，会导致失选择错了，会导致失败！败！=i*(i+i-i)=i*(i+i-i)L(G)=x|Z x,xVL(G)=x|Z x,xVT T*=+合法的算术表达式是指：合法的算术表达式是指：文法有两种基本运算：文法有两种基本运算：推导推导，归约归约。v 星推导星推导():():2.3 2.3 主要语法成分的定义主要语法成分的定义直接推导直接推导(=):(=):xAyxAy=x=x y y 即：指用产生式的右部符号串即：指用产生式的右部符号串替换替换左部非终结符。左部非终结符。加推导加推导算符算符v 加推导加推导():():设设 x,y(Vx,y(VN N+V+VT T)*，A-A-PP =*=*（当且仅当当且仅当=1 1=2 2=）即：指一步或一步以上的直接推导运算。即：指一步或一步以上的直接推导运算。（当且仅当当且仅当=或或=1 1=2 2=)即：指零步或零步以上的直接推导运算。即：指零步或零步以上的直接推导运算。直接推导直接推导算符算符星推导星推导算符算符 =+=+2.3.1 2.3.1 文法的运算问题文法的运算问题 实用中最常见的两种运算实用中最常见的两种运算：最左推导最左推导()()每次推导皆每次推导皆最左非终结符最左非终结符优先优先；最左归约最左归约()()每次归约皆每次归约皆最左可归约串最左可归约串优先优先。=.+=.+v 加归约加归约():直接归约直接归约():x():x y y xAyxAy =.=.（当且仅当当且仅当 1 1 2 2 ）=.=.=.=.v 星归约星归约()()：=.*=.*（当且仅当当且仅当 =或或 1 1 2 2 )=.=.=.=.=+=.+即：直接归约是直接推导的即：直接归约是直接推导的逆运算逆运算，用产生式的，用产生式的左部左部非终结符非终结符替换替换右部右部符号串符号串。即：指零步或零步以上的直接归约运算。即：指零步或零步以上的直接归约运算。即：指一步或一步以上的直接归约运算。即：指一步或一步以上的直接归约运算。直接归约直接归约算符算符加归约加归约算符算符星归约星归约算符算符这是相应的这是相应的算符算符i+i*ii+i*i给定一个符号串给定一个符号串 i+i*i i+i*i：T-F|T*F|T/F T-F|T*F|T/F F-i|(E)F-i|(E)G(E)G(E):E-T|E+T|E-T E-T|E+T|E-T文法运算示例：文法运算示例：【例例2.82.8】算数表达式文法：算数表达式文法：=.=.=.=.=.=.=.=.2.2.最左归约最左归约(从从符号串出发符号串出发)过程：过程：E E=E+T=E+T=T+T=T+T=F+T=F+T=i+T=i+T=i+T*F=i+T*F=i+F*F=i+F*F=i+i*F=i+i*F=i+i*i=i+i*i E E =+i+i*ii+i*iF+i*iF+i*iT+i*iT+i*iE+i*iE+i*iE+F*iE+F*iE+T*iE+T*iE+T*FE+T*FE+TE+TE i*i+ii*i+i =.+E E1.1.最左推导最左推导(从从开始符号出发开始符号出发)过程：过程：最左非终结符最左非终结符最左可归约串最左可归约串即：句型是由文法开始符号加推导出的任一符号串。即：句型是由文法开始符号加推导出的任一符号串。2.3 2.3 主要语法成分的定义主要语法成分的定义(续续1)1)2.3.2 2.3.2 句型、句子和语法树句型、句子和语法树若有若有 且且 V VT T*，则，则 是句子是句子；Z Z=+若有若有 ，则，则 是句型；是句型；Z=+2.2.句子句子即：句子是由开始符号加推导出的任一终结符号串。即：句子是由开始符号加推导出的任一终结符号串。1.1.句型句型设有文法设有文法 G(Z)=(VG(Z)=(VN N,V,VT T,Z,P),Z,P)，则：则：3.3.语法树语法树 句型句型(句子句子)产生过程的一种树结构表示；产生过程的一种树结构表示；树根树根-开始符号开始符号；树叶树叶给定的给定的句型句型(句子句子)。A A X X1 1 X X2 2 X Xn n2.3 2.3 主要语法成分的定义主要语法成分的定义(续续2)2)重复步骤重复步骤，直到再没有推导产生式为止。，直到再没有推导产生式为止。置树根为开始符号；置树根为开始符号；【语法树的构造算法语法树的构造算法】：若采用了若采用了推导产生式推导产生式：A-xA-x1 1x x2 2x xn n，则则有有子树：子树：如此构造的语法树，其如此构造的语法树，其全体树叶全体树叶（自左（自左至右）恰好是给定的句型。至右）恰好是给定的句型。E E=T=T=T*F=T*F=F*F=F*F=(E)*F=(E)*F=(E+T)*F=(E+T)*F=(T+T)*F=(T+T)*F=(T/F+T)*F=(T/F+T)*F=(T/F+F)*F =(T/F+F)*F =(T/F+F)*i=(T/F+F)*i 句型、句子和语法树示例：句型、句子和语法树示例：【例例2.102.10】算术表达式算术表达式文法：文法：证明证明 (T/F+F)*i(T/F+F)*i 是一个句型是一个句型(表达式型表达式型)；画出该句型的画出该句型的语法树。语法树。E-T|E+E-T|E+T|E-T|E-T T T-F|T*T-F|T*F|T/F|T/F F F-i|(E )F-i|(E )【证证】即：即：E (T/F+F)*i E (T/F+F)*i =+证闭证闭 句型句型 (T/F+F)*i(T/F+F)*i 的语法树构造：的语法树构造：E ET TT *FT *FF F(E (E )E +TE +TT TT /FT /FF Fi i E-T|E+T|E-T E-T|E+T|E-T T-F|T*T-F|T*F|T/FF|T/F F-i|(E)F-i|(E)【注注】关于语法树：关于语法树：子树子树 ：以任何具有：以任何具有分支的结点为根所形分支的结点为根所形成的树，称为原树的成的树，称为原树的子树。子树。简单子树简单子树 ：仅具有：仅具有单层分支的子树。单层分支的子树。(他他)(哥哥哥哥)(喜欢喜欢)(看看)图图2.2 2.2 他哥哥喜欢看书他哥哥喜欢看书的的语法树语法树(书书)2.3.3 2.3.3 短语、简单短语和句柄短语、简单短语和句柄【例例2.112.11】图图2.22.2为一个为一个中文句型中文句型的语法树：的语法树：短短 语语 -他他哥哥哥哥,喜欢看喜欢看,书书 ，喜欢看书喜欢看书 ，他他哥哥喜欢看书哥哥喜欢看书 简单短语简单短语 -他他哥哥，喜欢看，书哥哥，喜欢看，书句句 柄柄 -他他哥哥（最左边的简单短语哥哥（最左边的简单短语!）句柄句柄 -一个句型的一个句型的最左简单短语最左简单短语称为该句型的称为该句型的句柄句柄。2.3 2.3 主要语法成分的定义主要语法成分的定义(续续3)3)2.3.3 2.3.3 短语、简单短语和句柄短语、简单短语和句柄 设设 文法文法 G(Z),xG(Z),x y y 是一个句型，则是一个句型，则:则则 是句型是句型 x x y y 关于关于A A的短语的短语(A(A是是 的名字的名字)；=+=+1.1.短语短语 若若 Z Z xAyxAy x x y y ,Z Z x A y x A y 任一任一子树子树的的树叶全体树叶全体(具有共同具有共同祖先祖先的叶节点的叶节点符号串符号串)皆为皆为短语短语；=+简单短语简单短语 若若 Z Z xAyxAy=x=x y ,y ,则则 是句型是句型 x x y y 关于关于A A的简单短语的简单短语(A(A是是 的名字的名字)；任一任一简单子树简单子树的的树叶全体树叶全体(具有共同具有共同父亲父亲的叶的叶节点符号串节点符号串)皆为皆为简单短语简单短语；短语、简单短语和句柄短语、简单短语和句柄示例示例【例例2.122.12】图图2.32.3为一个算术表达式为一个算术表达式(型型)的语法树：的语法树：句型：句型：E+F-T/F*iE+F-T/F*i短语短语:E+F-T/F*iE+F-T/F*i，E+FE+F，F F，T/F*iT/F*i，T/FT/F，i i 简单短语简单短语:F:F，T/FT/F，i i 句柄句柄:F:F E E -T E +T T *F F T /F i 图图2.3 E+F-T/F*i 2.3 E+F-T/F*i 的语法树的语法树 一类典型的综合例题：一类典型的综合例题：【例例2.132.13】G(S):S-G(S):S-aAcBeaAcBe ;A-;A-Ab|bAb|b;B-d;B-d 给定符号串给定符号串：aAbcdeaAbcde 证明证明 =aAbcde 是一个句型；是一个句型；画出句型画出句型 的语法树；的语法树；指出指出 中的短语、简单短语和句柄。中的短语、简单短语和句柄。【题解题解】S=S=aAcBeaAcBe=aAbcBeaAbcBe=aAbcdeaAbcde 语法树如右图：语法树如右图：短语、简单短语和句柄短语、简单短语和句柄:S S a A c B e a A c B e A b d A b d 短语短语:aAbcdeaAbcde,AbAb,d,d 简单短语简单短语:AbAb,d,d 句柄：句柄：AbAbG2(S):S-b S|a -G2(S):S-b S|a -直接右递归直接右递归文法。文法。2.4 2.4 两种特性文法两种特性文法1 1 2.4.1 2.4.1 递归文法递归文法 设有文法：设有文法：G(Z)=(VG(Z)=(VN N,V,VT T,Z,P),Z,P)【定义定义】设设 AVAVN N，x,y(Vx,y(VN N+V+VT T)*，则则;若若 A A xAyxAy，：，：称文法具有称文法具有递归性递归性;=+特别特别：若若 A-A-A A ，称文法具有称文法具有直接左递归性直接左递归性；A A-A A，称文法具有称文法具有直接右递归性直接右递归性。递归文法是定义无限语言的工具（递归文法递归文法是定义无限语言的工具（递归文法定义的语言有无限个句子）！定义的语言有无限个句子）！如：如：G1(S):S-S b|a -G1(S):S-S b|a -直接左递归直接左递归文法；文法；递归文法示例递归文法示例【例例2.152.15】G(Z)G(Z)：Z-Z-aAbBaAbB|cZcZ A-A-bBcbBc|B-B-BbAcBbAc|a|a Z-Z-cZcZ 直接右递归性；直接右递归性；B-B-BbAcBbAc 直接左递归性；直接左递归性；A=A=bBcbBc=bBbAccbBbAcc 即即 A=+A=+A A 具有递归性具有递归性 (且且 又称为又称为A A具有自嵌套性具有自嵌套性)可以统称文法可以统称文法G(Z)G(Z)具有递归性。具有递归性。2.4 2.4 两种特性文法两种特性文法2 22.4.2 2.4.2 二义性文法二义性文法【定义定义】若文法中存在这样的句型，它具有若文法中存在这样的句型，它具有两棵两棵不同的语法树不同的语法树，则称该文法是，则称该文法是二义性二义性文法。文法。【例例2.142.14】算术表达式的另一种文法：算术表达式的另一种文法：句型句型 i+i*i i+i*i 有两棵有两棵不同的语法树不同的语法树(右图右图)：G(E)是二义性文法。是二义性文法。G G(E)(E)：E-E+E|E-E|E*E|E/E|(E)|i ;E-E+E|E-E|E*E|E/E|(E)|i ;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 二义性文法二义性文法会引起歧义，会引起歧义，应尽量避免之！应尽量避免之！2.5.1 2.5.1 文法的等价性文法的等价性 2.5 2.5 文法的等价变换文法的等价变换即：即：文法的等价性是指他们所定义的语言是一样的。文法的等价性是指他们所定义的语言是一样的。【定义定义】设设G G1 1、G G2 2是两个文法，若是两个文法，若L(GL(G1 1)=L(G)=L(G2 2)，则称则称G G1 1与与G G2 2等价，记作等价，记作G G1 1GG2 2。【例例2.152.15】：G G1 1：S-S-aS|aaS|a；G G2 2：S-Sa|a S-Sa|a L(G L(G1 1)=a,)=a,aaaa,aaaaaa,=a,=an n|n1|n1 L(G L(G2 2)=a,)=a,aaaa,aaaaaa,=a,=an n|n1|n1 L(G L(G1 1)=L(G)=L(G2 2)即即 G G1 1GG2 2 【注注】一个语言，其描述文法并不唯一。一个语言，其描述文法并不唯一。2.5.2 2.5.2 文法变换方法文法变换方法 在实际工作中，人们总是希望定义一种语言的在实际工作中，人们总是希望定义一种语言的文法尽可能地简单。另外，某些常用的语法分析技文法尽可能地简单。另外，某些常用的语法分析技术也会对文法提出一定的要求或限制；为了适应上术也会对文法提出一定的要求或限制；为了适应上述要求，有时需要对文法进行必要的改写。当然述要求，有时需要对文法进行必要的改写。当然改改写后的文法要与原文法等价写后的文法要与原文法等价通常称为通常称为文法变换文法变换。这里重点介绍三类变换：这里重点介绍三类变换：常用的三种文法变换方法：常用的三种文法变换方法：删除删除产生式；产生式；必选项法；必选项法；可选项法；可选项法；重复可选项法。重复可选项法。删除无用的产生式（文法的化简）；删除无用的产生式（文法的化简）；文法化简是指消除如下文法化简是指消除如下无用产生式无用产生式：删除删除 A-A A-A 形式的产生式形式的产生式(自定己自定己)；删除不能从其推导出终结符串的产生式删除不能从其推导出终结符串的产生式(不终结不终结)；删除在推导中永不使用的产生式删除在推导中永不使用的产生式(不可用不可用)。2.5.2 2.5.2 文法变换方法文法变换方法1 1.文法的化简文法的化简 第第步算法步算法(删除删除不终结不终结产生式产生式)：构造能构造能推导出终结符串的非终结符集推导出终结符串的非终结符集 V VVTVT:若有若有 A-A-且且 V VT T*;则则令令 AVAVVTVT ；若有若有 B-B-且且 (V(VT T+V+VVTVT)*;则令则令 BVBVVT VT;重复步骤重复步骤，直到，直到V VVTVT不再扩大为止。不再扩大为止。删除不在删除不在V VVTVT中的所有非终结符中的所有非终结符(连同其产生式连同其产生式)。2.5.2 2.5.2 文法变换方法文法变换方法1(1(续续1)1)第第步算法步算法(删除删除不可用不可用产生式产生式)：构造可用构造可用的非终结符集的非终结符集 V VUSUS:首先令首先令 ZVZVUS US;(Z;(Z 为文法为文法开始符号开始符号)=+删除不在删除不在V VUSUS中的所有非终结符中的所有非终结符(连同其产生式连同其产生式)。【例例2.162.16】化简下述文法：化简下述文法：G(S):S-Be|G(S):S-Be|EcEc A-A-AeAe|e|A|e|A B-C e|B-C e|AfAfC-C-CfCf;D-f;G-b;D-f;G-b 若有若有 Z A Z A，则则 令令 AVAVUS US;重复步骤重复步骤，直到，直到V VUSUS不再扩大为止。不再扩大为止。=+文法化简示例：文法化简示例：化简步骤：化简步骤：G(S):S-Be|G(S):S-Be|EcEc A-A-AeAe|e|A|e|A B-C e|B-C e|AfAfC-C-CfCf;D-f;G-b;D-f;G-b 删除删除 A-A;A-A;删除删除不终结不终结产生式产生式:V VVTVT=A,D,G,B,S;=A,D,G,B,S;应删除应删除 C,E(C,E(连同其产生式连同其产生式)得：得：G(S):S-Be;A-G(S):S-Be;A-AeAe|e;B-|e;B-AfAf;D-f;G-b;D-f;G-b;删除删除不可用不可用产生式产生式:V VUSUS=S,B,A;=S,B,A;应删除应删除 D,G(D,G(连同其产生式连同其产生式)整理后得：整理后得：G(S):G(S):A-A-AeAe|e|eB-B-AfAfS-BeS-Be2.5.2 2.5.2 文法变换方法文法变换方法2 2 删除删除 产生式产生式【算法算法】首先构造可以推出空串的非终结符集：首先构造可以推出空串的非终结符集：V V 若有若有 A-A-;则则 令令 AAV V ;若有若有 B-AB-A1 1 AAn n 且全部且全部 A Ai iV V ;则令则令 B BV V ;重复步骤重复步骤，直到，直到V V 不再扩大为止。不再扩大为止。删除删除 G(Z)G(Z)中的中的 A-A-形式的产生式；形式的产生式；假定假定 文法文法 G(Z);G(Z);L(G)L(G)依次改写依次改写G(Z)G(Z)中的产生式中的产生式 A-XA-X1 1 X X2 2 X Xn n :若有若有 X Xi i V V 则用则用 (X(Xi i|)替换之替换之(一个分裂为两个一个分裂为两个)；若有若有 j 个个 X Xi i V V ，则一个产生式将分裂为则一个产生式将分裂为2 2j j个个!【例例2.172.17】G(S):S-G(S):S-aAbc|bSaAbc|bS A-A-dABedABe|;B-A|b;B-A|b 删除删除 产生式示例：产生式示例：求解求解 V V =A,B=A,B 删除删除 产生式产生式 得：得：S-S-aAbc|bSaAbc|bS ；A-A-dABedABe ；B-A|bB-A|b 改写改写 含有含有 V V 中元素的产生式：中元素的产生式：S-S-a(A|a(A|)bcbc S-S-aAbc|abcaAbc|abc A-d(A|A-d(A|)(B|)(B|)e A-)e A-dABe|dBe|dAe|dedABe|dBe|dAe|de B-(A|B-(A|)B-A)B-A含有含有V V 元素元素的产生式的产生式 综合综合 G(S)：S-S-aAbc|abc|bSaAbc|abc|bSA-A-dABe|dBe|dAe|dedABe|dBe|dAe|deB-A|bB-A|b令令 （|）=或者或者 可变换成可变换成:A-a:A-a(|)2.5.2 2.5.2 文法变换方法文法变换方法3 3 必选项法（园括号法）必选项法（园括号法）常用的三种文法变换方法：常用的三种文法变换方法：基本思想基本思想：扩展文法，引进新的：扩展文法，引进新的描述符号描述符号：（）（）圆括号；圆括号；方括号；方括号；花括号。花括号。必选其中之一！必选其中之一！例如：有例如：有 A-aA-a|a|a 也可：也可：A-A-aAaA ；A-A-|【注注】此法有称此法有称提公因子法，提公因子法，利用此法可以使文法：利用此法可以使文法：具有相同左部的各产生式首符号不同！具有相同左部的各产生式首符号不同！也可：也可：S-S-S;S-S;S-|令令 =或者或者 2.5.2 2.5.2 文法变换方法文法变换方法3(3(续续1)1)可选项法（方括号法）可选项法（方括号法）常用的三种文法变换方法：常用的三种文法变换方法：例如：例如：S S-|可选也可不选！可选也可不选！例如例如 条件语句文法：条件语句文法：S-if(B)S S-if(B)S 可变换成：可变换成：S-S-S-if(B)S else SS-if(B)S else S可变换成：可变换成：S-if(B)S S-if(B)S else Selse SS(语句语句)，B(布布尔表达式尔表达式)或：或：S-if(B)S S;S-else S-if(B)S S;S-else S|S|2.5.2 2.5.2 文法变换方法文法变换方法3(3(续续2)2)重复可选项法（花括号法）重复可选项法（花括号法）常用的三种文法变换方法：常用的三种文法变换方法：例如：例如：A-A|A-A|令令 =或或 或或 或或 可变换为：可变换为：A-A-通过递推方法，可得：通过递推方法，可得：A=A=A=A=A=A=A=A=*有有 A-A-；或或 A A A;A;A-AA-A|；也可：也可：A A A ;A-A|A ;A-A|验证：验证：【注注】此方法常用来消除文法的此方法常用来消除文法的直接左递归直接左递归！产生式形式为：产生式形式为：xAyxAy-x-x y y 产生式形式为：产生式形式为：A-A-aBaB,A-a,A-,A-a,A-产生式形式为：产生式形式为：A-A-2.6 2.6 形式语言的分类形式语言的分类 chomskychomsky 把形式语言分为把形式语言分为四类四类，分别由四类文法，分别由四类文法定义；四类文法的区别在于定义；四类文法的区别在于产生式的形式不同产生式的形式不同：2 2 型语言型语言 由由 2 2型文法型文法定义定义 1 1 型语言型语言 由由 1 1型文法型文法定义定义 0 0 型语言型语言 由由 0 0型文法型文法定义定义 产生式形式为：产生式形式为：-3 3 型语言型语言 由由 3 3型文法型文法定义定义又称又称 无限制文法无限制文法！又称又称 上下文有关文法上下文有关文法！又称又称 上下文无关文法上下文无关文法！又称又称 正规文法正规文法！【注注】四类语言为四类语言为 包含关系，且有包含关系，且有 L0 L1 L2 L3；编译处理中，主要应用编译处理中，主要应用后两种文法后两种文法！谢谢收看！谢谢收看！再见