北方工业大学16编译原理期末复习题答案.doc

1、北方工业大学试卷 第 1 页 共 12 页 北方工业大学 编 译 原 理 课 程 期 末 复 习 题 （ 答 案 ） A 卷2016 年春季学期开课学院 考试方式：闭卷 考试时间：120 分钟班级 姓名 学号 题 号 一 二 三 四 五 六 七 八 九 十 总 分得 分阅卷人一判断题（每个小题 1 分，共 10 分）1. 程 序 语 言 主 要 由 语 法 和 语 义 两 方 面 定 义 。 （ ）2. 自 上 而 下 分 析 方 法 会 遇 到 的 主 要 问 题 有 左 递 归 和 回 溯 。 （ ）3. 已 知 文 法 G： Ei | EAE， A+|* ， 其 中 的 终 结 符 号

2、集 包 括 i， +。 （ ）4. 编 译 程 序 是 将 高 级 语 言 程 序 翻 译 成 机 器 语 言 程 序 。 （ ）5. 只 含 有 综 合 属 性 的 属 性 文 法 称 为 S-属 性 文 法 。 （ ）6. LL(1)文 法 中 第 一 个 L 的 含 义 是 从 左 到 右 扫 描 输 入 串 。 （ ）7. 在编译中进行语法检查的目的是为了发现程序中所有错误。 （ ）8. 一个语义子程序描述了一个文法所对应的翻译工作。 （ ）9. 一个句型的直接短语是唯一的。 （ ）10. 确定的自动机以及不确定的自动机都能正确地识别正规集。 （ ） 解 ： 1. 2. 3. 4. 5

3、. 6. 7. 8. 9. 10.二、选择题（每个小题 1 分，共 20 分）1. 文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是_。A. 短语文法 B. 正规文法 C. 上下文有关文法 D. 上下文无关文法2. 不可能是目标代码。 A. 汇编指令代码 B. 可重定位指令代码 C. 绝对指令代码 D. 中间代码3. 将编译程序分成若干个“遍”是为了 。 A. 提高程序的执行效率 B. 利用有限的机器内存并提高机器的执行效率C. 使程序的结构更加清晰 D. 利用有限机器内存但降低了机器的执行效率 4. 后缀式 ab+cd+/可用表达式 来表示。 序号订线装北方工业大学试

4、卷 第 2 页 共 12 页 A. a+b/c+d B. (a+b)/(c+d) C. a+b/(c+d) D. a+b+c/d 5. 文法 G：SxSx|y 所识别的语言是 。A. xyx B. (xyx)* C. xnyxn(n0) D. x*yx*6. 文法 GE：EE+T|TTT*P|PP(E)|i则句型 P+T+i 的句柄和最左素短语为 。A. P+T 和 i B. P 和 P+T C. i 和 P+T+i D. P 和 T7. 设有文法 GE：EE*T|TTT+i|i句子 1+2*8+6 按该文法 G 归约，其值为 。 A. 42 B. 23 C. 30 D. 178. 规范归约指

5、 。A. 最右推导的逆过程 B. 最左推导的逆过程C. 规范推导 D. 最左归约的逆过程9. 词法分析所依据的是 。A. 语义规则 B. 构词规则 C. 语法规则 D. 等价变换规则10. 状态转换图（见下图）接受的集合为 。A. 以 0 开头的二进制数组成的集合 B. 以 0 结尾的二进制数组成的集合C. 含奇数个 0 的二进制数组成的集合 D. 含偶数个 0 的二进制数组成的集合11. 词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此， 。A. 词法分析器作为子程序较好 B. 词法分析器并不作为一个独立的阶段C. 词法分析器分解为多个过程，由语法分析器选择使用 D. 词法分析

6、器应作为独立的一遍12. 若 a 为终结符，则 Aa 为 项目。 A. 移进 B. 归约 C. 接受 D. 待约010 YX北方工业大学试卷 第 3 页 共 12 页 13. 中间代码生成所依据的是 。A. 语法规则 B. 词法规则 C. 语义规则 D. 等价变换规则14. 终结符具有 属性。 A. 传递 B. 继承 C. 抽象 D. 综合15. 下推自动机识别的语言是 。 A. 0 型语言 B. 1 型语言 C. 2 型语言 D. 3 型语言16. 常用的中间代码形式不含 。 A. 三元式 B. 四元式 C. 逆波兰表达式 D. 语法树17. 算符文法是指 的文法。 A. 没有形如 U.VW

7、.的产生式（U、V、WV N） B. VT 中任意两个符号之间至多存在一种算符优先关系 C. 没有相同右部的产生式 D. 没有形如 U 的产生式 18. 下述语句类中，_在编译阶段通常不产生可执行代码。 A. 变量说明语句 B. 流程控制语句 C. 输入输出语句 D. 赋值语句 19. 文法所描述的语言是 的集合。 A. 文法的字母表中符号组成的符号串 B. 文法的字母表中终结符号组成的符号串 C. 由文法开始符号推导的符号串 D. 由文法开始符号推导的终结符号串 20. 符号串 ab1b2 是文法 GA：AaB, BbB|b 的句子，该句子的句柄是_。A. b1 B. b2 C. a D.

8、b1b2 解 ： 1. B 2. D 3. C 4. B 5. C6. B 7. A 8. A 9. B 10. D11. A 12. A 13. C 14. D 15. C 16. D 17. A 18. A 19. D 20. B 三、已知文法 G 的产生式为：ET|E+T|E-TTF|T*F (2-1)F (E)|i试求：（1）消除该文法的左递归；（5 分）（2）利用(1)得到的文法 G(2-1)，求(i+i*i) 的最左推导和语法分析树。 （5 分）解：（1）北方工业大学试卷 第 4 页 共 12 页 ETEE+TE|-TE |TFT|T*FT| (2-1)F(E)|i（2）ETEFT

9、E(E)TE(E)(TE)(FTE)(iTE)(iE)(i+TE)(i+FTE)(i+iTE)(i+i*FTE)(i+i*iTE)(i+i*i) (i+i*i)四、已知文法 G 的产生式：ETEE+TE|-TE |TFT|T*FT| (2-1)F(E)|i试求：（1）每个非终结符的 FIRST 集合；（5 分 ） （2）每个非终结符的FOLLOW 集合。 （5 分）答：FIRST(E)=(,i FOLLOW(E)=）,#FIRST(E)=-,+, FOLLOW(E)=),#FIRST(T)=(, i FOLLOW(T)=-,+, ), #FIRST(T)=*, FOLLOW(T)=-,+,),

10、#FIRST(F)=(, i FOLLOW(F)=*,-,+, ), #EE(根 )Ti ( )Fi +TT Ei * 北方工业大学试卷 第 5 页 共 12 页 五、已知文法 G3：Sa|(T);TT,S|S其中：S、T 是非终结符，a、 、, 、 （ 和 ）是终结符，S 为开始符合，试求：(1)计算非终结符的 FISTVT 和 LASTVT;(2)给出终结符的算符优先关系表；(3)给出(a,(a,a)的算符优先分析过程，指出每次规约的素短语。 （共 30 分，每小题 10分）解：(1)FIRSTVT 和 LASTVT 如下：FIRSTVT(S)=a，(FIRSTVT(T)=， ，a，(LA

11、STVT(S)=a，)LASTVT(T)=， ，a ，)(2) 构造优先关系表如下：a ( ) ， #a ( ， # =(3) 输入串(a,(a,a)的算符优先分析过程如下：栈 输入字符串 动作# (a， (a，a)# 预备#( a，(a，a)# 进#(a ,(a，a)# 进#(s ,(a，a)# 归#(t ,(a，a)# 归#(t， (a， a)# 进#(t， ( a，a)# 进#(t， (a ,a)# 进#(t， (s ,a)# 归#(t， (t ,a)# 归#(t， (t, a)# 进#(t， (t， a )# 进#(t， (t， s )# 归#(t， (t )# 归#(t， (t) )

12、# 进#(t， s )# 归#(t )# 归#(t) # 进#s # 归北方工业大学试卷 第 6 页 共 12 页 六、已知文法 G 的产生式为：ET|E+T|E-TTF|T*F (2-1)F (E)|i试给出表达式 i1*i2+i3 的规范式规约过程。用下面的格式描述该过程。 （10 分）步骤 符号栈 输入串 所用产生式答：输入串 i1*i2+i3 的分析步骤：步骤 符号栈 输入串 所用产生式0 # i1*i2+i3# 预备1 #i1 *i2+i3# 进2 #F *i2+i3# 归，用 Fi3 #T *i2+i3# 归，用 TF4 #T* i2+i3# 进5 #T*i2 +i3# 进6 #T

13、*F +i3# 归，用 Fi7 #T +i3# 归，用 FE*F8 #E +i3# 归，用 FT9 #E+ i3# 进10 #E+i3 # 进11 #E+F # 归，用 Ei 12 #E+T # 归，用 TF13 #E # 归，用 EE+T14 #E # 接受北方工业大学试卷 第 7 页 共 12 页 七、属性文法如表 5-1 所示，试求表达式 a+4+c 的抽象语法树，并描述建立抽象语法树过程。 （10 分）表 6-1 属性文法产生式 语义规则EE 1+T E.nptr := mknode( + , E1.nptr , T.nptr )EE 1-T E.nptr := mknode( - ,

14、 E1.nptr , T.nptr )ET E.nptr := T.nptrT(E) T.nptr := E.nptrTid T.nptr := mklear( id , id.entry )Tnum T.nptr := mklear( num , num.val )答：（1）p1 := mkleaf( id , entrya );（2）p2 := mkleaf( num , 4 );（3）p3 := mknode( + , p1 , p2 );（4）p4 := mkleaf( id , entryc );（5）p5 := mknode( + , p3 , p4 );八、已知翻译模式如下：产生

15、式 语义规则EE 1 or E2EE 1 and E2Eid 1 relop id2E.place := newtemp;emit( E.place := E1.place or E2.place ) E.place := newtemp;emit( E.place := E1.place and E2.place ) E.place := newtemp;emit( if id1.place relop.op id2.place goto nextstat+3);emit( E.place := 0);emit(goto nextstat + 2);emit( E.place := 1) 试

16、给出布尔表达式 ab and cd or ef 的三地址代码（10 分） 。答：+- idnum4id 指 向 符 号 表 中 c的 表 项 的 指 针指 向 符 号 表 中 a的 表 项 的 指 针表 达 式 a-4 +c的 语 法 树100：if a b goto 103101：t 1 := 0102：goto 104103：t 1 := 1104：if c d goto 107105：t 2 := 0106：goto 108107：t 2 := 1108：if e f goto 111109：t 3 := 0110：goto 112111：t 3 := 1112：t 4 := t1 an

17、d t2113：t 5 := t3 or t4北方工业大学试卷 第 8 页 共 12 页 北方工业大学试卷 第 9 页 共 12 页 九、已知翻译规则产生式 语义规则S if E then S1S if E then S1 else S2E.true := newlabel;E.false := S.next;S1.next := S.next;S.code := E.code | gen( E.true: ) | S1.codeE.true := newlabel;E.false := newlabel;S1.next := S.next;S2.next := S.next;S.code :

18、= E.code |gen( E.true : ) | S1.code |gen( goto S.next ) |gen( E.false : ) | S2.codeSwhile E do S1 S.begin := newlabel;E.true := newlabel; E.false := S.next;S1.next := S.begin;S.code := gen( S.bgein : ) | E.code |gen( E.true : ) | S1.code |gen( goto S.begin )试把下面的语句翻译成三地址代码While AC and BD DoIf A=1 th

19、en C:=C+1 elseWhile A=D Do A:=A+2答：100：if AC goto 102101：goto L.false 115102：if BD goto 104103：goto L.false 115104：goto 106105：goto L.false 109106：T1=C+1107：C:=T1108：goto S.next 113109：if A=D goto 111110：goto S.next 113 111：T2=A+2112：A:=T2113：goto 109 114：goto 100北方工业大学试卷 第 10 页 共 12页 十、已知翻译规则（见第九题） ，试把下面的原程序翻译成三地址代码。while a b doif c d thenx := y + zelsex := y - z答：L1: if a b goto L2goto LnextL2: if c d goto L3goto L4L3: t1 := y + zx := t1goto L1（goto L5）L4: t2 := y - zx := t2L5 goto L1Lnext: goto L1