上次課程內(nèi)容回顧.ppt

1,上次課程內(nèi)容回顧,一、二義性與二義性的消除 造成二義性的原因文法符號缺乏明確的優(yōu)先級和結(jié)合性 消除二義性的方法： 改寫二義文法為無二義文法 為文法符號規(guī)定優(yōu)先級和結(jié)合性 改變語言的結(jié)構(gòu)或書寫方式,二、語言與文法的分類 正規(guī)式、CFG、CSG 從計(jì)數(shù)問題看三者之間的關(guān)系,2,3.3.3 形式語言與自動機(jī)簡介,對0型文法施加以下第i條限制，即得到i型文法。 G的任何產(chǎn)生式（S除外）滿足|； G的任何產(chǎn)生式形如A，其中AN，(NT)*； G的任何產(chǎn)生式形如Aa或者AaB(或者ABa)，其中A和BN，aT。 ,文法、語言與自動機(jī),定義3.8 若文法G=(N，T，P，S)的每個(gè)產(chǎn)生式中，均有(NT)*，且至少含有一個(gè)非終結(jié)符，(NT)*，則稱G為0型文法。,3,3.3.3 形式語言與自動機(jī)簡介（續(xù)）,L3=anbncn|n1 L3=ambmcn|m,n1 （AAC AaAb|ab CcC|c） L3=akbmcn|k，m，n1 （a+b+c+ ）,例3.15 L3可用下述CSG描述： SaSBC (1) SaBC (2) CBBC (3) aBab (4) bBbb (5) bCbc (6) cCcc (7),句子akbkck 的推導(dǎo)： S =.= ak-1S(BC)k-1 (by 1) = ak(BC)k (by 2) =.= akBkCk (by 3) = akbBk-1Ck (by 4) =.= akbkCk (by 5) = akbkcCk-1 (by 6) =.= akbkck (by 7),結(jié)論：CSG、CFG、正規(guī)式能力遞減 但是：能力越強(qiáng)的文法，其文法的設(shè)計(jì)和自動機(jī)的構(gòu)造越困難 因此：語法分析僅用到CFG（除特別指出，文法即指CFG ）,再考察L3：,4,3.4 自上而下語法分析 3.4.1 自上而下分析的一般方法,用推導(dǎo)的方法分析輸入序列（記號流）： 對任何一個(gè)輸入序列，從S開始進(jìn)行最左推導(dǎo)，直到得到一個(gè)合法的句子或發(fā)現(xiàn)一個(gè)非法結(jié)構(gòu)。 在推導(dǎo)的過程中，從左到右掃描輸入序列，并試圖用一切可能的方法，自上而下建立它的分析樹。 自上而下分析是一種試探的過程，是反復(fù)使用不同產(chǎn)生式謀求與輸入序列匹配的過程。,5,3.4.1 自上而下分析的一般方法（續(xù)1）,例3.20 用下述文法分析輸入序列=cad：,S cAd A ab | a,問題： 若有A1|2，(公共左因子)，則會虛假匹配和大量回溯；造成分析效率低、語義動作難以恢復(fù)、以及出錯(cuò)位置的報(bào)告不確切等。 若有AA，(左遞歸)，則死循環(huán)使分析無法進(jìn)行下去。,重寫文法： 消除左遞歸，以避免陷入死循環(huán)； 提取左因子，以避免回溯。,6,3.4.2 消除左遞歸,定義3.9 若文法G中的非終結(jié)符A，對某個(gè)文法符號序列存在推導(dǎo)A=+A，則稱G是左遞歸的。若G中有形如AA的產(chǎn)生式，則稱該產(chǎn)生式對A直接左遞歸。 , 消除文法的直接左遞歸 考慮： AA| 產(chǎn)生的語言：*,替換為：AA AA| 消除了一個(gè)直接左遞歸,7, 消除文法的直接左遞歸(續(xù)1),A A1|A2|.|Am|1|2|.|n 其中i非空，j均不以A開始。然后用下述產(chǎn)生式代替A產(chǎn)生式：,若i為空，則形成一個(gè)有環(huán)的A產(chǎn)生式,算法3.1 消除直接左遞歸,A 1 A |2 A | .|n A A 1 A | 2 A | . | m A | ,輸入 G中所有的A產(chǎn)生式(含直接左遞歸) 輸出 等價(jià)的不含直接左遞歸的G 方法 首先，整理A產(chǎn)生式為如下形式：,8, 消除文法的直接左遞歸(續(xù)1),例3.17 用算法3.1消除算術(shù)表達(dá)式文法的直接左遞歸：,E TE (1) E+TE| (2) (G3.4) T FT (3) T*FT| (4) F (E) |-F|id (5)(7),EE+T|T TT*F|F (G3.4) F(E)|-F|id,替換： AA| 為： A A AA|,關(guān)鍵：將實(shí)際文法符號對應(yīng)到A、和 具體到E產(chǎn)生式： E +T|T A ,9, 消除文法的直接左遞歸(續(xù)2),輸入序列：id+id*id,改寫的代價(jià),EE+T|T TT*F|F F(E)|-F|id (G3.4),E TE (1) E+TE| (2) T FT (3) T*FT| (4) F (E) |-F|id (5)(7) (G3.4),EE+E|E*E |(E)|-E|id (G3.2),What a mess!,10, 消除文法的左遞歸,文法：SAa|b AAc|Sd| S左遞歸(但不是直接左遞歸) 因?yàn)椋篠=Aa=Sda,核心思想：將不是直接左遞歸的非終結(jié)符右部展開到其他產(chǎn)生式中,for i in 2n loop for j in 1i-1 loop end loop; end loop; ,用Aj1|2|.|k的右部 替換每個(gè)形如AiAj產(chǎn)生式中的Aj, 得到新產(chǎn)生式：Ai1|2|.|k; 消除Ai產(chǎn)生式中的直接左遞歸;,算法3.2 消除左遞歸 輸入 無回路文法G 輸出 無左遞歸的等價(jià)文法G 方法 將非終結(jié)符合理排序：A1，A2，.，An;,11, 消除文法的左遞歸（續(xù)1）,例3.18 用算法3.2消除文法SAa|b AAc|Sd|中的左遞歸。,核心思想：將不是直接左遞歸的符號用其右部展開到其他產(chǎn)生式 關(guān)鍵步驟：合理排序非終結(jié)符：A1，A2，.，An; 用Aj1|2|.|k右部替換AiAj中的Aj 得到Ai1|2|.|k; 消除Ai產(chǎn)生式中的直接左遞歸;, 將S的右部展開在A中，得到： AAc|Aad|bd| 消除新產(chǎn)生式中的直接左遞歸，得到：,S Aa | b A bdA | A (G3.8) A cA | adA | ,12,3.4.3 提取左因子,當(dāng)不確定用A產(chǎn)生式的哪個(gè)候選項(xiàng)替換A時(shí)，可以重寫A產(chǎn)生式來推遲這種決定，直到看見足夠的輸入，能正確決定所需選擇為止。 這一過程被稱為提取左因子，它類似于有限自動機(jī)的確定化。,公共前綴：A 1|2,將： A 1|2 替換為： A A A1|2 它等價(jià)于： A (1|2 ) （對照算術(shù)表達(dá)式中的提取公因式）,S cAd A ab | a,13,3.4.3 提取左因子（續(xù)1）,算法3.3 提取文法的左因子 輸入 文法G 輸出 等價(jià)的無左因子文法G 方法 重復(fù)下述過程，直到所有A產(chǎn)生式候選項(xiàng)中不再有公共前綴,例3.20 考察懸空else文法：SiCtS|iCtSeS|a Cb 用算法3.3提取左因子，得到如下文法：,既有左遞歸又含左因子？ 先消除左遞歸。 （為什么？）,SiCtSS|a SeS| Cb,重排A產(chǎn)生式：A1|2| .|n|； 并用 AA| 和 A1|2| .|n取代原A產(chǎn)生式。 ,14,3.4.4 遞歸下降分析,直接以程序的方式模擬產(chǎn)生式產(chǎn)生語言的過程； 每個(gè)產(chǎn)生式對應(yīng)一個(gè)子程序，產(chǎn)生式右邊的非終結(jié)符對應(yīng)子程序調(diào)用，終結(jié)符則與輸入序列匹配； 它對文法的限制是不能有公共左因子和左遞歸； 它是一種非形式化的方法，只要能寫出子程序，用什么樣的方法和步驟均可。,15,穩(wěn)妥的笨方法：,遞歸下降分析的文法： LE;L| EE+T|E-T|T TT*F|T/F|T mod F|F F(E)|id|num,消除左遞歸后的等價(jià)文法: L E;L| E TE E+TE|-TE| T FT T*FT|/FT| mod FT| F (E)|id|num, 構(gòu)造狀態(tài)轉(zhuǎn)換圖且化簡,構(gòu)造文法的狀態(tài)轉(zhuǎn)換圖并且化簡； 將轉(zhuǎn)換圖轉(zhuǎn)化為EBNF表示； 從EBNF構(gòu)造子程序。,16,文法的狀態(tài)轉(zhuǎn)換圖 ：,每個(gè)非終結(jié)符對應(yīng)一個(gè)狀態(tài)轉(zhuǎn)換圖：,為非終結(jié)符A建立一個(gè)初態(tài)和一個(gè)終態(tài)； 為AX1X2.Xn構(gòu)造從初態(tài)到終態(tài)的路徑，邊標(biāo)記為X1，X2，.，Xn。 根據(jù)識別同一集合的原則，化簡轉(zhuǎn)換圖。,L E;L| E TE E+TE|-TE| T FT T*FT|/FT |mod FT| F (E)|id|num,文法狀態(tài)轉(zhuǎn)換圖：,17,狀態(tài)圖的化簡：,標(biāo)記為A的邊可等價(jià)為標(biāo)記的邊轉(zhuǎn)向A轉(zhuǎn)換圖的初態(tài)； 邊連接的兩個(gè)狀態(tài)可以合并； 標(biāo)記相同的路徑可以合并； 不可區(qū)分的狀態(tài)可以合并。,化簡E產(chǎn)生式：,1. 合并路徑：,2. 轉(zhuǎn)向E的初態(tài)：,3. 合并連接的節(jié)點(diǎn)：,4. 將E的轉(zhuǎn)換圖代入E ：,5.合并連接的節(jié)點(diǎn)：,6.合并相同路徑：,18,狀態(tài)圖的化簡（續(xù)1）,最終全部化簡的轉(zhuǎn)換圖：, 文法的擴(kuò)展BNF（EBNF）表示, ：重復(fù)0或若干次（while） ：可選擇（if或while） |：括弧( )之內(nèi)的或關(guān)系（case） ( )：改變運(yùn)算的優(yōu)先級和結(jié)合性 EBNF表示：,（F無需化簡，為什么？）,L E; E T (+|-) T T F (*|/|mod) F F ( E ) | id | num,19, 遞歸下降子程序,L E; E T (+|-) T T F (*|/|mod) F F ( E ) | id | num,procedure L is begin lookahead := lexan； while (lookahead/=eof)loop E; match(;); end loop; end L;,procedure E is begin T; while lookahead(+|-) loop match(lookahead); T; end loop; end E;,procedure F is begin case lookahead is ( : match(); E; match(); id : match(id); num : match(num); others : error(“syntax error2“); end case; end F;,20, 遞歸下降子程序（續(xù)）,再看左遞歸問題：,若存在產(chǎn)生式E E + id，則E的遞歸下降子程序如下： procedure E is begin E; match(+); match(id); end E; 此程序永不停機(jī)。,#include const int id=0; void match(int x); void E() cout “match E“ endl; E(); match(+); match(id); cout “match + and id“ endl; / 永遠(yuǎn)不執(zhí)行 void main() E();,同樣，文法中的公共左因子也會給遞歸下降分析造成困難。,結(jié)束（2007年4月3日）,21,上次課程內(nèi)容回顧,形式語言與自動機(jī)簡介 自上而下分析的一般方法：自上而下(用推導(dǎo)的方法建立分析樹)、從左到右(掃描輸入序列)； 自上而下分析對文法的限制：不能有左遞歸和左因子 消除左遞歸： 左遞歸與直接左遞歸（定義3.9） 基本公式（替換AA|為A A AA|） 消除直接左遞歸（算法3.1）和消除左遞歸（算法3.2） 提取左因子：合并公共前綴（算法3.3） 遞歸下降分析（一個(gè)非終結(jié)符是一個(gè)子程序） 構(gòu)造文法的狀態(tài)轉(zhuǎn)換圖并且化簡； 將轉(zhuǎn)換圖轉(zhuǎn)化為EBNF表示； 從EBNF構(gòu)造子程序。,22,3.4.5 預(yù)測分析器 3.4.5.1 非遞歸預(yù)測分析器的工作模式,預(yù)測分析器的核心概念： 分析方法：格局與格局變換 分析表+驅(qū)動器（模擬算法） 預(yù)測分析表的構(gòu)造 LL（文法、語言、分析器）,23, 預(yù)測分析表,L E;L| E TE E+TE|-TE| T FT T*FT|/FT|mod FT| F (E)|id|num,文法：,LE;L| EE+T|E-T|T TT*F|T/F|T mod F|F F(E)|id|num,MA, a的內(nèi)容：若當(dāng)前棧頂是非終結(jié)符A，下一輸入終結(jié)符是a，則MA, a指示下一步動作。 構(gòu)造,分析表(MA, a)：,24, 工作方式,放幻燈的方式： 每張“幻燈片”稱為一個(gè)格局。 分析從某個(gè)初始格局開始，經(jīng)過一系列的格局變化，最終到達(dá)接收格局，表明分析成功； 或者到達(dá)出錯(cuò)格局，表明發(fā)現(xiàn)一個(gè)語法錯(cuò)誤。,格局：格局是一個(gè)三元組 （棧內(nèi)容，當(dāng)前剩余輸入，改變格局的動作） top ip,改變格局的動作： 匹配終結(jié)符：若top=ip(但#)，則pop且next(ip)； 展開非終結(jié)符： 若top= X且MX, a=(X)，則pop且push()； 報(bào)告分析成功：若top=ip=#，則分析成功并結(jié)束； 報(bào)告出錯(cuò)：其它情況，調(diào)用錯(cuò)誤恢復(fù)例程。,25, 驅(qū)動器算法,算法3.4 非遞歸的預(yù)測分析 輸入 輸入序列和文法G的預(yù)測分析表M 輸出 若L(G)，得到的一個(gè)最左推導(dǎo)；否則指出一個(gè)錯(cuò)誤 方法 初始格局為: （#S，#，分析器的第一個(gè)動作）,令ip指向#中的第一個(gè)終結(jié)符，top指向S; loop x := top; a := ip; exit when x=#; - 分析成功 end loop; ,if x T then if x=a then pop(x); next(ip); - 匹配終結(jié)符 else error(1); - 出錯(cuò)：棧頂終結(jié)符不是a end if;,else if Mx, a = XY1Y2.Yk then pop(X); push(YkYk-1.Y2Y1);-展開產(chǎn)生式 else error(2); - 出錯(cuò)：產(chǎn)生式不匹配 end if; end if;,26,loop x := top; a := ip; if x T then if x=a then pop(x); next(ip); - 匹配終結(jié)符 else error(1); - 出錯(cuò)：棧頂終結(jié)符不是a end if; else if Mx, a = XY1Y2.Yk then pop(X); push(YkYk-1.Y2Y1);-展開產(chǎn)生式 else error(2); - 出錯(cuò)：產(chǎn)生式不匹配 end if; end if; exit when x=#; - 分析成功 end loop;, 用預(yù)測分析器分析句子,id+id*id;,27, 用預(yù)測分析器分析句子（續(xù)）,棧 當(dāng)前剩余輸入 動作 #L id+id*id;# pop(L), push(E;L) (LE;L) #L;E id+id*id;# pop(E), push(TE) (ETE) #L;ET id+id*id;# pop(T), push(FT) (TFT) #L;ETF id+id*id;# pop(F), push(id) (Fid) #L;ETid id+id*id;# pop(id), next(ip) id #L;ET +id*id;# pop(T) (T) #L;E +id*id;# pop(E), push(+TE) (E+TE) #L;ET+ +id*id;# pop(+), next(ip) + #L;ET id*id;# pop(T), push(FT) (TFT) #L;ETF id*id;# pop(F), push(id) (Fid) #L;ETid id*id;# pop(id), next(ip) id #L;ET *id;# pop(T), push(*FT) (T*FT) #L;ETF* *id;# pop(*), next(ip) * #L;ETF id;# pop(F), push(id) (Fid) #L;ETid id;# pop(id), next(ip) id #L;ET ;# pop(T) (T) #L;E ;# pop(E) (E) #L; ;# pop(;), next(ip) ; #L # pop(L) (L) # # 正確結(jié)束,28,3.4.5.2 構(gòu)造預(yù)測分析表,首先構(gòu)造FIRST集合與FOLLOW集合； 然后根據(jù)兩個(gè)集合構(gòu)造預(yù)測分析表。,定義3.11 非終結(jié)符A的FOLLOW集合如下: FOLLOW（A） = a |S=*.Aa.，aT， 若A是某句型的最右符號，則#FOLLOW（A）。 ,通俗地講，的FIRST集合就是從開始可以導(dǎo)出的文法符號序列中的開頭終結(jié)符。 而A的FOLLOW集合，就是從開始符號可以導(dǎo)出的所有含A的文法符號序列中緊跟A之后的終結(jié)符。,例如：FIRST(E)= (，id, num FOLLOW(E)= )，; ,L E;L| E TE E+TE|-TE| T FT T*FT|/FT|mod FT| F (E)|id|num,定義3.10 文法符號序列的FIRST集合為: FIRST()=a|=*a.，aT， 若=*，則FIRST()。 ,29,3.4.5.2 構(gòu)造預(yù)測分析表（續(xù)1）,算法3.5 計(jì)算X的FIRST集合 輸入 文法符號X 輸出 X的FIRST集合 方法 應(yīng)用下述規(guī)則：,若XT，則FIRST(X)=X； 若X是非終結(jié)符且有X，則加入到FIRST(X)； 若X是非終結(jié)符且有XY1Y2.Yk，并設(shè)Y0=，Yk+1=。那么對所有j(0jk)，若aFIRST(Yj+1)且FIRST(Yj),則加入a到FIRST(X)。 ,對任意文法符號序列X1X2.Xn，F(xiàn)IRST(X1X2.Xn)的計(jì)算方法與算法3.5中步驟3類似 即：FIRST(X1X2.Xn)是所有FIRST(Xi)(i=1,2,k)的并集 其中k為第一個(gè)具有性質(zhì)不屬于FIRST(Yj)或kn的文法符號 若kn，則FIRST(X1X2.Xn）,再考慮：FIRST(E)=FIRST(TE)=FIRST(FTE)= (，id, num ,L E;L| E TE E+TE|-TE| T FT T*FT|/FT|mod FT| F (E)|id|num,30,3.4.5.2 構(gòu)造預(yù)測分析表（續(xù)2）,算法3.6 計(jì)算所有非終結(jié)符的FOLLOW集合 輸入 文法G 輸出 G中所有非終結(jié)符的FOLLOW集合 方法 應(yīng)用下述規(guī)則:,步驟3的理解： 若 S =*Aa a緊跟A之后 則 =*Ba a也緊跟B之后 因?yàn)?FIRST() 使得B成為A產(chǎn)生式右部最右的文法符號 即 對任何aFOLLOW(A)，均有aFOLLOW(B),加入#到FOLLOW(S)，其中S是開始符號，#是輸入結(jié)束標(biāo)記 若有產(chǎn)生式AB，則除外，F(xiàn)IRST()的全體加入到FOLLOW(B)。 若有產(chǎn)生式AB或AB而FIRST()，則FOLLOW(A)的全體加入到FOLLOW(B)。 ,31,3.4.5.2 構(gòu)造預(yù)測分析表（續(xù)3）,例3.22 計(jì)算非終結(jié)符的FIRST 與FOLLOW。 提示：自下而上計(jì)算FIRST 自上而下計(jì)算FOLLOW(為什么?),L E;L| E TE E+TE|-TE| T FT T*FT|/FT|mod FT| F (E)|id|num,FIRST(F) = ( id num FIRST(T) = * / mod FIRST(T) = FIRST(F) = ( id num FIRST(E) = + - FIRST(E) = FIRST(T) = FIRST(F) = ( id num FIRST(L) = FIRST(E) = ( id num,FOLLOW(L) = # FOLL0W(E) = ) ; FOLLOW(E) = ) ; FOLLOW(T) = + - ; ) FOLLOW(T) = + - ; ) FOLLOW(F) = + - * / mod ) ;,32,3.4.5.2 構(gòu)造預(yù)測分析表（續(xù)4）,算法3.7 構(gòu)造預(yù)測分析表 輸入 文法G 輸出 分析表M 方法 應(yīng)用下述規(guī)則,對文法的每個(gè)產(chǎn)生式A，執(zhí)行2和3； 對FIRST()的每個(gè)終結(jié)符a，加入到MA，a； 若FIRST()，則FOLLOW(A)每個(gè)終結(jié)符b（包括#），加入到MA，b； M中其它沒有定義的條目均是error。 ,MA，a如何指導(dǎo)下一步動作： 若當(dāng)前棧頂為A，當(dāng)前輸入為a，則規(guī)則2表示下一步動作是展開A，因?yàn)閍FIRST()，所以展開后下一次正好匹配a。 若當(dāng)前棧頂為A，當(dāng)前輸入為b且bFOLLOW(A)，則規(guī)則3表示下一步動作是展開A，即棧頂彈出A，繼續(xù)分析A之后的部分，因?yàn)閎FOLLOW(A)，所以彈出A后下一次正好匹配A的后繼b。,33,3.4.5.2 構(gòu)造預(yù)測分析表（續(xù)5）,FIRST(F/T/E)= ( id num FIRST(T) = * / mod FIRST(E) = + - FIRST(L) = ( id num FOLLOW(L) = # FOLL0W(E/E)= ) ; FOLLOW(T/T)= + - ; ) FOLLOW(F) = + - * / mod ) ;,2. 對FIRST()的每個(gè)終結(jié)符a，加入到MA，a； 3. 若FIRST()，則FOLLOW(A)每個(gè)終結(jié)符b(包括#)， 加入到MA，b；,從文法構(gòu)造分析表,E;L,E;L,E;L,TE,TE,TE,+TE,-TE,FT,FT,FT,*FT,/FT,mod FT,id,num,(E),34,3.4.5.3 LL(1)文法,MA,a的作用：指導(dǎo)產(chǎn)生式產(chǎn)生句子（指導(dǎo)推導(dǎo)） 問題：是否為任意文法構(gòu)造的分析表MA,a中都最多有一個(gè)條目？,例3.23 二義文法文法的預(yù)測分析表： 文法： SiCtSS|a SeS| Cb,預(yù)測分析表：,FIRST與FOLLOW集合： FIRST(C) = b FIRST(S) = , e FIRST(S) = i, a,FOLLOW(S) = #, e FOLLOW(S)= #, e FOLLOW(C) = t,a,iCtSS,b,eS,35,3.4.5.3 LL(1)文法（續(xù)1）,定義3.12 文法G被稱為是LL(1)文法，當(dāng)且僅當(dāng)為它構(gòu)造的預(yù)測分析表中不含多重定義的條目。由此分析表所組成的分析器被稱為LL(1)分析器，它所分析的語言被稱為LL(1)語言。第一個(gè)L代表從左到右掃描輸入序列，第二個(gè)L表示產(chǎn)生最左推導(dǎo)，1