18/19 学年 2 学期 编译原理B 试题标准答案 拟题学院（系）： 信息科学技术学院 拟 题 人： 宫生文 适用专业： 计算161-2 书写标准答案人： 宫生文 （答案要注明各个要点的评分标准）
一、单项选择题(请选择最确切的一项作为答案，每题1分，共10分)
1-5 ADDCA 6-10 DCBDC
二、填空题(每空1分，共10分)
1. 自上而下和自下而上（次序可换） 2.源程序 3.移进 接受 4.一张分析表 5. a/(b-c) 6. 编译执行和解释执行（次序可换） 是否生成目标代码 三、简答题（每题8分，共32分）
1、所求文法是G[S]: S→AC A→aaAbb | ab C→ccC | cc（视生成语言情况酌情给分） 2、短语：T、T*F、i、T+T*F、T+T*F+i;句柄：T；素短语：T*F、i；最左素短语：T*F（各2分） 3、FIRSTVT(S)={∨, ∧, i, - } FIRSTVT(T)={∧, i, -} FIRSTVT(U)={i, -} LASTVT(S)={∨, ∧, i, - } LASTVT(T)={∧, i, -} LASTVT(U)={i, -} （每错1项或者漏一项扣0.5分，共8）
4拓展给2分，每错写或者漏写1个项目集扣0.5分，项目集最多扣6分，共8分。
I1: S′?S· SaAbI2: S?a· S?a·Ab A?·1A0 ? A?·I4: S?aA·b AI8: S?aAb· I9: A?1A·0 01I5: A?1·A0 A?·1A0 ? A?·1I12: A?1A0· I0: S′?·S S?·a S?·aAb S?·b S?·bBa BbI3: S?b· S?b·Ba B?·1B0 ? B?·I6: S?bB·a aBI10: S?bBa· I11: B?1B·0 011I7: B?1·B0 B?·1B0 ? B?·I13: B?1B0·
四、计算题（每题15分，共45分）
1、（正
规式书写正确给6分，NFA画出来给4分，确定化为DFA给2分，共计12分） 2、（每问6分，视具体情况酌情给分）解：（1）FIRST(aBc)={a}, FIRST(bAB)={b} FIRST(aAb)={a}, A→b: FIRST(A→b)={b}, B→b: FIRST(b) = {b}, FIRST(ε)={ε} FOLLOW(A)={b, #}, FOOLOW(B)={c, #}
SELECT(S→aBc)={a}, SELECT(S→bAB) ={b}, SELECT(A→aAb)={a},
SELECT(A→b)={b}, SELECT(B→b)={b}, SELECT(B→?)={c, #}，select交集均为空。
因此，所得的LL(1)分析表如表下所示。
LL(1)分析表 S A B 3、拓广文法如下(2分)：
a b c # →aBc →bAB →aAb →b →b →? →? （0）S’ →S (1)S→aSAB (2)S→BA (3)A→aA (4)A→B (5)B→b
构造该文法的识别活前缀的DFA如下（每错写或者漏写1个项目集扣0.5分，项目集最多扣4分）：
FOLLOW（S）= FOLLOW（A）= FOLLOW（B）={a，b，$},该文法是SLR（1）文法。
该文法的SLR（1）分析表如下（6分，每错写或者漏写1个表项扣0.5分，项目集最多扣6分）
4. (1) DAG如右图所示6分)
n7 A _ n3 T1,T5, B + n1 S / n2 R n4 T3 n5 T4 n6 T4 n8 T6,B * (2) 四元式序列：(6分 T1:=S+R T4:=S/R A:=T1-T4 B:=T1*4
计算161-2编译原理试卷B答案
