形式语言概论讲稿.ppt-得力文库

资源描述

《形式语言概论讲稿.ppt》由会员分享，可在线阅读，更多相关《形式语言概论讲稿.ppt（41页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、形式语言概论第一页，讲稿共四十一页哦形式语言理论：形式语言理论：是指由数学方法研究自然语言和人工语是指由数学方法研究自然语言和人工语言言(程序设计语言程序设计语言)之语法理论，主要讨论了之语法理论，主要讨论了语言和文法的数学机制以及语言和文法的语言和文法的数学机制以及语言和文法的分类。分类。第二页，讲稿共四十一页哦文法的直观概念文法的直观概念如果语言只含有有穷多个句子，则只需列出句子的有如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在穷集就行了，但对于含有无穷句子的语言来讲，存在如何给出它的有穷表示的问题。虽然无法列出全部句如何给出它的有穷表示的问

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=ab123。显然，。显然，x=xx=x=x=x。符

5、符号号串串集集合合的的乘乘积积：两两个个符符号号串串集集合合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

7、 T分分别别是是非非空空有有限限的的非非终终结结符符号号集集和和终终结结符符号号集集，令令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)。其

8、中：。其中：VN：非终结符号集。非终结符号代表某一类的记号，如：非终结符号集。非终结符号代表某一类的记号，如“算术表达式算术表达式”、“赋值句赋值句”等等。等等。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：无符号二进制数的描述文法无符号二进制数的描述文法G=(VN,VT,P,B)VN=B，Bi VT=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型正规

12、文法文法类型逐逐渐渐增增加加限限制制第十四页，讲稿共四十一页哦0型型文文法法：对对任任一一产产生生式式，都都有有(VNVT)+，(VNVT)*。至至少少含含有有一个非终结符。一个非终结符。1型文法型文法（上下有关文法上下有关文法)：对对任一任一产产生式生式，都有，都有|，仅仅仅仅S除外。除外。1型文法又称为上下文有关文法，(CSG context sensitive grammar)它具有如下形式:，除有可能除有可能S外外，均有，均有=1A2=12,其中1,2 (VNVT)*,A VN,(VNVT)+,只有A出现在1,2的上下文中，才允许用取代A(即A)。1型文法中,1=|aabCBC=

13、aabBCC=aabbCC=aabbcC=aabbccCBCACABABABC思考：思考：符号串：符号串：aabbcc 是不是上述文法定义的是不是上述文法定义的?第十五页，讲稿共四十一页哦2型型文文法法（上上下下无无关关文文法法-CFG）：除除有有可可能能S,对对任任一一产产生生式式A，都有，都有A VN，(VNVT)+。2 2型型文文法法左左边边是是单单个个非非终终结结符符，右右边边是是由由终终结结符符和和非非终终结结符符组组成成的的符号串。符号串。上下无关文法也称上下无关文法也称CFG文法文法(Context Free Grammar)2型文法例型文法例1：G=G=（V VN N，V VT

14、 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 VT T=0=0，1 1，P=SP=S0S1,S0S1,S0101第十六页，讲稿共四十一页哦3型文法型文法（正（正规规文法）文法）：除除S外外,所有所有产产生式生式的形式都的形式都为为AaB或或Aa，其中其中A VN，B VN，a VT。正规文法是正规文法是CFGCFG文法的一个子集文法的一个子集正正规规

16、：w w是是U的直接推导的直接推导或说：或说：w w直接归约到直接归约到U 记作记作 Uw w。特别地，当特别地，当=时，时，A 例4：文法文法GSGS：S0S1S0S1，S01 S01，其中，其中V VNN=S,V=S,VT T=0,1=0,1直接推导：直接推导：0S10S10011 0011（U=0S1U=0S1，w=0011w=0011，使用规则，使用规则S01S01，=0=0，=1=1）S S 0S1 0S1（U=SU=S，w=0S1w=0S1，使用规则，使用规则S0S1S0S1，=，=）0S10S100S11 00S11（U=0S1U=0S1，w=00S11w=00S11，使用规则

17、，使用规则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=uv=u前面例子前面例子 G=(VN,VT,P,S)VN=E VT=i,+,*,(,)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的一个算术

18、表达式的一个算术表达式(由终结符组成由终结符组成)。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=x

19、uy直直接接推推导导中中，若若y VT*,U VN,即即U是是符符号号串串xUy中中最最右右非非终终结结符符，则则称称此此直直接接推推导导为为最最右右直直接接推推导导。若若一一个个推推导导的每一步直接推导都是最右直接推导，那么此推导称为最右推导。的每一步直接推导都是最右直接推导，那么此推导称为最右推导。最右直接推导又称为规范直接推导，最右推导又称为最右直接推导又称为规范直接推导，最右推导又称为规范推导规范推导。例例文法如文法如G12.996969a69第二十一页，讲稿共四十一页哦句型、句子和语言定定义义2.6如如果果符符号号串串x是是从从识识别别符符号号推推导导出出来来的的，即即Sx，则则称

20、称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都是文法都是文法G的句型，的句型，000111是是G的句子。的句子。结论结论句子一定是句型，句型不一定是句子。句子一定是句型，句型不一定是句子

21、。区别第二十二页，讲稿共四十一页哦例例:文法文法G=（VN，VT，P，S），），其中其中VN=S，VT=0，1，P=S0S1，S01表示什么语言？表示什么语言？答案：答案：L(G)0n1n n 1因为S0S100S110n1n重复利用规则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+i)是句型。是句型。第二十三页，讲稿共四十一页哦表示语言表示语言有文法推出语言有文法推出语言文法文法G

22、N为：为：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文法变成？文法变成？第二十五页，讲稿共四十一页哦文法

23、为更巧妙文法为第二十六页，讲稿共四十一页哦习题二习题二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 第二十八页，讲稿共四十一页哦文法的化简第二十九页，讲稿共四十一页哦化简文法例：GS 1)SBe 2)

24、BCe3)BAf 4)AAe 5)Ae 6)CCf7)DfSBeBAfAAe Ae第三十页，讲稿共四十一页哦文法和语言文法和语言0型文法产生的语言称为型文法产生的语言称为0型语言型语言1 1型文法或上下文有关文法（型文法或上下文有关文法（CSG ）产生的语言称产生的语言称为为1 1型语言型语言或上下文有关或上下文有关语言（语言（CSL）2 2型文法或上下文无关文法（型文法或上下文无关文法（CFG ）产生的语言称产生的语言称为为2型语言型语言或上下文无关或上下文无关语言（语言（CF L）3 3型文法或正则（正规）文法（型文法或正则（正规）文法（RG）产生的语言称产生的语言称为为3型语言型语言正则

25、（正规）正则（正规）语言（语言（RL）第三十一页，讲稿共四十一页哦语法树设文法设文法G=（VN,VT,P,S），对于文法），对于文法G的任意一个句型都存在一的任意一个句型都存在一个相应的语法树：个相应的语法树：树中每个结点都有一个标记，该标记是树中每个结点都有一个标记，该标记是VN VT中的一个符号；中的一个符号；树的根结点标记是文法的识别符号树的根结点标记是文法的识别符号S；若树的一个结点至少有一个叶子结点，则该结点的标记一定是一个若树的一个结点至少有一个叶子结点，则该结点的标记一定是一个非终结符；非终结符；若树的一个结点有多个叶结点，该结点的标记为若树的一个结点有多个叶结点，该结点的标记

26、为A，这些叶结点，这些叶结点的标记从左到右分别是的标记从左到右分别是B1，B2，.，Bn，则，则AB1B2Bn P文法的句型都可依据其产生式来生成相应的语法树。文法的句型都可依据其产生式来生成相应的语法树。第三十二页，讲稿共四十一页哦问题：一个句型是否对应唯一的一棵语法树？问题：一个句型是否对应唯一的一棵语法树？例：例：GZ:GZ:Z aZbZ aZbZ ZZ ZZ abZ ab 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)

27、(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+T)(T+T)(T*F+T)(F*F+T)(i*F+T)(i*i+T)(i*i+F)(i*i+i)EEEFFTTTTi+*(EFii改写为无二义文法改写为无二义文法:G(E)：E E+EE E*EE (E)E iGE:EE+T|TTT*F|FF(E)|i第三十五页，讲稿共四十一页哦上下文无关文法的语法树上下文无关文法的语法树例例:GS:EE+T|TE+T|TTT*F|

28、FF(E)|iEE+TT*F(E)iE+T句型句型E+(E+T)*i的语法树的语法树叶子结点：树中没有子孙的结点。叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。该推导树称为该句型的语法树。第三十六页，讲稿共四十一页哦产生式树产生式树例例: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)第三十七页，讲稿共四十一页哦

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

30、文法识别符号作为根结点，看其是否能够构造一个语法树，而且此语法树的所有叶子结点从左到右所构成的符号串恰好是待检查的符号串。如果能够生成这样的语法树，则表明待检查的符号串是该文法的一个句型或句子，否则便不是。自上而下分析方法可分为：不确定的自上而下分析方法和确定的自上而下分析方法两种。不确定的自上而下分析方法可能需要回溯，因此时间花费多，效率低第三十九页，讲稿共四十一页哦自上而下的语法分析自上而下的语法分析例：文法G：S cAd A ab A a识别输入串 w=cabd 是否该文法的句子SSScAdcAdab推导过程：推导过程：ScAdcabd第四十页，讲稿共四十一页哦自下而上分析方法自下而上分析方法的基本思想是从待检查的符号串出发，看最终是否能归约（推导的逆过程）到文法的识别符号。如果能够归约到文法的识别符号，则表明此待检查的符号串是该文法的一个句型或句子，否则便不是。从待检查的符号串出发，在其中寻找一个称为句柄的子串，此句柄如果与文法中某一产生式右部相匹配，那么就用此产生式左部（一个非终结符）去替换待检查符号串的句柄，替换之后得一个新符号串，然后，对这个新符号串作同样的处理。这个过程称为归约过程。第四十一页，讲稿共四十一页哦

展开阅读全文