中科大2021－2022學(xué)年秋季第一學(xué)期《編譯原理與技術(shù)》第五講 自頂向下分析

1、編譯原理與技術(shù) 自頂向下分析2022/7/251編譯原理與技術(shù)講義自頂向下分析分析樹的建立從根（開始符號）出發(fā)，從上而下，從左自右為輸入串建立分析樹為輸入串尋找一個最左推導(dǎo)e.g.1 文法G0如下S A B C A a B b C c輸入串 abc$串結(jié)束符2022/7/252編譯原理與技術(shù)講義自頂向下分析e.g.1 文法G0：S A B CA a B b C ca b c $S $當(dāng)前記號（指針）2022/7/253編譯原理與技術(shù)講義自頂向下分析e.g.1 文法G0：S A B CA a B b C ca b c $S $A B C$2022/7/254編譯原理與技術(shù)講義自頂向下分析e.g.

2、1 文法G0：S A B CA a B b C ca b c $S $A B C$a2022/7/255編譯原理與技術(shù)講義自頂向下分析e.g.1 文法G0：S A B CA a B b C ca b c $S $A B C$a終結(jié)符葉子與當(dāng)前符號匹配？2022/7/256編譯原理與技術(shù)講義自頂向下分析e.g.1 文法G0：S A B CA a B b C ca b c $S $A B C$ab指向下一記號2022/7/257編譯原理與技術(shù)講義自頂向下分析e.g.1 文法G0：S A B CA a B b C ca b c $S $A B C$ab2022/7/258編譯原理與技術(shù)講義自頂向下分

3、析e.g.1 文法G0：S A B CA a B b C ca b c $S $A B C$abc2022/7/259編譯原理與技術(shù)講義自頂向下分析e.g.1 文法G0：S A B CA a B b C ca b c $S $A B C$abc2022/7/2510編譯原理與技術(shù)講義自頂向下分析e.g.1 文法G0：S A B CA a B b C ca b c $S $A B C$abcOK！輸入串分析成功！2022/7/2511編譯原理與技術(shù)講義自頂向下分析e.g.1 文法G0：S A B CA a B b C c串a(chǎn)bc$的最左推導(dǎo)過程:S$ABC$aBC$abC$abc$2022/7/

4、2512編譯原理與技術(shù)講義自頂向下分析文法G0較簡單非終結(jié)符只有唯一的產(chǎn)生式試探分析法當(dāng)待分析（展開）的非終結(jié)符對應(yīng)多條產(chǎn)生式，可以選擇其一進行嘗試分析（最左推導(dǎo)）；當(dāng)此產(chǎn)生式無法與輸入串“匹配”時則需要“回溯”即放棄已建立的部分分析樹，同時調(diào)整輸入串指針恢復(fù)到此次分析前位置，再另選一產(chǎn)生式重新分析。只有當(dāng)所有的所有的嘗試均不成功，分析失?。?022/7/2513編譯原理與技術(shù)講義自頂向下分析試探分析法e.g.2 文法G1如下S x A yA ab A a輸入串 xay$ 的分析過程。2022/7/2514編譯原理與技術(shù)講義自頂向下分析試探分析法e.g.2 文法G1：（1）S x A y（2）

5、A ab （3）A a輸入串 xay$的分析過程。S$x A y $x a y $輸入串終結(jié)符葉子x與輸入符x匹配a b選用產(chǎn)生式（1）選用產(chǎn)生式（2）匹配失??！2022/7/2515編譯原理與技術(shù)講義自頂向下分析試探分析法e.g.2 文法G1：（1）S x A y（2）A ab （3）A a輸入串 xay$的分析過程。S$x A y $x a y $輸入串a(chǎn) b選用產(chǎn)生式（1）選用產(chǎn)生式（2）匹配失??！回溯：重新分析A2022/7/2516編譯原理與技術(shù)講義自頂向下分析試探分析法e.g.2 文法G1：（1）S x A y（2）A ab （3）A a輸入串 xay$的分析過程。S$x A y

6、$x a y $輸入串選用產(chǎn)生式（1）a選用產(chǎn)生式（3）終結(jié)符葉子a與輸入符a匹配分析成功！2022/7/2517編譯原理與技術(shù)講義試探分析法在文法有左遞歸特征時，可能導(dǎo)致無限循環(huán)而此時無法讀入任何輸入符（輸入指針保持不變）。如表達式文法G2：EE+T | T TT*F | FF(E) | id自頂向下分析a + b 輸入串EE + TE + T 2022/7/2518編譯原理與技術(shù)講義自頂向下分析預(yù)測分析法對于待分析的非終結(jié)符A，可以根據(jù)當(dāng)前輸入符號（記號）來準(zhǔn)確唯一地選擇A的某一產(chǎn)生式。若該產(chǎn)生式“匹配”成功，則意味著A分析成功；若匹配失敗，則即使選擇A的其它產(chǎn)生式也會導(dǎo)致A分析失?。ㄒ蚨?/p>

7、不需要回溯）。Case 1:文法G1 A a bA的兩個產(chǎn)生式右部具有 A a相同的（非空）前綴a 那么A面臨輸入符a選擇誰呢？2022/7/2519編譯原理與技術(shù)講義預(yù)測分析法提左因子的文法變換文法G1中， A a b A a A A a A b | 自頂向下分析A 1A 21和2不含相同前綴提左因子A AA 1 | 2引入非終結(jié)符A提左因子2022/7/2520編譯原理與技術(shù)講義預(yù)測分析法e.g.3 文法G1中， A a b A a A A a A b | A 面臨 a 時有唯一的產(chǎn)生式A a A； A面臨 b 時可以選A b； 空產(chǎn)生式 A 何時選用呢？ 自頂向下分析提左因子可以考慮（除

8、b外的）任一符號c。可以與之“匹配”！2022/7/2521編譯原理與技術(shù)講義預(yù)測分析法提左因子變換的一般形式自頂向下分析A 1 | 2 | n A i不含相同前綴, 不含前綴提左因子變換后：A A | A 1 | 2 | n 2022/7/2522編譯原理與技術(shù)講義預(yù)測分析法Case 2: 文法G2 E E + TE的產(chǎn)生式的（直接）左遞歸妨礙了E T 輸入符號的有效讀入（實際上不讀） 并導(dǎo)致死循環(huán)。消除左遞歸（A A）的文法變換 直接左遞歸的消除（A A）自頂向下分析A AA 消除直接左遞歸A AA A | 引入非終結(jié)符A ，形成右遞歸文法2022/7/2523編譯原理與技術(shù)講義預(yù)測分析法

9、e.g.4 消除文法G2中的直接左遞歸。E E + T E T EE T E + T E | T T * F T F T T F T * F T | F ( E ) F ( E ) F id F id自頂向下分析含左遞歸的文法G2不含左遞歸的文法G22022/7/2524編譯原理與技術(shù)講義EETTFii+*FTiF文法G2：i+i*i的分析樹ETEFTiT+EFTiFTi*文法G2：i+i*i的分析樹2022/7/2525編譯原理與技術(shù)講義自頂向下分析預(yù)測分析法消除左遞歸（A A）的文法變換間接左遞歸的消除（A B A） 對于含間接左遞歸的文法G，可以先設(shè)法變換為含有直接左遞歸的文法G（通常將

10、較簡單的產(chǎn)生式逐次代入較復(fù)雜的產(chǎn)生式），然后再行消除G中的直接左遞歸即可。2022/7/2526編譯原理與技術(shù)講義自頂向下分析預(yù)測分析法e.g.5消除文法G3中的（間接）左遞歸。S Aa | a | bA Ac | c | Sd將S相應(yīng)產(chǎn)生式分別代入A相關(guān)產(chǎn)生式，得到文法G3：S Aa | a | bA Ac | c | Aad | ad | bd 消除G3中（A的）直接左遞歸，則有2022/7/2527編譯原理與技術(shù)講義自頂向下分析預(yù)測分析法e.g.5消除文法G3中的（間接）左遞歸。S Aa | a | bA c A | ad A | bd AA c A | ad A | 上述文法不再含有左

11、遞歸。2022/7/2528編譯原理與技術(shù)講義自頂向下分析回顧一下什么是預(yù)測分析法？對于待分析的非終結(jié)符A，可以根據(jù)當(dāng)前輸入符號（記號）來準(zhǔn)確唯一地選擇A的某一產(chǎn)生式。若該產(chǎn)生式“匹配”成功，則意味著A分析成功；若匹配失敗，則即使選擇A的其它產(chǎn)生式也會導(dǎo)致A分析失?。ㄒ蚨恍枰厮荩Ｔ趯ξ姆ㄌ嶙笠蜃雍拖筮f歸后，可以實施預(yù)測分析了！但是，待分析或展開的非終結(jié)符A如何利用當(dāng)前輸入符（記號）來選擇產(chǎn)生式呢？2022/7/2529編譯原理與技術(shù)講義First集合（首符號集合） First() = a | *a | * , 其中 aVT, , (VTVN) First(a) = a | aVT A

12、V N，考查A的每個產(chǎn)生式：A X1X2Xn，Xi (VTVN), 計算First(A), (初始為) 1) 把Firtst(X1)- 加入First(A),如果First(X1)則結(jié)束計算First(A)，否則 2) 把Firtst(X2)- 加入First(A),如果First(X2)則結(jié)束計算First(A)，否則 n) 把Firtst(Xn)- 加入First(A),如果First(Xn)則結(jié)束計算First(A)，否則 n+1) 加入First(A)2022/7/2530編譯原理與技術(shù)講義e.g.6文法G2的First集合 E T E E + T E | T F T T * F T

13、| F ( E ) F idFirst( F ) = (, id 2022/7/2531編譯原理與技術(shù)講義e.g.6文法G2的First集合 E T E E + T E | T F T T * F T | F ( E ) F idFirst( T ) = *, 2022/7/2532編譯原理與技術(shù)講義e.g.6文法G2的First集合 E T E E + T E | T F T T * F T | F ( E ) F idFirst( T ) = First( F ) = (, id 2022/7/2533編譯原理與技術(shù)講義e.g.6文法G2的First集合 E T E E + T E | T

14、 F T T * F T | F ( E ) F idFirst( E) = +, 2022/7/2534編譯原理與技術(shù)講義e.g.6文法G2的First集合 E T E E + T E | T F T T * F T | F ( E ) F idFirst( E ) = First( T ) = First( F ) = (, id 2022/7/2535編譯原理與技術(shù)講義e.g.6文法G2的First集合 E T E E + T E | T F T T * F T | F ( E ) F idFirst( E ) = First( T )= First( F ) = (, id First

15、( E) = +, First( T ) = First( F ) = (, id First( T ) = *, First( F ) = (, id 2022/7/2536編譯原理與技術(shù)講義Follow集合（后繼符號集合） Follow(A)= a | S * Aa ，其中 aVT, A VN , (VTVN)* $ Follow(S). 若 A BP，則把First()-加入Follow(B) 若 A BP 或 A BP 且 * (即 First() ），則 把Follow(A)加入Follow(B) S * Aa S * Aa Ba Ba * B a Ba 顯然a Follow(A)

16、Follow(B)2022/7/2537編譯原理與技術(shù)講義e.g.7文法G2的Follow集合 E T E E + T E | T F T T * F T | F ( E ) F idFollow( E ) = $, ) $ Follow(E).2022/7/2538編譯原理與技術(shù)講義e.g.7文法G2的Follow集合 E T E E + T E | T F T T * F T | F ( E ) F idFollow( E ) = Follow(E)= $, ) 2022/7/2539編譯原理與技術(shù)講義e.g.7文法G2的Follow集合 E T E E + T E | T F T T *

17、 F T | F ( E ) F id Follow( T ) = (First(E)-) Follow(E)= + $, ) = +, $, ) 2022/7/2540編譯原理與技術(shù)講義e.g.7文法G2的Follow集合 E T E E + T E | T F T T * F T | F ( E ) F idFollow( T ) = Follow(T)= +, $, ) 2022/7/2541編譯原理與技術(shù)講義e.g.7文法G2的Follow集合 E T E E + T E | T F T T * F T | F ( E ) F id Follow( F ) = (First(T)-)

18、Follow(T) Follow(T)= * + , $ , ) = * , + , $ , ) 2022/7/2542編譯原理與技術(shù)講義e.g.7文法G2的Follow集合 E T E E + T E | T F T T * F T | F ( E ) F idFollow( F ) = * , + , $ , ) Follow( T ) = +, $ , ) Follow( T ) = + , $ , ) Follow( E ) = $ , ) Follow( E ) = $ , ) 2022/7/2543編譯原理與技術(shù)講義SAa 輸入串b 自頂向下分析A時，如果A只產(chǎn)生非空符號串，那么A

19、期望“看到”的當(dāng)前輸入的符號最好是aFirst(A)，這樣的話，選用產(chǎn)生式A來分析，即能產(chǎn)生（推導(dǎo)）出以a開頭的串并期待與相應(yīng)輸入串匹配。2022/7/2544編譯原理與技術(shù)講義自頂向下分析A時，如果A只產(chǎn)生的是不包含任何有效符號的串 ，則它 “看到”的當(dāng)前輸入的符號只能是bFollow(A)。這時選用產(chǎn)生式A 來“結(jié)束”對A的分析而開始的分析。SA輸入串b 2022/7/2545編譯原理與技術(shù)講義SAb SAab自頂向下分析A時，如果A既產(chǎn)生非空串也可以產(chǎn)生 ，則它 可能“看到”的當(dāng)前輸入的符號來自aFirst(A)，或者來自bFollow(A)。但A最不期望的是 ab，因為這樣，A面臨兩難

20、的選擇 A 還是 A ?2022/7/2546編譯原理與技術(shù)講義LL（1）文法一般的，文法G是LL(1)文法，如果任何AVN，其產(chǎn)生式，A1|2|n，滿足： First(i)First(j) = ，ij, i,j=1,2,n ; 若First(k)，則First(i)Follow(A) = , i k.read from Left to rightLeftmost derivation1 lookhead2022/7/2547編譯原理與技術(shù)講義LL（1）文法產(chǎn)生式不含左遞歸具有相同左部的產(chǎn)生式不含左因子LL(1)文法G進行自頂向下分析時，非終結(jié)符A面臨當(dāng)前輸入符號a時即可作出唯一的產(chǎn)生式的選擇

21、決定2022/7/2548編譯原理與技術(shù)講義自頂向下分析LL(1)文法的遞歸下降分析為LL（1）文法G（無左因子、左遞歸）構(gòu)造一個無回溯的預(yù)測分析器。文法G的每一個非終結(jié)符A對應(yīng)一個（遞歸）分析過程A()。分析過程A()1) 由當(dāng)前輸入符號(lookhead)決定產(chǎn)生式的選??；2) 產(chǎn)生式A X1X2Xn的分析過程：從左往右逐個分析。XiVT，則調(diào)用匹配過程 match(Xi) XiVN，則調(diào)用分析過程 Xi()3) 空產(chǎn)生式A ， 直接返回2022/7/2549編譯原理與技術(shù)講義遞歸分析過程A()void A() if ( lookhead First(X1X2Xn) ) /* 產(chǎn)生式AX1

22、X2Xn的分析過程 */ else if /*A的其它非空產(chǎn)生式的分析*/ else if ( ( lookhead Follow(A) ) and A P) return; /* 空產(chǎn)生式，直接返回 */ else error() /* 語法錯誤*/ 2022/7/2550編譯原理與技術(shù)講義遞歸下降分析匹配過程 match( token t )void match( token t ) if ( lookhead = t ) /終結(jié)符葉子和輸入符是否匹配（相同） lookhead = next_token(); /若匹配則獲取下一記號，即向前移動輸入指針 else error() /* 否則

23、語法錯誤需要符號 t */ 2022/7/2551編譯原理與技術(shù)講義遞歸下降分析e.g.8 編寫文法G2的遞歸分析過程。 E T E E + T E | T F T T * F T | F ( E ) F idvoid E() if (lookhead=( ) | (lookhead=id) T(); E(); else error(); 2022/7/2552編譯原理與技術(shù)講義e.g.8 編寫文法G2的遞歸分析過程。 E T E E + T E | T F T T * F T | F ( E ) F idvoid E () if (lookhead=+) match(+); T(); E (

24、); else / return; /將看成與任一符號匹配/ 從而將以下程序省略！ if ( (lookhead=$ ) | (lookhead=) ) return; else error(); 2022/7/2553編譯原理與技術(shù)講義e.g.8 編寫文法G2的遞歸分析過程。 E T E E + T E | T F T T * F T | F ( E ) F idvoid T() if (lookhead=( ) | (lookhead=id) F(); T(); else error(); 2022/7/2554編譯原理與技術(shù)講義e.g.8 編寫文法G2的遞歸分析過程。 E T E E +

25、 T E | T F T T * F T | F ( E ) F idvoid T () if (lookhead=*) match(*); F(); T (); else / return; /將看成與任一符號匹配/ 從而將以下程序省略！ if ( (lookhead=+ ) | (lookhead=$ ) | (lookhead=) ) return; else error(); 2022/7/2555編譯原理與技術(shù)講義e.g.8 編寫文法G2的遞歸分析過程。 E T E E + T E | T F T T * F T | F ( E ) F idvoid F() if (lookhead

26、=( ) match( ( ); E(); match( ) ); else if (lookhead=id) match( id ); else error(); 2022/7/2556編譯原理與技術(shù)講義自頂向下分析LL(1)文法的非遞歸的預(yù)測分析方法表驅(qū)動的預(yù)測分析通過查表決定產(chǎn)生式的選取輸入串控制程序（預(yù)測分析器）預(yù)測分析表X.$a1.ai.$分析棧輸出TopBottom2022/7/2557編譯原理與技術(shù)講義非遞歸的預(yù)測分析方法分析棧(stack)棧的內(nèi)容VTVN $，開始分析時，”$”位于棧底，S位于棧頂。分析表 M : VN (VT$) (P error)對于AVN，aVT，有 A

27、P M A, a = error() / 錯誤恢復(fù)例程控制程序2022/7/2558編譯原理與技術(shù)講義非遞歸的預(yù)測分析方法控制程序由當(dāng)前棧頂符號X和當(dāng)前輸入符號a決定采取的分析動作。 XVT X=a=$ ，則分析成功，STOP! X=a $ ，則 1) popup() / 從棧頂彈出X 2) 移動輸入指針至下一符號 X a，error() / 匹配失敗! / 調(diào)用錯誤恢復(fù)程序2022/7/2559編譯原理與技術(shù)講義非遞歸的預(yù)測分析方法控制程序 XVN M X, a = X U V W ，則 popup(); /彈出X push( W ); push( V ); push( U ); / 產(chǎn)生式

28、右部符號以逆序入棧 M X, a = error()，則調(diào)用錯誤恢復(fù)程序 2022/7/2560編譯原理與技術(shù)講義e.g.9 表達式文法G2的預(yù)測分析表 VT$ VN id+*()$EETEETEEE+TEEETTFTTFTTTT*FTTTFF idF (E)2022/7/2561編譯原理與技術(shù)講義e.g.10 表達式id+id*id的非遞歸預(yù)測分析過程分析棧輸入串輸出$ Eid + id * id $ E Tid + id * id $E T E$ E T Fid + id * id $T F T$ E T idid + id * id $F id$ E T + id * id $id匹配成

29、功$ E + id * id $T$ E T + id * id $E + T E2022/7/2562編譯原理與技術(shù)講義e.g.10 表達式id+id*id的非遞歸預(yù)測分析過程（續(xù)）分析棧輸入串輸出$ E T + id * id $E + T E$ E Tid * id $+匹配成功$ E T Fid * id $T F T$ E T idid * id $F id$ E T* id $id匹配成功$ E T F * id $T * F T$ E T F id $*匹配成功2022/7/2563編譯原理與技術(shù)講義e.g.10 表達式id+id*id的非遞歸預(yù)測分析過程（續(xù)）分析棧輸入串輸出$

30、 E T F id $*匹配成功$ E T id id $F id$ E T $id匹配成功$ E $T$ $E分析成功！2022/7/2564編譯原理與技術(shù)講義預(yù)測分析表的構(gòu)造考查任意產(chǎn)生式A：M A, a = A ,如果 a First()-M A, b = A ,如果 First()且bFollow(A)所有無定義的表項填上error()預(yù)測分析表如果不含多重定義表項則相應(yīng)文法是LL(1)的。2022/7/2565編譯原理與技術(shù)講義文法G4：(if then else)1) S i E t S S 2) S a3) S e S4) S 5) E be.g.11構(gòu)造文法G4的預(yù)測分析表Fi

31、rst(S) = i, a First(S) = e, First(E) = b Follow(S) = $, e Follow(S) = $, e Follow(E) = t 2022/7/2566編譯原理與技術(shù)講義e.g.11構(gòu)造文法G4的預(yù)測分析表1) S i E t S S , iFirst(i E t S S), 故而M S, i = S i E t S S 2) S a ,顯然，M S, a = S a 3) S e S ,顯然，M S, e = S e S4) S , 則對于Follow(S)=$,e中的每個符號,有：M S, $ = S 和 M S, e = S 5) E b

32、,顯然，M E, b = E b 2022/7/2567編譯原理與技術(shù)講義e.g.11構(gòu)造文法G4的預(yù)測分析表 VT$ VN a beit$SSaS iEtSSSS eSS S EE b有多重定義2022/7/2568編譯原理與技術(shù)講義二義性文法決不是LL（1）文法。其預(yù)測分析表有多重定義表項。文法G4不是LL(1)文法。文法G4具有二義性。對于串 i b t i b t a e a 有兩個不同的最左推導(dǎo)：S i E t S S i b t S S i b t i E t S S S i b t i b t S S S i b t i b t a S S i b t i b t a e S S

33、 i b t i b t a e a S i b t i b t a e a i b t i b t a e a i b t i b t a S i b t i b t a S i b t i b t a e S i b t i b t a e a122022/7/2569編譯原理與技術(shù)講義e.g.12文法G5不是LL（1）文法文法G5：1) A a A a 2) A 文法G5產(chǎn)生串長為偶數(shù)的a串，它是非二義文法，但卻不是LL(1)文法。因為：First( A ) = a , , Follow( A ) = $, a 分析表中M A, a = A a A a, A 有多重定義；或者 由于A 為

34、空產(chǎn)生式，而 First( A aAa ) Follow(A) a 2022/7/2570編譯原理與技術(shù)講義Aa A aa A a文法G5關(guān)于串a(chǎn)aaa的最左推導(dǎo)與分析樹 A1) a A a2) a a A a a3) a a a a4) a a a a顯然，在只有在偶數(shù)長(2)的a串的前一半a被產(chǎn)生（推導(dǎo)）出來后，產(chǎn)生式A方被選擇來作分析（推導(dǎo)）。而此前只用AaAa。2022/7/2571編譯原理與技術(shù)講義Aa a a a $輸入串自頂向下分析輸入a串，即尋找一個產(chǎn)生a串的最左推導(dǎo)過程。但遺憾是，輸入串是從左往右一個一個符號地被讀入，每當(dāng)讀入一個符號a時，由于不知道輸入串中總共有多少符號a，

35、也就無法判定此時是否已經(jīng)“讀完了”a串的前一半a。這就造成了A面臨輸入a時的存在矛盾（或多重）的產(chǎn)生式選擇。2022/7/2572編譯原理與技術(shù)講義錯誤恢復(fù)程序的錯誤類型編譯時錯誤(compile error)詞法錯誤如出現(xiàn)非法字符 語法錯誤如括號不配對、語句結(jié)束無分號（靜態(tài)）語義錯誤如形/實參數(shù)類型不匹配運行時錯誤(run-time error)動態(tài)（運行時）語義錯誤無限遞歸（循環(huán)）、地址（指針）越界、棧上溢（overflow）和下溢（underflow）、異常（exception）2022/7/2573編譯原理與技術(shù)講義錯誤恢復(fù)錯誤恢復(fù)的目標(biāo)錯誤（性質(zhì)）報告準(zhǔn)確，錯誤位置精準(zhǔn)能快速地從當(dāng)前

36、錯誤中恢復(fù)，以期發(fā)現(xiàn)后面的錯誤；任何（編譯）錯誤不能導(dǎo)致編譯器崩潰對常見的錯誤應(yīng)該有很好的恢復(fù)措施盡量減少“株連”錯誤的產(chǎn)生 2022/7/2574編譯原理與技術(shù)講義錯誤恢復(fù)錯誤恢復(fù)的策略緊急方式（panic mode）發(fā)現(xiàn)錯誤時，分析器將拋棄若干輸入符號，直到遇上希望的輸入同步符號為止。該方法較容易實現(xiàn)且不會陷入死循環(huán)，但對忽略的輸入無法進行分析。同步符號（集合）的選取若待分析語法成份為A，則同步符號（集合）Synch（A）的可以考慮： 1）Follow（A）考慮結(jié)束A的分析工作 2）First（A） 重新開始A的分析2022/7/2575編譯原理與技術(shù)講義e.g. 13 緊急方式錯誤恢復(fù)

37、a = Expr if ; ;尋找“;” 因為“;”Follow（Stat）被跳過的輸入串Missing “;”2022/7/2576編譯原理與技術(shù)講義e.g. 13 緊急方式錯誤恢復(fù) a = Expr if ; 3）為避免忽略過多的輸入符號，可以考慮將較高層次的語法單位的首符號（First）加入低層結(jié)構(gòu)的同步符號集合中。如語句Stat的首符號if加入Synch（Stat），這樣，當(dāng)某一語句分析出錯時，可以拋棄該語句中的其它輸入符號，而開始下一個新語句的分析。新的分析起點2022/7/2577編譯原理與技術(shù)講義錯誤恢復(fù)錯誤恢復(fù)的其它策略短語級恢復(fù)（phrase level） 對輸入串作局部校正

38、，插入或刪除符號出錯產(chǎn)生式（error production） 將出錯情況用產(chǎn)生式的形式來描述，（參見YACC）如 Stat error ; / 描述語句分析時出錯時將跳過若干輸入符號直至; 出現(xiàn)全局校正（global correction）2022/7/2578編譯原理與技術(shù)講義預(yù)測分析的錯誤恢復(fù)遞歸下降分析的錯誤恢復(fù)為每個分析過程增加一個參數(shù)同步符號集合一般地，當(dāng)錯誤發(fā)生時，錯誤恢復(fù)例程error（）將反復(fù)調(diào)用詞法程序忽略若干輸入符號，直至同步集合（可以考慮Follow集合）中的符號出現(xiàn)為止，然后分析過程結(jié)束返回。2022/7/2579編譯原理與技術(shù)講義e.g. 14 文法G2帶有錯誤恢復(fù)

39、的分析過程 E T E E + T E | T F T T * F T | F ( E ) F idvoid E(SyncSet) / $ if (lookhead=( ) | (lookhead=id) T( + SyncSet); E(SyncSet); else errorE(SyncSet); 2022/7/2580編譯原理與技術(shù)講義e.g. 14 文法G2帶有錯誤恢復(fù)的分析過程 E T E E + T E | T F T T * F T | F ( E ) F idvoid E (SyncSet) if (lookhead=+) match(+); T( + SyncSet); E

40、(SyncSet); else if ( (lookhead=$ ) | (lookhead=) ) return; else errorE(SyncSet); 2022/7/2581編譯原理與技術(shù)講義e.g. 14 文法G2帶有錯誤恢復(fù)的分析過程 E T E E + T E | T F T T * F T | F ( E ) F idvoid T(SyncSet) if (lookhead=( ) | (lookhead=id) F( * SyncSet); T(SyncSet); else errorT(SyncSet); 2022/7/2582編譯原理與技術(shù)講義e.g. 14 文法G2帶有錯誤恢復(fù)的分析過程