編譯原理課后題

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

2?1考慮文法G[S],其產(chǎn)生式如卜.:

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)))

⑴試說明此文法是二義性的?？梢詮膶τ诰?/p>

(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)此文法所產(chǎn)生的語言是什么？

解答：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從供選擇的答案中，選出應填入下面敘

述中？內(nèi)的最確切的解答。

有限狀態(tài)自動機可用五元組(VT,Q,5,

qO,Qf)來描述，設有一有限狀態(tài)自動機M

的定義如下：

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

T012f2

定義為：

(d)此文法產(chǎn)生的語言是：所有a的個數(shù)與6(q。，0)=q(3(q/0)=q,

b的個數(shù)相等的由a和b組成8(q/1)=q,6(q2，0)=q?

的字符串。M是一個"A有限會態(tài)自動機，它所對應的

狀態(tài)轉換圖為B,它所能接受的語言可以用

24從供選擇的答案中，選出應填入的正

正則表達式表示為Co其含義為Do

確答案。供選擇的答案：

已知文法G[S]的產(chǎn)生式如下：

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

成的正規(guī)集的正規(guī)式為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描述下列各正規(guī)表達式所表示的語言。

(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組成的符號串，且從右邊開始

有限自動機分為確定有限自動機和非確數(shù)第3位為0。

定有限自動機。確定有限自動機的現(xiàn)定性表(4)含3個1的由0和1組成的所有符號

現(xiàn)在映射6：QxVT—>q是單值函數(shù)，也就串。{a|aG{0,l}+,且a中含有3個1}

是說，對任何狀態(tài)q￡Q和輸入字符串a(chǎn)G(5){a|a￡{0,l}*,a中含0和1的數(shù)目為偶

VT,3(q,a)唯一確定下一個狀態(tài)。顯然，本數(shù)。}

題給出的是一個確定的有限自動機，它的狀

?已知文法G[S],其產(chǎn)生式如下：

態(tài)轉換圖是B中的②。47°

它所接受的語言可以用正則表達式表示S->(L)|a

為00(0|1)*,表示的含義為由兩個0開始的L->L,S|S

后跟任意個(包含0個)0或1組成的符號文法G[S]的算符優(yōu)先關系由下表給出。建

串的集合。立與下表相應的算符優(yōu)先函數(shù)并用算符優(yōu)

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

A:③BeC:②D:@文法G[S]的算符優(yōu)先關系表

3?2是非判斷，對下面的陳述，正確的在陳

述后的括號內(nèi)寫T,否則寫F。

⑴有窮自動機接受的語言是正則語言。()

⑵若r1和r2是￡上的正規(guī)式，則r11r2也

是()

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

則M的狀態(tài)數(shù)至少為4個>()

(4)令￡={a,b},則E上所有以b為首的字構

3

相鄰的非終結符號"()

解：(3)算符優(yōu)先文法中任何兩個相鄰的終結符

對每個終結符或$建立符號f與g,把f(和號之間至少滿足三種

g)分成一組。

關系(V、?>,=)之一。0

根據(jù)G[S]的算符優(yōu)先關系表，畫出如下的有

向圖：(4)任何LL⑴文法都是無二義性

的。0

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

法。()

(6)存在一種算法，能判定任何上下文無關

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

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

法，反之亦然。()

(87LR(U括號中的1是指，在選用產(chǎn)生式

A-a進行分析，看當前讀入符號是否在

FIRST(a)中。()

答案：

(1)x(2)4(3)x(4)4(5)個(6)?

(7)x(8)x

用算符優(yōu)先分析法分析句子(a,(a,a))：

420選擇題

棧輸入動作從供選擇的答案中，選出應填入內(nèi)的

$(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：①深度分析法②寬度優(yōu)先分析法

$N$歸約，接受③算符優(yōu)先分析法

④預測遞歸分析法

419判斷題B、D：①語法樹②有向無環(huán)圖

③最左推導④最右推導

對下面的陳述，正確的在陳述后的括號內(nèi)畫

否則畫"X"E：①右遞歸②左遞歸③直接右遞歸

④直接左遞歸

(1)存在有左遞歸規(guī)則的文法是LL(1)

答案：

的。0

43342

(2)任何算符優(yōu)先文法的句型中不會有兩個

4

選擇題L.val:-L?val木2十B.val

4.27i

L->LB

從供選擇的答案中，選出應填入內(nèi)的正1

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

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

B->0B.val:=0;

的是自底向上語法分析有算符優(yōu)先分析法

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

_B_：而算符優(yōu)先分析是尋找右句型的

(2)分析：設B.c是B的綜合屬性，是B產(chǎn)

_C_?LR分析法中分析能力最強的是

生的位對最終值的貢獻。要求出B.c,必須

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

求出B產(chǎn)生位的權，設B.ioB.i的求法請參

供選擇的答案：

A：①遞歸②回溯③枚舉④移進一規(guī)

約B、C：①短語②素短語

③最左素短語④句柄

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

@LALR(1)

答案：44332

55用s的綜合屬性val給出在下面的

文法中的S產(chǎn)生的二進制數(shù)的值(例如，

對于輸入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,產(chǎn)生式語義規(guī)則

它給出由B生成的位對于最后的數(shù)值的貢

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;

產(chǎn)生式語義規(guī)則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）用于自頂向下分析的翻譯模式，其基礎

產(chǎn)生式語義規(guī)則

文法中不能含有左遞歸。

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）對于允許遞歸調(diào)用的程序語言，程序運

L->BB.i:=L.i;L.val:=B.c;行時的存儲分配策略不能采用靜態(tài)的存儲

分配策略。（）

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;采用靜態(tài)分配策略。（）

R->B

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

個過程中有對名字a的非局部引用，則a必

B->0B.c:=O;

須在任何過程（或函數(shù)）夕做說明。（）

B->1B.c:=B.i;（4）在允許嵌套的詞法作用域的語言中，過

程不能作為參數(shù)，原因時不能建立其運行環(huán)境

的存取鏈。（）

515填空:從供選擇的答案中選出應填入

（5）在堆式存儲分配中，一個堆中存活的活

下面陳述中（）處的答案。動記錄不一定是鄰接的。（）

描述文法符號語義的屬性有兩種，一種（6）如果源程序正文中過程p直接嵌入在

稱為（A），另一種稱為（B）o（A）值的計算依過程q中，那么，p的一個活動記錄中的存

賴于分析樹中它的（C）的屬性值；（B）的值取鏈接指向q的最近的活動記錄。（）

答案：

的計算依賴于分析樹中它的（D）的屬性值。TFTFTT

供選擇的答案：6.8從供選擇的答案中，選出應填入下面

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

③綜合屬性④繼承屬性敘述中（?）內(nèi)的最確切的答案。

C,D:①父結點②子結點運行時的存儲分配策略分（A）和（B）

③兄弟結點④父結點與子結點兩類。（B）又分（C）和（D）。一個語

⑤父結點與兄弟結點言中不同種類的變量根據(jù)定義域和生存期

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

6

言中的靜態(tài)變量往往采用(A),而自動9?1試構造下面的程序的流圖，并找出其

(out)類變量往往采用(C使用mallac中

申請的內(nèi)存單元采用(D)<,中所有回邊及循環(huán)。

供選擇答案readP

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

③堆式分配④靜態(tài)分配c:=P*P

⑤隨機分配⑥動態(tài)分配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

答案：