北方工业大学《编译原理》课程期末复习题（答案）A 卷2016年春季学期开课学院考试方式：闭卷考试时间：120 分钟班级 姓名 学号 一判断题（每个小题1分，共10分）1. 程序语言主要由语法和语义两方面定义。

（ ）2. 自上而下分析方法会遇到的主要问题有左递归和回溯。

（ ）3. 已知文法G ：E →i | EAE ，A →+|* ，其中的终结符号集包括{i ，+}。

（ ）4. 编译程序是将高级语言程序翻译成机器语言程序。

（ ）5. 只含有综合属性的属性文法称为S-属性文法。

（ ）6. LL(1)文法中第一个L 的含义是从左到右扫描输入串。

（ ）7. 在编译中进行语法检查的目的是为了发现程序中所有错误。

（ ）8. 一个语义子程序描述了一个文法所对应的翻译工作。

（ ）9. 一个句型的直接短语是唯一的。

（ ） 10. 确定的自动机以及不确定的自动机都能正确地识别正规集。

（ ） 解：1.√ 2.√ 3.× 4.× 5.√ 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+/可用表达式 来表示。

订线装A. a+b/c+dB. (a+b)/(c+d)C. a+b/(c+d)D. a+b+c/d5. 文法G：S→xSx|y所识别的语言是。

A. xyxB. (xyx)*C. x n yx n(n≥0)D. x*yx*6. 文法G[E]：E→E+T|TT→T*P|PP→(E)|i则句型P+T+i的句柄和最左素短语为。

A. P+T和iB. P和P+TC. i和P+T+iD. P和T7. 设有文法G[E]：E→E*T|TT→T+i|i句子1+2*8+6按该文法G归约，其值为。

A. 42B. 23C. 30D. 178. 规范归约指。

A. 最右推导的逆过程B. 最左推导的逆过程C. 规范推导D. 最左归约的逆过程9. 词法分析所依据的是。

A. 语义规则B. 构词规则C. 语法规则D. 等价变换规则10. 状态转换图（见下图）接受的集合为。

A. 以0开头的二进制数组成的集合B. 以0结尾的二进制数组成的集合C. 含奇数个0的二进制数组成的集合D. 含偶数个0的二进制数组成的集合11. 词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，。

A. 词法分析器作为子程序较好B. 词法分析器并不作为一个独立的阶段C. 词法分析器分解为多个过程，由语法分析器选择使用D. 词法分析器应作为独立的一遍12. 若a为终结符，则A→α·aβ为项目。

A. 移进B. 归约C. 接受D. 待约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...的产生式（U、V、W∈V N）B. V T中任意两个符号之间至多存在一种算符优先关系C. 没有相同右部的产生式D. 没有形如U→ε的产生式18. 下述语句类中，____________在编译阶段通常不产生可执行代码。

A. 变量说明语句B. 流程控制语句C. 输入输出语句D. 赋值语句19. 文法所描述的语言是的集合。

A. 文法的字母表中符号组成的符号串B. 文法的字母表中终结符号组成的符号串C. 由文法开始符号推导的符号串D. 由文法开始符号推导的终结符号串20. 符号串ab1b2是文法G[A]：A→aB, B→bB|b的句子，该句子的句柄是________。

A. b1B. b2C. aD. b1b2解：1. B 2. D 3. C 4. B 5. C6. B7. A8. A9. B 10. D11. A 12. A 13. C 14. D 15. C16. D 17. A 18. A 19. D 20. B三、已知文法G的产生式为：E→T|E+T|E-TT→F|T*F (2-1)F→ (E)|i试求：（1）消除该文法的左递归；（5分）（2）利用(1)得到的文法G’(2-1)，求(i+i*i)的最左推导和语法分析树。

（5分）解：（1）E→TE’E’→+TE’|-TE’ |εT→FT’|T ’→*FT ’|ε (2-1)’ F →(E)|i （2）E ⇒TE ’⇒FT ’E ’⇒(E)T ’E ’⇒(E)εε⇒(TE ’)⇒(FT ’E ’)⇒(iT ’E')⇒(i εE ’)⇒(i+TE ’)⇒(i+FT ’E ’)⇒(i+iT ’E ’)⇒(i+i*FT ’E ’)⇒(i+i*iT ’E ’)⇒(i+i*i εε) ⇒(i+i*i)四、已知文法G 的产生式：E →TE ’E’→+TE’|-TE’ |εT →FT’|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’)={-,+,),#} FIRST(F)={(, i}FOLLOW(F)={*,-,+, ), #}E ’E(根) Tiε ( )Fi+T ’ ε T E ’i*ε五、已知文法G3：S→a|^|(T);T→T,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，∧，(}LASTVT(S)={a，∧，)}LASTVT(T)={，，a，∧，)}(2)(3)六、已知文法G 的产生式为：E→T|E+T|E-TT→F|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# 归，用F→i3 #T *i2+i3# 归，用T→F4 #T* i2+i3# 进5 #T*i2+i3# 进6 #T*F+i3# 归，用F→i7 #T +i3# 归，用F→E*F8 #E +i3# 归，用F→T9 #E+ i3# 进10 #E+i3 # 进11 #E+F # 归，用E→i12 #E+T # 归，用T→F13 #E # 归，用E→E+T14 #E # 接受七、属性文法如表5-1所示，试求表达式a+4+c的抽象语法树，并描述建立抽象语法树过程。

（10分）表6-1 属性文法产生式语义规则E→E1+T E.nptr := mknode( ‘ + ’, E1.nptr , T.nptr )E→E1-T E.nptr := mknode( ‘ - ’, E1.nptr , T.nptr )E→T E.nptr := T.nptrT→(E)T.nptr := E.nptrT→id T.nptr := mklear( id , id.entry )答：表达式 a - 4 + c 的语法树100：if a < b goto 103 101：t1 := 0102：goto 104 103：t1 := 1104：if c < d goto 107 105：t2 := 0106：goto 108 107：t2 := 1108：if e < f goto 111 109：t3 := 0110：goto 112 111：t3 := 1112：t4 := t1 and t2 113：t5 := t3 or t4九、已知翻译规则试把下面的语句翻译成三地址代码 While A<C and B<D DoIf A=1 then C:=C+1 else While A<=D Do A:=A+2答：十、已知翻译规则（见第九题），试把下面的原程序翻译成三地址代码。

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十一、对以下四元式程序，试求：（1）它的流图（5分），（2）对其中的循环进行循环优化（10分）。

十二、已知一个三地址代码如下。

试完成（1）给出对应的流图（5分）；（2）对流图中的代码进行优化（10分）。

I:=1Read J,KL1:If I>100 goto L2A:=K*IB:=J*IC:=A*BWrite CI:=I+1Goto L1 L2: Halt。