編譯原理題庫(kù)

第一章什么是編譯器？編譯程序的結(jié)構(gòu)分為幾個(gè)階段，各階段的任務(wù)是什么？遍、編譯前端及編譯后端的含義？編譯程序的生成方式有哪些？第二章1.寫一文法，使其語(yǔ)言是偶正整數(shù)的集合。要求：（1）允許0打頭（2）不允許0打頭解：（1）允許0開頭的偶正整數(shù)集合的文法E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8（2）不允許0開頭的偶正整數(shù)集合的文法E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|02.證明下述文法G［〈表達(dá)式〉］是二義的。〈表達(dá)式〉∷=a|(〈表達(dá)式〉)|〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉〈運(yùn)算符〉∷=+|-|*|/解：可為句子a+a*a構(gòu)造兩個(gè)不同的最右推導(dǎo):最右推導(dǎo)1〈表達(dá)式〉〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉〈表達(dá)式〉〈運(yùn)算符〉a〈表達(dá)式〉*a〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉*a〈表達(dá)式〉〈運(yùn)算符〉a*a〈表達(dá)式〉+a*aa+a*a最右推導(dǎo)2〈表達(dá)式〉〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉〈運(yùn)算符〉a〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉*a〈表達(dá)式〉〈運(yùn)算符〉a*a〈表達(dá)式〉+a*aa+a*a3.給出生成下述語(yǔ)言的上下文無(wú)關(guān)文法：（1）{anbnambm|n，m>=0}（2）{1n0m1m0n|n，m>=0}解：（1）{anbnambm|n，m>=0}S→AAA→aAb|ε(2){1n0m1m0n|n，m>=0}S→1S0|AA→0A1|ε第三章1、構(gòu)造一個(gè)DFA，它接收∑={a,b}上所有滿足下述條件的字符串：字符串中的每個(gè)a都有至少一個(gè)b直接跟在其右邊。解：已知∑={a,b}，根據(jù)題意得出相應(yīng)的的正規(guī)式為：(b*abb*)*根據(jù)正規(guī)式畫出相應(yīng)的DFAM，如下圖所示用子集法將其確定化XY(b*abb*)*XY(b*abb*)*XYb*abb*1XYb123456bbaIIaIb{X,1,2,3,Y}{4}{2,3}{4}—{5,6,1,2,3,Y}{2,3}{4}{2,3}{4}{6,1,2,3,Y}{5,6,1,2,3,Y}{6,1,2,3,Y}{4}{6,1,2,3,Y}IIaIb0121—3212314414由DFA得狀態(tài)圖用最小化方法化簡(jiǎn)得：{0}，{1}，{2}，{3,4}，按順序重新命名DFAM’10210243aaaabbbbb0312aaabbb練習(xí)1：文法G[V]：V→N|N[E]E→V|V+EN→i是否為L(zhǎng)L(1)文法，如不是，如何將其改造成LL(1)文法。解：LL(1)文法的基本條件是不含左遞歸和回溯（公共左因子），而G[V]中含有回溯，所以先消除回溯得到文法G’[V]：G’[V]：V→NV’V’→ε|[E]E→VE’E’→ε|+EN→i由LL(1)文法的充要條件可證G’[V]是LL(1)文法練習(xí)2：有文法G[s]:S→BAA→BS|dB→aA|bS|c(1)證明文法G是LL(1)文法。(2)構(gòu)造LL(1)分析表。(3)寫出句子adccd的分析過(guò)程解：(1)一個(gè)LL(1)文法的充要條件是：對(duì)每一個(gè)非終結(jié)符A的任何兩個(gè)不同產(chǎn)生式A→α|β，有下面的條件成立：①FIRST(α)∩FIRST(β)=Φ;②若β*ε,則有FIRST(α)∩FOLLOW(A)=Φ對(duì)于文法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}。其FOLLOW集如下：首先，F(xiàn)OLLOW(S)={#};對(duì)S→BA有：FIRST(A)\{ε}加入FOLLOW(B),即FOLLOW(B)={a,b,c,d};對(duì)A→BS有：FIRST(S)\{ε}加入FOLLOW(B),即FOLLOW(B)={a,b,c,d};對(duì)B→aA有：FOLLOW(B)加入FOLLOW(A),即FOLLOW(A)={a,b,c,d};對(duì)B→bS有：FOLLOW(B)加入FOLLOW(S),即FOLLOW(S)={#,a,b,c,d};由A→BS|d得：FIRST(BS)∩FIRST(d)={a,b,c}∩8qcsi2i=Φ;由B→aA|bS|c得：FIRST(aA)∩FIRST(bS)∩FIRST(c)={a}∩∩{c}=Φ。由于文法G[s]不存在形如β→ε的產(chǎn)生式，故無(wú)需求解形如FIRST(α)∩FOLLOW(A)的值。也即，文法G[S]是一個(gè)LL(1)文法。(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}。FOLLOW(S)={#,a,b,c,d}可構(gòu)造LL(1)預(yù)測(cè)分析表如下：

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的分析過(guò)程如下：第五章1已知文法G[S]為：

S→a|∧|(T)T→T,S|S(1)計(jì)算G[S]的FIRSTVT和LASTVT。(2)構(gòu)造G[S]的算符優(yōu)先關(guān)系表并說(shuō)明G[S]是否為算符優(yōu)先文法。(3)給出輸入串(a,(a,a))#的算符優(yōu)先分析過(guò)程。解：文法：

S→a|∧|(T)T→T,S|S展開為：

S→aS→∧S→(T)

T→T,ST→S(1)FIRSTVT--LASTVT表非終結(jié)符FIRSTVT集LASTVT集S{a∧(}{a∧)}T{a∧(,}{a∧),}(2)算符優(yōu)先關(guān)系表如下:表中無(wú)多重入口所以是算符優(yōu)先（OPG）文法。

a∧(),#a

∧

≮≮≮≯≯≯≯()

,#≮

≮≮

≮≮

≮≒≯≯≯≯≮≯≯≯≒(3)輸入串（a,(a,a)）#的算符優(yōu)先分析過(guò)程為：棧當(dāng)前字符剩余輸入串動(dòng)作#

#(

#(a

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

a,a))#

,a))#

a))#

a))#Movein

Movein

Reduce:S→a

Movein

Movein

Movein

Reduce:S→a

Movein

Move#(N

#(N,

#(N,(

#(N,(a

#(N,(N

#(N,(N,

#(N,(N,a

#(N,(N,N

#(N,(N

#(N,(N)

#(N,N

#(N

#(N)

#N(

a

,

,

(

a

,

,

a

)

)

)

)

)

)

#

#))#

)#

)#

)#

#

#

#in

Reduce:S→a

Reduce:T→T,S

Movein

Reduce:S→(T)

Reduce:T→T,S

Movein

Reduce:S→(T)第六章例1：有文法：S→(L)|aL→L,S|S給此文法配上語(yǔ)義動(dòng)作子程序(或者說(shuō)為此文法寫一個(gè)語(yǔ)法制導(dǎo)定義)，它輸出配對(duì)括號(hào)的個(gè)數(shù)。如對(duì)于句子(a,(a,a))，輸出是2。解：加入新開始符號(hào)S'和產(chǎn)生式S'→S，設(shè)num為綜合屬性，代表值屬性，則語(yǔ)法制導(dǎo)定義如下：產(chǎn)生式語(yǔ)義規(guī)則S'→Sprint(S.num)S→(L)S.num:=L.num+1S→aS.num:=0L→L1,SL.num:=L1.num+S.numL→SL.num:=S.num例2：構(gòu)造屬性文法，能對(duì)下面的文法，只利用綜合屬性獲得類型信息。D→L,id|LL→TidT→int|real解：屬性文法（語(yǔ)法制導(dǎo)）定義：產(chǎn)生式語(yǔ)義規(guī)則D→L,idD.type:=L.typeaddtype(id.entry,L.type)D→LD.type:=L.typeL→TidL.type:=T.typeaddtype(id.entry,T.type)T→intT.type:=integerT→realT.type:=real第七章例1：給出下面表達(dá)式的逆波蘭表示(后綴式)：(1)a*(-b+c)(2)if(x+y)*z=0thens:=(a+b)*celses:=a*b*c解：(1)ab-c+*(2)xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示if-then-else運(yùn)算）例2：請(qǐng)將表達(dá)式-(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,t1)(2)(+,c,d,t2)(3)(*,t1,t2,t3)(4)(-,t3,/,t4)(5)(+,a,b,t5)(6)(-,t4,t5,t6)例3：請(qǐng)將下列語(yǔ)句while(A<B)doif(C>D)thenX:=Y+Z翻譯成四元式解：假定翻譯的四元式序列從（100）開始：（100）ifA<Bgoto（102）（101）goto（107）（102）ifC>Dgoto（104）（103）goto（100）（104）T∶=Y+Z（105）X∶=T（106）goto（100）（107）例4：寫出for語(yǔ)句的翻譯方案解：產(chǎn)生式動(dòng)作S→forEdoS1S.begin:=newlabelS.first:=newtempS.last:=newtempS.curr:=newtempS.code:=gen(S.first“:=”E.init)||gen(S.last“:=”E.final)||gen(“if”S.first“>”S.last“goto”S.next)||gen(S.curr“:=”S.first)||gen(S.begin“:”)||gen(“if”S.curr“>”S.Last“goto”S.next)||S1.code||gen(S.curr:=succ(S.curr))||gen(“goto”S.begin)E→v:=initialtofinalE.init:=initial.placeE.final:=final.place第八章例1：C語(yǔ)言中規(guī)定變量標(biāo)識(shí)符的定義可分為extern,externstatic,auto,localstatic和register五種存儲(chǔ)類：(1)對(duì)五種存儲(chǔ)類所定義的每種變量，分別說(shuō)明其作用域。(2)試給出適合上述存儲(chǔ)類變量的內(nèi)存分配方式。(3)符號(hào)表中登記的存儲(chǔ)類屬性，在編譯過(guò)程中支持什么樣的語(yǔ)義檢查。解：(1)extern定義的變量，其作用域是整個(gè)C語(yǔ)言程序。externstatic定義的變量，其作用域是該定義所在的C程序文件。auto定義的變量，其作用域是該定義所在的例程。localstatic定義的變量，其作用域是該定義所在的例程。且在退出該例程時(shí)，該變量的值仍保留。register定義的變量，其作用域與auto定義的變量一樣。這種變量的值，在寄存器有條件時(shí)，可存放在寄存器中，以提高運(yùn)行效率。(2)對(duì)extern變量，設(shè)置一個(gè)全局的靜態(tài)公共區(qū)進(jìn)行分配。對(duì)externstatic變量，為每個(gè)C程序文件，分別設(shè)置一個(gè)局部靜態(tài)公共區(qū)進(jìn)行分配。對(duì)auto和register變量，設(shè)定它們?cè)谠摾痰膭?dòng)態(tài)區(qū)中的相對(duì)區(qū)頭的位移量。而例程動(dòng)態(tài)區(qū)在運(yùn)行時(shí)再做動(dòng)態(tài)分配。對(duì)localstatic變量，為每個(gè)具有這類定義的例程，分別設(shè)置一個(gè)內(nèi)部靜態(tài)區(qū)進(jìn)行分配。(3)實(shí)施標(biāo)識(shí)符變量重復(fù)定義合法性檢查，及引用變量的作用域范圍的合法性檢查。第九章例1：下面的程序執(zhí)行時(shí)，輸出的a分別是什么？若參數(shù)的傳遞辦法分別為(1)傳名；(2)傳地址；(3)得結(jié)果；4)傳值。

programmain(input,output);

procedurep(x,y,z);

begin

y∶=y+1;

z∶=z+x;

end;

begin

a∶=2;

b∶=3;

p(a+b,a,a);

printa

end.解：(1)參數(shù)的傳遞辦法為“傳名”時(shí)，a為9。(2)參數(shù)的傳遞辦法為“傳地址”，a為8。(3)參數(shù)的傳遞辦法為“得結(jié)果”，a為7。(4)參數(shù)的傳遞辦法為“傳值”，a為2。例2：過(guò)程參數(shù)的傳遞方式有幾種？簡(jiǎn)述“傳地址”和“傳值”的實(shí)現(xiàn)原理。解：參數(shù)的傳遞方式有下述幾種：傳值，傳地址，傳名，得結(jié)果“傳值”方式，這是最簡(jiǎn)單的參數(shù)傳遞方法。即將實(shí)參計(jì)算出它的值，然后把它傳給被調(diào)過(guò)程。具體來(lái)講是這樣的：1.形式參數(shù)當(dāng)作過(guò)程的局部變量處理，即在被調(diào)過(guò)程的活動(dòng)記錄中開辟了形參的存儲(chǔ)空間，這些存儲(chǔ)位置即是我們所說(shuō)的實(shí)參或形式單元。2.調(diào)用過(guò)程計(jì)算實(shí)參的值，并將它們的右值（r-value）放在為形式單元開辟的空間中。3.被調(diào)用過(guò)程執(zhí)行時(shí)，就像使用局部變量一樣使用這些形式單元?！皞鞯刂贰狈绞剑卜Q作傳地址，或引用調(diào)用。調(diào)用過(guò)程傳給被調(diào)過(guò)程的是指針，指向?qū)崊⒋鎯?chǔ)位置的指針。1.如實(shí)參是一個(gè)名字或是具有左值的表達(dá)式，則左值本身傳遞過(guò)去。2.如實(shí)參是一個(gè)表達(dá)式，比方a+b或2，而沒(méi)有左值，則表達(dá)式先求值，并存入某一位置，然后該位置的地址傳遞過(guò)去。3.被調(diào)過(guò)程中對(duì)形式參數(shù)的任何引用和賦值都通過(guò)傳遞到被調(diào)過(guò)程的指針被處理成間接訪問(wèn)。例3：下面是一個(gè)Pascal程序

programPP(input,output)

varK:integer;

functionF(N:integer):integer

begin

ifN<=0thenF:=1

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

end;

begin

K:=F(10);

...

end;

當(dāng)?shù)诙危ㄟf歸地）進(jìn)入F后，DISPLAY的內(nèi)容是什么？當(dāng)時(shí)整個(gè)運(yùn)行棧的內(nèi)容是什么？解：第十章例1：何謂代碼優(yōu)化？進(jìn)行優(yōu)化所需要的基礎(chǔ)是什么？解：對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同，而運(yùn)行速度加快或占用存儲(chǔ)空間減少，或兩者都有。優(yōu)化所需要的基礎(chǔ)是在中間代碼生成之后或目標(biāo)代碼生成之后。例2：編譯過(guò)程中可進(jìn)行的優(yōu)化如何分類？最常用的代碼優(yōu)化技術(shù)有哪些？解：依據(jù)優(yōu)化所涉及的程序范圍，可以分為：局部?jī)?yōu)化、循環(huán)優(yōu)化和全局優(yōu)化。最常用的代碼優(yōu)化技術(shù)有1.刪除多余運(yùn)算2.代碼外提3.強(qiáng)度削弱4.變換循環(huán)控制條件5.合并已知量與復(fù)寫傳播6.刪除無(wú)用賦值例3：試對(duì)以下基本塊B2：B：=3D：=A+CE：=A*CF：=D+EG：=B*FH：=A+CI：=A*CJ：=H+IK：=B*5L：=K+JM：=L應(yīng)用DAG對(duì)它們進(jìn)行優(yōu)化，并就以下兩種情況分別寫出優(yōu)化后的四元式序列：（1）假設(shè)只有G、L、M在基本塊后面還要被引用。（2）假設(shè)只有L在基本塊后面還要被引用。解：基本塊對(duì)應(yīng)的DAG如下：B：=3D：=A+CE：=A*CF：=D+EG：=B*FH：=A+CI：=A*CJ：=H+IK：=B*5L：=K+JM：=L例1一個(gè)編譯程序的代碼生成要著重考慮哪些問(wèn)題?解：代碼生成器的設(shè)計(jì)要著重考慮目標(biāo)代碼的質(zhì)量問(wèn)題，而衡量目標(biāo)代碼的質(zhì)量主要從占用空間和執(zhí)行效率兩個(gè)方面綜合考慮。課后習(xí)題答案：P36-6(1)是0~9組成的數(shù)字串(2)最左推導(dǎo):最右推導(dǎo):P36-8文法：最左推導(dǎo):最右推導(dǎo):語(yǔ)法樹：/********************************P36-9句子iiiei有兩個(gè)語(yǔ)法樹：P64–7(1)XYX1XYX1234Y511011確定化：01{X}φ{(diào)1,2,3}φφφ{(diào)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}{2,3}{2,3,4,Y}{2,3,4,Y}{2,3,5}{2,3,4}0320103201001101654016540111最小化：002110010021543015430111P64–12(a)a10a,b10a確定化：ab{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}φφφφ給狀態(tài)編號(hào)：ab012112203333a10a10abbb32b32a最小化：aa210bb210ab(b)032bba032abaab541ba541aa已經(jīng)確定化了,進(jìn)行最小化最小化：021bba021abaP81–1(1)按照T,S的順序消除左遞歸遞歸子程序：procedureS;begin ifsym='a'orsym='^' thenabvance elseifsym='(' thenbegin advance;T; ifsym=')'thenadvance; elseerror; end elseerrorend;procedureT;begin S;end;procedure;begin ifsym=',' thenbegin advance; S; endend;其中:sym:是輸入串指針I(yè)P所指的符號(hào)advance:是把IP調(diào)至下一個(gè)輸入符號(hào)error:是出錯(cuò)診察程序(2)FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST()={,,}FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW()={)}預(yù)測(cè)分析表a^(),#ST是LL(1)文法P81–2文法：(1)FIRST(E)={(,a,b,^}FIRST(E')={+,ε}FIRST(T)={(,a,b,^}FIRST(T')={(,a,b,^,ε}FIRST(F)={(,a,b,^}FIRST(F')={*,ε}FIRST(P)={(,a,b,^}FOLLOW(E)={#,)}FOLLOW(E')={#,)}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#}FOLLOW(F')={(,a,b,^,+,),#}FOLLOW(P)={*,(,a,b,^,+,),#}(2)考慮下列產(chǎn)生式:FIRST(+E)∩FIRST(ε)={+}∩{ε}=φFIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φFIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φFIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φFIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φFIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ所以,該文法式LL(1)文法.(3)+*()ab^#EE'TT'FF'P(4)procedureE;begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginT;E'end elseerrorendprocedureE';begin ifsym='+' thenbeginadvance;Eend elseifsym<>')'andsym<>'#'thenerrorendprocedureT;begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginF;T'end elseerrorend procedureT';begin ifsym='('orsym='a'orsym='b'orsym='^' thenT elseifsym='*'thenerrorendprocedureF;begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginP;F'end elseerrorend procedureF';begin ifsym='*' thenbeginadvance;F'endendprocedureP;begin ifsym='a'orsym='b'orsym='^' thenadvance elseifsym='('then begin advance;E; ifsym=')'thenadvance elseerror end elseerrorend;P133–1短語(yǔ):E+T*F,T*F,直接短語(yǔ):T*F句柄:T*FP133–2文法：(1)最左推導(dǎo):最右推導(dǎo):(2)(((a,a),^,(a)),a)(((S,a),^,(a)),a)(((T,a),^,(a)),a)(((T,S),^,(a)),a)(((T),^,(a)),a)((S,^,(a)),a)((T,^,(a)),a)((T,S,(a)),a)((T,(a)),a)((T,(S)),a)((T,(T)),a)((T,S),a)((T),a)(S,a)(T,S)(T)S“移進(jìn)-歸約”過(guò)程：步驟 棧 輸入串 動(dòng)作0 # (((a,a),^,(a)),a)# 預(yù)備1 #( ((a,a),^,(a)),a)# 進(jìn)2 #(( (a,a),^,(a)),a)# 進(jìn)3 #((( a,a),^,(a)),a)# 進(jìn)4 #(((a ,a),^,(a)),a)# 進(jìn)5 #(((S ,a),^,(a)),a)# 歸6 #(((T ,a),^,(a)),a)# 歸7 #(((T, a),^,(a)),a)# 進(jìn)8 #(((T,a ),^,(a)),a)#進(jìn)9 #(((T,S ),^,(a)),a)# 歸10 #(((T ),^,(a)),a)# 歸11 #(((T) ,^,(a)),a)# 進(jìn)12 #((S ,^,(a)),a)# 歸13 #((T ,^,(a)),a)# 歸14 #((T, ^,(a)),a)# 進(jìn)15 #((T,^ ,(a)),a)# 進(jìn)16 #((T,S ,(a)),a)# 歸17 #((T ,(a)),a)# 歸18 #((T, (a)),a)# 進(jìn)19 #((T,( a)),a)# 進(jìn)20 #((T,(a )),a)# 進(jìn)21 #((T,(S )),a)# 歸22 #((T,(T )),a)# 歸23 #((T,(T) ),a)# 進(jìn)24 #((T,S ),a)# 歸25 #((T ),a)# 歸26 #((T) ,a)# 進(jìn)27 #(S ,a)# 歸28 #(T ,a)# 歸29 #(T, a)# 進(jìn)30 #(T,a )# 進(jìn)31 #(T,S )# 歸32 #(T )# 歸33 #(T) # 進(jìn)34 #S # 歸P133–3(1)FIRSTVT(S)={a,^,(}FIRSTVT(T)={,,a,^,(}LASTVT(S)={a,^,)}LASTVT(T)={,,a,^,)}(2)a^(),a>>^>>(<<<=<)>>,<<<>>是算符文法，并且是算符優(yōu)先文法(3)優(yōu)先函數(shù)a^(),f44244g55523（4）棧 輸入字符串 動(dòng)作# （a,(a,a)）# 預(yù)備#( a,(a,a))# 進(jìn)#(a ,(a,a))# 進(jìn)#(s ,(a,a))# 歸#(t ,(a,a))# 歸#（t, (a,a)）# 進(jìn)#（t,（ a,a））# 進(jìn)#（t,（a ,a））# 進(jìn)#（t,（s ,a））# 歸#（t,（t ,a））# 歸#（t,（t, a））# 進(jìn)#（t,（t,a ））# 進(jìn)#（t,（t,s ））# 歸#（t,（t ））# 歸#（t,（t））# 進(jìn)#（t,s ）# 歸#（t ）# 歸#（t ） # 進(jìn)#s # 歸P164–1答：表達(dá)式（4*7+1）*2的附注語(yǔ)法樹如下圖：digit.lexval=2F.val=2Edigit.lexval=2F.val=2E.val=58ndigit.lexval=4digit.lexval=7digit.lexval=1F.val=4F.val=7F.val=1T.val=4*T.val=28E.val=28+T.val=1E.val=1E.val=29()F.val=29T.val=29T.val=58*L答：(1)abab+ab+P165ab+答：（1）D→idL {D.type:=L.type；addtype(id.type,L.type)}L→,idL1 {L.type:=L1.type；addtype(id.type,L1.type)}L→:T {L.type:=T.type}T→integer {T.type:=integer}T→real {T.type:=real}P217–1a*(-b+c) ab@c+*a+b*(c+d/e) abcde/+*+-a+b*(-c+d) a@bc@d+*+A(CornotD) AnotCD not ornot or (AandB)or(notCorD) ABandCnotDoror(AorB)and(CornotDandE) ABorCDnotEandorand if(x+y)*z=0then(a+b)↑c(diǎn)elsea↑b↑c(diǎn) xy+z*0=ab+c↑abc↑↑￥ 或xy+z*0=P1jezab+c↑P2jumpabc↑↑P1P2P217–3-(a+b)*(c+d)-(a+b+c)的三元式序列:+,a,b@,(1),-+,c,