第二章形式语言与自动机理论基础(形式语言).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 形式语言与自动机理论基础,2.1,预备知识,2.2,文法的讨论,2.3,文法和语言的定义,2.4,分析树和二义性,2.5,形式语言,概观,2.1,预备知识,2.1.1,字母表,2.1.2,符号串,一、符号串的定义,二、术语,三、符号串的运算,四、符号串集合的运算,字母表是,符号,的,非空有穷,集合；,例：,=,a，b，c,任何程序语言都有自己的字母表。,2.1.1,字母表,1.计算机语言：由符号,“,0,”,和,“,1,”,组成的字 母表:=0，1,2.,Pascal,语言字母表：=,A,Z,a,z,0,9,+,-,*,/,:,”,;,，,.,，,(,),3.,C,语言字母表：,=,A,Z,a,z,0,9,+,-,*,/,_,&,:,”,;,，,.,，?,(,),空格,!,#,%,一.符号串的定义,由,字母表,中的符号所组成的的任何,有穷序列,被称之为该字母表上的符号串,。,空符号串,：,无任何符号的符号串，记作,2.1.2,符号串,符号串的形式定义,：,(1)字母表上字符是上的符号串。,(2)若,x,是上的符号串，而,a,是的元素,则,xa,是上的符号串。,(3),y,是上的符号串,当且仅当它由(1)和(2)导出。,二,术语,（设,s,是,符号串,banana,）,前 缀,：移走,s,的尾部的零个或多于零个符号所得符号串,b,ba,ban,bana,banan,banana,后 缀,：删去,s,的头部的零个或多于零个符号所得符号串,banana,anana,nana,ana,na,a,子 串,:从,s,中删去一个前缀和一个后缀所得符号串,banana,anana,banan,真前缀、真后缀和真子串,：,不是,s,和,的前缀、后缀和子串,子序列,:从,s,中删去零个或多于零个符号(不要求是连续）而得到的符号串。如,baaa,长 度,：是符号串中符号的个数,。,例如|,aab,|=3,|=0,语 言,：,确定字母表上字符串的任何集合,例如,：,不含任何元素的空集合,，,即,只含有空符号串的集合,符合,Pascal,语法的程序,组成的集合,（,Pascal,语言）,符合英文语法的句子,组成的集合,1.,连接,：设,x,和,y,是符号串，它们的连接,xy,是把符号串,y,写在符号串,x,的之后得到的符号串。例如,x=,ba,y,=,nana,xy,=banana.,x=x,=,ba,2.,方幂,：x,0,=,x,1,=x x,2,=xx,x,n,=x,n-1,x,例如,x=,ba,x,1,=,ba,x,2,=,baba,x,3,=,bababa,三.,符号串的运算,（语言,L,和,M,）,1.,合并,：,LMs|s,L,or,s,M,属于,L,或属于,M,的符号串,s,所组成的集合,2.,连接,：,LMst|s,L,and,t,M,s,属于,L,和,t,属于,M,的,所有符号串,st,组成的集合,L,=,L,=,L,3.,方幂,：,L,0,=L,1,L,L,n,L,（n-1）,L,(,n0),四.语言(符号串集合）的运算,4.,语言,L,的,正闭包,，记作,L,+,L,+,L,1,L,2,L,3,L,4,5.,语言,L,的,Kleene,闭包(自反闭包),，记作,L,*,L,*,L,0,L,L,0,L,1,L,2,L,3,例：,A=,x,y,A,？,A,*,？,x,y,xx,xy,yx,yy,A,1,A,2,x,y,xx,xy,yx,yy,A,0,A,1,A,2,例:（语言,L,=,A,Z,a,z,D=0,9）,1,LD,=,A,Z,a,z,0,9,2,LD,所有一字母后跟一数字组成的符号串构成的集合,3,L,4,所有的四个字母的符号串构成的集合,4,L（LD),*,所有字母打头的字母和数字符号串构成的集合,5,D,+,所有长度大于等于1的数字串构成的集合,2.2 文法的讨论,例：有一英文句子：“,The grey wolf will eat the goat.”。,这是一个在语法、语义上都正确的句子。如何用语法单位如,、等推导出该句子？,The,grey,wolf,will,eat,the,goat,BNF,范式表示法：,如果用符号“,”(或“:=”)表示“定义为”，用符号“|”表示“或”，表示语法成分,句子 主语,谓语,（1）,主语 冠词,形容词,名词 （2）,冠词,the,（3）,形容词,grey,（4）,谓语,动词 直接宾语 （5）,动词 助动词 动词原,形,（6）,助动词,will,（7）,动词原,形,eat,（8）,直接宾语,冠词 名词 （9）,名词,wolf,（10）,名词,goat,（11）,名词,wolf|goat,由规则推导句子,：有了一组规则之后，可以按照一定的方式,用它们去,推导或产生句子,。,推导方法：从一个要识别的符号开始推导，即用相应规则的,右部,来替代规则的,左部,，每次仅用一条规则去进行推导。,=,=,冠词,形容词,名词,这种推导一直进行下去，直到所有带的符号都由终结符号替代为止。,1、,终结符号集,V,T,=,the,gray,wolf,will,eat,goat,2、,非终结符号集,V,N,=,句子，主语，,谓语,，,冠词，,形容词,，名词，,动词，,直接宾语，助动词，动词原,形,3、,语法规则集,P,=,句子,主语,谓语,，,4、,开始符号,S,=,句子,推导句子所需的四部分,2.3 文法和语言的形式定义,一.文法的形式定义,二.,直接推导和推导,三.,语言的形式定义,四.短语、直接短语、句柄,一.文法和语言的形式定义,定义1.1,：,一个上下文无关文法,G,是一个四元组,G=（,V,T,，V,N,S,P,），,其中：,1.,V,T,是一个,非空有穷,终结符号集合；,2.,V,N,是一个非空有穷的非终结符号集合，且,V,T,V,N,，,表示一类具有某种性质的符号,3.,S,V,N,开始符号。,4.,P,是一个产生式的非空有穷集合，每个产生式的形式是,A,，,其中,A,V,N,，,（V,T,V,N,）,*,开始符号,S,至少必须在某个产生式的左部出现一次,(V,T,V,N,）,*,表示什么集合?,一般情况下（缺省）符号指称：,1、A，B，C,等，,表示非终结符号,2、a,b,c,d,等，,表示终结符号,3、,，,等,表示文法符号串,（,终结符号和非终结符号组成的符号串,）,G=(a,+,*,(,),，,，,P),P：,*,（),a,（用,E、T、F,分别代替,、,、,）,E,E+T,T,T,T*F,F,F,(E),a,例,简单算术表达式的文法,G,二.直接推导和推导,令,G=(V,T,V,N,S,P),S,A,；,若,A,P,且,(V,T,V,N,),*,称,A,直接推出,表示成,A,同时也称,是,A,的,直接推导,，或称,直接归约,到,A,如果存在一个直接推导序列：,0,1,2,n,（n0）,表示成,0,n,，,称从,0,到,n,的,长度为,n,的推导。,0,n,表示从,0,出发，经0步或若干步，可推导出,n,（,0,=,n,或,0,n,）,+,*,+,推导,：,E,E+T T+T F+T ,a+T,a+F,a+a,E,E+T,T,T,T*F,F,F,(E),a,例,如,E,E+TT+TF+Ta+Ta+T,*,F,a+F,*,F,a+a,*,F,a+a,*a,特点：,A (A)，V,T,*,（,最左推导）,每一步推导都是对,最左非终结符号,进行替换,E,E+TE+T*,F,E+T*,a,E+F,*,a,E+a,*,a,T+a,*,a,F+a,*,a,a+a,*,a,特点：,A (A)，V,T,*,（,最右推导）,每一步推导都是对,最右非终结符号,进行替换，,也称规范推导，其归约称为规范归约,最左推导和最右推导,三.,语言的形式定义,设文法,G（V,T,，V,N,，,S,P）。,如果,S,则称,是一个,句型,。仅含终结符号的句型是一个,句子,。,语言,L(G）,是由文法,G,产生的所有句子所组成的集合：,L(G)|S,且,V,T,*,例子：,一个文法,G(a,b,S,S，P）,其中,P：,S,aSb,ab,则,S,aSb,aaSbb,a,3,Sb,3,a,n-1,Sb,n-1,a,n,b,n,*,+,四.短语、直接短语、句柄,令,G,是一个文法，如果有,S,A,且,A ,则称,是一个关于非终结符号,A,的，句型,的,短语,。,其次如果有,S,A,且,A,则称,是直接短语,。,一个句型的,最左直接短语,称为该句型的句柄,。,*,+,*,注意,：短语、直接短语是相对于句型而言，一个句型,可能有多个短语、直接短语，句柄只能有一个。,S,aAS,a,SbA,S,a,a,bA,S,例：,S,aAS|a,A,SbA,s,aAS,SbA,a,SbA,S,a,a,bA,a,a,bA,S,一.分析树的定义,二.画出分析树,三.子树,四.二义性文法的定义,2.4,分析树,(语法树,),和二义性,设,G=（V,T,，V,N,，S，P）,是一个上下文无关文法,G,的一棵,分析树,应满足如下条件：,每个结点有个,标记,，是,V,T,V,N,中的符号,根的标记是,S,如果结点是,内部结点,，则其标记,A,必在,V,N,中,如果编号为,n,的结点其标记为,A,n,1,n,2,n,k,是结点,n,的从左到右的儿子，并分别有标记,X,1,X,2,X,k,，,则,A,X,1,X,2,X,k,必须是,P,的产生式,如果结点,n,有标记,，,那么结点,n,是叶子，且是它父亲唯一的儿子，其他叶子结点是终结符,一.分析树（语法树）的定义,G(S):(1),S,aASa,(2),A,SbA,SS,ba,句子,aabbaa,的分析树,3,1,2,4,6,5,7,8,9,10,11,S,a,A,S,S,b,A,a,a,b,a,A,S,a,S,b,S,A,a,a,b,a,A,S,a,S,b,S,A,a,a,b,a,aSbAS,aabAS,aabbaS,aabbaa,aAS,S,二,.画分析树 (自顶向下）,一棵分析树中一个特有的结点连同它的全部后裔，连接这些后裔的边以及这些结点的标记,S,A,b,S,a,S,b,a,A,a,a,三.,子树,1、,短语,：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。,2、,直接短语,：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。,3、,句柄,：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。,子树,和,短语、直接短语、句柄,S,aAS,a,SbA,S,例：,S,aAS|a,A,SbA,对表达式文法,G,和句子,a+a,*a，,挑选出最左推导过程中产生的句型中的短语，直接短语，句柄,G=(a,+,*,(,),，,，,P),P：,（,用,E、T、F,分别代替,、,、,）,E,E+T,T,T,T*F,F,F,(E),a,E,E+T,T+T,F+T,a+T,a+T,*F,a+F,*F,a+a,*F,a+a,*a,E,E+T,T+T,F+T,a+T,a+T,*F,a+F,*F,a+a,*F,E+T,T,T+T,F,F+T,a,a,+,T,a,T*F,a,+,T,*F,a,F ,F*F,a,+,F,*F,a,a,a,+,a,*F,a,*F,a,a,a,a,*,a,a,+,a,*a,E,E,+,T,T,F,a,T,*,F,F,a,a,a+a,*a,短语,例,给定文法,G=(,a,b,c,d,e,S,A,B,S,P,),其中,P:,SaAcBe,Ab,AAb,Bd,给出句子,abbcde,的最右推导过程，并指出每一步推导的短语、直接短语、句柄。,S,aAcBe,aAcBe,aAcBe,aAcBe,abbcde,abbcde,b,bb,d,b,d,b,短语 直接短语 句柄,aAcde,aAcde,d d d,aAbcde,aAbcde,d,Ab,Ab,d,Ab,引例,文法,G,产生式如下：,E,E+E,E*E,(E),a,对于句子,a+a,*a,有如下两个最左推导：,E,E+E,a+E,a+E,*E,a+a,*E,a+a,*a,E,E*EE+E*E,a+E,*,Ea+a,*E,a+a,*a,四.,文法的二义性（,ambiquity,）的定义,E,E+E,a+E,a+E,*E,a+a,*E ,a+a,*a,E,E*EE+E*E ,a+E,*,Ea+a,*E,a+a,*a,E,E,+,E,E,*,E,a,a,a,E,E,*,E,+,E,E,a,a,a,如果一个文法的句子,存在两棵语法树,则称该句子是二义性的；,换而言之，,无二义性文法的句子,只有一棵语法树,，,尽管推导过程可以不同,。,如果一个文法,包含二义性句子,则称这个文法是二义性的;,否则，该,文法是无二义性的。,不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的。,文法等价,定义：,如果两个文法,G,1,、G,2,对应的语言集合相同,L(G,1,)=L(G,2,)，,则称文法等价,若文法,G,存在形如,A,A,的推导,则称文法,G,是递归文法.,文法,G1,产生式如下：,E,E+E,E*E,(E),a,直接递归文法,文法,G2,产生式如下：,E,T,+a,T,E*a,间接递归文法,递归文法,2.5 形式语言概观,N.Chomsky,把文法分为,四种类型,，即,0型、1型、2型、3型。差别在于,对产生式施加了不同限制,0型,：,G=(V,T,V,N,S,P),规,则形式,：,(,V,T,V,N,)*,0型文法产生的语言称为0型语言,1型（上下文有关）,：,规则有,产生式,形式,：,A,A,V,N,(,V,T,V,N,)*,1,型文法产生的语言称为1型语言（上下文有关）,2,型（上下文无关）,：,规,则形式,：,A,A,V,N,，,(,V,T,V,N,)*,2型文法产生的语言称为,2型语言（上下文无关）,3型（正规文法）,：左线性和右线性文法,A,aB,或,A,a（,右线性）,A,B,V,N,a,V,T,A,Ba,或,A,a（,左,线性）,3型文法产生的语言称为,3型语言（正规语言),语言层,正规语言3,上下文无关语言2,上下文有关语言1,递归可枚举语言0,图灵机,TM,线性界限自动机,LBA,下推自动机,PDA,有穷自动机,FA,小 结,掌握符号串和符号串集合的运算、文法和语言的定义,几个重要概念：短语、直接短语和句柄、分析树（语法树）、文法的二义性。,了解文法和语言的分类。,