编译原理课后题

(a,(L)二>(a,(L,S))

2・1考虑文法G[S],其产生式如卜.:

n(a,(S,S))n(a,(a,S))=(a,(a,a))

③(a,((a,a),(a,a)))

S->(L)|aL—L,

S—^(L)^^(L,S)—^(S,S)—^(a,S)

S|S

(a,(L))n(a,(L,S))

⑴试指出此文法的终结符号、非终结符号。0(a,(S,S))=(a,((L),S))=

⑵给出下列各句子的分析树：(a,((L,S),S))=>(a,((S,S),S))

①(a,a)

n(a,((a,S),S))=^>(a,((a,a),S))=

②(a,(a,a))

(a,((a,a),(L)))

③(a,((a,a),(a,a)))

二>(a,((a,a),(L,S)))=>(a,((a,a),(S,S)))

⑶构造下列各句子的一个最左推导：n(a,((a,a),(a,S)))

①(a,a)

n(a,((a,a),(a,a)))

②(a,(a,a))

(d)①(a,a)

③(a,((a,a),(a,a)))

Sn(L)=>(L,S)=>(L,a)n(S,a)=

(4)构造下列各句子的一个最右推导：

(a,a)

①(a,a)

②(a,(a,a))

②(a,(a,a))

sn(L)n(L,S)=>(L,(L))=(L,(L,S))

③(a,((a,a),(a,a)))

n(L,(L,a))

(5)这个文法生成的语言是什么？(L,(S,a))n(L,(a,a))=^(S,(a,a))

(a)终结符号为：{(,),%,,}=>(a,(a,a))

非终结符号为：{S,L}

③(a,((a»a),(a,a)))

开始符号为：SS^^(L)^^(L,S)-^(L,(L))—^(L,(L,S))

(b)①(a,a)②(a,(a,a))

n(L,(L,(L)))

sSs(L,(L,(L,S)))—(L,(L,(L,a)))

(L,(L,(S,a)))

0(L,(L,(a,a)))(L,(S,(a,a)))

(L,((L),(a,a)))

=(L,((L,S),(a,a)))二>(L,((L,a),(a,a)))

=XL,((S,a),(a,a)))

=(L,((a,a),(a,a)))=(S,((a,a),(a,a)))

an(a,((a,a),(a,a)))

(e)L(G[S])=(al,a2,....an)s£a

其中ai(l<i<n),即L(G[S])是一个以a为

原子的纯表，但不包括空表。

2・2考虑文法G[S]

a«->aSbS|S->aSbS|bSaS|£

③(a,((a,a),(a,a)))

⑴试说明此文法是二义性的。可以从对于句

(c)①(a,a)a

子abab有两个不同的最左推导来说明。(2)

S=①)=(L,S)

abab

^(S,S)=(a,S)n(a,a)对于句子构造两个不同的最右推导。

(3)对于句子abab构造两棵不同的分析树。

②(a,(a,a))=

(4)

Sn(L)n(L,S)^^(S,S)^*(a,S)此文法所产生的语言是什么？

解答：B,C：①S=(L)二(L,S)=>(L,a)=>(S,a)

(a)句子abab有如下两个不同的最左推导：n(a,a)

S—^aSbS—^abS—^abaSbS—^ababS②S—^(L)—(L,S)—^(S,S)—^(S,a)

=^ababn(a,a)

S—^aSbS—^abSaSbS—^abaSbS—③Sn(L)—(L,S)—^(S,S)—^(a,S)

ababS=*>ababn(a,a)

所以此文法是二义性的。D：

(b)句子abab的两个不同的最右推导：

S^>aSbS^^aSbaSbS^^aSbaSb

①()

aSbab=*abab2S@s

>Zl\

S^^aSbS^^aSb^^abSaSb^abSab/l\LZl\

^^abab

—,s

S

a

—

a

a

E：①(a,a)②a,a③(a)@a

解答：

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

3J从供选择的答案中，选出应填入下面叙

述中？内的最确切的解答。

有限状态自动机可用五元组(VT,Q,5,

qO,Qf)来描述，设有一有限状态自动机M

的定义如下：

V={0,1),Q={q,q,qbQ={q}，6的

T012f2

定义为：

(d)此文法产生的语言是：所有a的个数与6(q。，0)=q(3(q/0)=q,

b的个数相等的由a和b组成8(q/1)=q,6(q2，0)=q?

的字符串。M是一个"A有限会态自动机，它所对应的

状态转换图为B,它所能接受的语言可以用

24从供选择的答案中，选出应填入的正

正则表达式表示为Co其含义为Do

确答案。供选择的答案：

已知文法G[S]的产生式如下：

S一(L)|aA:①歧义的②非歧义的③确定

的④非确定

L-L,S|S

属于L(G[S])的句子是A,(a,a)是L(G[S])

B:

的句子，这个句子的最左推导是B,最右

推导是C,分析树是D,句柄是E.

供选择的答案：

A：①a②a,a③(L)④(L,a)

2

成的正规集的正规式为b*(a|b)*u()

(5)对任何一个NFAM都存在一个DFAM;

使得L(M')=L(M)a()

(6)对一个右线性文法G,必存在一个左线性

文法G',使得L(G)=L(G'),反之亦然。()

答案：

(1)T(2)T(3)F(4)F(5)T(6)T

3・3描述下列各正规表达式所表示的语言。

(1)0(0|1)*0

⑵((£|0)1*)*

C：①(0|l『②00(011厂③(0|l)"00④(3)(0|1)*0(0|1)(011)

0(011)-0(4)0*10*10*10*

D：①由。和1所组成的符号串的集合(5)(00111)*((01|10|(00|11)*(01|10)(00|11)*)*

②以0为头符号和尾符号、由0和1答案

所组成的符号串的集合；

③以两个0结束的，由0和1所组成(1)以0开头并且以0结尾的，由。和1组

的符号串的集合；成的所有符号串。

④以两个0开始的，由。和1所组成的⑵{a|a£{O,l}*}即由0和1组成的所有符

符号串的集合。号串。

试题分析(3)由0和1组成的符号串，且从右边开始

有限自动机分为确定有限自动机和非确数第3位为0。

定有限自动机。确定有限自动机的现定性表(4)含3个1的由0和1组成的所有符号

现在映射6：QxVT—>q是单值函数，也就串。{a|aG{0,l}+,且a中含有3个1}

是说，对任何状态q£Q和输入字符串aG(5){a|a£{0,l}*,a中含0和1的数目为偶

VT,3(q,a)唯一确定下一个状态。显然，本数。}

题给出的是一个确定的有限自动机，它的状

・已知文法G[S],其产生式如下：

态转换图是B中的②。47°

它所接受的语言可以用正则表达式表示S->(L)|a

为00(0|1)*,表示的含义为由两个0开始的L->L,S|S

后跟任意个(包含0个)0或1组成的符号文法G[S]的算符优先关系由下表给出。建

串的集合。立与下表相应的算符优先函数并用算符优

答案先分析法分析句子(aja,a))。

A:③BeC:②D:@文法G[S]的算符优先关系表

3・2是非判断，对下面的陈述，正确的在陈

述后的括号内写T,否则写F。

⑴有穷自动机接受的语言是正则语言。()

⑵若r1和r2是£上的正规式，则r11r2也

是()

⑶设M是一个NFA,并且L(M)={x,y,z),答案:

则M的状态数至少为4个>()

(4)令£={a,b},则E上所有以b为首的字构

3

相邻的非终结符号"()

解：(3)算符优先文法中任何两个相邻的终结符

对每个终结符或$建立符号f与g,把f(和号之间至少满足三种

g)分成一组。

关系(V、・>,=)之一。0

根据G[S]的算符优先关系表，画出如下的有

向图：(4)任何LL⑴文法都是无二义性

的。0

(5)每一个SLR⑴文法也都是LR⑴文

法。()

(6)存在一种算法，能判定任何上下文无关

文法是否是LL(1)的。()

(7)任何一个LL(1)文法都是一个LR(1)文

法，反之亦然。()

(87LR(U括号中的1是指，在选用产生式

A-a进行分析，看当前读入符号是否在

FIRST(a)中。()

答案：

(1)x(2)4(3)x(4)4(5)个(6)«

(7)x(8)x

用算符优先分析法分析句子(a,(a,a))：

420选择题

栈输入动作从供选择的答案中，选出应填入内的

$(a.(a.a))$初始

正确答案。

$(a.(a.a))$移进

$(a,(a.a)*移进在编译程序中，语法分析分为自顶向

$(N,(a.a))$归约下分析和自底向上分析两类。_A_和

移进

$(N.(a.a))$LL(1)分析法属于自顶向下分析；_B_和

$(N.(a.a))$移进

$(N.(a,a)*移进LR分析法属于自底向上分析。自顶向下分

$(N.(N.a))$归约析试图为输入符号串构造一个_C_；自底向

$(N.(N.a)好移进上分析试图为输入符号串构造一个

$(N.(N.a擀移进

_D_o采用自顶向下分析方法时，要求文

$(N.(N.N))$归约

约

归

$(N,(N法中不含有_E_。

)*进

移

$(N.(N)*

供选择的答案：

$(N,N¥归妁

$(N归妁

$(N)$移进A、B：①深度分析法②宽度优先分析法

$N$归约，接受③算符优先分析法

④预测递归分析法

419判断题B、D：①语法树②有向无环图

③最左推导④最右推导

对下面的陈述，正确的在陈述后的括号内画

否则画"X"E：①右递归②左递归③直接右递归

④直接左递归

(1)存在有左递归规则的文法是LL(1)

答案：

的。0

43342

(2)任何算符优先文法的句型中不会有两个

4

选择题L.val:-L•val木2十B.val

4.27i

L->LB

从供选择的答案中，选出应填入内的正1

确答案。L.p:=L.p*2-i;

自底向上语法分析采用_A_分析法，常用

B->0B.val:=0;

的是自底向上语法分析有算符优先分析法

和LR分析法。LR分析是寻找右句型的B->1B.val:=l;

_B_：而算符优先分析是寻找右句型的

(2)分析：设B.c是B的综合属性，是B产

_C_«LR分析法中分析能力最强的是

生的位对最终值的贡献。要求出B.c,必须

D；分析能力最弱的是E.

求出B产生位的权，设B.ioB.i的求法请参

供选择的答案：

A：①递归②回溯③枚举④移进一规

约B、C：①短语②素短语

③最左素短语④句柄

C、E：®SLR(1)@LR(0)@LR(1)

@LALR(1)

答案：44332

55用s的综合属性val给出在下面的

文法中的S产生的二进制数的值(例如，

对于输入101.101,S.val=5.625)：

S—L.L|L看下面的图示:

L—LB|B

B-0|1另外，设L.fi为继承因子，L.fs为综

合因子，语法制导定义如下：

(1)试用各有关综合属性决定S.val。

(2)试用一个语法制导定义来决定S.vah

在这个定义中仅有B的综合属性，设为c,产生式语义规则

它给出由B生成的位对于最后的数值的贡

s->L.i:=l;L.fi:=2;L.fs:=l;

献。例如，在101.101中的第一位和最后一

LS.vaI:=L.val;

位对于值5.625的贡献分别为4和0.125。

答案：Ll.i=l,Ll.fi=2;Ll.fs:=l;

(1)用综合属性决定s.val的语法制导定义：S->L2.i=2-1;L2.fi=l;

L1.L2L2.fs:=2-1;

产生式语义规则S.val:=Ll.val+L2.val;

LL.s:=L.i;B.i:=L.s;

S.val:=L.val;

S->L->BL.val:=B.c;

Ll.i:=L.i*Ll.fi;

S.val^Lj.val+Lval*Lp;

S->L.L2L->L.s:=Ll.s*Ll.fs;

12I.B

I......-------1B.i:=L,s;

L.val:=B.val;L.val:=LI.val+B.c;

L->BL.p:=2i;

BB.c：=0；

5

->0

516判断题：判断下面陈述的正误。

B->1B.c:=B.i;

（1）语法制导定义中某文法符号的一个属

若把文法改写成如下形式，则语法制导定义性，既可以是综合属性，又可以是继承属性。

会更清楚：（2）只使用综合属性的语法制导定义称为

S->L.R|LS-属性定义。

L->LB|B（3）把L-属性定义变换成翻译模式，在构

R->RB|B造翻译程序的过程中前进了一大步。

B>0|1（4）一个特定的翻译模式既适于自顶向下

分析，又适于自底向上分析。

（5）用于自顶向下分析的翻译模式，其基础

产生式语义规则

文法中不能含有左递归。

S->LL.i:=l;S.val:=L.val;（6）在基础文法中增加标记非终结符不会

导致新的语法分析冲突。

L.i=l;R.i=2-1;

S->L.R答案：FTTFTF

S.val:=L.val+R.val;

B.i:=L.i;Ll.i:=L.i*2;

L->L1B6・7判断题

L.val:=L1.val+R.c;

（1）对于允许递归调用的程序语言，程序运

L->BB.i:=L.i;L.val:=B.c;行时的存储分配策略不能采用静态的存储

分配策略。（）

Rl.i:=R.i;R.s:=Rl.s*2-l;

R->R1B（2）若一个程序语言的任何变量的存储空

B.i:=R.s;

间大小和相互位置都能在编译时确定，则可

R.s:=R.i;B.i:=R.s;采用静态分配策略。（）

R->B

R.val:=B.c;（3）在不含嵌套过程的词法作用域中，若一

个过程中有对名字a的非局部引用，则a必

B->0B.c:=O;

须在任何过程（或函数）夕做说明。（）

B->1B.c:=B.i;（4）在允许嵌套的词法作用域的语言中，过

程不能作为参数，原因时不能建立其运行环境

的存取链。（）

515填空:从供选择的答案中选出应填入

（5）在堆式存储分配中，一个堆中存活的活

下面陈述中（）处的答案。动记录不一定是邻接的。（）

描述文法符号语义的属性有两种，一种（6）如果源程序正文中过程p直接嵌入在

称为（A），另一种称为（B）o（A）值的计算依过程q中，那么，p的一个活动记录中的存

赖于分析树中它的（C）的属性值；（B）的值取链接指向q的最近的活动记录。（）

答案：

的计算依赖于分析树中它的（D）的属性值。TFTFTT

供选择的答案：6.8从供选择的答案中，选出应填入下面

A,B:①L-属性②R-属性

③综合属性④继承属性叙述中（?）内的最确切的答案。

C,D:①父结点②子结点运行时的存储分配策略分（A）和（B）

③兄弟结点④父结点与子结点两类。（B）又分（C）和（D）。一个语

⑤父结点与兄弟结点言中不同种类的变量根据定义域和生存期

答案：3425的不同往往采用不同的存储分配策略，C语

6

言中的静态变量往往采用(A),而自动9・1试构造下面的程序的流图，并找出其

(out)类变量往往采用(C使用mallac中

申请的内存单元采用(D)<,中所有回边及循环。

供选择答案readP

A,B,C,D:①栈式分配②最佳分配x:=1

③堆式分配④静态分配c:=P*P

⑤随机分配⑥动态分配ifc<100gotoLI

B:=P*P

答案：A:@B:@C:①D:③X:=x+1

B:=B+x

writex

翻译算术表达式一g+b)*(c+d)

halt

+(a+b+c)为LI:B:=10

(1)四元式，x:=x+2

(2)三元式B:=B+x

(3)间接三元式writeB

答案：