前后文无关文法和语言(姚版).ppt
《前后文无关文法和语言(姚版).ppt》由会员分享,可在线阅读,更多相关《前后文无关文法和语言(姚版).ppt(102页珍藏版)》请在三一办公上搜索。
1、1,第二章 前后文无关文法和语言,语言文法概述文法和语言的形式定义文法的类型上下文无关文法及其语法树句型的分析有关文法实用中的一些说明,本章目的,为语言的语法描述寻求工具。通过该工具,可以:掌握对源程序给精确无二义(严谨、简洁、易读)的语法描述手段之一-文法。根据语言文法的特点来指导语法分析的过程从描述语言的文法可以自动构造出可用的分析程序制导语义翻译,本章难重点,关于文法和语言的概念是形式语言的理论基础,形式语言抽象地定义为一个数学系统。形式是指这样的事实:语言的所有规则只以什麽符号串能出现的方式来陈述。这里介绍的语言的语法描述工具正是这样的系统。,文法及语言的表示,当我们表述一种语言时,无
2、非是说明这种语言的句子(句子:一定字符集(称字母表)上的一字符串),如果语言只含有有穷多个句子,则只需列出句子的有穷集就行了,但对于含有无穷句子的语言来讲,存在着如何给出它的有穷表示的问题。以自然语言为例,人们无法列出全部句子,但是人们可以给出一些规则,用这些规则来说明(或者定义)句子的组成结构(也就是各种属性的单词所允许的排列规则),比如汉语句子可以是由主语后随谓语而成,构成谓语的是动词和直接宾语,我们采用EBNF来表示这种句子的构成规则:,“我是大学生”。是汉语的一个句子,句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词,“我
3、是大学生”的构成符合上述规则,而“我大学生是”不符合上述规则,我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据,换句话说,这些规则看成是一种元语言,用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。,英语句子,sentence subject This|Computers|Iverb-phrase|adverb neververb is|run|am|tellobject the|a|noun university|world|cheese|liesThis is a university.Computers run the world.I am the c
4、heese.I never tell lies.,语言概述,语言是由句子组成的集合,是由一组记号所构成的集合。汉语-所有符合汉语语法的句子的全体英语-所有符合英语语法的句子的全体程序设计语言-所有该语言的程序的全体 语法:每个句子构成的规律研究语言 语义:每个句子的含义 语用:每个句子和使用者的关系,研究程序设计语言 语法:每个程序构成的规律 语义:每个程序的含义1、语法-表示构成语言句子的各个记号之间的组合规律。语法包括:词法规则和语法规则 例如:C语法规定了构成条件语句的各个记号的组合规律为:第一个单词(记号)必须是”if”,然后是单词”(”、表达式,.。2、语义-表示各个记号的特定含义。
5、(各个记号和记号所表示的对象之间的关系)对一个语言来说,不仅要给出它的词法、语法规则,而且要定义它的单词符号和语法单位的意义。离开语义,语言只不过是一堆符号的集合。所谓一个语言的语义是这样的一组规则,使用它可以定义一个程序的意义。这些规则称为语义规则。阐明语义要比阐明语法难的多,现在还没有一种形式系统描述语义。,例如:我们根据C语法可以判断出声明语句”int i=999;”是正确的,但是无法判断出声明语句”int i=9999999;”是错误的,因为该语句的语法没有错误(即单词的排列顺序是对的),其错误是因为数值9999999超过了整型变量的最大允许值。这个错误就需要语义检查才能发现。如果不考
6、虑语义,即只从语法这一侧面来看语言,这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实:语言的所有规则只以什么符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,有关定义和记号,符号:可以相互区别的记号(元素)。字母表:符号(元素)的非空有穷集合。符号串:由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串(没有符号的符号串)是上的符号串 2.若x是上的符号串,a是的元素,则xa是上的符号串 3.y是上的符号串,当且仅当它可以由1和2导出。例如:=a,b,a,b,aa,ab,
7、aabba都是上的符号串,符号串s的头(前缀):移走符号串s尾部的零个或多于零个符号得到的符号串.如:b是符号串banana的一个前缀.符号串s的尾(后缀):删去符号串s头部的零个或多于零个符号得到的符号串.如:nana是符号串banana的一个后缀.符号串s的子串:从s中删去一个前缀和一个后缀得到的符号串.如:ana是符号串banana的一个子串.,符号串的运算符号串的长度:符号串中符号的个数.符号串s的长度记为|s|。的长度为0连接:符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy 如 x=ab,y=cd 则 xy=abcd 有a=a 方幂:符号串自身连接n次得到的符号串
8、an 定义为 aaaa n个a a1=a,a2=aa则a0=符号串集合:若集合A中所有元素都是某字母表上的符号串,则称A为字母表上的符号串集合。,两个符号串集合A和B的乘积定义为 AB=xy|xA且yB若集合A=ab,cde,B=0,1 则 AB=ab1,ab0,cde0,cde1使用*表示上的一切符号串(包括)组成的集合。*称为的闭包。上的除外的所有符号串组成的集合记为+。+称为的正闭包。,例:=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,语言是由句子组成的集合,是由一组符号所构成的集合。换言之,字母表上的一个语言是上的一些
9、符号串的集合(字母表上的每个语言是*的一个子集)。例如:字母表=a,b,*=,a,b,aa,ab,ba,bb,aaa,aab,集合ab,aabb,aaabbb,anbn,或表示为w|w*且w=anbn,n1为字母表上的一个语言。集合a,aa,aaa,或表示为w|w*且w=an,n1 为字母表上的一个语言。是一个语言。即 是一个语言。,文法和语言的形式定义,如何来描述一种语言?如果语言是有穷的(只含有有穷多个句子),可以将句子逐一列出来表示如果语言是无穷的,找出语言的有穷表示。语言的有穷表示有两个途经:-生成方式(文法):语言中的每个句子可以用严格定义的规则来构造。-识别方式(自动机):用一个过
10、程,当输入的一任意串属于语言时,该过程经有限次计算后就会停止并回答“是”,若不属于,要么能停止并回答“不是”,(要么永远继续下去。),文法是程序语言的生成系统,而自动机则是程序语言的识别系统;用文法可以精确地定义一个语言,并依据该文法构造出识别这个语言的自动机。因此,文法对程序语言和编译程序的构造具有重要意义,如程序语言的词法可用正规文法描述,语法可用上下文无关文法描述,而语义则要借助于上下文有关文法描述。下面给出文法的定义.进而在文法的定义的基础上,给出推导的概念,句型、句子和语言的定义.,文法和语言的形式定义,文法的定义推导的定义句型、句子、语言的定义,文法的定义,文法G定义为四元组(VN
11、,VT,P,S)VN:非终结符集 VT:终结符集 P:产生式(规则)集合 S:开始符号VNVT=,SVNV=VNVT,称为文法G的文法符号集合,文法G定义为四元组(VN,VT,P,S),其中 VN为非终结符号(或语法实体,或变量)集;VT为终结符号集;P为产生式(也称规则)的集合;VN,VT和P是非空有穷集。S称作识别符号或开始符号,它是一个非终结符,至少要在一条产生式中作为左部出现。VN和VT不含公共的元素,即VN VT=用V表示VN VT,称为文法G的字母表或字汇表,规则的定义,规则(重写规则、产生式或生成式),是形如或=的(,)有序对,且V+,V*。称为规则的左部(或生成式的左部)。称为
12、规则的右部(或生成式的右部)。,文法的定义,例:文法G=(VN,VT,P,S)VN=S,VT=0,1 P=S0S1,S01 S为开始符号,终结符号是指语言不可再分的基本符号,通常是一个语言的字母表;终结符代表了语法的最小元素,是一种个体记号。非终结符号也称语法变量,它代表语法实体或语法范畴;非终结符代表一个一定的语法概念,因此,一个非终结符是一个类、一个集合。例如,在程序语言中,可以把变量、常数、“+”、“*”等看作是终结符,而像“算术表达式”这个非终结符则代表着一定算术式组成的类,如i*(i+i)、i+i+i等;也即每个非终结符代表着由一些终结符和非终结符且满足一定规则的符号串组成的集合。,
13、文法开始符号是一个特殊的非终结符,它代表文法所定义的语言中我们最终感兴趣的语法实体,即语言的目标,而其它语法实体只是构造语言目标的中间变量;如表达式文法的语言目标是表达式,而程序语言的目标通常为程序。产生式(也称产生规则或规则)是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个。例如,有:P1 P2 Pn 为书写方便,可将这些有相同左部的产生式合并为一个,即缩写成 P12n 其中,每个i(i=1,2,n)称为P的一个候选式,直竖“”读为“或”,它与“”一样是用来描述文法的元语言符号(即不属于的字符)。,例 文法G=(VN,VT,P,S)VN=标识符,字母,数字 VT=a,b,c,
14、x,y,z,0,1,9 P=a,z 0,9 S=,例:试构造产生标识符的文法。解答首先,标识符是以字母开头的字母数字串,我们用L表示“字母”类非终结符,用D表示“数字”类非终结符,而用T表示“字母或数字”类非终结符,则有:Labz D019 TLD 其次,如果用S表示“字母数字串”类,则T是一字母或数字,ST也是字母数字串,即有 STST 其中,产生式STST是一种左递归形式,由它可以产生一串T。,最后,作为“标识符”的非终结符I,它或者是一单个字母,或者为一字母后跟字母数字串,即 ILLS 因此,产生标识符的文法GI为:G=(a,b,z,0,9,I,S,T,L,D,P,I)P:ILLS ST
15、ST TLD Labz D019,例:写一文法,使其语言是奇数集合,但不允许出现以0打头的奇数。解答根据题意,我们可以将奇数划分为如图21所示的三个部分,即最高位允许出现19,用非终结符B表示;中间部分可以出现任意多位数字09,每一位用非终结符D表示;最低位只允许出现1、3、5、7、9等奇数,用A表示。,图21 奇数划分示意,由于中间部分可出现任意位,所以另引入了一个非终结符M,它包括最高位和中间位部分。假定开始符为N,则可得到文法GN为:G=(0,1,9,N,A,M,B,D,P,N)P:NAMA/*一位数字多位数字*/MBMD/*仅两位数字(无中间位)多于两位数字*/A13579 B1234
16、56789 D0B,推导,推导把产生式看成重写规则,把符号串中的非终结符用其产生式右部的串来代替。亦即:从识别符号开始,不断将当前符号串中的非终结符号替换为该符号的某个规则的右部。直到当前的符号串中所有的符号都是终结符号为止。,“我是大学生”的推导过程,开始先找=左端的带有句子的规则并把它由=右端的符号串代替,这个动作表示成:句子 主语谓语 然后在得到的串主语谓语中,选取主语或谓语,再用相应规则的=右端代替之。比如,选取了主语,并采用规则主语=代词,那么得到:主语谓语 代词谓语,重复做下去.句子:“我是大学生”的全部动作过程是:句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我
17、是名词 我是大学生,实际上,推导过程就是对所要分析的句子进行断句(语法分析)的过程。例如,句子“我是大学生”如果符合句子的规则,则其在语法结构上必然是由两部分组成的:前一部分是主语,后一部分是谓语;又因为主语是由代词或名词组成的,所以符合上述文法的句子的前缀必是代词或名词。这样,如果所要识别的字符串的第一个单词不是或,则该句子不符合文法;否则,继续判断其后续子串是否符合谓语的语法.,推导的定义,直接推导“”是文法G的产生式,若有v,w满足:v=,w=,其中V*,V*则称v直接推导到w,记作 v w 或w直接归约到v其中“”表示直接推导出,是应用产生规则进行推导的记号。注意“”与“”不同,“”是
18、产生式中的定义记号。直接推导是对文法符号串A中的非终结符A用相应的产生式A的右部来替换,从而得到。我们给出推导的说明如下:,例:G:S0S1,S01 S 0S1 00S11 000S111 00001111 句子 主语谓语 代词谓语 我谓语我动词直接宾语 我是直接宾语 我是名词 我是大学生,(1)如果1可直接推出2,2可直接推出3,n-1可直接推出n,即存在一个自1至n的推导序列:123n(n0),则我们称1可推导出n,记为1 n,它表示从1出发经过一步或若干步可推导出n。(2)如果记1 1,则表示从1出发,经过0步或者若干步可推导出n;也即1 n意味着或者1 n,或者1 n。,+,*,+,*
19、,推导的定义,例如,对下面的文法GE:EE+EE*E(E)i(3.1)其中,惟一的非终结符E可以看成是代表一类算术表达式。我们可以从E出发进行一系列的推导,如表达式i+i*i的推导如下:EE+EE+E*E E+E*iE+i*ii+i*i,文法的句型、句子的定义,句型:有文法G,若S=x,则称x是文法G的句型。句子:有文法G,若S=x,且xVT*,则称x是文法G的句子。由定义可知,仅含终结符的句型是一个句子。开始符S本身只能是文法的一个句型而不可能是一个句子;此外,上面推导出的i+i*i是文法GE的一个句子(当然也是一个句型),而E+E、E+E*E、E+E*i和E+i*i都是文法GE的句型。例:
20、G:S0S1,S01S 0S1 00S11 000S111 00001111G的句型S,0S1,00S11,000S111,00001111G的句子00001111,01,*,*,例:GE:EE+T|T TT*F|F F(E)|aEE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a句子:用符号a,+,*,(和)构成的算术表达式,文法,语言的定义,由文法G生成的语言记为L(G),它是文法G的一切句子的集合:L(G)=x|S=x,其中S为文法的开始符号,且xVT*例:G:S0S1,S01 L(G)=0n1n|n1,*,例 文法GS:(1)SaSBE(2)SaBE(3)E
21、BBE(4)aBab(5)bBbb(6)bEbe(7)eEee L(G)=anbnen|n1,S a S BE(SaSBE)a aBEBE(SaBE)aabEBE(aBab)aabBEE(EBBE)aabbEE(bBbb)aabbeE(bEbe)aabbee(eEee)G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成,使用产生式(1)n-1次,得到推导序列:S=an-1S(BE)n-1,然后使用产生式(2)一次,得到:S=an-1S(BE)n-1 an(BE)n。然后从an(BE)n继续推导,总是对EB使用产生式(3)的右部进行替换,而最终在得到的串中,所有的B都先于所有的E。例如
22、,若n=3,aaaBEBEBE aaaBBEEBE aaaBBEBEE aaaBBBEEE。即有:S=*anBnEn接着,使用产生式(4)一次,得到S=anbBn-1En,然后使用产生式(5)n-1次得到:S=anbnEn,最后使用产生式(6)一次,使用产生式(7)n-1次,得到:S=anbnen 也能证明,对于n1,串anbnen是唯一形式的终结符号串,*,*,*,*,*,已知语言描述,写出文法例:若语言由0、1符号串组成,串中0和1的个数相同,构造其文法。A 0B|1CB 1|1A|0BBC 0|0A|1CC已知文法,写出语言描述例:GE:EE+T|T TT*F|F F(E)|a,文法的等
23、价,若L(G1)=L(G2),则称文法G1和G2是等价的。如文法G1A:A0R 与G2S:S0S1 等价 A01 S01 RA1,文法的类型,语言学家NoamChomsky于1956年首先建立了形式语言的描述,定义了四类文法及相应的形式语言,并分别与相应的识别系统相联系,它对程序语言的设计、编译方法、计算复杂性等方面都产生了重大影响。,1、0型文法与0型语言(对应图灵机)如果文法G的每一个产生式具有下列形式:其中,V*VNV*(注:V=VNVT),即至少含有一个非终结符;V*;则称文法G为0型文法或短语文法,记为PSG。0型文法相应的语言称为0型语言或称递归可枚举集,它的识别系统是图灵(Tur
24、ing)机。,2、1型文法与1型语言(对应线性界限自动机,自然语言)文法G的每一个产生式,均在0型文法的基础上增加了字符长度上满足的限制,则称文法G为1型文法或上下文有关文法,记为CSG。1型文法相应的语言称为1型语言或上下文有关语言,它的识别系统是线性界限自动机。1型文法的另一种定义方法是文法G的每一个产生式具有下列形式:A 其中,、V*,AVN,V+;显然它满足前述定义的长度限制,但它更明确地表达了上下文有关的特性,即A必须在、的上下文环境中才能被所替换。,3、2型文法与2型语言(对应下推自动机,程序设计语言)文法G的每一个产生式具有下列形式:A 其中,AVN,V*,则称文法G为2型文法或
25、上下文无关文法,记为CFG。2型文法相应的语言称为2型语言或上下文无关语言,它的识别系统是下推自动机。,4、3型文法与3型语言(对应有限自动机)文法G的每个产生式具有下列形式:Aa或AaB 其中,A、BVN,aVT*,则文法G称为3型文法、正规文法或右线性文法,记为RG。3型文法相应的语言为3型语言或正规语言,它的识别系统是有限自动机。3型文法还可以呈左线性形式:Aa或ABa,例:1型(上下文有关)文法 文法GS:SCDAbbA CaCABaaB CbCBBbbB ADaD C BDbD D AabD,例:2型(上下文无关)文法 文法GS:SAB ABS|0 BSA|1,例:3型(正规)文法,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 前后文 无关 文法 语言 姚版
链接地址:https://www.31ppt.com/p-6245182.html