编译原理样卷及答案

编译原理样卷及答案.--.可修编.一、简答题（每题4分，共24分）构造一个文法G，使得：L(G)={(m)m|m>0}解答：G[S]:s->()|(S)构造一个正规式，它接受={0，1}上符合以下规则的字符串：串有且只有2个1的0、1字符串全体。解答：0*10*10*消除文法G[S]中的直接左递归和回溯S→(L)|aS|aL→L，S|S解答：S→(L)|aS'S'→S|εL→SL'L'→，SL'|ε4、文法G[S]是乔姆斯基几型文法？S→ABS|ABAB→BAA→0B→1解答：1型文法/上下文有关文法5、按Thmopson算法构造...

.--.可修编.一、简答题（每题4分，共24分）构造一个文法G，使得：L(G)={(m)m|m>0}解答：G[S]:s->()|(S)构造一个正规式，它接受={0，1}上符合以下规则的字符串：串有且只有2个1的0、1字符串全体。解答：0*10*10*消除文法G[S]中的直接左递归和回溯S→(L)|aS|aL→L，S|S解答：S→(L)|aS'S'→S|εL→SL'L'→，SL'|ε4、文法G[S]是乔姆斯基几型文法？S→ABS|ABAB→BAA→0B→1解答：1型文法/上下文有关文法5、按Thmopson算法构造与正则表达式(1*|0)*等价的NFA。解答：略6、设计一个状态转换图，其描述的语言规则为：如果以a开头，则其后是由a、b组成的任意符号串；如果以b开头，则其后是至少包含一个a的由a、b组成的任意符号串。解答：略二、（本题10分）对于文法G[E]：E→ET+|TT→TF*|FF→F^|a(1)给出句子FF^^*的最左推导和语法树；(2)给出句子FF^^*的短语、直接短语和句柄。解答：(1)2分：句子FF^^*的最左推导2分：句子FF^^*的语法树E=>T=>TF*=>FF*=>FF^*=>FF^^*(2)3分:句子FF^^*的短语FF^^*、FF^^*、F、F^、F^^2分:句子FF^^*的直接短语F、F^1分:句子FF^^*的句柄F三、（本题15分）构造与下列NFA等价的最小化DFA。解答：（1）10分：构造与NFA等价的DFA（2）5分：对DFA最小化首先，将所有的状态集合分成子集：k1={0,1,2,4}k2={3,5}四、（本题15分）对下列文法G[S]：s→eT|RTT→DR|εR→dR|εD→a|bd(1)写出文法G[S]每个非终结符的FIRST集和FOLLOW集；(2)判断文法G[S]是否LL(1)文法（注：必须给出判断过程，否则不得分）；(3)写出文法文法G[S]的预测分析表。解答：（1）8分：每个First集合和FOLLOW集合各1分FIRST集FOLLOW集s→eT|RT{e}{a,b,d,ε}#T→DR|ε{a,b}{ε}#R→dR|ε{d}{ε}a,b,#D→a|bd{a}{b}D,#(2)2分：判断文法G[S]是LL(1)文法。对于产生式s→eT|RT：FIRST(eT)∩FIRST(RT)-ε={e}∩{a,b,d}=ΦFIRST(eT)∩FOLLOW(S)={e}∩{#}=Φ对于产生式T→DR|ε：FIRST(DR)∩FOLLOW(T)={a,b}∩{#}=Φ`对于产生式R→dR|ε：FIRST(dR)∩FOLLOW(R)={d}∩{a,b,#}=Φ对于产生式D→a|bd：FIRST(a)∩FIRST(bd)={a}∩{b}=Φ所以，对于文法G[S]是LL(1)文法。(3)5分：文法G[S]的预测分析表。五、（本题18分）已知文法G[S]：S→rDD→D，i|i(1)画出识别文法活前缀的完整DFA，并判断该文法是否LR(0)文法(必须说明判断依据)；(2)构造该文法的SLR(1)分析表，并判断该文法是否SLR(1)文法(必须说明判断依据)。解答：(1)8分：画出识别文法活前缀的完整DFA文法拓展并对产生式编号：（0）S'→S（1）S→rD（2）D→D，i（3）D→i(2)2分：判断该文法不是LR(0)文法对于状态3，项目集中存在“移进-规约”冲突，所以该文法不是LR(0)文法。(3)6分：构造该文法的SLR(1)分析表状态ACTIONGOTOr，i#SD0S211acc2S433S5r14r3r35S66r2r2(4)2分：判断文法是SLR(1)分析表回答1：因为SLR(1)分析表不存在冲突，所以文法是SLR(1)分析表。回答2：对于状态3，FOLLOW(S)∩{,}=(#)∩{,}=Ф，“移进-规约”冲突可以用SLR(1)方法解决，所以文法是SLR(1)分析表。六、（本题8分）文法G[E]的LR分析表如下图所示：(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(6)F→i写出对输入串i*i+i的LR分析过程(即状态，符号，输入串的变化过程)。解答:七、（本题10分）写出下列语句的四元式序列if(y>z&&(cn))while(a>b)x=x+y*a;elsem=m+n;解答：1(j>,y,z,3)2(j,-,-,13)3(j<,c,d,7)4(j,-,-,5)5(j>,m,n,7)6(j,-,-,13)7(j>,a,b,9)8(j,-,-,13/16)9(*,y,a,t0)10(+,x,t0,t1)11(=,t1,-,x)12(j,-,-,7)13(j,-,-,16)14(-,x,1,t5)15(=,t5,-,x)16..........

                    本文档为【编译原理样卷及答案】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

编译原理样卷及答案

你可能还喜欢