编译方法马知行曹启君机械工业出版社编译原理演示文稿2.ppt

第二章 文法和语言 2.1 文法的基本概念 一个程序设计语言是一个记号系统，如自然语言一样，它的完整的定义应包括语法和语义两方面。所谓一个语言的语法其实是指一组规则，用它可以形成和产生一个合适的程序。目前在程序设计语言的识别中广泛使用的是上下文无关的文法。在这理主要介绍文法和语言的概念。 语言根据所含句子数量有限(穷)与否又可分为: 有限(穷)语言和无限(穷)语言。,例：设有文法： G: the big ate|caught mouse|cat,则： = =the= the big =the big cat =the big cat =the big cat ate=the big cat ate=the big cat ate the =the big cat ate the mouse,2.1.1 符号和符号串 定义 2.1 字母表是有穷非空集合。用或 V表示。 例：无符号二进制数的字母表为: =0，1 C语言的字母表为字母、数字和若干专用符号组成的符号集 定义 2.2 符号串是由字母表中的符号组成的有穷序列，又称字符串、串。 例：a,b,c,ba,bbac,caacb,···等都是字母表a,b,c上的符号串。,定义 2.3 不包含任何字符串的空符号串用表示 定义 2.4 符号串x的长度，即符号串x中的字符的个数用|x|表示(读作x的长度) 例：|abc|=3 |a|=1 |=0 定义 2.5 设非空符号串u=xvy,其中v,则称v为u的子串,若|u| |v|则称v为u的真子串,定义 2.6 如果z=xy是一个符号串，则x是z和头，而y是z的尾。如果x是非空的，那么y是固有尾；同样如果y非空，那么x是固有头。 例：设z=abc，那么z的头是,a，ab，abc。除abc外，其它都是固有头。z的尾是,c，bc，abc。z的固有尾是,c，bc,定义 2.7 设x、y 是同一字母表上的两个符号串，把符号串y写在符号串X的后面所得到的符号串，称为x、y的连接。记为xy 例：x=ab，y=wabu 则 z=xy=abywabu 显然：|x|+|y|=|z| x=x=x,定义 2.8 设x是符号串，把x自身连接n次得到符号串z,即z=xx···xx(n个x)，称为符号串x的方幂,记为z=xn 例：x0= x1=x x2=xx x3=xxx ··· 定义 2.9 符号串集合，若集合A中的一切元素都是其字母表上的符号串，则称A为该字母表上的符号串集合。 注意：、和（表示空集）的区别,定义 2.10 两个符号串集合A和B的乘积， AB定义为： AB=xy|xA且yB 例：设A=a,bc，B=b,c,da则集合 AB=ab,ac,ada,bcb,bcc,bcda。 注意：由于x=x=x 因此A=A=A ，但A=A= 则： A0= A1=A A2=AA An=An-1A=AAn-1（n0）,定义 2.11 A的闭包 A*=A0A1A2··· A的正闭包 A+= A1A2A3··· 显然A+=AA*=A*A A*=A0A+,由于一个字母表上的正闭包包含了该字母表中的符号所能组成的一切符号串，而语言是该字母表上的某些符号串的集合，因此，某个字母表上的语言是这个字母表上的正闭包的子集，而且通常是真子集。 例：若=0,1,则*=,0,1，00,01，10,11,000，001，010, ··· 例：令L=A,B,C,···,Z,a,b, ···,z,D=0,1, ···9 1.LD 2.LD 3.L 4. L(LD)* 5. D+ 6.D+L*则分别代表什么集合？ 1.字母或数字的集合 2.由一个字母开头后面跟一个数字的集合 3.由字母组成的集合 4.由字母开头后面是字母数字（可省略）的集合 5.数字串集合 6.数字串和字母串集合（包括）,：当对符号串z=xy的头感兴趣而对其余部分不感兴趣时，可以采用省略写法：z=x···；如果只是为了强调x在符号串z中的某处出现，则可表示为:z=···x···；如果只是为了强调x在符号串z约定中的末尾出现，则可表示为:z=···x；,2.1.2 文法和语言的形式定义 语言是字母表上的某些符号串集合，在这集合中的每个符号串都是按一定规则生成的。其规则最常用的是重写规则（又称产生式），它是形如或：=或（，）的有序对，（读作定义为或 由组成），其中称为规则的左部，称为规则的右部。,定义 2.12 文法G定义为四元组（Vn,Vt，P，S）。 其中: Vn为非终结符号（或语法实体，或变量）集； Vt为终结符号集； P为产生式（也称规则）的集合； S称作识别符号或开始符号。它是一个非终结符,至少要在一条规则中作为左部出现。 Vn，Vt和P是非空有穷集， 显然：Vn和Vt不含公共的元素，即VnVt = 定义 2.13 用V表示VnVt。V称为文法G的字汇表。,例:文法G=（Vn,Vt，P，S） 其中 : Vn=S, Vt=0，l, P=S 0 ，S1 ， S0 S ，S1 S , S=S。 该文法刻划的是无符号二进制整数。 上述文法可（通过约定）简单表示为： GS: S 0 S1 S0 S S1 S 进而可（通过引入“|” ）简单表示为:（巴科斯范式 BNF） GS: S 0 |1 |0 S | 1 S,例:刻划整数的文法： G =（Vn, Vt，P，S） 其中: Vn=, Vt=+,-,0,1,2,3,4,5,6,7 ,8,9 P= + | | 0 |1 |2 | 3 |4 |5 |6 |7 |8 |9 S=,例:能被5整除的整数文法： G=（Vn, Vt，P，S） 其中: Vn=,， Vt=+,-,0,1,2,3,4,5,6,7,8,9 P= + | | 0 |1 |2 | 3 |4 |5 |6 |7 |8 |9 | 0 |5 S=,·约定： 1：用尖括号括起的是非终结符，不用尖括号括起来的是终结符号；或者用大写字母表示非终结符号，小写字母表示终结符号 2：可用GZ指出识别符号；如果文法G没有明确指出识别符号，将第一条产生式的左部的非终结符号称为识别符号 3：如果A1，A2，A3， A 4 ， ··Ak是所有以A为左部的产生式（称它们为A的产生式），可以写成A1|2|3|4···|k,称1,2,3,4···,k 为A的选择（或候选式）.,例:| +|- | 0|1|2|3|4|5|6|7|8|9 定义 2.14 设G是一文法，如果对于符号串2，,1， 1，2v*能写出1=1A2，2=12且A 是G中的一条规则，则说符号串1 直接推导到2 ，或说，2是1的直接推导(一步推导），或说，2归约到1，记作1=2,例:设有文法G: | +|- | 0|1|2|3|4|5|6|7|8|9 试推导出2012 = =2=20=201=2012,定义 2.15 若文法G存在直接推导的序列 V=0=1=2=3=4···=n=W(n0) 则称V推导出W， 或称W归约到V，记作V=+=W, 其中n为推导的步数，也称推导长度,称V +推导出W。 例：=+=2012 定义 2.16 如果对于符号串V和W有V=+=W或V=W 即(n0)则记作V=*=W，称V *推导出W. 例: 对文法G有: =*=2006 例: 对文法G有: =*=,定义2.17 设GS是一文法， 若V*且有S=*=，则称为文法GS的一个句型； 若Vt*且有S=+= ，则称为GS的一个句子。 可见句子是句型的特例 例: 设有文法G: | 0|1|2|3|4|5|6|7|8|9 显然0000、2012、1234、都是G文法的句型 ，其中0000、2012、1234是G的句子.而 3、 不是句型(因为它们不能从开始符号推导出),定义 2.18 文法G所产生的语言定义为： L(G)=|S=+=且Vt*。 定义 2.19 若L(G1)= L(G2），则称G1，G2是等价的 例：设 G1： | 0|1|2|3|4|5|6|7|8|9 设G2）： 0| 1| 2| 3| 4| 5| 6| 7| 8| 9 |0|1|2|3|4|5|6|7|8|9 则L（ G1）= L（ G2）,由此可以看出，语言是该文法描述的全部句子的集合。 换言之，一个语言是在某特定字母表上按一定的规则构成的符号串集合。,文法提供了三个要点。 1在语言的设计和编译器的编写方面，文法都提供了极大的优点. 2文法给出了精确的，也于理解的语言语法说明 设计得漂亮的文法，把结构加于程序设计语言，这些结构对把源程序翻译成真正的目标代码和错误诊断都是有用的。 3语言也是逐步完善的，需要补充新的结构和完成附加任务。如果存在以语法为基础的语言的实现，这些新结构的加入就更方便了。,语言的特征： 1一种语言需借助于另一种语言(元语言)来描述 2语法是以有穷的方式来描述潜在无穷句子集合的手段 3语法上的正确不能保证语义上的正确,2.1. 推导与递归 定义 2.20 如果每次推导最左非终结符称最左推导，记为=L= 定义 2.21 如果每次推导最右非终结符称最右推导，最右推导又称为规范推导，记为=R=，由最右推导得出的句型称为右句型又称规范句型,递归规则与递归文法 由于语言通常是无穷的而文法是有限的，用有限的文法定义无穷的语言就必须使用递归定义。 递归规则 若文法中存在规则 AA 这种左部和右部具有相同的非终结符号的规则称为直接递归规则或称递归规则。 若AA，即为左递归规则； 若AA，即为右递归规则； 若AA(、），即为自嵌套规则。 这种递归称为直接递归或规则递归,递归文法 有时文法中不含有直接的递归规则，但通过若干推导仍能得到递归，这种递归称为间接递归或文法递归. 含有递归的文法被称为递归文法。 如： AB BA 则A=B= A,2.1.4 文法的分类 形式语言自1956年乔姆斯基（Chomsky）进行描述以来，得到了很大的发展。乔姆斯基从理论上讨论了语言和文法，按照文法规则的不同定义形式进行分类，并且为每一语言构造象自动机一样的识别器。形式语言的理论形成和发展对计算机科学有着深刻的影响，特别是对程序设计语言的设计技术、编译实现都有重大影响。 乔姆斯基把文法分成四种类型，即0型、1型、2型和3型文法。 1. 设文法G=（Vn,Vt，P，S）如果P中的每条规则为如下形式：,uv 其中 u（VnVt ）+ 且至少含有一个非终结符， v（VnVt ）*，则 称G是 0型文法或短语文法。 任何0型语言都是递归可枚举的；反之，递旧可枚举集必定是一个0型语言。,2. 设文法G=（Vn,Vt，P，S），若P中的每条规则为如下形式: xUy xuy 其中 U Vn , u (VnVt ）+ x,y （VnVt ）* 则称G是1型文法或上下文有关文法。 意为非终结符U在x、y这样的上下文条件下，允许替换为u. 3. 设文法G= （Vn,Vt，P，S） 若P中的每条规则为如下形式: U u 其中 U Vn , u (VnVt ）* 则称G称为2型的或上下文无关文法。大部分高级语言文法近似于2型文法.,4. 设文法G= （Vn,Vt，P，S） 若P中的每条规则为如下式: UaB 或 Ua，其中U,B Vn a Vt 则称G为3型文法或正规文法或线性文法。与词法分析有关的文法属于3型文法 三型文法又分左线性和右线性的。 若P中的每条规则为如下式: UaB或Ua 称为右线性的 若P中的每条规则为如下式: UBa或Ua 称为左线性的。 0型文法、1型文法、2型文法、3型文法所描述(产生)的0型、1型、2型、3型语言可分别为图灵机(TM)、线性界限自动机(LBA)、下推自动机(PDA)、有限自动机(FA)所识别.,显然， 3型文法是2型文法的特例, 2型文法是1型文法的特例, 1型文法是0型文法的特例。 例1：写出语言L=aibjck | i,j,k1的2型文法 GS: SaS|aB BbB|bC CcC|c 例2：写出语言L=aibk | i,k1的2型文法 GS: SAB AaA|a BbB|b 例3：写出语言L=aibi | i1的2型文法 GS: SaSb|ab 例4：写出语言L=aibk | i,k1的3型文法 GS: SaS|aB BbB|b,2.2 句型分析 所谓句型分析是指给定一个字符串判定是否是文法上定义的句子。在日常生活中语言（无论中文、英文）都是上下文有关。实际上程序设计语言也是上下文有关的。如：GOTO GOTO无符号整数;标识符的前说明后使用问题，但程序设计语言中的大部分规则是可以写成上下文无关文法，上下文无关文法有足够的能力描述现今程序设计语言的语法结构，比如描述算术表达式，描述各种语句等等。 由于上下文无关文法不必考虑这所处的上下文，计算机实现比较方便，因而在程序设计语言的识别中较多地采用下文无关文法，今后如不特别指出的文法均为上下文无关的文法。,2.2.1 语法树 如果把推导的过程用一种直观的图形表示就形成了一棵树，即语法树也称推导树或分析树。 例：设GS： SAB AaAb|ab BcBd|cd 关于句子abccdd的最右推导为： S=AB=AcBd=Accdd =abccdd 其构造语法树如下：,注意树中的概念和文法的关系： 1结点 表示一个文法符号(V中的一个元素) 2根结点 表示识别符号(S) 3上下层 表示存在一个直接推导(存在这样一条 产生式) 4子树 表示一个直接推导序列 5直接子孙结点(下层从左往右) 表示相应的句型,定义 2.22 如果对于某文法的同一句子存在不同的语法树，则称句子的二义性的。包含二义性句子的文法称为二义性文法，否同称该文法为无二义性的 定义 2.23 如果对于某语言不存在无二义性文法，则称该语言是二义性的 注意：目前人们已经证明，二义性问题是不可判定的。即，不存在一个算法，它能在有限步骤内，确切判定任给的一个文法是否为二义的,例：设有文法GE： EE+E|E*E|（E）|i 证明该文法是二义性的 由于对于句子i*i+i有,两种不同的语法树，故该文法是二义性的,注意：文法的二义性和语言的二义性是两个不同的概念。 因为 对于同一语言可能有两个不同的文法G1和G2，一个是二义性的，但另一个却不是二义性的。 例： G1E: EE+E|E*E|(E)|i G2E: EE+T|T TT*F|F F(E)|i 对于非二义性文法来说，最左（最右）推导是唯一的。,消除二义性 如果语言不是二义性的，那么就存在一可以定义该语言非二义性文法(通过改造文法)。反之,如果语言是二义性的，就不能通过改造文法消除其二义性的。 例： GS： Sif E then S | if E then S else S| b 对于句型 if E then E then S else S 存在二棵不同的语法树，故该文法是二义性的。 在实际应用中靠近的then和 else先行匹配，为了识别方便可以消去二义性把该文法改写成： GS： SS1 | S2 S1if E then S1 else S1|b S2if E then S1|if E then S1 else S2,2.2.2 文法的约定 文法虽然规定的语言的形成方法,但文法中有的规则会对分析带来麻烦,有会带来灾难，为此需对文法中的规则加以限制。 有害规则 定义 2.23 文法G中形如UU的规则，称为有害规则。 这种规则没有增加句子的集合，给文法增加了二义性，给今后的分析带来不必要的麻烦，删除这样的规则没有形响到文法定义的语言。,例：设GS： SS|DS|D D0|1 删除有害规则SS后的新文法 G'S： SDS|D D0|1 显然有L(GS)=L(G'S)，,定义 2.24 文法G中某一规则 U u, 其中u（VnVt ）* ，若满足下列条件之一，则称该规则为多余规则。 （1）U(除开始符号外)不出现在该文法的任何其它的规则的右部。 （2）若在推导中使用该规则，则不能推出终结符号串。,例：设GS： (1) S Be (2) B Ce (3) B Af (4) A Ae (5) A e (6) C Cf (7) D f 由于非终结符D不在规则右部出现，非终结符C不能推导成终结符号串，故都是多余规则，应删除。（6）、（7）删除后（2）也不能推导成终结符号串也删除。,故GS： (1) S Be (2) B Af (3) A Ae (4) A e 当一个上下文无关的文法中不含有害规则和多余规则时，称这个文法是压缩了的文法，在以后各章中介绍的文法不特指都是压缩了的文法。,2.2.2 句型的分析方法 对于一个上下文无关文法，语法树就是该文法上的句型的推导过程的几何表示。语法树能将所给句型的结构很直观地显示出来了。利用语法树可直接对句型进行分析。这里所说的句型分析问题，就是对所给定的符号串分析是否是文法定义的句型。句型的分析也就是否能构造出推导过程(或归约过程)。进一步说，当给定一个符号串时，试图按照文法的规则为该符号串构造推导(或语法树)，以此识别出它是该文法的一个句型；当符号串全部由终结符号组成时，就是识别输入符号串是否是某文法的一个句子。,对于程序设汁语言来说，要识别输入符号串是否是程序设计语言的程序(句子)。程序实际上被定义为程序设计语言的一个句子。句型分析是一个识别输入符号串是否为语法上正确的程序的过程、在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序，分析算法又称识别算法。 这种分析算法又可分成两大类：即自顶向下的和自底向上的分析方法。 自顶向下 : 推导 开始符号到句子 (树生长) 自底向上 : 归约 句子到开始符号 (树修剪),自顶向下的分析方法 自顶向下的分析方法也称为自上而下的分析方法,它是从文法的开始符号出发，反复使用各种产生式，寻找“匹配”于输入符号串的推导。 例：GS： ScAd Aab Aa 识别输入串w=cabd是否该文法的句子。 (a) (b) (c),自底向上的分析方法 自底向上的分析方法又称自下而上的方法，它是从输入符号用开始，逐步进行“归约”，直至归约到文法的开始符号。 例:设有文法 GS： ScAd Aab Aa 识别输入串w=cabd是否该文法的句子。 (c) (b) (a),句型分析的有关问题 在自顶向下的分析方法中，需解决的问题是形如A1|2|3|4···|k的规则究竟选择那一个候选式? 在自底向上的分析方法中，需解决的问题是如在文法中存在形如A和B的规则，并在分析过程中发现形如的符号串是把它替换成A还是B？ 例:设GS: SaBC Bib|b CDE|FG Dd Eeh Fde Gt 当分析句子abdet时,对于C规则很难确定先用DE还是FG,例：GS:SaAcBe Ab AAb Bb 识别输入符号串abbbcbe 栈 输入符号串 a bbcde ab bcde aA bcde aAb cde aA cde aAc de aAcb e aAcB e aAcBe S,定义 2.25 设GS是一个文法，xuy 是文法G的一个句型，如果有S=*=xUy =+= xuy 则称u是句型xuy相对于非终结符U的短语、特别是，如果有Uu则称u是句型xuy相对于规则 Uu的简单短语。 上述定义的意思为某一句型中的子符号串归约后的符号串仍为句型 即S=*= xUy =+= xuy 定义 2.26 一个句型的最左简单短语称为该句型的句柄。,例：写出GN: NA AAD|D D0|1|2|3|4|5|6|7|8|9 中的句型AD3的短语、简单短语和句柄 N = AD = ADD = AD3 短语： 3 AD AD3 简单短语： AD 3 句柄(最左简单短语) AD 而A、 D 3不是短语.,每次归约句柄的归约方式，称为规范归约，归范归约又称最左归约，它是最右推导的逆过程（其分析过程中均为右句型）。 在规范归约中，由于每次归约的是句柄，所在句柄后面不会出现非终结符号，基于这一点，在采用的所谓移入归约法中，在移入归约过程中，一旦发现句柄即可用规则的左部替换，这种方法犹如“剪句柄”。归约过程实质上也是语法树的构造过程。,也可以由语法树的特性来求短语、简单短语及句柄： 步骤: （1）画出所求句子(型)的语法树(整个推导) （2）找出该语法树的所有子树 （3）每一子树的叶结点(从左往右)序列表示一个短语（4）高(深)度为1的子树的叶结点(从左往右)序列表示一个简单短语 （5）最左的高(深)度为1的子树的叶结点(从左往右)序列表示一个句柄(最左简单短语),例：设GS： SAB AaAb|ab BcBd|cd 求出句子abccdd的短语,简单短语和句柄： S=AB=AcBd=Accdd=abccdd 其构造语法树如下：,短语:abccdd, ab, ccdd, cd. 简单短语:ab, cd 句柄:ab.,例：GE:EE+T|T TT*F|F F(E)|i 试求出句子i+i*i+i的短语、简单短语和句柄,故短语为： i+i*i+i , i+i*i , i , i*i , i , i , i . 简单短语为: i , i , i , i . 句柄为: i .,