编译原理试题及答案二

编译原理试题及答案二CH.4.练习题1(P81.)1.考虑下面文法G1:

S→a|^|(T)T→T，S|S(1)消去G1的左递归。然后对每个非终结符,写出不带回溯的递归子程序。解(1)消左后的文法G1’:S→a|^|(T)T→ST’T’→,ST’|ε2023/2/2CH.4.练习题1(P81.)解(1)不带回溯的递归子程序:S→a|^|(T)ProcedureS;Beginifsym=‘a’orsym=‘^’thenadvanceelseifsym=‘(‘thenbeginadvance;T;ifsym=‘)’thenadvance

elseerrorendelseerrorEnd;CH.4.练习题1(P81.)解(1)不带回溯的递归子程序:T→ST’ProcedureT;BeginS;T’end;

解(1)不带回溯的递归子程序:T’→,ST’|εprocedureT’;beginifsym=‘,’thenbeginadvance;

S;T’endEnd;CH.4.练习题1(P81.)(2)经改写后的文法是否是LL(1)的?给出它的预测分析表。消左后的文法G1’:S→a|^|(T)T→ST’T’→,ST’|ε(2)因为G1’:①文法不含左递归;②对S→a|^|(T)FIRST(a)={a},FIRST(^)={^},FIRST((T))={(},集合互不相交且不含ε;③对T’→,ST’|εFIRST(,ST’)={,},FIRST(ε)={ε},其交集为空。

但ε∈FIRST(T’)=FIRST(,ST’)∩FIRST(ε)={，,ε},

然而，FOLLOW(T’)={)}FIRST(T’)={，,ε}，两者不相交。所以，G1’是LL(1)文法。CH.4.练习题1(P81.)(2)构造G1’的预测分析表:①对S→a|^|(T)②对T→ST’

FIRST(a)={a}FIRST(ST’)={a,^,(}FIRST(^)={^}③对T’→,ST’|εFIRST((T))={(}FIRST(,ST’)={,}预测分析表:

FOLLOW(T’)={)}

a^(),#

SS→aS→^S→(T)

TT→ST’T→ST’T→ST’

T’T’→εT’→,ST’2023/2/2CH4.1.(3)给出对符号串(a，^)的分析过程步骤符号栈输入串动作,所用产生式.0#S(a,^)#初始；用S,(查表1#)T((a,^)#S→(T),展开S2#)Ta,^)#匹配(；用T,a查表3#)T’Sa,^)#T→ST’,展开T;用S,a查表4#)T’aa,^)#S→a,展开S5#)T’,^)#匹配a;用T’,,查表6#)T’S,,^)#T’→,ST’,展开T’7#)T’S^)#匹配,；用S,^查表8#)T’^^)#S→^,展开S9#)T’)#匹配^；用T’,)查表10#))#T’→ε,展开T’11##匹配)12##分析成功,完毕分析CH.4.练习题3(P82.)3.下面文法中,哪些是LL(1)的,说明理由。(1)

S→ABcA→a|εB→b|ε。解，因为FOLLOW(S)={#}

①文法不含左递归;FIRST(S)={a,b,c}

②对A→a|ε

候选式的FIRST集合互不相交;ε∈

FIRST(A)

但,FOLLOW(A)={b,c}FIRST(A)={a,ε}两者不相交。③B→b|ε其候选式的FIRST集合互不相交;ε∈

FIRST(B)

但，FOLLOW(B)={c}FIRST(B)={b,ε}两者也不相交。

所以，文法是LL(1)文法。CH.4.练习题3(P82.)3.下面文法中,哪些是LL(1)的,说明理由。(2)

S→AbA→a|B|εB→b|ε。解(1)

因为FOLLOW(S)={#}

对A→a|B|ε

;FIRST(S)={a,b}

FIRST(B)={b,ε}与FIRST(ε)={ε}相交;所以文法不是LL(1)文法。解(2)对A→a|ε因为ε∈FIRST(A)={a,b,ε}，FOLLOW(A)={b},FOLLOW和FIRST两者相交。所以文法不是LL(1)文法。CH.4.练习题3(P82.)3.下面文法中,哪些是LL(1)的,说明理由。(3)

S→ABBAA→a|εB→b|ε。解，虽然FOLLOW(S)={#}①文法不含左递归;FIRST(S)={a,b,ε}②对A→a|ε，其候选式的FIRST集合不相交;对B→b|ε，其候选式的FIRST集合也不相交;但对A→a|ε〔由B→b|ε出发证明也可〕FOLLOW(A)={a,b,#},FIRST(A)={a,ε}两者相交。所以，文法不是LL(1)文法。CH.4.练习题3(P82.)3.下面文法中,哪些是LL(1)的,说明理由。(4)

S→aSe|BB→bBe|CC→cCe|d。解，

因为

①文法不含左递归;②对S→aSe|B、B→bBe|C

和C→cCe|d

各产生式的候选式的FIRST集合均不相交;即

FIRST(aSe)∩FIRST(B)=

；

FIRST(bBe)∩FIRST(C)=

；

FIRST(cCe)∩FIRST(d)=

；

③FIRST(S)={a,b,c,d}，FIRST(B)={b,c,d}FIRST(C)={c,d}均不含ε。所以，文法是LL(1)文法。编译原理参考答案程序设计语言

Chapter7.语义分析和中间代码产生2023/2/2P217-1a*〔-b+c〕后缀式：ab-c+*a+b*〔c+d/e〕后缀式：abcde/+*+-a+b*〔-c+d〕后缀式：a-bc-d+*+notAornot〔CornotD〕后缀式：AnotCDnotornotor〔AandB〕or〔notCorD〕后缀式：ABandCnotDoror2023/2/2P217-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)2023/2/2P218-4自下而上分析过程中把赋值语句A:=B*〔-C+D〕翻译成三地址码的步骤：〔参看p179的语义子程序〕2023/2/2语法分析 翻译过程：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:=E7

S........产生一个新的中间变量T1E3.place=k5产生代码

k5:=uminusk3……名字属性地址ABCDT1T2T3……k1K2k3k4k5k6k7符号表2023/2/2A:=B*(-C+D)的三地址码k5:=uminusk3k6:=k5+k4k7:=k2*k6k1:=k7名字属性地址ABCDT1T2T3……k1K2k3k4k5k6k7符号表〔参看p179的语义子程序〕2023/2/2P218-6：用节的方法，把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，-，-，.〕TCFC2023/2/2P218-7100：〔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：用节的方法，把下面的语句翻译成四元式序列：whileA<CandB<DdoifA=1thenC:=C+1elsewhileA≤DdoA:=A+2;2023/2/2编译原理参考答案程序设计语言

Chapter8.–Chapter11.2023/2/2CH8.–CH11.1.什么是符号表？符号表有哪些重要作用？2.符号表的表项常包括哪些局部？各描述什么？3.有哪些存储分配策略？并表达何时用何种存储分配策略？4.代码优化的常用措施和优化的三个层次。2023/2/2编译原理参考答案程序设计语言

补充题2023/2/2补充题1.画出编译程序的总体逻辑构造图，简述各局部的主要功能。2023/2/2补充题2.文法G[Z]:Z→0U|1VU→1Z|1V→0Z|0请写出此文法描述的只含有４个符号的全部句子。G[Z]产生的语言是什么？该文法在Chomsky文法分类中属于几型文法？2023/2/2【解】〔1〕0101，0110，1010，1001〔2〕分析G[Z]所推导出的句子的特点：由Z开场的推导不外乎图1所示的四种情形。由Z推导出10或01后就终止或进入递归，而Z的每次递归将推导出一样的符号串：10或01。所以G[Z]产生的语言L(G[Z])={x|x∈(10|01)+}(3)该文法属于3型文法。Z→0U|1VU→1Z|1V→0Z|02023/2/2补充题3.文法和它的LR分析表如下，给出串dbdb#的LR分析过程。G[S]：(1)S→AdB(2)A→a(3)A→ε(4)B→b(5)B→Bdb(6)B→εACTIONGOTOadb#SAB0s3r3121acc2s43r24r6s5r665r4r46s7r17s88r5r5LR分析表2023/2/2【解】串dbdb#的LR分析过程如下：步骤状态符号输入串下一步的动作00#dbdb#

r3归约102#Adbdb#

s4移进2024#Adbdb#s5移进30245