《形式语言概论》PPT课件.ppt
《《形式语言概论》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《形式语言概论》PPT课件.ppt(44页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
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
14、VT T=0=0,1 1,P=SP=S0S1,S0S1,S01013型型文文法法(正正规规文文法法):除除S外外,所所有有产产生生式式的的形形式式都都为为AaB或或Aa,其中其中A VN,B VN,a VT。正规文法是正规文法是CFGCFG文法的一个子集文法的一个子集正正规规文文法法例例: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,y,z=x,y,z,P=AxB|yC,BzB|y|yC,CxD,DyD|x P=AxB|yC,BzB|y|yC,CxD,DyD|x 若若 则称右线型文法则称右线型文法直接推导直接推导
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,使用规则
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语言概论 形式语言 概论 PPT 课件
限制150内