大連海事大學(xué)《編譯原理》期末總復(fù)習(xí)講述

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

2、n語(yǔ)法樹：語(yǔ)法樹： SSS*SS+aaaP28#4n只含有4個(gè)符號(hào)的句子：Z =U0 V1U =Z1 1V =Z0 0P28#5S =AB A =aA B =bBcbc A =aA描述的語(yǔ)言描述的語(yǔ)言: an|n=0B =bBcbc描述的語(yǔ)言描述的語(yǔ)言: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的語(yǔ)法樹：的語(yǔ)法樹： EE+TTE+TT*FFi短語(yǔ)：短語(yǔ)：T+T*F+i,T+T*F簡(jiǎn)單短語(yǔ)：簡(jiǎn)單短語(yǔ)：T*F， T ，i句柄：句柄： T 已知文法已知文法GE:GE:E:=E+T|TE

3、:=E+T|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ǔ)法樹；、畫出相應(yīng)的語(yǔ)法樹；( (注意：相同的葉子節(jié)點(diǎn)用注意：相同的葉子節(jié)點(diǎn)用不同的下標(biāo)加以區(qū)分，如：不同的下標(biāo)加以區(qū)分，如：i1 i1、i2i2、i3i3) )3 3、指出該句子所有的短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄。、指出該句子所有的短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄。存在的問(wèn)題存在的問(wèn)題n給出的推導(dǎo)不是規(guī)范推導(dǎo)；給出的推導(dǎo)不是規(guī)范推導(dǎo)；n一次使用多條規(guī)則；一次使用多條規(guī)則；n沒有標(biāo)明句柄所在的位置；沒有標(biāo)明句柄所在的位置；n不是從文

4、法的開始符號(hào)進(jìn)行推導(dǎo)；不是從文法的開始符號(hào)進(jìn)行推導(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)的語(yǔ)法樹的語(yǔ)法樹短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄為

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

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

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

8、，畫一條從結(jié)的規(guī)則，畫一條從結(jié)點(diǎn)點(diǎn)W指向結(jié)點(diǎn)指向結(jié)點(diǎn)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

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

10、Z)構(gòu)造相應(yīng)的確定的有限自動(dòng)機(jī)構(gòu)造相應(yīng)的確定的有限自動(dòng)機(jī): : 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）對(duì)于）對(duì)于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 q

11、i i ；對(duì)于每一個(gè)對(duì)于每一個(gè)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)為止。至少含有一個(gè)至少含有一個(gè)Z Z中元素的中元素的q qi i作為作為MM的終態(tài)的終態(tài)構(gòu)造正規(guī)式構(gòu)造正規(guī)式b(ab|bb)*

12、ab的的DFA（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、對(duì)、對(duì)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(q

13、0 0,b)=move(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、對(duì)、對(duì)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 =q2 f(q1,a) =q2move(q1,b)= move(1,2,3,b)=5-closure(5)= 5 =q3 f(q1,b) =q3KK q0q0, ,q

14、1q1,q2,q3,q2,q34、對(duì)、對(duì)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 =q4 f(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、對(duì)、對(duì)K中未標(biāo)記狀態(tài)中未標(biāo)記狀態(tài)q3做：做：move(q3,a)=move(5,a)=move(q3,b)= move(5,b)=2

15、-closure(2)= 2,3 =q5 f(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、對(duì)、對(duì)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 =q2 f(q4,a) =q2move(q4,b)= move(2,3,y,b)=5-closure(5)= 5 =q3 f(q4,b) =q3KK q0q0, ,q1q1, ,q2q2, ,q3q3, ,q4q4,q5,q5初態(tài)初態(tài)終態(tài)終

16、態(tài)xya a1b b23a a4b bb b56b bb b7、對(duì)、對(duì)K中未標(biāo)記狀態(tài)中未標(biāo)記狀態(tài)q5做：做：move(q5,a)=move(2,3,a)=4,6-closure(4,6)= 4,6 =q2 f(q5,a) =q2move(q5,b)= move(2,3,b)=5-closure(5)= 5 =q3 f(q5,b) =q3KK q0q0, ,q1q1, ,q2q2, ,q3q3, ,q4q4, ,q5q5等價(jià)的等價(jià)的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) =

17、, f(q0,b) =q1f(q1,a) =q2, f(q1,b) =q3f(q2,a) = , f(q2,b) =q4f(q3,a) = , f(q3,b) =q5f(q4,a) =q2, f(q4,b) =q3Z q4 f(q5,a) =q2, f(q5,b) =q3NFA MNFA M轉(zhuǎn)換為轉(zhuǎn)換為DFA M DFA M 的過(guò)程的過(guò)程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

18、) =q1f(q1,a) =q2, f(q1,b) =q3f(q2,b) =q4 f(q3,b) =q5f(q4,a) =q2, f(q4,b) =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,

19、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、初始劃分由兩個(gè)子集組成，即：、初始劃分由兩個(gè)子集組成，即：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,q

20、4,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 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 再分割再分割:

21、 :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 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左圖識(shí)別過(guò)程：q0-q1-q2-q4右圖識(shí)別過(guò)程：q0-q1-q2-q4考察字符串：bbbab左圖識(shí)別過(guò)程：q0-q1-q3-q5-q2-q4右圖識(shí)別過(guò)程：q0-q1-q

22、0-q1-q2-q4q0初態(tài)初態(tài)bq20q4abq1abbq0初態(tài)初態(tài)bq1q2aq3b0q4 終態(tài)終態(tài)q5bababb設(shè)字母表設(shè)字母表a,ba,b上的正規(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確定化確定化xy12ba

23、a1、-closure(x)=-closure(x)=x,1,y=q0 x,1,y=q0 K K q q0 0 2、對(duì)、對(duì)K中未標(biāo)記狀態(tài)中未標(biāo)記狀態(tài)q0做：做：(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

24、 =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 , , q q2 2 3 3、對(duì)、對(duì)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

25、,b)=q2,b)=q2KK q q0 0 , , q q1 1 , , q q2 2 4 4、對(duì)、對(duì)KK中未標(biāo)記狀態(tài)中未標(biāo)記狀態(tài)q q2 2做：做：(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)= 等價(jià)的等價(jià)的DFA M 如下如下 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

26、(qf(q2 2,a)=q1,a)=q1NFA M 轉(zhuǎn)換為轉(zhuǎn)換為DFA M 的過(guò)程的過(guò)程 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)=q1IIaIbq0 =x,1,yq1 =1,yq2=2q1 =1,yq1 =1,yq2=2q2=2q1 =1,yDFA M 的狀態(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

27、)=q2,b)=q2 f(qf(q2 2,a)=q1,a)=q1q20q00q1初態(tài)初態(tài)ababa將DFA M最小化q20q00q1初態(tài)初態(tài)ababa1、初始劃分由兩個(gè)子、初始劃分由兩個(gè)子集組成，即：集組成，即：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

28、0,q,q2 2不能再分割，即不能再分割，即q0,q1為等價(jià)狀態(tài)為等價(jià)狀態(tài)進(jìn)行合并進(jìn)行合并0q0q2初態(tài)初態(tài)終態(tài)終態(tài)aba第四章第四章 自頂向下的語(yǔ)法分析自頂向下的語(yǔ)法分析（1 1）消除直接左遞歸）消除直接左遞歸（2 2）消除間接左遞歸的算法）消除間接左遞歸的算法（3 3）FirstFirst集合和集合和FollowFollow集合的求解方法集合的求解方法（4 4）避免回溯的判斷方法）避免回溯的判斷方法（5 5）簡(jiǎn)單回溯的消除方法）簡(jiǎn)單回溯的消除方法（6 6）LL(1)LL(1)分析表的構(gòu)造算法分析表的構(gòu)造算法（7 7）LL(1)LL(1)分析方法分析方法一、消除左遞歸一、消除左遞歸消除間接左

29、遞歸的算法消除間接左遞歸的算法消除直接左遞歸消除直接左遞歸引進(jìn)新的非終結(jié)符引進(jìn)新的非終結(jié)符提公因子提公因子1. 引進(jìn)新的非終結(jié)符的方法U:=Ux1|Ux2|Uxm|y1|y2|yn左遞歸規(guī)則形如：左遞歸規(guī)則形如：U:=x1 U| x2 U| xm U|左遞歸規(guī)則左遞歸規(guī)則不以不以U開頭開頭方法：方法：引進(jìn)新的非終結(jié)符號(hào)引進(jìn)新的非終結(jié)符號(hào)U改改寫寫U:= y1 U | y2 U | yn U 2.提公因子的方法提公因子的方法U:=(y1|y2|yn)U:=Ux1|Ux2|Uxm|y1|y2|yn左遞歸規(guī)則形如：左遞歸規(guī)則形如：左遞歸規(guī)則左遞歸規(guī)則不以不以U開頭開頭改改寫寫x1|x2|xm3.消除

30、間接左遞歸的算法步驟（消除間接左遞歸的算法步驟（1）(1)(1)將文法中所有的非終結(jié)符號(hào)排序?qū)⑽姆ㄖ兴械姆墙K結(jié)符號(hào)排序: : U U1 1,U,U2 2, ,U,Un n; ;消除間接左遞歸的算法步驟（消除間接左遞歸的算法步驟（2）i=2i=n?j=1Yj=i-1?Y存在存在Ui :=U:=Ujy y?Y如果如果U Uj:= := x1 | | x2 | | | | xk則則U Ui:= := x1 y| | x2 y | | | | xk y消除消除U Ui i 規(guī)則中的直接左遞歸規(guī)則中的直接左遞歸j=j+1NNi=i+1N結(jié)束結(jié)束考查是否存在排在考查是否存在排在后面的非終結(jié)符后面的非終結(jié)

31、符（ Ui i ）定義為定義為（：（：= =）以排在）以排在U Ui i 前面的非終結(jié)前面的非終結(jié)符號(hào)（符號(hào)（U Uj j）開頭的）開頭的規(guī)則。規(guī)則。消除間接左遞歸的算法步驟（消除間接左遞歸的算法步驟（3）(3)消去多余規(guī)則消去多余規(guī)則(壓縮文法壓縮文法)此算法要求此算法要求1）文法沒有回路）文法沒有回路(U2）文法不存在規(guī)則）文法不存在規(guī)則U:=U) FIRST集的定義集的定義*符號(hào)串符號(hào)串x推導(dǎo)推導(dǎo)終結(jié)頭符號(hào)集終結(jié)頭符號(hào)集FIRST(x)= a|xa aVTxFIRST(x)文法避免回溯的條件文法避免回溯的條件多選規(guī)則：多選規(guī)則：U:=xU:=x1 1|x|x2 2| |x|xn n文法避

32、免回溯的條件文法避免回溯的條件: :不含空規(guī)則不含空規(guī)則FIRST(xFIRST(xi i ) ) FIRST( xFIRST( xj j ) = ) = (ij)(ij)FOLLOW(U)FOLLOW(U)的定義的定義*非終結(jié)符號(hào)非終結(jié)符號(hào)U U的的后繼后繼終結(jié)終結(jié)符號(hào)集。符號(hào)集。FOLLOW(U)= aFOLLOW(U)= a |Z|ZU Ua a aVaVT T識(shí)別符號(hào)識(shí)別符號(hào)特別地特別地：Z ZU U# FOLLOW(U)# FOLLOW(U)輸入結(jié)束符輸入結(jié)束符求求FOLLOW(U)FOLLOW(U)的算法步驟的算法步驟1)1)1)1) # #FOLLOW(Z);FOLLOW(Z);

33、識(shí)別符號(hào)識(shí)別符號(hào)求求FOLLOW(U)FOLLOW(U)的算法步驟的算法步驟2)2)2) A:=2) A:=U UFIRST()-FIRST()-FOLLOW(U)FOLLOW(U)文法滿足避免回溯的條件文法滿足避免回溯的條件*U:=xU:=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ī)則消除回溯的簡(jiǎn)單方法消除回溯的簡(jiǎn)單方法U:=xU:=xi i|x|xj jFI

34、RST(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:=aXX:=W|VX:=W|V LL(1)分析表分析表M的結(jié)構(gòu)的結(jié)構(gòu)行標(biāo)題行標(biāo)題非終結(jié)符號(hào)非終結(jié)符號(hào)U列標(biāo)題列標(biāo)題終結(jié)符號(hào)終結(jié)符號(hào)a結(jié)束符結(jié)束符#MU,a規(guī)則規(guī)則當(dāng)當(dāng)U面臨輸入符號(hào)面臨輸入符號(hào)a時(shí)應(yīng)選擇的規(guī)則時(shí)應(yīng)選擇的規(guī)則出錯(cuò)標(biāo)志出錯(cuò)標(biāo)志構(gòu)造構(gòu)造LL(1)分析表分析表M的算法的算法(3)其它均置其它均置ERROR規(guī)則規(guī)則U:=x(1)aFIRST(x)U:=x

35、MU,a(2)FIRST(x)U:=xMU,b MU,#FOLLOW(U)空空LL(1)分析方法基本思想分析方法基本思想從從左左到右掃描源程序到右掃描源程序從識(shí)別符號(hào)開始生成句子的最從識(shí)別符號(hào)開始生成句子的最左左推導(dǎo)推導(dǎo)只要向前查看只要向前查看一個(gè)一個(gè)輸入符號(hào)輸入符號(hào)便能確定當(dāng)前應(yīng)選擇的規(guī)則便能確定當(dāng)前應(yīng)選擇的規(guī)則LL(1)方法方法LL(1)分析方法的實(shí)現(xiàn)分析方法的實(shí)現(xiàn)LL(1)方法方法LL(1)分析表分析表M符號(hào)棧符號(hào)棧SK: 符號(hào)棧符號(hào)棧S的棧頂指針的棧頂指針J:輸入串輸入串R的指針的指針實(shí)現(xiàn)步驟實(shí)現(xiàn)步驟(3)棧頂元素棧頂元素=(1)棧頂元素棧頂元素當(dāng)前符號(hào)當(dāng)前符號(hào)匹配匹配k:=k-1j:

36、=j+1(2)棧頂元素棧頂元素SkVN當(dāng)前輸入符號(hào)為當(dāng)前輸入符號(hào)為Rj查查M表表MSk,Rj元素元素Sk:=x1x2xnx1x2xn代替代替Sk入棧順序入棧順序由右向左由右向左輸入符號(hào)輸入符號(hào)= #成功成功S棧棧Skxnx2x1棧頂元素出棧棧頂元素出棧輸入下一符號(hào)輸入下一符號(hào)出棧出棧P78#4P78#4(續(xù))（2）不是不是LL(1)文法文法，文法中有直接左遞歸的規(guī)，文法中有直接左遞歸的規(guī)則：則：（3）消除直接左遞歸消除直接左遞歸：引進(jìn)新的非終結(jié)符號(hào)引進(jìn)新的非終結(jié)符號(hào)BP78#4(續(xù))（4）構(gòu)造構(gòu)造LL(1)分析表分析表abe#ABB A aABeA A B bBB bBB 對(duì)文法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) ) (a,(a,(T T) )(a,(a,(T T,S) ,S) (a,(a,(S S,S),S)(a,(a,(a,(a,S S) ) (a,(a,a)(a,(a,a)（2）改寫文法：消除直接左遞歸T T,S|S引入新的非終結(jié)符號(hào)引入新的非終結(jié)符號(hào)TT STT ,ST|改寫后的文法：改寫后的文法：S a| |(T)T STT ,ST|消除間接左遞歸后：消除間接左遞歸后：