编译原理第二章--文法和语言

第二章文法和语言本章讲述目前广泛使用的上下文无关文法即用上下文无关文法作为程序设计语言语法的描述工具阐明语法的一个工具是文法本章将介绍文法和语言的概念本章重点上下文无关文法及其句型分析中的有关问题第一节文法的直观概念当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明或者定义句子的组成结构，比如“我是大学生”是汉语的一个句子汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用EBNF来表示这种句子的构成规则徇子〉=〈主语〉〈谓语〉〈主语〉=〈代词〉|〈名词〉〈代词〉=我|你他〈名词〉=王明|大学生|工人|英语〈谓语〉=〈动词〉〈直接宾语〉〈动词〉=是|学习〈直接宾语〉=〈代词〉|〈名词〉“我是大学生”的构成符合上述规则，而“我大学生是不符合上述规则，我们说它不是句子这些规则成为我们判别句子结构合法与否的依据一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子我们开始去找=左端的带有〈句子〉的规则并把它表示成=右端的符号串，这个动作表示成〈句子〉〈主语〉〈谓语〉，然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应的规则=右端代替之比如，选取了〈主语〉，并采用规则〈主语〉=〈代词〉，那么得到〈主语〉〈谓语〉〈代词〉〈谓语〉，重复做下去，我们得到句子“我是大学生”的全部动作过程是徇子〉=＞〈主语〉〈谓语〉n〈代词〉〈谓语〉n我〈谓语〉n我〈动词〉〈直接宾语〉n我是〈直接宾语〉n我是〈名词〉n我是大学生符号的含义是，使用一条规则，代替左边的某个符号，产生右端的符号串显然，按照上述办法，不仅生成“我是大学生”这样的句子，还可以生成“王明是大学生”，“王明学习英语”，“我学习英语”，“他学习英语”，“你是工人”，“你学习王明”等几十个句子事实上，使用文法作为工具，不仅为了严格地定义句子的结构，也是为了用适当条数的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具第二节符号和符号串符号和符号串，在形成语言中和编译技术中是很重要的概念任何一种语言，都是由许多语言的基本符号组成的符号串的集合如英语的基本符号有26个字母和一些标点符号，英语:就是由这些符号所组成的符号串的集合-字母表和符号串字母表是元素的非空有穷集合，字母表中的元素称为符号由字母表中的符号所组成的任何有穷序列称之为“符号串”例如:00,01,10是字母表2={0,1}上的符号串,又如ab,abc,bc是字母表2={a,b,c}上的符号串还允许有空符号串空符号串是不包含任何符号的符号串用£表示，其长度为0,即|£|=0-符号串的运算相等X=Y当且仅当组成X的诸符号与组成Y的诸符号依次相等，2={a,b,c}X=abbc Y=abbc X=Y X=ab Y=ba XWY符号串的长度,X是符号串，则其长度用|X|表示其数值等于组成该符号串的符号个数如X=STV|X|=3而|£|=0

③符号串的联接,X和Y是符号串，它们的联接XY是把Y的符号写在X的符号之后，得到的符号串X=ST Y=abu XY=STabu|X|=2|Y|=3|XY|=5由于£的含义显然有£X=X£=X

⑤集合的乘积运算符号串的集合若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合AB={XY|XeA,YEB}如A={a,b}B={c,d}AB={ac,ad,be,bd•••对于任意符号串X总有£X=X£=X/.{£}A=A{e}=A

①定义1文法G定义为四元组VN,VT,P,So其中为非终结符号集、VNVT终结符号集1非空有穷集P产生式的集合IS称为识别符号或开始看号，它是一个非终结符，它至少要在一条规则中作为左部出现VnAV=6V=VnUV V称为文法G的字母表T T

②定义2,如是文法G=VN,VT,P,S的规则，丫和3是V*中的任意符号，若有符号串V,W满足V=Ya8,w=y3s则说V应用规则a-B直接产生W或说W是V的直接推导或说W直接归约到V记作Vnw如，对于G[S]:S-OS1,S-O1V=OS1W=0011直接推导OS10011,使用的规则Sf01这里丫=0,5=1V=S,W=OS1直接推导S-0S1使用的规则S-0S1,这里丫=£,6=£

③定义3,如果存在直接推导的序列V=Wo=Wi=W……=Wn=W n02则称V推导出W或称W归约到V记作V与W

④定义4若有V W,或丫=处则记作V W如，对于G[S]S-0Sl,S-01存在直接推导序列V=OS100S11000S11100001111=W,B|JOS100001111也可记作OS100001111

⑤定义5,设G[S]是一文法，如果符号串X是从识别符号推导出来的，即S X,则称X是文法G[S]的句型若X仅由终结符号组成，即S XXEVT*S识别符号，则称X是文法G[S]的句子

⑥定义6,文法G所产生的语言L G={X|S X,XeVT*,S识别符号},即文法G[S]所产生的所有句子的集合A、形式语言理论可以证明如下两点B、给定一个文法，就能从结构上唯一地确定其语言G-L G给定一种语言，能确定其文法，但这种文法不是唯一的L-G1或G2,……在此我们用例子说明如文法G[Z]:1Z-aZb2Z-ab由该文法所确定的语言为用规则1:Z aZb a2Zb2…an-lZbn-1用规贝2:anbn所以，L G[Z]={anbn|n2}又如已知语言为L G={abna|n》l}可构造其文法G:G:Z-aBa B-b B|b对于上述语言，还可构造文法G GZ-aB B-Bb|b很显然,G不同于G’对上述语言还可以构造出其他文法

⑦定义7,若L Gl=L G2则称文法G1和G2是等价的第四节文法的类型乔姆斯基把文法分成四种类型，即型、1型、2型和3型这几类文法的差别在于对产生式施加不同的限制

1.设G=VN,VT,P,S,如果它的每个产生式a是这样一种结构a£VNU VT*且至少含有一个非终结符，而B£VNUVT*,则G是一个型文法0型文法也称短语方法一个非常重要的理论结果是,0型文法的能力相当于图灵机Turingo2,设G=VN,VT,P,S为一文法，若P中的每一个产生式a-B均满足|B闫a|,|a|指符号串a的长度，仅仅S—£除外，则文法G是1型或上下文有关的

3、设G=VN,VT,P,S,若P中的每一个产生式a-B满足a是一非终结符，3e VNUVT*则此文法称为2型的或上下文无关的例G={S,A,B},{a,b},P,S,其中P由下列产生式组成S-aB AfbAASfbA BfbA-a B-bSAfaS BfaBB有时，为书写简洁，常把相同左部的生产式，形如Af四A—012Af an缩写为A-ai|a2|---|an这里的元符号“I”读做“或上例的P可写为S-aB|bAA-a|aS|bAAB-b|bS|aBB

4.设G=VN,VT,P,S,若P中的每一个产生式的形式都是A-aB或A-a,其中A和B是非终结符,a是终结符，则G是3型文法或正规文法例文法G={S,A,B},{0,1},P,S,其中P由下列产生式组成S-OA A-1BSflB B-1BS-0B-lA-0A B-0A-OS显然G是正规文法四个文法类的定义是逐渐增加限制的，因此每一种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是0型文法第五节上下文无关文法及其语法树上下文无关文法有足够能力描述现今程序设计语言的语法结构，如算术表达式，各种语句等-语法树上下文无关文法句型推导的图解过程给定文法6=VN,VT,P,S对于G的任何句型都能构造与之关联的语法树这棵树满足下列4个条件

1、每个结点都有一个标记，此标记是V的一个符号

2.根的标记是S

3、若一结点n至少有一个它自己除外的子孙，并且有标记A,则A肯定在VN中

4、如果结点n的直接子孙，从左到右的次序是结点nl,n2,…,nk,其标记分别为Al,A2,…,AK,那么A-A1A2…AK一定是P中的一个产生式从一个例子来说明某语法树的构造例1G[S]={S,A},{a,b},P,S,其中P为1S-aAS2A-SbA3Af SS4S-a5Afba图2-5-1是G[S]的一棵语法树图2-5-1的语法树是G[S]的文法的句型aabbaa的推导过程非常直观自然的描述，从左至右读出图2-5-1的语法树的叶子标记,得到的就是句型aabbaao图・推导树25-1最左最右推导在推导的任何一步a B,其中、B是句型，都是对a中的最左最右非终结符进行替换，则称这种推导为最左最右推导最右推导常被称为规范推导由规范推导所得的句型称规范句型例如,S=aAS=aAa=aSbAa naSbbaa naabbaa二递归规则与递归文法递归的概念在编译技术中是一个很重要的概念递归定义是指在定义某事物时，又用到某事物本身递归规则，是指在规则的左部和右部具有相同的非终结符号的规则在文法中，可以包含有递归规则如U-XUY即为递归规则若乂=£则U-UY左递归若丫=£则U-XU右递归X、YW£则U-XU Y自嵌入文法的递归性质，若文法中至少包含一条递归规则，即U U…，U…U,U…U…则称此文法是直接递归的文法具有直接递归还具有间接递归如afBX有a YXU4UYX间接左递归U当YXU间接右递归U与・・・u…自嵌入定义递归文法，使得我们能够用有穷的文法去刻划无穷的语言例如有文法G[S]S-aB|bBBf a|b由于该文法是无递归性的，所以由它所描述的语言是有穷的，上述文法所确定的语言为（）L G[S]={aa,ab,ba,bb}例如文法G[Z]6Z-aZb7Z-ab由于该文法是递归性的，所以由它所描述的语言是无穷的由该文法所确定的语言为用规则

（1）:Z aZb a2Zb2・・・an-lZbn-1用规则

（2）:anbn所以，L（G[Z]）={anbn|n2}

（三）推导过程与语法树的生成给定一文法和相应的句子，据文法画出语法树给定一文法和相应的句子，据推导的定义，推出该文法的句型或句子，这种推导过程，用几何图形表示，就是语法树的生长过程例1中，对句子aabbaa推导过程可以列举以下3个推导过程1:S aASaAa ASbAa=aSbbaa=aabbaa推导过程2:S aASaSbAS aabASnaabbaS=aabbaa推导过程3:S aASaSbAS aSbAaaaby^a aabbaa不管是上述第1个还是第

2.第3个推导过程，它们相联的语法树都是图2-5-lo这就是说，一棵语法树表示了一个句型的种种可能的（但未必是所有的）不同推导过程，包括最左（最右）推导，但是，一个句型是否只对应唯一的一棵语法树呢？一个句型是否只有唯一的一个最左（最右）推导呢？不是的

（四）文法的二义性如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的或者说，若一个文法中存在某个句子，它有两个不同的最左（最右）推导，则这个文法是二义的例2文法G[E]（）E—E+E|E*E|E|i该文法的Vn={E}VT={+,*,（,）,i}可以看到,i*i+i是该文法的一个句子，因根据文法可以将其推导出来但是这样的句子可以有两棵语法树，很明显，也存在着两个最右（或最左）推导，见下图注意图中结点间连线上的数字，并不表示推导顺序，而是表示归约的顺序由于该句子对应着两棵语法树，所以该文法是二义性文法E+E_____

④E*E1E+E

①|

②・♦

②|

③11••图2-5-3图2-5-2对于例2的文法G,句型i*i+i就有两个不同的最左推导1和2,它们所对应的语法树分别如图2-5-2和图2-5-3所示推导1E=E+E=E*E+Eni*E+Eni*i+Eni*i+i推导2EnE*Eni*E=i*E+Eni*i+E=i*i+ii*i+i是文法G的一个句子，这个句子可以用完全不同的两种办法生成，在生成过程的第一步，一种办法使用产生式E-E+E进行推导，另一种办法是使用产生式E-E*E因而i*i+i对应了两棵不同的语法树第六节句型的分析若已有文法，我们就可以用它来推导和产生句子了，但是如若给定一个符号串，如何来确定该符号串是否是文法的句子呢？可用试图按照文法的规则构造推导也可以用语法树，以此识别它是否是该文法的句子语法分析分为两大类，即自上向下的和自下向上的所谓自上而下分析法，是从文法的开始符号出发，反复使用各种产生式，寻找“匹配”于输入符号串的推导自下而上的方法，则是从输入符号串开始，逐步进行“归约”，直至归约到文法的开始符号从语法树建立的方式可以很好的理解这两类方法的区别自上而下方法是从文法识别符号开始，将它做为语法树的根，向下逐步建立语法树,使语法树的末端接点符号串正好是输入符号串；自下而上方法则是从输入符号串开始，以它做为语法树的末端结点符号串，自底向上地构造语法树

（一）向上而下的分析方法以一个简单的例子，说明自上而下分析方法的基本思想例3考虑文法G[S]；1S-cAd2Af ab3Afa识别输入串w=cabd是否该文法的句子即从根符号S开始如图2-6-1（a）所示，试着为cabd构造一棵语法树在构造的第一步，唯一的一个产生式可施用，则构造了直接推导S（cAd,从S向下画语法树如图2-6-1的（b）所示这棵树的最左叶子标记为c,已和w的第一个符号匹配，考虑下一个叶子，标记A,可用A的第一个候选（产生式

（2））去扩展A,则会得到如图

2.6-1的（c）所示的语法树，构造的直接推导为cAd（cabdo这时输入符号串w的第二个符号a得到了匹配，第三个输入符号为b,将它与下一叶子标记b相比较，a b得以匹配，叶子d匹配了第四个输入符号，这时可以宣布识别过程胜利结束所构造的推导过程为:S（cAd（cabd图2-6-1向上而下的分析

（二）自下而上的分析方法仍使用上例中的文法来为输入符号串cabd构造推导或语法树，所采用的是自下而上的方法首先从输入符号串开始扫描cabd,从中寻找一个子串，该子串与某一产生式的右端相匹配a b子串a和子串ab都是合格的，假若我们选用了ab,用产生式

（2）的左端A去替代它，即把ab归约c到了A,得到子串cAdo构造了一个直接推导cAd（cabd,即从cabd叶子开始向上构造语法树，如图2-6-2的（b）所示接下去，在得到的串cAd中又找到了子串cAd与产生式

（1）的右端相匹配，则用S替代cAd,或称将cAd归约至I」S,得到了又一直接推导S（cAd,形成了图2-6-2的（c）所示的语法树，符号串cabd的推导序列为SncAdncabdA/\cabdb图2-6-2自下而上的分析c

（三）句型分析的有关问题

2、在自底向上分析中，在分析每一步都是从当前串中选择一个子串，将它归约到某个非终结符号，这个子串“可归约串”，如何找？这个可归约串，称“句柄二但是，如何找出这些句柄呢？若有两条以上的规则，其右部符号串相同，若该符号串又构成句型的句柄时;那么，又将根据哪条规则进行归约呢？

⑧定义8,令G是文法,S是文法的开始符号，ci B5是文法的一个句型，如果有S A6且A B,则称8是句型a85相对于非终结符A的短语特别，如果A（B则称B是句型a86相对于规则A-B的直接短语（简单短语）一个句型的最左直接短语，称为句型的句柄例4定义表达式的无二义文法G[E]:E-TIE+T T—F|T*F（）1E|i考虑它的一个句型i*i+i,为了讲授方便，我们将句型写作il*i2+i3因为有:DE F*i2+i3的且F（il则称il是il*i2+i3的相对于非终结符F的短语，也是相对于规则F-i直接短语

②E il*F+i3语且F（i2则i2是句型il*i2+i3的相对于F的短语，也是相对于规则F-i的直接短

③E il*i2+F短语且F（i3则i3也是句型il*i2+i3的相对于F的短语，也是相对于规则F-i的直接且T±ii

④E3T*i+i则ii是句型ii*i+i3的相对于T的短语232

⑤E3ii*i+T且T4i3则i是句型ii*i2+i3的相对于T的短语33

⑥E^T+i3且T与产i2则ii*i是句型ii*i+i3的相对于T的短语22

⑦E3E+i3且E当ii*i2则ii*i2是句型ii*i2+i3的相对于E的短语一且E与ii*i+i3则ii*i2+i3是句型ii*i+is的相对于E的短语22即il,i2,i3,il*i2和il*i2+i3都是句型il*i2+i3的短语，而且il,i2,i3均为直接短语，其E E中il是

⑧最左3直接短语，即句柄

（四）子树与短语子树，是由该树的某个结点（称为子树的根）连同它向下射出的部分组成利用语法树，我们很容易地找到该句型的短语，直接短语，句柄若句型中某些符号，按从左到右顺序，组成某棵小树的末端结点，那么，由这些末端结点所组成的符号串，即是相对于子树根的短语第七节有关文法的实用限制在实用中，我们将限制文法中不得含有有害规则和多余规则，所谓有害规则，是指形为U-U的产生式它对描述语言显然是没有必要的说它有害，是说它只会引起文法的二义性所谓多余规则，是指文法中那些连一个句子的推导都用不到的规则，这类规则在文法中以两种形式出现一例5文法G[S]1S-Be1S—Be2B—Ce3B—Af3B—Af4A—A4A—Ae e5A-e5A一e6C-Cf7D—f对文法G=VN,VT,P,S来说，为了保证其任一非终结符A在句子推导中出现，必须满足如下两个条件LA必须在某句型中出现即有S aAB,其中a,B属于VTUVN*

2、必须能够从A推出终结符号串t来即A t,,其中t£V若程序设计语言的文法包含有多余规则时，其中必定有错误存在，因此检查文法是否包含多余规则是很有必要的。