资源描述：
《《编译原理》样卷及答案教学文案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、…………………………………………………………最新精品资料推荐……………………………………………………一、简答题（每题4分，共24分）1、构造一个文法G，使得：L(G)={(m)m
2、m>0}解答：G[S]:s->()
3、(S)2、构造一个正规式，它接受S={0，1}上符合以下规则的字符串：串内有且只有2个1的0、1字符串全体。解答：0*10*10*3、消除文法G[S]中的直接左递归和回溯S→(L)
4、aS
5、aL→L，S
6、S解答：S→(L)
7、aS'S'→S
8、εL→SL'L'→，SL'
9、ε4、文法G[S]是乔姆斯基几型文法？S→ABS
10、ABAB→BAA→0B→1解答：1型文法/上下文有关文法……………
11、……………………………………………最新精品资料推荐……………………………………………………11…………………………………………………………最新精品资料推荐……………………………………………………5、按Thmopson算法构造与正则表达式(1*
12、0)*等价的NFA。解答：略6、设计一个状态转换图，其描述的语言规则为：如果以a开头，则其后是由a、b组成的任意符号串；如果以b开头，则其后是至少包含一个a的由a、b组成的任意符号串。解答：略二、（本题10分）对于文法G[E]：E→ET+
13、TT→TF*
14、FF→F^
15、a(1)给出句子FF^^*的最左推导和语法树；(2)给出句子FF^^*的短语、直接短语和
16、句柄。解答：(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…………………………………………………………最新精品资料推荐……………………………………………………11…………………………………………………………最新精品资料推荐……………………………………………………三、（本题15分）构造与下列NFA等价的最小化DFA。解答：（1）10分：构造与NFA等价的DFA（2）5分：对DFA最小化首
17、先，将所有的状态集合分成子集：k1={0,1,2,4}k2={3,5}…………………………………………………………最新精品资料推荐……………………………………………………11…………………………………………………………最新精品资料推荐………………………………………………………………………………………………………………最新精品资料推荐……………………………………………………11…………………………………………………………最新精品资料推荐……………………………………………………四、（本题15分）对下列文法G[S]：s→eT
18、RTT→DR
19、εR→dR
20、εD→a
21、bd(1)写出文法G[S]每个非终结
22、符的FIRST集和FOLLOW集；(2)判断文法G[S]是否LL(1)文法（注：必须给出判断过程，否则不得分）；(3)写出文法文法G[S]的预测分析表。解答：（1）8分：每个First集合和FOLLOW集合各1分FIRST集FOLLOW集s→eT
23、RT{e}{a,b,d,ε}#T→DR
24、ε{a,b}{ε}#R→dR
25、ε{d}{ε}a,b,#D→a
26、bd{a}{b}D,#(2)2分：判断文法G[S]是LL(1)文法。对于产生式s→eT
27、RT：FIRST(eT)∩FIRST(RT)-ε={e}∩{a,b,d}=ΦFIRST(eT)∩FOLLOW(S)={e}∩{#}=Φ对于产生式T→DR
28、ε：F
29、IRST(DR)∩FOLLOW(T)={a,b}∩{#}=Φ`…………………………………………………………最新精品资料推荐……………………………………………………11…………………………………………………………最新精品资料推荐……………………………………………………对于产生式R→dR
30、ε：FIRST(dR)∩FOLLOW(R)={d}∩{a,b,#}=Φ对于产生式D→a
31、bd：FIRST(a)∩FIRST(bd)={a}∩{b}=Φ所以，对于文法G[S]是LL(1)文法。(3)5分：文法G[S]的预测分析表。五、（本题18分）已知文法G[S]：S→rDD→D，i
32、i(1)画出识别文法活前缀的
33、完整DFA，并判断该文法是否LR(0)文法(必须说明判断依据)；(2)构造该文法的SLR(1)分析表，并判断该文法是否SLR(1)文法(必须说明判断依据)。解答：(1)8分：画出识别文法活前缀的完整DFA文法拓展并对产生式编号：（0）S'→S（1）S→rD（2）D→D，i（3）D→i…………………………………………………………最新精品资料推荐……………………………………………………11………………………………
