1、編譯原理編譯原理期末總復(fù)習(xí)期末總復(fù)習(xí)考試題型及分?jǐn)?shù)分布n填空題(10分）n單選題（20分）n判斷題（10分）n解析題（60分）第二章第二章文法與形式語言簡介文法與形式語言簡介（1 1）給出）給出句型句型或或句子句子最左推導(dǎo)或最右推導(dǎo)最左推導(dǎo)或最右推導(dǎo)（規(guī)范推導(dǎo)）；（規(guī)范推導(dǎo)）；（2 2）畫出）畫出句型句型或或句子的語法樹；句子的語法樹；（3 3）求句型的短語、簡單短語、句柄；）求句型的短語、簡單短語、句柄；（4 4）判斷一個文法是二義性的文法）判斷一個文法是二義性的文法P28#3n規(guī)范推導(dǎo)：規(guī)范推導(dǎo)：aa+a*S =SS*|SS+|a S=aa+a*Sa+a*=SS+a*=Sa*=SS*=n語

2、法樹：語法樹：SSS*SS+aaaP28#4n只含有4個符號的句子：Z =U0 V1U =Z1 1V =Z0 0P28#5S =ABA =aAB =bBcbc A =aA描述的語言描述的語言: an|n=0B =bBcbc描述的語言描述的語言:bncn|n=1L(GS)=anbmcm|n=0,m=1P28#7E =T E+T E-T T =F T*F T/FF =(E) i， 句型句型T+T*F+i的語法樹：的語法樹： EE+TTE+TT*FFi短語：短語：T+T*F+i,T+T*F簡單短語：簡單短語：T*F， T ，i句柄：句柄： T 已知文法已知文法GE:GE:E:=E+T|TE:=E+T

3、|TT:=TT:=T* *F|FF|FF:=(E)|iF:=(E)|i1 1、試給出句子、試給出句子i i* *(i+i)(i+i)的規(guī)范推導(dǎo)；的規(guī)范推導(dǎo)；2 2、畫出相應(yīng)的語法樹；、畫出相應(yīng)的語法樹；( (注意：相同的葉子節(jié)點用注意：相同的葉子節(jié)點用不同的下標(biāo)加以區(qū)分，如：不同的下標(biāo)加以區(qū)分，如：i1 i1、i2i2、i3)i3)3 3、指出該句子所有的短語、簡單短語、句柄。、指出該句子所有的短語、簡單短語、句柄。存在的問題存在的問題n給出的推導(dǎo)不是規(guī)范推導(dǎo)；給出的推導(dǎo)不是規(guī)范推導(dǎo)；n一次使用多條規(guī)則；一次使用多條規(guī)則；n沒有標(biāo)明句柄所在的位置；沒有標(biāo)明句柄所在的位置；n不是從文法的開始符號

4、進行推導(dǎo)；不是從文法的開始符號進行推導(dǎo)；句子句子i i* *(i+i)(i+i)的規(guī)范推導(dǎo)的規(guī)范推導(dǎo)E ET T T T* *F F T T* *(E)(E) T T* *(E+T) (E+T) T T* *(E+F) (E+F) T T* *(E+i) (E+i) T T* *(T+ i) (T+ i) T T* *(F + i) (F + i) T T* *(i + i) (i + i) F F* * (i + i) (i + i) i i * * (i + i) (i + i) 句子句子i i* *(i+i)(i+i)的語法樹的語法樹短語、簡單短語、句柄短語、簡單短語、句柄為了區(qū)分相同的

5、短語，可以采用加下標(biāo)的方法。為了區(qū)分相同的短語，可以采用加下標(biāo)的方法。i i1 1、i i3 3是相對于非終結(jié)符號是相對于非終結(jié)符號F F、T T的短語、簡單短語的短語、簡單短語; ;i i2 2是相對于非終結(jié)符號是相對于非終結(jié)符號F F、T T、E E的短語、簡單短語的短語、簡單短語; ;i i2 2+i+i3 3是相對于非終結(jié)符號是相對于非終結(jié)符號E E的短語的短語; ;(i (i2 2+i+i3 3) )是相對于非終結(jié)符號是相對于非終結(jié)符號F F的短語的短語; ;i i1 1* *(i (i2 2+i+i3 3) )是相對于非終結(jié)符號是相對于非終結(jié)符號T T、E E的短語的短語; ;i

6、i1 1是句柄是句柄; ;P28#8S =S*S|S+S|(S)|a 給出句子給出句子a+a*a 兩棵不同的語法樹兩棵不同的語法樹SSS*S+SaaaSSS+S*Saaa已知文法已知文法GS:GS:S:=iSeS|iS|iS:=iSeS|iS|i試說明該文法是二義性的文法。試說明該文法是二義性的文法。句子句子iiieiiiiei兩棵不同的語法樹兩棵不同的語法樹S:=iSeS|iS|i第三章第三章 詞法分析詞法分析1 1、正規(guī)文法和有限自動機的等價性正規(guī)文法和有限自動機的等價性2 2、正規(guī)式和有限自動機的等價性正規(guī)式和有限自動機的等價性3、 NFANFA到到DFADFA轉(zhuǎn)換的子集法及最小化轉(zhuǎn)換的

7、子集法及最小化正則文法的狀態(tài)圖畫法如下正則文法的狀態(tài)圖畫法如下：1、文法中的每個非終結(jié)符號對應(yīng)狀態(tài)圖中的一個結(jié)點，、文法中的每個非終結(jié)符號對應(yīng)狀態(tài)圖中的一個結(jié)點，即圖中的每個結(jié)點代表一個非終結(jié)符號。即圖中的每個結(jié)點代表一個非終結(jié)符號。2、增設(shè)一個結(jié)點代表開始狀態(tài)、增設(shè)一個結(jié)點代表開始狀態(tài)S，而文法中的，而文法中的識別符號對識別符號對應(yīng)的結(jié)點為終結(jié)狀態(tài)應(yīng)的結(jié)點為終結(jié)狀態(tài) 3、對于文法中的每一條形如、對于文法中的每一條形如Ua的規(guī)則，畫一條從結(jié)點的規(guī)則，畫一條從結(jié)點S指向結(jié)點指向結(jié)點U的弧線，并在弧上標(biāo)記的弧線，并在弧上標(biāo)記a。4、對于文法中每一條形如、對于文法中每一條形如U =Wa的規(guī)則，畫一條

8、從結(jié)的規(guī)則，畫一條從結(jié)點點W指向結(jié)點指向結(jié)點U的弧線，并在弧上標(biāo)記的弧線，并在弧上標(biāo)記a。SUa開始狀態(tài)開始狀態(tài)WUa有正則文法GZ：Z:=Ua|Vb，U:=Zb|b，V:=Za|a ，畫出該文法的狀態(tài)圖，并檢查句子abba是否合法。 SUVZaaabbbP60#1句子abba合法。Z:=Ua|VbU:=Zb|bV:=Za|aZ:=Ua|Vb，U:=Zb|b，V:=Za|a從正規(guī)式從正規(guī)式R R構(gòu)造構(gòu)造NFA MNFA M的步驟的步驟1 11 1、把正規(guī)式、把正規(guī)式R R表示為：表示為：初態(tài)初態(tài)終態(tài)終態(tài)xyR R從從上的正規(guī)式上的正規(guī)式R R構(gòu)造構(gòu)造NFA MNFA M的步驟的步驟2 22 2

9、、把、把R R分裂并加進新的結(jié)點分裂并加進新的結(jié)點每條弧標(biāo)記為每條弧標(biāo)記為上的一個字符或上的一個字符或結(jié)點分裂規(guī)則結(jié)點分裂規(guī)則加入加入k結(jié)點結(jié)點1弧變弧變2弧弧結(jié)點分裂規(guī)則結(jié)點分裂規(guī)則1弧變弧變2弧弧結(jié)點分裂規(guī)則結(jié)點分裂規(guī)則加入加入k結(jié)點結(jié)點閉包去掉變閉環(huán)閉包去掉變閉環(huán)前后各前后各1條空弧條空弧kijR1子集法的基本思想子集法的基本思想NFANFA基本思想基本思想：NFANFA的的一組一組狀態(tài)狀態(tài)DFADFA的的一個一個狀態(tài)狀態(tài)對應(yīng)對應(yīng)等價的等價的DFA DFA 子子集集法法轉(zhuǎn)轉(zhuǎn)換換子集法子集法設(shè)已給具有設(shè)已給具有動作的動作的NFA M=NFA M=（K,f,SK,f,S0 0,Z),Z)構(gòu)造

10、相應(yīng)的確定的有限自動機構(gòu)造相應(yīng)的確定的有限自動機: : DFA M = DFA M =（KK,ff,q,q0 0,Z ),Z )構(gòu)造構(gòu)造K K 及及f f 的步驟可遞歸地描述如下：的步驟可遞歸地描述如下：（1 1）給出）給出MM的初態(tài)的初態(tài) ： 遞歸描述步驟（遞歸描述步驟（1 1）K=K= qq0 0 q q0 0 = = -closure(S-closure(S0 0) )遞歸描述步驟（遞歸描述步驟（2 2）（2 2）對于）對于KK中尚未標(biāo)記的狀態(tài)中尚未標(biāo)記的狀態(tài)q qi i =S=Si1 i1 ,S,Si2 i2 ,S,Simim, S, Sik ik K做做 ：標(biāo)記標(biāo)記q qi i ；對

11、于每一個對于每一個aa，置：，置：若若q qj j不在不在KK中中, ,則將則將q qj jf(qf(qi i , a)=q, a)=qj jKKMMJ=move(SJ=move(Si1 i1 ,S,Si2 i2 ,S,Simim,a),a)， q qj j = = -closure(J)= I-closure(J)= Ia a遞歸描述步驟（遞歸描述步驟（3 3）（3 3）重復(fù)（）重復(fù)（2 2）直到）直到MM中不再有未標(biāo)記的中不再有未標(biāo)記的狀態(tài)為止。狀態(tài)為止。至少含有一個至少含有一個Z Z中元素的中元素的q qi i作為作為MM的終態(tài)的終態(tài)構(gòu)造正規(guī)式構(gòu)造正規(guī)式b(ab|bb)*ab的的DFA（

12、1）NFA初態(tài)初態(tài)終態(tài)終態(tài)xy初態(tài)初態(tài)終態(tài)終態(tài)xya a1b b23ab|bbab|bb4b b初態(tài)初態(tài)終態(tài)終態(tài)xya a1b b234b bbbbb初態(tài)初態(tài)終態(tài)終態(tài)xya a1b b23a a4b bb b56b bb babab（2）DFA1、-closure(x)=-closure(x)=xx =q=q0 0 初態(tài)初態(tài)終態(tài)終態(tài)xya a1b b23a a4b bb b56b bb bKK q q0 0 2 2、對、對KK中未標(biāo)記狀態(tài)中未標(biāo)記狀態(tài)q q0 0做：做：move(qmove(q0 0,a)=move(x,a)=,a)=move(x,a)=move(qmove(q0 0,b)=m

13、ove(x,b)= 1,b)=move(x,b)= 1-closure(1)=-closure(1)=1,2,3=1,2,3=q q1 f(qf(q0 0,b)=,b)= q1KK q0q0,q1,q13、對、對K中未標(biāo)記狀態(tài)中未標(biāo)記狀態(tài)q1做：做：初態(tài)初態(tài)終態(tài)終態(tài)xya a1b b23a a4b bb b56b bb bmove(q1,a)=move(1,2,3,a)=4,6-closure(4,6)=4,6=q2f(q1,a)=q2move(q1,b)= move(1,2,3,b)=5-closure(5)=5=q3f(q1,b)=q3KK q0q0, ,q1q1,q2,q3,q2,q34

14、、對、對K中未標(biāo)記狀態(tài)中未標(biāo)記狀態(tài)q2做：做：move(q2,a)=初態(tài)初態(tài)終態(tài)終態(tài)xya a1b b23a a4b bb b56b bb bmove(4,6,a)=move(q2,b)= move(4,6,b)=2,y-closure(2,y)=2,3,y=q4f(q2,b)=q4KK q0q0, ,q1q1, ,q2q2,q3,q4,q3,q4初態(tài)初態(tài)終態(tài)終態(tài)xya a1b b23a a4b bb b56b bb b5、對、對K中未標(biāo)記狀態(tài)中未標(biāo)記狀態(tài)q3做：做：move(q3,a)=move(5,a)=move(q3,b)= move(5,b)=2-closure(2)=2,3=q5f(

15、q3,b)=q5KK q0q0, ,q1q1, ,q2q2, ,q3q3,q4,q5,q4,q5初態(tài)初態(tài)終態(tài)終態(tài)xya a1b b23a a4b bb b56b bb b6、對、對K中未標(biāo)記狀態(tài)中未標(biāo)記狀態(tài)q4做：做：move(q4,a)=move(2,3,y,a)=4,6-closure(4,6)=4,6=q2f(q4,a)=q2move(q4,b)= move(2,3,y,b)=5-closure(5)=5=q3f(q4,b)=q3KK q0q0, ,q1q1, ,q2q2, ,q3q3, ,q4q4,q5,q5初態(tài)初態(tài)終態(tài)終態(tài)xya a1b b23a a4b bb b56b bb b7、

16、對、對K中未標(biāo)記狀態(tài)中未標(biāo)記狀態(tài)q5做：做：move(q5,a)=move(2,3,a)=4,6-closure(4,6)=4,6=q2f(q5,a)=q2move(q5,b)= move(2,3,b)=5-closure(5)=5=q3f(q5,b)=q3KK q0q0, ,q1q1, ,q2q2, ,q3q3, ,q4q4, ,q5q5等價的等價的DFA M DFA M 如下如下KK q q0 0 , q, q1 1 , , q q2 2 ,q,q3 3 , , q q4 4 ,q,q5 5f(q0,a)=,f(q0,b)=q1f(q1,a)=q2,f(q1,b)=q3f(q2,a)=,f

17、(q2,b)=q4f(q3,a)=,f(q3,b)=q5f(q4,a)=q2,f(q4,b)=q3Zq4f(q5,a)=q2,f(q5,b)=q3NFA MNFA M轉(zhuǎn)換為轉(zhuǎn)換為DFA M DFA M 的過程的過程IIaIbq0=x=xq1 =1,2,3=1,2,3q2 =4,6=4,6q3 =5=5q4 =2,3,y=2,3,yq1 =1,2,3=1,2,3q2 =4,6=4,6q3 =5=5q2 =2,3,y=2,3,yq5=2,3=2,3q3 =5=5f(q0,b)=q1f(q1,a)=q2,f(q1,b)=q3f(q2,b)=q4f(q3,b)=q5f(q4,a)=q2,f(q4,b)

18、=q3f(q5,a)=q2,f(q5,b)=q3q5 =2,3=2,3q2 =4,6=4,6q2 =4,6=4,6q3 =5=5DFA M DFA M 的狀態(tài)圖的狀態(tài)圖f(q0,a) = , f(q0,b) =q1, f(q1,a) =q2, f(q1,b) =q3, f(q2,a) = , f(q2,b) =q4, f(q3,a) = , f(q3,b) =q5, f(q4,a) =q2, f(q4,b) =q3, f(q5,a) =q2, f(q5,b) =q3bq0初態(tài)初態(tài)bq1q2aq3b0q4終態(tài)終態(tài)q5babab最小化q0初態(tài)初態(tài)bq1q2aq3b0q4 終態(tài)終態(tài)q5babab1、

19、初始劃分由兩個子集組成，即：、初始劃分由兩個子集組成，即：q q0 0,q,q1 1,q,q2 2,q,q3 3，q q5 5( (非終態(tài)）非終態(tài)）q q4 4（終態(tài)）（終態(tài)）b2、考查子集、考查子集q0,q1,q2,q3,q5 q q0 0,q,q1 1,q,q2 2,q,q3,3,q q5 5 a a：=q=q2 2 q0,q1,q2,q3,q5 q q0 0,q,q1 1,q,q2 2,q,q3,3,q q5 5 b b：=q1,q3,q4,q5 q q4 4 q0初態(tài)初態(tài)bq1q2aq3b0q4 終態(tài)終態(tài)q5bababb q q0 0,q,q1 1,q,q2 2,q,q3,3,q q5

20、 5 ： q0,q1,q3,q5 qq2 2 = q0,q1,q3,q5 q0,q1,q3,q5 , ,q q2 2，q q4 4 q0初態(tài)初態(tài)bq1q2aq3b0q4 終態(tài)終態(tài)q5bababb3、考查子集、考查子集q0,q1,q3,q5 q q1 1,q,q5 5 a a：=q=q2 2 q q0 0,q,q1 1,q,q3,3,q q5 5 b b：=q1,q3,q5 q0,q1,q3,q5 子集子集 q0,q1,q3,q5 再分割再分割: :f(q0,a) = f(q3,a) = q q0 0, ,q q3 3, ,a a：= q q0 0, ,q q3 3, , q q1 1,q,q5

21、 5 q0初態(tài)初態(tài)bq1q2aq3b0q4 終態(tài)終態(tài)q5bababbq0初態(tài)初態(tài)bq1q2aq3b0q4 終態(tài)終態(tài)q5bababq0初態(tài)初態(tài)bq20q4ab q q0 0, ,q q3 3, , q q1 1,q,q5 5 qq2 2 qq4 4 q1abbb考察字符串：bab左圖識別過程：q0-q1-q2-q4右圖識別過程：q0-q1-q2-q4考察字符串：bbbab左圖識別過程：q0-q1-q3-q5-q2-q4右圖識別過程：q0-q1-q0-q1-q2-q4q0初態(tài)初態(tài)bq20q4abq1abbq0初態(tài)初態(tài)bq1q2aq3b0q4 終態(tài)終態(tài)q5bababb設(shè)字母表設(shè)字母表a,ba,b上的

22、正規(guī)式上的正規(guī)式R=(a|ba)R=(a|ba)* *1 1、構(gòu)造、構(gòu)造NFA MNFA M , ,使得使得L(ML(M )=L(R) ; )=L(R) ;2 2、將、將NFA MNFA M確定化，得到確定化，得到DFA M DFA M 使得使得L(ML(M )=L(M); )=L(M);3 3、將、將DFA MDFA M最小化。最小化。構(gòu)造構(gòu)造NFA MNFA Mxy1aR=(a|ba)*2ba將將NFA MNFA M確定化確定化xy12baa1、-closure(x)=-closure(x)=x,1,y=q0 x,1,y=q0 K K q q0 0 2、對、對K中未標(biāo)記狀態(tài)中未標(biāo)記狀態(tài)q0

23、做：做：(1)(1)標(biāo)記標(biāo)記q q0 0(2)move(q(2)move(q0 0,a)=move(,a)=move(x,1,y,a)=1,a)=1-closure(1)= -closure(1)= 1,y=q11,y=q1 f(qf(q0 0,a)=q1,a)=q1xy12baamove(q0,b)=move(x,1,y,b)=move(x,1,y,b)= 22-closure(2)= -closure(2)= 2=q22=q2 q q0 0 =x,1,y=x,1,y， q q1 1 =1,y =1,y f(qf(q0 0,b)=q2,b)=q2KK q q0 0 , , q q1 1 ,

24、, q q2 2 3 3、對、對KK中未標(biāo)記狀態(tài)中未標(biāo)記狀態(tài)q q1 1做：做：(1)標(biāo)記標(biāo)記q1(2)move(q1,a)= move(1,y,a)= 1-closure(1)= -closure(1)= 1,y=q11,y=q1 f(qf(q1 1,a)=q1,a)=q1 q q0 0 =x,1,y=x,1,y， q q1 1 =1,y =1,y， q2=2xy12baamove(q1,b)= move(1,y,b)=2 f(qf(q1 1,b)=q2,b)=q2KK q q0 0 , , q q1 1 , , q q2 2 4 4、對、對KK中未標(biāo)記狀態(tài)中未標(biāo)記狀態(tài)q q2 2做：做：(

25、1)標(biāo)記標(biāo)記q2(2)move(q2,a)= move(2,a)= 1-closure(1)= -closure(1)= 1,y=q11,y=q1 f(qf(q2 2,a)=q1,a)=q1move(q2,b)= move(2,b)= 等價的等價的DFAM如下如下 f(qf(q0 0,a)=q1,a)=q1 f(qf(q0 0,b)=q2,b)=q2 f(qf(q1 1,a)=q1,a)=q1 f(qf(q1 1,b)=q2,b)=q2 f(qf(q2 2,a)=q1,a)=q1NFAM轉(zhuǎn)換為轉(zhuǎn)換為DFAM的過程的過程 f(qf(q0 0,a)=q1,a)=q1 f(qf(q0 0,b)=q2

26、,b)=q2 f(qf(q1 1,a)=q1,a)=q1 f(qf(q1 1,b)=q2,b)=q2 f(qf(q2 2,a)=q1,a)=q1IIaIbq0=x,1,yq1=1,yq2=2q1=1,yq1=1,yq2=2q2=2q1=1,yDFAM的狀態(tài)圖的狀態(tài)圖 f(qf(q0 0,a)=q1,a)=q1 f(qf(q0 0,b)=q2,b)=q2 f(qf(q1 1,a)=q1,a)=q1 f(qf(q1 1,b)=q2,b)=q2 f(qf(q2 2,a)=q1,a)=q1q20q00q1初態(tài)初態(tài)ababa將DFA M最小化q20q00q1初態(tài)初態(tài)ababa1、初始劃分由兩個子、初始劃

27、分由兩個子集組成，即：集組成，即：q q0 0,q,q1 1( (終態(tài)）終態(tài)）q q2 2（非終態(tài)）（非終態(tài)）q q0 0,q,q1 1a a= = qq1 1 q q0 0,q,q1 1b b= = qq2 2 2 2、考查子集、考查子集q q0 0,q,q1 1q20q00q1初態(tài)初態(tài)ababaq q0 0,q,q1 1a a= = qq1 1 q q0 0,q,q1 1b b= = qq2 2 子集子集q q0 0,q,q2 2不能再分割，即不能再分割，即q0,q1為等價狀態(tài)為等價狀態(tài)進行合并進行合并0q0q2初態(tài)初態(tài)終態(tài)終態(tài)aba第四章第四章自頂向下的語法分析自頂向下的語法分析（1 1

28、）消除直接左遞歸）消除直接左遞歸（2 2）消除間接左遞歸的算法）消除間接左遞歸的算法（3 3）FirstFirst集合和集合和FollowFollow集合的求解方法集合的求解方法（4 4）避免回溯的判斷方法）避免回溯的判斷方法（5 5）簡單回溯的消除方法）簡單回溯的消除方法（6 6）LL(1)LL(1)分析表的構(gòu)造算法分析表的構(gòu)造算法（7 7）LL(1)LL(1)分析方法分析方法一、消除左遞歸一、消除左遞歸消除間接左遞歸的算法消除間接左遞歸的算法消除直接左遞歸消除直接左遞歸引進新的非終結(jié)符引進新的非終結(jié)符提公因子提公因子1. 引進新的非終結(jié)符的方法U:=Ux1|Ux2|Uxm|y1|y2|yn

29、左遞歸規(guī)則形如：左遞歸規(guī)則形如：U:=x1U|x2U|xmU|左遞歸規(guī)則左遞歸規(guī)則不以不以U開頭開頭方法：方法：引進新的非終結(jié)符號引進新的非終結(jié)符號U改改寫寫U:=y1U|y2U|ynU2.提公因子的方法提公因子的方法U:=(y1|y2|yn)U:=Ux1|Ux2|Uxm|y1|y2|yn左遞歸規(guī)則形如：左遞歸規(guī)則形如：左遞歸規(guī)則左遞歸規(guī)則不以不以U開頭開頭改改寫寫x1|x2|xm3.消除間接左遞歸的算法步驟（消除間接左遞歸的算法步驟（1）(1)(1)將文法中所有的非終結(jié)符號排序?qū)⑽姆ㄖ兴械姆墙K結(jié)符號排序: : U U1 1,U,U2 2, ,U,Un n; ;消除間接左遞歸的算法步驟（消除

30、間接左遞歸的算法步驟（2）i=2i=n?j=1Yj=i-1?Y存在存在Ui:=U:=Ujy y?Y如果如果U Uj:= := x1| |x2| | |xk則則U Ui:= := x1y| |x2y| | |xky消除消除U Ui i 規(guī)則中的直接左遞歸規(guī)則中的直接左遞歸j=j+1NNi=i+1N結(jié)束結(jié)束考查是否存在排在考查是否存在排在后面的非終結(jié)符后面的非終結(jié)符（ Ui i ）定義為定義為（：（：= =）以排在）以排在U Ui i 前面的非終結(jié)前面的非終結(jié)符號（符號（U Uj j）開頭的）開頭的規(guī)則。規(guī)則。消除間接左遞歸的算法步驟（消除間接左遞歸的算法步驟（3）(3)消去多余規(guī)則消去多余規(guī)則(

31、壓縮文法壓縮文法)此算法要求此算法要求1）文法沒有回路）文法沒有回路(U2）文法不存在規(guī)則）文法不存在規(guī)則U:=U)FIRST集的定義集的定義*符號串符號串x推導(dǎo)推導(dǎo)終結(jié)頭符號集終結(jié)頭符號集FIRST(x)= a|xaaVTxFIRST(x)文法避免回溯的條件文法避免回溯的條件多選規(guī)則：多選規(guī)則：U:=xU:=x1 1|x|x2 2| |x|xn n文法避免回溯的條件文法避免回溯的條件: :不含空規(guī)則不含空規(guī)則FIRST(xFIRST(xi i ) ) FIRST( xFIRST( xj j ) = ) = (ij)(ij)FOLLOW(U)FOLLOW(U)的定義的定義*非終結(jié)符號非終結(jié)符號

32、U U的的后繼后繼終結(jié)終結(jié)符號集。符號集。FOLLOW(U)= aFOLLOW(U)= a |Z|ZU Ua a aVaVT T識別符號識別符號特別地特別地：Z ZU U# FOLLOW(U)# FOLLOW(U)輸入結(jié)束符輸入結(jié)束符求求FOLLOW(U)FOLLOW(U)的算法步驟的算法步驟1)1)1)1) # #FOLLOW(Z);FOLLOW(Z);識別符號識別符號求求FOLLOW(U)FOLLOW(U)的算法步驟的算法步驟2)2)2) A:=2) A:=U UFIRST()-FIRST()-FOLLOW(U)FOLLOW(U)文法滿足避免回溯的條件文法滿足避免回溯的條件*U:=xU:=

33、x1 1|x|x2 2| |x|xn n1)FIRST(x1)FIRST(xi i)FIRST(x)FIRST(xj j)= (ij)= (ij)2)2)若若x xj jFIRST(xFIRST(xi i)FOLLOW(U)= (ij)FOLLOW(U)= (ij)非空規(guī)則非空規(guī)則消除回溯的簡單方法消除回溯的簡單方法U:=xU:=xi i|x|xj jFIRST(xFIRST(xi i)FIRST(x)FIRST(xj j) ) =a=aU:=xU:=xi i|x|xj j改寫改寫U:=aW|aVU:=aW|aV提取提取a aU:=a(W|V)U:=a(W|V)引入引入X XU:=aXU:=a

34、XX:=W|VX:=W|VLL(1)分析表分析表M的結(jié)構(gòu)的結(jié)構(gòu)行標(biāo)題行標(biāo)題非終結(jié)符號非終結(jié)符號U列標(biāo)題列標(biāo)題終結(jié)符號終結(jié)符號a結(jié)束符結(jié)束符#MU,a規(guī)則規(guī)則當(dāng)當(dāng)U面臨輸入符號面臨輸入符號a時應(yīng)選擇的規(guī)則時應(yīng)選擇的規(guī)則出錯標(biāo)志出錯標(biāo)志構(gòu)造構(gòu)造LL(1)分析表分析表M的算法的算法(3)其它均置其它均置ERROR規(guī)則規(guī)則U:=x(1)aFIRST(x)U:=xMU,a(2)FIRST(x)U:=xMU,b MU,#FOLLOW(U)空空LL(1)分析方法基本思想分析方法基本思想從從左左到右掃描源程序到右掃描源程序從識別符號開始生成句子的最從識別符號開始生成句子的最左左推導(dǎo)推導(dǎo)只要向前查看只要向前查看

35、一個一個輸入符號輸入符號便能確定當(dāng)前應(yīng)選擇的規(guī)則便能確定當(dāng)前應(yīng)選擇的規(guī)則LL(1)方法方法LL(1)分析方法的實現(xiàn)分析方法的實現(xiàn)LL(1)方法方法LL(1)分析表分析表M符號棧符號棧SK: 符號棧符號棧S的棧頂指針的棧頂指針J:輸入串輸入串R的指針的指針實現(xiàn)步驟實現(xiàn)步驟(3)棧頂元素棧頂元素=(1)棧頂元素棧頂元素當(dāng)前符號當(dāng)前符號匹配匹配k:=k-1j:=j+1(2)棧頂元素棧頂元素SkVN當(dāng)前輸入符號為當(dāng)前輸入符號為Rj查查M表表MSk,Rj元素元素Sk:=x1x2xnx1x2xn代替代替Sk入棧順序入棧順序由右向左由右向左輸入符號輸入符號= #成功成功S棧棧Skxnx2x1棧頂元素出棧棧頂元素出棧輸入下一符號輸入下一符號出棧出棧P78#4P78#4(續(xù))（2）不是不是LL(1)文法文法，文法中有直接左遞歸的規(guī)，文法中有直接左遞歸的規(guī)則：則：（3）消除直接左遞歸消除直接左遞歸：引進新的非終結(jié)符號引進新的非終結(jié)符號BP78#4(續(xù))（4）構(gòu)造構(gòu)造LL(1)分析表分析表abe#ABB AaABeAABbBBbBB對文法GS:(1)(1)句子句子(a,(a,a)(a,(a,a)的最左推導(dǎo)：的最左推導(dǎo)：S S ( (T T) )( (T T,S) ,S) ( (S S,S),S)(a,(a,S S)