《编译原理》样卷及答案

一、简答题（每题4分，共24分）1、 构造一个文法G，使得：L(G)=(m )m|m>0 解答： GS: s-> ()|(S)2、 构造一个正规式，它接受S=0，1上符合以下规则的字符串： 串内有且只有2个1的0、1字符串全体。解答： 0*10*10*3、 消除文法GS中的直接左递归和回溯 S (L) | aS | aL L，S | S解答： S (L) | aS'S' S | L S L'L'，S L' | 4、 文法GS是乔姆斯基几型文法？ S ABS | AB AB BA A 0 B 1解答：1型文法/上下文有关文法5、按Thmopson算法构造与正则表达式 (1*|0) * 等价的NFA。解答：略6、设计一个状态转换图，其描述的语言规则为：如果以a开头，则其后是由a、b组成的任意符号串；如果以b开头，则其后是至少包含一个a的由a、b组成的任意符号串。解答：略二、（本题10分）对于文法GE：EET+|T TTF* | F FF | 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分）对下列文法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集s eT | RT e a, b, d, #T DR | a, b #R dR | d a,b,#D a | bd a bD,# (2) 2分： 判断文法GS是LL(1)文法。 对于产生式s eT | RT：FIRST(eT)FIRST(RT)- =ea,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)=ab= 所以，对于文法GS是LL(1)文法。 (3) 5分：文法GS的预测分析表。五、（本题18分）已知文法GS：S r D D 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)分析表状态ACTIONGOTOr ，i#SD0S211acc2S433S5r14r3r35S66r2r2 (4) 2分：判断文法是SLR(1)分析表 回答1： 因为SLR(1)分析表不存在冲突，所以文法是SLR(1)分析表。 回答2： 对于状态3， FOLLOW(S),=(#),=，“移进-规约”冲突可以用 SLR(1)方法解决，所以文法是SLR(1)分析表。六、（本题8分）文法GE的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 && (c<d | m>n) while(a>b) x=x+y*a; else m=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 .