编译原理 文法和语言.ppt

1,第三章文法和语言,语言是一个记号系统，完整的定义包括语法和语义两方面。语法是一组规则，用它可以形成和产生一个合适的程序。文法就是阐明语法的一个重要的形式工具。语义包括静态语义和动态语义，阐明语义要比语法困难的多。本章主要讨论文法和语言的概念，上下文无关文法及其句型的分析。,2,本章内容,3.1 文法的直观概念3.2 符号和符号串3.3 文法和语言的形式定义3.4 文法的类型3.5 上下文无关文法及其语法树3.6 句型的分析3.7 有关文法实用中的一些说明3.8 典型例题及解答,3,3.1 文法的直观概念,如何来描述一种语言？如果语言是有穷的(只含有有穷多个句子)，可以将句子逐一列出来表示；如果语言是无穷的，语言的有穷表示有两个途经:生成方式(文法):语言中的每个句子可以用严格定义的规则来构造。识别方式(自动机):用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。参见课本句子组成的实例。,4,3.2 符号和符号串,1、字母表,字母表是符号的非空有穷集合。任何程序语言都有自己的字母表，例如:1.计算机语言：由符号“0”和“1”组成的字母表,=0，1 2.ASCII字符集；3.Pascal字母表为：=AZ,az,09,+,-,*,/,:,;，.，,(,),5,3.2 符号和符号串,2、符号串,一.符号串的定义(1)是上的一个符号串。(2)若x是上的符号串，而a是的元素,则xa是 上的符号串。(3)y是上的符号串,当且仅当它由(1)和(2)导出。由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作字。,6,3.2 符号和符号串,二 术语 设s是符号串前缀:移走s的尾部的零个或多于零个符号后缀:删去s的头部的零个或多于零个符号子串:从s中删去一个前缀和一个后缀子序列:从s中删去零个或多于零个符号(这些符号不要求是连续的）逆转:将s中的符号按相反次序写出而得到的符号串。长度:是该符号串中的符号的数目。例|aab|=3,|=0。,7,例：符号串s=banana前缀：,b,ba,ban,bana,banan,banana后缀：banana,anana,nana,ana,na,a,子串:banana,anana,banan,anan,真前缀，真后缀，真子串:xsx 子序列:baa(这些符号不要求是连续的）逆转：ananab长度：banana=6,3.2 符号和符号串,8,三、符号串的运算1.连接：设x和y是符号串，它们的连接 xy是把y的符号写在x的符号之后得到的符号串。例如，x=ba,y=nana,xy=banana.2.方幂：x0=;x1=x;x2=xx;xn=xn-1x;例:x=ba 则 x1=ba;x2=baba;x3=bababa;,3.2 符号和符号串,9,四.符号串集合(语言）的运算 设L和M是两个符号串集合，则 1.合并：LMs|sL or sM 2.连接：LM st|sL and tM 3.方幂：L0=，L1L，L2LL,.,LnLn-1L 4.语言L的闭包，记作L*，L*Li(i=0)=L0L1L2L3 5语言L的正闭包，记作L+（L+L L*）L+Li(i=1)=L1L2L3L4,3.2 符号和符号串,10,例如：L=AZ,az D=09 1LD=AZ,az,09 2LD是由所有用一个字母后跟一个数字组成的符号串所构成的集合。3L4是由所有的四个字母的符号串构的集合。4L（LD)*是由所有的字母打头的字母和数字组成的符号串所构成的集合.5D+是由所有的长度大于等于1的数字串所构成的集合.,3.2 符号和符号串,11,文法的定义推导的概念句型、句子和语言的定义,3.3 文法和语言的形式定义,12,文法定义,文法G 定义为四元组(VN，VT，P，S)，其中VN:非终结符号集；VT:终结符号集；P:规则的集合；并且VN，VT和P是非空有穷集。S:称作开始符(识别符)，是一个非终结符，它至少要在一条产生式中作为左部出现。注：VN和VT不含公共的元素，即VN VT=，用V表示VN VT，称为文法G的字母表 规则(重写规则、产生式或生成式)，是形如的(,)有序对,其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称作规则的右部。,13,文法的定义,例:文法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=,15,元符号:|一般不用将文法G的四元组显式的写出来，只写出产生式即可，并约定第一条产生式的左部为识别符。习惯上大写字母表示非终结符，小写字母表示终结符，有时也将G写为GS,(1)G：SaAb Aab AaAb A,(2)GS：Aab AaAb A SaSb(3)GS:Aab|aAb|SaSb,文法的写法,16,推导的定义,直接推导“”是文法G的产生式,若有v,w满足v=,w=,其中V*,V*,则称v直接推导到w,记作 v w 也称w直接归约到v例：G：S0S1，S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1,17,推导的定义,例：.(.).()VAR;BEGIN READ()END.VAR A;BEGIN READ()END.(A)VAR A;BEGIN READ()END.VAR A;BEGIN READ(A)END.(A),18,推导的定义,若存在v=w0 w1.wn=w,(n0)则记为v+w，称作v推导出w，或w归约到v 若有v=+w 或 v=w，则记为v=*w,19,例：G：S0S1，S010S1 00S1100S11 000S111000S111 00001111 S 0S1 00S11 000S111 00001111 S=+00001111 S=*S 00S11=*00S11,20,句型、句子的定义,句型有文法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,21,句型、句子,例：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，+，*，(和)构成的算术表达式,22,(文法生成的)语言的定义,由文法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生成 分析参见课本P37.,24,文法的等价,若L(G1)=L(G2)，则称文法G1和G2是等价的。例：文法G1A：A0R 与 G2S：S0S1 等价 A01 S01 RA1,25,3.4 文法的类型,通过对产生式施加不同的限制，文法可分为以下四类：0型文法：对任一产生式，都有(VNVT)+，(VNVT)*。0型文法的能力相当于图灵机，可以表征任何递归可枚举集，且任何0型语言都是递归可枚举的。0型文法描述的语言为0型语言，用L0表示。例如：aSbcAd,26,3.4 文法的类型,1型文法：对任一产生式，都有|，仅仅 S除外。1型文法又称作上下文有关文法（context-sensitive)：其产生式的形式为1A212，即只有A出现在1和2的上下文中时，才允许取代A。其识别系统是线性界限自动机。该文法描述的语言为1型语言或上下文有关语言,用L1表示。例如：aUbaABBaab,27,3.4 文法的类型,2型文法：对任一产生式,都有VN,(VNVT)*2型文法又称作上下文无关文法（context-free)：该文法相当于对1型文法中的规则形式加以限制，即要求1和2必须为空。2型文法描述的语言为2型语言或上下文无关语言，用L2表示。其识别系统是不确定的下推自动机。,28,3.4 文法的类型,例：2型（上下文无关）文法 文法GS：SABABS|0BSA|1,29,3型文法：任一产生式的形式都为AaB或Aa，其中AVN，BVN，aVT*3型文法又叫正规文法，产生的语言为3型语言（正规语言），是有穷自动机所接受的集合。高级程序设计语言的单词符号，如标识符、无符号整数等都是采用3型文法来描述的。,3.4 文法的类型,30,3.4 文法的类型,GS：S0A|1B|0A0A|1B|0SB1B|1|0,GI：I lTI lT lTT dTT lT d,例：3型文法,31,3.4 文法的类型,0型文法,四类文法之间的逐级“包含”关系,3型文法,32,3.5 上下文无关文法及其语法树,上下文无关文法有足够的能力描述程序设计语言的语法结构实例参见课本P39-40 例3.6（描述表达式及各种语句）语法树：是描述上下文无关文法句型推导的直观工具。,33,语法树的定义 设G=(VN,VT,P,S)为一上下文无关文法，若一棵树满足下列4个条件，则此树为G的语法树(推导树)(派生树）1.每个结点都有一个标记，此标记是V的一个符号2.根的标记是S3.若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN4.如果结点n的直接子孙从左到右依次为n1，n2，nk，并且标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式,3.5 上下文无关文法及其语法树,34,语法树的结果：从左到右读出叶子的标记而构成的符号串即为语法树的结果,3.5 上下文无关文法及其语法树,构造句型aabbaa的语法树,S a A S S b A a a b a,例:GS:1)SaAS 2)ASbA 3)ASS 4)Sa 5)Aba,35,句型aabbaa的可能推导序列,例:GS:1)SaAS 2)ASbA 3)ASS 4)Sa 5)Aba,SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa,3.5 上下文无关文法及其语法树,36,规范推导、规范句型：最左（最右）推导：在推导的任何一步，其中，是句型，都是对中的最左（右）非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树)定理：G为上下文无关文法，对于，有S=*，当且仅当文法G有以为结果的一棵语法树(推导树),3.5 上下文无关文法及其语法树,37,一棵语法树表示了一个句型的种种可能的(但未必是所有的)推导过程，包括最左(最右)推导。一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?,3.5 上下文无关文法及其语法树,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,3.5 上下文无关文法及其语法树,39,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件,文法的二义性和语言的二义性,3.5 上下文无关文法及其语法树,40,文法的二义性和语言的二义性是不同的概念。因为可能有两个不同的文法G和G,其中G是二义的,但有L(G)=L(G)，也就是说，这两个文法所产生的语言是相同的。如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。,文法的二义性和语言的二义性,3.5 上下文无关文法及其语法树,41,GE:E i E E+E E E*E E(E),文法的二义性和语言的二义性,3.5 上下文无关文法及其语法树,二义文法改造为无二义文法,GE：E T|E+T T F|T*F F（E）|i,规定算符优先性和结合性,42,3.6（上下文无关文法）句型的分析,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。(以后介绍的算法均属此类）,43,从左到右的句型分析算法分类：自上而下分析法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。,3.6 句型的分析,44,从语法树的构造过程来理解两种句型分析方法1.自上而下方法从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串2.自下而上方法从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树,3.6 句型的分析,45,1.自上而下的语法分析,例：文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子,SSScAdcAd a b推导过程：S cAd cAd cabd,3.6 句型的分析,46,例：文法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,1.自下而上的语法分析,3.6 句型的分析,47,自上而下的语法分析(1)S cAd(2)A ab(3)A a 识别输入串w=cad是否为该文法的句子,串的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配。宣告分析失败(意味着，识别程序不能为串cad构造语法树，即cad不是句子):显然是错误的结论。导致失败的原因是在分析中对A的选择不是正确的。,S c A d a b,这时应回溯，把A为根的子树剪掉，扫描过的输入串中的a吐出来,再试探用产生式（3）,若S cAd 后选择(2)扩展A，S cAd cabd 那将会？,48,自下而上的语法分析(1)S cAd(2)A ab(3)A a识别输入串w=cabd是否为该文法的句子,对串cabd的分析中，如果不用产生式(2的ab，而是用产生式(3)将a归约到了A，则在cAbd 中无法找到一个可归约串了，最终就达不到归约到S的结果，因而也无从知道cabd是一个句子,c a b d c A b d a,49,句型分析的有关问题,1）在自上而下的分析方法中选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？（回溯）2）在自下而上的分析方法中如何识别可归约的串？在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”。在规范归约中该可归约串称为句柄。,50,句柄及其相关概念,1.短语：xuy是文法GS的一句型,如果有 S=*xUy 且U=+u,其中UVN,uV+，则称u是句型xuy相对于非终结符号U的短语。短语是在句型的推导过程中能由某个非终结符号推导出的子串。2.直接短语（简单短语）：若有 S=*xUy 且U=u，则称u是句型xuy相对于非终结符号U的直接短语。直接短语则是能由某个非终结符号直接推导出的子串。3.句柄：任一句型的最左直接短语称为该句型句柄。,51,句柄及其相关概念,例:写出GE中句型 i*i+i的所有短语、简单短语和句柄。GE:E T|E+T T F|T*F F（E）|i,解：首先构造出句型 i1*i2+i3对应的语法树因为F=i，所以i1,i2,i3分别是句型i1*i2+i3相对于规则Fi的直接短语，而句柄是最左侧的直接短语即i1。因为T=+i1,所以i1是句型i1*i2+i3相对于T的短语，i3也是同样情况。,52,句柄及其相关概念,注意：并不是句型中的任意子序列都可构成短语。如上例中的 i2+i3.,因为T=+i1*i2，所以i1*i2是句型i1*i2+i3相对于T的短语。因为E=+i1*i2，所以i1*i2是句型i1*i2+i3相对于E的短语。因为E=+i1*i2+i3，所以i1*i2+i3是句型i1*i2+i3相对于E的短语。综上：i1，i2，i3，i1*i2，i1*i2+i3均是句型i1*i2+i3的短语，其中i1，i2，i3为直接短语，i1为句柄。,53,直接短语：a2,b2a3,a4 短语：a2,b2a3,a4,a2b1b2a3,a1a2b1b2a3a4句柄：a2,给出句型aabbaa的所有短语、直接短语和句柄,S a1 A S S b1 A a4 a2 b2 a3,句柄及其相关概念,例:GS:1)SaAS 2)ASbA 3)ASS 4)Sa 5)Aba,54,3.7 有关文法实用中的一些说明,对文法进行限制（目的是化简文法）文法中不含有有害规则和多余规则有害规则：形如UU的产生式。会引起文法的二义性多余规则：指文法中任何句子的推导都不会用到的规则，它们以不可到达和不可终止两种情况出现 1)文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。2)文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。,55,对于文法GS，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件：1.A必须在某句型中出现 即有S=*A，其中，属于V*2.必须能够从A推出终结符号串t来 即A=*t，其中tVT*,3.7 有关文法实用中的一些说明,56,化简文法 例：GS：1)SBe 2)BCe 3)BAf 4)AAe 5)Ae 6)CCf 7)Df,3.7 有关文法实用中的一些说明,D为不可到达,C为不可终止,产生式 2）6）7）为多余规则应去掉。,57,对文法的扩充：上下文无关文法中的规则,本书所给上下文无关文法的定义中，某些规则可以具有形式A，称这种规则为规则。有些教材对此进行了限制，但这不牵扯到本质的问题。两种定义的唯一差别是句子在不在语言中 如果语言L有一个有穷的描述，则L1=L也同样有一个有穷的描述，并且可以证明，若L是上下文有关语言、上下文无关语言或正规语言，则L分别是上下文有关语言、上下文无关语言和正规语言。,3.7 有关文法实用中的一些说明,58,3.8 典型例题,例1：证明文法GE是二义的。P46例2：给出下述语言的上下文无关文法L1=anb2ncm|n,m=0L2=anbmc2m|n,m=0解：要产生形如anb2ncm的符号串，可分别产生形如 anb2n和cm的串，所以L1对应的文法为：SABA|aAbbB|cB,同理可得L1对应的文法为：SABA|aA B|bBcc,59,作业,课本 P48:1;2;3;5P48-49:6.(1)(3)(5);11;13,