《形式语言概论》PPT课件.ppt-淘文阁

资源描述

《《形式语言概论》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《形式语言概论》PPT课件.ppt（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第2章形式语言概论形式语言概论文法和语言形式化定义文法和语言形式化定义文法的类型文法的类型语言和语法树语言和语法树文法和语言的几点说明文法和语言的几点说明分析方法简介分析方法简介本章小结本章小结形式语言理论：形式语言理论：是指由数学方法研究自然语言和人工语是指由数学方法研究自然语言和人工语言言(程序设计语言程序设计语言)之语法理论，主要讨论之语法理论，主要讨论了语言和文法的数学机制以及语言和文法了语言和文法的数学机制以及语言和文法的分类。的分类。文法的直观概念文法的直观概念如果语言只含有有穷多个句子，则只需列出句子的如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷

2、句子的语言来讲，存在有穷集就行了，但对于含有无穷句子的语言来讲，存在如何给出它的有穷表示的问题。虽然无法列出全部句如何给出它的有穷表示的问题。虽然无法列出全部句子，但是可以给出一些规则，用这些规则来说明句子子，但是可以给出一些规则，用这些规则来说明句子的组成结构，然后用它们去推导产生句子。的组成结构，然后用它们去推导产生句子。文法：是阐述语法的一个工具“你是大学生”对 “我是教师”对“我大学生是”错 “我学习大学生”对句子句子=主语谓语主语谓语主语主语=代词代词|名词名词代词代词=我我|你你|他他名词名词=王明王明|大学生大学生|教师教师|英语英语谓语谓语=动词直接宾语动词直接宾语动词动词=是

3、是|学习学习直接宾语直接宾语=代词代词|句子句子主语谓语主语谓语代词谓语代词谓语我谓语我谓语我动词直接宾语我动词直接宾语我是名词我是名词我是教师我是教师推导：推导：我是教师我是教师巴科斯巴科斯-瑙尔范式瑙尔范式(EBNF)例如，描述标识符的文法如下：例如，描述标识符的文法如下：:=:=:=:=a|b|c|d|z:=0|1|2|3|4|5|6|7|8|9字母表和符号串字母表和符号串字母表：字母表：是元素的非空有穷集合，用是元素的非空有穷集合，用表示。字母表中的表示。字母表中的元素称为符号。元素称为符号。例如：例如：汉语的字母表中包括汉字、数字及标点符号等。PASCAL语言的字母表是由字母、

4、数字、算符、保留字等组成。符号串的长度：符号串的长度：符号串中符号的个数。符号串符号串中符号的个数。符号串x的长度记为的长度记为|x|。如。如|ab012|=5。空符号串：空符号串：不含任何符号的符号串，记为不含任何符号的符号串，记为。|=0。符号串：符号串：符号的有穷序列称为符号串，如符号的有穷序列称为符号串，如compiler,string等。等。符号串的连接：符号串的连接：设设x和和y是符号串，它们的连接是符号串，它们的连接xy是把是把y的符的符号写在号写在x的符号之后得到的符号串。的符号之后得到的符号串。如如:x=ab:x=ab、y=123y=123，则，则xy=ab123xy=ab1

5、23。显然，。显然，x=x=xx=x=x。符符号号串串集集合合的的乘乘积积：两两个个符符号号串串集集合合A和和B的的乘乘积积定定义义为为：AB=xy|x A且且y B。特别地。特别地A=A=A。如如:A=ab,c,B=d,efg,:A=ab,c,B=d,efg,则则AB=abd,abefg,cd,cefgAB=abd,abefg,cd,cefg。符号串的方幂：符号串的方幂：设设x为符号串，则为符号串，则xn=xxx(x连接连接n次次)。特别有特别有x0=。符号串集合：符号串集合：若集合若集合A中的一切元素都是某字母表上的符号中的一切元素都是某字母表上的符号串，则称串，则称A为该字母表上的符号串

6、集合为该字母表上的符号串集合。符号串集合的方幂：符号串集合的方幂：同一符号串集合的乘积。同一符号串集合的乘积。如如:A=a,bc,则则A2=aa,abc,bca,bcbc A3=A2A=?符号串集合的正闭包符号串集合的正闭包:符号串集合符号串集合A A正闭包正闭包A A+=A=A1 1 A A2 2.A An n.即即A A+为集合为集合A A上所上所有符号串的集合。有符号串的集合。符号串集合的自反闭包符号串集合的自反闭包:符号串集合符号串集合A A正闭包正闭包A A*=A A+=A=A+显然有显然有 A A+=AA=AA*=A=A*A A文法文法产生式：产生式：设设V VN N,V,VT T

7、分分别别是是非非空空有有限限的的非非终终结结符符号号集集和和终终结结符符号号集集，令令V=VV=VN N V VT T,V,VN N V VT T=，一个产生式是一般形式为：，一个产生式是一般形式为：A-，其其中中A V VN N,V V*，A称称为为产产生生式式的的左左部部，称称为为产生式的右部产生式的右部。-表示为定义为表示为定义为如果产生式集合中的产生式有共同的左部，如果产生式集合中的产生式有共同的左部，如如:A-，A-，则可将其简写为：，则可将其简写为：A-|。变量表变量表符号表符号表文法：文法：文法文法G定义为四元组定义为四元组(VN,VT,P,S)。其中：。其中：VN：非终结符号

8、集。非终结符号代表某一类的记号，：非终结符号集。非终结符号代表某一类的记号，如如“算术表达式算术表达式”、“赋值句赋值句”等等。等等。VT：终结符号集。终结符号代表不可再分的基本符号，：终结符号集。终结符号代表不可再分的基本符号，如保留字、标识符、常数、运算符、界符等。如保留字、标识符、常数、运算符、界符等。VNVT=；V=VN VT称为文法称为文法G的词汇表。的词汇表。S：开始符号。开始符号是一个特殊的非终结符号，表：开始符号。开始符号是一个特殊的非终结符号，表示文法示文法G所定义的最终的语法范畴。所定义的最终的语法范畴。P：产生式的集合。产生式是定义语法范畴的一种书写：产生式的集合。产生式

9、是定义语法范畴的一种书写格式，形式如下：格式，形式如下：其中，其中，称为产生式左部，它必须是包含非终结符；称为产生式左部，它必须是包含非终结符；称为产生式右部，它可以是终结符、非终结符或他们的组合。称为产生式右部，它可以是终结符、非终结符或他们的组合。例例1：文法文法G=（VN，VT，P，S）VN=标识符，字母，数字标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P=a,z 0,9 S=习惯上只将产生式写出。并有如下约定：习惯上只将产生式写出。并有如下约定：1、第一条产生式的左部是开始符号；、第一条产生式的左部是开始符号；2、用用尖尖括括号号括括起起的的是是非非终终结结符符，否否则则

10、为为终终结结符符。或或者者大大写写字字母母表示非终结符，小写字母表示终结符；表示非终结符，小写字母表示终结符；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代表单个变量或常数；代表单个变量或常数；+、*、（、）是构成算术表达式的运算符和括号。定义由前面、（、）是构成算术表达式的运算符和括号。定义由前面符号组成

11、的单个变量或常量组成的算术表达式；若符号组成的单个变量或常量组成的算术表达式；若E是一个算术是一个算术表达式，则表达式，则E+E,E*E,(E)也是算术表达式，写成文法形式：也是算术表达式，写成文法形式：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型型文文法法：对对任任一一产产生生式式，都

12、都有有(VNVT)+，(VNVT)*。至少含有一个非终结符。至少含有一个非终结符。1型型文文法法（上上下下有有关关文文法法）：对对任任一一产产生生式式，都都有有|，仅仅仅仅S除外。除外。1型文法又称为上下文有关文法，它具有如下形式:，除有可能除有可能S外外，均有均有=1A2 =12,其中1,2 (VNVT)*,A VN,(VNVT)+,只有A出现在1,2的上下文中，才允许用取代A。1型文法中,1=|aSBC=aabCBC=aabBCC=aabbCC=aabbcC=aabbccCBCACABABABC2型型文文法法（上上下下无无关关文文法法）：除除有有可可能能S,对对任任一一产产生生式式A，都有

13、，都有A VN，(VNVT)+。2 2型型文文法法左左边边是是单单个个非非终终结结符符，右右边边是是由由终终结结符符和和非非终终结结符符组组成的符号串。成的符号串。上下无关文法也称上下无关文法也称CFG文法文法(Context Free Grammar)2型文法例型文法例1：G=G=（V VN N，V VT T，P P，S S），其其中中V VN N=S=S，TT，V VT T=a=a，b b，c,c,dd，P=SP=SaTd,TaTd,TbT|cT|b|c bT|cT|b|c 2型文法例型文法例2：G=G=（V VN N，V VT T，P P，S S），其中），其中V VN N=S=S，V

15、(定义定义2.3)：设设文文法法G=G=（V VN N,V VT T,P,P,S S），A是是文文法法G G的的产产生生式式，若若有有,V V*，使使得得U=A,=A,w=w=,则则说说：U（应应用用规规则则A）直直接接产产生生w w 或或说说：w w是是U的的直直接接推推导导或或说说：w w直直接接归归约约到到U 记作记作 Uw w。特别地，当特别地，当=时，时，A 例4：文法文法GSGS：S0S1 S0S1，S01 S01，其中，其中V VNN=S,V=S,VT T=0,1=0,1直接推导：直接推导：0S10S10011 0011（U=0S1U=0S1，w=0011w=0011，使用规则

16、，使用规则S01S01，=0=0，=1=1）S S 0S1 0S1（U=SU=S，w=0S1w=0S1，使用规则，使用规则S0S1S0S1，=，=）0S10S100S11 00S11（U=0S1U=0S1，w=00S11w=00S11，使用规则，使用规则S0S1S0S1，=0=0，=1=1）推导推导(定义定义2.4)：存在存在v=v=0 0=1 1=n n=w,(n0)=w,(n0)则称则称w为为v的一个推导，记为的一个推导，记为v uv u。另使用另使用(定义定义2.5)v u v u 表示表示v v u u或或 v=u v=u前面例子前面例子 G=(VN,VT,P,S)VN=E VT=i,

17、+,*,(,)P=Ei,E E+E,E 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中中最最左左非非终终结结符符，则则称称此此直直接接推推导导为为最最左左直直接接推推导导。若若一一个个推推导导的的每每一一步步直直接接推推导导都都是是最最左左直直接接推推导导，那那么

18、么此此推推导导称为最左推导。称为最左推导。例例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中中最最右右非非终终结结符符，则则称称此此直直接接推推导导为为最最右右直直接接推推导导。若若一一个个推推导导的的每每一一步步直直接接推推导导都都是是最最右右直直接接推推导导，那么此推导称为最右推导。那么此推导称为最右推导。最最右右直直接接推推导导又又称称为为规规范范直直接接推推导导，最最右右推推导导又又称称为为规规范范推推导导。例例文法如文法如G12.

19、996969a69句型、句子和语言定定义义2.6如如果果符符号号串串x是是从从开开始始符符号号推推导导出出来来的的，即即Sx，则称则称x是文法是文法GS的句型。开始符号的句型。开始符号S也是文法也是文法G的句型。的句型。定定义义2.7如如果果符符号号串串x是是终终结结符符号号构构成成，即即Sx，x VT*，则称则称x是文法是文法GS的句子。的句子。定义定义2.8设设S是文法是文法G的开始符号，文法的开始符号，文法G的语言的语言L(G)=u|S+u,u VT*，即即文文法法的的语语言言是是文文法法的的所所有有句句子子构成的集合。构成的集合。例例4中文法：中文法：S，0S1，000111都是文法都

20、是文法G的句型，的句型，000111是是G的句子。的句子。结论结论句子一定是句型，句型不一定是句子。句子一定是句型，句型不一定是句子。区别例例:文法文法G=（VN，VT，P，S），），其中其中VN=S，VT=0，1，P=S0S1，S01表示什么语言？表示什么语言？答案：答案：L(G)0n1n n 1因为S0S100S11 0n1n重复利用规则S0S1n例：证明例：证明(i*i+i)是文法是文法G(E)：E i|E+E|E*E|(E)的一个句子。的一个句子。n 证明：证明：n E (E)(E+E)(E*E+E)(i*E+E)n (i*i+E)(i*i+i)n E，(E)，(E*E+E)，(i*i

21、+i)是句型。是句型。表示语言表示语言有文法推出语言有文法推出语言文法文法GN为：为：N-D|ND D-0|1|2|3|4|5|6|7|8|9 GN的语言是什么？的语言是什么？表示语言GN的语言是的语言是V+。V=0,1,2,3,4,5,6,7,8,9GN的语言是的语言是 G(N)=(0|1|2|3|4|5|6|7|8|9)n|n=1有语言推出文法有语言推出文法文法为S S ABCABCA A aA|aaA|aB B bB|bbB|bC C cCcC|c 文法为文法为S S aS|aAaS|aAA A bA|bBbA|bBB B cBcB|c c 习题二习题二2.2(4)若若i,j,k=0文

22、法变成？文法变成？文法为更巧妙文法为习题二习题二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 文法的化简化简文法例：GS1)SBe2)BCe3)BAf4)AAe 5)Ae6)CCf7)DfSBeBAfAAe Ae文法和语言文法和

23、语言n0型文法产生的语言称为型文法产生的语言称为0型语言型语言n1 1型文法或上下文有关文法（型文法或上下文有关文法（CSG ）产生的语产生的语言称为言称为1 1型语言型语言或上下文有关或上下文有关语言（语言（CSL）n2 2型文法或上下文无关文法（型文法或上下文无关文法（CFG ）产生的语产生的语言称为言称为2型语言型语言或上下文无关或上下文无关语言（语言（CF L）n3 3型文法或正则（正规）文法（型文法或正则（正规）文法（RG）产生的产生的语言称为语言称为3型语言型语言正则（正规）正则（正规）语言（语言（RL）语法树设文法设文法G=（VN,VT,P,S），对于文法），对于文法G的任意一个

24、句型都存的任意一个句型都存在一个相应的语法树：在一个相应的语法树：树中每个结点都有一个标记，该标记是树中每个结点都有一个标记，该标记是VN VT中的一个符号；中的一个符号；树的根结点标记是文法的识别符号树的根结点标记是文法的识别符号S；若树的一个结点至少有一个叶子结点，则该结点的标记一定若树的一个结点至少有一个叶子结点，则该结点的标记一定是一个非终结符；是一个非终结符；若树的一个结点有多个叶结点，该结点的标记为若树的一个结点有多个叶结点，该结点的标记为A，这些叶，这些叶结点的标记从左到右分别是结点的标记从左到右分别是B1，B2，.，Bn，则，则AB1B2Bn P文法的句型都可依据其产生式来生成

25、相应的语法树。文法的句型都可依据其产生式来生成相应的语法树。问题：一个句型是否对应唯一的一棵语法树？问题：一个句型是否对应唯一的一棵语法树？例：例：GZ:GZ:Z Z aZbaZbZ Z Z ZZ Z abab Z Z a Z b a Z b a b a b Z Z a Z b a Z b Z Z a b a b句型句型aabbaabb的语法树的语法树句型句型(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*E|(E)ETF(E)(E

27、也把该推导树称为该句型的语法树。也把该推导树称为该句型的语法树。产生式树产生式树例例:GS:EE+T|TE+T|T,TT*F|F,F(E)|iE+ETE+ET*TFE+ET*TFiE+ET*TFiFE+ET*TFiFE()E+ET*TFiFE()+EF(a)(b)(c)(d)(e)(f)文法和语言的几点说明(1)文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达的；(2)文法中某些非终结符，由它不能推出终结符号串来，称为不可终止的（无用非终结符）；(3)可空终结符,可以用于消除左递归；(4)一个文法，如果它的一个句子有两棵或两棵以上的语法树，则称该句子具有二义性。如果一个文法含有

28、二义性的句子，则该文法具有二义性。形如UU的产生式。会引起文法的二义性。自上而下分析方法自上而下分析方法的基本思想是从文法的识别符号出发，看是否能够推导出待检查的符号串，如果能够推导出这个符号串，则表明此符号串是该文法的一个句型或句子，否则便不是。或者说，以文法识别符号作为根结点，看其是否能够构造一个语法树，而且此语法树的所有叶子结点从左到右所构成的符号串恰好是待检查的符号串。如果能够生成这样的语法树，则表明待检查的符号串是该文法的一个句型或句子，否则便不是。自上而下分析方法可分为：不确定的自上而下分析方法和确定的自上而下分析方法两种。不确定的自上而下分析方法可能需要回溯，因此时间花费多，效

29、率低自上而下的语法分析自上而下的语法分析例：文法G：S cAdA abA a识别输入串w=cabd是否该文法的句子SSScAdcAdab推导过程：推导过程：ScAdcabd自下而上分析方法自下而上分析方法的基本思想是从待检查的符号串出发，看最终是否能归约（推导的逆过程）到文法的识别符号。如果能够归约到文法的识别符号，则表明此待检查的符号串是该文法的一个句型或句子，否则便不是。从待检查的符号串出发，在其中寻找一个称为句柄的子串，此句柄如果与文法中某一产生式右部相匹配，那么就用此产生式左部（一个非终结符）去替换待检查符号串的句柄，替换之后得一个新符号串，然后，对这个新符号串作同样的处理。这个过程

30、称为归约过程。自下而上的语法分析自下而上的语法分析例：文法G：S cAdA abA a识别输入串w=cabd是否该文法的句子SAAcabdcabdcabd规约过程：规约过程：ScAdcabd句型分析的有关问题句型分析的有关问题1）如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是V，且有n条规则：VA1|A2|An，那么如何确定用哪个右部去替代V？2）如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”小结文法和语言形式化定义；文法的类型，0型文法，上下相关文法，上下无关文法，正规文法；语言和语法树，推导和规范推导、句型句子和语言、产生式树；文法和语言的几点说明，多余规则，有害规则，二义性、可空终结符；分析方法简介，自上而下和自下而上的分析方法；

展开阅读全文