文档库 最新最全的文档下载
当前位置:文档库 › 编译原理期末考试试卷与答案

编译原理期末考试试卷与答案

编译原理期末考试试卷与答案
编译原理期末考试试卷与答案

得分一.填空题(每

空2 分,

20 分)

1. 不同的编译程序关于数据空间的存储分配策略可能不同,但大部分编译中采用的方案有两种:静态存储分配方案和动态存储分配方案,而后者又分为( 1)和( 2)。

2.规范规约是最( 3)规约。

3.编译程序的工作过程一般划分为 5 个阶段:词法分析、( 4)、语义分析与中间代码生成,代码优化及( 5)。另外还有( 6)和出错处理。

4.表达式 x+y*z/(a+b) 的后缀

式为(7)。

5.文法符号的属性有综合属性和( 8)。

6.假设二位数组按行存放,而且每个元素占用一个存储单元,则数组a[1..15,1..20]某个元素a[i ,j]

的地址计算公式为( 9)。

7.局部优化是局限于一个(10)范围内的一种优化。

得分

二.选择题(1-6 为单选题, 7-8 为多选题,每问 2 分,共 20 分)

1. 一个上下文无关文

法G包括四个组成部分:一组终结符,一组非终结符,一个(),以

及一组

()。

A.字符串 B .产生式 C .开始符号 D .文法2. 程序的基本块是指

()。

A.一个子程

序 B .一个仅有一个入口和一个出口的语句

C.一个没有嵌套的程序段 D .一组顺序执行的程序段,仅有一个入口和一个出口3. 高级语言编译程序常用的语法分析方法中,递归下降分析法

属于()分析方法。

A.自左向右 B .自顶向下 C .自底向上 D .自右向左4.在通常的语法分析方法

中,()特别适用于表达式的分析。

A.算符优先分析法 B . LR 分析法

C.递归下降分析法 D . LL (1)分析法

5.经过编译所得到的目标程序是()。

A.四元式序

列 B .间接三元式序列

C.二元式序

列 D .机器语言程序或汇编语言程序

6.一个文法所描述的语言

是();描述一个语言的文法是()。

A.唯一的 B .不唯一的 C .可能唯一,也可能不唯一

7.如果在文法G中存在一个句子,当其满足下列条件()之一时,则称该文法是二义文法。A.其最左推导和最右推导相同 B .该句子有两个不同的最左推导

C.该句子有两个不同的最右推导 D .该句子有两棵不同的语法树

E.该句子对应的语法树唯一

8.下面()语法制导翻译中,采用拉链—回填技术。

A. 赋值语句

B. 布尔表达式的计算

C. 条件语句

D. 循环语句

得分三.解答题(共 60 分)

1.(共 15 分)已知文法G[E]:

E→ ETE|(E) |i

T→*|+

( 1)将文法 G改造成 LL( 1)文法;( 5 分)

( 2)构造文法 G中每个非终结符的FIRST 集合及 FOLLOW集合;( 5 分)

( 3)构造 LL( 1)分析表。( 5 分)

2.(共 12 分)给定文法G[S] : S→ S(S)| ε

( 1)给出句子 (()())()() 的规范推导过程;(4 分)

(2)指出每步推导所得句型的句柄;( 4 分)

(3)画出该句子的语法推导树。( 4 分)

3.(共 8 分)在一个移入 - 规约分析过程中采用以下的语法制导翻译模式,在按一个产生式规约时,立即执行括号中的动作。

A →

aB{print

“0”;

}

A → c {print “1”;}

B →

Ab{print

“2”;

}

( 1)当分析器的输入为aacbb 时,打印的字符串是什么?( 3 分)

( 2)写出分析过程。( 5 分)

4.( 10 分)翻译循环语句while (ad) then x:=y+z 。要求:给出加注释的分析树及四

元式序列。

参考以下部分翻译模式:

(1) S → if E then M S 1 {backpatch(E.truelist,M.quad);

S.nextlist:=merge(E.falselist,S 1 .nextlist)}

(2) S → while M 1 E do

M 2 S 1 {backpatch(S 1.nextlist

,M 1, .qua d); backpatch(E.truelist,M

2, .quad );

S.nextlist:=E.falselist

emit

( ‘ j,-,-, ’ M1 .quad)}

(3) S → A {S.nextlist:=makelist ()} (4) L → S

{L.nextlist:=S.nextli st}

(5) M →ε

{M.quad:=nextquad}

(6) E →

id 1 relop id2 {E.truelist:=makelist(next quad);

e.falselist:=makelist(nextquad+1); emit( ‘ j ’ relop.op,

‘, ’ id 1.place ‘ , ’ id 2 .place

‘ , ’‘ 0’ );

emit(

‘ j,-,-,0 ’ )}

(7) S → L:=E {emit(:=,E.place,-,L.place)} (8) E →E+E {E.place:=newtemp ; 1 2

emit(+,E .place,E 2.place,E.place,)}

1 5. (共 15 分)设有表格构造文

法 G[S] :

S → a| ∧ |(T)

T → T,S|S

(1) 计算文法 G[S] 的 FIRSTVT 集和 LASTVT 集。( 5 分)

(2)

构造 G[S] 的优先关系表,并判断 G[S] 是否为算符优先文法。 ( 5 分)

(3)

计算 G[S] 的优先函数。( 5 分)

得分

二. 单项选择题 (每题 2 分,共 10 分)

1. 设有文法 G[I] : I → I1|I0|Ia|Ic|a|b|c

下列符号串中是该文法句子的有()。

① ab0 ② a0c01 ③ aaa ④ bc10

可选项有:

A.① B .②③

C .③④

D .①②③④

2. 程序的基本块是指

)。

A.一个子程序 B .一个仅有一个入口和一个出口的语句

C.一个没有嵌套的程序段 D .一组顺序执行的程序段,仅有一个入口和一个出口

3. 高级语言编译程序常用的语法分析方法中,递归下降分析法属于()分析方法。

A.自左向右 B .自顶向下C.自底向上D.自右向左4.经过编译所得到的目标程序是()。

A.四元式序

列 B .间接三元式序列

C.二元式序

列 D .机器语言程序或汇编语言程序

5.运行阶段的存储组织与管理的目的是()。

① 提高编译程序的运行速度② 节省编译程序的存储空间

③ 提高目标程序的运行速度④ 为运行阶段的存储分配做准备

可选项有:

A. ①②

B. ②

③C. ③

D. ④②

得分 2. (10 分)已知文

G[S]:

S→ aBc|bAB

A→ aAb|b

B→b| ε

( 4)构造其 LL( 1)分析表;

( 5)判断符号串baabbb 是否为该文法的句子(写出含有符号栈、输入串和规则的分析过程)。

3.(10 分 ) 已知文法 G为:

E→ E+T|T

T→ T*P|P

P→ i

(1)构造该文法的优先关系表(不考虑语句括号#),并指出此文法是否为算符优先文法。

(2)构造文法 G的优先函数表。

4.( 8 分)在一个移入 - 规约分析过程中采用以下的语法制导翻译模式,在按一个产生式规约时,立即执行括号中的动作。

S → bAb

{print “ 1”

}

A → (

B {print “2”} A → a {print “ 3”} B → Aa) {print

“ 4”}

( 3) 当输入序列为 b(((aa)a)a)b 时,打印的字符串是什么? ( 4) 写出移入 - 规约分析过程。

5. (12 分)翻译循环语句 while (x>y) do if (a=b) then x:=2*y+a 。要求:给出加注释的分析

树、

三地址码序列及相应的四元式序列。 参考以下部分翻译模

式:

(1) S → if E then

M S 1 {backpatch(E.truelist,M.q uad);

S.nextlist:=merge(E.falselist,S 1 .nextlist)}

(2) S → while M 1 E do M 2 S 1

{backpatch(S 1.nextlist ,M 1, .quad);

backpatch(E.truelist,M

2, .quad);

S.nextlist:=E.falselist

emit

( ‘ j,-,-, ’

M1 .quad)} (3) S → A {S.nextlist:=makelist ()} (4) L → S

{L.nextlist:=S.nextli st}

(5) M →ε

{M.quad:=nextquad}

(6) E → id 1 relop

id 2 {E.truelist:=makelist(next quad);

e.falselist:=makelist(nextquad+1); emit( ‘ j ’ relop.op,

‘, ’ id 1.place ‘ , ’ id 2 .place ‘ , ’‘ 0’ );

emit(

‘ j,-,-,0 ’ )}

(7) S → L:=E {emit(:=,E.place,-,L.place)}

(8) E →E+E {E.place:=newtemp ; 1 2

emit(+,E

.place,E 2

.place,E.place,)}

1 6. (8 分 ) Generate assembly code for

the

following sequence assuming that x,y and z are in memory

locations(noticing only two registers R1 and R2).

S=0

I=0

L1: if x>y goto L2

Z=s+a[i]

I=i+1

Goto L1

L2:

7. (6 分 ) Give out the all basic blocks of the following program fragment and construct the relevant flow graph(DAG).

read C

A=0

B=1

L4: A=A+B

if B>C goto L2

B=B+1

goto L4

L2: write A

8. (8 分 )Translate the assignment

statement b[i]=b*c-

b*d

into

(1) A syntax tree.

(2)Three address instructions.

答案::

(1)栈式动态存储分配

(2)堆式动态存储分配

(3)左

(4)语法分析

(5)目标代码生成

(6)表格管理

(7)xyz*ab+/+

(8)继承属性

(9)a+(i-1)*20+j-1

(10)基本块

一、选择题(每问 2 分,共20 分)

1.C B

2.D

3.B

4.A

5.D

6.A,C

7.BCD,选对一个得 1 分且不超过满分,选错一个扣一分,扣完

为止

8.BCD,选对一个得

二、解答题1 分且不超过满分,选错一个扣一分,扣完

为止

1.( 1)文法存在左递归,消除左递归后的文法为:E→ (E)E ’ |i E ’( 2 分)

E’→ TEE’ | ε( 2 分)

T→ *|+ (1 分)

(2)(5 分) 没考虑 #扣0.5 分,其它错或少写一个

0.5 分

FIRST(E)={(,i} FIRST(E ’ )={*

,+,

ε } FIRST(T)={*,+}

FOLLOW(E)={),*,+,#} FOWLLOW(E ’ )= {),*,+,#} FOLLOW(T)={(,i}

( 3)每错一个扣0.5 分,全错或不写不得分,扣完为止,

5 分

( ) i * + #

E E→ (E)E ’E→ iE ’

E’E’→εE’→TEE’E’→TEE’E’ → ε

E’ →εE’ →ε

T T→ * T→ +

2.( 1)规范推导过程如下。写错推导符号扣0.5 分, 错写或少写一步推导扣0.5 分,扣完为止,最左推导扣2分,共 4分。

S S(S) S( ) S( S)() S( )() S(S)()() S(S( S))()

()

S(S( ))()() S(S(S)())()()

S(S( )())()

() S(( )())()

()

(()())()()

( 2)( 1)中加下划线的部分是句柄,标识如(1)。每少写一个句

柄扣

0.5 分,扣完为止,

4 分。

( 3)每少写步扣

0.5 分,扣完为止,

4 分。S

S ( S )

)

S ( S

)

ε

)

S ( S ) ε

)

ε

S

( S ) )

ε

S

( S

)

)

3.( 1)打印的字符串是:12020(错一个扣0.5 分,共 3 分)

( 2)归约过程中错一步扣0.5 分,扣完为止。(共 5 分)

4.( 1)每少写一步扣0.5 分,扣完为止,共 5 分。

S

while M1.q=100 E1.t=102 do M2.q=102 S1

E1.f=107

εa

E2.f=103

(E3.t=102) εL.p=

x

:=

E4.p=T1

c>d x E5.p=

y

+

E6.p=z

y z

( 2)少写一个四元式

扣0.5 分,全错或不写不得分,回填错

误扣

0.5 分,

5 分。

四元式序列为:

100( j ,a, b,102) 101( j , _, _,107) 102( j ,c, d ,104) 103(( j, _, _,106) 104( , y, z, T1) 105(: , T1, _, x) 106( j , _, _,100)

5.( 1)少写一个扣1 分,全错或不写不得分,

5 分。

FIRSTVT(S)={a, ∧ ,(}

FIRSTVT(T)={, a,

∧,(}

LASTVT(S)={ a, ∧ ,)}

LASTVT(T)={ a, ∧

,),

, }

(2) 优先表如下。每错一个扣0.5 分,全错或不写不得分,扣完为止,

3 分

文法G[S] 没有两个非终结符相邻的情

况,

且其优先表中任一对终结符之间最多

满足

?、?、三种关系中的

一种,因此是 G[S] 算符优先文法。( 2 分)

可以不考虑终结符“ #”。

a ∧( ) , # A ? ? ? ∧? ? ? ( ? ? ? ?

) ? ?

, ? ? ? ? ? ? # ? ? ? ?

或者

( 3)优先函数。可以不考虑终结符“#”。每错一个

扣0.5 分,全错或不写不得分,扣完为止,共

5

分。

a ∧( ) , #

f 6 6 2 6 6 2

g 7 7 7 2 5 2

或者

a ∧( ) ,

f 4 4 2 4 4

g 5 5 5 2 3

三、填空题(每空 2 分,共 20 分)

1 目标程序(target code )语法分析( syntax analyzer )代码优化器( code optimizer )代码产生器( code generator )符号表管理( symbol table manager)

2 继承属性( inherited attribute )

3 局部优化( local optimization )

4 四元式( quatriple )

5 E + * ( ) id

四、单项选择题(每题 2 分,共 10 分)

1.B

2.D

3.B

4.D

5.C

五、解答题(共 70 分)

1.( 1) L(G)={0 m1m|M ≥1} 共 2 分,≥写成>扣 1 分

( 2) S=>0S1=>00S11=>000111,共 3 分, => 写成 -> 扣 1 分

( 3)共 3 分,错处扣

0.5 分,扣完为止

2. ( 1)空白表格也可以填写“错误”字样, 共 4 分,错一个扣

0.5 分,扣完为止

a b c $(#) S S→ aBc S→ bAB

A A→ aAb A→ b

B B→ b B→ εB→ ε

( 2)共 6 分,其中判断

“baabbb 是该文法句子”为2 分,其他错一个

0.5 分,扣完为

符号栈输入串规则

$S baabbb$

$BAb baabbb$ S→ bAB $BA aabbb$

$BbAa aabbb$A→ aAb $BbA abbb$

$BbbAa abbb$ A→ aAb $BbbA bbb$

$Bbbb bbb$ A→ b $Bbb bb$

$Bb b$

$b $ B→ ε$ $ success

3.(1) 共 6 分,其中判断“该文法为算符优先文法”

2 分,其他错一个

0.5 分,扣完为

+ * i

+ > < < * > > <

i > >

(2)共 4 分,错一个扣 0.5 分,扣完为止

+ * i

f 2 4 4

g 1 3 5

4.( 1)34242421 ,

4 分,错一个

0.5 分

(2)共 4 分,错一个

0.5 分,扣完为止

stack Input string action $ b(((aa)a)a)b$

$b (((aa)a)a)b$ shift

$b( ((aa)a)a)b$abbb$ shift $b(( (aa)a)a)b$bbb$ shift $b((( aa)a)a)b$bb$ shift $b(((a a)a)a)b$$ shift

$b(((A a)a)a)b$ reduce,

A → a

$b(((Aa )a)a)b$ shift $ b(((Aa) a)a)b$ shift

$ b(((B a)a)b$ reduce,

B → Aa)

$b((A a)a)b$ reduce,

A → (B

$b((Aa )a)b$ shift $b((Aa) a)b$ shift

$b(( B a)b$ reduce,

B → Aa)

$b(A a)b$ reduce,

A → (B

$b(Aa )b$ shift $b(Aa) b$ shift

$b(B b$ reduce,

B → Aa)

$bA b$ reduce,

A → (B

$bAb $ shift

$S $ reduce,

S → bAb

$s$ accept

5.共 12 分,其中带注释的分析树、三地址码序列和四元式序列

分别为 4 分,错一个序列扣0.5 分,而

错某点(某项)少于或等

于5个扣 0.5 分

带注释语法树 ( 略 )

三地址码序列四元式序列M1: if (x>y) goto M2 100 (j>, x,y,102) goto M4 101 (j,-,-,108)

M2: if (a=b) goto M3 102 (j=,a,b,104) goto M1 103 (j,-,-,100)

M3: t1=2*y 104 (*,2,y,t1)

t2=t1+a 105 (+,t1,a,t2)

x=t2 106 (=,t2,-,x)

goto M1 107 (j,-,-,100)

M4: 108 (-,-,-,-)

6.共 8 分,错一个扣

0.5 分,扣完为止

LD R1,0

ST S,R1

ST I,R1

L1: LD R1,X

SUB R1,R1,Y (OR SUB R1,Y)

BGTZ R1,L2

LD R2,a(R1)

ADD R2,R2,S (OR ADD R2,S)

ST Z,R2

LD R1,I ( 从这开始,下面的语句中的R1 也可以全部变成 R2) ADD R1,R1,1 (OR INC R1)

ST I,R1

BR L1

L2:

7.共 6 分,基本块划分和流图各为3 分,错一处扣 1 分,扣完为止

B1 B2 B3 read c

A=0

B=1

L4: A=A+B

If B>C goto L2 (OR B4)

B=B+1

Goto L4 (OR B2)

B4 L2: write A

8.( 1)共 4 分,错一项扣 1 分,扣完为止( 2)共 4 分,错一项扣 1 分,扣完为止

t1=b*c

t2=b*d

t3=t1-t2

t4=i+1 (or t4=i)

编译原理期末考试习题及答案

一、填空题|(每题4分,共20分) 1. 乔母斯基定义的3型文法(线性文法)产生式形式 A→Ba|a,或A→aB|a,A,B∈Vn, a,b∈Vt 。 2.语法分析程序的输入是单词符号,其输出是语法单位。 3 型为 B → .aB 的LR(0)项目被称为移进项目,型为 B → a.B 的LR(0) 项目被称为待约项目, 4.在属性文法中文法符号的两种属性分别为继承属性和综合属性。 5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。 二.已知文法 G(S) (1) E → T | E+T (2) T → F | F*F (3) F →(E)| i (1)写出句型(T*F+i)的最右推到并画出语法树。(4分) (2)写出上述句型的短语,直接短语和句柄。(4分) 答:(1)最右推到(2分) E ==> T ==> F ==> (E) ==> (E+T) ==> (E+F) ==> (E+i) ==> (T+i) ==> (T*F+i) (2) 语法树(2分) (3)(4分) 短语:(T*F+i),T*F+i ,T*F , i 直接短语:T*F , i 句柄:T*F 三. 证明文法G(S) :S → SaS |ε是二义的。(6分) 答:句子aaa对应的两颗语法树为:

因此,文法是二义文法 四.给定正规文法G(S): (1) S → Sa | Ab |b (2) A → Sa 请构造与之等价的DFA。(6分) 答:对应的NFA为:(6分) 状态转换表: a b {F} Φ{S} {S} {S,A} Φ {S,A} {S,A} {S} 五. 构造识别正规语言b*a(bb*a)*b* 最小的DFA(要求写出求解过程)。(15分)答:(1)对应的NFA(5分) a b {0} {1,3} {0} {1,3} Φ{2,3} {2,3} {1,3} {2,3} (5分) 六. 已知文法G(S) : (1) S → ^ | a | (T) (2) T → T,S | S 试:(1)消除文法的左递归;(4分) (2)构造相应的first 和 follow 集合。(6分) 答:(1)消除文法的左递归后文法 G’(S)为: (1) S → ^ | a | (T)

编译原理期末复习

编译原理期末复习 鉴于编译原理马上就要期末考试,我将手中集中的一些资料上的题目进行了整理归类,每种类型题目给出了所涉及到的基本知识,然后对每类题目中的第一道例题进行了做法进行了讲解,剩下的例题请给大家作为练习,答案也都给出,希望对大家复习有所帮助,最后由于时间很紧,整理的有些仓促,整理中难免有遗漏或错误,请大家见谅。 注:下面出现的字母中,若无特别说明,小写英文字母为终结符,大写英文字母为非终结符,希腊字母为终结符与非终结符的任意组合。 1、简答题(或者名词解释) 下面涉及到的概念中,加下划线的都是在以往一些试卷中出现的原题,务必掌握。 注:这类题目老师说答案不会超过一百个字,否则写的再多也不给分,有些点到即可,不要重复啰嗦。(1)简述编译程序的概念及其构成 答:1)编译程序:它特指把某种高级程序设计语言翻译成等价的低级程序设计语言的翻译程序。 2)构成: (2)简述词法分析阶段的主要任务(也有可能问语法分析阶段主要任务)答:词法分析的任务是输入源程序,对源程序进行扫描,识别其中的单词符号,把字符串形式的源程序转换成单词符号形式的源程序。 语法分析的主要任务是对输入的单词符号进行语法分析(根据语法规则进行推导或者归约),识别各类语法单位,判断输入是不是语法上正确的程序 (3) 简述编译程序的构造过程(这个大家看看,是对(1)和(2)的综合) 答:1)构造词法分析器:用于输入源程序进行词法分析,输出单词符号; 2)构造语法分析器:对输入的单词符号进行语法分析,识别各类语法单位,判断输入是不是语法上正确的程序 3)构造语义分析和中间代码产生器:按照语义规则对已归约出的语法单位进行语义分析并把它们翻译成中间代码。 4)构造优化器:对中间代码进行优化。 5) 构造目标代码生成器:把中间的代码翻译成目标程序。 6) 构造表格管理程序:登记源程序的各类信息和编译各阶段的进展情况。 7)构造错误处理程序:对出错进行处理。 (4) 说明编译和解释的区别: 1)编译要程序产生目标程序,解释程序是边解释边执行,不产生目标程序; 2)编译程序运行效率高而解释程序便于人机对话。 (5)文法:描述语言语法结构的形式规则,一般用一个四元式表示: G=(V T,V N,S,P),其中V T:终结符集合(非空) V N:非终结符集合(非空),且V T ?V N=? S:文法的开始符号,S?V N P:产生式集合(有限)。

编译原理期末考试卷

2001年编译原理试题 1.(10分)处于/* 和 */之间的串构成注解,注解中间没有*/。画出接受这种注解的DFA的状态转换图。 2.(10分)为语言 L ={a m b n | 0 ≤ m ≤ 2n}(即a的个数不超过b的个数的两倍) 写一个LR(1)文法,不准超过6个产生式。(若超过6个产生式,不给分。若所写文法不是LR(1)文法,最多给5分。) 3.(10分)构造下面文法的LL(1)分析表。 D → TL T → int | real L → id R R → , id R | ε 4.(15分)就下面文法 S → ( L) | a L → L , S | S ?给出一个语法制导定义,它输出配对括号的个数。 ?给出一个翻译方案,它输出每个a的嵌套深度。 如句子(a, (a, a) ),第一小题的输出是2,第二小题的输出是1 2 2。 5.(10分)Pascal语言for语句的含义见教材第222页习题7.13。请为该语句设计一种合理的中间代码结构。你可以按第215页图7.17的方式或者第219页图7.19的方式写出你的设计,不需要写产生中间代码的语法制导定义。 6.(5分)一个C语言程序如下: func(i1,i2,i3) long i1,i2,i3; { long j1,j2,j3; printf("Addresses of i1,i2,i3 = %o,%o,%o\n",&i1,&i2,&i3); printf("Addresses of j1,j2,j3 = %o,%o,%o\n",&j1,&j2,&j3); } main() { long i1,i2,i3;

编译原理期末考试题目及答案

一、填空题(每空2分,共20分) 1.编译程序首先要识别出源程序中每个单词,然后再分析每个句子并翻译其意义。 2.编译器常用的语法分析方法有自底向上和自顶向下两种。 3.通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析,中间代码生成、代码优化与目标代码的生成则是对源程序的综合。 4.程序设计语言的发展带来了日渐多变的运行时存储管理方案,主要分为两大类,即静态存储分配方案和动态存储分配方案。 5.对编译程序而言,输入数据是源程序,输出结果是目标程序。 1.计算机执行用高级语言编写的程序主要有两种途径:解释和编译。 2.扫描器是词法分析器,它接受输入的源程序,对源程序进行词法分析并识别出一个个单词符号,其输出结果是单词符号,供语法分析器使用。 3.自下而上分析法采用移进、归约、错误处理、接受等四种操作。 4.一个LL(1)分析程序需要用到一张分析表和符号栈。 5.后缀式abc-/所代表的表达式是a/(b-c)。 二、单项选择题(每小题2分,共20分) 1.词法分析器的输出结果是__C。 A.单词的种别编码B.单词在符号表中的位置 C.单词的种别编码和自身值D.单词自身值 2.正规式M 1 和M 2 等价是指__C_。 A.M1和M2的状态数相等 B.M1和M2的有向边条数相等 C.M1和M2所识别的语言集相等D.M1和M2状态数和有向边条数相等 3.文法G:S→xSx|y所识别的语言是_C____。 A.xyx B.(xyx)* C.xnyxn(n≥0) D.x*yx* 4.如果文法G是无二义的,则它的任何句子α_A____。 A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能不同 C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导,但它们对应的语法树相同5.构造编译程序应掌握____D__。 A.源程序B.目标语言C.编译方法D.以上三项都是 6.四元式之间的联系是通过__B___实现的。 A.指示器B.临时变量C.符号表D.程序变量 7.表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。 A.┐AB∨∧CD∨B.A┐B∨CD∨∧ C.AB∨┐CD∨∧D.A┐B∨∧CD∨ 8. 优化可生成__D___的目标代码。 A.运行时间较短 B.占用存储空间较小 C.运行时间短但占用内存空间大D.运行时间短且占用存储空间小 9.下列___C___优化方法不是针对循环优化进行的。 A. 强度削弱B.删除归纳变量C.删除多余运算D.代码外提 10.编译程序使用_B_区别标识符的作用域。 A. 说明标识符的过程或函数名B.说明标识符的过程或函数的静态层次 C.说明标识符的过程或函数的动态层次 D. 标识符的行号 三、判断题(对的打√,错的打×,每小题1分,共10分) 2.一个有限状态自动机中,有且仅有一个唯一的终态。x

编译原理试题(卷)汇总-编译原理期末试题(卷)(8套含答案解析-大题集)

编译原理考试题及答案汇总 一、选择 1.将编译程序分成若干个“遍”是为了_B__。 A . 提高程序的执行效率 B.使程序的结构更加清晰 C. 利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2.正规式 MI 和 M2 等价是指__C__。 A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。 C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等 3.中间代码生成时所依据的是 _C_。 A.语法规则 B.词法规则 C.语义规则 D.等价变换规则 4.后缀式 ab+cd+/可用表达式__B_来表示。 A. a+b/c+d B.(a+b)/(c+d) C. a+b/(c+d) D. a+b+c/d 6.一个编译程序中,不仅包含词法分析,_A____,中间代码生成,代码优化,目标代码生成等五个部分。 A.( ) 语法分析 B.( )文法分析 C.( )语言分析 D.( )解释分析 7.词法分析器用于识别__C___。 A.( ) 字符串 B.( )语句 C.( )单词 D.( )标识符 8.语法分析器则可以发现源程序中的___D__。 A.( ) 语义错误 B.( ) 语法和语义错误 C.( ) 错误并校正 D.( ) 语法错误 9.下面关于解释程序的描述正确的是__B___。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A.( ) (1)(2) B.( ) (1) C.( ) (1)(2)(3) D.( ) (2)(3) 10.解释程序处理语言时 , 大多数采用的是__B___方法。 A.( ) 源程序命令被逐个直接解释执行 B.( ) 先将源程序转化为中间代码 , 再解释执行 C.( ) 先将源程序解释转化为目标程序 , 再执行 D.( ) 以上方法都可以 11.编译过程中 , 语法分析器的任务就是__B___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A.( ) (2)(3) B.( ) (2)(3)(4)C.( ) (1)(2)(3) D.( ) (1)(2)(3)(4) 12.编译程序是一种___C__。 A. ( ) 汇编程序 B.( ) 翻译程序 C.( ) 解释程序 D.( ) 目标程序 13.文法 G 所描述的语言是_C____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B.( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C.( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 14.文法分为四种类型,即 0 型、1 型、2 型、3 型。其中 3 型文法是___B__。 A. ( ) 短语文法 B.( ) 正则文法 C.( ) 上下文有关文法 D.( ) 上下文无关文法15.一个上下文无关文法 G 包括四个组成部分,它们是:一组非终结符号,一组终结符号,一个开始符号,以及一组 __D___。 A.( ) 句子 B.( ) 句型 C.( ) 单词 D.( ) 产生式 16.通常一个编译程序中,不仅包含词法分析,语法分析,中间代码生成,代码优化,目标代码生成等五个部分,还应包括_C____。

期末考试编译原理试卷及答案

一. 填空题(每空2分,共20分) 1. 不同的编译程序关于数据空间的存储分配策略可能不同,但大部分编译中采用的方案有两种:静 态存储分配方案和动态存储分配方案,而后者又分为(1) 和 (2) 。 2. 规范规约是最(3)规约。 3. 编译程序的工作过程一般划分为5个阶段:词法分析、(4) 、语义分析与中间代码生成,代码优化及(5) 。另外还有(6)和出错处理。 4.表达式x+y*z/(a+b)的后缀式为 (7) 。 5.文法符号的属性有综合属性和 (8)。 6.假设二位数组按行存放,而且每个元素占用一个存储单元,则数组a[1..15,1..20]某个元素a[i ,j]的地址 计算公式为(9)。 7.局部优化是局限于一个(10)范围内的一种优化。 二. 选择题(1-6为单选题,7-8为多选题,每问2分,共20分) 1. 一个上下文无关文法G 包括四个组成部分:一组终结符,一组非终结符,一个( ),以及一组 ( )。 A . 字符串 B . 产生式 C . 开始符号 D . 文法 2.程序的基本块是指( )。 A . 一个子程序 B . 一个仅有一个入口和一个出口的语句 C . 一个没有嵌套的程序段 D . 一组顺序执行的程序段,仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中,递归下降分析法属于( )分析方法。 A . 自左向右 B . 自顶向下 C . 自底向上 D . 自右向左 4.在通常的语法分析方法中,( )特别适用于表达式的分析。 A . 算符优先分析法 B . LR 分析法 C . 递归下降分析法 D . LL (1)分析法 5.经过编译所得到的目标程序是( )。 A . 四元式序列 B . 间接三元式序列 C . 二元式序列 D . 机器语言程序或汇编语言程序 6. 一个文法所描述的语言是( );描述一个语言的文法是( )。 A . 唯一的 B . 不唯一的 C . 可能唯一,也可能不唯一 7. 如果在文法G 中存在一个句子,当其满足下列条件( )之一时,则称该文法是二义文法。 A . 其最左推导和最右推导相同 B . 该句子有两个不同的最左推导 C . 该句子有两个不同的最右推导 D . 该句子有两棵不同的语法树

《编译原理》期末考试复习题

《编译原理》期末考试复习题 一、是非题(请在括号内,正确的划√,错误的划×)(每个2分,共20分) ×1.计算机高级语言翻译成低级语言只有解释一种方式。() ×2.在编译中进行语法检查的目的是为了发现程序中所有错误。() √3.甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 () ×4.正则文法其产生式为 A->a , A->Bb, A,B∈VN , a 、b∈VT 。 () √5.每个文法都能改写为 LL(1) 文法。 () √6.递归下降法允许任一非终极符是直接左递归的。 () ×7.算符优先关系表不一定存在对应的优先函数。 () ×8.自底而上语法分析方法的主要问题是候选式的选择。 () ×9.LR 法是自顶向下语法分析方法。 () ×10.简单优先文法允许任意两个产生式具有相同右部。 () 三、填空题(每空1分,共10分) 1.编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有__ ___和 ___ _。 表格管理出错处理_ 2.若源程序是用高级语言编写的,__ __是机器语言程序或汇编程序,则其翻译程序称为 __ __ 。 _目标程序_编译程序 3.编译方式与解释方式的根本区别在于__ __。 是否生成目标代码_ 4.对编译程序而言,输入数据是__ __, 输出结果是__ ___。 _源程序目标程序

5.产生式是用于定义__ __的一种书写规则。 _语法成分 6.语法分析最常用的两类方法是___ __和__ __分析法。 自上而下_自下而上 四、简答题(20分) 1. 什么是句子?什么是语言 ? 答:(1)设G是一个给定的文法,S是文法的开始符号,如果S x(其中x∈VT*),则称x是文法的一个句子。 (2)设G[S]是给定文法,则由文法G所定义的语言L(G)可描述为:L(G)={x│S x,x∈VT*} 。 一、是非题(请在括号内,正确的划√,错误的划×)(每个2分,共20分) ×1.对于数据空间的存贮分配,FORTRAN采用动态贮存分配策略。() ×2.甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。() √3.递归下降分析法是自顶向上分析方法。() ×4.产生式是用于定义词法成分的一种书写规则。() √5.LR 法是自顶向下语法分析方法。() √6.在SLR (1 )分析法的名称中,S的含义是简单的。() ×7.综合属性是用于“ 自上而下” 传递信息。() ×8.符号表中的信息栏中登记了每个名字的属性和特征等有关信息,如类型、种属、所占单元大小、地址等等。() ×9.程序语言的语言处理程序是一种应用软件。() ×10.解释程序适用于COBOL 和FORTRAN 语言。() 三、填空题(每空1分,共10分) 1.一个句型中的最左简单短语称为该句型的___句柄__。

编译原理试题及答案(期末复习版).pdf

<编译原理>历年试题及答案 一.(每项选择 2 分,共 20 分)选择题 1.将 编译程序分成若干个“遍”是为了_b__。 a.提 高程序的执行效率 b.使程序的结构更加清晰 c. 利用有限的机器内存并提高机器的执行效率 d. 利用有限的机器内存但降低了机器的执行效率 2.构造编译程序应掌握__d__。 a.源程序 b.目标语言 c.编译方 法 d.以上三项都是 3.变量应 当 c_。 a.持有左值 b.持有右值 c.既持有左值又持有右值 d.既不持 有左值也不持有右值 4.编译程序绝大多数时间花在 _d___上。 a.出错处理 b.词法分析 c.目标代码 生成 d.管理表格 5.词法分析器的输 出结果是_c___。 a.单词的种别编码 b.单词在符号表中的位置 c.单词 的种别编码和自身值 d.单词自身值 6.正规式 MI 和 M2 等价是指__c__。 a. MI 和 M2 的状态数相等 b.Ml 和 M2 的有向弧条数相等。 C.M1 和 M2 所识别的语言集相等 d. Ml 和 M2 状态数和有向弧条数相等7.中间代码生成时所依据的是—c。 a.语法规则 b.词法规则c.语义规则 d.等价变换规则 8.后缀式 ab+cd+/可用表达式__b_来表示。 a. a+b/c+d b. (a+b)/(c+d) c. a+b/(c+d) d. a+b+c/d 9.程序所需 的数据空间在程序运行前就可确定,称为____c__管理技术。 a.动态存储 b.栈式存储 c.静态存储 d.堆式存储 10.堆式 动态分配申请和释放存储空间遵守___d_____原则。 a.先请先放 b.先请后放 c.后请先放 d.任意 二(每小题 10 分,共 80 分)简答题 1.画出编译程序的 总体结构图,简述各部分的主要功能。 2. 已知文法 G[E]: E→ET+|T T→TF* | F F→F^ | a 试证:FF^^*是文法的句型,指出该句型的短语、简单短语和句柄.

编译原理考试试卷

南京工业大学继续教育学院编译原理期末考试试卷 (2012-2013学年) A卷 一、选择题(每题2分,共20分) 得分 1. 一个上下文无关文法G包括四个组成部分:一组终结符,一组非终结符,一个_____,以及一组产生式。 A.字符串 B.运算符号 C.开始符号 D.文法 2.程序的基本块是指_____。 A.一个子程序 B.一个仅有一个入口和一个出口的语句 C.一个没有嵌套的程序段 D.一组顺序执行的程序段,仅有一个入口和一 个出口 3. 高级语言编译程序常用的语法分析方法中,递归下降分析法属于_____分析方法。 A.自左向右 B.自顶向下 C.自底向上 D.自右向左 4.经过编译所得到的目标程序是_____。 A.四元式序列 B.间接三元式序列 C.二元式序列 D.机器语言程序或汇编语言程序 5.运行阶段的存储组织与管理的目的是_____。 ①提高编译程序的运行速度②节省编译程序的存储空间 ③提高目标程序的运行速度④为运行阶段的存储分配做准备 A. ①② B. ②③ C. ③④ D. ④②6.词法分析器的输出结果是_____。 A.( ) 单词的种别编码B.( ) 单词在符号表中的位置C.( ) 单词的种别编码和自身值D.( ) 单词自身值 7.正规式M 1 和M 2 等价是指_____。

A.( ) M1和M2的状态数相等B.( ) M1和M2的有向边条数相等 C.( ) M1和M2所识别的语言集相等D.( ) M1和M2状态数和有向边条数相等 8.文法G:S→xSx|y所识别的语言是_____。 A.( ) xyx B.( ) (xyx)* C.( ) xnyxn(n≥0) D.( ) x*yx* 9.语言是_____。 A.句子的集合B.产生式的集合 C.符号串的集合D.句型的集合 10.编译程序前三个阶段完成的工作是 A.词法分析、语法分析和代码优化 B.代码生成、代码优化和词法分析 C.词法分析、语法分析、语义分析和中间代码生成 D.词法分析、语法分析和代码优化 二、名词解释(每题2分,共20分) 得分 1.最左推导: 2.语法: 3.文法: 4.基本块: 5.语法制导翻译: 6.短语: 7.规范句型:

编译原理期末考试试卷及答案

期末考试试卷(A)卷 一、填空题(每小题2分,共20分) 1、字母表∑,用∑*表示∑上所有有穷长的串集合,∑*称为∑的①。 2、设z=abc,则z的固有头是①。 3、如何由语言基本符号组成程序中各个语法成分(包括程序)的一组规则叫 ①。 4、设∑={a,b},∑上的正规式(a|b)(a|b) 相应的正规集为① 5、NFA的映象f是从"状态×字"映射到"状态子集",f为①值函数。 6、LR分析是按规范句型的①为可归约串。 7、结点的①属性值由该结点的兄弟结点和父结点的属性值计算。 8、如果分析树中一结点的属性b依赖于属性c,那么这个结点的属性b的语义规 则的计算必须在定义属性c的语义规则的计算①。 9、对于栈式符号表,引入一个显示嵌套层次关系表- ①表,该表总是 指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置。 10、任一有向边序列n1 → n2,n2 → n3,…,nk-1 → nk为从结点n1到结点nk 的一条通路。如果n1=nk,则称该通路为①。 二、单项选择(每小题2分,共14分) 1、乔姆斯基把文法分成4种类型,即0型、1型、2型和3型。其中3型文法也称 为()。 A.上下无关文法 B.正规文法 C.上下文有关文法 D.无限制文法 2、生成非0开头的正偶数集的文法是()。 A. Z::=ABC B. Z::=ABC C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|ε B::=BA|B0|0 A::=1|2|3|…|9 A::=1|2|3|…|9 C. Z::=ABC|2|4|6|8 D. Z::=ABC|2|4|6|8 C::=0|2|4|6|8 C::=0|2|4|6|8 B::=BA|B0|0 B::=BA|B0|ε A::=1|2|3|…|9 A::=1|2|3|…|9 3、简单优先分析法从左到右扫描输入串,当栈顶出现()时进归约。

编译原理试题及答案

参考答案 一、单项选择题(共10小题,每小题2分,共20分) 1.语言是 A .句子的集合 B .产生式的集合 C .符号串的集合 D .句型的集合 2.编译程序前三个阶段完成的工作是 A .词法分析、语法分析和代码优化 B .代码生成、代码优化和词法分析 C .词法分析、语法分析、语义分析和中间代码生成 D .词法分析、语法分析和代码优化 3.一个句型中称为句柄的是该句型的最左 A .非终结符号 B .短语 C .句子 D .直接短语 4.下推自动机识别的语言是 A .0型语言 B .1型语言 C .2型语言 D .3型语言 5.扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即 A . 字符 B .单词 C .句子 D .句型 6.对应Chomsky 四种文法的四种语言之间的关系是 A .L 0?L 1?L 2?L 3 B .L 3?L 2?L 1?L 0 C .L 3=L 2?L 1?L 0 D .L 0?L 1?L 2=L 3 7.词法分析的任务是 A .识别单词 B .分析句子的含义 C .识别句子 D .生成目标代码 8.常用的中间代码形式不含 A .三元式 B .四元式 C .逆波兰式 D .语法树 9. 代码优化的目的是 A .节省时间 B .节省空间 C .节省时间和空间 D .把编译程序进行等价交换 10.代码生成阶段的主要任务是 A .把高级语言翻译成汇编语言 B .把高级语言翻译成机器语言 C .把中间代码变换成依赖具体机器的目标代码 装 订 线

D.把汇编语言翻译成机器语言 二、填空题(本大题共5小题,每小题2分,共10分) 1.编译程序首先要识别出源程序中每个(单词),然后再分析每个(句子)并翻译其意义。2.编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。 3.通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析),中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。 4.程序设计语言的发展带来了日渐多变的运行时存储管理方案,主要分为两大类,即(静态存储分配)方案和(动态存储分配)方案。 5.对编译程序而言,输入数据是(源程序),输出结果是(目标程序)。 三、名词解释题(共5小题,每小题4分,共20分) 1.词法分析 词法分析的主要任务是从左向右扫描每行源程序的符号,按照词法规则 从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位, 并转换成统一的内部表示(token),送给语法分析程序。 2.LL(1)文法 若文法的任何两个产生式A →α | β都满足下面两个条件: (1)FIRST(α) ? FIRST(β ) = φ; (2)若β?* ε,那么FIRST(α) ? FOLLOW( A ) = φ。 我们把满足这两个条件的文法叫做LL(1)文法,其中的第一个L代表从左 向右扫描输入,第二个L表示产生最左推导,1代表在决定分析器的每步 动作时向前看一个输入符号。除了没有公共左因子外,LL(1)文法还有一 些明显的性质,它不是二义的,也不含左递归。 3.语法树 句子的树结构表示法称为语法树(语法分析树或语法推导树)。 给定文法G=(V N,V T,P,S),对于G的任何句型都能构造与之关联的 语法树。这棵树具有下列特征: (1)根节点的标记是开始符号S。 (2)每个节点的标记都是V中的一个符号。 (3)若一棵子树的根节点为A,且其所有直接子孙的标记从左向右的排列 次序为A1A2…A R,那么A→A1A2…A R一定是P中的一条产生式。

(完整word版)编译原理期末试题(二)含答案,推荐文档

《编译原理》期末试题(二) 一、是非题: 1.一个上下文无关文法的开始符,可以是终结符或非终结符。 ( ) 2.一个句型的直接短语是唯一的。() 3.已经证明文法的二义性是可判定的。() 4.每个基本块可用一个DAG表示。() 5.每个过程的活动记录的体积在编译时可静态确定。() 6.2型文法一定是3型文法。() 7.一个句型一定句子。 ( ) 8.算符优先分析法每次都是对句柄进行归约。 X ( ) 9.采用三元式实现三地址代码时,不利于对中间代码进行优化。() 10.编译过程中,语法分析器的任务是分析单词是怎样构成的。 ( ) 11.一个优先表一定存在相应的优先函数。 X ( ) 12.目标代码生成时,应考虑如何充分利用计算机的寄存器的问题。 ( ) 13.递归下降分析法是一种自下而上分析法。 ( ) 14.并不是每个文法都能改写成LL(1)文法。 ( ) 15.每个基本块只有一个入口和一个出口。 ( ) 16.一个LL(1)文法一定是无二义的。 ( ) 17.逆波兰法表示的表达试亦称前缀式。 ( ) 18.目标代码生成时,应考虑如何充分利用计算机的寄存器的问题。 ( ) 19.正规文法产生的语言都可以用上下文无关文法来描述。 ( ) 20.一个优先表一定存在相应的优先函数。 ( ) 21.3型文法一定是2型文法。 ( ) 22.如果一个文法存在某个句子对应两棵不同的语法树,则文法是二义性的。 ( ) 答案:1.× 2.× 3.× 4.√ 5.√ 6.×7.×8.× 9.√10.× 11.× 12.√ 13.× 14.√ 15.√ 16.√ 17.× 18.√19.√ 20.×21.√22.√ 二、填空题: 2.编译过程可分为(词法分析),(语法分析),(语义分析与中间代码生成),(优化)和(目标 代码生成)五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树,则称这个文法是(二义性的)。 4.从功能上说,程序语言的语句大体可分为(执行性)语句和(说明性)语句两大类。 5.语法分析器的输入是(单词符号),其输出是(语法单位)。 6.扫描器的任务是从(源程序中)中识别出一个个(单词符号)。 7.符号表中的信息栏中登记了每个名字的有关的性质,如(类型、种属、所占单元大小、地址)等等。 8.一个过程相应的DISPLAY表的内容为(现行活动记录地址和所有外层最新活动记录的地址) 10.常用的两种动态存贮分配办法是(栈式)动态分配和(堆式)动态分配。 11.一个名字的属性包括( 类型)和(作用域 )。 12.常用的参数传递方式有(传地址),(传值),(传名) 13.根据优化所涉及的程序范围,可将优化分成为(局部优化),(循环优化),(全局优化)三个级别。 14.语法分析的方法大致可分为两类,一类是(自上而下)分析法,另一类是(自下而上) 分析法。 15.预测分析程序是使用一张(分析表)和一个(符号栈)进行联合控制的。 17.一张转换图只包含有限个状态,其中有一个被认为是(初)态;而且实际上至少要有一个(终)态。 19.语法分析是依据语言的(语法)规则进行。中间代码产生是依据语言的(语义)规则进行的。 21.一个文法G,若它的预测分析表M不含多重定义,则该文法是(LL(1) 文法)文法。 22.对于数据空间的存贮分配, FORTRAN采用( 静态策略, PASCAL采用( 动态)策略。

编译原理2011期末考试试卷答案

2011~ 2012 学年第 1 学期期末考试试卷答案 《编译原理》(共 4 页) (考试时间: 2011 年 12 月 25 日) 一、选择题(每题 1 分,共 10 分) 1.B 2.D 3.A 4.D 5.D 6.C 7.B 8.C 9.D 10.B 二、简答题(每题 5 分,共 20 分) 1.何谓二义性文法?试举一例说明。 答:若文法G 的一个句子对应有两棵或两棵以上不同的推导树,则称该句子是 二义性的。产生二义性句子的文法称为二义性文法,否则该文法是无二义性的。 例子:给定文法G[] : *||a|b 考察句子 ab*,它有两棵不同的推导树,如下所示: * a * b a b a 2.通过合并 LR(1) 文法中的同心状态得到的 LALR(1) 文法可能会产生哪些冲突?一定不会产生哪些冲突?为什么? 答:可能会产生归约 -归约冲突,一定不会产生移进 -归约冲突。 因为在对 LR(1) 合并同心集合时,有可能将原本没有冲突的同心集的项目集 合并后造成一些归约项目向前搜索符集合的交集不是空,产生归约-归约冲突。但是由于文法本身已经是LR(1) 文法,因此可知,在项目集中一定不存在移进 -归约冲突,也就是移进项目要求输入的终结符和任意归约项目的向前搜索符集合的交集都是空集。这样,在将同心集合并之后,移进项目要求输入的终结符和归约项目的向前搜索符集合的交集也还是空集。 3.自顶向下的预测分析方法为什么不能分析具有左递归的文法? 答:在自顶向下的语法分析技术中,要解决的问题是根据当前输入符号判断将识 别符号以及非终结符号替换成哪条规则的右部,若文法具有左递归,则在分析过程中,无法判断替换的规则,造成无穷递归求解过程。 4.设 G=(V N,V T, P,)是上下文无关文法,产生式集合P 中任意一个产生式应具有什么样的形式?若G 是正则文法呢? 答:上下文无关文法的产生式形式为: A →α,其中, A ∈ V N,α∈( V N∪V T)* 正则文法产生式形式为: N,a∈V T A→,或→ (右线性文法)其中,A,B ∈V aBA a A→Ba,或 A → a(左线性文法)其中, A,B ∈ V N, a∈V T 三、推导题(共70 分) 1.对于文法 G[S]:

编译原理期末A试卷答案

黄冈师范学院 2012—2013学年度第一学期期末试卷参考答案 考试课程:编译原理考核类型:考试A卷 考试形式:闭卷出卷教师:牛冀平 考试专业:计算机科学与技术,软件工程 考试班级:计科201001班,软件201001班 一、填空(每空0.5分,共 10分) 1、编译程序的功能是是对(高级语言)进行翻译,使之生成目标代码。 2、编译程序的工作过程一般划分为5个阶段:(词法分析)、语法分析、语义分析与中间代码生成,(代码优化)及目标代码生成。另外还有表格管理和(出错处理)。 3、一个上下文无关文法所含四个组成部分是一组终结符号、一组(非终结符号)、一个开始符号、(一组产生式)。 4、设G是一个给定的文法,S是文法的开始符号,如果S=> x(其中x∈V*),则称x 是文法的一个(句型)。 5、规范归约中的可归约串是指句柄,算符优先分析中的可归约串是指(最左素短语)。 6、在编译过程中,可采用的中间代码形式有()、()、()等。(三元式、间接三元式、四元式、逆波兰式、抽象语法树)(任选三个即可) 7、语法分析最常用的两类方法是(自上而下)和(自下而上)分析法。 8、表达式(a+b)*c的后缀表达式为(ab+c*)。 9、符号表的结构一般有(线性表)、(有序表)、(散列表或哈希表)等。 分别使用的查找方法有(顺序查找)、(折半查找)和(哈希法查找) 10、代码优化的目的是(减少代码的时空开销)。 11、寄存器是CPU内部的(存储单元),其访问时间小于CPU对内存的访问时间。 12、如果一个句子存在两棵不同的语法树就说明该句子是(二义性)的。 二、选择题(每题1分,共10分)

编译原理试题及答案——加强版

编译原理试题及答案 <高级版> 一、对于文法 G[S] : S → 1A | 0B | ε A → 0S | 1AA B → 1S | 0BB ⑴ (3 分 ) 请写出三个关于 G[S] 的句子; ⑵ (4 分 ) 符号串 11A0S 是否为 G [S] 的句型?试证明你的结论。 ⑶ (3 分 ) 试画出 001B 关于 G [S] 的语法树。 二、请构造一个文法,使其产生这样的表达式 E :表达式中只含有双目运算符 + 、 * ,且 + 的优先级高于 * , + 采用右结合, * 采用左结合,运算对象只有标识符 i ,可以用括号改变运算符优先级。要求给出该文法的形式化描述。 三、设有语言 L={ α | α∈ {0,1} + ,且α不以 0 开头,但以 00 结尾 } 。 ⑴试写出描述 L 的正规表达式; ⑵构造识别 L 的 DFA (要求给出详细过程,并画出构造过程中的 NDFA 、 DFA 的状态转换图,以及 DFA 的形式化描述 ) 。 四、给定文法 G[S] : S → AB A → a B | bS | c B → AS | d ⑴ (6 分 ) 请给出每一个产生式右部的 First 集;

⑵ (3 分 ) 请给出每一个非终结符号的 Follow 集; ⑶ (8 分 ) 请构造该文法的 LL(1) 分析表; ⑷ (8 分 ) 什么是 LL(1) 文法?该文法是 LL(1) 文法吗?为什么? 五、给定文法 G[S] : S → SaA|a A → AbS|b ⑴请构造该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 。 ⑵请构造该文法的 LR(0) 分析表。 ⑶什么是 LR(0) 文法?该文法是 LR(0) 文法吗?为什么? ⑷什么是 SLR(1) 文法?该文法是 SLR(1) 文法吗?为什么? 六、给定下列语句: if a+b>c then x := a*(b-c) + (b*c-d)/e ⑴写出其等价的逆波兰表示; ⑵写出其等价的四元式序列。 七、已知下列 C 语言程序: int * f() { int a = 100; return &a; } main()

编译原理期末考试题目及答案

一、填空题(每空 2分,共20分) 1编译程序首先要识别出源程序中每个 单词,然后再分析每个句子并翻译其意义。 2?编译器常用的语法分析方法 有自底向上 和自顶向下 两种。 3?通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的 分析,中间代码生成、代码 优化与目标代码的生成则是对源程序的 综合。 4?程序设计语言的发展带来了日渐多变的运行时存储管理方案,主要分为两大类,即 静态存储分配 方案和动态存储分配 5?对编译程序而言,输入数据是 源程序,输出结果是目标程序。 1计算机执行用高级语言编写的程序主要有两种途径: 解释和编译。 2?扫描器是词法分析器,它接受输入的 源程序,对源程序进行词法分析并识别出一个个单词符号,其输出结果是单词符 号,供语法 分析器使用。 3?自下而上分析法采用 移进、归约、错误处理、 接受等四种操作。 4?一个LL (1)分析程序需要用到 一张分析表 和符号栈。 5. 后缀式abc-/所代表的表达式是 a/(b-c )。 3 . 文法G : S T xSx|y 所识别的语言是 _C _________ 。 A ? xyx B ? (xyx)* C ? xnyxn(n > 0) D ? x*yx* 4 ?如果文法 G 是无二义的,则它的任何句子 a_ ______ 。 A ?最左推导和最右推导对应的语法树必定相同 B ?最左推导和最右推导对应的语法树可能不同 C ?最左推导和最右推导必定相同 D ?可能存在两个不同的最左推导,但它们对应的语法树相同 5 ?构造编译程序应掌握 _____ D_。 A ?源程序 B ?目标语言 C ?编译方法 6. 四元式之间的联系是通过 __B —实现的。 A .指示器 B .临时变量 C ?符号表 7. 表达式(「A B ) A (C V D )的逆波兰表示为__B_。 A . 「AB VA CD V B . AqB V CD VA 9. 下列—C —优化方法不是针对循环优化进行的。 A.强度削弱 B .删除归纳变量 10 .编译程序使用_B_区别标识符的作用域。 A.说明标识符的过程或函数名 C .说明标识符的过程或函数的动态层次 三、判断题(对的打",错的打X,每小题 1分,共10 分) 2 . 一个有限状态自动机中,有且仅有一个唯一的终态。 二、单项选择题(每小题 2分,共20分) 1词法分析器的输出结果是 _C 。 A ?单词的种别编码 B ? C ?单词的种别编码和自身值 D ? 2. 正规式 M 1和M 2等价是指__C_。 A ? M1和M2的状态数相等 C ? M1和M2所识别的语言集相等 单词在符号表中的位置 单词自身值 B ? M1和M2的有向边条数相等 D ? M1和M2状态数和有向边条数相等 D .以上三项都是 D .程序变量 C . AB V 「C D VA D . AqB VA CD V 8. 优化可生成__D_的目标代码。 A .运行时间较短 C .运行时间短但占用内存空间大 B .占用存储空间较小 D .运行时间短且占用存储空间小 C .删除多余运算 D ?代码外提 B .说明标识符的过程或函数的静态层次 D.标识符的行号

编译原理期末试题答案

一、单项选择题(共10小题,每小题2分,共20分) 1.语言是 A.句子的集合B.产生式的集合 C.符号串的集合D.句型的集合 2.编译程序前三个阶段完成的工作是 A.词法分析、语法分析和代码优化 B.代码生成、代码优化和词法分析 C.词法分析、语法分析、语义分析和中间代码生成 D.词法分析、语法分析和代码优化 3.一个句型中称为句柄的是该句型的最左 A.非终结符号B.短语C.句子D.直接短语 4.下推自动机识别的语言是 A.0型语言B.1型语言 C.2型语言D.3型语言 5.扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即 A.字符B.单词C.句子D.句型 6.对应Chomsky四种文法的四种语言之间的关系是 A.L0?L1?L2?L3 B.L3?L2?L1?L0 C.L3=L2?L1?L0D.L0?L1?L2=L3 7.词法分析的任务是 A.识别单词B.分析句子的含义 C.识别句子D.生成目标代码 8.常用的中间代码形式不含 A.三元式B.四元式C.逆波兰式D.语法树 9.代码优化的目的是 A.节省时间B.节省空间 C.节省时间和空间D.把编译程序进行等价交换 10.代码生成阶段的主要任务是 A.把高级语言翻译成汇编语言 B.把高级语言翻译成机器语言 C.把中间代码变换成依赖具体机器的目标代码 D.把汇编语言翻译成机器语言 二、填空题(本大题共5小题,每小题2分,共10分) 1.编译程序首先要识别出源程序中每个(单词),然后再分析每个(句子)并翻译其意义。2.编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。 3.通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析),中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。 4.程序设计语言的发展带来了日渐多变的运行时存储管理方案,主要分为两大类,即(静态存储分配)方案和(动态存储分配)方案。 5.对编译程序而言,输入数据是(源程序),输出结果是(目标程序)。 三、名词解释题(共5小题,每小题4分,共20分) 1.词法分析

编译原理期末测验试卷及答案

编译原理期末测验试卷及答案

————————————————————————————————作者:————————————————————————————————日期:

一. 填空题(每空2分,共20分) 1. 不同的编译程序关于数据空间的存储分配策略可能不同,但大部分编译中采用的方案有两 种:静态存储分配方案和动态存储分配方案,而后者又分为(1) 和 (2) 。 2. 规范规约是最(3)规约。 3. 编译程序的工作过程一般划分为5个阶段:词法分析、(4) 、语义分析与中间代码生成,代码优化及(5) 。另外还有(6)和出错处理。 4.表达式x+y*z/(a+b)的后缀式为 (7) 。 5.文法符号的属性有综合属性和 (8)。 6.假设二位数组按行存放,而且每个元素占用一个存储单元,则数组a[1..15,1..20]某个元素a[i ,j]的地址计算公式为(9)。 7.局部优化是局限于一个(10)范围内的一种优化。 二. 选择题(1-6为单选题,7-8为多选题,每问2分,共20分) 1. 一个上下文无关文法G 包括四个组成部分:一组终结符,一组非终结符,一个( ),以 及一组( )。 A . 字符串 B . 产生式 C . 开始符号 D . 文法 2.程序的基本块是指( )。 A . 一个子程序 B . 一个仅有一个入口和一个出口的语句 C . 一个没有嵌套的程序段 D . 一组顺序执行的程序段,仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中,递归下降分析法属于( )分析方法。 A . 自左向右 B . 自顶向下 C . 自底向上 D . 自右向左 4.在通常的语法分析方法中,( )特别适用于表达式的分析。 A . 算符优先分析法 B . LR 分析法 C . 递归下降分析法 D . LL (1)分析法 5.经过编译所得到的目标程序是( )。 A . 四元式序列 B . 间接三元式序列 C . 二元式序列 D . 机器语言程序或汇编语言程序 6. 一个文法所描述的语言是( );描述一个语言的文法是( )。 A . 唯一的 B . 不唯一的 C . 可能唯一,也可能不唯一 得分 得分

相关文档 最新文档