編譯原理題庫

1、第一章 什么是編譯器？ 編譯程序的結(jié)構(gòu)分為幾個(gè)階段，各階段的任務(wù)是什么? 遍、編譯前端及編譯后端的含義？ 編譯程序的生成方式有哪些？ 第二章 1.寫一文法，使其語言是偶正整數(shù)的集合。 要求：（1）允許0打頭（2） 不允許0打頭 允許0開頭的偶正整數(shù)集合的文法 7 NT|D 7 NT|D 7 D|1|3|5|7|9 7 0|2|4|6|8 D （2）不允許0開頭的偶正整數(shù)集合的文法 E 7 NT|D 7 FT|G 7 D|1|3|5|7|9 7 2|4|6|8 7 N|0 7 D|0 G 2.證明下述文法 G 表達(dá)式是二義的。 表達(dá)式： 運(yùn)算符： 解：可為句子 最右推導(dǎo)1 表達(dá)式 表達(dá)式 表達(dá)式

2、 表達(dá)式 表達(dá)式 最右推導(dǎo)2 表達(dá)式 表達(dá)式 表達(dá)式 表達(dá)式 表達(dá)式 3. =a|（表達(dá)式）| 表達(dá)式運(yùn)算符表達(dá)式 =+|-|*|/ a+a*a構(gòu)造兩個(gè)不同的最右推導(dǎo)： 表達(dá)式 運(yùn)算符 =表達(dá)式運(yùn)算符表達(dá)式 * a 運(yùn)算符 運(yùn)算符 表達(dá)式 運(yùn)算符 運(yùn)算符 運(yùn)算符 運(yùn)算符 表達(dá)式* a =表達(dá)式運(yùn)算符表達(dá)式 表達(dá)式運(yùn)算符表達(dá)式 表達(dá)式運(yùn)算符a 表達(dá)式* a a + a * a 給出生成下述語言的上下文無關(guān)文法： (1) anbnambm| n , m=0 (2) 1n0m1m0n| n , m=0 解:(1) anbnambm| n , m=0 S7 AA A7 aAb| 精品文庫 歡迎下載16

3、 1nOm1mOn| n, m=0 4 1S0|A A7 0A1| 第三章 1、構(gòu)造一個(gè)DFA它接收刀=a, b上所有滿足下述條件的字符串: 至少一個(gè)b直接跟在其右邊。 解： 已知刀=a, b，根據(jù)題意得出相應(yīng)的的正規(guī)式為： 根據(jù)正規(guī)式畫出相應(yīng)的 用子集法將其確定化 DFA M如下圖所示 (b*abb*)* 字符串中的每個(gè) a都有 CD (b*abb*)* X b*abb* X 2 3 4 b 5 a b X,1,2,3,Y 4 2,3 4 一 5,6,1,2,3,Y 2,3 4 2,3 5,6,1,2,3,Y 4 6,1,2,3,Y 6,1,2,3,Y 4 6,1,2,3,Y I Ia Ib

4、 0 1 2 1 一 3 2 1 2 3 1 4 4 1 4 由DFA得狀態(tài)圖 順序重新命名 用最小化方法化簡得: DFA M 第四章 練習(xí)1:文法 V 7 N|NE GV: E 7 V|V+E 是否為LL(1)文法，如不是，如何將其改造成 解： LL(1)文法的基本條件是不含左遞歸和回溯(公共左因子) 7 i LL(1)文法。 ，而GV中含有回溯，所以先消 V 7 |E 7 |+E FIRST(A) 加入 FOLLOW(B),即 FOLLOW(B)=a, b, c, d ; FIRST(S) 加入 FOLLOW(B),即 FOLLOW(B)=a, b, c, d ; FOLLOW(B加入 F

5、OLLOW(A),即 FOLLOW(A)=a, b, c, d ; FOLLOW(B加入 FOLLOW(S),即 FOLLOW(S)=#, a, b, c, d ; 由 A7 BS|d 得： FIRST(BS) 由 B7 aA|bS|c 得： FIRST(aA) n FIRST(d) = a, b, c n d= n FIRST(bS) n FIRST(c) =a n b 由于文法Gs不存在形如3 7 的產(chǎn)生式，故無需求解形如 也即，文法 GS是一個(gè)LL(1)文法。 (2)由 Gs:S 7 BA FIRST(B)=a, b, c; FIRST(A)=a, b, c, d; A 7 BS|d B

6、 7 aA|bS|c 的 FOLLOW(B)=a, b, c, d ; FOLLOW(A)=a, b, c, d ; n c= O FIRST( a ) n FOLLOW(A的值。 除回溯得到文法 G V: G V :V 7 NV E7 VEE N7 i G V是LL(1)文法 由LL(1)文法的充要條件可證 練習(xí)2:有文法 Gs: B 7 aA|bS|c S 7 ba a 7 BS|d (1)證明文法G是LL(1)文法。 構(gòu)造LL(1)分析表。 (3)寫出句子adccd的分析過程 解：(1) 一個(gè)LL(1)文法的充要條件是：對每一個(gè)非終結(jié)符A的任何兩個(gè)不同產(chǎn)生式A7 a | 3，有下面的條件

7、成立： FIRST( a ) n FIRST( 3 )=; 若 3 *= ,則有 FIRST( a ) n FOLLOW(A) 對于文法Gs: S 7 BA A 7 BS|d B 7 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)=#; 對S7 ba有： 對A7 BS有： 對B7 aA有： 對B7 bS有： a b u d # S S7 BA S7 BA S7 BA A A7 BS A7 BS A7 BS A7 d B B7 aA B7 bS B

8、7 c c S S7 BA S7 BA S7 BA A A7 BS A7 BS A7 BS A7 d B7 aA B7 bS B7 c O FOLLOW(S)=#, a, b, c, d FIRST(S)=a, b, c 可構(gòu)造LL(1)預(yù)測分析表如下: (3)在分析表的控制下，句子adccd的分析過程如下: (1) 解: 非終結(jié)符 FIRSTVT 集 lastvt集 s a A ( a A ) a A ( , a A ) , St(T) Tt s Tt T,S (1) FIRSTVT - LASTVT 表 OPG文法。 第五章 1已知文法GS為： St a| A |(T)TtT,S|S 計(jì)算

9、 GS的 FIRSTVT和 LASTVT 構(gòu)造GS的算符優(yōu)先關(guān)系表并說明 GS是否為算符優(yōu)先文法。 給出輸入串(a,(a,a)#的算符優(yōu)先分析過程。 文法： T t T,S|S St a| A |(T) 展開為： St a StA (2)算符優(yōu)先關(guān)系表如下：表中無多重入口所以是算符優(yōu)先( (3)輸入串(a,(a,a) ) #的算符優(yōu)先分析過程為: 當(dāng)前字 符 剩余輸入串 動(dòng)作 E(a (N (N, #(N,( #(N,(a #(N,(N I(N,(N, (N,(N,a (N,(N,N (N,(N (N,(N) (N,N (N a ) ) ) ) ) ) # # a,(a,a)# ,(a,a)#

10、 (a,a)# (a,a)# a,a)# ,a)# a)# a)# )# )# )# )# # 第六章 例1:有文法：S 7 (L)|a L 給此文法配上語義動(dòng)作子程序 的個(gè)數(shù)。如對于句子(a,(a,a), 解：加入新開始符號(hào)S和產(chǎn)生式 義如下： 產(chǎn)生式 Move in Move in Reduce: S 7 a Move in Move in Move in Reduce: S 7 a Move in Move in Reduce: S 7 a Reduce: T 7t,S Move in Reduce: S 7 (T) Reduce: T 7t,S Move in Reduce: S (T

11、) 7 L,S|S (或者說為此文法寫一個(gè)語法制導(dǎo)定義)，它輸出配對括號(hào) 輸出是2。 S 7 S,設(shè)num為綜合屬性，代表值屬性，則語法制導(dǎo)定 S S S 7 (L) 7 a 7 L1,S 7 S 語義規(guī)則 prin t(S .num) S.nu m:=L. nu m+1 S. nu m:=0 L.num :=L1. nu m+S .num L.nu m:=S. num 例2:構(gòu)造屬性文法，能對下面的文法，只利用綜合屬性獲得類型信息。 D 7 L,id | L L7 T id T7 int | real 解：屬性文法 7 L,id | L L (語法制導(dǎo))定義： 產(chǎn)生式語義規(guī)則 7 L,idD

12、.typ e:=L.t ype addt yp e(id.e ntry,L.t ype) 7 LD.t yp e:=L.t ype L.t yp e:=T.t ype addt yp e(id.e ntry,T.t ype) T.t ype:=in teger T.t yp e:=real 7 int 7 real 第七章 例1 :給出下面表達(dá)式的逆波蘭表示(后綴式): a*(-b+c) (2) if(x+y)*z=0 then s:=(a+b)*c else s:=a*b*c 解： (1) ab-c+* (2) xy+z*O=sab+c*:=sab*c*:= Y (注：Y表示 if-then

13、-else運(yùn)算) 例 2：請將表達(dá)式-(a+b)*(c+d)-(a+b) 解： 分別表示成三元式、間接三元式和四元式序列。 三元式 間接三元式 (1) (+ a, b) 間接三元式序列 間接碼表 (+ c, d) (1) (+ a, b) (1) (3) (* (1), (2) (+ c, d) (2) (-(3), /) (3) (* (1), (2) (3) (+ a, b) (-(3), /) (4) (6) (- (4), (5) (5) (- (4), (1) (1) (5) 四元式 (1) (+, a, b, t1) (+, c, d, t2) (*, t1, t2, t3) (4

14、) (-, t3, /, t4) (+, a, b, t5) (6) (-, t4, t5, t6) 例3:請將下列語句 while (AD) then X:=Y+Z 翻譯成四元式 解： 假定翻譯的四元式序列從(100)開始： (100) if AD goto (104) (103) goto (100) (104) T : =Y+Z (105) X : =T (106) goto (100) (107) 例4：寫出for 解： 產(chǎn)生式 S T for E do S1 語句的翻譯方案 動(dòng)作 S.begi n := n ewlabel S.first := n ewte mp S.last :=

15、 n ewte mp S.curr:= n ewte mp S.code:=ge n( S.first |ge n(S.last “ :=” E.i nit) “ :=” E.final) “if ” S.first ( ” |ge n( |ge n( S.curr |ge n( S.begi n |ge n( |S1.code |ge n( S.curr := succ(S.curr) |gen(“ goto ” S.begin) E T v:=i nitial to finalE.i nit := in itial. place E.final := fin al. place a ? “

16、if ” S.curr “ ” S.last S.first) ) “ ” S.Last “ goto ” S.next) “ goto ” S.next) 第八章 auto, local static 例1: C語言中規(guī)定變量標(biāo)識(shí)符的定義可分為extern, extern static, 對五種存儲(chǔ)類所定義的每種變量，分別說明其作用域。 試給出適合上述存儲(chǔ)類變量的內(nèi)存分配方式。 符號(hào)表中登記的存儲(chǔ)類屬性，在編譯過程中支持什么樣的語義檢查。 和register 五種存儲(chǔ)類： (1) 解： (1) extern定義的變量，其作用域是整個(gè)C語言程序。 extern static定義的變量，其作用域

17、是該定義所在的C程序文件。 auto定義的變量，其作用域是該定義所在的例程。 local static定義的變量，其作用域是該定義所在的例程。且在退出該例程時(shí)，該變 量的值仍保留。 register定義的變量，其作用域與auto定義的變量一樣。這種變量的值，在寄存器 有條件時(shí)，可存放在寄存器中，以提高運(yùn)行效率。 (2) 對extern變量，設(shè)置一個(gè)全局的靜態(tài)公共區(qū)進(jìn)行分配。 對extern static 變量，為每個(gè)C程序文件，分別設(shè)置一個(gè)局部靜態(tài)公共區(qū)進(jìn)行分配。 對auto和register變量，設(shè)定它們在該例程的動(dòng)態(tài)區(qū)中的相對區(qū)頭的位移量。而例 程動(dòng)態(tài)區(qū)在運(yùn)行時(shí)再做動(dòng)態(tài)分配。 對local

18、 static 變量，為每個(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)傳值。 P rogram main (inpu t,out pu t); pro cedure p( x,y,z); begin y : =y+1; z : =z+x; en d; begin a : =2; b : =3; p (a+b,a,a); print a en d. 解: (1) 參數(shù)的傳遞辦法為 “傳

19、名”時(shí)， a 為9。 參數(shù)的傳遞辦法為 “傳地址”， a 為8。 參數(shù)的傳遞辦法為 “得結(jié)果”， a 為7。 參數(shù)的傳遞辦法為 “傳值”， a為2。 例2:過程參數(shù)的傳遞方式有幾種？簡述“傳地址”和“傳值”的實(shí)現(xiàn)原理。 解： 參數(shù)的傳遞方式有下述幾種：傳值，傳地址，傳名，得結(jié)果 “傳值”方式，這是最簡單的參數(shù)傳遞方法。即將實(shí)參計(jì)算出它的值，然后把它傳給被調(diào)過 程。具體來講是這樣的： 1. 形式參數(shù)當(dāng)作過程的局部變量處理，即在被調(diào)過程的活動(dòng)記錄中開辟了形參的存儲(chǔ)空 間，這些存儲(chǔ)位置即是我們所說的實(shí)參或形式單元。 2. 調(diào)用過程計(jì)算實(shí)參的值，并將它們的右值(r-value )放在為形式單元開辟的空

20、間中。 3. 被調(diào)用過程執(zhí)行時(shí)，就像使用局部變量一樣使用這些形式單元。 指向?qū)崊?“傳地址”方式，也稱作傳地址，或引用調(diào)用。調(diào)用過程傳給被調(diào)過程的是指針， 存儲(chǔ)位置的指針。 1. 如實(shí)參是一個(gè)名字或是具有左值的表達(dá)式，則左值本身傳遞過去。 2. 如實(shí)參是一個(gè)表達(dá)式，比方a+b或2,而沒有左值，則表達(dá)式先求值，并存入某一位 置，然后該位置的地址傳遞過去。 3. 被調(diào)過程中對形式參數(shù)的任何引用和賦值都通過傳遞到被調(diào)過程的指針被處理成間接 訪問。 例3：下面是一個(gè) Pascal程序 P rogram PP (i npu t,out put) var K:in teger; fun cti on F(

21、N:i nteger):i nteger begin if N =0 the n F:=1 else F:=N * F(N-1); en d; begin K:=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ǔ)是什么？ 解： 而運(yùn) 對代碼進(jìn)行等價(jià)變換， 使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同, 行速度加快或占用存儲(chǔ)空間減少，或兩者都有。 優(yōu)化所需要的基礎(chǔ)是在中間代碼生成之后或目標(biāo)代碼生成之后。 例2:編譯過程中可進(jìn)行的優(yōu)化如何分類？最常用的代碼優(yōu)化技術(shù)

22、有哪些？ 解： 依據(jù)優(yōu)化所涉及的程序范圍，可以分為：局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化。 最常用的代碼優(yōu)化技術(shù)有 1.刪除多余運(yùn)算2.代碼外提3.強(qiáng)度削弱4.變換循環(huán)控制條件 5.合并已知量與復(fù)寫傳 播6.刪除無用賦值 B: =3 D :=A+C E: =A*C F :=D+E G: =B*F H :=A+C I : =A*C J :=H+I K: =B*5 L :=K+J M =L B2: 例3:試對以下基本塊 解： 基本塊對應(yīng)的DAG如下： B: =3D: =A+C E: =A*C F : =D+E G: =B*F H : =A+C I : =A*C J : =H+I K: =B*5 L : =

23、K+J M =L 例1 一個(gè)編譯程序的代碼生成要著重考慮 (1) (2) 應(yīng)用DAG對它們進(jìn)行優(yōu)化，并就以下兩種情況分別寫出優(yōu)化后的四元式序列: 假設(shè)只有 G L、M在基本塊后面還要被引用。 假設(shè)只有L在基本塊后面還要被引用。 些問題？ 解： 代碼生成器的設(shè)計(jì)要著重考慮目標(biāo)代碼的質(zhì)量問題，而衡量目標(biāo)代碼的質(zhì)量主要從占 用空間和執(zhí)行效率兩個(gè)方面綜合考慮。 課后習(xí)題答案： P36-6 L(G)是09組成的數(shù)字串 (2)最左推導(dǎo)： N = ND = NDD = NDDD 二 DDDD = ODDD = O1DD= 012D二 0127 N = ND = 最右推導(dǎo)： N = ND NDD = DDD

24、= 5DD= 56D= 568 N7 = ND7= N27= ND27= N127= D127= 0127 ND N4 = D4= 34 ND N8 = ND8= N68= D68= 568 P36-8 文法: Et Tt Ft +T|E -T T E F T* F|T/ F (E)|i 最左推導(dǎo)： E = E *r = T +T= F +T= i +T=i +T* F = i +F* F = i +i *F = i +i *i E = T=T*F=F*F = i*F = i*( E)= i*( E +T)= i*( T +T)= i*( F +T) =i*(i +T)= i*( i +F)

25、= i*(i +i) 最右推導(dǎo)： E=E *Fr=E +T*F = E 4T*i = E +F*i = E +i*i = T 十 i*i=F +i*i=i+i*i E=T = F*T = F*F = F*( E)=F*(E +T)=F*(E+F)=F*(E +i) =F*( T +i) = F *( F +i) = F *( i +i)=i*( i 4i) 語法樹./* i+i+i i-i-i i+i*i P36-9 句子iiiei 有兩個(gè)語法樹: =iiiei S 二 iSeS= iSei = iiSei S 二 iS= iiSeS= iiSei = iiiei P64 - 7 (1) 1(

26、01) 101 歡迎下載17 0 1 X 1,2,3 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 最小化： 0,1,2,3,4,5, 6 0,1,2,3,4,51,2,4,6 0,1,234,5 0 =1,3,5 0,1,2,3,4, 5, 6 0,1,234 0 =1,3,5 0,1,2,3, 4, 5, 6 0,1,2,3。=1,30,1,2,31 =1,2,4 0,1,2,34, 5, 6 0,1。=10,1 =1,2 2,3。叫32,34 0, 1, 2,3,

27、 4, 5, 6 1 1 精品文庫 P64- 12 歡迎下載29 a b 0 0,1 1 0,1 0,1 1 1 0 給狀態(tài)編號(hào): a b 0 1 2 1 1 2 2 0 3 3 3 3 A 0,1 1 2,3a =0,3 0,1, 2, 3 0,1 b =2 2,3b =3 (b) 最小化: 0,1, 2,3,4,5 0,1a =10,1b =2,4 2,3,4,5a =1,3,0,52,3,4,5b =2,3,4,5 2,4a =1,02,4b =3,5 3,5a =3,53,5b =2,4 0,1, 2,4, 3,5 = 1 = 1,0 0,1b =2,4 2,4b =3,5 0,1a

28、2,4a 3,5 P 81 - 1 (1)按照T,S的順序消除左遞歸 G(S) ST aFI 仃) T T ST Tt ,ST I 遞歸子程序： p rocedure S; begin if sym=a or sym= the n abva nee else if sym=( the n begi n advance;T; if sym=) the n adva nee; else error; end else error end; p roeedure T; begin ST en d; proeedure T : begin if sym=, the n begi n advanee;

29、ST end end; 其中： sym:是輸入串指針I(yè)P所指的符號(hào) advanee:是把IP調(diào)至下一個(gè)輸入符號(hào) error:是出錯(cuò)診察程序 FIRST(S)=a,A,( FIRST(T)=a,A,( FIRST()=, FOLLOW(S)=),# FOLLOW(T)=) FOLLOWT )=) 預(yù)測分析表 a A ( ) J # S St a St a St (T) T Tt st Tt ST Tt st T， Tt s Tt ,ST 是LL(1)文法 P 81 - 2 文法: E E T T F F P T E + E F T T | P F * F (E ) (1) FIRST(E)=(,

30、a,b,A FIRST(E)=+, FIRST(T)=(,a,b,A FIRST(T)=(,a,b,A, FIRST(F)=(,a,b,A FIRST(F)=*, FIRST( P)=(,a,b,A FOLLOW(E)=#,) FOLLOW(E)=#,) FOLLOW(T)=+,),# FOLLOW(T)=+,),# FOLLOW(F)=(,a,b,A,+,),# FOLLOW(F)=(,a,b,A,+,),# FOLLOW( P)=*,(,a,b,A,+,),# 考慮下列產(chǎn)生式： EJ +E|s T J T|e F J *F 2 Pt (E)|A|a|b FIRST(+E) n FIRST(

31、 )=+ n = 0 FIRST(+E) n FOLLOW(E)=+ n #,)=0 n = 0 n +,),#=0 n FiRST( )=* n = 0 n FOLLOW(F)=* n (,a,b,A,+,),#=0 n FIRST(a) n FIRST(b) n FIRST()= 0 FIRST(T) n FIRST( )=(,a,b, FIRST(T) n FOLLOW(T)=(,a,b,A FIRST(*F) FIRST(*F) FIRST(E) 所以,該文法式LL(1)文法. + ( ) a b A # E Et TE Et TE Et TE Et TE E Et+ E E J E

32、J T Tt FT Tt FT Tt FT Tt ft T Tt s Tt T Tt E Tt T Tt T Tt T Tt F Ft PF Ft PF Ft PF Ft PF F Ft s FT*F F J F J F J F J FT s FT P PT (E) Pt a Pt b PT A P rocedure E; begin if sym=( or sym=a or sym=b or sym- the n beg in T; E end else error end p rocedure E; begin if sym=+ the n beg in adva nee; E end e

33、lse if sym) and sym# the n error end p rocedure T; begin if sym=( or sym=a or sym=b or sym- the n beg in F; T end else error end p rocedure T; begin if sym=( or sym=a or sym=b or sym= then T else if sym=* the n error end p rocedure F; begin if sym=( or sym=a or sym=b or sym= the n beg in P; F end el

34、se error end p rocedure F; begin if sym=* the n beg in adva nee; F end end p rocedure P; begin if sym-a or sym-b or sym= the n adva nee else if sym=( the nbegin advanee; E; if sym=) the n adva nee else error end else error end; P133- 1 E= E +T二 E+ T* F 短語：E+T*F, T*F, 直接短語：T*F 句柄:T*F P133- 2 文法: St a

35、|A|(T) Tt T,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)= (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) = (a,S),S,S),SM (a,a), S,S), S) =(a,a),A ,S),S)= (a,a),A ,(T), S)= (a,a),A ,(S), S)= (a,a),A ,(a

36、), 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)= (T), ,(a), a) 二(T,S),A ,(a), a)二(T,a),A ,(a),a)= (S,a),A ,(a),a)二(aa)】 ,(a),a) (

37、a,a),(a),a) (S),A,(a),a) (T, ar,(a),a) (LSV,(a),a) (IL,A,(a),a) (S,A,(a),a) (T,A,(a),a) (T,( (T,( (T,( (LS,(a),a) aj),a) S),a) T),a) (TS),a) (IL,a) (S,a) (TS) (T)_ S “移進(jìn)-歸約”過程: 步驟棧 輸入串 (a，a),A,(a),a)# (a，a)，A，(a),a)# 動(dòng)作 預(yù)備 進(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

38、),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 ),A,(a),a)# 歸 10 #(T ),(a),a)# 歸 11 #(T) ，八,(a),a)# 進(jìn) 12 #(S ,(a),a)# 歸 13 #(T ,(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 #(T, (a),a)# 進(jìn) 19 #(T,( a),a)# 進(jìn) 20 #(T,(

39、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,A,( FIRSTVT(T)=,a,A,( LASTVT(S)=a,A,) LASTVT(T)=,a,A,) a A ( ) J a A ( = J 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) # ( t, ( s ,a）# 歸 # ( t, ( t ,a）# 歸 # ( t, ( t, a）# 進(jìn) # (t, (t,a ）# 進(jìn) # (t, (t,s ）# 歸 # ( t, ( t ）# 歸 # (