2010年编译原理期中试题(answer).doc

厦门大学编译原理课程期中试卷计算机科学系2007年级计算机科学与技术专业姓名： 学号： 成绩： 1(20分) (1)写出字母表S = a, b上语言L = w | w中a的个数是偶数的正则表达式，并给出接受该语言的最小状态DFA。 状态0表示已接收了偶数个a，状态1表示已接收了奇数个a，0为终止状态。由于状态0是终态，而状态1不是终态，二者是可区分的，图1已经是最小终态的DFA。图1.正规表达式：(b|ab*a)*(b*ab*ab*)* | b*（注意：直接给出DFA即可，不必从正规表达式出发构造e-NFA，然后再化简e-NFA。） (2) 构造一个DFA，它接收=0,1上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正则表达式。 (10 | 0)*2(20分) 为下面的语言设计文法：（1） L1 = w | wa, b*，且a的个数是b的个数的两倍S aSaSbS | aSbSaS | bSaSaS | e（2） L2= wwR | wa, b*，wR表示w的反转（reverse）S aSa | bSb | e3(10分) 设有句型gaabb ，且在此句型的推导过程中用到产生式A aa，分别指出LL(1)方法和LR(1)方法在扫描到此句型的什么位置时决定用此产生式？4(20分)已知描述二叉树的文法如下： T n(T, T ) | e其中，空二叉树对应的符号串为e，只有一个结点的二叉树对应的符号串为n(,)。（1） 构造该文法的LR(0)项目集规范族。（2） 构造识别所有活前缀的DFA。（3） 判断该文法是不是SLR(1)文法。若不是，请描述出冲突。如果是，则构造SLR(1)分析表。解：(1) 构造拓广文法的LR(0)项目集规范族如下：I0: T. TI4: T n (T., T )T .n(T, T )T . I5: T n (T, .T )I1: T T. T .n(T, T )I2: T n. (T, T ) T .I3: T n (.T, T ) T .n(T, T ) I6: T n (T, T. )T .I7: T n (T, T ) .(3) 计算FOLLOW(T) = $, , ），构造该文法的SLR(1)分析表如下：ACTIONGOTOn(),$TI0s2r2r2r21I1accI2s3I3s2r2r2r24I4s5I5s2r2r2r26I6s7I7r1r1r15. （20分）语法部分考虑以下文法：SAaA| bAb请问：（1）该文法是LL（1）的吗？说明理由。（2）该文法是LR（1）的吗？说明理由。（提示：不需构造分析表，根据LR分析器原理即可回答）（3）在Chomsky文法体系中，描写该文法产生的语言的最小的类别是什么？(1) FIRST(S) = a, b FIRST(A) = e, bFOLLOW(S) = $ FOLLOW(A) = a, b FOLLOW(A) FIRST(bAb) = b该文法的LL(1)分析表如下：ab$SSAaSAaAAAA bAbLL(1)分析表中存在多重定义表目，因此，该文法不是LL(1)文法。(2) 构造文法的LR（1）项目集规范族：A b. Ab, a A . ,bA .b Ab, b bI0: S. S , $S . A a, $A . ,aA . bAb, a该状态存在移进/归约冲突，该文法不是LR（1）文法。（3）该文法生成的语言是(bb)*a，属于正则语言（3型语言）。