文档介绍：编译原理试题答案及评分参考( B卷) (课程代号: 9047 ) 一、单项选择题题号 123456789 10 答案 DDDACADA 题号 11 12 13 14 15 16 17 18 19 20 答案 CABADA 二、多项选则题题号 12345 答案 BCE BCDE BCD AE BD 三、填空题 26. 源程序, 目标程序 27. 0 型、 1 型、 2 型, 3 型文法 28. 规范句型, 句柄 29. 从左到右, 最左归约 30. 非终结四、计算题 31. 答: 句型(SdSdS) 的语法树如下所示: (1 分) 其所有短语: ①(SdSdS)②SdSdS③SdS④S(2 分) 简单短语: S(1 分) 句柄: S(1 分) 素短语: SdS (1 分) 最左素短语: SdS (1 分) 32. 答: G[A]:A → aB B→ bC C→ aD D→ bD|aE E→ aE|bD| ε 33. 答: 对应文法为 G(S) = ({S,X,Y},{a,b,c},{S → aS|X,X → bX|Y,Y → cY| ε},S) S SdA S(A)SdA [ 评分标准] 文法四元组完整 1 分;每个非终结符对应的产生式正确各 2分 34. 答案如答 34图:答 34图 35. 答: 将非终结符按 A,B,C 排序,有已知文法的产生集为: {A→ BaC |Cb B,B → AC| c,C → Bb| c}, 试消除 G 的左递归。当 i=1 j=0, 无替换,不存在直接左递归当 i=2,j=1, 存在替换,将 A 的产生式代入到 B 的产生式右部,得: B→(BaC |Cb B)C |c即B→ |Cb BC|c ,存在直接左递归,改写如下: n9 n10 n1 n2 n3 T1 AB n4 5 T2 n5 20 M n6 n7 n8 T3 DC - + T4 L* ,T4 + ,N B→Cb BCB′| cB′ B′→ aCCB ′|ε当 i=3,j=1, 无替换,不存在直接左递归当 i=3,j=2, 存在替换,将 B 的产生式代入到 C 的产生式右部,得: C→(Cb BCB′| cB′)b|c 即C→Cb BCB′b| cB′b|c ,存在直接左递归,改写如下: C→ cB′ bC′| cC′ C′→b BCB′ bC′|ε最后得到消除后左递归的的文法如下: A→ BaC |CbBB→Cb BCB′| cB′ B′→ aCCB ′|ε C→ cB′ bC′| cC′ C′→b BCB′ bC′|ε六、设计分析题。 36. 答: FIRSTVT (S) ={a ,∧,()} LASTVT (S) ={a ,∧,()} FIRSTVT (T) ={a ,∧,,,()} LASTVT (