北航计算机学院编译习题讲解

2008年6月27日1北京航空航天大学计算机科学与工程系1、复习2、习题讲解习题课习题课(1(1--33章）章）2008年6月27日2北京航空航天大学计算机科学与工程系第一章第一章概论(介绍名词术语、了解编译系统的结构和编译过程）2008年6月27日3北京航空航天大学计算机科学与工程系所谓编译过程是指将高级语言程序翻译为等价的目标程序的过程。1.21.2编译过程编译过程词法分析语法分析语义分析、生成中间代码代码优化生成目标程序习惯上是将编译过程划分为5个基本阶段：2008年6月27日4北京航空航天大学计算机科学与工程系典型的编译程序具有7个逻辑部分S.PO.P语义分析、生成中间代码生成目标程序代码优化语法分析程序词法分析程序出错处理符号表管理2008年6月27日5北京航空航天大学计算机科学与工程系第二章第二章•掌握符号串和符号串集合的运算、文法和语言的定义•几个重要概念：递归、短语、简单短语和句柄、语法树、文法的二义性、文法的实用限制等。•掌握文法的表示：BNF、扩充的BNF范式、语法图。•了解文法和语言的分类2008年6月27日6北京航空航天大学计算机科学与工程系3.1词法分析的功能3.2词法分析程序的设计与实现–状态图3.3词法分析程序的自动生成–有穷自动机、LEX第三章第三章::词法分析词法分析2008年6月27日7北京航空航天大学计算机科学与工程系补充补充正则文法正则文法NFANFA正则表达式正则表达式123456DFADFA最小化2008年6月27日8北京航空航天大学计算机科学与工程系习题习题11－－33章章2008年6月27日9北京航空航天大学计算机科学与工程系第一章第一章•2．典型的编译程序可划分为哪几个主要的逻辑部分？各部分的主要功能是什么？2008年6月27日10北京航空航天大学计算机科学与工程系所谓编译过程是指将高级语言程序翻译为等价的目标程序的过程。1.2编译过程词法分析语法分析语义分析、生成中间代码代码优化生成目标程序习惯上是将编译过程划分为5个基本阶段：2008年6月27日11北京航空航天大学计算机科学与工程系典型的编译程序具有7个逻辑部分S.PO.P语义分析、生成中间代码生成目标程序代码优化语法分析程序词法分析程序出错处理符号表管理2008年6月27日12北京航空航天大学计算机科学与工程系P19：4.试证明：A+=AA*=A*A证：∵A*=A0∪A+，A+=A1∪A2∪…∪An∪…得：A*=A0∪A1∪A2∪…∪An∪…∴AA*=A（A0∪A1∪A2∪…∪An∪…）=AA0∪AA1∪AA2∪…∪AAn∪…=A∪A2∪A3∪An+1∪…=A+同理可得：A*A=(A0∪A1∪A2∪…∪An∪…)A=A0A∪A1A∪A2A∪…∪AnA∪…=A∪A2∪A3∪An+1∪…=A+因此：A+=AA*=A*A2008年6月27日13北京航空航天大学计算机科学与工程系P26:1.设G[〈标识符〉]的规则是：〈标识符〉::=a|b|c|〈标识符〉a|〈标识符〉c|〈标识符〉0|〈标识符〉1试写出VT和VN，并对下列符号串a,ab0,a0c01,0a,11,aaa给出可能的一些推导。解：VT={a,b,c,0,1}，VN={〈标识符〉}(1)不能推导出ab0,11,0a(2)〈标识符〉=a(3)〈标识符〉=〈标识符〉1=〈标识符〉01=〈标识符〉c01=〈标识符〉0c01=a0c01(4)〈标识符〉=〈标识符〉a=〈标识符〉aa=aaa2008年6月27日14北京航空航天大学计算机科学与工程系P26P26：：22．．写一文法，其语言是偶整数的集合写一文法，其语言是偶整数的集合常见错误：1.终结符集中没有奇数。2.如下定义：偶整数=数字串偶数字，数字串=数字|数字串数字数字串不能=ε。3.忽略负偶数。2008年6月27日15北京航空航天大学计算机科学与工程系作法一：偶整数::=2×整数整数::=数字串数字数字串::=数字数字::=0|1|2|3|4|5|6|7|8|9作法二：z=偶整数G(z)=0|2|2Z|2(Z+1)|2(Z-1)或：G(Z)=0|2|Z+2|Z-22008年6月27日16北京航空航天大学计算机科学与工程系解：G[偶整数]：偶整数::=符号偶数字|符号数字串偶数字符号::=+|—|ε数字串::=数字串数字|数字数字::=偶数字|1|3|5|7|9偶数字::=0|2|4|6|83.写一文法，使其语言是偶整数的集合，但不允许有以0开头的偶整数。2008年6月27日17北京航空航天大学计算机科学与工程系•4.设文法G的规则是：〈A〉::=bA|cc试证明：cc,bcc,bbcc,bbbcc∈L[G]证：（1）〈A〉=cc（2）〈A〉=b〈A〉=bcc（3）〈A〉=b〈A〉=bb〈A〉=bbcc（4）〈A〉=b〈A〉=bb〈A〉=bbb〈A〉=bbbcc又∵cc,bcc,bbcc,bbbcc∈Vt*∴由语言定义，cc,bcc,bbcc,bbbcc∈L[G]2008年6月27日18北京航空航天大学计算机科学与工程系5试对如下语言构造相应文法：（1）{a(bn)a|n=0,1,2,3,……},其中左右圆括号为终结符。（2）{（an）（bn）|n=1,2,3,……}解：（1）文法[G〈S〉]：S::=a(B)aB::=bB|ε(2)文法[G〈S〉]：--错了，两个n不等S::=(A)(B)A::=aA|aB::=bB|bS::=(B)B::=aBb|a)(b2008年6月27日19北京航空航天大学计算机科学与工程系7.对文法G3[〈表达式〉]〈表达式〉::=〈项〉|〈表达式〉+〈项〉|〈表达式〉-〈项〉〈项〉::=〈因子〉|〈项〉*〈因子〉|〈项〉/〈因子〉〈因子〉::=（〈表达式〉）|i列出句型〈表达式〉+〈项〉*〈因子〉的所有短语和简单短语。表达式=表达式+项=表达式+项*因子表达式表达式+项项*因子短语有：〈表达式〉+〈项〉*〈因子〉和〈项〉*〈因子〉简单短语是：〈项〉*〈因子〉2008年6月27日20北京航空航天大学计算机科学与工程系8文法V::=aaV|bc的语言是什么？•解：L（G[V]）={a2nbc|n=0,1,2,……}V⇒aaV⇒aaaaV⇒....⇒a2nbc(n≥1)V⇒bc(n=0)2008年6月27日21北京航空航天大学计算机科学与工程系P33：5.已知文法G[E]：E::=ET+|TT::=TF*|FF::=FP↑|PP::=（E）|i有句型TF*PP↑+，问此句型的短语，简单短语，和句柄是什么？解：此句型的短语有：TF*PP↑+，TF*，PP↑，P简单短语有：TF*，P句柄是：TF*常见错误：1.认为下列是短语：TF*PP↑、PP↑+、+2.认为TF*PP↑+不是短语。3.认为PP↑是简单短语。4.不能正确识别句柄2008年6月27日22北京航空航天大学计算机科学与工程系8.证明下面的文法G是二义的：S::=iSeS|iS|i证：由文法可知iiiei是该文法的句子，又由文法可知iiiei有两棵不同的语法树。所以该文法是二义性文法。2008年6月27日23北京航空航天大学计算机科学与工程系P393．试构造一个从文法中删除无用符号的算法。2008年6月27日24北京航空航天大学计算机科学与工程系多余规则：（1）在推导文法的所有句子中，始终用不到的规则。即该规则的左部非终结符不出现在任何句型中。--不可达（2）在推导句子的过程中，一旦使用了该规则，将推不出任何终结符号串。即该规则中含有推不出任何终结符号串的非终结符。--不活动例如给定G[Z]，若其中关于U的规则只有如下一条：U::=xUy该规则是多余规则。若还有U::=a，则此规则并非多余若某文法中无有害规则或多余规则，则称该文法是压缩过的。2008年6月27日25北京航空航天大学计算机科学与工程系判断U是否为无用符号条件条件•检查文法中每一条规则左部的每个非终结符U是否满足下述两个条件：–条件1：Z⇒xUy,x,y∈V*,Z为识别符号（即：要求U必须出现在某个句型中）–条件2：U⇒t,t∈Vt*（即：能从U推出终结符号串）*＋2008年6月27日26北京航空航天大学计算机科学与工程系判断条件判断条件22的算法的算法•算法思路：对满足条件的符号作标记，最后没有标记的符号为无用符号。•加标记的方法如下：–对于形如U::=u(u∈Vt*)的规则，左部U自然满足条件2，因此对U标记。–当一规则U::=W的右部W中包含的非终结符全被加标记时，即满足条件2时，左部U也满足条件2，对U加标记。2008年6月27日27北京航空航天大学计算机科学与工程系流程图流程图开始对所有U::=W的左部加标记，IfW中仅包含终结符和已被加标记的非终结符所有U∈Vn已全部被标记最近一次执行框1未对任何U∈Vn加标记123否否是是停机2008年6月27日28北京航空航天大学计算机科学与工程系举例举例•例：对于文法Z::=BeA::=AeA::=eB::=CeB::=AfC::=CfD::=f*第一遍第二遍***第三遍*所以：B::=Ce和C::=Cf是多余也多余，未查出。不满足条件1，不是条件22008年6月27日29北京航空航天大学计算机科学与工程系练习练习•写一文法，使其语言是偶整数的集合，但不允许有以0开头的偶整数。2008年6月27日30北京航空航天大学计算机科学与工程系第三章词法分析P67.1．画出下述文法的状态图〈Z〉::=〈B〉e〈B〉::=〈A〉f〈A〉::=e|〈A〉e使用该状态图检查下列句子是否是该文法的合法句子f，eeff，eefe解：SAeBZefef，eeff不是该文法的合法句子，eefe是该文法的合法句子2008年6月27日31北京航空航天大学计算机科学与工程系解：（1）Z→A1|0A→A0|0（2）V={A,Z,0,1}Vn={A,Z}Vt={0,1}（3）L(G[S])={0或0n1,n≥1}L(G[S])={0|00*1}2、有下列状态图，其中S为初态，Z为终态。（1）写出相应的正则文法：（2）写出该文法的V，Vn和Vt；（3）该文法确定的语言是什么？S开始A00Z012008年6月27日32北京航空航天大学计算机科学与工程系•5．令A，B，C是任意正则表达式，证明以下关系成立：A|A=A（A*）*=A*A*=ε|AA*（AB）*A=A（BA）*（A|B）*=（A*B*）*=（A*|B*）2008年6月27日33北京航空航天大学计算机科学与工程系•证明：⑴A∣A＝｛x∣x∈L(A)或x∈L(A)｝＝｛x∣x∈L(A)｝＝A⑵（A*）*＝（A*）0∪（A*）1∪（A*）2∪…∪（A*）n＝ε∪(A0∪A1∪A2∪…∪An)∪(A1…)＝ε∪A0∪A1∪A2∪…∪An＝A*2008年6月27日34北京航空航天大学计算机科学与工程系⑶ε︱AA*所表示的语言是:{ε}∪LA·LA*＝LA0∪LA（LA0∪LA1∪LA2∪…）＝LA0∪LA1∪LA2∪…＝LA*故ε︱AA*＝A*⑷(LALB)*LA=({ε}∪L(A)LB∪LALBLALB∪LALBLALBLALB∪…)LA=LA∪LALBLA∪LALBLALBLA∪LALBLALBLALB∪LA…•=LA∪({ε}∪LBLA∪LBLALBLA∪…)•=LA(LBLA)•∴(AB)*A=A(BA)*2008年6月27日35北京航空航天大学计算机科学与工程系•⑸三个表达式所描述的语言都是LALB中任意组合•∴（A|B）*=(A*B*)=(A*|B*)*2008年6月27日36北京航空航天大学计算机科学与工程系6、构造下列正则表达式相应的DFA•（1）1（0|1）*|0•（2）1（1010*|1（010）*1）*02008年6月27日37北京航空航天大学计算机科学与工