编译原理计算题

编译原理计算题1、写一个文法，使其语言是奇数集，且每个奇数不以0开头。(5分)2、 设文法G(S)：Sf(L)|aS|aL-L,S|S消除左递归和回溯；计算每个非终结符的FIRST和FOLLOW；构造预测分析表。3、 Whilea>0Vb<0doBeginX：=X+1；ifa>0thena：=a—lelseb：=b+lEnd；翻译成四元式序列。(7分)4、 已知文法G(E)E-T|E+TT-F|T*FF-(E)|i(1)给出句型(T*F+i)的最右推导及画出语法树；⑵给出句型(T*F+i)的短语、素短语。(7分)5、设布尔表达式的文法为E—E(1)VE(2)E-E(1)AE(2)E—i假定它们将用于条件控制语句中，请(1)改写文法，使之适合进行语法制导翻译和实现回填；(2)写出改写后的短个产生式的语义动作。(6分)6、设有基本块Tl：=2T2：=10/TT3：=S—RT4：=S+RA：=T2*T4B：AT5：=S+RT6：=T3*T5B：=T6⑴画出DAG图；(2)假设基本块出口时只有A,B还被引用，请写出优化后的四元序列。(6分)7、已知文法G(S)S—a|Al(T)写出句子((a,a),a)的规范归约过程及每一步的句柄。8、已知文法G(S):S-a|(T)T-T,S|S的优先关系表如下:关系a()aJJ(<<=<)>><<>>请计算出该优先关系表所对应的优先函数表。9、写一个文法,使其语言是偶数集,且每个偶数不以0开头。(5分)10、已知文法G(S):S—a|Al(T)T—T,S|S⑴给出句子(a,(a,a))的最左推导并画出语法树；⑵给出句型((T,S),a)的短语、直接短语、句柄。(8分)11、把语句ifx>0Ay>0thenz:=x+yelsebeginx:=x+2;y:=y+3END;翻译成四元式序列。(6分)12、设某语言的for语句的形式为fori:=E(1)TOE(2)doS其语义解释为i:=E(1);LIMIT:=E(2);again:ifi<=LIMITthenBEGINS;i:=i+1;gotoagainEND;⑴写出适合语法制导翻译的产生式；⑵写出每个产生式对应的语义动作。(6分)13、设文法G(S):S—S+aF|aF|+aFFf*aF|*a⑴消除左递归和回溯；⑵构造相应的FIRST和FOLLOW集合;⑶构造预测分析表(10分)14、对以下基本块T1:=2T2:=A-BT3:=A+BT4:=T2*T3T5:=3*T1T6:=A-BL:=A+BT7:=T6*LT8:=T5*4M:=T8+T7L:=M

⑴画出DAG图；⑵假设只有L在基本块出口之后还被引用，请写出优化后的四元式序列。（6分）15、（8分）化简文法G[S]S—ASe|BCaD|aD|ACA—Cb|DBSC—bC|dB—AcD—aD16、（12分）设Li{a,b,c}*是满足下述条件的符号串构成的语言:（1） 若出现a，则其后至少紧跟两个c；（2） 若出现b，其后至少紧跟一个c。试构造识别L的最小化的DFA，并给出描述L的正规表达式。-qbP|q17、（12分）已给文法G[S]:S-SaP|-qbP|q将G[S]改造成LL（1）文法，并给出LL（1）分析表。18、（12分）给定文法G[S]:S-Aa|dAb|Bb|dBaA-cB构造文法G[S]的LR（1）分析表。19、（8分）将下面的条件语句表示成逆波兰式和四元式序列ifa>bthenx:=a+b*celsex:=b-a;

20、(8分)给定基本块：A:=3*5B:=E+FC:=A+12D:=E+FA:=D+12C:=C+1E:=E+FE是活跃的，给出用DAG图完成优假定出基本块后，只有AE是活跃的，给出用DAG图完成优1、写一个文法，使其语言是奇数集，且每个奇数不以0开头。(5分)解：文法G(N)：N—AB|BA—AC|DB—l|3|5|7|9D—B|2|4I6I8CfO|D (5分)2、设文法G(S)：Sf(L)|aS|aL—L,SIS(1)消除左递归和回溯；计算每个非终结符的FIRST和FOLLOW；构造预测分析表。解：(1)S—(L)|aS'SJS|£L—SL'LJSL'|£评分细则：消除左递归2分,提公共因子2分。

FIRST)S)={(,a}FIRST(S')={,FIRST)S)={(,a}FIRST(S')={,a,£}FIRST(L)={(,a}FIRST(L')={,,£}FIRST(L')={,,£}FOLLOW(L'〕={)}3、Whilea>0VbVOdoBeginX：=X+1；ifa>0thena：=a—1elseb：=b+1End；翻译成四元式序列。(7分)解：(j>，a，0，5)(j，－，－，3)(jV,b,0,5)(j，－，－，15)(+,x,1,T1)(:=,T1,—,x)(j>,a,0,9)(j，—，—，12)(—，a，1，T2)(：=，T2，—，a)(j，—，—，1)(＋，b，1，T3)(：=，T3，—，b)(j，—，—，1)(15)评分细则：控制结构4分，其它3分。4、已知文法G(E)E—T|E+TT—F|T*FF-(E)|i给出句型(T*F+i)的最右推导及画出语法树;给出句型(T*F+i)的短语、素短语。(7分)解：(1)最右推导：ETF(E)(E+T)(E+F)(E+i)(T+i)(T*F+i)(2)短语：(T*F+i)，T*F+i，T*F，i (2分)(1分)(1分)5、设布尔表达式的文法为E—E(1)VE(2)E—E(1)AE(2)E—i假定它们将用于条件控制语句中，请改写文法，使之适合进行语法制导翻译和实现回填；写出改写后的短个产生式的语义动作。(6分)解：(1)E0—E(1)E—E0E(2)EA—E(1)E—EAE(2)E—i (3分)(2)E—E(1){BACKPATCH(E(1)・FC,NXQ)；EO・TC：=E(1)・TC}E—E0E(2){E・FC：=E(2)・FC；E・TC：=MERG(EO・TC,E(2)・TC)}EA—E(1){BACKPATCH(E(1)・TC,NXQ)；E0・FC：=E(1)・FC}E—EAE(2){E・TC：=E(2)・TC；E・FC：=MERG(EA・FC,E(2)・FC}E—i{E・TC：=NXQ；E・FC：=NXQ+1；GEN(jn2,entry(i),－0)；GEN(j,－,－,0) (3分)6、设有基本块T1：=2T2：=10/TT3：=S-RT4：=S+RA：=T2*T4B：AT5：=S+RT6：=T3*T5B：=T6画出DAG图；假设基本块出口时只有A,B还被引用，请写出优化后的四元序列。(6分)

解：(l)DAG：(2)优化后的四元式T3：=S—RT4：=S+RA：=5*T4(3分)B：=T3(3分)7、已知文法G(S)S—a|Al(T)T—T,SIS写出句子((a,a),a)的规范归约过程及每一步的句柄。句型归约规则((a,a)句型归约规则((a,a),a)S—a((S,a),a)T—S((T,a),a)S—a((T,S),a)T—T,S((S),a)T—S((T),a)S—S(T)(S,a)T—S(T,a)S—a(T,S)T—T,S(T)S—(T)句柄aSaT,SS(T)SaT,S(T)(4分)8、答：优先函数表如下f函数2分，g函数2分)10、已知文法G(S):S—a|Al(T)T—T,S|S⑴给出句子(a,(a,a))的最左推导并画出语法树；⑵给出句型((T,S),a)的短语、直接短语、句柄。(8分)11、把语句ifx>0Ay>0thenz:=x+yelsebeginx:=x+2;y:=y+3END;翻译成四元式序列。(6分)12、 设某语言的for语句的形式为fori:=E(1)TOE(2)doS其语义解释为i:=E(1);LIMIT:=E(2);again:ifi<=LIMITthenBEGINS;i:=i+1;gotoagainEND;⑴写出适合语法制导翻译的产生式；⑵写出每个产生式对应的语义动作。(6分)13、 设文法G(S):S—S+aF|aF|+aFFf*aF|*a⑴消除左递归和回溯；⑵构造相应的FIRST和FOLLOW集合；⑶构造预测分析表(10分)14、对以下基本块T1:=2T2:=A-BT3:=A+BT4:=T2*T3T5:=3*T1T6:=A-BL:=A+BT7:=T6*LT8:=T5*4M:=T8+T7L:=M⑴画出DAG图；⑵假设只有L在基本块出口之后还被引用，请写出优化后的四元式序列。(6分)9、答：文法G(S):S-AB|B|A0A—AD|CB-2|4|6|8Cfl|3|5|7|9|B

D-O|C10、答：最左推导：(2分)S=>(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,a))语法树：(2分，此处略)11、答：⑴(j>,x,0,3)⑵(j,-,-,8)⑶(j>,y,0,5)⑷(j,-,-,8)⑸(+,x,y,T1)⑹(:=,T1,-,Z)⑺(j,-,-,12)⑻(+,x,2,T2)⑼(:=,t2,-,X)⑽(+,Y,3,t3)(:=,T3,-,y)(12)(控制结构3分，其它3分)12、答：⑴(2分)Fffori:=E(1)toE(2)doS-FS(1)⑵(每个语义动作2分)F-fori:=E(1)toE(2)do{GEN(:=,E(1).place,-,entry(i));F.place:=entry(i);LIMIT:=Newtemp;GEN(:=,E(2).place,-,LIMIT);:=NXQ;F.QUAD:=q;GEN(jW,entry(i),LIMIT,q+2)F.chain:=NXQ;G)j,-,-,0)}S-FS(1){BACKPATCH(S(1).chain,NXQ);GEN(+,F.place,1,F.place);GEN(j,-,-,F.QUAD);S.chain:=F.chain}13、答:⑴(消除左递归2分，提公共左因子2分)S-aFS'1+aFS'S'f+aFS'|£F_*aF'F'—F|£⑵(3分)FIRST(S)二{a,+}FOLLOW(S)二{#}FIRST(S')二{+,£}FOLLOW(S')二{#}FIRST(F)={*}FOLLOW(F)二{+,#}FIRST(F')={*,£)FOLLOW(F')二{+,#}⑶(3分)一a+*#SS-aFS'S-+aFS'一一S'一S'-+aFS'一S'-eF一一F—*aF'一F'一F'-eF'—FF'-e14、 答：⑴DAG（3分，此处略）⑵四元式序列：（3分）T2:=A-BT3:=A+BT4:=T2*T3L:=T4+2415、 化简后：S—ASe|ACA—CbC—bC|d16、 DFA如图所示。相应的正规式为（c|acc|bc）*。217、改造后的文法：S-PS'S'-aPS'lfS'|eP-qP'P'-bP|e各候选式的FIRST集，各非终结符的FOLLOW集为产生式FIRST集FOLLOW集

SfPS'{q}{#}S'faPS'ffS'fe{a}{f}{e}{#}PfqP'{q}{a,f,#}P'fbPfe{b}{e}{a,f,#}LL(1)分析表为bf■1ssnaPS1fS1ETP1EE■MP1：'E18、分析表如下图所示状峦JETTONGOTCiabcdasA