编译原理期末考试

一、填空（每题2分，共20分）

1.从功能上说，程序语言的语句大体可分为（执行性）语句和（说明性）语句两大类。

2.扫描器的任务是从（源程序）中识别出一个个（单词符号）。

3.所谓最左派生是指（任何一步a都是对a中最左非终结符进行替换的）。

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

5.■•个上下文无关文法所含的四个组成部分是（一组终结符号，一组非终结符号、一个开始符

号、一组产生式）»

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

些子程序）。

7.LR分析法中的两种冲突是（移入一归约）和（归约一归约）。

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

9.属性定义中有两种性质的属性，分别是（继承属性）和（综合属性）。

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

11.所谓最仃推导是指：任何一步呻都是对a中最右非终结符进行替换的。

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

址。）

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

等等。

短语：一棵子树的所有叶I咱左至右排列起来形成一个相对于上树根的短而

直接短酒：仅有父子两代的一梃网，它的所仙I旧M起来所形成的符利

句柄：一个句型的分析树巾用左地F那棵只有父f两代的子树的所有叶子的自左至右排列.

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

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

一张嵌套层次显示表diaplay.假定现在进入的过程层次为i,则它的diaplay表含有i+1个单元，

自顶向下每个单元依次存放着现行层、直接外层....直至最外层（主程序，0层）等每层过程的

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

二、名词解释（每题3分，共15分）

1.编译器预处理：对于一个编译器，如果要处理的输入是对原编译器的输入的扩充，就把输入

中的扩充部分转换成原输入的形式，然后把其结果交给原编译器处理，也就是把扩展的部分

转换成标准形式，这就是编译器预处理

2.LL（K）文法——（P89）

3.歧义文法一一（p71）

二义性（或歧义性，ambiquity）的定义：

如果一个文法的句子存在两棵分析树，那么，该句f是二义性的.如果一个文法包含二义性的句

£则称这个文法是二义性的.否她该文法是无二义性的.

正则表达式一一(P47)：每个正则表达式定义一个正则集。若用RE表示E上的正则表达式，并

用L(RE)所表示的正则集，则RE的语法定义和相应正则集如下面所述，其中A和B表示正则表

达式，并且a表示字母表£中的任一符号。

WeRSiLC0)-Q⑵短阳L何■(祖

向■(a)

⑷⑶1RE,L(W)■W圜A|B《R&L蜃闻・L⑴

时&BeRE.L(A■B)-L用L®[7]A'3RB,

4.属性文法一一(P260)

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

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

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

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

2.生成语言L(G)fa-mcPa%"|p>=0,m>=l,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,SS写出句子((a,b),b)的规范规约过程及每一步

的句柄。

解：句型规约句柄

((a,b),b)

((S,b),b)S->aa

((T,b),b)T->SS

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

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

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

(T,b)T->SS

(T,S)S->bb

(T)T->T,ST,S

SS->(T)(T)

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

1.已知文法G(E)

E-T|E+T

T-F|T*F

F-(E)|i

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

解：1.(4分)

EnT=F=(E)n(E+T)=(E+F)

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

Zl\

Zl\

E+T

Zl\

T*F

2.(4分)

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

直接短语：T*F,i

句柄：T*F

素短语：T*F,i

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

SfMa|bMc|dc|bda

Mfd

解：SSfMa|bMc|dc|bdaMfd

S'f.S

S—.Ma

Sfb.Mc

Sf.bMc

S—>b.daS-bd.a

S—.dc

M-».dMfd.

S.bda

M->.d

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

等价的SLR(l)文法是

Sfda|bdc|dc|bda

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

1.下面的文法定义详"；L={a'ncm|m,nWl}。3个讲法制导定义，其语义规则的作用是：对

不属于语言L的子集L尸(anbncn|n>1}的句子，打印出错信息°

SfDCDfaDb|abC-»Cc|c

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

S->DCifD.lengthwC.lengththenprint("error”)

D->abD.length:=1

D—>aD)bD.length:=D|.length+1

C->cC.length:=1

C—>CicC.length:=Cj.length+1

2.给;II文法G(L)的翻译模式，它分别计湾，彳川；中0l-j1的个数，(要求ANTLR代码)

S^L.LlL

L—BL

L-e

B-0|1

GrammerLOI

@membcrs{intnO;intnl;}

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

j：<O>j{nO+=l;}

ri，j{nl+=l；}

I'a，

ws：C丁\门'\n'r\r')+{skip。;};

名词解释

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

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

简称DAGo

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

4.短语一一令G是一个文法。S划文法的开始符号，假定a66是文法G的一个句型，如果有$

aA6且AB,则称B是句型a0相对非终结符A的短语。

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

筒述题

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

2、已知文法G(S)

S-a|A|(T)

T-T,S|S

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

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

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

答

翦

1>逆波二表示：abc*+ab+/d—

三

■送r

L'•

①/*O

I

X，

②Z①

(

③Y+,

za,3

(

+,人

④xa.

z

(

⑤v-©④,@d)

z

(

\

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

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

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

应着重考虑的问题：(1)如何使生成的目标代码较短；(2)如何充分利用寄存器，以减少访问

内存次数；

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

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

解：文法G(N)：

N—AB|B

ATAQD

BT1|3|5|7|9

D->B|2|4|6|8

C—O|D(5分)

2、设文法G(S)：

S—>(L)]aS|a

L—L,S|S

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

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

(3)构造预测分析表。

解：(1)

S->(L)|aS,

S'TS|£

L—SL'

L'TSL'W

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

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

FIRST(S,)={,a,8}FOLLOW⑻)={#,,,)}

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

FIRST(L,)={,,£}FOLLOW(L')={)}

3、Whilea>0Vb<0do

Begin

X：=X+1；

ifa>0thena：=a_1

elseb：=b+l

End；

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

解：

a,0,5)

3)

(3)(jV,b,0,5)

(4)0,一，一，15)

(5)(+,x,1,Tl)

(6)(：=,Tl,x)

(7)(jN，a,0,9)

(8)(j,一，—12)

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

(10)(：=,T2,a)

(11)0,一，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)VE(2)

E->E(1)AE(2)

E—i

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

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

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

解：⑴EO—E(l)

E-E0E(2)

EA-E⑴

E—EAE(2)

E—i(3分)

⑵E-E⑴

{BACKPATCH(E(1)FC,NXQ)；

EOTC：=E(1)TC}

ETE0E(2)

{EFC：=E(2)FC；

ETC：=MERG(E0TC,E(2)TC)}

EA-E⑴

{BACKPATCH(E(1)TC,NXQ)；

EOFC：=E(1)FC)

E—EAEQ)

{ETC：=E(2)TC；

EFC：=MERG(EAFC,E(2)FC)

E—i

{ETC：=NXQ；EFC：=NXQ+1；

GEN(jn2,entry(i),一0)；

GEN(j,0)(3分)

6、设有基本块

Tl：=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分)

解：(l)DAG：

(2)优化后的四元式

T3：=S-R

T4：=S+R

A：=5*T4

B：=T3+T4(3分)

例题3

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

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

解析：本题考察的是程序的语言的组成句子与文法之间的关系；正规表达式r=(a13|0(0|1)*表

示的是a,b,c中的任意一个与0、1串的连接，由于0、1串的长度和组成是不固定的，所以整个

句子的数据就是不固定的，也就是说语言L(r)的组成元素是无穷的。

试题4：编译器和解释器是两种高级语言处理程序，与编译器相比，_B_o编译器对高级语言源

程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代

码生成等几个阶段：其中，代码优化和_仁并不是每种编译器都必需的。词法分析的作用是识别

源程序中的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-TdS|S

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

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

语；E是短语。

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

B：①S②b③⑴@Sd(T)

C：①S②b③⑴@Sd(T)

D：①S②S,⑴，b③S,(T),TdS,b④(SdCT)db)

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

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

S

(T)

(TdS)

(TdSb)

(S(T))

从语法树我们可以看出，短语就是位于同一个非终端结点的所有叶子结点，比如S、Sd(T)、

Sd(T)db就是是相对于T的短语，b、(T)、(Sd(T)db)是相对于S的短语。而直接短语则进一步要

求这些叶子结点的非终端结点是它们的直接父结点。因此可以S、(T)、b都是该句型的直接短语。

语法树上最左的直接短语就是句柄，本题中是S。

所谓素短语是指这样一个短语，它至少含有一个终结符，并且除它自身之外不再含任何更小

的素短语。最左素短语则指处于句型最左边的那个素短语。

最左推导是指任何一步推导过程。一B,都是对。中的最左非终结符进行替换。因此，在语

法树中也很容易看出，如果语法树中的只有最左的非终结符结点(包括各级结点)具有其子树，

则它就是最左推导。最右推导与之类似，最右推导也称规范推导。本题从语法推导树可以看出，

既不是最左推导也不是最右推导，就是一般的推导。

A：@B：①C：③D：②E：①

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

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

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

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

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

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

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

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

L-属性文法要求对于每个产生式A9X1X2…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是可用寄存器

答：

LDRO,B

MULRO,C

LDRI,E

ADDRI,F

ADDRO,RI

MULRO,2

STRO,H

二、设£={0,1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的

正规式，并构造一个识别该正规集的DFA。（8分）

答：

构造相应的正规式：（0|1）*1（0|1）（3分）

NFA:（2分）

三、（6分）写一个文法使其语言为L（G）={anbn,ambn|

答：文法G（S）:

S->aSb|B

BfbBa|ba

四、对于文法G（E）:（8分）

E->T|E+T

T->F|T*F

Ff（E）|i

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

2.写出上述句型的短语，直接短语、句柄和素短语。

答:1.（4分）

E=>T=>F=>(E)n(E+T)=(E+F)T

F

/1\

n(E+i)=>(T+i)n(T*F+i)

2.(4分)短语：CT*F+i),T*F+i,T*F,i直接短语：T*F,i

句柄：T*F素短语：T*F,i

五、设文法G(S)：(12分)

SfSiA|A

ATA+B|B

Bf)A*|(

1.构造各非终结符的FIRSTVT和LASTVT集合；

2.构造优先关系表和优先函数。(12分)

答：(6分)

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

FIRSTVT(A)={+,),(}

F1RSTVT(B)={),(}

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

LASTVT(A)={+,*,(}

LASTVT(B)={*,(}

优先关系表:(3分)

*

ii()

i><<<

+>><<>

(>>>

)<<<

*>>>

优先函数:（3分）

i+()*

f26616

g14661

六、设某语言的do-while语句的语法形式为（9分）

S->doS⑴WhileE

其语义解释为:

针对自下而上的语法分析器，按如下要求构造该语句的翻译模式:

（1）写出适合语法制导翻译的产生式；

（2）写出每个产生式对应的语义动作。

答：（1）.适合语法制导翻译的文法（3分）

G(S):

Rfdo

UfRS⑴While

SfUE

(2).(6分)

R—>do

{R,QUAD:=NXQ}

UfRS⑴While

{U・QUAD:=R.QUAD;

BACKPATCH(S.CHAINzNXQ)}

SfUE

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

S.CHAIN:=E.FC}

答案二：(1)SfdoMiS⑴WhileM2E

MfE(3分)

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

(1)

SfdoMiSWhileM2E

(

(1)

BACKPATCH(S.CHAIN,M2.QUAD);

BACKPATCH(E.TC,M^.QUAD);

S.CHAIN:=E.FC

)

七、(8分)将语句if(A〈X)八(B>0)thenwhileC>0doC:=C+D翻译成四元式。

答：100(jv,A,X,102)

101(j,-，，109)

1020>,B,0,104)

103(j,・，，109)

104(j>,C,0,106)

105(j,-，-，109)

106(+,c,D,Tl)

107(:=,Tl,・，C)

1080，-，-,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图；

⑵设A,B是出基本块后的活跃变量，请给出优化后的四元式序列。

(2)BfaB

(3)Bfb

00#abab#

103#abab#

2034#abab#

3038#aBab#

402#Bab#

5026#Bab#

60267#Bab#

70269#BaB#

8025#BB#

901#S#acc

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

BfSB|s

S->[eC]|.i

C—>eC|£

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

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

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

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

Predict(B->e)=(*)

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

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

Predict(C->eC)={e}

Predict(C->£)={]}

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

LL(1)分析表如下:

i*e[

->iB*e->£

A

->sB->SB

B

->[eC]->.i

S

->eC->8

C

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

S—LaR|R

LfbR|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⑶为：

STABIbCA->b|九

B—aD|XC—AD|b

D-aS|c

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

解：First(S)={b,a,X)

First(A)={b,X}

First(B)={a,X}

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

First(D)={a,c}

Follow(S)={#}

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

Follow(B)={#}

Follow(C)={#}

Follow(D)={#}

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

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

2.文法的产生式为：

<S>^a|b|(<R>)

<T>-*<S>c<T>|<S>

<R>-*<T>

1)构造句型(bc<S>c<T>)的推导树，并指出该句型的所有短语、简单短语、句柄。

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

a)((<S>c(b)))b)(<S>)c)(a)d)<S>c<T>e)<S>f)b

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

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

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

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

解答：1)句型(bc<S>c<T»的推导树如图2.1所示:

图2.1句型（bc〈S>c<T〉）的推导树

短语：b;bc<S>c<T>;<S>c<T>;（bc<S>c<T»

简单短语：b;<S>c<T>

句柄：b

2）a）句型（（。>£；（13）））的推导树如图2.2所示：

（中）

中

图2.2句型（«S>c（b）））的推导树

句柄为bo

b）句型（〈S>）的推导树如图2.3所示:

图2.3句型(<S>)的推导树

句柄为<S>.

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

半

T

T

T

.

图2.4句子(a)的推导树

句柄为a。

d)〈S>c〈T>不是文法G［〈S>］的句型，.•.句柄不存在。

e)<S>是开始符号，，句柄不存在。

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

T

b

图2.5句子b的推导树

句柄为b。

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

证明：考察文法G［<S>］：

<S>f<S>a

<S>—>b

BP<A>=<S>a=<S>ap=b,

考虑最左推导vS>='<S>a'n<S>aa'与最左推导<S>n'〈S>a'nba’,

法0表示i次直接推导，

iik-1

当i>k时FIRSTk(<S>aa)AFIRSTk(ba)=baH0,

刁不是LL(k)文法。

由于文法G［<S>］是有直接左递归产生式的文法，所以命题得证。

4.考察如下文法G［<S>］：

<S>-<A>a<B>

<S>一<B>b

<A>fa<D>

<A>一〈D>

<B>—d

<B>-e

〈BAe

<D>-f〈D>

<D>-g

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

解答：

a)G［<S>］各个产生式的选择集合为：

Select(<S>—><A>a<B>)=FIRST(<A>a<B>)={aXg}

Select(<S>—><B>b)=FIRST(<D>b)={d,e,b)

Select(<A>—>a<D>)=FIRST(a<B>)={a}

Select(<A>-^<D>)=FIRST(<D>)={f,g}

Select(<B>->d)=FIRST(<d>)={d}

Select(<B>—►e)=FIRST(<e>)={e}

Select(<B>->8)=FOLLOW(<B>)={b,l}

Select(<D>->f<D>)=FIRST(长D>)={f}

Select(<D>-^g)=FlRST(g)={g}

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

.,.GL<s>］是LL(1)文法。

5.试判定下述文法G［<S>］是否是LR(1)文法？为什么？

<S>-<AXA>

<A>f<A>a

<A>fa

解答：a)•••对文法G［<S>］存在的句子aaa,有二棵不同的推导树(图5.1)：

中I

<A>aa

・<A>■

...该文法是二义性文法,G[<S>]不是LR(1)文法。

(c)DS,A,B可导出空

2)first(S)={a,b},first(A)={a,X},first(B)={b,X}

follow(S)={#},follow(A)={a,b,#},follow(B)={a,b,#!

predict(S->ABBA)={a,b,#}

predict(A->a)={a},predict(A->入)={a,b,#}(*)

predict(B->b)={b},predict(B->入)={a,b,#}(**)

由(*)和(**)两行知，不是LL(D文法.

(d)1)没有非终极符可导出空

2)first(C)={c,d},first(B)={b,c,c},first(S)={a,b,c,d}

follow(S)={e,#},follow(B)={e,#},follow(C)={c,e,#}

predict(S->aSe)={a},predict(S->B)={b,c,d}

predict(B->bBe)={b},predict(B->C)={c,d}

predict(C->cCc)={c},predict(C->d)={d}

因为满足LL(1)文法的条件，所以是LL(1)文法.

4.13

First(E)=[-,(,id}Follow(E)={#J}

First(Etail)={-%)Follow(Etail)={4$,)}

First(Var)={id}Follow(Var)={-，#,)}

First(Vtail)={(,%}Follow(Vtail){-,#,)}

[1]predict(E-E)={-}

⑵predict(E-(E))={(}

⑶predict(E-VarEtail)={id)

predict(Etail--E)={-}

⑸predict(Etail-A)={#.)}

[6]predict(Vai-idVtail)={id}

[7]predict(Vtail-(E»={()

[8]predict(VtaiLA)={-,))

分析表:

-()id#

E123

Etail455

Var6

Vtail8788

2001年编译原理试题

1.（10分）处于/*和*/之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态

转换图。

2.（10分）为语言

L={a'V|0<m<2n）（即a的个数不超过b的个数的两倍）

写一个LR（1）文法，不准超过6个产生式。（若超过6个产生式，不给分。若所写文法不是LR

（1）文法，最多给5分。）

3.（10分）构造下面文法的LL（1）分析表。

D->TL

Tfint|real

LridR

R.,idR|£

4.(15分)就下面文法

S.(L)|aLfL,S|S

•给出一个语法制导定义，它输出配对括号的个数。

•给出一个翻译方案，它输出每个a的嵌套深度。

如句子(a,(a,a)),第一小题的输出是2,第二小题的输出是122。

9.(10分)如果在A机器上我们有C语言编译器C。，也有它的源码&(用C语言写成)。如

何利用它通过尽量少的工作来得到B机器的C语言编译器CCBo

10.(5分)表达式(标.(九yz.(x+y)+z)3)45和(Xx.(九yz.(x+y)+z)35)4有同样的结果。在抽象机

FAM上，哪一个表达式对应的目标代码的执行效率高？为什么？

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

1.

2.LR(1)文法LR(1)文法二义文法

S->AB|aABbSfABSfAASb|£

A->aaAb|8AfaaAb|ab|8A->a|8

B->Bb|8B—>Bb|£

3.intrealid,$

DD-»TLDfTL

TTfintT—>real

LLfidR

RR.—idRR—>£

4.SJSprint(S.num)

Sf(L)S.num:=L.num+1

SfaS.num:=0

LfLhSL.num:=L^num+S.num

LfSL.num:=S.num

S，->{S.depth:=0}S

S.{L.depth:=S.depth+1}(L)

Sfa{print(S.depth)}

Lt{Li.depth:=L.depth}L,,{S.depth:=L.depth}S

L->{S.depth:=L.depth}S

9.•修改源码5八的代码生成部分，让它产生B机器的代码，称结果程序为外。

・将品提交给C。进行编译，得到一个可执行程序。

•将区提交给上述可执行程序进行编译，得到所需的编译器Cg。

10.第一个表达式在执行大yz.(x+>')+z)3时出现参数个数不足的情况，因此有FUNVAL的值进

入栈顶，然后发现参数个数不足，又把它做成FANVAL的情况。而第二个表达式执行的是(心心。

+y)+z)35,不会出现参数个数不足的情况。因此第二个表达式的执行效率比第一个表达式的高。

2003年编译原理试题

1.（20分）写出字母表£={a,b}上语言L={卬|卬中a的个数是偶数}的正规式，并画出接受该

语言的最简DFAo

2.（15分）考虑下面的表达式文法，它包括数组访问、加和赋值：

EfE[E]|E+E|E=E|（E）|id

该文法是二义的。请写一个接受同样语言的LR（1）文法，其优先级从高到低依次是数组访问、加

和赋值，并且加运算是左结合，赋值是右结合。

3.（10分）下面是产生字母表£={0,1,2}上数字串的-—个文法：

SfDSD|2

D-0|1

写一个语法制导定义，它打印一个句子是否为回文数（一个数字串，从左向右读和从右向左读都

一样时，称它为回文数）。

4.（10分）教材上721节的翻译方案

PT{offset:=0)

D

DTD;D

。fid:7{,T.type,offset);offset:=offset+T.width}

Ttinteger{T.type:=integer;T.width:=4}

TTreal{T.type:=real;T.width:=8}

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

用变量。

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

1.语言L的出规弓是：，

（4b*a|b）或b9（ab*a/?*）*

接受该语言的最简DFA是：

2.EfT=E|T

TfT+F|F

FtF[E]|(E)|id

3.S-Sprint(S.val)

S—>D]S]D2S.val=(Di.val=D2.val)andSi.val

Sf2S.val=true

Df0D.val=0

D-»1D.val=1

4.文法符号。的属性协亮八是继承属性，代表在分析。前原来使用的变量奶外的大小；属性

叨是综合属性，代表在分析。后原来使用的变量加々的大小。P的属性奶e/是综合属性，

记录该过程所分配的空间。

P—>{D.offset\:=0}D{P,offset:=D.offset!}

D—>{D\.ojfset\:=D.offsetl\D\;

{D2.offset\:=D\.offset2}Di{D.ojfsetl:=D2.offset2}

£)-»id:T{enter(,T.type,D.offsetI);

D.offsetl:=D.offset\+T.width)

Ttinteger{T.type:=integer;T.width:=4}

TTreal{T.type:=real;T.width:=8}

1.(15分)

(a)字母表X={(,)}上的语言{(),(()()),((())),()()()()()}是不是正规语言？为什么？

(b)正规式(0|1)*和((£|0)「)*是否等价，说明理由。

2.(15分)接受文法

S^Aa|bAc|dc|bda

Afd

活前缀的DFA见下图。请根据这个DFA来构造该文法的SLR(l)分析表，并说明该文法为什么不

是SLR(l)文法。

3.(10分)现有字母表£=｛a｝,写一个和正规式a*等价的上下文无关文法，要求所写的文法既不

是LR文法，也不是二义文法。

4.(20分)

(a)下面的文法定义语言L=｛a'11/|m,n21｝。写一个语法制导定义，其语义规则的作用是：

对不属于语言L的子集L尸｛anbncn|n>1｝的句子，打印出错信息。

S—>DCD—>aDb|abCfCc|c

(b)语句的文法如下：

S—>id:=E|ifEthenS|whileEdoS|beginS;Send|break

写一个翻译方案，其语义动作的作用是：若发现break不是出现在循环语句中，及时报告错误。

2005年编译原理和技术试题参考答案

1.(a)语言｛(),(()()),((())),()()()()()｝是正规语言,因为该语言只包括有限个句子，它可

以用正规式定义如下：

()1(()())1((()))1()()()()()

(b)我们分析正规式(伯|0)1*)*表示的语言。可以看出正规式(£[0)1*描述的语言是集合｛£,1,

11,111,...,0,01,011,0111,它含长度