前后文无关文法和语言(姚版).ppt
《前后文无关文法和语言(姚版).ppt》由会员分享,可在线阅读,更多相关《前后文无关文法和语言(姚版).ppt(102页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第二章第二章 前后文无关文法和语言前后文无关文法和语言n语言文法概述语言文法概述n文法和语言的形式定义文法和语言的形式定义n文法的类型文法的类型n上下文无关文法及其语法树上下文无关文法及其语法树n句型的分析句型的分析n有关文法实用中的一些说明有关文法实用中的一些说明1第第2章章 前后文无关文法和语言前后文无关文法和语言本章目的本章目的 为语言的语法描述寻求工具。为语言的语法描述寻求工具。通过该工具,可以:通过该工具,可以:y掌握掌握对源程序给精确无二义(严谨、简洁、易读)对源程序给精确无二义(严谨、简洁、易读)的语法描述手段之一的语法描述手段之一-文法。文法。y根据语言文法的特点来指导语法分析
2、的过程根据语言文法的特点来指导语法分析的过程y从描述语言的文法可以自动构造出可用的分析程从描述语言的文法可以自动构造出可用的分析程序序y制导语义翻译制导语义翻译第第2章章 前后文无关文法和语言前后文无关文法和语言本章难重点本章难重点 关于文法和语言的概念是形式语言的理论基础,形式语言抽象地定义为一个数学系统。形式是指这样的事实:语言的所有规则只以什麽符号串能出现的方式来陈述。这里介绍的语言的语法描述工具正是这样的系统。第第2章章 前后文无关文法和语言前后文无关文法和语言第第2章章 前后文无关文法和语言前后文无关文法和语言文法及语言的表示 当我们表述一种语言时,无非是说明这种语言的句子(句子句子
3、:一定字符集(称字母表)上的一字符一定字符集(称字母表)上的一字符串串),如果语言只含有有穷多个句子,则只需列出句子的有穷集就行了,但对于含有无穷句子的语言来讲,存在着如何给出它的有穷表示的问题。以自然语言为例,人们无法列出全部句子,但是人们可以给出一些规则,用这些规则来说明(或者定义)句子的组成结构(也就是各种属性的单词所允许的排列规则),比如汉语句子可以是由主语后随谓语而成,构成谓语的是动词和直接宾语,我们采用EBNF来表示这种句子的构成规则:第第2章章 前后文无关文法和语言前后文无关文法和语言“我是大学生”。是汉语的一个句子句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语
4、谓语=动词直接宾语动词=是学习直接宾语=代词名词 第第2章章 前后文无关文法和语言前后文无关文法和语言 “我是大学生”的构成符合上述规则,而“我大学生是”不符合上述规则,我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据,换句话说,这些规则看成是一种元语言,用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。第第2章章 前后文无关文法和语言前后文无关文法和语言英语句子sentence subject This|Computers|Iverb-phrase|adverb neververb is|run|am|tellobject the|a|noun unive
5、rsity|world|cheese|liesThis is a university.Computers run the world.I am the cheese.I never tell lies.第第2章章 前后文无关文法和语言前后文无关文法和语言语言概述语言概述n语言是由句子组成的集合,是由一组记号所构成的语言是由句子组成的集合,是由一组记号所构成的集合。集合。n汉语汉语-所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体n英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体n程序设计语言程序设计语言-所有该语言的程序的全体所有该语言的程序的全体 语法语法:每个句
6、子构成的规律:每个句子构成的规律n研究语言研究语言 语义语义:每个句子的含义:每个句子的含义 语用语用:每个句子和使用者的关系:每个句子和使用者的关系第第2章章 前后文无关文法和语言前后文无关文法和语言研究程序设计语言 语法:每个程序构成的规律 语义:每个程序的含义1、语法语法-表示构成语言句子的各个记号之间的组合规律。语法包括:词法规则和语法规则 例如:C语法规定了构成条件语句的各个记号的组合规律为:第一个单词(记号)必须是”if”,然后是单词”(”、表达式,.。2、语义语义-表示各个记号的特定含义。(各个记号和记号所表示的对象之间的关系)对一个语言来说,不仅要给出它的词法、语法规则,而且要
7、定义它的单词符号和语法单位的意义。离开语义,语言只不过是一堆符号的集合。所谓一个语言的语义是这样的一组规则,使用它可以定义一个程序的意义。这些规则称为语义规则。阐明语义要比阐明语法难的多,现在还没有一种形式系统描述语义。第第2章章 前后文无关文法和语言前后文无关文法和语言 例例 如如:我我 们们 根根 据据 C C语语 法法 可可 以以 判判 断断 出出 声声 明明 语语 句句”int”int i=999;”i=999;”是是 正正 确确 的的,但但 是是 无无 法法 判判 断断 出出 声声 明明 语语 句句”int”int i=9999999;”i=9999999;”是是错错误误的的,因因为
8、为该该语语句句的的语语法法没没有有错错误误(即即单单词词的的排排列列顺顺序序是是对对的的),其其错错误误是是因因为为数数值值99999999999999超超过过了了整整型变量的最大允许值。这个错误就需要语义检查才能发现。型变量的最大允许值。这个错误就需要语义检查才能发现。如果不考虑语义,即只从语法这一侧面来看语言,这种意如果不考虑语义,即只从语法这一侧面来看语言,这种意义下的语言称作义下的语言称作形式语言形式语言。形式语言抽象地定义为一个数学。形式语言抽象地定义为一个数学系统。系统。“形式形式”是指这样的事实:语言的所有规则只以什么是指这样的事实:语言的所有规则只以什么符号串能出现的方式来陈述
9、。形式语言理论是对符号串集合符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。研究的基础。第第2章章 前后文无关文法和语言前后文无关文法和语言有关定义和记号有关定义和记号符号符号:可以相互区别的记号(元素)。:可以相互区别的记号(元素)。字母表字母表:符号(元素)的非空有穷集合。:符号(元素)的非空有穷集合。符号串符号串:由字母表:由字母表 中的符号组成的任何有穷序列中的符号组成的任何有穷序列称为该字母表上的符号串。称为该字母表上的符号串。1.1.空符号串空符号串(没有没有符号
10、的符号串符号的符号串)是是 上的符号串上的符号串 2.2.若若x x是是 上的符上的符号串号串,a,a是是 的元素的元素,则则xaxa是是 上的符号串上的符号串 3.3.y y是是 上的符号串上的符号串,当且仅当它可以由当且仅当它可以由1 1和和2 2导出。导出。例如:例如:=a,b =a,b ,a,b,aa,ab,aabba,a,b,aa,ab,aabba都都是是 上的符号串上的符号串第第2章章 前后文无关文法和语言前后文无关文法和语言 符号串符号串s s的头(的头(前缀前缀):移走符号串):移走符号串s s尾部尾部的零个或多于零个符号得到的符号串的零个或多于零个符号得到的符号串.如:如:b
11、 b是符号串是符号串bananabanana的一个前缀的一个前缀.符号串符号串s s的尾(的尾(后缀后缀):删去符号串):删去符号串s s头部头部的零个或多于零个符号得到的符号串的零个或多于零个符号得到的符号串.如如:nana:nana是符号串是符号串bananabanana的一个后缀的一个后缀.符号串符号串s s的的子串子串:从:从s s中删去一个前缀和一中删去一个前缀和一个后缀得到的符号串个后缀得到的符号串.如如:ana:ana是符号串是符号串bananabanana的一个子串的一个子串.第第2章章 前后文无关文法和语言前后文无关文法和语言符号串的运算符号串的运算符号串的符号串的长度长度:
12、符号串中符号的个数:符号串中符号的个数.符号串符号串s s的长度的长度记为记为|s|s|。的长度为的长度为0 0连接连接:符号串:符号串x x、y y的连接的连接,是把是把y y的符号写在的符号写在x x的符号的符号之后得到的符号串之后得到的符号串xy xy 如如 x=ab,y=cd x=ab,y=cd 则则 xy=abcd xy=abcd 有有a=a a=a 方幂方幂:符号串自身连接:符号串自身连接n n次得到的符号串次得到的符号串 a an n 定义为定义为 aaaa n aaaa n个个a aa a1 1=a,a=a,a2 2=aa=aa则则a a0 0=符号串符号串集合集合:若集合:若
13、集合A A中所有元素都是某字母表中所有元素都是某字母表 上上的符号串,则称的符号串,则称A A为字母表为字母表 上的符号串集合。上的符号串集合。第第2章章 前后文无关文法和语言前后文无关文法和语言两个符号串集合两个符号串集合A A和和B B的乘积定义为的乘积定义为 AB=AB=xy|xxy|x A A且且y y B B 若集合若集合A=A=ab,cdeab,cde,B=B=0,10,1 则则 AB=AB=ab1,ab0,cde0,cde1ab1,ab0,cde0,cde1 使用使用 *表示表示 上的一切符号串(包括上的一切符号串(包括)组成的集)组成的集合。合。*称为称为的的闭包闭包。上的上的
14、除除外的所有符号串组成的集合记为外的所有符号串组成的集合记为+。+称为称为的的正闭包正闭包。第第2章章 前后文无关文法和语言前后文无关文法和语言例:=a,b *=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,第第2章章 前后文无关文法和语言前后文无关文法和语言语言语言是由句子组成的集合,是由一组符号所构成的集合。换言之,字母表上的一个语言是上的一些符号串的集合 (字母表上的每个语言是*的一个子集)。例如:字母表=a,b,*=,a,b,aa,ab,ba,bb,aaa,aab,集合ab,aabb,aaabbb,anbn,或表示为w|w*且w=
15、anbn,n1为字母表上的一个语言。集合a,aa,aaa,或表示为w|w*且w=an,n1 为字母表上的一个语言。是一个语言。即 是一个语言。第第2章章 前后文无关文法和语言前后文无关文法和语言文法和语言的形式定义 如何来描述一种语言?如何来描述一种语言?如果语言是有穷的(只含有有穷多个句子),可以将如果语言是有穷的(只含有有穷多个句子),可以将句子逐一列出来表示句子逐一列出来表示如果语言是无穷的,找出语言的有穷表示。语言的有如果语言是无穷的,找出语言的有穷表示。语言的有穷表示有两个途经:穷表示有两个途经:-生成方式生成方式 (文法文法):语言中的每个句子可以用):语言中的每个句子可以用严格定
16、义的规则来构造。严格定义的规则来构造。-识别方式(识别方式(自动机自动机):用一个过程,当输入的一):用一个过程,当输入的一任意串属于语言时,该过程经有限次计算后就会停任意串属于语言时,该过程经有限次计算后就会停止并回答止并回答“是是”,若不属于,要么能停止并回答,若不属于,要么能停止并回答“不是不是”,(要么永远继续下去。),(要么永远继续下去。)第第2章章 前后文无关文法和语言前后文无关文法和语言文法是程序语言的生成系统,而自动机则是程序语言的识别系统;用文法可以精确地定义一个语言,并依据该文法构造出识别这个语言的自动机。因此,文法对程序语言和编译程序的构造具有重要意义,如程序语言的词法可
17、用正规文法描述,语法可用上下文无关文法描述,而语义则要借助于上下文有关文法描述。下面给出文法的定义.进而在文法的定义的基础上,给出推导的概念,句型、句子和语言的定义.第第2章章 前后文无关文法和语言前后文无关文法和语言文法和语言的形式定义文法和语言的形式定义n文法的定义文法的定义n推导的定义推导的定义n句型、句子、语言的定义句型、句子、语言的定义第第2章章 前后文无关文法和语言前后文无关文法和语言文法的定义文法的定义文法文法G定义为四元组(定义为四元组(VN,VT,P,S)VN:非终结符集非终结符集 VT:终结符集终结符集 P:产生式(规则)集合产生式(规则)集合 S:开始符号开始符号VNVT
18、=,S SVNV=V=VNVT,称为文法称为文法G G的文法的文法符号集合符号集合第第2章章 前后文无关文法和语言前后文无关文法和语言文法文法G定义为四元组定义为四元组(VN,VT,P,S),其中 VN为非终结符号(或语法实体,或变量)集;VT为终结符号集;P为产生式(也称规则)的集合;VN,VT和P是非空有穷集。S称作识别符号或开始符号,它是一个非终结符,至少要在一条产生式中作为左部出现。VN和VT不含公共的元素,即VN VT=用V表示VN VT,称为文法G的字母表或字汇表第第2章章 前后文无关文法和语言前后文无关文法和语言规则的定义规则的定义n规则(重写规则、产生式或生成式),规则(重写规
19、则、产生式或生成式),是形如是形如或或=的(的(,)有有序对,且序对,且VV+,VV*。称为规则的左部称为规则的左部(或生成式或生成式的左部的左部)。称为规则的右部称为规则的右部(或生成式或生成式的右部的右部)。第第2章章 前后文无关文法和语言前后文无关文法和语言文法的定义文法的定义n例:文法例:文法G=(VN,VT,P,S)VN=S,VT=0,1 P=S0S1,S01 S为开始符号为开始符号第第2章章 前后文无关文法和语言前后文无关文法和语言 终结符号终结符号终结符号终结符号是指语言不可再分的基本符号,通常是一个语言的字母表;终结符代表了语法的最小元素,是一种个体记号。非终结符号非终结符号非
20、终结符号非终结符号也称语法变量,它代表语法实体或语法范畴;非终结符代表一个一定的语法概念,因此,一个非终结符是一个类、一个集合。例如,在程序语言中,可以把变量、常数、“+”、“*”等看作是终结符,而像“算术表达式”这个非终结符则代表着一定算术式组成的类,如i*(i+i)、i+i+i等;也即每个非终结符代表着由一些终结符和非终结符且满足一定规则的符号串组成的集合。第第2章章 前后文无关文法和语言前后文无关文法和语言 文法开始符号是一个特殊的非终结符,它代表文法所定义的语言中我们最终感兴趣的语法实体,即语言的目标,而其它语法实体只是构造语言目标的中间变量;如表达式文法的语言目标是表达式,而程序语言
21、的目标通常为程序。产生式(也称产生规则或规则)是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个。例如,有:P1 P2 Pn 为书写方便,可将这些有相同左部的产生式合并为一个,即缩写成 P12n 其中,每个i(i=1,2,n)称为P的一个候选式,直竖“”读为“或”,它与“”一样是用来描述文法的元语言符号(即不属于的字符)。第第2章章 前后文无关文法和语言前后文无关文法和语言例例 文法文法G=(VN,VT,P,S)VN=标识符,字母,数字标识符,字母,数字 VT=a,b,c,x,y,z,0,1,9 P=a,zz 0,0,99 S=第第2章章 前后文无关文法和语言前后文无关文法和语言
22、例:试构造产生标识符的文法。解答首先,标识符是以字母开头的字母数字串,我们用L表示“字母”类非终结符,用D表示“数字”类非终结符,而用T表示“字母或数字”类非终结符,则有:Labz D019 TLD 其次,如果用S表示“字母数字串”类,则T是一字母或数字,ST也是字母数字串,即有 STST 其中,产生式STST是一种左递归形式,由它可以产生一串T。第第2章章 前后文无关文法和语言前后文无关文法和语言 最后,作为“标识符”的非终结符I,它或者是一单个字母,或者为一字母后跟字母数字串,即 ILLS 因此,产生标识符的文法GI为:G=(a,b,z,0,9,I,S,T,L,D,P,I)P:ILLS S
23、TST TLD Labz D019第第2章章 前后文无关文法和语言前后文无关文法和语言例:写一文法,使其语言是奇数集合,但不允许出现以0打头的奇数。解答根据题意,我们可以将奇数划分为如图21所示的三个部分,即最高位允许出现19,用非终结符B表示;中间部分可以出现任意多位数字09,每一位用非终结符D表示;最低位只允许出现1、3、5、7、9等奇数,用A表示。第第2章章 前后文无关文法和语言前后文无关文法和语言图21 奇数划分示意第第2章章 前后文无关文法和语言前后文无关文法和语言 由于中间部分可出现任意位,所以另引入了一个非终结符M,它包括最高位和中间位部分。假定开始符为N,则可得到文法GN为:G
24、=(0,1,9,N,A,M,B,D,P,N)P:N NAMA/*一位数字多位数字*/M MBMD/*仅两位数字(无中间位)多于两位数字*/A A13579 B B123456789 D D0B第第2章章 前后文无关文法和语言前后文无关文法和语言推导推导 推导把产生式看成重写规则,把符号串中的非终结符用其产生式右部的串来代替。亦即:从识别符号开始,不断将当前符号串中的非终结符号替换为该符号的某个规则的右部。直到当前的符号串中所有的符号都是终结符号为止。第第2章章 前后文无关文法和语言前后文无关文法和语言“我是大学生”的推导过程 开始先找=左端的带有句子的规则并把它由=右端的符号串代替,这个动作表
25、示成:句子 主语谓语 然后在得到的串主语谓语中,选取主语或谓语,再用相应规则的=右端代替之。比如,选取了主语,并采用规则主语=代词,那么得到:主语谓语 代词谓语,重复做下去.句子:“我是大学生”的全部动作过程是:句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生 第第2章章 前后文无关文法和语言前后文无关文法和语言 实际上,推导过程就是对所要分析的句子进行断句(语法分析)的过程。例如,句子“我是大学生”如果符合句子的规则,则其在语法结构上必然是由两部分组成的:前一部分是主语,后一部分是谓语;又因为主语是由代词或名词组成的,所以符合上述文法的句子的前缀必是代词或
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 前后文 无关 文法 语言 姚版
限制150内