《编译原理》样卷及答案

1、编译原理样卷及答案一、简答题(每题4分，共24分)1、构造一个文法G,使得：L (G) = (,n),n | m0解答： GS : s- () I (S)2、构造一个正规式，它接受S=0, 1上符合 以下规则的字符串：串内有且只有2个1的 0、1字符串全体。解答： 0*10*10*3、消除文法GS中的直接左递归和回溯Sf (L) I aS I aLf L, SIS解答：s- (L)laS*SJ SlL SLLf SLl4、文法GS是乔姆斯基几型文法?S-ABS|ABAB-BAA-0解答：1型文法/上下文有关文法5、按Thmopson算法构造与正则表达式(1*|0)*等价 的 NFAo解答6、如

2、t甘一个状态 以a ;如a、b组成的任意符p中。解答二、(本题10分)对于文法GE：E-ET+|TT-TF* | FF-FA | a(1) 给出句子FF的最左推导和语法树；(2) 给出句子Fi的短语、直接短语和句柄。(1) 2分：句子 句子的语法树PPA 人* 的最左推导E=T=TF*=FF*=FFA*=FFAA*(2) 3分：句子FF*的短语ff“*、FF*、F、Fa Faa 2分:句子 FF* 的直接短语F、FA1分:句子FF*的句柄三、(本题15分)构造与下列NFA等价的最小 化 DFA。iI.(SAB0JC11221nwq3RB2冏12(D,E 刀3(H.454554S解答：（1） 1

3、0分：构造与NFA 等价的DFA（2） 5分：对DFA最小化首先，将所有的状态集合分成子集: kl=0,lz2z4k2=3z5在Kt=0, 1 2, 4中，因为状态1、4没有a输人，而其它状态均有a输人, 折以将状态K1分割成Ku=0, 2和 Kir=K 4在状态2中.有O.=1eK22产1心2t）=2eK|j 所以状态0与状态2等价，在状态集K萨1, 4中，有Ib=3Kj弘书丘所以状态1与状态4是否等价取决于状态3和状杰5是否竽价.在状杰集Kr=3, 5中，有3t=4Ki25a=4eKn3b=5eK25b=5GK2折以状态3与状杰5等价，从而状恚I与状态4等价.最终将K分割戍三个不相交的子集

4、 （0.為、I, 4、3, 5.选0, 2中的0作为代表.，原来由状态2导入（出）体余狀态的孤改为由狀 态0导人（出：逸】，4中的丨作为代埶 原来由狀态4导人（tfa）其余状态的 炎改为由状态1导入（出）：选3, 5中的3作为代表，原来由状态5导人（出） 其余状态的弧改为由状态3导入（岀）；然后洎去其余伏态.最小化后的状态图如 图所示四、（本题15分）对下列文法GS：eT I RTT DR I R dR I wD a I bd(1) 写出文法GS每个非终结符的FIRST 集和FOLLOW集；(2) 判断文法GS是否LL(1)文法(注：必 须给出判断过程，否则不得分)；(3) 写出文法文法GS的

5、预测分析表。解答：(1) 8分：每个First集合和FOLLOW 集合各1分FIRST 集6FOLLOW集s eTIRTe a, b, d, e#Tt DRa,b#1 ERdRda,b,#1 打D aaD,#Ibdb(2) 2 分:判断文法G S是LL文法。对于产生式 st eT I RT： FIRST (eT) Cl FIRST (RT) - =e D a, b, d二FIRST (eT)PIFOLLOW(S)=e D #二对于产生式 Tt DR I e： FIRST (DR) Cl FOLLOW(T)=a,b D # = 对于产生式 Rt dR I ： FIRST (dR) Cl FOLL

6、OW (R)=d Cl a, b, #二对于产生式 D- a I bd： FIRST (a) Cl FIRST(bd)=a Cl b二所以，对于文法GS是LL(1)文法。(3) 5分:文法GS的预测分析表。abdc#SRTRTRTeTRTTDRDRR8dREDabd五、(本题18分)已知文法GS：S-rD(1)画出识别文法活前缀的完整DFA,并判断该文法是否LR(O)文法(必须说明判断依据)； 构造该文法的SLR分析表，并判断该文 法是否SLR(1)文法(必须说明判断依据)o 解答：(1) 8分：画出识别文法活前缀的完整DFA文法拓展并对产生式编号:D i(O) S JS (1) S-rD(2

7、) 2分：判断该文法不是LR(O)文法 对于状态3,项目集中存在“移进-规约”冲突，所以该文法不是LR(O)文法。(3) 6分：构造该文法的SLR(1)分析表状态ACTIONGOTOr91#SD0S211acc2S433S5rl4r3r35S66r2r2(4) 2分:判断文法是SLR分析表回答1：因为SLR (1)分析表不存在冲 突，所以文法是SLR(l)分析表。回答2： 对于状态3, FOLLOWCI 移进-规约”冲突可以用SLR (1)方法解决，所以文法是SLR分析表。六二(本题8分)文法Ge的LR分析表如下图(1)E E+T(2)E T(3)TT*F(4)T F(5)F (E)(6)F写

8、出对输入备i*i + i的LR分析过程(即状 态，符号，输入串的变化过程)。解答:状态符号输入串(1)0#i*i+i#(2)05#i*i+l#(3)03#F* i + i #(4)02#T*i + i#(5)027#T*i + i#(6)0275#T*i+ i#(7)02710#T*FH#(8)02#T+ j#(9)01#E+ i#状态ACTION(动作)GOTO(转换)/+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5七、(本题10分)写出下列语句的四元式序列if(yz & (cn)while(ab)x=x+y*a;elsem=m+n;解答:2345678910111213141516(j， 厶 3) (j，丁，13)