编译原理考试习题及答案

程序设计语言,Chapter3.词法分析,编译原理参考答案,2020/5/19,CH.3.练习题8(P64.),8.给出下面的正规表达式。(1)以01结尾的二进制数串;正规式(0|1)*01(2)能被5整除的十进制整数;允许任意0开头：(0|1|2|3|4|5|6|7|8|9)*(0|5)不允许0开头（0本身除外）：(0|5)|(1|2|3|9)(0|1|2|3|9)*(0|5),2020/5/19,CH.3.练习题7(P64.),7.(1)1(0|1)*101构造DFA。解1:正规式对应的NFA:,(1)正规式1(0|1)*101,DFA:,(1)正规式1(0|1)*101,DFA:,2020/5/19,CH.3.练习题7(P64.),7.构造下列正规式相应的DFA。(1)1(0|1)*101解2:正规式对应的NFA:,0,4,1,2,3,1,1,0,1,1,0,DFA:,2020/5/19,7.构造下列正规式相应的NFA。(P64.)(2)1(1010*|1(010)*1)*0,2020/5/19,7.构造下列正规式相应的NFA。(P64.)(2)1(1010*|1(010)*1)*0,7.(2)1(1010*|1(010)*1)*0的NFA。,2020/5/19,CH.3.练习题14(P64.),(1)正规式:(10|0)*(2)NFA:确定化:,DFA:,2020/5/19,CH.3.练习题14(P64.),(1)正规式:(10|0)*(2)NFA:,DFA:,构造一个DFA，它接受S0,1上所有满足如下条件的字符串：每个1都有0直接跟在右边。,DFA:(最简),程序设计语言,Chapter2.高级语言及其语法描述,编译原理参考答案,CH.2.练习题6(P36.),6.令文法G6为:ND|NDD0|1|2|3|4|5|6|7|8|9(1)G6的语言L(G6)是什么?注意：集合的写法不正确解：L(G6)=0,1,2,3,4,5,6,7,8,9+=09数字构成的所有数字串，可以0开头(2)给出句子0127、34和568的最左和最右推导。注意：1)步骤，和的区别；2)不能写为解：0127的最左推导：NNDNDDNDDDDDDD0DDD01DD012D01270127的最右推导：NNDN7ND7N27ND27N127D1270127,+,CH.2.练习题8(P36.),8.令文法为ET|E+T|E-TTF|T*F|T/FF(E)|i,(1)给出i+i*i、i*(i+i)的最左推导和最右推导。,解：此处仅以i*(i+i)为例给出答案,最左推导ETT*FF*Fi*Fi*(E)i*(E+T)i*(T+T)i*(F+T)i*(i+T)i*(i+F)i*(i+i),最右推导ETT*FT*(E)T*(E+T)T*(E+F)T*(E+i)T*(T+i)T*(F+i)T*(i+i)F*(i+i)i*(i+i),CH.2.练习题8(P36.),8.令文法为ET|E+T|E-TTF|T*F|T/FF(E)|i,i-i-i的语法树,(2)给出i+i+i、i+i*i和i-i-i的语法树。,i+i+i的语法树,i+i*i的语法树,注意：树枝和符号均不可随意增减！,2020/5/19,CH.2.练习题9(P36.),9.证明下面的文法是二义的：SiSeS|iS|i证明:因为存在句子iiiei，它对应两棵不同的语法树,如右图:所以该文法是二义文法。说明：按定义只要能给出一个反例即可，iiiei不是唯一的反例。,编译原理参考答案,程序设计语言,Chapter5.自下而上语法分析,2020/5/19,CH.5.练习题1(P133.),1.令文法G1为：EE+T|TTT*F|FF(E)|i证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。,证明1:存在从开始符号E出发到E+T*F的推导：EE+TE+T*FE+T*F是G1的一个句型。短语:E+T*F是句型相对于非终结符E的短语;T*F是句型相对于非终结符T的短语。直接短语:T*F是句型相对于规则TT*F的直接短语句柄:T*F,2020/5/19,CH.5.练习题1(P133.),1.令文法G1为：EE+T|TTT*F|FF(E)|i证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。,证明2:可构造出E+T*F的语法树，如右图所示，E+T*F是G1的一个句型。证明3:(也可用归约来证明)（概念熟悉后，短语、直接短语和句柄可直接列出而不用说明）短语:E+T*F，T*F直接短语:T*F句柄:T*F,2020/5/19,CH.5.练习题2(P133.),2.考虑下面的表格结构文法G2：Sa|(T)TT,S|S(1)给出(a,(a,a)的最左和最右推导。,(1)解:(a,(a,a)的最左推导：S(T)(T,S)(S,S)(a,S)(a,(T)(a,(T,S)(a,(S,S)(a,(a,S)(a,(a,a)最右推导：S(T)(T,S)(T,(T)(T,(T,S)(T,(T,a)(T,(S,a)(T,(a,a)(S,(a,a)(a,(a,a),2020/5/19,CH.5.练习题2(P133.),2.(2)指出(a,(a,a)的规范归约及每一步的句柄。根据这个规范归约，给出“移进-归约”的过程，并给出它的语法树自下而上的构造过程。,2020/5/19,CH.5.练习题2(P133.),2.(2).给出(a,(a,a)“移进-归约”的过程。,(2)解:(a,(a,a)的“移进-归约”过程:步骤符号栈输入串动作句柄1#(a,(a,a)#a2#(a,(a,a)#移进(3#(a,(a,a)#移进a4#(S,(a,a)#归约SaS5#(T,(a,a)#归约TSa6#(T,(a,a)#移进,7#(T,(a,a)#移进(8#(T,(a,a)#移进a,2020/5/19,CH.5.练习题2(P133.),2.(2).给出(a,(a,a)“移进-归约”的过程。,(2)解:(a,(a,a)的“移进-归约”过程:步骤符号栈输入串动作句柄9#(T,(S,a)#归约SaS10#(T,(T,a)#归约TSa11#(T,(T,a)#移进,12#(T,(T,a)#移进a13#(T,(T,S)#归约SaT,S14#(T,(T)#归约TT,S(T)15#(T,(T)#移进)16#(T,S)#归约S(T)T,S,2020/5/19,CH.5.练习题2(P133.),2.(2).给出(a,(a,a)“移进-归约”的过程。,(2)解:(a,(a,a)的“移进-归约”过程:步骤符号栈输入串动作句柄17#(T)#归约TT,S(T)18#(T)#移进)19#S#归约S(T)20成功,分析结束,接受输入串,2020/5/19,CH.5.练习题2(P133.),2.(2).给出(a,(a,a)的语法树自下而上构造过程。,(2)解:(a,(a,a)的语法树自下而上构造过程:用序号表示,2020/5/19,CH.5.练习题3(P133.),3.(1)计算练习2文法G2的FIRSTVT和LASTVT。Sa|(T)TT,S|S,(1)解:（执行相应的算法可求得）FIRSTVT(S)=a,(FIRSTVT(T)=,a,(LASTVT(S)=a,)LASTVT(T)=,a,),2020/5/19,CH.5.练习题3(P133.),3.(2)计算文法G2的优先关系,G2是一个算符优先文法吗?Sa|(T)TT,S|S,(2)解:FIRSTVT(S)=a,(FIRSTVT(T)=,a,(LASTVT(S)=a,)LASTVT(T)=,a,)逐一考察S(T)和TT,S两两相邻的符号，得到算符优先关系,如右图；G2是算符优先文法。,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,2020/5/19,3.(4)给出输入串(a,(a,a)的算符优先分析过程。,Sa|(T)TT,S|S,最左素短语,2020/5/19,.,.,.,.,.,.,.,.,.,.,.,.,.,3.(4)给出输入串(a,(a,a)的算符优先分析过程。,Sa|(T)TT,S|S,最左素短语,2020/5/19,5.(1)考虑文法SAS|bASA|a列出这个文法的所有LR(0)项目。,CH.5.练习题5(P134.),解(1):拓广文法，加入SS拓广文法的LR(0)项目有:S.SSS.S.ASSA.SSAS.S.bSb.A.SAAS.AASA.A.aAa.,2020/5/19,5.(2)构造文法SAS|bASA|a的LR(0)项目集规范族及识别活前缀的DFA。,1）拓广文法，加入SS,2）画出DFA,5.(2)构造文法SAS|bASA|a的LR(0)项目集规范族及识别活前缀的DFA。,0:S.SS.ASS.bA.SAA.a,5:ASA.SA.SS.ASS.bA.SAA.a,7:SAS.AS.AA.SAA.aS.ASS.b,1:SS.AS.AA.SAA.aS.ASS.b,3:Sb.,4:Aa.,2:SA.SS.ASS.bA.SAA.a,6:AS.AA.SAA.aS.ASS.b,S,b,a,A,A,S,b,a,A,S,a,b,S,a,b,A,S,A,b,a,S,a,b,A,2020/5/19,5.(3)文法SAS|bASA|a是LR(0)文法吗？,不是LR(0)文法！因为存在冲突，例如状态1、状态5,编译原理参考答案,程序设计语言,Chapter4.自上而下语法分析,2020/5/19,CH.4.练习题1(P81.),1.考虑下面文法G1:Sa|(T)TT，S|S(1)消去G1的左递归。然后对每个非终结符,写出不带回溯的递归子程序。,解(1)消左后的文法G1:Sa|(T)TSTT,ST|,CH.4.练习题1(P81.),解(1)不带回溯的递归子程序:Sa|(T)ProcedureS;Beginifsym=aorsym=thenadvanceelseifsym=(thenbeginadvance;T;ifsym=)thenadvanceelseerrorendelseerrorEnd;,CH.4.练习题1(P81.),解(1)不带回溯的递归子程序:TSTProcedureT;BeginS;Tend;,解(1)不带回溯的递归子程序:T,ST|procedureT;beginifsym=,thenbeginadvance;S;TendEnd;,CH.4.练习题1(P81.),(2)经改写后的文法是否是LL(1)的?给出它的预测分析表。消左后的文法G1:Sa|(T)TSTT,ST|,(2)因为G1:文法不含左递归;对Sa|(T)FIRST(a)=a,FIRST()=,FIRST(T)=(,集合互不相交且不含;对T,ST|FIRST(,ST)=,FIRST()=,其交集为空。但FIRST(T)=FIRST(,ST)FIRST()=，,然而，FOLLOW(T)=)FIRST(T)=，,，两者不相交。所以，G1是LL(1)文法。,2020/5/19,CH.4.练习题1(P81.),(2)构造G1的预测分析表:对Sa|(T)对TSTFIRST(a)=aFIRST(ST)=a,(FIRST()=对T,ST|FIRST(T)=(FIRST(,ST)=,预测分析表:FOLLOW(T)=),CH4.1.(3)给出对符号串(a，)的分析过程,步骤符号栈输入串动作,所用产生式.0#S(a,)#初始；用S,(查表1#)T(a,)#S(T),展开S2#)Ta,)#匹配(；用T,a查表3#)TSa,)#TST,展开T;用S,a查表4#)Taa,)#Sa,展开S5#)T,)#匹配a;用T,查表6#)TS,)#T,ST,展开T7#)TS)#匹配,；用S,查表8#)T)#S,展开S9#)T)#匹配；用T,)查表10#)#T,展开T11#匹配)12#分析成功,结束分析,CH.4.练习题3(P82.),3.下面文法中,哪些是LL(1)的,说明理由。(1)SABcAa|Bb|。,解，因为FOLLOW(S)=#文法不含左递归;FIRST(S)=a,b,c对Aa|候选式的FIRST集合互不相交;FIRST(A)但,FOLLOW(A)=b,cFIRST(A)=a,两者不相交。Bb|其候选式的FIRST集合互不相交;FIRST(B)但，FOLLOW(B)=cFIRST(B)=b,两者也不相交。所以，文法是LL(1)文法。,CH.4.练习题3(P82.),3.下面文法中,哪些是LL(1)的,说明理由。(2)SAbAa|B|Bb|。,解(1)因为FOLLOW(S)=#对Aa|B|;FIRST(S)=a,bFIRST(B)=b,与FIRST()=相交;所以文法不是LL(1)文法。解(2)对Aa|因为FIRST(A)=a,b,，FOLLOW(A)=b,FOLLOW和FIRST两者相交。所以文法不是LL(1)文法。,CH.4.练习题3(P82.),3.下面文法中,哪些是LL(1)的,说明理由。(3)SABBAAa|Bb|。,解，虽然FOLLOW(S)=#文法不含左递归;FIRST(S)=a,b,对Aa|，其候选式的FIRST集合不相交;对Bb|，其候选式的FIRST集合也不相交;但对Aa|（由Bb|出发证明也可）FOLLOW(A)=a,b,#,FIRST(A)=a,两者相交。所以，文法不是LL(1)文法。,CH.4.练习题3(P82.),3.下面文法中,哪些是LL(1)的,说明理由。(4)SaSe|BBbBe|CCcCe|d。,解，因为文法不含左递归;对SaSe|B、BbBe|C和CcCe|d各产生式的候选式的FIRST集合均不相交;即FIRST(aSe)FIRST(B)=；FIRST(bBe)FIRST(C)=；FIRST(cCe)FIRST(d)=；FIRST(S)=a,b,c,d，FIRST(B)=b,c,dFIRST(C)=c,d均不含。所以，文法是LL(1)文法。,编译原理参考答案,程序设计语言,Chapter7.语义分析和中间代码产生,2020/5/19,P217-1,a*（-b+c）后缀式：ab-c+*a+b*（c+d/e）后缀式：abcde/+*+-a+b*（-c+d）后缀式：a-bc-d+*+notAornot（CornotD）后缀式：AnotCDnotornotor（AandB）or（notCorD）后缀式：ABandCnotDoror,2020/5/19,P217-3,-（a+b）*（c+d）-（a+b+c）的四元式序列：（1）(+，a，b，T1)（2）(-，T1，-，T2)（3）(+，c，d，T3)（4）(*，T2，T3，T4)（5）(+，a，b，T5)（6）(+，T5，c，T6)（7）(-，T4，T6，T7),2020/5/19,P218-4,自下而上分析过程中把赋值语句A:=B*（-C+D）翻译成三地址码的步骤：（参看p179的语义子程序）,语法分析翻译过程：A:=B*(-C+D)A:=E1*(-C+D)E1.place=k2A:=E1*(-E2+D)E2.place=k3A:=E1*(E3+D)A:=E1*(E3+E4)A:=E1*(E5)A:=E1*E6A:=E7S,产生一个新的中间变量T1E3.place=k5产生代码k5:=uminusk3,k1K2k3k4k5k6k7,符号表,2020/5/19,A:=B*(-C+D)的三地址码,k5:=uminusk3k6:=k5+k4k7:=k2*k6k1:=k7,k1K2k3k4k5k6k7,符号表,（参看p179的语义子程序）,2020/5/19,P218-6：用7.4.2节的办法，把Aor（Bandnot（CorD）翻译成四元式序列,100：（jnz，A，-，0）101：（j，-，-，102）102：（jnz，B，-，104）103：（j，-，-，0）104：（jnz，C，-，.）105：（j，-，-，106）106：（jnz，D，-，.）107：（j，-，-，.）,2020/5/19,P218-7,100：（j，A，C，102）101：（j，-，-，115）102：（j，B，D，104）103：（j，-，-，115）104：（j=，A，1，106）105：（j，-，-，109）106：（+，C，1，T1）107：（:=，T1，-，C）108：（j，-，-，100）109：（j，A，D，111）110：（j，-，-，100）111：（+，A，2，T2）112：（:=，T2，-，A）113：（j，-，-，109）114：（j，-，-，100）115：,用7.5.1节的办法，把下面的语句翻译成四元式序列：whileACandBDdoifA=1thenC:=C+1elsewhileADdoA:=A+2;,编译原理参考答案,程序设计语言,Chapter8.Chapter11.,2020/5/19,CH8.CH11.,1.什么是符号表？符号表有哪些重要作用？2.符号表的表项常包括哪些部分？各描述什么？3.有哪些存储分配策略？并叙述何时用何种存储分配策略？4.代码优化的常用措施和优化的三个层次。,编译原理参考答案,程序设计语言,补充题,2020/5/19,补充题,1.画出编译程序的总体逻辑结构图，简述各部分的主要功能。,2020/5/19,补充题,2.