编译原理样卷及答案

《编译原理样卷及答案》由会员分享，可在线阅读，更多相关《编译原理样卷及答案（9页珍藏版）》请在装配图网上搜索。

1、一、简答题（每题4 分，共 24 分）mm1、 构造一个文法G，使得： L(G)= () | m0解答：GS: s- ()|(S)2、 构造一个正规式，它接受=0 ，1 上符合以下规则的字符串：串内有且只有2 个 1 的0、 1 字符串全体。解答：0*10*10*3、 消除文法 GS 中的直接左递归和回溯S (L) | aS | a LL，S|S解答：S (L) | aSS S |LSLL ， S L |4、 文法 GS 是乔姆斯基几型文法S ABS|AB AB BAA 0 B 1解答： 1 型文法 / 上下文有关文法、Thmopson*5按算法构造与正则表达式(1 |0)等价的。解答：略6、

2、设计一个状态转换图，其描述的语言规则为：如果以a 开头，则其后是由a、b 组成的任意符号串；如果以b 开头，则其后是至少包含一个a 的由 a、 b 组成的任意符号串。解答：略二、（本题 10 分）对于文法GE ：EET+|TTTF* | FFF | a(1) 给出句子 FF* 的最左推导和语法树；(2) 给出句子 FF* 的短语、直接短语和句柄。解答：(1) 2分：句子 FF* 的最左推导2分：句子 FF* 的语法树E=T=TF*=FF*=FF*=FF*(2) 3分 : 句子 FF* 的短语FF*、 FF* 、 F、F、 F2 分 : 句子 FF* 的直接短语F、 F1分 : 句子 FF* 的

3、句柄F三、（本题 15 分）构造与下列NFA等价的最小化DFA。解答：（ 1）10 分：构造与NFA等价的 DFA（2） 5 分：对 DFA最小化首先，将所有的状态集合分成子集：k1=0,1,2,4k2=3,5四、（本题 15 分）对下列文法GS ：s eT | RTT DR |R dR |D a | bd(1) 写出文法 GS 每个非终结符的 FIRST 集和 FOLLOW集；(2)判断文法GS 是否 LL(1) 文法（注：必须给出判断过程，否则不得分）；(3) 写出文法文法 GS 的预测分析表。解答：（ 1） 8 分：每个First集合和 FOLLOW集合各 1 分FIRST集FOLLOW

4、集s eT e #| RT a, b, d,T DRa, b#|R dR d a,b,#|D a aD,#| bd bGS 是 LL(1)文法。(2)2分：判断 文 法对于产生式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)=da,b,#=对于产生式D a | bd： FIRST(a) FIRST(bd)=a b= 所以，对于文法GS 是 LL(1) 文法。(3) 5分

5、：文法GS 的预测分析表。五、（本题 18 分）已知文法GS ：S r DD D ，i | i(1)画出识别文法活前缀的完整DFA，并判断该文法是否 LR(0) 文法 ( 必须说明判断依据 ) ；(2)构造该文法的 SLR(1) 分析表，并判断该文法是否SLR(1) 文法 ( 必须说明判断依据 ) 。解答：(1) 8分：画出识别文法活前缀的完整DFA文法拓展并对产生式编号：（0）S S（1）S r D（2）D D ，i（3）D i(2) 2分：判断该文法不是LR(0) 文法对于状态3，项目集中存在“移进- 规约”冲突，所以该文法不是LR(0) 文法。(3) 6分：构造该文法的 SLR(1) 分

6、析表ACTIONGOTO状态r，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(yz & (cn)while(ab)x=x+y*a;elsem=m+n;解答：1 (j, y, z, 3)2 (j , -,-, 13)3 (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 .