千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦編譯原理期末考試試卷與答案得分一．填空題（每

空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)thenx:=y+z。要求：給出加解釋的分析樹及四

元式序列。

參考以下部分翻譯模式：

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

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

(2)S→whileM1Edo

M2S1{backpatch(S1.nextlist

,M1,.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.nextlist}

(5)M→ε

{M.quad:=nextquad}

(6)E→

id1relopid2{E.truelist:=makelist(nextquad);

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

‘,’id1.place‘,’id2.place

‘,’‘0’);

emit(

‘j,-,-,0’)}

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

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

15．（共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)doif(a=b)thenx:=2*y+a。要求：給出加解釋的分析

樹、

三地址碼序列及相應的四元式序列。參考以下部分翻譯模

式：

(1)S→ifEthen

MS1{backpatch(E.truelist,M.quad);

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

(2)S→whileM1EdoM2S1

{backpatch(S1.nextlist,M1,.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.nextlist}

(5)M→ε

{M.quad:=nextquad}

(6)E→id1relop

id2{E.truelist:=makelist(nextquad);

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

‘,’id1.place‘,’id2.place‘,’‘0’);

emit(

‘j,-,-,0’)}

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

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

emit(+,E

.place,E2

.place,E.place,)}

16.(8分)Generateassemblycodefor

the

followingsequenceassumingthatx,yandzareinmemory

locations(noticingonlytworegistersR1andR2).

S=0

I=0

L1:ifx>ygotoL2

Z=s+a[i]

I=i+1

GotoL1

L2:

7．(6分)Giveouttheallbasicblocksofthefollowingprogramfragmentandconstructtherelevantflowgraph(DAG).

readC

A=0

B=1

L4:A=A+B

ifB>CgotoL2

B=B+1

gotoL4

L2:writeA

8.(8分)Translatetheassignment

statementb[i]=b*c-

b*d

into

(1)Asyntaxtree.

(2)Threeaddressinstructions.

答案：：

(1)棧式動態存儲分配

(2)堆式動態存儲分配

(3)左

(4)語法分析

(5)目標代碼生成

(6)表格管理

(7)xyz*ab+/+

(8)繼承屬性

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

(10)基本塊

一、挑選題（每問2分，共20分）

1.CB

2.D

3.B

4.A

5.D

6.A,C

7.BCD,選對一個得1分且不超過滿分，選錯一個扣一分，扣完

為止

。

8.BCD，選對一個得

二、解答題1分且不超過滿分，選錯一個扣一分，扣完

為止

。

1．（1）文法存在左遞歸，消退左遞歸后的文法為：E→(E)E’|iE’（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*+#

EE→(E)E’E→iE’

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

E’→εE’→ε

TT→*T→+

2．（1）規范推導過程如下。寫錯推導符號扣0.5分,錯寫或少寫一步推導扣0.5分，扣完為止，最左推導扣2分，共4分。

SS(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）打印的字符串是：12022（錯一個扣0.5分，共3分）

（2）歸約過程中錯一步扣0.5分，扣完為止。（共5分）

4．（1）每少寫一步扣0.5分，扣完為止，共5分。

S

whileM1.q=100E1.t=102doM2.q=102S1

E1.f=107

εadxE5.p=

y

+

E6.p=z

yz

（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∧(),#

f662662

g777252

或者

a∧(),

f44244

g55523

三、填空題（每空2分，共20分）

1目標程序（targetcode）語法分析（syntaxanalyzer）代碼優化器（codeoptimizer）代碼產生器（codegenerator）符號表管理（symboltablemanager）

2繼承屬性（inheritedattribute）

3局部優化（localoptimization）

4四元式（quatriple）

5E+*()id

四、單項挑選題（每題2分，共10分）

1.B

2.D

3.B

4.D

5.C

五、解答題（共70分）

1．（1）L(G)={0m1m|M≥1}共2分，≥寫成＞扣1分

（2）S=>0S1=>00S11=>000111，共3分，=>寫成->扣1分

（3）共3分，錯處扣

0.5分，扣完為止

2.（1）空白表格也可以填寫“錯誤”字樣,共4分，錯一個扣

0.5分，扣完為止

abc$(#)SS→aBcS→bAB

AA→aAbA→b

BB→bB→εB→ε

（2）共6分，其中推斷

“baabbb是該文法句子”為2分，其他錯一個

扣

0.5分，扣完為

止

符號棧輸入串規章

$Sbaabbb$

$BAbbaabbb$S→bAB$BAaabbb$

$BbAaaabbb$A→aAb$BbAabbb$

$BbbAaabbb$A→aAb$BbbAbbb$

$Bbbbbbb$A→b$Bbbbb$

$Bbb$

$b$B→ε$$success

3.(1)共6分，其中推斷“該文法為算符優先文法”

為

2分，其他錯一個

扣

0.5分，扣完為

止

+*i

+>>>

(2)共4分，錯一個扣0.5分，扣完為止

+*i

f244

g135

4．（1）34242421，

共

4分，錯一個

扣

0.5分

（2）共4分，錯一個

扣

0.5分，扣完為止

stackInputstringaction$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(((aa)a)a)b$$shift

$b(((Aa)a)a)b$reduce,

A→a

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

$b(((Ba)a)b$reduce,

B→Aa）

$b((Aa)a)b$reduce,

A→(B

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

$b（（Ba)b$reduce,

B→Aa）

$b(Aa)b$reduce,

A→(B

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

$b(Bb$reduce,

B→Aa）

$bAb$reduce,

A→(B

$bAb$shift

$S$reduce,

S→bAb

$s$accept

5．共12分，其中帶解釋的分析樹、三地址碼序列和四元式序列

分離為4分，錯一個序列扣0.5分，而

錯某點（某項）少于或等

于5個扣0.5分

帶解釋語法樹(略)

三地址碼序列四元式序列M1:if(x>y)gotoM2100(j>,x,y,102)gotoM4101(j,-,-,108)

M2:if(a=b)gotoM3102(j=,a,b,104)gotoM1103(j,-,-,100)

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

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

x=t2106(=,t2,-,x)

gotoM1107(j,-,-,100)

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

6．共8分，錯一個扣

0.5分，扣完為止

LDR1,0

STS,R1

STI,R1

L1:LDR1,X

SUBR1,R1,Y(ORSUBR1,Y)

BGTZR1,L2

LDR2,a(R1)

ADDR2,R2,S(ORADDR2,S)

STZ,R2

LDR1,I(從這開頭，下面的語句中的R1也可以所有變成R2)ADDR1,R1,1(ORINCR1)

STI,R1

BRL1

L2:

7．共6分，基本塊劃分和流圖各為3分，錯一處扣1分，扣完為止

B1B2B3readc

A=0

B=1

L4:A=A+B

IfB>CgotoL2(ORB4)

B=B+1

GotoL4(ORB2)

B4L2:writeA

8.（1）共4分，錯一項扣1分，扣完為止（2）共4分，錯一項扣1分，扣完為止

t1=b*c

t2=b*d

t3=t1-t2

t4=i+1(ort4=i)

b[t4]=t3

一、推斷題：

1

.一個上下文無關文法的開頭符，可以是終結符或非終結符。()2

.一個句型的直接短語是唯一的。()3

.已經證實文法的二義性是可判定的。（）4

.每個基本塊可用一個DAG表示。（）5.每個過程的活動記錄的體積在編譯時可靜態確定。（

）

6.2型文法一定是3型文法。（

）

7

.一個句型一定句子。()8.算符優先分析法每次都是對句柄舉行歸約。()9

.采納三元式實現三地址代碼時，不利于對中間代碼舉行優化。（）

10.編譯過程中，語法分析器的任務是分析單詞是怎樣構成的。()11.一個優先表一定存在相應的優先函數。

()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.一個過程相應的DISPLAY表的內容為（）。9

.一個句型的最左直接短語稱為句型的（）。10.常用的兩種動態存貯分配方法是（）動態分配和（）動態分配。11.一個名字的屬性包括()和()。12.常用的參數傳遞方式有（），（）和（）。13.按照優化所涉及的程序范圍，可將優化分成為（），（

）和（）三個級別。14.語法分析的辦法大致可分為兩類，一類是（）分析法，另一類是（）分析法。

15.預測分析程序是使用一張（）和一個（）舉行聯合控制的。16.常用的參數傳遞方式有（），（）和（）。

17.一張轉換圖只包含有限個狀態,其中有一個被認為是（）態;而且實際上至少要有一個（）態。

18.按照優化所涉及的程序范圍，可將優化分成為（），（）和（）三個級別。

19.語法分析是依據語言的（）規章舉行。中間代碼產生是依據語言

的（）規章舉行的。20.一個句型的最左直接短語稱為句型的（）。

21.一個文法G，若它的預測分析表M不含多重定義，則該文法是（）文法。

22

.對于數據空間的存貯分配，FORTRAN采納()策略，PASCAL采納()策略。

23

.假如一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是

()。

24

.最右推導亦稱為（），由此得到的句型稱為

（）句型。

25

.語法分析的辦法大致可分為兩類，一類是（）分析法，另一類是（）分析法。

26

.對于文法G，僅含終結符號的句型稱為()。

27

.所謂自上而下分析法是指（）。28

.語法分析器的輸入是（），其輸出是（）。

29.局限于基本塊范圍的優化稱

（

。

）

30

.預測分析程序是使用一張（）和一個（）舉行聯合控制的。

31.2型文法又稱為（）文法；3型文法又稱為（）文法。

32.每條指令的執行代價定義為

（）。

33.算符優先分析法每次都是對

（）舉行歸約。

三、名詞解釋題：

1.局部優化

2.二義性文法

3.DISPLAY表

4.詞法分析器

5.最左推導

6.語法

7.文法

8.基本塊

9.語法制導翻譯

10.短語

11.待用信息

12.規范句型

13.掃描器

14.超前搜尋

15.句柄

16.語法制導翻譯

17.規范句型

18.素短語

19.語法

20.待用信息

21.語義

四、簡答題：

1.寫一個文法G,使其語言為不以0開始的偶數集。

2.已知文法G(S)及相應翻譯計劃

S→aAb{print“1”}

S→a{print“2”}

A→AS{pri

nt

“3”}

A→

c

{print“4”}

輸入acab,輸出是什么？

3.已知文法G(S)

S→bAa

A→(B

|aB→Aa)

寫出句子b(aa)b的規范歸約過程。

4.考慮下面的程序：

,

procedurep(x,y,z)；

beginy:=x+y;z:=z*z;endbegin

A:=2;B:=A*2;P(A,A,B);PrintA,B

end.

試問，若參數傳遞的方式分離采納傳地址和傳值時，程序執行后輸出A,B的值是什么?

5.文法G(S)S→dABA→aA|aB→Bb|ε

描述的語言是什么？6.證實文法G(S)

是二義性的。

7.已知文法G(S)S→BA

A→BS|d

B→aA|bS|c

的預測分析表如下

ab

cd#S

S→BAS→BAS→BA

AA→BSA→BSA→BSA→dB

B→aA

B→bS

B→c

給出句子adccd的分析過程。lbmclanbn|

8.寫一個文法G,使其語言為L(G)={al>=0,m>=1,n>=2}9.已知文法

G(S):

S→a|(T)

T→T,S|S

的優先關系表如下：

關系a(),a--.>.>(.>

,

.>

請計算出該優先關系表所對應的優先函數表。10.何謂優化？按所涉及的程序范圍可分為哪幾級優化？11.目標代碼有哪幾種形式？生成目標代碼時通常應考慮哪幾個問題？12.一字母表Σ={a,b}，試寫出Σ上全部以a為首的字組成的正規集相對應的正規式。

13.基本的優化辦法有哪幾種？

14.寫一個文法G,使其語言為L(G)={abncn|n≥0}

15.考慮下面的程序：

,

procedurep(x,y,z);

begin

y:=y+z;

z:=y*z+x

end;

begin

a:=2;

b:=3;

p(a+b,b,a);

printa

end.

試問，若參數傳遞的方式分離采納傳地址和傳值時，程序執行后輸出a的值是什么?

16.寫出表達式a＋b*(c-d)/e的逆波蘭式和三元序列。

17.證實文法G(A)

A→AA|(A)|ε

是二義性的。

18.令Σ={a,b}，則正規式a*b|b*a表示的正規集是什么？

19.何謂DISPLAY表？其作用是什么？

20.考慮下面的程序：

,

procedurep(x,y,z)；

begin

y:=y+2;

z:=z+x;

end

begin

a:=5;

b:=2;

p(a+b,a-b,a);

printa

end.

試問，若參數傳遞的方式分離采納傳地址和傳值時，程序執行后輸出a的值是什

么

?

21.寫一個文法G,使其語言為L(G)={anbncm|n>0為奇數，

22.寫出表達式a:=(b+c)*e+(b+c)/f的逆波蘭式和三元序列。m>0為偶

數

}

23.一個文法G別是LL(1)文法的充要條件是什么？

24.已知文法G[S]

S→S*aF|aF|

*aFF→+aF|

+a

消退文法左遞歸和提公共左因子。

25.符號表的作用是什么？符號表查找和收拾技術有哪幾種？五、計算題：

1.設文法G(S):

S→^|a|(T)

T→T,S|S

⑴消退左遞歸；

⑵構造相應的FIRST和FOLLOW集合；

⑶構造預測分析表

2.語句ifEthenS

(1)改寫文法，使之適合語法制導翻譯；

(2)寫出改寫后產生式的語義動作。

3.設文法G（S）：

S→(T)|

a

T→T+S|S

(1）計算FIRSTVT和LASTVT；

（2）構造優先關系表。

4.設某語言的for語句的形式為

fori:＝E(1)toE(2)doS

其語義解釋為

i:＝E(1)

LIMIT:＝E(2)

again:ifi＜＝LIMITthen

Begin

S;

i:＝i

＋1

goto

again

End;

（1）寫出適合語法制導翻譯的產生式；

（2）寫出每個產生式對應的語義動作。

5.把語句

whilea0thena:=a+1

elsea:=a*3-1;

翻譯成四元式序列。

6.設有基本塊

D:=A-C

E:=A*C

F:=D*E

S:=2

T:=A-C

Q:=A*C

G:=2*S

J:=T*Q

K:=G*5

L:=K+J

M:=L

假設基本塊出口時惟獨M還被引用，請寫出優化后的四元序列。

7.已知文法G(S)

S→a|^|

(T)T→T,S|S

(1)給出句子(a,(a,a))的最左推導；

(2)給出句型((T,S),a)的短語,直接短語，句柄。

8.對于C語言doSwhileE語句

(1)改寫文法，使之適合語法制導翻譯；

(2)寫出改寫后產生式的語義動作。

9.已知文法G(S)

S→

aAcBeA

→Ab|b

B→d

(1)給出句子abbcde的最左推導及畫出語法樹；

(2)給出句型aAbcde的短語、素短語。

10.設文法G(S):

S→(T)|aS|a

T→T,S|S

⑴消退左遞歸和提公共左因子；

⑵構造相應的FIRST和FOLLOW集合；

⑶構造預測分析表。

11.把語句

ifX>0∨Y0doX:=A*3

elseY:=B+3;

翻譯成四元式序列。

12.已知文法G(S)

E→E+T|T

T→T*F|

FF→

(E)|i

(1)給出句型(i+i)*i+i的最左推導及畫出語法樹；

(2)給出句型(E+T)*i+F的短語，素短語和最左素短語。

13.設文法G（S）：

S→T|S∨T

T→U|T∧U

U→i|-U

（1）計算FIRSTVT和LASTVT；

（2）構造優先關系表。

參考答案一、是非題：

1.×

2.×

3.×

4.√

5.√

6.×

7.×8.×9.√10.×11.×

12.√13.×14.√15.√16.√17.×18.√19.√20.×21.√22.√

二、填空題：

1.(最右推導）

2.(詞法分析），（語法分析），（中間代碼生成），（代碼優化），（目標代碼生

成）

3.(二義性的）

4.(執行性），（說明性）

5.(單詞符號），（語法單位）。

6.(源程序），（單詞符號）

7.(類型、種屬、所占單元大小、地址）

8.(現行活動記錄地址和全部外層最新活動記錄的地址)

9.(句柄）

10.(棧式)，（堆式）

11.(類型)，（作用

域）

12.(傳地址），（傳值），（傳

名）

13.(局部優化），（循環優化），（全局優

化）

14.(自上而下），（自下而上）

15.(分析表），（符號棧）

16.(傳地址），（傳值），（傳

名）

17.(初），（終）

18.(局部優化），（循環優化），（全局優

化）

19.(語法），（語義）

20.(句柄）

21.(LL(1)文法）

22.(靜態），（動態）

23.(二義性文法）

24.(規范推導），（規范）

25.(自上而下），（自下而上）

26.(句子)

27.(從開頭符號動身，向下推導，推出句子）

28.(單詞符號），（語法單位）

29.(局部優化）

30.(分析表），（符號棧）

31.(上下文無關文法），（正規）

32.(指令拜訪主存次數加1）

33.(最左素短語）

三、名詞解釋題：

1.局部優化局限于基本塊范圍的優化稱。

2.二義性文法假如一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義性文法。

3.DISPLAY表過程的嵌套層次顯示表，記錄該過程的各外層過程的最新活動記錄的起始地址。

4.詞法分析器執行詞法分析的程序。

5.最左推導任何一步α=>β都是對α中的最右非終結符替換。

6.語法一組規章，用它可形成和產生一組合式的程序。

7.文法描述語言的語法結構的形式規章。

8.基本塊指程序中一挨次執行的語句序列，其中惟獨一個入口和一個出口，入口就是其中的第一

個語句，出口就是其中的最后一個語句。

9.語法制導翻譯在語法分析過程中，按照每個產生式所對應的語義子程序舉行翻譯的方法叫做語法

制導翻譯。

10.短語令G是一個文法，S劃文法的開頭符號，假定αβδ是文法G的一個句型，假如有SαAδ且

Aβ，則稱β是句型αβδ相對非終結符A的短語。

第1頁共25頁

11.待用信息假如在一個基本塊中，四元式i對A定值，四元式j要引用A值，而從i到j之間沒有A的

其它定值，則稱j是四元式i的變量A的待用信息。

12.規范句型由規范推導所得到的句型。

13.掃描器執行詞法分析的程序。

14.超前搜尋在詞法分析過程中，有時為了確定詞性，需超前掃描若干個字符。

15.句柄一個句型的最左直接短語。

16.語法制導翻譯在語法分析過程中，按照每個產生式所對應的語義程序舉行翻譯的辦法叫做語法制導翻譯。

17.規范句型由規范推導所得到的句型。

18.素短語素短語是指這樣一個短語，至少含有一個終結符，并且，除它自身外不再含任何更小的素

短語。

19.語法是組規章，用它可形成和產生一個合式的程序。

20.待用信息假如在一個基本塊中，四元式i對A定值，四元式j要引用A值，而從i到j之間沒有A的

其它定值，則稱j是四元式i的變量A的待用信息。

21.語義定義程序的意義的一組規章。

四、簡答題：

1.所求文法是G[S]:

S→AB|B

A0A→AD

|C

B→2|4|6|8

C→1|3|5|7|9|B

D→0|C

2.輸出是4231

3.句子b(aa)b的規范歸約過程：

步驟符號棧輸入串動作

0#b(aa)b#準備

1#b(aa)b#移進

2#b(aa)b#移進

3#b(aa)b#移進

4#b(Aa)b#歸約

5#b(Ma)b#移進

6#b(Ma)b#移進

7#b(Bb#歸約

8#bAb#歸約

9#bAb#移進

10#S#接受4.傳地址A=6,

B=16

傳值A=2,B=4

5.L(G)={danm

≥0}b|n>0,m

6.證實：

由于文法G[S]存在句子aa有兩個不同的最左推導，所以文法G[S]是是二義性的。

S=>SaS=>SaSaS=>aSaS=>aaS=>aa

S=>SaS=>aS=>aSaS=>aaS=>aa

7.句子adccd的分析過程：

步驟符號棧輸入串產生式

0#Sadccd#

1#ABadccd#S→BA2#AAaadccd#B→aA3#AAdccd#

第2頁共25頁

4#Addccd#A→d

5#Accd#

6#SBccd#A→BS

7#Scccd#B→c

8#Scd#

9#ABcd#B→c

10#Acd#

11#Ad#

12#dd#A→d

13##

8.所求文法是G[S]:

S→AB

A→aAc|

DD→bD|

b

B→aBb|aabb

9.

函數a(),

f4244

g5523

10.優化：對程序舉行各種等價變換，使得從變換后的程序動身，能產生更有效的目標

代碼。三種級別：局部優化、循環優化、全局優化

11.目標代碼通常采納三種形式：機器語言，匯編語言，待裝配機器語言

模塊。應著重考慮的問題：

(1)如何使生成的目標代碼較短；

(2)如何充分利用寄存器，以削減拜訪內存次數；

(3)如何充分利用指令系統的特點。

12.正規式a(a|b)*。

13.刪除多余運算，代碼外提，強度減弱，變換循環控制條件，合并已知量，復寫傳揚和刪除無用賦值。

14.文法G[S]:

S→aB|a

B→bc|bBc

15.傳值a=2傳

地址a=15

16.逆波蘭式:abcd-*e/+

三元序列:oparg1arg2

(1)-cd

(2)*b(1)

(3)/(2)e

(4)+a(3)

17.證實：

由于文法G[S]存在句子()有兩個不同的最左推導，所以文法G[S]是是二義性的。

A=>AA=>(A)A=>()A=>()

A=>AA=>A=>(A)=>()

18.(a*b|b*a)={a,b,ab,ba,aab,bba,,}

19.Display表:嵌套層次顯示表

因為過程嵌套允許內層過程引用外層過程定義的數據，因此，當一個過程運行時必需跟蹤它的全部外層過程的最新活動記錄起始地址，display表就是用于記下每個外層過程的最新活動記錄起始地址。

第3頁共25頁

20.傳地址a=12

傳值a=5

21.所求文法是G[S]:

S→AC

A→aaAbb|ab

C→ccC|cc

22.逆波蘭式abc+e*bc+f/+:=

三元序列oparg1arg2

(1)+bc

(2)*(1)e

(3)+bc

(4)/(3)f

(5)+(2)(4)

(6):=a(5)

23.一個文法G別是LL(1)文法的充要條件是:

(1)FIRST(α)∩FIRST(β)=Ф

(2)假如β=*>ε,FIRST(α)∩FOLLOW(A)=Ф

24.消退左遞歸

S→aFS’|*aFS’

S’→*aFS’|ε

F→+aF|+a

提公共左因子,文法G’(S)

S→aFS’|*aFS’

S’→*aFS’|ε

F→+aF’

F’→F|ε

25.作用：記下源程序中浮現的各種名字及其信息，以及了解各階段的發展情況。

主要技術：線性表，對折查找，雜奏技術。

五、計算題：

1.

(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)構造預測分析表：

a^(),#

SS→aS→^S→(T)'

TT→ST’T→ST’T→ST’

T’T’→εT’→,ST’

2.(1)

C→ifEthen

(1)

S→CS

(2)

C→ifEthen{BACK(E.TC,NXQ);

C.chain:=E.FC}

S

(1)

{S.chain:=MERG(C.Chain,S

(1

).

Chain)}→CS

3.

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

FIRSTVT(T)={+,aa,(}

第4頁共25頁

LASTVT(S)={a,)}

LASTVT(T)={+,a,)}

(2)

a+()

a.>.>

+

(.>>.

4.

(1)F→for

i:=E

(1