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

更新时间:2024-01-19 00:48:01 阅读量: 教育文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

北方工业大学

序号 《编译原理》课程期末复习题(答案)

2016年春季学期

开课学院

考试方式:闭卷

A卷

考试时间: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+/可用表达式 来表示。

北方工业大学试卷 第1页 共12页

A. a+b/c+d B. (a+b)/(c+d) C. a+b/(c+d) D. a+b+c/d 5. 文法G:S→xSx|y所识别的语言是 。

A. xyx

B. (xyx)*

6. 文法G[E]: E→E+T|T T→T*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. 设有文法G[E]: E→E*T|T T→T+i|i

句子1+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(n≥0) D. x*yx*

B. 最左推导的逆过程

C. 规范推导 D. 最左归约的逆过程

A. 以 0开头的二进制数组成的集合 B. 以0结尾的二进制数组成的集合 C. 含奇数个0的二进制数组成的集合 D. 含偶数个0的二进制数组成的集合 11. 词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确,因此, 。 A. 词法分析器作为子程序较好 B. 词法分析器并不作为一个独立的阶段 C. 词法分析器分解为多个过程,由语法分析器选择使用 D. 词法分析器应作为独立的一遍

12. 若a为终结符,则A→α·aβ为 项目。 A. 移进

B. 归约

C. 接受

C. 语义规则

D. 等价变换规则 D. 待约

13. 中间代码生成所依据的是 。 A. 语法规则

B. 词法规则

北方工业大学试卷 第2页 共12页

14. 终结符具有 属性。 A. 传递

B. 继承

C. 抽象

D. 综合

15. 下推自动机识别的语言是 。 16. 常用的中间代码形式不含 。

A. 三元式 B. 四元式 C. 逆波兰表达式 D. 语法树 17. 算符文法是指 的文法。

A. 没有形如U→...VW...的产生式(U、V、W?VN) B. VT中任意两个符号之间至多存在一种算符优先关系 C. 没有相同右部的产生式 D. 没有形如U→ε的产生式

18. 下述语句类中,____________在编译阶段通常不产生可执行代码。 A. 变量说明语句 B. 流程控制语句 C. 输入输出语句 D. 赋值语句 19. 文法所描述的语言是 的集合。 A. 文法的字母表中符号组成的符号串 B. 文法的字母表中终结符号组成的符号串 C. 由文法开始符号推导的符号串 D. 由文法开始符号推导的终结符号串

20. 符号串ab1b2是文法G[A]:A→aB, B→bB|b的句子,该句子的句柄是________。 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的产生式为:

E?T|E+T|E-T

T?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’|

北方工业大学试卷 第3页 共12页

A. 0型语言 B. 1型语言 C. 2型语言 D. 3型语言

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) E(根)

T E’

F T’ ε

( )

ε T E’

ε

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} FIRST(E’)={-,+, ε} FIRST(T)={(, i} FIRST(T’)={*, ε} FIRST(F)={(, i}

FOLLOW(E)={),#} FOLLOW(E’)={),#} FOLLOW(T)={-,+, ), #} FOLLOW(T’)={-,+,),#} FOLLOW(F)={*,-,+, ), #}

北方工业大学试卷 第4页 共12页

五、已知文法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) 构造优先关系表如下: 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) )# 进 #(t,s )# 归 #(t )# 归 #(t) # 进 #s # 归 北方工业大学试卷 第5页 共12页

六、已知文法G 的产生式为:

E?T|E+T|E-T

T?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# 3 #T *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

#

所用产生式 预备 进

归,用F→i 归,用T→F 进 进

归,用F→i 归,用F→E*F 归,用F→T 进 进

归,用E→i 归,用T→F 归,用E→E+T 接受

北方工业大学试卷 第6页 共12页

七、属性文法如表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.nptr T→(E) T.nptr := E.nptr

T→id T.nptr := mklear( id , id.entry ) T→num 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 );

-+id指向符号表中c的表项的指针id指向符号表中a的表项的指针num4八、已知翻译模式如下: 产生式 语义规则 表达式 a - 4 + c 的语法树E→E1 or E2 {E.place := newtemp; emit( E.place ‘:=’ E1.place ‘or’ E2.place ) } E→E1 and E2 {E.place := newtemp; emit( E.place ‘:=’ E1.place ‘and’ E2.place ) } E→id1 relop id2 {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’) } 试给出布尔表达式a

100:if a < b goto 103 107:t2 := 1

101:t1 := 0 108:if e < f goto 111

102:goto 104 109:t3 := 0

103:t1 := 1 110:goto 112

104:if c < d goto 107 111:t3 := 1

105:t2 := 0 112:t4 := t1 and t2

106:goto 108 113:t5 := t3 or t4

北方工业大学试卷 第7页 共12页

北方工业大学试卷第8页 共12页

九、已知翻译规则

产生式 S→ if E then S1 S→ if E then S1 else S2 S→while 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.false := 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( ‘goto’ S.begin ) 语义规则 试把下面的语句翻译成三地址代码 While A

If A=1 then C:=C+1 else 答: 100:if A

北方工业大学试卷 第9页 共12页

十、已知翻译规则(见第九题),试把下面的原程序翻译成三地址代码。

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(goto L5) L4: t2 := y - z x := t2 L5 goto L1 Lnext: goto L1

北方工业大学试卷第10页 共12页

十一、对以下四元式程序,试求:(1)它的流图(5分),(2)对其中的循环进行循环优化(10分)。 I:=1 Read J,K L: A:=K*I B:=J*I C:=A*B Write C I:=I+1 If I<100 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 I<100 goto LB:=B+JI:=I+1If I<100 goto Lhalthalt变化控制条件I:=1Read J,KI:=1A:=K*IRead J,KB:=J*IA:=K*IT1:=100KB:=J*IL C:=A*BWrite CL C:=A*B删除归纳变量A:=A+KWrite CB:=B+JA:=A+KI:=I+1B:=B+JT1:=100*KIf A

十二、 已知一个三地址代码如下。试完成(1)给出对应的流图(5分);(2)对流图中的代码进行优化(10分)。

I:=1 Read J,K L1:If I>100 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 I>100 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 I>100 goto L2 L1: If A>T1 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 北方工业大学试卷 第12页 共12页

本文来源:https://www.bwwdw.com/article/ymxo.html

Top