編譯原理題庫(kù)

1、第一章?什么是編譯器？?編譯程序的結(jié)構(gòu)分為幾個(gè)階段，各階段的任務(wù)是什么？?遍、編譯前端及編譯后端的含義？?編譯程序的生成方式有哪些？第二章?1. 寫(xiě)一文法，使其語(yǔ)言是偶正整數(shù)的集合。?要求：（1）允許 0打頭 （2） 不允許 0 打頭解：（ 1）允許 0 開(kāi)頭的偶正整數(shù)集合的文法Et NT|DTt NT|DNtD|1|3|5|7|9Dt0|2|4|6|8（2）不允許 0 開(kāi)頭的偶正整數(shù)集合的文法E t NT|DT t FT|GN t D|1|3|5|7|9D t 2|4|6|8F tN|0G tD|02.證明下述文法 G表達(dá)式是二義的。表達(dá)式 =a|（表達(dá)式）| 表達(dá)式運(yùn)算符表達(dá)式運(yùn)算符：=+

2、卜|*|/解：可為句子 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|

3、n ，m>=0StAAAt aAb| e(2) 1nOmlmOn| n , m>=04 1S0|A 2 0A1| £第三章1、構(gòu)造一個(gè)DFA它接收刀=a, b上所有滿足下述條件的字符串：字符串中的每個(gè)a都有至少一個(gè)b直接跟在其右邊。解:已知刀=a, b，根據(jù)題意得出相應(yīng)的的正規(guī)式為：（b*abb*）*根據(jù)正規(guī)式畫(huà)出相應(yīng)的DFA M如下圖所示用子集法將其確定化IaIbX,1,2,3,Y42,345,6,1,2,3,Y2342,35,6,1,2,3,Y46,1,2,3,Y6,1,2,3,Y46,1,2,3,Y由DFA得狀態(tài)圖 順序重新命名DFA MIIaIb0121一3212

4、314414用最小化方法化簡(jiǎn)得：0 , 1 , 2 , 3,4,按b1a3abbbbFIRST(B)=a, b, c; FIRST(A)=a, b, c, d; FIRST(S)=a, b, c 其FOLLOW如下：首先，F(xiàn)OLLOW(S)=#;對(duì)St BA有：FIRST(A) s 加入 FOLLOW(B),即 FOLLOW(B)=a, b, c, d ;對(duì)At BS有：FIRST(S) s 加入 FOLLOW(B),即 FOLLOW(B)=a, b, c, d ;對(duì)Bt aA有：FOLLOW(B加入 FOLLOW(A),即 FOLLOW(A)=a, b, c, d ;對(duì)Bt bS有：FOLL

5、OW(B加入 FOLLOW(S),即 FOLLOW(S)=#, a, b, c, d ;練習(xí)1 :文法GV:V t N|NE e是否為L(zhǎng)L(1)文法，如不是，如何將其改造成解：LL(1)文法的基本條件是不含左遞歸和回溯(公共左因子) 除回溯得到文法 G V:G ' V :V t NVE t VE' ENt i由LL(1)文法的充要條件可證練習(xí)2:有文法 Gs:S t ba a t BS|d(1)證明文法G是LL(1)文法。 構(gòu)造LL(1)分析表。(3)寫(xiě)出句子adccd的分析過(guò)程解：(1) 一個(gè)LL(1)文法的充要條件是：對(duì)每一個(gè)非終結(jié)符 有下面的條件成立： FIRST( a

6、) A FIRST( 3 )=; 若 B *s ,則有 FIRST( a ) A FOLLOW(A)對(duì)于文法Gs:S t ba a t BS|d B t aA|bS|c其FIRST集如下：t V|V+EN t iLL(1)V ' t£ |E 't£ |+EG V是LL(1)文法B t aA|bS|c文法。，而GV中含有回溯，所以先消A的任何兩個(gè)不同產(chǎn)生式ATa |由 At BS|d 得：FIRST(BS)A FIRST(d) = a, b, c A d=;由 Bt aA|bS|c 得： FIRST(aA)A FIRST(bS) A FIRST(c) =a A

7、 b A c=。由于文法Gs不存在形如3Ts的產(chǎn)生式，故無(wú)需求解形如FIRST( a ) A FOLLOW(A的值。也即，文法 GS是一個(gè)LL(1)文法。(2)由 Gs:S t BA A t BS|d B 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#SSt BASt BASt BAAat bsAt bsat bsat dBBt

8、aABt bSBt cSSt BASt BASt BAAat bsAt bsat bsAt dBBt aABt bSBt c(3)在分析表的控制下，句子adccd的分析過(guò)程如下:棧當(dāng)前輸入符號(hào)輸入串說(shuō)明#Sadccd#St BA#ABadccd#Bt aA#AAaadccd#AAdccd#ATd#Addccd#Accd#At bs#SBccd#Btc#Scccd#Scd#St BA#ABcd#Btc#Accd#Ad#ATd#dd#分析成功第五章1已知文法GS為：St a| A |(T)TtT,S|S(1) 計(jì)算 GS的 FIRSTVT和 LASTVT(2) 構(gòu)造GS的算符優(yōu)先關(guān)系表并說(shuō)明GS是

9、否為算符優(yōu)先文法。(3) 給出輸入串(a,(a,a)#的算符優(yōu)先分析過(guò)程。解：文法：St a| A |(T) T t T,S|S展開(kāi)為：St a StASt (T)Tt T,STt S(1) FIRSTVT - LASTVT 表非終結(jié)符FIRSTVT 集LASTVT集S a A ( a A ) T a A ( , a A ) , 義如下：產(chǎn)生式語(yǔ)義規(guī)則(2)算符優(yōu)先關(guān)系表如下：表中無(wú)多重入口所以是算符優(yōu)先( OPG文法。aA()5#a>> >>A>< >>fI<<<><<<>><<

10、<>#(3)輸入串(a,(a,a) ) #的算符優(yōu)先分析過(guò)程為:棧當(dāng)前字 符剩余輸入串動(dòng)作#(a,(a,a)#Move in#(a,(a,a)#Move in#(a5(a,a)#Reduce: S t a#(N5(a,a)#Move in#(N,(a,a)#Move in#(N,(a,a)#Move in#(N,(a5a)#Reduce: S t a#(N,(N5a)#Move in#(N,(N,a)#Move in#(N,(N,a)#Reduce: S t a#(N,(N,N)#Reduce: T tT,S#(N,(N)#Move in#(N,(N)#Reduce: S t (T

11、)#(N,N)#Reduce: T tT,S#(N)#Move in#(N)#Reduce: S t (T)#N#例 1 有文法：S t (L)|a Lt L,S|S給此文法配上語(yǔ)義動(dòng)作子程序(或者說(shuō)為此文法寫(xiě)一個(gè)語(yǔ)法制導(dǎo)定義)，它輸出配對(duì)括號(hào) 的個(gè)數(shù)。如對(duì)于句子(a,(a,a)，輸出是2。解：加入新開(kāi)始符號(hào)S'和產(chǎn)生式S' t s,設(shè)num為綜合屬性，代表值屬性，則語(yǔ)法制導(dǎo)定S't sprin t(S. num)t (L) S.nu m:=L. nu m+1S.num:=OLt L1,SL.num:=L1.num+S.numLt sL. nu m:=S. num例 2

12、：構(gòu)造屬性文法，能對(duì)下面的文法，只利用綜合屬性獲得類型信息。D t L,id | L Lt T id Tt int | real解：屬性文法(語(yǔ)法制導(dǎo))定義：產(chǎn)生式 語(yǔ)義規(guī)則DtL,idD.type:=L.typeaddtype(id.entry,L.type)DtLD.type:=L.typeLtT idL.type:=T.typeaddtype(id.entry,T.type)Tt intT.type:=integerTt realT.type:=real第七章例 1 ：給出下面表達(dá)式的逆波蘭表示 ( 后綴式 ) ：(1) a*(-b+c)(2) if(x+y)*z=0 then s:=(

13、a+b)*c else s:=a*b*c解：(1) ab-c+*(2) xy+z*O=sab+c*:=sab*c*:= ¥(注：Y表示 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),

14、 (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) do if (C>D) then X:=Y+Z 翻譯成四元式解：假定翻譯的四元式序列從(100)開(kāi)始：( 100) if A<B goto( 102)(101) goto (107)( 102 ) if C>D goto( 104)(103)goto (100)

15、(104)T : =Y+Z(105)X: =T(106)goto (100)(107)例 4：寫(xiě)出 for語(yǔ)句的翻譯方案解：產(chǎn)生式動(dòng)作S t for E do S1S.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“: ”)|

16、gen(“ if ” S.curr“>” S.Last“ goto ” S.next)|S1.code|gen(S.curr := succ(S.curr)|gen(“ goto ” S.begin)E t v:=i nitial to finalE.i nit := in itial.placeE.final := final.place第八章例 1： C 語(yǔ)言中規(guī)定變量標(biāo)識(shí)符的定義可分為extern, extern static, auto, local static和 register 五種存儲(chǔ)類：(1) 對(duì)五種存儲(chǔ)類所定義的每種變量，分別說(shuō)明其作用域。(2) 試給出適合上述存儲(chǔ)類

17、變量的內(nèi)存分配方式。(3) 符號(hào)表中登記的存儲(chǔ)類屬性，在編譯過(guò)程中支持什么樣的語(yǔ)義檢查。 解：(1) extern 定義的變量，其作用域是整個(gè) C 語(yǔ)言程序。extern static定義的變量，其作用域是該定義所在的 C 程序文件。auto 定義的變量，其作用域是該定義所在的例程。local static定義的變量，其作用域是該定義所在的例程。且在退出該例程時(shí)，該變量的值仍保留。register 定義的變量，其作用域與 auto 定義的變量一樣。這種變量的值，在寄存器 有條件時(shí)，可存放在寄存器中，以提高運(yùn)行效率。(2) 對(duì) extern 變量，設(shè)置一個(gè)全局的靜態(tài)公共區(qū)進(jìn)行分配。對(duì) exter

18、n static 變量，為每個(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ì) local static 變量，為每個(gè)具有這類定義的例程，分別設(shè)置一個(gè)內(nèi)部靜態(tài)區(qū)進(jìn)行 分配。(3) 實(shí)施標(biāo)識(shí)符變量重復(fù)定義合法性檢查，及引用變量的作用域范圍的合法性檢查。第九章例 1：下面的程序執(zhí)行時(shí)，輸出的 地址； (3) 得結(jié)果； 4) 傳值。program main (input,output);procedure p(x,y,z);beginy : =y+i;z : =z+x;e

19、nd;begina: =2;b: =3;p(a+b,a,a);print aend.解：(1) 參數(shù)的傳遞辦法為“傳名”時(shí)，(2) 參數(shù)的傳遞辦法為“傳地址”，(3) 參數(shù)的傳遞辦法為“得結(jié)果”，(4) 參數(shù)的傳遞辦法為“傳值”，a 分別是什么？若參數(shù)的傳遞辦法分別為a 為 9。a 為 8。a 為 7。 a 為 2 。(1) 傳名； (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)

20、作過(guò)程的局部變量處理，即在被調(diào)過(guò)程的活動(dòng)記錄中開(kāi)辟了形參的存儲(chǔ)空 間，這些存儲(chǔ)位置即是我們所說(shuō)的實(shí)參或形式單元。2. 調(diào)用過(guò)程計(jì)算實(shí)參的值，并將它們的右值( r-value )放在為形式單元開(kāi)辟的空間中。3. 被調(diào)用過(guò)程執(zhí)行時(shí)，就像使用局部變量一樣使用這些形式單元。 “傳地址”方式，也稱作傳地址，或引用調(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ò)

21、傳遞到被調(diào)過(guò)程的指針被處理成間接 訪問(wèn)。例 3：下面是一個(gè) Pascal 程序program PP(input,output)var K:integer;function F(N:integer):integer beginif N< =0 then F:=1else F:=N * F(N-1); end;beginK:=F(10);en d;當(dāng)?shù)诙?遞歸地)進(jìn)入 F后，DISPLAY的內(nèi)容是什么？當(dāng)時(shí)整個(gè)運(yùn)行棧的內(nèi)容是什么?解：運(yùn)行妝祁局；例1:何謂代碼優(yōu)化？進(jìn)行優(yōu)化所需要的基礎(chǔ)是什么？解：對(duì)代碼進(jìn)行等價(jià)變換， 使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同，而運(yùn)行速度加快或占用存

22、儲(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ù)寫(xiě)傳 播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)化，并就以下兩種情況分別寫(xiě)出優(yōu)化后的四元式序列:(1 )假設(shè)只有

23、G L、M在基本塊后面還要被引用。 (2 )假設(shè)只有L在基本塊后面還要被引用。解：基本塊對(duì)應(yīng)的DAG如下:B: =3D : =A+CE: =A*C F : =D+EG: =B*F H : =A+CI : =A*C J : =H+IK: =B*5 L : =K+JM =L例1 一個(gè)編譯程序的代碼生成要著重考慮哪些問(wèn)題？解：代碼生成器的設(shè)計(jì)要著重考慮目標(biāo)代碼的質(zhì)量問(wèn)題，而衡量目標(biāo)代碼的質(zhì)量主要從占 用空間和執(zhí)行效率兩個(gè)方面綜合考慮。課后習(xí)題答案：P36-6L(G)是o9組成的數(shù)字串(2)最左推導(dǎo)：N ND NDDNDDD DDDD 0DDD 01DD 012D0127NNDDD3D34NND最右推

24、導(dǎo):NDDDDD5DD56D568NNDN7ND7N27ND27N127D1270127NNDN4D434NNDN8ND8N68D68568P36-8文法：ETE T|E TTFT * F|T / FF(E)|i最左推導(dǎo):E E TT T FT iT iT* F i F* F ii *F i i*iE T T*F F * Fi*Fi*( E)i *( E T) i*( TT) i*( F T)i*(i T)i*(i F)i*(ii)最右推導(dǎo):EE TE T* FE T*iE F *iE i *iT i* iF i*i i i*iE T F *T F * FF*( E)F*( ET)F *( E

25、 F ) F*( E i)F*( T i)F*(F i)F *( ii) i*(i i)語(yǔ)法樹(shù):E/E+T/ IE+TFTFiFiEE + TEE - T/ IE-TFF Fi iTFiFiP36-9句子iiiei有兩個(gè)語(yǔ)法樹(shù):2 siseis s e s ssee SP64 - 71(01)*1010n確定化:01X01,2,30001,2,32,32,3,42,32,32,3,42,3,42,3,52,3,42,3,52,32,3,4,Y2,3,4,Y2,3,52,3,4最小化:0,1,2,3,4,5, 60,1,2,3,4,5°1,3,50,1,2,3,4,511,2,4,60

26、,1,2,3,4, 5, 60,1,2,3,401,3,50,1,2,3, 4, 5, 60,1,2,301,30,1,2,311,2,40,1,2,34, 5, 60,1 010,111,22,3032,3140, 1, 2,3, 4, 5, 6P64 - 12a確定化:ab00,110,10,11100000給狀態(tài)編號(hào):ab012112203333最小化: 0,1, 2,$0,1 a 12,3a 0,3 0,1, 2, 320,1 b2,3b 30(b)最小化: 0,1, 2,3,4,5a1,0 3,5 2,4,11,03,52,4b3,5b 3,50,1b 2,4b 3,5b0,1a 1

27、0,1b2,3,4,5a 1,3,0,5 2,4a3,5a 0,1,0,1a2,4a3,5a2,42,3,4,5b 2,3,4,53,52,4 2,43,52,4P81 - 1(1) 按照 T,S 的順序消除左遞歸G (S)Sa F| 仃)TSTT,ST |遞歸子程序： procedure S;beginif sym='a' or sym='人'then abvanceelse if sym='('then begin advance;T; if sym=')' then advance;else error;endelse er

28、rorend;procedure T; beginS;T end;procedure T ;beginif sym=','then beginadvance;S;Tendend;其中:sym: 是輸入串指針 IP 所指的符號(hào) advance: 是把 IP 調(diào)至下一個(gè)輸入符號(hào) error: 是出錯(cuò)診察程序(2)FIRST(S)=a,(FIRST(T)=af,(FIRST( T )=,FOLLOW(S)=),# FOLLOW(T)=) FOLLOWT )=)預(yù)測(cè)分析表aA()5#SS aS AS (T)TT STT STT STTTT ,ST是LL(1)文法文法:EETTFFPP8

29、1 - 2T EE |F TT IP F* F |(E )| a | b |(1)FIRST(E)=(,a,bfFIRST(E')=+,£ FIRST(T)=(,a,bFIRST(T')=(,a,b,A,£ FIRST(F)=(,a,b,AFIRST(F')=*,£ FIRST(P)=(,a,b,AFOLLOW(E)=#,)FOLLOW(E')=#,)FOLLOW(T)=+,),#FOLLOW(T')=+,),# FOLLOW(F)=(,a,b,A,+,),# FOLLOW(F')=(,a,b,A,+,),# FOL

30、LOW(P)=*,(,a,bf,+,),#考慮下列產(chǎn)生式：E E|TT|F*F |P(E)|A|a|bFIRST(+E) A FIRST( & )=+ n £ = $FIRST(+E) A FOLLOW(E')=+ A #,)=$FIRST(T) A FIRST( £ )=(,a,b,AA £ = $FIRST(T) A FOLLOW(T')=(,a,b,A A +,),#=$FIRST(*F') A FIRST( £ )=* A £ = $FIRST(*F') A FOLLOW(F')=* A

31、(,a,b,A,+,),#=$FIRST(E) A FIRST(a) A FIRST(b) A FIRST(A)= $ 所以,該文法式LL(1)文法.+*()abA#EE TE'E TE'E TE'E TE'E'EEEETT FTT FTT FTT FTT'TT TTT TT TTTTFF PFF PFF PFF PFF'FF *FFFFFFFPP (E)P aP bP Aprocedure E;beginif sym='(' or sym='a' or sym='b' or sym=

32、9; a' the n beg in T; E' end else errorendprocedure E'beginif sym='+'the n beg in adva nee; E endelse if sym<>')' and sym<>'#' then error endprocedure T;beginif sym='(' or sym='a' or sym='b' or sym=' a' the n beg in F; T

33、' end else errorendprocedure T'beginif sym='(' or sym='a' or sym='b' or sym=' a' the n Telse if sym='*' then errorend procedure F;beginif sym='(' or sym='a' or sym='b' or sym='人' then begin P; F' end else errorend pr

34、ocedure F' beginif sym='*'then begin advance; F' end end procedure P;beginif sym='a' or sym='b' or sym='A'then advanceelse if sym='(' thenbeginadvance; E;if sym=')' then advanceelse errorendelse errorend;P133- 1E E T E T* F 短語(yǔ) : E+T*F, T*F, 直接短

35、語(yǔ) : T*F 句柄 : T*FP133-2文法：TS aT|,AS|(|ST)(1) 最左推導(dǎo) :S (T)(T,S)(S,S)(a,S)(a,(T)(a,(T,S)S (T,S) (S,S) (T),S) (T,S),S) (T,S,S),S)(a,(S,S)(a,(a,S)(a,(a,a)(S,S,S),S) ( T), S,S), S) (a,a),S,S),S)(a,a),A , S), S)(a,a),A,(T), S) (a,a),A ,( S), S)(a,a),A ,( a), S)( T , S), S, S), S) ( S, S), S, S), S)( a, S),

36、S,S), S)(a,a),A ,(a),a)最右推導(dǎo)：S(T)(T,S)(T,(T)(T,(T,S)(T,(T,a)(T,(S,a)(T,(a,a)(S,(a,a)(a,(a,a)S(T,S)(T,a)(S,a)(T),a)(T,S),a)(T,(T), a)(T,(S),a)(T,(a),a)(T,S,(a),a)(T, ,(a), a)(S,A ,(a), a) (T)f ,(a),a)(T,S)T ,(a), a)(T,a)】 ,(a),a)(S,a),A ,(a),a)(a,a),A ,(a),a)(a,a),A,(a),a)(S),A,(a) ),a)(T, a),A,(a),a)

37、(TS),A,(a),a)(IL,A,(a),a)(S,A,(a),a)(T,A,(a),a)(TS,(a),a)(T,( a),a)(T,( S),a)(T,( T),a)(TS),a)(!L,a)(S,a)(TS)(D_S“移進(jìn)-歸約”過(guò)程:步驟棧輸入串動(dòng)作0#(a,a),A,(a),a)#預(yù)備1#(a,a),A,(a),a)#進(jìn)2#(a,a),A,(a),a)#進(jìn)3#(a,a),A,(a),a)#進(jìn)4#(a,a),A,(a),a)#進(jìn)5#(S,a),A,(a),a)#歸6#(T,a),A,(a),a)#歸7#(T,a),A,(a),a)#進(jìn)8#(T,a),A,(a),a)#進(jìn)9#(T,S

38、),A,(a),a)#歸10#(T),A,(a),a)#歸11#(T),A,(a),a)#進(jìn)12#(S,A,(a),a)#歸13#(T,A,(a),a)#歸14#(T,A,(a),a)#進(jìn)15#(T,a,(a),a)#進(jìn)16#(T,S,(a),a)#歸17#(T,(a),a)#歸18#(a),a)#進(jìn)19#(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

39、)#歸32#(T)#歸33#(T)#進(jìn)34#S#歸P133-3(1) FIRSTVT(S)=a,(FIRSTVT(T)=,a】,(LASTVT(S)=af,)LASTVT(T)=,a,)aA()Ja>>A>>(<<<=<)>><<<>>G6是算符文法，并且是算符優(yōu)先文法(3)優(yōu)先函數(shù)棧輸入字符串動(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)#

40、 ( 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ǔ)法樹(shù)如下圖：LE.val=58nT.val=58digit .l exval=2F.val=29T.val=28T.val=1P164 2答：(1)ba、bP165- 11答：(1) D id LD.type:= L.typeLt , id L 1L.type:= L 1 .typeLt : TL.type:= T.typeTt in teger T.type := in tegerTt real T.type := real;addtype(id.