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

,编译程序的设计原理与实现,如何让计算机认识、理解和执行高级程序设计语言？,第2章形式语言基础,计算机处理语言，首先应考虑语言的形式化、规范化，使其具有可计算性和可操作性；这就是形式语言理论研究的问题。形式语言诞生于1956年，由Chomsky创立。通常，语言研究至少涉及三个方面：语法、语义和语用；,形式语言的基本观点是：语言是符号串之集合！,形式语言理论研究的基本问题是：,研究符号串集合的表示方法、结构特性,以及运算规律。,因此：,【内容提要】,2.1形式语言是符号串集合2.2形式语言是由文法定义的2.3各种语法成分的定义2.4两类特性文法2.5文法变换方法2.6形式语言的分类,第2章形式语言基础,字母表-元素(符号)的非空有限集合；符号串-符号的有限序列；符号串集合-有限个或者无限个符号串组成的集合；规则-以某种形式表达的在一定范围内共同遵守的章程和制度；这里，指符号串的组成规则。,2.1形式语言是符号串集合,【形式语言】是字母表上的符号按一定的规则组成的所有符号串集合；其中的每个符号串称为一个句子。,【名词解释】：,三要素！,【例2.1】L1=00,01,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.连接：.=如：a.b=ab,2.1.1符号串(集合)的运算,3.方幂：n=n-1=n-1,4.闭包：,n个,.符号串的运算,设,为两个符号串，则：,的正闭包：+=1|2|n|,的星闭包：*=0|1|2|n|,0=(空符号串)什么符号也没有的符号串！,1=；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,即：(a|b)*=(a|b)n,n0,同理：(a|b)+=(a|b)n,n0,符号串运算示例,泛指：由a，b组成的任意符号串！（包括空串）,(3)ab|cd=ab或者cd,1.乘积：AB=xy|xA且yB,4.闭包：A的正闭包：A+=A1A2AnA的星闭包：A*=A0A1A2An,设A和B为两个符号串集合，则：,2.和：AB=A+B=x|xA或xB,3.方幂：An=AAA=AAn-1=An-1A,n个,A0=;,A1=A;A2=AA;A3=AAA;,.符号串集合的运算,2.1.1符号串(集合)的运算,符号串集合运算示例,【例2.4】设A=a,b,B=c,d则A+B=a,b,c,d则AB=xy|xA,yB=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,符号串集合运算示例(续)：,推论：若A为任一字母表，则A*就是该字母表上的所有符号串(包括空串)的集合。,2.2形式语言是由文法定义的,形式语言是符号串的集合，对形式语言的描述有两种方式：,(1)枚举方式：语言为有穷集合时设有字母表A=a,b,c,有L1=a,aa,ab,ac,L2=c,cc(2)使用文法：语言为无穷集合时，无法枚举设有字母表B=0,1,B+=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形式语言是由文法定义的,每个元素,2.2.1什么是文法？,Z-或者A-|注：此文法实际称为上下文无关文法描述符号：-(定义为/生成)，|(或者是)文法符号：Z,AVN，,(VN+VT)*,每个规则,【注意】提供了规则集，就相当给出了一个文法：,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,可以用右图给出的,S-aAc,A-bA|,文法规则来表示：,2.2.2文法是怎样定义语言的？,则L(G)=x|Zx,xVT*,即：一个文法所定义的语言，就是由该文法开始,设有文法G(Z)，L(G)为G所定义的语言；,利用推导算符=进行连续推导,符号推导出的所有仅含终结符的所有符号串之集合。,其中的每个符号串皆称为句子。,2.1,使用文法的规则进行,形式语言是字母表上的符号按一定的规则组成的所有符号串集合。,从开始符号出发，对符号串中的定义对象，采用推导的方法（用其规则右部替换左部）产生新的符号串，如此进行，直到新符号串中不再出现定义的对象为止，则最终的符号串就是一个句子。,S-aAcA-bA|,利用文法规则表示语言,【句子产生过程】(=推导算符),S,=aAc,=ac,=ac,S,=aAc,=abAc,=abc,=abc,S,=aAc,=bAc,=abbAc,=abbc,一个句子!,又一个句子!,Sabnc,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,其四元组也可写成：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,n0,I=A|代入A=(|d)n,n0,正规方程式,标识符：字母开头的字母、数字序列,求解文法所定义的语言(2),则L(G)的求解过程代入法：,【例2.9】G(Z):,所以：L(G)=abnc|n0,A=bA=bbA=bn,n0,Z=aAcabnc,n0,即：Abn,，n0,即：,Zabnc，n0,则VN=E(算术表达式),T(项),F(因式)；VT=i(变量或常数),+,-,*,/,(,)；Z=E;P:,【例2.10】简单算术表达式文法,【注】此文法定义了算术表达式的层次嵌套结构:,令G(Z)=(VN,VT,Z,P),(表达式),表达式,项,因式,文法E-E+E|EE|E*E|E/E|i|(E)?,算术表达式文法应用示例：,根据语言定义式2.1，,证明i*(i+i-i),是文法G(E)的一个句子,(即合法的算术表达式):,E,=T,=T*F,=T*(E),=T*(E-T),=T*(E+T-T),=F*(E+T-T),=i*(E+T-T),=,观察推导过程，可以看到：一旦产生式选择错了，会导致失败！,=i*(i+i-i),合法的算术表达式是指：,文法有两种基本运算：推导和归约,星推导():,2.3各种语法成分的定义,1.直接推导(=):xAy=xy即：指用产生式的右部符号串替换左部非终结符。,加推导算符,加推导():,设x,y(VN+VT)*，,A-P,（当且仅当=1=2=）即：指一步或一步以上的直接推导运算。,（当且仅当=或=1=2=)即：指零步或零步以上的直接推导运算。,直接推导算符,星推导算符,2.3.1文法的运算,2.直接归约():xyxAy,星归约():,即：直接归约是直接推导的逆运算，用产生式的左部非终结符替换右部符号串。,直接归约算符,加归约算符,星归约算符,加归约():,2.3.1文法的运算,规范推导和规范归约,实用中最常见的两种运算：最左推导()每次推导皆最左非终结符优先；最左归约()每次归约皆最左可归约串优先。,最右推导也称为规范推导最左归约也称为规范归约,同一个句子可以通过不同的推导序列推导出来,通常只考虑两种特殊推导，即最左推导和最右推导,N1=N=ND=N2=D2=12,12D2N2NDNN1,N1-NN-ND|DD-0|1|2,最左归约是最右推导的逆过程！,i+i*i,给定一个符号串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*i,F+i*i,T+i*i,E+i*i,E+F*i,E+T*i,E+T*F,E+T,E,1.最左推导(从开始符号出发)过程：,最左非终结符,最左可归约串,2.3.2句型、句子和语法树,2.句子,1.句型,设有文法G(Z)=(VN,VT,Z,P)，则：,3.语法树,重复步骤，直到推导过程结束为止。,置树根为开始符号；,【语法树的构造算法】,若推导采用了产生式：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是一个句型(表达式型)；(2)画出该句型的语法树。,【证】,即：E(T/F+F)*i,句型(T/F+F)*i的语法树构造：,E,T,T*F,F,(E),E+T,T,T/F,F,i,【注】关于语法树：子树：由某一结点连同所有分支组成的部分。简单子树：仅具有单层分支的子树。,3.句柄-一个句型的最左简单短语称为该句型的句柄。,2.3.3短语、简单短语和句柄,设文法G(Z),xy是一个句型，则:,则是句型xy关于A的短语(A是的名字)；,ZxAy,2.简单短语若ZxAy=xy,则是句型xy关于A的简单短语(A是的名字)；,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,2.3.3短语、简单短语和句柄,一类典型的综合例题：,【例2.15】G(S):S-aAcBe;A-Ab|b;B-d,给定符号串：aAbcde,证明=aAbcde是一个句型；,画出句型的语法树；,指出中的短语、简单短语和句柄。,【题解】,S=aAcBe=aAbcBe=aAbcde,语法树如右图：,短语、简单短语和句柄:,短语:aAbcde,Ab,d,简单短语:Ab,d,句柄：Ab,G2(S):S-bS|a-直接右递归文法。,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)：Z-aAbB|cZA-bBc|B-BbAc|aZ-cZ直接右递归性；B-BbAc直接左递归性；A=bBc=bBbAcc即AA具有递归性(且又称为A具有自嵌套性)可以统称文法G(Z)具有递归性。,2.4.2二义性文法,【定义】若文法中存在这样的句型，它具有两棵不同的语法树，则称该文法是二义性文法。,【例2.17】算术表达式的另一种文法：,句型i+i*i有两棵不同的语法树(右图)：,G(E)是二义性文法。,G(E)：E-E+E|E*E|(E)|i;,i(变量或常数),二义性文法会引起歧义，应尽量避免之！,文法二义性的消除,【方法1】不改变文法的原有规则,加进一些非形式的规定。,【方法2】构造一个等价的无二义性文法，将排除二义性的规则合并到文法中,加进运算符的优先顺序和结合规则对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(G1)=L(G2)即G1G2【结论】一个语言，其描述文法并不唯一。,2.5.2文法变换方法,在实际工作中，人们总是希望定义一种语言的文法尽可能地简单。另外，某些常用的语法分析技术也会对文法提出一定的要求或限制。因此，有时需要对文法进行必要的改写。改写后的文法要与原文法等价通常称为文法变换。这里重点介绍三类变换：,BNF（巴科斯范式）表示法：,删除产生式；,删除无用的产生式（文法的化简）；,文法的化简是指消除如下无用产生式：1.A-A形式的产生式(自定己)；2.不能从其推导出终结符号串的产生式(不终结)；3.在推导中永不使用的产生式(不可用)。,文法的化简,删除不终结产生式算法：,(1)构造能推导出终结符号串的非终结符集VVT:,若有A-且VT*;则令AVVT；若有B-且(VT+VVT)*;则令BVVT;重复步骤，直到VVT不再扩大为止。,(2)删除不在VVT中的所有非终结符(连同其产生式)。,删除不可用产生式算法：,(1)构造可用的非终结符集VUS:,首先令ZVUS;(Z为文法开始符号),(2)删除不在VUS中的所有非终结符(连同其产生式)。,【例2.19】化简下述文法：,若有ZA，则令AVUS;,重复步骤，直到VUS不再扩大为止。,文法的化简,文法化简示例,化简步骤：,删除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):,删除产生式,【算法】,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个!,删除产生式示例：,(1)求解V=A,B,(2)删除产生式得：,S-aAbc|bS；A-dABe；B-A|b,(3)改写右部含有V中元素的产生式：,S-a(A|)bcS-aAbc|abc,A-d(A|)(B|)eA-dABe|dBe|dAe|de,B-(A|)B-A,含有V元素的产生式,综合G(S)：,【例2.20】G(S):S-aAbc|bSA-dABe|;B-A|b,令(|)=或者,1.必选项法（圆括号法）,BNF（巴科斯范式）表示法,必选其中之一！,例如：有A-a|a,也可写成：A-aA；A-|,基本思想：扩展文法，引进新的描述符号：()圆括号；方括号；花括号,可变换成:A-a(|),也可写成：S-S;S-|,令=或者,2.可选项法（方括号法）,例如：S-|,可选也可不选！,例如条件语句文法：,S-if(B)S,可变换成：S-,S-if(B)SelseS,可变换成：,S-if(B)SelseS,S(语句)，B(布尔表达式),或：,S-if(B)SS;S-elseS|,BNF（巴科斯范式）表示法,3.重复可选项法（花括号法）,例如：A-A|,令=或或或,可变换为：A-,通过递推方法，可得：A=A=A=A=*有A-或AA;A-A|,也可写成：AA;A-A|,验证：,【注】此方法常用来消除文法的直接左递归！,BNF（巴科斯范式）表示法,产生式形式为：A-u,2.6形式语言的分类,Chomsky把形式语言分为四类，分别由四类文法定义；四类文法的区别在于产生式的形式不同：,(2)1型语言由1型文法定义,(1)0型语言由0型文法定义,又称无限制文法！,产生式形式为：-,(VNVT)*且至少有一个非终结符(VNVT)*,又称上下文有关文法！,AVN,(VNVT)*,u(VNVT)+A只有在和这样的上下文环境中才能换成u,2.6形式语言的分类,产生式形式为：A-aB或A-a,产生式形式为：A-,(3)2型语言由2型文法定义,(4)3型语言由3型文法定义,又称上下文无关文法！,编译处理中，主要应用后两种文法！,【注】四类语言为包含关系，且有L0L1L2L3；,AVN,(VNVT)*将A替换成时，与A的上下文无关,又称正规文法！,A,BVN,aVT*,产生式形式为：A-Ba或A-a,右线性文法,左线性文法,主要内容总结,文法是规则集合，四元组：G(Z)=(VN,VT,Z,P)文法所定义的语言：,文法应用示例：简单语言的文法构造：无符号整数文法：G(N):N-dN|d,求解文法所定义的语言(或句子)方法：,形式语言是符号串集合且由文法定义！,正规方程组迭代求语言（如标识符文法）,直接由定义求解句子(如算术表达式文法)。,标识符文法：G(I):,d(数字),(字母),主要内容总结,文法的运算：推导和归约(二者互为逆运算),推导：,归约：,文法的运算与主要语法成分的定义！,主要语法成分的定义,句型，句子，语法树，,短语，简单短语，句柄,从语法树上看句型(句子)、短语、简单短语和句柄：,直接推导(=),加推导(),最左推导();,直接归约(),加归约(),最左归约();,语法树的树叶全体-句型(句子)；,语法树的子树树叶全体短语(简单短语)；,语法树的最左简单子树树叶全体句柄！,课后习题,2.2设有文法GN:GN定义的语言是什么?给出句子0123和268的最左推导和最右推导,2.4写一个文法，使其语言是奇数的集合，且每个奇数不以0开头。,2.7下面文法生成的语言是什么？,S-ABA-aA|B-bc|bBc,G1：,S-aA|aA-aS,G2：,N-D|NDD-0|1|2|3|4|5|6|7|8|9,2.11已知文法GS:请找出符号串(a)和(A(SaA)(b)的短语、简单短语和句柄,S-(AS)|(b)A-(SaA)|(a),