編譯原理題庫

第一章

什么是編譯器？

編譯程序的結(jié)構(gòu)分為幾個階段，各階段的任務(wù)是什么？

遍、編譯前端及編譯后端的含義？

編譯程序的生成方式有哪些？

第二章

1.寫一文法，使其語言是偶正整數(shù)的集合。

要求：（1）允許。打頭（2）不允許0打頭

解：（1）允許0開頭的偶正整數(shù)集合的文法

E-NT|D

T-NT|D

N-*D|1|3|5|7|9

D-0|2|4|6|8

（2）不允許0開頭的偶正整數(shù)集合的文法

E-NT|D

T-*FT|G

N-D|l|3|5|7|9

D-2|4|6|8

F-*N|O

G-D|O

2.證明下述文法G［〈表達式〉］是二義的。

〈表達式〉：：=a|（〈表達式〉）|〈表達式〉〈運算符〉〈表達式〉

〈運算符〉：：=+卜|*|/

解：可為句子a+a*a構(gòu)造兩個不同的最右推導(dǎo)：

最右推導(dǎo)1〈表達式〉〈表達式〉〈運算符〉〈表達式〉

〈表達式〉〈運算符〉a

〈表達式〉*a

〈表達式〉〈運算符〉〈表達式〉*a

〈表達式〉〈運算符〉a*a

〈表達式〉+a*a

a+a*a

最右推導(dǎo)2〈表達式〉〈表達式〉〈運算符〉〈表達式〉

〈表達式〉〈運算符〉〈表達式〉〈運算符〉〈表達式〉

〈表達式〉〈運算符〉〈表達式〉〈運算符〉a

〈表達式〉〈運算符〉〈表達式〉*a

〈表達式〉〈運算符〉a*a

〈表達式〉+a*a

a+a*a

3.給出生成下述語言的上下文無關(guān)文法：

(1){anbnambmln,m〉=0}

(2){InOmlmOnln,m>=0}

解:(1){anbnambm|n,m>=0}

S-*AA

A-*aAb|E

(2){InOmlmOnln,m>=0}

S—1SO|A

A-OA1|e

第三章

1、構(gòu)造一個DFA,它接收E={a,b}上所有滿足下述條件的字符串:

字符串中的每個a都有至少一個b直接跟在其右邊。

解：

已知￡={a,b},根據(jù)題意得出相應(yīng)的的正規(guī)式為：(b*abb*)*

根據(jù)正規(guī)式畫出相應(yīng)的DFAM,如下圖所示

用子集法將其確定化

Ilalb

{X,1,2,3,Y{4}{253}

)

{4}——{5,6,1,2,3,Y}

{253}{4}{253}

Ila1b

{5,6,1,2,3,

{4}{6,1,2,3,Y}

Y}012

1——3

{6,1,2,3,Y}{4}{6,1,2,3,Y}

212

由DFA得狀態(tài)圖用最小化方法化

314

簡得：{0},{1},{2},{3,4},按順序重新命名DFAM，

414

第四章

練習(xí)1：文法G[V]：

V-*N|N[E]E-VIV+EN-i

是否為LL(1)文法，如不是，如何將其改造成LL(1)文法。

解：

LL⑴文法的基本條件是不含左遞歸和回溯(公共左因子)，而G[V]

中含有回溯，所以先消除回溯得到文法G，[V]：

G'[V]：V-*NV,V'fe|[E]

E—VE'E'-e|+E

N-i

由LL(1)文法的充要條件可證G1V]是LL(1)文法

練習(xí)2：有文法G[s]:

S-BAA-*BS|dB-*aA|bS|c

⑴證明文法G是LL⑴文法。

⑵構(gòu)造LL(l)分析表。

(3)寫出句子adccd的分析過程

解：(1)一個LL(1)文法的充要條件是：對每一個非終結(jié)符A的任何兩

個不同產(chǎn)生式A-a|B,有下面的條件成立：

①FIRST(a)AFIRST(B)=①；

②若B*￡，則有FIRST(a)nFOLLOW(A)=①

對于文法G[s]:

S-*BAA-*BS|dB-aA|bS|c

其FIRST集如下：

FIRST(B)={a,b,c};FIRST(A)={a,b,c,d};FIRST(S)={a,b,

c}o

其FOLLOW集如下：

首先，F(xiàn)OLLOW(S)={#};

對S-BA有：FIRST(A)\{e}力口入FOLLOW(B),即FOLLOW(B)={a,

b,c,d};

對A-BS有:FIRST(S)\{e}加入FOLLOW(B),即FOLLOW(B)={a,b,

c,d};

對B-aA有：FOLLOW(B)力口入FOLLOW(A),即FOLLOW(A)={a,b,

c,d};

對B—bS有:FOLLOW(B)力口入FOLLOW(S),即FOLLOW(S)={#,a,b,

c,d};

由A-BS|d得：

FIRST(BS)nFIRST(d)={a,b,c}nfzxvnhz=①；

由BfaA|bS|c得：

FIRST(aA)nFIRST(bS)nFIRST(c)={a}An{c}=

①。

由于文法G[s]不存在形如的產(chǎn)生式，故無需求解形如

FIRST”)AFOLLOW(A)的值。也即，文法G[S]是一個LL⑴文法。

(2)由G[s]:S->BAA-BS|dB-aA|bS|c的

FIRST(B)={a,b,c};FOLLOW(B)={a,b,c,d};

FIRST(A)={a,b,c,d};FOLLOW(A)={a,b,c,d};

FIRST(S)={a,b,c}oFOLLOW(S)={#,a,b,c,d}可構(gòu)造LL⑴預(yù)測

分析表如下:

abcd#

SS-BAS-BAS-BA

AA-BSA-BSA-BSA-*d

BB-aAB-bSB-c

SS-BAS-BAS-BA

AA-BSA-BSA-BSA-*d

BB-aAB-bSB-c

(3)在分析表的控制下，句子adccd的分析過程如下:

棧當(dāng)前輸入符號輸入串說明

#Sadeed#S-BA

#ABadeed#B-?aA

#AAaadeed#

#AAdccd#A—d

#Addccd#

#Accd#A-BS

#SBccd#B—c

#Scccd#

#Scd#S-BA

#ABcd#B->c

#Accd#

#Ad#A-d

#dd

##分析成功

第五章

1已知文法G[S]為:

S-a|A|(T)T-*T,S|S

(1)計算G[S]的FIRSTVT和LASTVT。

(2)構(gòu)造G[S]的算符優(yōu)先關(guān)系表并說明G[S]是否為算符優(yōu)先文法。

(3)給出輸入串(a,(a,a))#的算符優(yōu)先分析過程。

解：文法：

S-a|A|(T)T-T,S|S

展開為：

S-aS->AS->(T)

T-T,ST-*S

(1)FIRSTVT-LASTVT表

非終結(jié)符FIRSTVT集LASTVT集

S{aA(}{aA)}

T{aA(,}{aA),}

⑵算符優(yōu)先關(guān)系表如下：表中無多重入口所以是算符優(yōu)先(OPG)文

法。

aA()#

a

A

市市

(=

)

4=

#

(3)輸入串(a,(a,a))#的算符優(yōu)先分析過程為:

當(dāng)前

棧剩余輸入串動作

字符

##(#(a#(a,a,(a,a))#MoveinMove

(N#(N,#(,(,(a,a))#inReduce:S一

N,(#(N,(aa,(a,a))#aMove

#(N,(N#(N,,a(a,a))#inMove

(N,#(N,(N,))a,a))#inMove

a#(N,(N,N)),a))#inReduce:S—

#(N,(N#())a))#aMove

N,(N)#(N,##a))#inMove

N#(N#(N))#)#)#)#inReduce:S-*

)#N###aReduce:T一

T,SMove

inReduce:S一

(T)Reduce:T一

T,SMove

inReduce:S一

(T)

第六章

例1:有文法;：S—(L)|aL—L,S|S

給此文法配上語義動作子程序（或者說為此文法寫一個語法制導(dǎo)

定義），它輸出配對括號的個數(shù)。如對于句子（a,（a,a））,輸出是2。

解：加入新開始符號S'和產(chǎn)生式S'-S,設(shè)num為綜合屬性，代表值

屬性，則語法制導(dǎo)定義如下：

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

S'-Sprint(S.num)

S-(L)S.num:=L.num+l

S—aS.num:=0

L-*L1,SL.num:=Ll.num+S.num

L-*SL.num:=S.num

例2：構(gòu)造屬性文法，能對下面的文法，只利用綜合屬性獲得類型信

息。

D-*L,id|LL-TidT->int|real

解：屬性文法（語法制導(dǎo)）定義：

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

D-L,idD.type:=L.type

addtype(id.entry,L.type)

D—LD.type:=L.type

L-TidL.type:=T.type

addtype(id.entry,T.type)

T-intT.type:=integer

T—realT.type:=real

第七章

例1：給出下面表達式的逆波蘭表示(后綴式)：

(1)a*(-b+c)

(2)if(x+y)*z=Othens:=(a+b)*celses:=a*b*c

解：

(1)ab-c+*

(2)xy+z*O=sab+c*:=sab*c*:=￥

(注：￥表示if-then-else運算)

例2：請將表達式-(a+b)*(c+d)-(a+b)分別表示成三元式、間接三元式

和四元式序列。

解：

三元式間接三元式

(1)(+a,b)間接三元式序列間

接碼表

(2)(+c,d)(1)(+a,b)(1)

(3)(*(1),(2))(2)(+c,d)(2)

(4)(-(3),/)(3)(*(1),(2))(3)

(5)(+a,b)(4)(-(3),/)(4)

(6)(-(4),(5))(5)(-(4),(1))(1)

(5)

四元式

(1)(+,a,b,tl)(2)(+,c,d,t2)

(3)(*,tl,t2,t3)(4)(-,t3,/,t4)

(5)(+,a,b,t5)(6)(-,t4,t5,t6)

例3：請將下列語句

while(A<B)doif(OD)thenX:=Y+Z

翻譯成四元式

解：

假定翻譯的四元式序列從(100)開始：

(100)ifA<Bgoto(102)

(101)goto(107)

(102)ifODgoto(104)

(103)goto(100)

(104)T：=Y+Z

(105)X：=T

(106)goto(100)

(107)

例4：寫出for語句的翻譯方案

解:

產(chǎn)生式動作

SfforEdoSIS.begin:=newlabel

S.first:=newtemp

S.last:=newtemp

S.curr:=newtemp

S.code:=gen(S.firstE.init)

||gen(S.lastE.final)

||gen(“if”S.first“>”S.last“goto”S.next)

||gen(S.currS.first)

||gen(S.begin":")

||gen(“if”S.curr“>"S.Last“goto”

S.next)

||Sl.code

||gen(S.curr:=succ(S.curr))

||gen(“goto"S.begin)

E一v:=initialtofinalE.init:=initial.place

E.final:=final.place

第八章

例1：C語言中規(guī)定變量標(biāo)識符的定義可分為extern,externstatic,auto,

localstatic和register五種存儲類:

(1)對五種存儲類所定義的每種變量，分別說明其作用域。

⑵試給出適合上述存儲類變量的內(nèi)存分配方式。

(3)符號表中登記的存儲類屬性，在編譯過程中支持什么樣的語義檢

查。

解：

(1)extern定義的變量，其作用域是整個C語言程序。

externstatic定義的變量，其作用域是該定義所在的C程序文件。

auto定義的變量，其作用域是該定義所在的例程。

localstatic定義的變量，其作用域是該定義所在的例程。且在退

出該例程時，該變量的值仍保留。

register定義的變量，其作用域與auto定義的變量一樣。這種變

量的值，在寄存器有條件時，可存放在寄存器中，以提高運行效率。

⑵對extern變量，設(shè)置一個全局的靜態(tài)公共區(qū)進行分配。

對externstatic變量，為每個C程序文件，分別設(shè)置一個局部靜

態(tài)公共區(qū)進行分配。

對auto和register變量，設(shè)定它們在該例程的動態(tài)區(qū)中的相對區(qū)

頭的位移量。而例程動態(tài)區(qū)在運行時再做動態(tài)分配。

對localstatic變量，為每個具有這類定義的例程，分別設(shè)置一個

內(nèi)部靜態(tài)區(qū)進行分配。

(3)實施標(biāo)識符變量重復(fù)定義合法性檢查，及引用變量的作用域范圍

的合法性檢查。

第九章

例1：下面的程序執(zhí)行時，輸出的a分別是什么？若參數(shù)的傳遞辦法

分別為(1)傳名；(2)傳地址；(3)得結(jié)果；4)傳值。

programmain(input,output);

procedurep(x,y,z);

begin

y:=y+l;

Z:=z+x;

end;

begin

a:=2;

b:=3;

p(a+b,a,a);

printa

end.

解：

⑴參數(shù)的傳遞辦法為“傳名”時，a為9。

(2)參數(shù)的傳遞辦法為“傳地址”，a為8。

(3)參數(shù)的傳遞辦法為“得結(jié)果”，a為7o

(4)參數(shù)的傳遞辦法為“傳值”，a為2。

例2：過程參數(shù)的傳遞方式有幾種？簡述“傳地址”和“傳值”的實現(xiàn)原

理。

解：

參數(shù)的傳遞方式有下述幾種：傳值，傳地址，傳名，得結(jié)果

“傳值”方式，這是最簡單的參數(shù)傳遞方法。即將實參計算出它的值，

然后把它傳給被調(diào)過程。具體來講是這樣的：

1.形式參數(shù)當(dāng)作過程的局部變量處理，即在被調(diào)過程的活動記錄中開

辟了形參的存儲空間，這些存儲位置即是我們所說的實參或形式單

yL?

2.調(diào)用過程計算實參的值，并將它們的右值(r-value)放在為形式單

元開辟的空間中。

3.被調(diào)用過程執(zhí)行時，就像使用局部變量一樣使用這些形式單元。

“傳地址”方式，也稱作傳地址，或引用調(diào)用。調(diào)用過程傳給被調(diào)過程

的是指針，指向?qū)崊⒋鎯ξ恢玫闹羔槨?/p>

1.如實參是一個名字或是具有左值的表達式，則左值本身傳遞過去。

2.如實參是一個表達式，比方a+b或2,而沒有左值，則表達式先求

值，并存入某一位置，然后該位置的地址傳遞過去。

3.被調(diào)過程中對形式參數(shù)的任何引用和賦值都通過傳遞到被調(diào)過程

的指針被處理成間接訪問。

例3：下面是一個Pascal程序

programPP(input,output)

varK:integer;

functionF(N:integer)integer

begin

ifN<=0thenF:=l

elseF:=N*F(N-l);

end;

begin

K:=F(10);

end;

當(dāng)?shù)诙?遞歸地)進入F后，DISPLAY的內(nèi)容是什么？當(dāng)時整個

運行棧的內(nèi)容是什么？

解：

第十章

例1:何謂代碼優(yōu)化？進行優(yōu)化所需要的基礎(chǔ)是什么？

解：

對代碼進行等價變換，使得變換后的代碼運行結(jié)果與變換前代碼運行

結(jié)果相同，而運行速度加快或占用存儲空間減少，或兩者都有。

優(yōu)化所需要的基礎(chǔ)是在中間代碼生成之后或目標(biāo)代碼生成之后。

例2：編譯過程中可進行的優(yōu)化如何分類？最常用的代碼優(yōu)化技術(shù)有

哪些？

解：

依據(jù)優(yōu)化所涉及的程序范圍，可以分為：局部優(yōu)化、循環(huán)優(yōu)化和全局

優(yōu)化。

最常用的代碼優(yōu)化技術(shù)有

1.刪除多余運算2.代碼外提3.強度削弱4.變換循環(huán)控制條件5.合

并已知量與復(fù)寫傳播6.刪除無用賦值

例3：試對以下基本塊B2：

B：=3D：=A+C

E：=A*CF：=D+E

G：=B*FH：=A+C

I：=A*CJ：=H+I

K：=B*5L：=K+J

M：=L

應(yīng)用DAG對它們進行優(yōu)化，并就以下兩種情況分別寫出優(yōu)化后的四

元式序列:

（1）假設(shè)只有G、L、M在基本塊后面還要被引用。

（2）假設(shè)只有L在基本塊后面還要被引用。

解：

基本塊對應(yīng)的DAG如下

B：=3D：=A+C

E：=A*CF：=D+E

G：=B*FH：=A+C

I：=A*CJ：=H+I

K：=B*5L：=K+J

M：=L

例1一個編譯程序的代碼生成要著重考慮哪些問題?

解：

代碼生成器的設(shè)計要著重考慮目標(biāo)代碼的質(zhì)量問題，而衡量目標(biāo)代碼

的質(zhì)量主要從占用空間和執(zhí)行效率兩個方面綜合考慮。

課后習(xí)題答案：

P36-6

(1)

L(G|)是0?9組成的數(shù)字串

(2)最左推導(dǎo)：

NnNDnNDDnNDDDnDDDDnODDDn01DDn012。n0127

NnND=DD=3Dn34

NnND=NDDnDDD=>5DDn56Dn568

最右推導(dǎo)：

NnNDnN7nND!nN27nND21nN127nD127n0127

NnNDnN4nD4n34

NnNDnN8nND8nN68n068n568

P36-8

文法：

E^T\E+T\E-T

TfF[T*F]T/F

F^(E)\i

最左推導(dǎo)：

EnTnT*FnF*Fni*Fni*(E)=i*(E+T)ni*(T+T)ni*(F+T)

n，*(，+T)n，*(，+尸)=>%*(，+，)

最右推導(dǎo)：

石nE+TnE+T*尸nE+T*inE+尸*，nE+i*2nT+i*inF+i*ini+i*i

EnT=>F*T=>F*W=>F*(E)=>F*(E+T)n/*(E+W)=>F*(E+i)

=>R*(T+i)nF*(F+i)n尸*。+i)n，*(，+?)

*/********************************

句子iiiei有兩個語法樹：

SniSeSniSeiniiSeiniiiei

S=iS=USeSniiSeiniiiei

P64-7

1

確定化：

01

{X}6{1,2,3}

4)小小

{1,2,3){2,3}{2,3,4}

{2,3}{2,3}{2,3,4}

{2,3,4){2,3,5}{2,3,4)

{2,3,5}{253}{2,3,4,Y}

(2,3,4,Y){2,3,5}{2,3,4)

最小化：

{0,123,4,5},{6}

{0,123,4,5}0={1,3,5}{0,123,4,5}1={1,2,4,6)

{0,1,2,3,4},⑸,{6}

{0,123,4}0={1,3,5}

(0,1,2,3},{4},{5},{6}

{0,1,2,3}。={1,3}{0,1,2,3}1={1,2,4}

{0,1},{2,3}{4},{5},{6}

{0,1}0={1}{0,%={1,2}

{2,3}。={3}{2,3}]={4}

{0},{1},{2,3},{4},{5},{6}

確定化:

ab

{0}{051}{1}

{0,1}{051}{1}

{1}{0}小

小小

給狀態(tài)編號:

ab

012

112

203

333

最小化：

{0,1},{2,3}

{0,1}“={1}{0,1}^={2}

{2,3}.={0,3}{2,%={3}

{0,1},{2},{3}

a

b

(b)

aa

已經(jīng)確定化了，進行最小化

最小化：

{{011},{2,3,4,5))

{0,1}“={1}{0,1}*={2,4}

{2,3,4,5}0={1,3,0,5}{2,3,4,5}〃={2,3,4,5}

{2,4}“={1,0}{2,4}〃={3,。

{3,5}“={3,5}{3,5}〃={2,4}

{{0,1},{2,4},{3,5})

{0,1}〃={1}{0,1}〃={2,4}

{2,4}°={1,0}{2,41={3,5}

{3,5}“={3,5}{3,5}〃={2,4}

a

P81-1

(1)按照T,S的順序消除左遞歸

G，(S)

Sfa|，(T)

T—ST'

rsr\s

遞歸子程序：

procedureS;

begin

ifsym='a'orsym='A'

thenabvance

elseifsym='('

thenbegin

advance;T;

ifsym=')'thenadvance;

elseerror;

end

elseerror

end;

procedureT;

begin

s；r

end;

procedureT；

begin

ifsym=','

thenbegin

advance;

s；r

end

end;

其中：

sym:是輸入串指針I(yè)P所指的符號

advance:是把IP調(diào)至下一個輸入符號

error:是出錯診察程序

(2)

FIRST(S尸{a,人,(}

FIRST(T)={aJ,(}

FIRST(T)={,,￡}

FOLLOW(S)={),?#}

FOLLOW(T>{)}

FOLLOW。』）｝

預(yù)測分析表

A

a()9#

sS—》aSf(T)

TTfSTTfSTTTST

TTT’fST

是LL(1)文法

P81-2

文法：

——?丁JE2,

石,—+石|w

丁—?尸丁,

丁,—丁Iw

尸—?—，

尸，—‘尸'|?

廣一《石)||上—

(1)

FIRST(E尸{(,a,bj}

FIRST(E>{+,E}

FIRST(T)={(,a,b「}

FIRST(T,)={(,a,b,A,e}

FIRST(F>{(,a,b?}

FIRST(F>{*,E}

FIRST(P>{(,a,b?}

FOLLOW(E>{#,)}

FOLLOW(E')={#,)}

FOLLOW(T>{+,),#}

FOLLOW(T')={+,),#}

FOLLOW(F>{(,a,b?,+,),#}

FOLLOWS尸{(,a,b,人,+,),#}

FOLLOW(P)={*,(,a,b,A,+,),#}

(2)

考慮下列產(chǎn)生式：

E'^+E\s

T'^T\s

F'^*F'\s

P^(ET\a\b

FIRST(+E)nFIRST(￡)={+}n{￡}=6

FIRST(+E)nFOLLOW(E')={+}n{#,)}=e

FIRST(T)nFIRST(e)={(,a,b,A}n{￡}=6

FIRST(T)AFOLLOW(T')={(,a,b,A}A{+,),#}=4)

FIRST(*F')nFIRST(￡)={*}n{￡}=6

FIRST(*F')AFOLLOW(F)={*}A{(,a,b,A,+,),#}=1

FIRST((E))nFIRST(a)AFIRST(b)AFIRST(人)=小

所以，該文法式LL(1)文法.

(3)

+*()abA#

EEfTE，EfTE，EfTE，EfTE，

E'EJ+EE

TTfFTTfFTT—FTTfFT

T'TTBTfTTTfTTflTfTT

FFfPFFfPF，F(xiàn)fPFFfPF

F'F'prf*尸F(xiàn)'F'尸—￡尸—￡尸一￡F'

PfA

P尸■(￡)P告aPfb

(4)

procedureE;

begin

ifsym='('orsym='a'orsym='b'orsym='人'

thenbeginT;E'end

elseerror

end

procedureE';

begin

ifsym='+'

thenbeginadvance;Eend

elseifsym<>')'andsym<>'#'thenerror

end

procedureT;

begin

ifsym='('orsym='a'orsym='b'orsym='A'

thenbeginF;T'end

elseerror

end

procedureT';

begin

ifsym='('orsym='a'orsym='b'orsym='A，

thenT

elseifsym='*'thenerror

end

procedureF;

begin

ifsym='('orsym='a'orsym='b'orsym='A'

thenbeginP;F'end

elseerror

end

procedureF';

begin

ifsym='*'

thenbeginadvance;F'end

end

procedureP;

begin

ifsym='a'orsym='b'orsym='A'

thenadvance

elseifsym='('then

begin

advance;E;

ifsym=')'thenadvance

elseerror

end

elseerror

end;

P133-1

EnE+TnE+T*F

短語：E+T*F,T*F,

直接短語:T*F

句柄:T*F

P133-2

文法：

Sf。國⑺

TfT,S\S

(1)最左推導(dǎo)：

S=>(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,a))

S=>(T,S)=>(S,S)0((T),S)=>((T,S),S)=>((T,S,S),S)=>((S,S,S),S)=>(((T),S,S),S)

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

=>(((a,a)/,S),S)n(((a,a)「,(T)),S)n(((a,a)J,(S)),S)n(((a,a)J,(a)),S)

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

最右推導(dǎo)：

Sn(T)n(T,S)n(T,(T))n(T,(T,S))n(T,(T,a))n(T,(S,a))n(T,(a,a))

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

Sn(T,S)n(T,a)n(S,“)n((T),a)=>((T,S),a)n((T,(T)),a)n((T,(S)),a)

=>((T,(a)),a)n((T,S,(a)),a)n((T,3(a)),a)n((S,',(a)),a)n(((T),A,(?)),?)

n(((T,S),A,(a)),a)n(((T,a),A,(a)),a)n(((SM),3(a)),a)=>(((a,a),A,(a)),a)

(2)

(((a,a),A,(a)),a)

((⑤a),人,(a)),a)

(((T,a)?,(a)),a)

(((LS),A,(a)),a)

((皿,⑶),a)

((S,A,(a)),a)

((D,(a)),a)

((XS,(a)),a)

((T,(a)),a)

((T,(S)),a)

(。,①),a)

((XS),a)

?Tl，a)

(S,a)

心)

(T)

S

“移進-歸約”過程:

步驟棧輸入串動作

0#(((a,a),A,(a)),a)#預(yù)備

1#(((a,a),A,(a)),a)#進

2#(((a,a),A,(a)),a)#進

3#(((a,a),A,(a)),a)#進

4#(((a,a),A,(a)),a)#進

5#(((S,a),A,(a)),a)#歸

6#(((T,a),A,(a)),a)#歸

7#(((T,a),人,(a)),a)#進

8#(((T,a),A,(a)),a)#進

9#(((T,S),A,(a)),a)#歸

10#(((T)C(a)),a)#歸

11#(((T),A,(a)),a)#進

12#((S,A,(a)),a)#歸

13#((T,A,(a)),a)#歸

14#((T,人,(a)),a)#進

15#((T6，⑶),a)#進

16#((T,S,(a)),a)#歸

17#((T,(a)),a)#歸

18#((T,(a)),a)#進

19#((T,(a)),a)#進

20#((T,(a)),a)#進

21#((T,(S)),a)#歸

22#((T,(T)),a)#歸

23#((T,(T)),a)#進

24#((T,S),a)#歸

25#((T),a)#歸

26#((T),a)#進

27#(S,a)#歸

28#(T,a)#歸

29#(T,a)#進

30#(T,a)#進

31#(T,S)#歸

32#(T)#歸

33#(T)#進

34#S#歸

P133-3

(l)FIRSTVT(S)={a,A,(}

FIRSTVT(T)={?a,A,(}

LASTVT(S)={a,A,)}

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

(2)

aA()

a>>

A>>

(<<<=<

)>>

<<<>>

G6是算符文法，并且是算符優(yōu)先文法

⑶優(yōu)先函數(shù)

aA()

f44244

g55523

(4)

棧輸入字符串動作

#(a,(a,a))#預(yù)備

#(a,(a,a))#進

#(a,(a,a))#進

#(s,(a,a))#歸

#(t,(a,a))#歸

#(t,(a,a))#進

#(t,(a,a))#進

#(t,(a,a))#進

#(t,(s,a))#歸

#(t,(t,a))#歸

#(t,(t,a))#進

#(t,(t,a))#進

#(t,(t,s))#歸

#(t,(t))#歸

#(t,(t))#進

#(t,s)#歸

#(t)#歸

#(t)#進

#s#歸

P164-1

答：表達式(4*7+1)*2的附注語法樹如下圖:

diQit.lexval

+Rv分1二1

Tval=1

T.val=4*Fval=7

Fvnl=1

Pl64-2

答:

⑴

⑵

P165-11

答：(1)D-idL{D.type:=L