编译原理第二章形式语言基础(1)

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,编译程序的设计原理与实现,如何让计算机,认识、理解 和 执行,高级程序设计语言？,第 2 章 形式语言基础,计算机处理语言，首先应考虑语言的形式化、规,范化，使其具有可计算性和可操作性；这就是形式语,言理论研究的问题。,形式语言诞生于1956年，由chomsky创立。通常，,语言研究至少涉及三个方面：,语法,、,语义,和,语用,；,这里仅侧重于,语法的研究,。,形式语言的,基本观点,是：,语言是符号串之集合！,形式语言理论研究的,基本问题,是：,研究符号串集合的表示方法、结构特性,以及运算规律。,【前 言】,【内容提要】,第 2 章 形式语言基础,2.1,形式语言是,符号串集合,2.2,形式语言是由,文法定义,的,2.3,主要,语法成分,的定义,2.4,两类,特性文法,2.5,文法变换,方法,2.6 关于,形式语言的分类,问题,字母表,-,元素,(,符号,),的非空有限集合；,符,号串,-,符号的有限序列；,符号串集合,-,有限个或者无限个符号串组成的集合；,规 则,-,以,某种形式表达的在一定范围内共同遵守的章程和制度；这里，指符号串的组成规则。,2.1 形式语言是符号串集合,【形式语言】,是,字母表,上的符号，按一定的,规则,组成的所有,符号串集合,；其中的每个符号串,称为,句子,。,【名词解释】：,三要素！,【例2.1】L,1,=00,01,10,11;,字母表,1,=0,1,句子有：00,01,10,11,【注】b,0,=,（空符号串）,b,1,=b,b,2,=bb,b,3,=bbb,L,1,为有限语言;L,2,为无限语言。,形式语言概念示例：,【例2.2】L,2,=ab,m,c,b,n,|m0,n0,字母表,2,=a,b,c,句型,1:,ab,m,c,有句子：,abc,abbc,abbbc,句型,2:,b,n,;,有句子：,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.1.1 符号串(集合)的运算(续1),【例】：,ab|cd=ab（,或者,cd）,abc.de=abcde,(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组成的,任意符号串！,（包括空串）,1.,乘积：,AB=xy|x,A,且,yB,2.1.1 符号串(集合)的运算(续2),4.,闭包：,A,的正闭包,：A,+,=A,1,A,2,A,n,A,的星闭包,：A,*,=A,0,A,1,A,2,A,n,设,A,和,B,为两个符号串集合，则：,2.,和：,AB=A+B=x|x,A 或 xB,3.,方幂：,A,n,=AAA=AA,n-1,=A,n-1,A,n,个,A,0,=,;,A,1,=A,;,A,2,=AA;A,3,=AAA;,.符号串集合的运算,符号串集合运算示例：,【例2.3】设 A=a,b,B=c,d,则 A+B=a,b,c,d,则 AB=xy|x,A,yB=,ac,ad,bc,bd,【例2.4】设 A=a,则 A,*,=A,0,A,1,A,2,A,n,=,+a+aa+aaa+,=,a,aa,aaa,=a,n,|n0,【例2.5】设 A=a，b，A,*,=?,A,*,=A,0,A,1,A,2,A,n,A,0,=,;,A,1,=A=a，b;,A,2,=A.A=a，b.a，b=aa,ab,ba,bb;,A,3,=A.A,2,=a，b.aa,ab,ba,bb,=aaa,aab,aba,abb,baa,bab,bba,bbb;,A,*,=x|x=(a|b),n,，n0,符号串集合运算示例,(,续,),：,推论,：若 A为任一字母表,则,A,*,就是该字母,表上,的所有符号串(包括空串)的集合。,S,A 定义的对象(S,句子,最大的定义对象，又,称为开始符号;A为句型aAc的,短语,），,a,b,c-,为,字母表中的符号;-空符号串。,-,|-为,描述符号,(-定义为;|或者是）,2.1.2 符号串集合的文法描述,【例2.5】,L=ab,n,c|n0，,字母表,：=a,b,c；,展开,：L=ac,abc,abbc,abbbc,右图给出的表示,S-,aAc,A-bA|,长久以来，探讨符号串集合(即形式语言)的各种描述方法，一直是语言计算机处理的重要任务之一。,方法-,文法规则,；,其中：,从,开始符号,出发，对符号串中的,定义对象,，采用,推导,的方法（,用其规则右部替换左部,）产生新的符号串，如此进行，直到新符号串中不再出现定义的对象为止，则最终的符号串就是一个,句子,。,S-,aAc,A-bA|,规则,应用,说明示例：,【,句子产生过程,】(,=,推导算符,):,怎样利用上述,文法规则,表示语言L?,S,=,aAc,=ac,=ac,S,=aAc,=abAc,=abc,=abc,S,=aAc,=abAc,=abbAc,=abbc,一个句子!,又一个句子!,S ab,n,c,n0,=,+,再一个句子!,【定义】文法(grammar)是规则的有限集,其中的上下文无关文法可定义为四元组：,G(Z)=(V,N,V,T,Z,P),V,N,:非终结符集（定义的对象集，如：语法成分等)；,V,T,:终结符集（字母表）；,Z:开始符号（研究范畴中，最大的定义对象）；,P:规则集（又称产生式集）；,A-,或者 A-,|,其中,描述符号：-(定义为)，|(或者是),文法符号：Z,AV,N,，,(V,N,+V,T,),*,2.2 形式语言是由文法定义的,每个元素,每个规则,2.2.1 什麽是文法？,2.2 形式语言是由文法定义的（续3）,【注意】提供了规则集，就相当给出了一个文法：,S-,aAc,A-bA|,G(S):,2.2.2 文法是怎样定义语言的？,则 L(G)=x|Z x,xV,T,*,即：一个文法所定义的,语言,，就是由该文法,开始,设 有文法 G(Z),L(G)为G所定义的语言；,V,T,=a,b,c;,Z,=S;,P,:,V,N,=S,A；,G(Z)=(V,N,V,T,Z,P),利用=进行连续推导之意！,符号推导出,的所有,仅含终结符,的,符号串,之集合,。,其中的每个符号串皆称为,句子,。,=,+,2.1,【例2.6】,标识符,的文法,【,标识符,】指字母开头的字母、数字序列。,令 G(Z)=(V,N,V,T,Z,P),则 V,N,=I(标识符),A(标识符尾)；,V,T,=(字母),d,(数字）,；,Z =I;,P:,I,-A|,A-A|d A|,同理，,【,无符号整数,】文法 可写成：,G(N):,N-d N|d,其,四元组,也可写成：G(N)=(N,d,N,P ),得：,I,=,(,|d,),n,n0,令：,I,=A|,A=A|d A|,标识符文法,所定义的语言求解：,上面构造的,标识符文法,属于,正规文法,(定义在后)类，,正确性检验较容易；下面给出一个,算法,：,I,-A|,A-A|d A|,求解 I 值步骤：,先求解,A:A=(,|d,)A,A=(,|d,),2,A,A=(,|d,),n,A,代入 A=,得：A=,(,|d,),n,n0,I=,A|,代入,A=,(,|d,),n,n0,正规方程式,标识符：字母开头的字母、数字序列；,则 V,N,=E(算术表达式),T(项)，F(因式)；,V,T,=i(变量或常数),+,-,*,/,(,）,；,Z =E;,P:,【例2.7】简单算术表达式文法,【注】此文法定义了算术表达式的层次嵌套结,构:,E-T|E+,T|E-,T,T-F|T*,F|T/,F,F-i|(E ),令 G(Z)=(V,N,V,T,Z,P),(表达式),表达式,项,因式,算术表达式文法应用示例：,根据,语言定义式,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-i),L(G)=x|Z x,xV,T,*,=,+,合法的算术表达式是指：,练习题,【习题2.1】解释下列词语：,形式语言；,文法；,文法所定义的语言。,【习题2.2】试构造下述语言,L,的文法：,L,=a,m,b,n,|m0,n1;,【习题2.3】试求下述文法G(Z)所定义的语言：,G(Z):Z-b|bB,B-bZ,【习题2.4】P36_8,谢谢收看！,再见,