《形式语言概论》PPT课件.ppt

《《形式语言概论》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《形式语言概论》PPT课件.ppt（44页珍藏版）》请在三一办公上搜索。

1、第2章形式语言概论,文法和语言形式化定义 文法的类型 语言和语法树 文法和语言的几点说明 分析方法简介 本章小结,形式语言理论：是指由数学方法研究自然语言和人工语言(程序设计语言)之语法理论，主要讨论了语言和文法的数学机制以及语言和文法的分类。,文法的直观概念,如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在如何给出它的有穷表示的问题。虽然无法列出全部句子，但是可以给出一些规则，用这些规则来说明句子的组成结构，然后用它们去推导产生句子。,文法：是阐述语法的一个工具,“你是大学生”对“我是教师”对“我大学生是”错“我学习大学生”对,句子=主语谓语主语=

2、代词|名词代词=我|你|他名词=王明|大学生|教师|英语谓语=动词直接宾语动词=是|学习直接宾语=代词|,句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是名词 我是教师,推导：我是教师,例如，描述标识符的文法如下：:=:=:=:=a|b|c|d|z:=0|1|2|3|4|5|6|7|8|9,字母表和符号串,字母表：是元素的非空有穷集合，用表示。字母表中的元素称为符号。例如：汉语的字母表中包括汉字、数字及标点符号等。PASCAL语言的字母表是由字母、数字、算符、保留字等组成。,符号串的长度：符号串中符号的个数。符号串x的长度记为|x|。如|ab012|=5。空符号串：不含任何符号的符号串，

3、记为。|=0。,符号串：符号的有穷序列称为符号串，如compiler,string等。,符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。如:x=ab、y=123，则xy=ab123。显然，x=x=x。,符号串集合的乘积：两个符号串集合A和B的乘积定义为：AB=xy|xA且yB。特别地A=A=A。如:A=ab,c,B=d,efg,则AB=abd,abefg,cd,cefg。,符号串的方幂：设x为符号串，则xn=xxx(x连接n次)。特别有x0=。,符号串集合：若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。,符号串集合的方幂：同

4、一符号串集合的乘积。如:A=a,bc,则A2=aa,abc,bca,bcbc A3=A2A=?,符号串集合的正闭包:符号串集合A正闭包A+=A1A2.An.即A+为集合A上所有符号串的集合。符号串集合的自反闭包:符号串集合A正闭包A*=A+=A+显然有 A+=AA*=A*A,文法,产生式：设VN,VT分别是非空有限的非终结符号集和终结符号集，令V=VNVT,VNVT=，一个产生式是一般形式为：A-，其中A VN,V*，A称为产生式的左部，称为产生式的右部。-表示为定义为 如果产生式集合中的产生式有共同的左部，如:A-，A-，则可将其简写为：A-|。,变量表,符号表,文法：文法G定义为四元组(V

5、N,VT,P,S)。其中：VN：非终结符号集。非终结符号代表某一类的记号，如“算术表达式”、“赋值句”等等。VT：终结符号集。终结符号代表不可再分的基本符号，如保留字、标识符、常数、运算符、界符等。VNVT=；V=VNVT称为文法G的词汇表。S：开始符号。开始符号是一个特殊的非终结符号，表示文法G所定义的最终的语法范畴。P：产生式的集合。产生式是定义语法范畴的一种书写格式，形式如下：其中，称为产生式左部，它必须是包含非终结符；称为产生式右部，它可以是终结符、非终结符或他们的组合。,例1：文法G=（VN，VT，P，S）VN=标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P=a,z 0

6、,9 S=习惯上只将产生式写出。并有如下约定：1、第一条产生式的左部是开始符号；2、用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符；3、G可写成GS，其中S是开始符号；,文法例子,例2：无符号二进制数的描述文法 如下形式：1011.0101G=(VN,VT,P,B)VN=B，BiVT=0,1,.P=BBi|Bi.Bi Bi0|1|Bi 0|Bi 1,例3：设E代表“算术表达式”；i代表单个变量或常数；+、*、（、）是构成算术表达式的运算符和括号。定义由前面符号组成的单个变量或常量组成的算术表达式；若E是一个算术表达式，则E+E,E*E,(E)也是算术表达式

7、，写成文法形式：G=(VN,VT,P,S)VN=E VT=i,+,*,(,)P=Ei,E E+E,E E*E,E(E),思考：(i+i)是不是该文法定义的表达式？,文法的类型：语言学家乔姆斯基(Chomsky)把文法分成以下四种类型：,0型 短语文法1型 上下文有关文法2型 上下文无关文法3型 正规文法,文 法 类 型,逐 渐 增 加 限 制,0型文法：对任一产生式，都有(VNVT)+，(VNVT)*。至少含有一个非终结符。1型文法（上下有关文法）：对任一产生式，都有|，仅仅 S除外。,1型文法又称为上下文有关文法，它具有如下形式:，除有可能S外，均有=1A2=12,其中1,2(VNVT)*,

8、AVN,(VNVT)+,只有A出现在1,2的上下文中，才允许用取代A。1型文法中,1=|=|,1型文法例：G=（VN,VT，P，S），其中VN=S,B,C，VT=a,b,c，P=SaSBC,SabC,CBBC,bBbb,bCbc,cCcc,S=aSBC=aabCBC=aabBCC=aabbCC=aabbcC=aabbcc,CBCACABABABC,2型文法（上下无关文法）：除有可能S,对任一产生式A，都有AVN，(VNVT)+。2型文法左边是单个非终结符，右边是由终结符和非终结符组成的符号串。上下无关文法也称CFG文法(Context Free Grammar),2型文法例1：G=（VN，VT

9、，P，S），其中VN=S，T，VT=a，b，c,d，P=SaTd,TbT|cT|b|c 2型文法例2：G=（VN，VT，P，S），其中VN=S，VT=0，1，P=S0S1,S01,3型文法（正规文法）：除S外,所有产生式的形式都为 AaB或Aa，其中A VN，B VN，a VT。正规文法是CFG文法的一个子集,正规文法例：G=（VN，VT，P，A），其中VN=A,B,C,D，VT=x,y,z，P=AxB|yC,BzB|y|yC,CxD,DyD|x,若 则称右线型文法,直接推导(定义2.3)：设文法G=（VN,VT,P,S），A是文法G的产生式，若有,V*，使得U=A,w=,则说：U（应用规则A

10、）直接产生w 或说：w是U的直接推导 或说：w直接归约到U 记作 U w。特别地，当=时，A 例4：文法GS：S0S1，S01，其中VN=S,VT=0,1直接推导：0S10011（U=0S1，w=0011，使用规则S01，=0，=1）S 0S1（U=S，w=0S1，使用规则S0S1，=，=）0S100S11（U=0S1，w=00S11，使用规则S0S1，=0，=1）,推导(定义2.4)：存在v=0=1=n=w,(n0)则称w为v的一个推导，记为v u。另使用(定义2.5)v u 表示v u或 v=u,前面例子 G=(VN,VT,P,S)VN=E VT=i,+,*,(,)P=Ei,E E+E,E

11、 E*E,E(E),由 E(E)，E=(E)再由 E E+E，(E)=(E+E)再使用E(E)，(E+E)=(i+E)=(i+i)证明(i+i)是文法G的一个算术表达式(由终结符组成)。,v推导出ww规约到v,最左推导,定义2.9 在xUy=xuy直接推导中，若x VT*,U VN,即U是符号串xUy中最左非终结符，则称此直接推导为最左直接推导。若一个推导的每一步直接推导都是最左直接推导，那么此推导称为最左推导。例 G12：|a|b|c|x|y|z0|1|2|3|4|5|6|7|8|9aa6a69,最右推导,定义2.10 在xUy=xuy直接推导中，若y VT*,U VN,即U是符号串xUy中

12、最右非终结符，则称此直接推导为最右直接推导。若一个推导的每一步直接推导都是最右直接推导，那么此推导称为最右推导。最右直接推导又称为规范直接推导，最右推导又称为规范推导。例 文法如G12.996969a69,句型、句子和语言,定义2.6 如果符号串x是从开始符号推导出来的，即S x，则称x是文法GS的句型。开始符号S也是文法G的句型。定义2.7 如果符号串x是终结符号构成，即S x，x VT*，则称x是文法GS的句子。定义2.8 设S是文法G的开始符号，文法G的语言L(G)=u|S+u,u VT*，即文法的语言是文法的所有句子构成的集合。,例4中文法：S，0S1，000111都是文法G的句型，0

13、00111是G的句子。结论句子一定是句型，句型不一定是句子。,区别,例:文法G=（VN，VT，P，S），其中 VN=S，VT=0，1，P=S 0S1，S 01 表示什么语言？,答案：L(G)0n1n n1,因为S0S100S11 0n1n重复利用规则S0S1,例：证明(i*i+i)是文法G(E)：E i|E+E|E*E|(E)的一个句子。证明：E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E，(E)，(E*E+E)，(i*i+i)是句型。,表示语言,表示语言,有文法推出语言,文法GN为：N-D|ND D-0|1|2|3|4|5|6|7|8|9 GN的语言是什么？,表

14、示语言,GN的语言是V+。V=0,1,2,3,4,5,6,7,8,9,GN的语言是 G(N)=(0|1|2|3|4|5|6|7|8|9)n|n=1,有语言推出文法,文法为,文法为,文法为,习题二2.2(4)若i,j,k=0文法变成？,文法为,更巧妙文法为,习题二2.2(6)能被5整除的整数集合的文法 EN0|N5 N|DD0|2|3|4|5|6|7|8|9,N,(1)允许0开头的偶正整数集合的文法 ENT|D TNT|D ND|1|3|5|7|9 D0|2|4|6|8(2)不允许0开头的偶正整数集合的文法 ENT|D TFT|G ND|1|3|5|7|9 D2|4|6|8 FN|0 GD|0,

15、文法的化简,化简文法,例：GS 1)SBe 2)BCe3)BAf 4)AAe 5)Ae 6)CCf7)Df,SBeBAfAAe Ae,文法和语言,0型文法产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFG）产生的语言称为2型语言或上下文无关语言（CF L）3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）,语法树,设文法G=（VN,VT,P,S），对于文法G的任意一个句型都存在一个相应的语法树：树中每个结点都有一个标记，该标记是VNVT中的一个符号；树的根结点标记是文法的识别符号

16、S；若树的一个结点至少有一个叶子结点，则该结点的标记一定是一个非终结符；若树的一个结点有多个叶结点，该结点的标记为A，这些叶结点的标记从左到右分别是B1，B2，.，Bn，则AB1B2BnP,文法的句型都可依据其产生式来生成相应的语法树。,问题：一个句型是否对应唯一的一棵语法树？,例：GZ:Z aZbZ ZZ ab,Z a Z b a b,Z a Z b Z a b,句型aabb的语法树,句型(i*i+i)的语法树,E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i),E(E)(E*E)(i*E)(i*E+E)(i*i+E)(i*i+i),文法G(E)：E i|E+E|E*

17、E|(E),E T F(E)(E+T)(T+T)(T*F+T)(F*F+T)(i*F+T)(i*i+T)(i*i+F)(i*i+i),改写为无二义文法:,G(E)：E E+EE E*EE(E)E i,GE:EE+T|TTT*F|FF(E)|i,上下文无关文法的语法树,例:GS:EE+T|TTT*F|FF(E)|i,E E+T T*F(E)i E+T,句型E+(E+T)*i的语法树,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。,产生式树,例:GS:EE+T|T,TT*F|F,F(E)|i,*,T,F,i,F,E,(,),*

18、,T,F,i,F,E,(,),+,E,F,(a),(b),(c),(d),(e),(f),文法和语言的几点说明,(1)文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达的；(2)文法中某些非终结符，由它不能推出终结符号串来，称为不可终止的（无用非终结符）；(3)可空终结符,可以用于消除左递归；(4)一个文法，如果它的一个句子有两棵或两棵以上的语法树，则称该句子具有二义性。如果一个文法含有二义性的句子，则该文法具有二义性。形如UU的产生式。会引起文法的二义性。,自上而下分析方法,自上而下分析方法的基本思想是从文法的识别符号出发，看是否能够推导出待检查的符号串，如果能够推导出这个符号

19、串，则表明此符号串是该文法的一个句型或句子，否则便不是。或者说，以文法识别符号作为根结点，看其是否能够构造一个语法树，而且此语法树的所有叶子结点从左到右所构成的符号串恰好是待检查的符号串。如果能够生成这样的语法树，则表明待检查的符号串是该文法的一个句型或句子，否则便不是。自上而下分析方法可分为：不确定的自上而下分析方法和确定的自上而下分析方法两种。不确定的自上而下分析方法可能需要回溯，因此时间花费多，效率低,自上而下的语法分析,例：文法G：S cAd A ab A a识别输入串 w=cabd 是否该文法的句子,SSScAdcAd a b推导过程：S cAd cabd,自下而上分析方法,自下而上

20、分析方法的基本思想是从待检查的符号串出发，看最终是否能归约（推导的逆过程）到文法的识别符号。如果能够归约到文法的识别符号，则表明此待检查的符号串是该文法的一个句型或句子，否则便不是。从待检查的符号串出发，在其中寻找一个称为句柄的子串，此句柄如果与文法中某一产生式右部相匹配，那么就用此产生式左部（一个非终结符）去替换待检查符号串的句柄，替换之后得一个新符号串，然后，对这个新符号串作同样的处理。这个过程称为归约过程。,自下而上的语法分析,例：文法G：S cAd A ab A a识别输入串 w=cabd 是否该文法的句子,SAA c a b d c a b d c a b d 规约过程：S cAd cabd,句型分析的有关问题,1）如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是V，且有n条规则：VA1|A2|An，那么如何确定用哪个右部去替代V？2）如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”,小结,文法和语言形式化定义；文法的类型，0型文法，上下相关文法，上下无关文法，正规文法；语言和语法树，推导和规范推导、句型句子和语言、产生式树；文法和语言的几点说明，多余规则，有害规则，二义性、可空终结符；分析方法简介，自上而下和自下而上的分析方法；,