第3章文法和语言课件.ppt
《第3章文法和语言课件.ppt》由会员分享,可在线阅读,更多相关《第3章文法和语言课件.ppt(99页珍藏版)》请在三一办公上搜索。
1、,第3章,当我们表述一种语言时,无非是说明这种语言的句子,如果语言只含有有穷多个句子,则只需列出句子的有穷集就行了,但对于含有无穷句子的语言来讲,存在着如何给出它的有穷表示的问题。,3.1 文法的直观概念,以自然语言为例,人们无法列出全部句子,但是人们可以给出一些规则,用这些规则来说明(或者定义)句子的组成结构,比如汉语句子可以是由主语后随谓语而成,构成谓语的是动词和直接宾语,我们采用EBNF来表示这种句子的构成规则。,当我们表述一种语言时,无非是说明这种语,BNF范式和语法图1.巴科斯范式:EBNF|你|我|他王明|大学生|工人是|学习|带的叫非终止符,不带的叫终止符。True|False,
2、BNF范式和语法图,例子:我 我 我是 我是 我是大学生,例子:,“我是大学生”的构成符合上述规则,而“我大学生是”不符合上述规则,我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据,换句话说,这些规则看成是一种元语言,用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。,“我是大学生”的构成符合上述规则,而“,语言概述,语言是由句子组成的集合,是由一组符号所构成的集合。汉语-所有符合汉语语法的句子的全体 英语-所有符合英语语法的句子的全体 程序设计语言-所有该语言的程序的全体,研究语言内容包括:每个句子构成的规律 每个句子的含义 每个句子和使用者的关系,语言概
3、述 语言是由句子组成的集合,是由一组符号,研究程序设计语言 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系语言研究的三个方面 语法 Syntax 语义 Semantics 语用 Pragmatics,研究程序设计语言,语法-表示构成语言句子的各个记号之间的组合规律语义-表示各个记号的特定含义。(各个记号和记号所表示的对象之间的关系)语用-表示在各个记号所出现的行为中,它们的来源、使用和影响。,语法-表示构成语言句子的各个记号之间的组合规律,每种语言具有两个可识别的特性,即语言的形式和该形式相关联的意义。语言的实例若在语法上是正确的,其相关联的意义可以从两个观点来看,其一是该句子的创
4、立者所想要表示的意义,另一是接收者所检验到的意义。这两个意义并非总是一样的,前者称为语言的语义,后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。,每种语言具有两个可识别的特性,即语言,如果不考虑语义和语用,即只从语法这一侧面来看语言,这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实:语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,如果不考虑语义和语用,即只从语法这一侧,例子:整数(1)单个数字是整数(2)整数再接上数字仍是整数,用BNF范式表示:0
5、|1|2|9|,所以合起来有:|0|1|2|9,例子:整数(1)单个数字是整数用BNF范式表示:所以合起来有,标识符:以字母开头以后由字母和数字组成的符号串。,例子:的巴科斯范式 a|b|z 0|1|9,标识符:以字母开头以后由字母和数字组成的符号串。例子:,例子:判定字符串a4y是 y y 4y 4y a4y,例子:判定字符串a4y是,2、语法图 作用:直观、形象的描述语法规则。例子:标识符的语法图表示,2、语法图 标识符字母字母数字,例子:无符号数的语法图表示 2.45E+12,例子:无符号数的语法图表示无符号数无符号整数数字E无符号整数,3.2 符号和符号串,1、字母表:它是非空有穷集。
6、例如:=a,b,c或=1,2,32、符号:字母表中的元素称为符号。,3、符号串:符号的有穷序列,符号串也称为字。用来表示空符号串。例如:a,ab,abc,dsfsd,3.2 符号和符号串1、字母表:它是非空有穷集。3、符号串:,4、长度:符号串的长度是指该串所包含的符号个数。用|x|表示符号串x的长度。例如:|a|=1,|abn|=35、连结:设x和y为符号串,则称xy 为他们的连结。例如:x=aa,y=bb,则xy=aabb6、空集:不含任何元素的集合,记为。,4、长度:符号串的长度是指该串所包含的符号个数。用|x|表示,7、乘积:设A和B是符号串集,则用AB表示A和B的乘积。A=a,b,B
7、=c,d,则AB=ac,ad,bc,bd,8、方幂:设A为符号串集,则定义 A0=A1=A An=An-1 A 例如:A=a,b 则有:A0=A1=a,b A2=aa,ab,ba,bb,7、乘积:设A和B是符号串集,则用AB表示A和B的乘积。8、,9、正闭包:设A为符号串集,则用A+表示A的正闭包,其具体定义如下:A+=A1A2A3 例如:A=a,A+=a,aa,aaa,10、星闭包:设A为一集合,则定义A的星闭包为A*,其具体定义如下A*=A0A+例如:A=a,A*=,a,aa,aaa,9、正闭包:设A为符号串集,则用A+表示A的正闭包,其具体定,一、引言 例子:y:=a+b*x,3.3 文
8、法与语言的形式定义,语法:赋值语句由变量加“:=”加表达式构成。语义:右边表达式求值与左变量结合赋值。用途:表达式的值的保存和计算。,一、引言3.3 文法与语言的形式定义 语法:赋值语句由,形式化方法:用一整套带有严格规定的符号体系来描述问题的理论和方法。表示文法需要一种工具,其中最常用的工具是所谓的巴克斯范式(BNF)。,例子:A=an|n1 A=a2n|n1 其BNF表示有:其BNF表示有:(1)Aa|aA(1)Aaa|aaA(2)Aa|Aa(2)Aaa|Aaa,形式化方法:用一整套带有严格规定的符号体系来描述问题的理,例子:A=abna|n1 其BNF表示有多种如下:(1)AaBa Bb
9、|Bb(2)AaBa Bb|bB(3)AaB Bba|bB,例子:A=abna|n1 其BNF表示有多种如下:,如何来描述一种语言?如果语言是有穷的(只含有有穷多个句子),可以将句子逐一列出来表示如果语言是无穷的,找出语言的有穷表示。语言的有穷表示有两个途经:生成方式(文法):语言中的每个句子可以用严格定义的规则来构造。识别方式(自动机):用一个过程,当输入的一任意串属于语言时,该过程经有限次计算后就会停止并回答“是”,若不属于,要麽能停止并回答“不是”,(要麽永远继续下去。),如何来描述一种语言?,文法即是生成方式描述语言的:语言中的每个句子可以用严格定义的规则来构造.下面给出文法的定义.进
10、而在文法的定义的基础上,给出推导的概念,句型、句子和语言的定义.,文法即是生成方式描述语言的:语言中的每个句子可以用严格定义的,定义,文法G定义为四元组(VN,VT,P,S)其中VN为非终结符号(或语法实体,或变量)集;VT为终结符号集;P为产生式(也称规则)的集合;VN,VT和P是非空有穷集。S称作识别符号或开始符号,它是一个非终结符,至少要在一条产生式中作为左部出现。VN和VT不含公共的元素,即VN VT=用V表示VN VT,称为文法G的字母表或字汇表,规则,也称重写规则、产生式或生成式,是形如或=的(,)有序对,其中是字母表V的正闭包V+中的一个符号,是V*中的一个符号。称为规则的左部,
11、称作规则的右部。,定义文法G定义为四元组(VN,VT,P,S)其中规则,也称,文法的定义,例 文法G=(VN,VT,P,S)VN=S,VT=0,1 P=S0S1,S01 S为开始符号,文法的定义例 文法G=(VN,VT,P,S),例 文法G=(VN,VT,P,S)VN=标识符,字母,数字VT=a,b,c,x,y,z,0,1,9P=a,z 0,9 S=,例 文法G=(VN,VT,P,S),文法的写法 1 G:SaAb Aab AaAb A 2 GS:Aab AaAb A SaSb 3 GS:Aab|aAb|SaSb,文法的写法,二、文法和语言形式定义1、规则式,产生式例子:Bb|Bb Aa|A2
12、、文法GZ:规则的非空有穷集合。Z:识别符号,开始符号。V:字母表,符号集合。例子:GS=S0,S,1 VS,0,1,二、文法和语言形式定义,定义3.1 文法是一个四元组G(VN,VT,P,Z)。非终极符集记为VN(大写字母)终极符集记为VT(小写字母)产生式集记为P 初始符记为Z,定义3.1 文法是一个四元组G(VN,VT,P,Z)。,例子:自然数G1(VN,VT,P,Z)和标识符G2(VN,VT,P,I)VN=N,D VT=0,1,2,9P=ND|ND,D0|1|2|9,G1:ND|ND D0|1|2|9,例子:自然数G1(VN,VT,P,Z)和标识符G2G1:N,标识符G2(VN,VT,
13、P,I)VN=I,D,L VT=0,1,2,9,a,bzP=IL|IL|ID,La|b|z D0|1|2|9,G2:IL|IL|ID La|b|c|z D0|1|2|9,标识符G2(VN,VT,P,I)G2:IL|IL|ID,定义3.2+,例子:X=AB,Aa,Bb+*3、星推导:x,4、句型:称x为句型,若有Z x,其中Z是文法的开始符。,例子:GS:S0S1 S01解:S0S1 00S11 000111,所以有:S=01,0011,000111 L(G)=0n1n|n1,例子:GS:S0S1所以有:S=01,00,6、语言:所有句子的集合称为语言。设是G给定文法,Z是开始符,则语言L(G)
14、可描述如下:,定义3.3 设G1,G2为给定文法,如果L(G1)=L(G2),则称G1和G2等价。,6、语言:所有句子的集合称为语言。设是G给定文法,Z是开始符,例1 已知文法求语言并判断是否等价 G1=(VN,VT,P,A)G2=(VN,VT,P,Z)VN=A VN=A,B VT=a,b VT=a,b P=Aab P=ABb,Ba,A1ab L(G1)=abA2Bbab L(G2)=ab G1与G2是等价的。,例1 已知文法求语言并判断是否等价A1ab L(G1)=,例2:G3S:SA|S-A Aa|b|c G4S:SA|A-S Aa|b|c,推导过程如下:,SS-A,A,S-A-A,A-A
15、-A,a-b-c,例2:G3S:SA|S-A 推导过程如下:SS-,G3与G4等价,但G3与G4的语义不同。,推导过程如下:,SA-S,A,A-A-S,A-A-A,a-b-c,a-b-c和a-b-c,G3与G4等价,但G3与G4的语义不同。推导过程如下:S,文法的等价,若L(G1)=L(G2),则称文法G1和G2是等价的。如文法G1A:A0R 与G2S:S0S1 等价 A01 S01 RA1,文法的等价若L(G1)=L(G2),则称文法G1和G2是等价,定义3.4 0型文法(短语结构文法):产生式为:,其中和是符号串。1型文法(上下文有关文法):产生式为:Au,其中AVN,u为非空串。2型文法
16、(上下文无关文法):A,其中AVN,为非空串。,3.4 文法的类型,定义3.4 3.4 文法的类型,3型文法(正则文法):产生式为:Aa,AbB,其中A,BVN,#a,bVT是符号串。例子:GZ:Za ZaA Ab|bB Bb所以:GZ是3型文法,3型文法(正则文法):,文法的类型,例:1型(上下文有关)文法 文法GS:SCDAbbA CaCABaaB CbCBBbbBADaD CBDbD DAabD,文法的类型例:1型(上下文有关)文法,文法的类型,例:2型(上下文无关)文法 文法GS:SABABS|0BSA|1,文法的类型例:2型(上下文无关)文法,3型文法,GS:S0A|1B|0A0A|
17、1B|0SB1B|1|0,GI:I lTI lT lTT dTT lT d,3型文法GS:GI:I lT,文法的类型,0型文法,四种文法之间的逐级“包含”关系,3型文法,文法的类型2型文法1型文法0型文法四种文法之间的逐级“包含”,文法和语言,0型文法产生的语言称为0型语言1型文法或上下文有关文法(CSG)产生的语言称为1型语言或上下文有关语言(CSL)2型文法或上下文无关文法(CFG)产生的语言称为2型语言或上下文无关语言(CF L)3型文法或正则(正规)文法(RG)产生的语言称为3型语言正则(正规)语言(RL),文法和语言,文法和语言,四种文法之间的关系 是将产生式做进一步限制而定义的。语
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 文法 语言 课件
链接地址:https://www.31ppt.com/p-2109025.html