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

编译原理期末考试

编译原理期末考试
编译原理期末考试

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

1.从功能上说,程序语言的语句大体可分为(执行性)语句和(说明性)语句两大类。2.扫描器的任务是从(源程序)中识别出一个个(单词符号)。

3.所谓最左派生是指(任何一歩α→β都是对α中最左非终结符进行替换的)。

4.语法分析最常用的两类方法是(自顶向下)和(自底向上)分析法。

5.一个上下文无关文法所含的四个组成部分是(一组终结符号,一组非终结符号、一个开始符号、一组产生式)。

6.所谓语法制导翻译方法是(为每个产生式配上一个翻译子程序,并在语法分析的同时执行这些子程序)。

7.LR分析法中的两种冲突是(移入—归约)和(归约—归约)。

8.产生式是用于定义(语法范畴)的一种书写规则。

9.属性定义中有两种性质的属性,分别是(继承属性)和(综合属性)。

10.常用的两种动态存储分配方法是(栈式动态分配)和(堆式动态分配)。

11. 所谓最右推导是指:任何一步αβ都是对α中最右非终结符进行替换的。

12. 一个过程相应的DISPLAY表的内容为(现行活动记录地址和所有外层最新活动记录的地址。)

13. 符号表中的信息栏中登记了每个名字的有关的性质,如(类型、种属、所占单元大小、地址)等等。

14.运行时的DISPLAY表的内容是什么?它的作用是什么?

答:DISPLAY表是嵌套层次显示表。每当进入一个过程后,在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i,则它的diaplay表含有i+1个单元,自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层(主程序,0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。

二、名词解释(每题3分,共15分)

1.编译器预处理:对于一个编译器,如果要处理的输入是对原编译器的输入的扩充,就把输入中的扩充部分转换成原输入的形式,然后把其结果交给原编译器处理,也就是把扩展的部分转换成标准形式,这就是编译器预处理

2.LL(K)文法――(P89)

3.歧义文法――(p71)

正则表达式――(P47) :每个正则表达式定义一个正则集。若用RE表示∑上的正则表达式,并用L(RE)所表示的正则集,则RE的语法定义和相应正则集如下面所述,其中A和B表示正则表达式,并且а表示字母表∑中的任一符号。

4.属性文法――(P260)

三、简答题(每题5分,共15分)

1.设有L(G)={a2n+1b2m+1c2p | n>=1, m>=1, p>=1}

1)给出它的正则表达式。

2)构造识别该语言的DFA。

2.生成语言L(G)={a p b m c p a n b n | p>=0, m>=1, n>=2}的文法G是什么?它是chomsky的哪型文法。

解:G(3)文法为

S->AC

A->aAc|B

B->bB|b

C->aCb|ab

它是乔姆斯基2型文法

3.已知文法G(S):S→a|b|(T)T→T,S|S 写出句子((a,b),b)的规范规约过程及每一步的句柄。

解:句型规约句柄

((a,b),b)

((S,b),b)S->a a

((T,b),b) T->S S

((T,S),b) S->b b

((T),b) T->T,S T,S

(S,b) S->(T) (T)

(T,b) T->S S

(T,S) S->b b

(T) T->T,S T,S

S S->(T) (T)

四、计算题(每题10分,共20分)

1.已知文法G(E)

E→T|E+T

T→F|T*F

F→(E)|i

给出句型α=(T*F+i)的最右派生及画出语法树。

解:1. (4分)

E?T?F?(E) ?(E+T) ?(E+F)

?(E+i) ?(T+i) ?(T*F+i)

2. (4分

)

短语:(T*F+i), T*F+i, T*F, i

直接短语:T*F, i

句柄:T*F

素短语:T*F, i

2.说明下面的文法不是SLR(1)文法,并重写一个等价的SLR(1)文法。

S → M a | b M c | d c | b d a

M → d

解:S? → S S → M a | b M c | d c | b d a M → d

因为a是M的后继符号之一,因此在上面最右边一个项目集中有移进-归约冲突。

等价的SLR(1)文法是

S → d a | b d c | d c | b d a

五、设计题(每题15分,共30分)

1.下面的文法定义语言L = { a n b n c m | m, n ≥ 1}。写一个语法制导定义,其语义规则的作用是:对

不属于语言L的子集L1= { a n b n c n | n ≥ 1}的句子,打印出错信息。

S → D C D → a D b | a b C → C c | c

解:语法制导的定义如下:

S → D C if D.length ≠C.length then print (“error”)

D → a b D.length := 1

D → a D1 b D.length := D1.length + 1

C → c C.length := 1

C → C1 c C.length := C1.length + 1

2.给出文法G(L)的翻译模式,它分别计算字符串中0与1的个数。(要求ANTLR代码)

S→L.L| L

L→BL

L→ε

B→0|1

Grammer L01

@members {int n0; int n1;}

Start: {n0=0; n1=0;} j{system.out.println(n0);system.out.println(n1);}

;

j: …0?j{n0 +=1;}

|…1? j{n1 +=1;}

| …a?

;

ws:(…?| …\t?| …\n?| …\r?)+{skip();};

名词解释

1.遍--指编译程序对源程序或中间代码程序从头到尾扫描一次。

2.无环路有向图(DAG)--如果有向图中任一通路都不是环路,则称庐有向图为无环路有向图,简称DAG。

3.语法分析--按文法的产生式识别输入的符号串是否为一个句子的分析过程。

4.短语--令G是一个文法。S划文法的开始符号,假定αβδ是文法G的一个句型,如果有S αAδ且AB,则称β是句型αβ相对非终结符A的短语。

5.后缀式--一种把运算量写在前面,把算符写在后面的表示表达式的方法。

简述题

1、写出表达式(a+b*c)/(a+b)-d的逆波兰表示及三元式序列。

2、已知文法G(S)

S→a|∧|(T)

T→T,S|S

写出句子((a,a),a)的规范归约过程及每一步的句柄。

3、何谓优化?按所涉及的程序范围可分为哪几级优化?

4、目标代码有哪几种形式?生成目标代码时通常应考虑哪几个问题?

答案:1、逆波兰表示:abc*+ab+/d-

三元式序列:

①(*,b,c)

②(+,a,①)

③(+,a,b)

④(/,②,③)

⑤(-,④,d)

3、优化:对程序进行各种等价变换,使得从变换后的程序出发,能产生更有效的目标代码。

三种级别:局部优化、循环优化、全局优化。

4、目标代码通常采用三种形式:机器语言,汇编语言,待装配机器语言模块。

应着重考虑的问题:(1)如何使生成的目标代码较短;(2)如何充分利用寄存器,以减少访问内存次数;

(3)如何充分利用指仅系统的的特点。

计算题:1、写一个文法,使其语言是奇数集,且每个奇数不以0开头。(5分) 解:文法G(N):

N→AB|B

A→AC|D

B→1|3|5|7|9

D→B|2|4|6|8

C→0|D(5分)

2、设文法G(S):

S→(L)|a S|a

L→L,S|S

(1) 消除左递归和回溯;

(2) 计算每个非终结符的FIRST和FOLLOW;

(3) 构造预测分析表。

解:(1)

S→(L)|aS?

S?→S|ε

L→SL?

L?→SL?|ε

评分细则:消除左递归2分,提公共因子2分。

(2) FIRST)S)={(,a}FOLLOW(S)={#,,,)}

FIRST(S?)={,a,ε}FOLLOW(S?)={#,,,)}

FIRST(L)={(,a}FOLLOW(L)={ )}

FIRST(L?)={,,ε}FOLLOW(L?〕={ )}

3、While a>0 ∨b<0do

Begin

X:=X+1;

if a>0 then a:=a-1

else b:=b+1

End;

翻译成四元式序列。(7分)

解:

(1) (j>,a,0,5)

(2) (j,-,-,3)

(3) (j<,b,0,5)

(4) (j,-,-,15)

(5) (+,×,1,T1)

(6) (:=,T1,-,×)

(7) (j≥,a,0,9)

(8) (j,-,-,12)

(9) (-,a,1,T2)

(10) (:=,T2,-,a)

(11) (j,-,-,1)

(12) (+,b,1,T3)

(13) (:=,T3,-,b)

(14) (j,-,-,1)

(15)

评分细则:控制结构4分,其它3分。

4、已知文法G(E)

E→T|E+T

T→F|T * F

F→(E)|i

(1) 给出句型(T * F+i)的最右推导及画出语法树;

(2) 给出句型(T * F+i)的短语、素短语。(7分)

解:(1) 最右推导:

ETF(E)(E+T)(E+F)(E+i)

(T+i)(T*F+i)

(2) 短语:(T*F+i),T*F+i,T*F,i(2分)

素短语:T*F,i (1分)

5、设布尔表达式的文法为

E → E(1)∨E(2)

E → E(1)∧E(2)

E → i

假定它们将用于条件控制语句中,请

(1) 改写文法,使之适合进行语法制导翻译和实现回填;

(2) 写出改写后的短个产生式的语义动作。(6分)

解:(1) E0→E(1)

E→E0E(2)

EA→E(1)

E→EAE(2)

E→i(3分)

(2) E→E(1)

{BACKPA TCH(E(1)·FC,NXQ);

E0·TC:=E(1)·TC}

E→E0E(2)

{E·FC:=E(2)·FC;

E·TC:=MERG(E0·TC,E(2)·TC)}

EA→E(1)

{BACKPA TCH(E(1)·TC,NXQ);

E0·FC:=E(1)·FC}

E→EAE(2)

{E·TC:=E(2)·TC;

E·FC:=MERG(EA·FC,E(2)·FC}

E→i

{E·TC:=NXQ;E·FC:=NXQ+1;

GEN(jn2,entry(i),-0);

GEN(j,-,-,0)(3分) 6、设有基本块

T1:=2

T2:=10/T

T3:=S-R

T4:=S+R

A:=T2 * T4

B:A

T5:=S+R

T6:=T3 * T5

B:=T6

(1) 画出DAG图;

(2) 假设基本块出口时只有A,B还被引用,请写出优化后的四元序列。(6分)

解:(1)DAG:

(2) 优化后的四元式

T3:=S-R

T4:=S+R

A:=5*T4

B:=T3+T4(3分)

例题3

若正规表达式r=(a|b|c)(0|1)*,则L(r)中有__D__个元素。

(12)A.12 B.18 C.6 D.无穷

解析:本题考察的是程序的语言的组成句子与文法之间的关系;正规表达式r=(a|b|c)(0|1)*表示的是a,b,c中的任意一个与0、1串的连接,由于0、1串的长度和组成是不固定的,所以整个句子的数据就是不固定的,也就是说语言L(r)的组成元素是无穷的。

试题4:编译器和解释器是两种高级语言处理程序,与编译器相比, B 。编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等几个阶段:其中,代码优化和 C 并不是每种编译器都必需的。词法分析的作用是识别源程序中的 B ;语法分析中的预测分析法是 B 的一种语法分析方法;编译器在 C 阶段进行表达式的类型检查及类型转换。

(13) A、解释器不参与运行控制,程序执行的速度慢

B、解释器参与运行控制,程序执行的速度慢

C、解释器参与运行控制,程序执行的速度快

D、解释器不参与运行控制,程序执行的速度快

(14) A、词法分析 B、语法分析 C、中间代码生成 D、语义分析

(15) A、字符串 B、单词 C、标识符 D、语句

(16) A、自左至右 B、自顶向下 C、自底向上 D、自右至左

(17) A、词法分析 B、语法分析 C、语义分析 D、目标代码生成

例题5:假设某程序语言的文法如下:

S→a | b | (T)

T→TdS | S

其中,V T={a,b,d,(,)},V N={S,T},S是开始符号。

考查该文法,称句型(Sd(T)db)是S的一个A。其中B是句柄;C是素短语;D是该句型的直接短语;E是短语。

A:①最左推导②最右推导③规范推导④推导

B:①S ②b ③(T) ④Sd(T)

C:①S ②b ③(T) ④Sd(T)

D:①S ②S,(T),b ③S,(T),TdS,b ④(Sd(T)db)

E:①(Sd(T)db) ②d(T) ③Td ④Sd(T)d

此句型的语法树如下所示:

S

(T)

(T d S)

(T d S b)

(S (T))

从语法树我们可以看出,短语就是位于同一个非终端结点的所有叶子结点,比如S、Sd(T)、Sd(T)db就是是相对于T的短语,b、(T)、(Sd(T)db)是相对于S的短语。而直接短语则进一步要求这些叶子结点的非终端结点是它们的直接父结点。因此可以S、(T)、b都是该句型的直接短语。语法树上最左的直接短语就是句柄,本题中是S。

所谓素短语是指这样一个短语,它至少含有一个终结符,并且除它自身之外不再含任何更小的素短语。最左素短语则指处于句型最左边的那个素短语。

最左推导是指任何一步推导过程ζ→β,都是对ζ中的最左非终结符进行替换。因此,在语法树中也很容易看出,如果语法树中的只有最左的非终结符结点(包括各级结点)具有其子树,则它就是最左推导。最右推导与之类似,最右推导也称规范推导。本题从语法推导树可以看出,既不是最左推导也不是最右推导,就是一般的推导。

A:④ B:① C:③ D:② E:①

1、算符优先关系表不一定存在对应的优先函数。正确

2、数组元素的地址计算与数组的存储方式有关。正确

3、仅考虑一个基本块,不能确定一个赋值是否真是无用的。正确

4、每个文法都能改写为LL(1)文法。不正确

5、对于数据空间的存贮分配,FORTRAN采用动态贮存分配策略。不正确

一、回答下列问题:(30分)

1.什么是S-属性文法?什么是L-属性文法?它们之间有什么关系?

解答:S-属性文法是只含有综合属性的属性文法。(2分)

L-属性文法要求对于每个产生式A X1X2…Xn,其每个语义规则中的每个属性或者是综合属性,或者是Xj的一个继承属性,且该属性仅依赖于:

(1)产生式Xj的左边符号X1,X2…Xj-1的属性;

(2)A的继承属性。(2分)

S-属性文法是L-属性文法的特例。(2分)

2.什么是句柄?什么是素短语?

一个句型的最左直接短语称为该句型的句柄。(3分)素短语是这样的一个短语,它至少包含一个终结符并且不包含更小的素短语。(3分)

3.划分程序的基本块时,确定基本块的入口语句的条件是什么?

解答:(1)程序第一个语句,或

(2)能由条件转移语句或无条件转移语句转移到的语句,或

(3)紧跟在条件转移语句后面的语句。

4.(6分)运行时的DISPLAY表的内容是什么?它的作用是什么?

答:DISPLAY表是嵌套层次显示表。每当进入一个过程后,在建立它的活动记录区的同时建立

一张嵌套层次显示表diaplay.假定现在进入的过程层次为i,则它的diaplay表含有i+1个单元,自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层(主程序,0层)等每层

过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。

5.(6分)对下列四元式序列生成目标代码:

A:=B*C

D:=E+F

G:=A+D H:=G*2

其中,H 是基本块出口的活跃变量, R0和R1是可用寄存器 答:

LD R0, B MUL R0, C LD R1, E ADD R1, F ADD R0, R1 MUL R0, 2 ST R0, H

二、设∑={0,1}上的正规集S 由倒数第二个字符为1的所有字符串组成,请给出该字集对应的正规式,并构造一个识别该正规集的D FA 。(8分)

答:

构造相应的正规式:(0|1)*1(0|1) (3分) NFA: (2分)

三、(6分)写一个文法使其语言为L(G)={ a n b m a m b n | m,n ≥1}。

答:文法G(S):

S → aSb | B B → bBa | ba 四、对于文法G(E): (8分)

E →T|E+T T →F|T*

F F →(E)|i

1. 写出句型(T*F+i)的最右推导并画出语法树。

2. 写出上述句型的短语,直接短语、句柄和素短语。 答:1. (4分)

E ?T ?

F ?(E) ?(E+T) ?(E+F)

?(E+i) ?(T+i) ?(T*F+i)

2. (4分)短语:(T*F+i), T*F+i, T*F, i 直接短语:T*F, i 句柄:T*F 素短语:T*F, i 五、设文法G(S):(12分)

(

|*)B B

|B A A A |SiA S A →+→→

1. 构造各非终结符的FIRSTVT 和LASTVT 集合; 2. 构造优先关系表和优先函数。(12分) 答:(6分)

FIRSTVT(S)={ i ,+,),( } FIRSTVT(A)={ +,),( } FIRSTVT(B)={ ),( }

LASTVT(S)={ i ,+,*,( } LASTVT(A)={ +,*,( } LASTVT(B)={ *,( }

六、设某语言的do-while 语句的语法形式为 (9分) S → do S (1) While E

其语义解释为:

针对自下而上的语法分析器,按如下要求构造该语句的翻译模式: (1) 写出适合语法制导翻译的产生式; (2) 写出每个产生式对应的语义动作。 答:(1). 适合语法制导翻译的文法(3分)

真 假

G(S):

R→ do

U→R S(1) While

S→U E

(2). (6分)

R→ do

{ R.QUAD:=NXQ }

U→R S(1) While

{ U.QUAD:=R.QUAD;

BACKPATCH(S.CHAIN, NXQ) }

S→U E

{ BACKPATCH(E.TC, U.QUAD);

S.CHAIN:=E.FC }

答案二:(1) S → do M1 S(1) While M2 E

M →ε (3分)

(2) M →ε { M.QUAD := NXQ } (6分)

S → do M1 S(1) While M2 E

{

BACKPATCH(S(1).CHAIN, M2.QUAD);

BACKPATCH(E.TC, M1.QUAD);

S.CHAIN:=E. FC

}

七、(8分)将语句if (A0) then while C>0 do C:=C+D翻译成四元式。答:100 (j<,A,X,102)

101 (j,-,-,109)

102 (j>,B,0,104)

103 (j,-,-,109)

104 (j>,C,0,106)

105 (j,-,-,109)

106 (+,C,D,T1)

107 (:=,T1,-,C)

108 (j,-,-,104)

109

八、(10分) 设有基本块如下:

T1:=S+R

T2:= 3

T3:= 12/T2

T4:=S/R A:=T1-T4 T5:=S+R B:=T5

T6:=T5*T3 B:=T6

(1)画出DAG 图;

(2)设A,B

答:(1) DAG 如右图:(6

(2) 四元式序列:(4分)

T1:=S+R T4:=S/R A:=T1-T4

B:=T1*4 九、(9分) 设已构造出文法(1) S → BB

(2) B → aB (3) B → b

假定输入串为abab ,请给出LR 分析过程(即按照步骤给出状态,符号,输入串的变化过程)。 答:步骤 状态 符号 输入串 0 0 # abab# 1 03 #a bab# 2 034 #ab ab# 3 038 #aB ab# 4 02 #B ab# 5

026

#Ba

b#

6 026

7 #Bab #

7 0269 #BaB #

8 025 #BB #

9 01 #S # acc

二、(10分)设有文法G[A]: A → iB*e

B → SB|ε

S → [eC]|.i

C → eC|ε

判定该文法是否为LL(1)文法?若是则给出它的LL(1)分析表,否则说明理由。

解:先计算各个产生式的Predict集:

Predict (A-> iB*e)={ i };

Predict (B-> SB) ={ [ , .}

Predict (B->ε ) ={ * }

Predict (S->[eC]) ={ [ }

Predict (S->. i) ={ . }

Predict (C-> eC) ={ e }

Predict (C->ε ) ={ ] }

因为Predict集没有冲突,所以是LL(1)文法。

LL(1)分析表如下:

三、(15分)设有文法G[S]:

S → LaR|R

L → bR|c

R → L

判断该文法是否为LR(1)文法。若是则给出它的LR(1)状态机以及LR分析表。

5.已知文法G[S]:

S → S;G│G

G → G(T)│ H

H → a │ (S)

T → T+S │ S

找出句型:a(T+S);H;(S)的短语、简单短语和句柄。

解:短语共有7个:a(T + S) ; H ; (S)

a(T + S) ; H

a(T + S)

T + S

(S)

H

a

简单短语4个:a , T + S , H , (S)

句柄:a。

6.已知文法G[S]为:

S→AB | bC A→b | λ

B→aD | λ C→AD | b

D→aS | c

对其每一个非终级符求First集和Follow集。

解:First (S) = { b , a , λ }

First (A) = { b , λ }

First (B) = { a , λ }

First (C) = { b , a , c }

First (D) = { a , c }

Follow (S) = { # }

Follow (A) = { a , c , #}

Follow (B) = { # }

Follow (C) = { # }

Follow (D) = { # }

1.编译程序在逻辑上由哪几部分组成?

答:六个阶段: 词法分析,语法分析,语义分析,中间代码生成,中间代码优化和目标代码生成。

2. 文法G[]的产生式为:

→a|b|()

c|

1)构造句型(bcc)的推导树,并指出该句型的所有短语、简单短语、句柄。

2)若句柄存在,求下述符号串的句柄。

a)((c(b))) b)() c)(a) d)c e) f)b

分析:符号串的某一部分符号要成为句柄,必须满足:

a)该符号串必须是该文法的句型(句子)。

b)是最左简单短语,所以文法的开始符号不是句柄。

因此只要给出句型(句子)对应的推导树就容易求出短语、简单短语和句柄。

解答:1)句型(bcc)的推导树如图2.1所示:

图2.1 句型(bcc)的推导树短语:b;bcc;c;(bcc)

简单短语:b;c

句柄:b

2) a)句型((c(b)))的推导树如图2.2所示:

图2.2 句型((c(b)))的推导树∴句柄为b。

b) 句型()的推导树如图2.3所示:

图2.3 句型()的推导树

∴句柄为

c) 句子(a)的推导树如图2.4所示:

图2.4 句子(a)的推导树

∴句柄为a。

d)c不是文法G[]的句型,∴句柄不存在。

e)是开始符号,∴句柄不存在。

f)句子b的推导树如图2.5所示:

图2.5 句子b的推导树

∴句柄为b。

3. 试证具有直接左递归产生式的文法不是LL(k)文法。

证明:考察文法G[]:

a

→b

= α=a β=b,

考虑最左推导?ia i ?aa i与最左推导?ia i ?ba i,i≥0表示i次直接推导,

当i≥k时FIRST k(aa i)∩FIRST k(ba i)=ba k-1 ≠?,

∴G[]不是LL(k)文法。

由于文法G[]是有直接左递归产生式的文法,所以命题得证。

4. 考察如下文法G[]:

a

b

→a

→d

→e

→ε

→f

→g

a) 试证文法G是LL(1)文法。

解答:

a)G[]各个产生式的选择集合为:

Select(a)=FIRST(a)={a,f,g}

Select(b)=FIRST(b)={d,e,b}

Select(→a)=FIRST(a)={a}

Select()=FIRST()={f,g}

Select(→d)=FIRST()={d}

Select(→e)=FIRST()={e}

Select(→ε)=FOLLOW()={b, }

Select(→f)= FIRST(f)={f}

Select(→g)= FIRST(g)={g}

显然,具有相同左部的产生式的选择集合不相交

∴G[]是LL(1)文法。

5.试判定下述文法G[]是否是LR(1)文法?为什么?

a

→a

解答:a)∵对文法G[]存在的句子aaa,有二棵不同的推导树(图5.1):

∴该文法是二义性文法,G[]不是LR(1)文法。

4.13

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。 9.(10分)如果在A 机器上我们有C 语言编译器CC A ,也有它的源码S A (用C 语言写成)。如何利用它通过尽量少的工作来得到B 机器的C 语言编译器CC B 。 10.(5分)表达式(λx .(λyz .(x + y ) + z ) 3) 4 5和(λx .(λyz .(x + y ) + z ) 3 5) 4有同样的结果。在抽象机FAM 上,哪一个表达式对应的目标代码的执行效率高?为什么?

2001年编译原理试题参考答案

1.

2.LR (1)文法 LR (1)文法 二义文法 S → AB | aABb S → AB S → AASb | ε A → aaAb | ε A → aaAb | ab | ε A → a | ε B → Bb | ε B → Bb | ε

3. int real id , $ D D →TL D →TL T T →int T →real L L →id R R R →, id R R → ε

4. S ' → S print(S.num) S → (L) S.num := L.num +1 S → a S.num := 0 L → L 1,S L.num := L 1.num + S.num L → S L.num := S.num S ' → {S.depth := 0} S S → {L.depth := S.depth +1} (L) S → a {print(S.depth)} L → {L 1.depth := L.depth} L 1, {S.depth := L.depth} S L → { S.depth := L.depth} S

9. ? 修改源码S A 的代码生成部分,让它产生B 机器的代码,称结果程序为S B 。 ? 将S B 提交给CC A 进行编译,得到一个可执行程序。 ? 将S B 提交给上述可执行程序进行编译,得到所需的编译器CC B 。

10.第一个表达式在执行λyz .(x + y ) + z ) 3时出现参数个数不足的情况,因此有FUNV AL 的值进入栈顶,然后发现参数个数不足,又把它做成FANV AL 的情况。而第二个表达式执行的是(λyz .(x + y ) + z ) 3 5,不会出现参数个数不足的情况。因此第二个表达式的执行效率比第一个表达式的高。

2003年编译原理试题

*

1.(20分)写出字母表∑ = {a, b}上语言L = {w | w 中a 的个数是偶数}的正规式,并画出接受该语言的最简DFA 。 2.(15分)考虑下面的表达式文法,它包括数组访问、加和赋值: E → E[E] | E + E | E = E | (E) | id

该文法是二义的。请写一个接受同样语言的LR(1)文法,其优先级从高到低依次是数组访问、加和赋值,并且加运算是左结合,赋值是右结合。 3.(10分)下面是产生字母表∑ = { 0, 1, 2}上数字串的一个文法: S → D S D | 2 D → 0 | 1

写一个语法制导定义,它打印一个句子是否为回文数(一个数字串,从左向右读和从右向左读都一样时,称它为回文数)。 4.(10分)教材上7.2.1节的翻译方案

P → {offset := 0}

D

D → D ; D D → id : T { enter (id .name , T .type , offset ); offset := offset + T .width } T → integer {T .type := integer ; T .width := 4 } T → real {T .type := real ; T .width := 8 }

使用了变量offset 。请重写该翻译方案,它完成同样的事情,但只使用文法符号的属性,而不使用变量。

2003年编译原理试题参考答案

1.语言L 的正规式是: (a b *a | b )* 或 b *(a b *a b *)* 接受该语言的最简DFA 是:

2. E → T = E | T T → T + F | F F → F[E] | (E) | id

3.

S ' → S print(S.val)

S → D 1 S 1 D 2 S.val = (D 1.val = D 2.val) and S 1.val S → 2 S.val = true

D → 0 D.val = 0 D → 1

D.val = 1

4.文法符号D 的属性offset 1是继承属性,代表在分析D 前原来使用的变量offset 的大小;属性offset 2是综合属性,代表在分析D 后原来使用的变量offset 的大小。P 的属性offset 是综合属性,记录该过程所分配的空间。 P → {D .offset 1 := 0} D {P .offset := D .offset 2 }

D → {D 1.offset 1 := D .offset 1 }D 1 ;

{D 2.offset 1 := D 1.offset 2 }D 2 {D .offset 2 := D 2.offset 2 }

b

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

一、填空题|(每题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:产生式集合(有限)。

《编译原理》考试题

《编译原理》考试题 一、选择题:(每题2分,共20分) 1.文法G所描述的语言是的集合。 A)文法G的字汇表V中所有符号组成的符号串 B)文法G的字汇表V的闭包V*中的所有符号串 C)由文法的识别符号推出的所有符号串 D)由文法的识别符号推出的所有终结符号串 2.设有文法G[S]=({b},{S,B},S,{S→b|bB,B→bS}),试问该文法所描述的语言是。 A)L(G[S])={b i|i≥0} B)L(G[S])={b2i|i≥0} C)L(G[S])={b2i+1|i≥0} D)L(G[S])={b2i+1|i≥1} 3.一个句型中的最左称为该句型的句柄。 A)短语B)简单短语 C)素短语D)终结符号 4. 正则文法能产生下面的语言:L={a n b n|n≥1}。 A)存在一个B)存在多个 C)不存在D)无法判断 5.编译程序中的语法分析器接受以为单位的输入,并产生有关信息供以后各阶段使用。 A)表达式B)产生式 C)单词D)语句 6.编译方法中,自顶向下的语法分析方法有。 A)简单优先分析方法B)算符优先分析方法 C)SLR方法D)LL(1)分析方法 7.简单优先分析法每次都是对进行归约。 A)最左短语B)简单短语C)句柄D)最左素短语 8.LR语法分析栈中存放的状态是识别的DFA状态。 A)前缀B)可归前缀 C)项目D)句柄 9.表达式-(a+b)/(c-d)-(a+b*c)的逆波兰表示是(@代表单目运算-)。 A)ab+cd-/@bc*a+- B)ab+/cd@bc*a+-- C)ab+@cd-/abc*+- D)ab+cd-/abc*+@- 10.乔姆斯基(Chomsky)把文法分成四种类型,即0型、1型、2型和3型。其中,3型文法是。 A)上下文无关文法B)上下文有关文法 C)正则文法D)短语文法 二、填空题:(每空1分,共20分) 1.假设G是一个文法,S是文法的开始符号,如果S *x,则称x是。 2.已知文法G[E]:E→E+T|T,T→T*F|F,F→(E)|i;该文法的开始符号是,终结符号集合V T是,非终结符号集合V N 是,句型T+T*F+i的短语有T+T*F+i,第一个T,T*F和。 3.确定的有限自动机DFA是一个,通常表示为。 4.LL(1)分析法中,第一个L的含义是,第二个L的含义是,“1”的含义是。 5.自底向上语法分析方法的基本思想是:从待输入的符号串开始,利用文法的规则步步向上进行,试图到文法的。 6.在编译程序中安排中间代码生成的目的是和。 7.文法符号的属性有两种,一种称为,另一种称为。 8.一个程序是正确的,包含两层含义:一是;二是。 9.文法G产生的全体是该文法描述的语言。 三、判断题:(每题2分,共20分) 1.符号就是字符。 2.移进—归约法是一种语法分析方法。 3.每一个NFA都对应有唯一的一个最小化的DFA。

编译原理期末考试卷

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

《编译原理》模拟期末试题汇总 6套,含答案

《编译原理》模拟试题一 一、是非题(请在括号内,正确的划√,错误的划×)(每个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.简单优先文法允许任意两个产生式具有相同右部。 (×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾,多划按错论)(每个4分,共40分) 1.一个编译程序中,不仅包含词法分析,_____,中间代码生成,代码优化,目标代码生成等五个部分。 A.( ) 语法分析B.( )文法分析C.( )语言分析D.( )解释分析 2.词法分析器用于识别_____。 A.( ) 字符串B.( )语句 C.( )单词 D.( )标识符 3.语法分析器则可以发现源程序中的_____。 A.( ) 语义错误 B.( ) 语法和语义错误 C.( ) 错误并校正D.( ) 语法错误 4.下面关于解释程序的描述正确的是_____。

(1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A.( ) (1)(2) B.( ) (1)C.( ) (1)(2)(3) D.( ) (2)(3) 5.解释程序处理语言时 , 大多数采用的是_____方法。 A.( ) 源程序命令被逐个直接解释执行 B.( ) 先将源程序转化为中间代码 , 再解释执行 C.( ) 先将源程序解释转化为目标程序 , 再执行 D.( ) 以上方法都可以 6.编译过程中 , 语法分析器的任务就是_____。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A.( ) (2)(3) B.( ) (2)(3)(4) C.( ) (1)(2)(3) D.( ) (1)(2)(3)(4) 7.编译程序是一种_____。 A. ( ) 汇编程序B.( ) 翻译程序 C.( ) 解释程序 D.( ) 目标程序 8.文法 G 所描述的语言是_____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B.( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C.( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 9.文法分为四种类型,即0型、1型、2型、3型。其中3型文法是_____。 A. ( ) 短语文法 B.( ) 正则文法 C.( ) 上下文有关文法 D.( ) 上下文无关文法 10.一个上下文无关文法 G 包括四个组成部分,它们是:一组非终结符号,一组终结符号,一个开始符号,以及一组 _____。 A.( ) 句子B.( ) 句型 C.( ) 单词 D.( ) 产生式 三、填空题(每空1分,共10分)

编译原理试题(卷)汇总-编译原理期末试题(卷)(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 . 该句子有两棵不同的语法树

编译原理试题

中间语言与语法制导翻译重点与难点 重点:语法制导翻译的基本思想,属性文法,翻译模式,说明语句的翻译方案。 三地址码,各种语句的目标代码结构、属性文法与翻译模式。 难点:属性的意义,对综合属性,继承属性,固有属性的理解,属性计算,怎么通过属性来表达翻译。布尔 表达式的翻译,对各种语句的目标代码结构、属性文法与翻译模式的理解。 基本要求 掌握语法制导翻译的基本思想,属性文法,综合属性,继承属性,固有属性,属性计算,s_属性文法, L_属性文法,说明语句的翻译方案,翻译模式、属性文法的实现 掌握中间语言与语义分析的基本概念;熟练掌握语法(结构)树、三地址代码、赋值与控制语句的翻译、 说明语句的翻译;掌握组合数据说明的翻译、过程调用翻译。 例题解析 例1 给定文法E --> T { R.i := T.p } R { E.p := R.s } R --> addop T { R1.i := mknode( addop.val, R.i, T.p ) } R { R.s := R1.s } R --> : { R.s := R1.s } T --> ( E ) { T.p := E.p } T --> id { T.p := mkleaf( id, id.entry) } T --> num { T.p := mkleaf( n um, n um.val ) } (1) 指岀文法中的各非终结符具有哪些综合属性和哪些继承属性 ⑵ 画岀按本翻译模式处理表达式 a + 20 + ( b - 10 ) 时所生成的语法树 【解】 (1)E的综合属性p,R的继承属性i,综合属性s ; T的综合属性p ⑵处理表达式a + 20 + ( b - 10 ) 时所生成的语法树如下 例2定义一个计算器的属性文法,完成一个输入表达式值的计算和显示 【解】计算器的文法 L T E E T E1 + T | T T T T1 * F | F F T ( E ) | digit

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

《编译原理》期末考试复习题 一、是非题(请在括号内,正确的划√,错误的划×)(每个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.规范句型:

编译原理考试试题1

编译原理 一、(5×6分)回答下列问题: 1.什么是S-属性文法?什么是L-属性文法?它们之间有什么关系? 2.什么是句柄?什么是素短语? 3.划分程序的基本块时,确定基本块的入口语句的条件是什么? 4.运行时的DISPLAY 表的内容是什么?它的作用是什么? 5.对下列四元式序列生成目标代码: A:=B*C D:=E+F G:=A+D H:=G*2 其中,H 是基本块出口的活跃变量, R0和R1是可用寄存器 二、(8分)设∑={0,1}上的正规集S 由倒数第二个字符为1的所有字符串组成,请给出该字集对应的正规式,并构造一个识别该正规集的DFA 。 三、(6分)写一个文法使其语言为L(G)={ a n b m a m b n | m,n ≥1}。 四、(8分)对于文法G(E): E →T|E+T T →F|T* F F →(E)|i 1. 写出句型(T*F+i)的最右推导并画出语法树。 2. 写出上述句型的短语,直接短语、句柄和素短语。 五、(12分)设文法G(S): ( |*)B B |B A A A |SiA S A →+→→ 1.构造各非终结符的FIRSTVT 和LASTVT 集合; 2.构造优先关系表和优先函数。 六、(9分)设某语言的do-while 语句的语法形式为 S → do S (1) While E 其语义解释为: 真 假 S (1)的代码 E 的代码

针对自下而上的语法分析器,按如下要求构造该语句的翻译模式: (1) 写出适合语法制导翻译的产生式; (2) 写出每个产生式对应的语义动作。 七、(8分)将语句if (A0) then while C>0 do C:=C+D; 翻译成四元式。 八、(10分) 设有基本块如下: T1:=S+R T2:= 3 T3:= 12/T2 T4:=S/R A:=T1-T4 T5:=S+R B:=T5 T6:=T5*T3 B:=T6 (1)画出DAG图; (2)设A,B是出基本块后的活跃变量,请给出优化后的四元式序列。 九、(9分) 设已构造出文法G(S): (1) S → BB (2) B → aB (3) B→ b 的LR分析表如下 ACTION GOTO 状态 a b # S B 0 s3 s4 1 2 1 acc 2 s6 s7 5 3 s3 s 4 8 4 r3 r3 5 r1 6 s6 s 7 9 7 r3 8 r2 r2 9 r2 假定输入串为abab,请给出LR分析过程(即按照步骤给出状态,符号,输入串的变化过程)。

编译原理期末试题及答案

2、写出表达式a+b*(c-d)/e的逆波兰式和三元序列。 3、写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。 4、已知文法G(S)及相应翻译方案 S→aAb {print “1”} S→a {print “2”} A→AS {print “3”} A→c {print “4”} 输入acab, 输出是什么 5、已知文法G(S) S→bAa A→(B | a B→Aa) 写出句子b(aa)b的规范归约过程。 6、已知文法G[S] S→S*aF | aF | *aF F→+aF | +a 消除文法左递归。 1、设文法G(S): S→^ | a | (T) T→T,S | S ⑴消除左递归; ⑵构造相应的FIRST和FOLLOW集合; ⑶构造预测分析表 2.语句if E then S (1) 改写文法,使之适合语法制导翻译; (2) 写出改写后产生式的语义动作。 4.设某语言的for语句的形式为 for i:=E(1) to E(2) do S 其语义解释为 i:=E(1) LIMIT:=E(2) again: if i<=LIMIT then Begin S; i:=i+1 goto again End; (1)写出适合语法制导翻译的产生式; (2)写出每个产生式对应的语义动作。 7.已知文法G(S) S→a | ^ | (T) T→T,S | S (1) 给出句子(a,(a,a))的最左推导; (2) 给出句型((T,S),a)的短语, 直接短语,句柄。 8.对于C 语言do S while E语句 (1)改写文法,使之适合语法制导翻译;

(2)写出改写后产生式的语义动作。 9.已知文法G(S) S→aAcBe A→Ab| b B→d (1)给出句子abbcde的最左推导及画出语法树; (2)给出句型aAbcde的短语、素短语。 10.设文法G(S): S→(T) | aS | a T→T,S | S ⑴消除左递归和提公共左因子; ⑵构造相应的FIRST和FOLLOW集合; ⑶构造预测分析表。 12.已知文法G(S) E→E+T | T T→T*F| F F→(E)| i (1) 给出句型(i+i)*i+i的最左推导及画出语法树; (2) 给出句型(E+T)*i+F 的短语,素短语和最左素短语。 答案: (1)消除左递,文法变为G’[S]: S→^ | a | (T)' T→ST’ | S T’→,ST’ |ε 此文法无左公共左因子。 (2)构造相应的FIRST和FOLLOW集合: FIRST(S)={a, ^, (},FOLLOW(S)={#, ,, )} FIRST(T)={a, ^, (} ,FOLLOW(T)={}} FIRST(T’)={,, ε} ,FOLLOW(F)={)} (3) C→if E then S→CS(1) (2) C→if E then {BACK, NXQ); :=} S→CS(1) {:=MERG, S(1). Chain)} 4. (1) F→for i:=E(1) to E(2) do S→FS(1) (2)F→for i:=E(1) to E(2) do {GEN(:=, E(1).place, _, entry(i)); :=entry(i);

(完整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]:

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

一、填空题(每空 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.标识符的行号

相关文档 最新文档