形式语言概论讲稿.ppt
《形式语言概论讲稿.ppt》由会员分享,可在线阅读,更多相关《形式语言概论讲稿.ppt(41页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、形式语言概论第一页,讲稿共四十一页哦形式语言理论:形式语言理论:是指由数学方法研究自然语言和人工语是指由数学方法研究自然语言和人工语言言(程序设计语言程序设计语言)之语法理论,主要讨论了之语法理论,主要讨论了语言和文法的数学机制以及语言和文法的语言和文法的数学机制以及语言和文法的分类。分类。第二页,讲稿共四十一页哦文法的直观概念文法的直观概念 如果语言只含有有穷多个句子,则只需列出句子的有如果语言只含有有穷多个句子,则只需列出句子的有穷集就行了,但对于含有无穷句子的语言来讲,存在穷集就行了,但对于含有无穷句子的语言来讲,存在如何给出它的有穷表示的问题。虽然无法列出全部句如何给出它的有穷表示的问
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=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文法的一个子集文法的一个子集正正规规
15、文文法法例例:G=G=(V VN N,V VT T,P P,A A),其其中中V VN N=A,=A,B,B,C,C,DD,V VT T=x,=x,y,y,z z ,P=AxB|yC,BzB|y|yC,CxD,DyD|x P=AxB|yC,BzB|y|yC,CxD,DyD|x 若若 则称右线型文法则称右线型文法第十七页,讲稿共四十一页哦直接推导直接推导(定义定义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 或说:或说
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语言 概论 讲稿
限制150内