第三章文法和语言.ppt

1,第三章文法和语言,本章目的为语言的语法描述寻求工具,以便：对源程序给出精确无二义的语法描述。（严谨、简洁、易读）根据语言文法的特点来指导语法分析的过程从描述语言的文法可以自动构造出可用的分析程序制导语义翻译,2,文法和语言,预备知识文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法的句型分析有关文法实用中的一些说明有关文法的一些关系,3,预备知识-语言概述,语言是由句子组成的集合，是由一组记号所构成的集合。汉语-所有符合汉语语法的句子的全体英语-所有符合英语语法的句子的全体程序设计语言-所有该语言的程序的全体 每个句子构成的规律研究语言 每个句子的含义 每个句子和使用者的关系,4,预备知识-语言概述,研究程序设计语言 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系语言研究的三个方面 语法 Syntax 语义 Semantics 语用 Pragmatics,5,预备知识-语言概述,语法-表示构成语言句子的各个记号之间的组合规律语义-表示按照各种表示方法所表示的各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用-表示在各个记号所出现的行为中，它们的来源、使用和影响。,6,预备知识-语言概述,每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。,7,预备知识-形式语言,如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,8,预备知识-有关定义和记号,符号：可以相互区别的记号（元素）。字母表：符号（元素）的非空有穷集合。符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串(没有符号的符号串)是上的符号串 2.若x是上的符号串,a是的元素,则xa是上的符号串 3.y是上的符号串,当且仅当它可以由1和2导出。例如：=a,b,a,b,aa,ab,aabba都是上的符号串,9,预备知识-有关定义和记号,符号串s的前缀：移走符号串s尾部的零个或多于零个符号得到的符号串.如：b是符号串banana的一个前缀.符号串s的后缀：删去符号串s头部的零个或多于零个符号得到的符号串.如:nana是符号串banana的一个后缀.符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串.如:ana是符号串banana的一个子串.,10,对于每个符号串s，s和两者都是符号串s的前缀，后缀和子串。符号串s的真前缀，真后缀，真子串：任何非空符号串 x,相应地，是s的前缀，后缀或子串，并且 s x 符号串的运算符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。的长度为0连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy 如 x=ab,y=cd 则 xy=abcd 有a=a 方幂：符号串自身连接n次得到的符号串 an 定义为 aaaa n个a a1=a,a2=aa则a0=,11,符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为 AB=xy|xA且yB 若 集合A=ab,cde B=0,1 则 AB=ab1,ab0,cde0,cde1使用*表示上的一切符号串（包括）组成的集合。*称为的闭包。上的除外的所有符号串组成的集合记为+。+称为的正闭包。,12,例：=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,13,语言：字母表上的一个语言是上的一些符号串的集合(上的每个语言是*的一个子集)。例如：=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 为字母表上的一个语言。是一个语言。即 是一个语言。,14,语言上的运算,设L是（上的）一个语言,M是（上的）一个语言,语言L和M的并，交，差，补是一个语言。如语言L和M的并为 LM，是一个语言:w|w is in L or is in M 如：L1=a,b,y,z M1=1,28,9 L1M1=a,b,y,z，1,28,9 语言L和M的连接是一个语言，记为 LM LM=st|sL且 tM 如：L1M1=a1,b1,y1,z1,a2,b2a9z9 有L=L=L。L的n次连接Ln=LL.L,15,语言上的运算,语言L的 闭包记为 L*，L*=L0 L1 L2.L0=，Ln=L Ln-1=Ln-1 L,n1语言L的正 闭包记为 L+，L+=L1 L2 L3.L+=LL*=L*L L*=L+如：L1=a,b,y,z M1=1,28,9（L1M1）=a,b,y,z，1,28,9（L1M1）*=a,b,y,z，1,28,9，aa,1a,xyz,6789st.L1（L1M1）*=所有字母打头的字母和数字符号串,16,语言的描述,如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要麽能停止并回答“不是”，（要麽永远继续下去。）,17,文法 数学系统,一个形式数学系统可由下列基本成分来刻画：一组基本符号，一组形成规则，一组公理，一组推理规则。,18,文法和语言的形式定义,文法的定义推导的定义句型、句子、语言的定义,19,文法的定义,文法G定义为四元组（VN，VT，P，S）VN：非终结符集VT：终结符集P：产生式（规则）集合S：开始符号VNVT=，SVNV=VNVT，称为文法G的文法符号集合,20,规则的定义,规则（重写规则、产生式或生成式），是形如或=的（，）有序对，且V+，V*。称为规则的左部(或生成式的左部)。称为规则的右部(或生成式的右部)。,21,文法的定义,例3.1 文法G=（VN，VT，P，S）VN=S,VT=0,1 P=S0S1,S01 S为开始符号,22,文法的定义,习惯上只将产生式写出。并有如下约定：第一条产生式的左部是开始符号用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符G可写成GS，S是开始符号G：SaAb Aab AaAb A GS：Aab AaAb A SaSb 缩写形式 GS：Aab|aAb|SaSb注意：元符号和源符号,例3.2 文法G=（VN，VT，P，S）VN=标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P=a,z 0,9 S=,24,推导的定义,直接推导“”是文法G的产生式，若有v,w满足：v=,w=,其中V*,V*则称v直接推导到w,记作 v w 或w直接归约到v例：G：S0S1，S01 S 0S1 00S11 000S111 00001111.VAR;BEGIN READ()END.VAR A;BEGIN READ(A)END.,25,推导的定义,若存在v w0 w1.wn=w,(n0)则称v w，v推导出w，或w归约到v若有v w，或v=w，则记为v w,26,文法的句型、句子的定义,句型有文法G，若S x，则称x是文法G的句型。句子有文法G，若S x，且xVT*，则称x是文法G的句子。例：G：S0S1，S01S 0S1 00S11 000S111 00001111,27,例：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，+，*，(和)构成的算术表达式,28,文法，语言的定义,由文法G生成的语言记为L(G),它是文法G的一切句子的集合:L(G)=x|S x，其中S为文法的开始符号，且x VT*例：G：S0S1，S01L(G)=0n1n|n1,例3.3 文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee L（G）=anbnen|n1,30,S a S BE(SaSBE)a aBEBE(SaBE)aabEBE(aBab)aabBEE(EBBE)aabbEE（bBbb)aabbeE（bEbe)aabbee（eEee)G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成,已知语言描述，写出文法例：若语言由0、1符号串组成，串中0和1的个数相同，构造其文法。A 0B|1CB 1|1A|0BBC 0|0A|1CC已知文法，写出语言描述例：GE：EE+T|T TT*F|F F(E)|a,32,语法 Syntax 语义 Semantics,偶正整数的集合0,2,4,2n,dd.0(2，4，6，8),33,文法的等价,若L（G1）=L（G2），则称文法G1和G2是等价的。如文法G1A：A0R 与G2S：S0S1 等价 A01 S01 RA1,34,文法的类型,通过对产生式施加不同的限制，Chomsky将文法分为四种类型：0型文法：对任一产生式，都有(VNVT)+，(VNVT)*1型文法：对任一产生式，都有|，仅仅 S除外2型文法：对任一产生式，都有VN，(VNVT)*3型文法：任一产生式的形式都为AaB或Aa，其中AVN，BVN，aVT,35,文法的类型,例：1型（上下文有关）文法 文法GS：SaSBESaBEEBBEaBabbBbbbEbeeEee,36,文法的类型,例：1型（上下文有关）文法 文法GS：SCDAbbA CaCABaaB CbCBBbbBADaD CBDbD DAabDL(G)=ww|wa,b*,37,文法的类型,例：2型（上下文无关）文法 文法GS：SaB|bAAa|aS|bAABb|bS|aBB 文法GS：S0A|1B|0A0A|1B|0SB1B|1|0,38,文法的类型,例：定义标识符的3型（正规）文法 文法GI：I lTI lT lTT dTT lT d,39,文法和语言,0型文法产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFL）产生的语言称为2型语言或上下文无关语言（CF L）3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）,40,文法和语言,四种文法之间的关系 是将产生式做进一步限制而定义的。语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。,41,文法和识别系统,0型文法（短语文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的1型文法（上下文有关文法）：产生式的形式为1A212，即只有A出现在1和2的上下文中时，才允许取代A。其识别系统是线性界限自动机。,42,带 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an,有限控制器,磁头,图灵机,43,文法的类型,2型文法（上下文无关文法、CFG）：产生式的形式为A，取代A时与A的上下文无关。其识别系统是不确定的下推自动机。3型文法（正规文法、右线性文法）：产生的语言是有穷自动机（FA）所接受的集合,44,上下文无关文法及其语法树,上下文无关文法有足够的能力描述现今程序设计语言的语法结构算术表达式语句赋值语句条件语句读语句,45,算术表达式上下文无关文法表示,文法G=(E,+,*,I,(,),P,E P:E iE E+EE E*EE(E),46,条件语句上下文无关文法表示,ifthen|ifthenelse,47,上下文无关文法的语法树,用于描述上下文无关文法的句型推导的直观方法,例:GS:SaASASbAASSSaAba,S a A S S b A a a b a,句型aabbaa的语法树（推导树）,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。,48,上下文无关文法的语法树,给定文法G，对于G的任何句型都能构造与之关联的语法树（推导树）。这棵树满足下列4个条件：1、每个结点都有一个V中的符号作标记2、根的标记是开始符号S3、若一结点n至少有一个它自己除外的子孙，并且n有标记A，则AVN4、如果结点n的直接子孙，从左到右的次序是结点n1,n2,nk，其标记分别为A1,A2,Ak，那么AA1A2,Ak一定是P中的一个产生式,49,上下文无关文法的语法树,定理：G为上下文无关文法，对于，有S，当且仅当文法G有以为结果的一棵推导树。,50,上下文无关文法的语法树,推导过程中施用产生式的顺序,例:GS:SaASASbAASSSaAba,S a A S S b A a a b a,SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa,51,最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型,52,问题：一个句型是否对应唯一的一棵语法树？,53,例：GE:E iE E+EE E*EE(E),E E+E E*E i i i,E E*E i E+E i i,句型 i*i+i 的两个不同的最左推导：推导1：E E+E E*E+E i*E+E i*i+E i*i+i推导2：E E*E i*E i*E+E i*i+E i*i+i,54,二义文法,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的。,55,二义文法,判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的。但可以为无二义性寻找一组充分条件。二义文法改造为无二义文法GE:E i GE：E T|E+T E E+E T F|T*F E E*E F（E）|i E(E)规定优先顺序和结合律,56,句型的分析,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。,57,句型的分析,分析算法可分为：自上而下分析法：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。两种方法反映了两种不同的语法树的构造过程,58,自上而下的语法分析,例：文法G：S cAd A ab A a识别输入串w=cabd是否该文法的句子,SSScAdcAd a b推导过程：S cAd cabd,59,自下而上的语法分析,例：文法G：S cAd A ab A a识别输入串w=cabd是否该文法的句子,SAA c a b d c a b d c a b d 规约过程：S cAd cabd,60,句型分析的有关问题,1）如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是V，且有n条规则：VA1|A2|An，那么如何确定用哪个右部去替代V？2）如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”,61,句型分析,短语、直接短语、句柄的定义：文法GS，S A且A b则称b是句型b相对于非终结符A的短语。若有A b则称b是句型b相对于该规则A b的直接短语。一个句型的最左直接短语称为该句型的句柄。,62,句型分析,E F T T F F i1*i2+i3短语：直接短语：句柄：,GE：EE+T|T TT*F|F F(E)|i句型：i*i+i,63,有关文法实用中的一些说明,有关文法的实用限制上下文无关文法中的规则,64,有关文法的实用限制,文法中不得含有有害规则和多余规则有害规则：形如UU的产生式。会引起文法的二义性多余规则：指文法中任何句子的推导都不会用到的规则1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达2）文法中某些非终结符，由它不能推出终结符号串来，称为不可终止的,65,有关文法的实用限制,对于文法GS，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件：1）A必须在某句型中出现。2）必须能从A推出终结符号串t来。即1）文法GS，对 某两个符号串和：S A 2）A t,tVT,66,化简文法,例：GS 1)SBe SBe2)BCe BAf3)BAf AAe 4)AAe Ae5)Ae 6)CCf7)Df,67,上下文无关文法中的规则,具有形式A的规则称为规则，其中AVN某些著作和讲义中限制这种规则的出现。因为规则会使有关文法的一些讨论和证明变得复杂两种定义的唯一差别是句子在不在语言中。,68,上下文无关文法中的规则,如果语言L有一个有穷的描述，则L也同样有一个有穷描述。并且可以证明，若L是上下文有关语言、上下文无关语言或正规语言，则L和L-分别是上下文有关语言、上下文无关语言和正规语言,69,上下文无关文法中的规则,定理3.1 文法G，任一P中的产生式A，都有AVN，(VN VT)*,(即可能为)，则L(G)也能这样一种文法产生，任一产生式A，只有如下两种形式：AVN，(VN VT)+,(即)或者 S且 S不出现在任何产生式右边,70,上下文无关文法中的规则,定理3.2G是上下文有关文法，则存在另一个上下文有关文法G1，L(G)=L(G1)，且G1的开始符号不出现在G1的任何产生式的右边。若G为上下文无关文法或正规文法，类似结论成立。,71,有关文法的一些关系,一般来说，一个集合上的（二目）关系就是某一性质，此性质对集合中的任意两个有序符号来说，或者满足，或者不满足。所定义的符号和 是符号串之间的两个关系。我们习惯采用中缀表示法表示关系，即如果在集合中的两个元素c和d之间满足某一关系，我们就记作cRd。,72,R+，R*,集合A上的一关系R,a,b,c是A的元素。若 cRc,称R为自反的.若由aRb能得到 bRa 则称R为对称的。若由aRb和 bRc能得到 aRc 则称R为传递的。给定任一关系R，我们定义一个新的关系 R+，称为R的传递闭包。aR1b aRb aR+b c:aRc且 cRi-1b,i1 R*，称为R的自反传递闭包,73,FIRST集和FOLLOW集,设G=(VN,VT,S,P)是上下文无关文法FIRST（）=a|a,aVT,V*若 则规定FRIST（）。FOLLOW（A）=aS A 且a FRIST（），V*，V+若S u A,且，则#FOLLOW(A)。,74,1.若XV,则FIRST(X)=X.2.若XVN,且有产生式Xa，则把a加入到FIRST(X)中;若X也是一条产生式,则把也加到FIRST(X)中.3.若XY是一个产生式且YVN,则把FIRST(Y)中的所有非元素都加到FIRST(X)中;若X Y1Y2YK 是一个产生式,Y1,Y2,Y(i-1)都是非终结符,而且对于任何j,1j i-1,FIRST(Yj)都含有(即Y1.Y(i-1),则把FIRST(Yj)中的所有非元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj,j=1,2,K)均含有,则把加到FRIST(X)中.,75,FOLLOW,1.对于文法的开始符号S,置#于FOLLOW(S)中;2.若 B 是一个产生式,则把 FIRST()加至FOLLOW(B)中;3.若 B是一个产生式,或B是 一个产生式而(即FIRST()），则把FOLLOW（A），加至FOLLOW（B）中,76,作业,3。8练习 题5，8，9，14，16验证L(G)是匹配的括号串 G:S(S)S|,