【文章內(nèi)容簡介】 ush ? , goto C (C, ? ,? ) 34 預測分析表 構造算法 G的每個產(chǎn)生式Ａ ? ?執(zhí)行第二步和第三步； a?Select(Ａ ? ?),把Ａ ? ?加至 ?[A,a]中， ?[A,a]標上 “ 出錯標志 ” 。 可以證明，一個文法 G的預測分析表不含多重入口，當且僅當該文法是 LL(1)的 35 例：不含左遞歸的表達式文法 G[ E]: (1) E – TE’ (2) E’ – +TE’ (3) E’ – ? (4) T – FT’ (5) T’ – *FT’ (6) T’ – ? (7) F – (E) (8) F – a 預測分析表的構造－舉例 例：含左遞歸的表達式文法G[E]： E→E+T|T T→T*F|F F→(E)|a 36 a + * ( ) E (1) (1) E’ (2) (3) (3) T (4) (4) T’ (6) (5) (6) (6) F (8) (7) G[ E]: (1) E – TE’ (2) E’ – +TE’ (3) E’ – ? (4) T – FT’ (5) T’ – *FT’ (6) T’ – ? (7) F – (E) (8) F – a 37 預測分析程序的 總控程序算法 ? BEGIN ? 首先把 ’ ‘然后把文法開始符號推入棧；把第一個輸入符號讀進 b。 ? FLAG： =TRUE； ? WHILE FLAG DO BEGIN ? 把棧頂符號上托出去并放在Ｘ 中； ? IF X ? Vt THEN IF X=b THEN ? 把下一 個輸入符號讀進 b ? ELSE ERROR ELSE IF X=‘’ THEN ? IF X=b THEN FLAG:=FALSE ? ELSE ERROR ? ELSE IF ?[X,b]={X – X1X2..XK} ? THEN 把 XK， X K1,..,X1一一推進棧 ? ELSE ERROR ? END OF WHILE。 ? STOP/*分析成功，過程完畢 *／ ? END 38 分析輸入串 a+a 棧內(nèi)容 棧頂符號 當前輸入 余留串 M[X,b ] 1 E E a +a E – TE’ 2 E’T T a +a T – FT’ 3 E’T’F F a +a F – a 4 E’T’a a a +a 5 E’T’ T’ + a T’ – ? 6 E’ E’ + a E’ – +TE’ 7 E’T+ + + a 8 E’T T a T – FT’ 9 E’T’F F a F – a 10 E’T’a a a 11 E’T’ T’ T’ – ? 12 E’ E’ E ’ – ? 13 39 非 LL(1)文法的改造 LL(1)文法的性質(zhì)： LL(1)文法是無二義的 LL(1)文法不含左遞歸 非 LL(1)文法的改造 方法 提左公因子 消除左遞歸 40 提左公因子 將產(chǎn)生式 A? ?β |?? 變換為： ?A? ?B ?B? β |? 41 左遞歸規(guī)則 G[S]: S→Sa S→b L={ba n | n≥0} W=baaa S S a S a S a ? b 42 左遞歸 關于非終結符 P的規(guī)則 直接左遞歸 若 P → P α | β α 、 β ∈V *且 β 不以 P開頭 一般 左遞歸 若 P =* P α S→Aa A→Sb … 43 消除左遞歸 消除直接左遞歸 形如： P → P α | β α 非 ?， 不以 P打頭 改寫為： P → β Q Q → α Q| ? 44 消除左遞歸 例 :E → E+T|T T →T*F|F F →(E)| a G[ E]： (1) E → TE’ (2) E’ → +TE’ (3) E’ → ? (4) T → FT’ (5) T’ → *FT’ (6) T’ → ? (7) F → (E) (8) F → a 形如： P → P α| β α非 ?， 不以 P打頭 P → βQ Q → αQ| ? 45 消除一般左遞歸 消除一般左遞歸 要求文法 : (A(=+(A) （ 1） 以某種順序?qū)⑽姆ǚ墙K結符排列 A1 ,A2 …An （ 2） for i:=1 to n do begin for j:=1 to i1 do 用 Ai?1| ?2r…| ? k r替代 形如 Ai Ajr的規(guī)則 ,其中 Aj ?1| ?2…| ?k是關于 Aj的全部產(chǎn)生式 。 消除 Ai規(guī)則的直接左遞歸 。 end。 p89 （ 3） 化簡由 2得到的文法 46 LL(1)分析中的一種錯誤處理辦法 發(fā)現(xiàn)錯誤 1棧頂?shù)慕K結符與當前輸入符不匹配 2非終結符 A于棧頂，面臨的輸入符為 a，但分析表 M的 M[A,a]為空 “應急”恢復策略 跳過輸入串中的一些符號直至遇到“同步符號”為止。 同步符號的選擇 1把 FOLLOW(A)中的所有符號作為 A的同步符號。跳過輸入串中的一些符號直至遇到這些“同步符號”，把