第三章文法和语言.ppt

1,第三章文法和语言,为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）形式工具-“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述,2,本章内容,文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法的句型分析有关文法实用中的一些说明,3,3.1 文法的直观概念,例：语言规则:=:=我|他:=:=是:=学生|汽车句子：他是汽车、我是学生非句子：你是学生,4,3.2 符号和符号串,字母表：元素的非空有穷集合。元素又称为符号。符号串：由字母表中的符号组成的任何有穷序列。空串用表示。符号串的连接：设x和y是符号串，它们的连接：xy。注意：x=x=x符号串的方幂：设x是符号串，x的方幂xn是把x自身连接n次得到的符号串。x0=x1=x,5,符号串集合：若集合A上的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。符号串集合的乘积：设A和B是符号串集合，则:AB=xy|xA且yB 注意：A=A=A集合闭包*：上所有有穷长的串的集合。*=012 n 0=集合正闭包+：+=12 n,6,3.3 文法和语言的形式定义,如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：生成方式（文法）：语言中的每个句子可以用严格 定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。,7,文法即是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造,规则（重写规则、产生式、生成式）：形如 或:=的（，）有序对。称为规则左部 称为规则右部,8,文法定义,文法G定义为四元组(VN，VT，P，S)其中VN:非终结符号(或语法实体，或变量)集；VT:终结符号集；P:规则的集合；VN，VT和P是 非空有穷集。S:称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现。VN和VT不含公共的元素，即VN VT=用V表示VN VT，称为文法G的字母表或字汇表 规则，也称重写规则、产生式或生成式，是形如或=的(，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称作规则的右部。,9,文法的定义,例 文法G=（VN，VT，P，S）VN=S,VT=0,1 P=S0S1,S01 S为开始符号,例 文法G=（VN，VT，P，S）VN=标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P=a z 0 9 S=,11,文法的写法 元符号:=|习惯 大写字母表示非终结符 小写字母表示终结符,(1)G：SaAb Aab AaAb A,(2)GS：Aab AaAb A SaSb(3)GS:Aab|aAb|SaSb,12,推导的定义,直接推导“”是文法G的产生式，若有v,w满足：v=,w=,其中V*,V*则称v直接推导到w,记作 v w 也称w直接归约到v例：G：S0S1，S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1,13,推导,.(.).()VAR;BEGIN READ()END.VAR A;BEGIN READ()END.(A)VAR A;BEGIN READ()END.VAR A;BEGIN READ(A)END.(A),14,推导的定义,若存在v=w0 w1.wn=w,(n0)则记为v=+w，称作v推导出w，或w归约到v 若有v=+w 或 v=w，则记为v=*w,15,例：G：S0S1，S010S1 00S1100S11 000S111000S111 00001111 S 0S1 00S11 000S111 00001111 S=+00001111 S=*S 00S11=*00S11,16,句型、句子的定义,句型有文法G，若S=*x，则称x是文法G的句型。句子有文法G，若S=*x，且xVT*，则称x是文法G的句子。例：G：S0S1，S01S 0S1 00S11 000S111 00001111G的句型S,0S1,00S11,000S111,00001111G的句子00001111,01,17,句型、句子,例：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，+，*，(和)构成的算术表达式,18,(文法生成的)语言的定义,由文法G生成的语言记为L(G),它是文法G的一切句子的集合:L(G)=x|S=*x，其中S为文法的开始符号，且x VT*例：G：S0S1，S01 L(G)=0n1n|n1,例 文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee L（G）=anbnen|n1 G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成,20,文法的等价,若L（G1）=L（G2），则称文法G1和G2是等价的。如文法G1A：ADB 与G2S：S0S1 等价 ADE S01 EAB D0 B1,21,3.4 文法的类型,通过对产生式施加不同的限制，Chomsky将文法分为四种类型：0型文法：对任一产生式，都有(VNVT)+，(VNVT)*1型文法：对任一产生式，都有|，仅仅 S除外2型文法：对任一产生式，都有VN 3型文法：任一产生式的形式都为AaB或Aa，其中AVN，BVN，aVT*,22,文法的类型,例：1型（上下文有关）文法 文法GS：SCDAbbA CaCABaaB CbCBBbbBADaD CaBDbD DbAabD,23,文法的类型,例：2型（上下文无关）文法 文法GS：SABABS|0BSA|1,24,3型文法,GS：S0A|1B|0A0A|1B|0SB1B|1|0,GI：I lTI lT lTT dTT lT d,25,文法的类型,0型文法,四类文法之间的逐级“包含”关系,3型文法,26,文法和语言,0型文法产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFG）产生的语言称为2型语言或上下文无关语言（CF L）3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）,27,文法和语言,四种文法之间的关系 是将产生式做进一步限制而定义的。语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。,28,根据形式语言理论,文法和识别系统间有这样的关系,0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的 1型文法（上下文有关文法）：产生式的形式为1A212，即只有A出现在1和2的上下文中时，才允许取代A。其识别系统是线性界限自动机。,29,带 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an,有限控制器,磁头,任何能用图灵机描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述,30,2型文法（上下文无关文法CFG）：产生式的形式为A，取代A时与A的上下文无关。其识别系统是不确定的下推自动机。3型文法（正规文法RG）：产生的语言是有穷自动机（FA）所接受的集合,31,3.5 上下文无关文法及其语法树,上下文无关文法有足够的能力描述程序设计语言的语法结构语法树-句型推导的直观表示,32,语法树-句型推导的直观表示(句型、推导),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 EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*aEE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a,33,规范推导 规范句型,最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型,34,语法树,设G=(VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）：1.每个结点都有一个标记，此标记是V的一个符号2.根的标记是S3.若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN4.如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式语法树的结果：从左到右读出叶子的标记而构成的行谓之句型,35,上下文无关文法的语法树,句型aabbaa的可能推导序列和语法树,例:GS:SaASASbAASSSaAba,S a A S S b A a a b a,SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa,36,语法树-句型推导的直观表示,给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树)定理：G为上下文无关文法，对于，有S=*，当且仅当文法G有以为结果的一棵语法树(推导树),37,一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?,38,例：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,39,二义文法,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的 判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件,40,文法的二义性和语言的二义性,文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是二义的，但是却有L(G)=L(G)，也就是说，这两个文法所产生的语言是相同的。二义文法改造为无二义文法GE:E i GE：E T|E+T E E+E T F|T*F E E*E F（E）|i E(E)规定算符优先性和结合性 如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。,41,3.6（上下文无关文法）句型的分析,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。,42,句型的分析算法分类,分析算法可分为：自上而下分析法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。,43,两种方法反映了两种语法树的构造过程。,自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树,44,自上而下的语法分析,例：文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子,SSScAdcAd a b推导过程：S cAd cAd cabd,45,自下而上的语法分析,例：文法G：S cAd A ab A a识别输入串w=cabd是否该文法的句子,SAA c a b d c a b d c a b d 规约过程构造的推导：cAd cabd S cAd,46,自上而下的语法分析(1)S cAd(2)A ab(3)A a 识别输入串w=cad是否为该文法的句子,若S cAd 后选择(2)扩展A，S cAd cabd那将会？w的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配？宣告分析失败（其意味着，识别程序不能为串cad构造语法树，即cad不是句子）-显然是错误的结论。导致失败的原因是在分析中对A的选择不是正确的。,S c A d a b 这时应该回朔，把A为根的子树剪掉，扫描过的输入串中的a吐出来,再试探用产生式（3）,47,(1)S cAd(2)A ab(3)A a识别输入串w=cabd是否为该文法的句子自下而上的语法分析,对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么在c A b d中无法找到一个可归约串了，最终就达不到归约到S的结果，因而也无从知道cabd是一个句子,c a b d c A b d a,48,句型分析的有关问题,1）在自上而下的分析方法中如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？2）在自下而上的分析方法中如何识别可归约的串？在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”,49,短语定义：,语法分析基础,50,举例：短语,文法 G（S）:（1）S AB（2）A aA（3）A（4）B b（5）B bB,对于右边的文法G(S),句子 aaab 的短语有：aaab；a：aaab；aa：aaab；aaa：aaab；aaab：aaab b：aaab 句型aaAb的短语有：aA：aaAb；aaA：aaAb；aaAb：b：aaAb,语法分析基础,51,直接短语,语法分析基础,52,举例：直接短语,文法 G（S）:（1）S AB（2）A aA（3）A（4）B b（5）B bB,对于右边的文法G(S)句子 aaab 的直接短语有：aaab；b：aaab 句型aaAb的直接短语有：aA：aaAb；b：aaAb,语法分析基础,53,句柄定义：,rm,对于文法 G=(VN,VT,P,S),以及,(VNVT)*,wVT*若 S Aw 且 A，且在最左，则称 是句型w 相对于非终结符 A 的句炳,语法分析基础,54,举例：句柄,文法 G（S）:（1）S AB（2）A aA（3）A（4）B b（5）B bB,对于右边的文法G(S),句子 aaab 的直接短语有：aaab；b：aaab aaab 的句柄：右句型aaAb的直接短语有：aA：aaAb；b：aaAb aaAb 的句柄：aA,语法分析基础,55,3.7 文法实用中的一些说明,限制化简文法文法中不含有有害规则和多余规则有害规则：形如UU的产生式。会引起文法的二义性多余规则：指文法中任何句子的推导都不会用到的规则 文法中不含有不可到达和不可终止的非终结符1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。2）文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。,56,对于文法GS，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件：1.A必须在某句型中出现 即有S=*A，其中，属于V*2.必须能够从A推出终结符号串t来 即A=*t，其中tVT*,57,化简文法,例：GS：1)SBe 2)BCe D为不可到达 3)BAf C为不可终止 4)AAe 5)Ae 6)CCf 7)Df 产生式 2），6），7）为多余规则应去掉。,58,上下文无关文法中的规则,上下文无关文法中某些规则可具有形式A，称这种规则为规则因为规则会使得有关文法的一些讨论和证明变得复杂,有时会限制这种规则的出现两种定义的唯一差别是句子在不在语言中文法构思的启示是要找出语言的有穷描述，而如果语言L有一个有穷的描述，则L1=L也同样有一个有穷的描述，并且可以证明，若L是上下文有关语言、上下文无关语言或正规语言，则L和L-分别是上下文有关语言、上下文无关语言和正规语言。,