《编译原理》样卷及答案

《编译原理》样卷及答案

ID:38910984

大小:2.88 MB

页数:9页

时间:2019-06-21

《编译原理》样卷及答案_第1页
《编译原理》样卷及答案_第2页
《编译原理》样卷及答案_第3页
《编译原理》样卷及答案_第4页
《编译原理》样卷及答案_第5页
资源描述:

《《编译原理》样卷及答案》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

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型文法/上下文有关文法5、按Thmopson算法构造与正则表达式(1*

11、0)*等价的NFA。解答:略96

12、、设计一个状态转换图,其描述的语言规则为:如果以a开头,则其后是由a、b组成的任意符号串;如果以b开头,则其后是至少包含一个a的由a、b组成的任意符号串。解答:略二、(本题10分)对于文法G[E]:E→ET+

13、TT→TF*

14、FF→F^

15、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分:

16、句子FF^^*的句柄F9三、(本题15分)构造与下列NFA等价的最小化DFA。解答:(1)10分:构造与NFA等价的DFA(2)5分:对DFA最小化首先,将所有的状态集合分成子集:k1={0,1,2,4}k2={3,5}9四、(本题15分)对下列文法G[S]:s→eT

17、RTT→DR

18、εR→dR

19、εD→a

20、bd(1)写出文法G[S]每个非终结符的FIRST集和FOLLOW集;(2)判断文法G[S]是否LL(1)文法(注:必须给出判断过程,否则不得分);(3)写出文法文法G[S]的预测分析表。解答:(1)8分:每个First集合和FOLLOW集合各1分9FIRST集F

21、OLLOW集s→eT

22、RT{e}{a,b,d,ε}#T→DR

23、ε{a,b}{ε}#R→dR

24、ε{d}{ε}a,b,#D→a

25、bd{a}{b}D,#(2)2分:判断文法G[S]是LL(1)文法。对于产生式s→eT

26、RT:FIRST(eT)∩FIRST(RT)-ε={e}∩{a,b,d}=ΦFIRST(eT)∩FOLLOW(S)={e}∩{#}=Φ对于产生式T→DR

27、ε:FIRST(DR)∩FOLLOW(T)={a,b}∩{#}=Φ`对于产生式R→dR

28、ε:FIRST(dR)∩FOLLOW(R)={d}∩{a,b,#}=Φ对于产生式D→a

29、bd:FIRST(a)∩FI

30、RST(bd)={a}∩{b}=Φ所以,对于文法G[S]是LL(1)文法。(3)5分:文法G[S]的预测分析表。9五、(本题18分)已知文法G[S]:S→rDD→D,i

31、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,项目集中存在“移进-规约”冲突,所以

32、该文法不是LR(0)文法。(3)6分:构造该文法的SLR(1)分析表状态ACTIONGOTOr,i#SD0S211acc2S4393S5r14r3r35S66r2r2(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写出对输入串

33、i*i+i的LR分析过程(即状态,符号,输入串的变化过程)。9解答:七、(本题10分)写出下列语句的四元式序列if(y>z&&(c

34、

35、m>n))while(a>b)x=x+y*a;elsem=m+n;9解答: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....

36、.....

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。