《1编译原理期末复习题.docx》由会员分享，可在线阅读，更多相关《1编译原理期末复习题.docx（14页珍藏版）》请在三一办公上搜索。
1、1编译原理期末复习题北方工业大学 序号 编译原理课程期末复习题 开课学院 考试方式：闭卷 A卷 考试时间：120 分钟 班级 姓名 学号 题 号 得 分 阅卷人 装 一 二 三 四 五 六 七 八 九 十 总 分 一判断题 1. 程序语言主要由语法和语义两方面定义。 2. 自上而下分析方法会遇到的主要问题有左递归和回溯。 3. 已知文法G：Ei | EAE，A+|* ，其中的终结符号集包括i，+。 4. 编译程序是将高级语言程序翻译成机器语言程序。 5. 只含有综合属性的属性文法称为S-属性文法。 订 6. LL(1)文法中第一个L的含义是从左到右扫描输入串。 7. 在编译中进行语法检查的目的
2、是为了发现程序中所有错误。 8. 一个语义子程序描述了一个文法所对应的翻译工作。 9. 一个句型的直接短语是唯一的。 10. 确定的自动机以及不确定的自动机都能正确地识别正规集。 解：1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 二、选择题 线 1. 文法分为四种类型，即0型、1型、2型、3型。其中3型文法是_。 A. 短语文法 B. 正规文法 C. 上下文有关文法 D. 上下文无关文法 2. 不可能是目标代码。 A. 汇编指令代码 B. 可重定位指令代码 C. 绝对指令代码 D. 中间代码 3. 将编译程序分成若干个“遍”是为了 。 A. 提高程序的执行效率 B. 利用有限的
3、机器内存并提高机器的执行效率 C. 使程序的结构更加清晰 D. 利用有限机器内存但降低了机器的执行效率 4. 后缀式ab+cd+/可用表达式 来表示。 北方工业大学试卷 第1页 共11页 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)* 6. 文法GE： EE+T|T TT*P|P P(E)|i 则句型P+T+i的句柄和最左素短语为 。 A. P+T和i B. P和P+T C. i和P+T+i D. P和T 7. 设有文法GE： EE*T|T TT+i|i 句子1+
4、2*8+6按该文法G归约，其值为 。 A. 42 B. 23 C. 30 D. 17 8. 规范归约指 。 A. 最右推导的逆过程 9. 词法分析所依据的是 。 A. 语义规则 B. 构词规则 C. 语法规则 D. 等价变换规则 10. 状态转换图接受的集合为 。 0 X 1 Y 0 C. xnyxn(n0) D. x*yx* B. 最左推导的逆过程 C. 规范推导 D. 最左归约的逆过程 A. 以 0开头的二进制数组成的集合 B. 以0结尾的二进制数组成的集合 C. 含奇数个0的二进制数组成的集合 D. 含偶数个0的二进制数组成的集合 11. 词法分析器作为独立的阶段使整个编译程序结构更加简
5、洁、明确，因此， 。 A. 词法分析器作为子程序较好 B. 词法分析器并不作为一个独立的阶段 C. 词法分析器分解为多个过程，由语法分析器选择使用 D. 词法分析器应作为独立的一遍 12. 若a为终结符，则Aa为 项目。 A. 移进 B. 归约 C. 接受 C. 语义规则 D. 等价变换规则 D. 待约 13. 中间代码生成所依据的是 。 A. 语法规则 B. 词法规则 北方工业大学试卷 第2页 共11页 14. 终结符具有 属性。 A. 传递 B. 继承 C. 抽象 D. 综合 15. 下推自动机识别的语言是 。 16. 常用的中间代码形式不含 。 A. 三元式 B. 四元式 C. 逆波兰表
6、达式 D. 语法树 17. 算符文法是指 的文法。 A. 没有形如U.VW.的产生式 B. VT中任意两个符号之间至多存在一种算符优先关系 C. 没有相同右部的产生式 D. 没有形如U的产生式 18. 下述语句类中，_在编译阶段通常不产生可执行代码。 A. 变量说明语句 B. 流程控制语句 C. 输入输出语句 D. 赋值语句 19. 文法所描述的语言是 的集合。 A. 文法的字母表中符号组成的符号串 B. 文法的字母表中终结符号组成的符号串 C. 由文法开始符号推导的符号串 D. 由文法开始符号推导的终结符号串 20. 符号串ab1b2是文法GA：AaB, BbB|b的句子，该句子的句柄是_。
7、 A. b1 B. b2 C. a D. b1b2 解：1. B 2. D 3. C 4. B 5. C 6. B 7. A 8. A 9. B 10. D 11. A 12. A 13. C 14. D 15. C 16. D 17. A 18. A 19. D 20. B 三、已知文法G的产生式为： ET|E+T|E-T TF|T*F (2-1) F (E)|i 试求： 消除该文法的左递归； 利用(1)得到的文法G(2-1)，求(i+i*i)的最左推导和语法分析树。 解： ETE E+TE|-TE | TFT| 北方工业大学试卷 第3页 共11页 A. 0型语言 B. 1型语言 C. 2型
8、语言 D. 3型语言 T*FT| (2-1) F(E)|i ETEFTE(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) E(根) T E F T ( ) T E i + i*i北方工业大学试卷 第4页 共11页 四、已知文法G3： Sa|(T); TT,S|S 其中：S、T是非终结符，a、 、, 、 是终结符，S为开始符合，试求： (1)计算非终结符的FISTVT和LASTVT; (2)给出终结符的算符优先关系表； (3)给出(a,(a,a)的算符优先分析过程，指出每次规约的素短语。
9、 解：(1)FIRSTVT和LASTVT如下： FIRSTVT(S)=a，( FIRSTVT(T)=，a，( LASTVT(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)# 归
10、 #(t，(t, a)# 进 #(t，(t，a )# 进 #(t，(t，s )# 归 #(t，(t )# 归 #(t，(t) )# 进 #(t，s )# 归 #(t )# 归 #(t) # 进 #s # 归 北方工业大学试卷 第5页 共11页 五、已知文法G 的产生式为： ET|E+T|E-T TF|T*F (2-1) F (E)|i 试给出表达式i1*i2+i3的规范式规约过程。用下面的格式描述该过程。 步骤 符号栈 输入串 所用产生式 答：输入串i1*i2+i3的分析步骤： 步骤 符号栈 输入串 0 # i1*i2+i3# 1 #i1 *i2+i3# 2 #F *i2+i3# 3 #T *
11、i2+i3# 4 #T* i2+i3# 5 #T*i2 +i3# 6 #T*F +i3# 7 #T +i3# 8 #E +i3# 9 #E+ i3# 10 #E+i3 # 11 #E+F # 12 #E+T # 13 #E # 14 #E # 所用产生式 预备 进 归，用Fi 归，用TF 进 进 归，用Fi 归，用FE*F 归，用FT 进 进 归，用Ei 归，用TF 归，用EE+T 接受 北方工业大学试卷 第6页 共11页 六、属性文法如表5-1所示，试求表达式a+4+c的抽象语法树，并描述建立抽象语法树过程。 表6-1 属性文法 产生式 语义规则 EE1+T E.nptr := mknode
12、( + , E1.nptr , T.nptr ) EE1-T E.nptr := mknode( - , E1.nptr , T.nptr ) ET E.nptr := T.nptr T(E) T.nptr := E.nptr Tid T.nptr := mklear( id , id.entry ) Tnum T.nptr := mklear( num , num.val ) 答： p1 := mkleaf( id , entrya ); p2 := mkleaf( num , 4 ); p3 := mknode( + , p1 , p2 ); p4 := mkleaf( id , entr
13、yc ); p5 := mknode( + , p3 , p4 ); -+id指向符号表中c的表项的指针id指向符号表中a的表项的指针num4表达式 a - 4 + c 的语法树北方工业大学试卷 第7页 共11页 七已知翻译规则 产生式 S if E then S1 S if E then S1 else S2 Swhile E do S1 E.true := newlabel; E.false := S.next; S1.next := S.next; S.code := E.code | gen( E.true: ) | S1.code E.true := newlabel; E.fals
14、e := newlabel; S1.next := S.next; S2.next := S.next; S.code := E.code | gen( E.true : ) | S1.code | gen( goto S.next ) | gen( E.false : ) | S2.code 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( g
15、oto S.begin ) 语义规则 试把下面的语句翻译成三地址代码 While AC and BD Do If A=1 then C:=C+1 else 答： 100：if AC goto 102 101：goto L.false 115 102：if BD goto 104 103：goto L.false 115 104：goto 106 105：goto L.false 109 106：T1=C+1 107：C:=T1 108：goto S.next 113 109：if A=D goto 111 110：goto S.next 113 111：T2=A+2 112：A:=T2 113
16、：goto 109 114：goto 100 While A=D Do A:=A+2 北方工业大学试卷 第8页 共11页 八、已知翻译规则，试把下面的原程序翻译成三地址代码。 while a b do if c d then x := y + z else x := y - z 答： L1: if a b goto L2 goto Lnext L2: if c d goto L3 goto L4 L3: t1 := y + z x := t1 goto L1 L4: t2 := y - z x := t2 L5 goto L1 Lnext: goto L1 北方工业大学试卷第9页 共11页 九
17、、对以下四元式程序，试求：它的流图，对其中的循环进行循环优化。 I:=1 Read J,K L: A:=K*I B:=J*I C:=A*B Write C I:=I+1 If I100 goto L Halt I:=1I:=1Read j,KRead J,KA:=K*IB:=J*IL A:=K*I强度削弱B:=J*IC:=A*BC:=A*BWrite CWrite CI:=I+1A:=A+KIf I100 goto LB:=B+JI:=I+1If I100 goto Lhalthalt变化控制条件I:=1Read J,KI:=1A:=K*IRead J,KB:=J*IA:=K*IT1:=100
18、KB:=J*IL C:=A*BWrite CL C:=A*B删除归纳变量A:=A+KWrite CB:=B+JA:=A+KI:=I+1B:=B+JT1:=100*KIf At1 GOTO LIf A100 goto L2 A:=K*I B:=J*I C:=A*B Write C I:=I+1 Goto L1 L2: Halt I:=1 Read J,K L1: If I100 goto L2 A:=K*I B:=J*I C:=A*B Write C I:=I+1 goto L1 L2:Halt I:=1 I:=1 Read J,K Read J,K A:=K*I A:=K*I B:=J*I B:=J*I T1=100*K L1: If I100 goto L2 L1: If AT1 goto L2 C:=A*B C:=A*B Write C Write C I:=I+1 A:=A+K A:=A+K B:=B+J B:=B+J Goto L1 goto L1 Halt Halt 北方工业大学试卷 第11页 共11页
