資源描述：
《編譯原理 第11講(第五章).ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。
1、第5章自頂向下語法分析方法5.1確定的自頂向下分析思想5.2LL(1)文法判別FIRST和FOLLOW集定義和計算5.3非LL(1)文法的改造1自上而下的語法分析面臨的問題-實現(xiàn)考慮回朔文法的左遞歸性S→Sa2自上而下分析對文法的要求例文法G0[S]:(1)S→Sa(2)S→b分析baa是不是文法的句子按照自上而下的分析思想選用產(chǎn)生式(1)來推導S?Sa語法樹末端結點最左符號為非終結符，所以選用（1）繼續(xù)推導S?Sa?Saa此時語法樹末端結點最左符號仍為非終結符，所以選用（1）繼續(xù)推導S?Sa?Saa?Saa
2、a問題——試圖用S匹配輸入串時，出現(xiàn)：在沒有讀入任何輸入符號的情況下，又得重新要求S去進行新的匹配原因——文法含有左遞歸3自上而下分析的進一步討論自上而下分析也稱面向目標的分析方法，也就是從文法的開始符號出發(fā)企圖推導出與輸入的符號串完全匹配的句子，若能構造出推導則表明輸入串是給定文法的句子，否則表明該輸入不是給定文法的句子。自上而下分析對文法的要求－文法不能含有左遞歸規(guī)則。自上而下分析又可分為確定的和不確定的兩種不確定的分析方法稱為帶回溯的分析方法，這種方法實際上是一種窮舉的試探方法確定的分析方法需對文法有一
3、定的限制4（選）自上而下的語法分析－左遞歸規(guī)則G[S]:S→Sa??????????????S→bL={ban
4、n≥1}W=baaaSbSSaSa5（選）左遞歸－關于非終結符P的規(guī)則直接左遞歸若P→Pα
5、βα、β∈V*且α、β不以P開頭一般左遞歸若P=>*PαS→AaA→Sb…6（選）消除文法中左遞歸規(guī)則消除直接左遞歸形如：P→Pα
6、βα非?，α，β不以P打頭改寫為：P→βQQ→αQ
7、?其中Q為新增加的非終結符7（選）消除文法中左遞歸規(guī)則例:E→E+T
8、TT→T*F
9、FF→(E)
10、aG[E]:(1)E→TE’
11、(2)E’→+TE’(3)E’→?(4)T→FT’(5)T’→*FT’(6)T’→?(7)F→(E)(8)F→a8（選）消除一般左遞歸要求文法: 1.無回路(A(=>+(A)2.無空產(chǎn)生式（1）.以某種順序?qū)⑽姆ǚ墙K結符排列A1,A2…An（2）fori:=1tondobeginforj:=1toi-1do用Ai-->?1
12、?2r…
13、?kr替代形如Ai-->Ajr的規(guī)則,其中Aj-->?1
14、?2…
15、?k是關于Aj的全部產(chǎn)生式;消除Ai規(guī)則的直接左遞歸;end;（3）化簡由2得到的文法9（選）回溯的原因例G[S
16、]:S→xAyA→ab｜a若當前輸入串為xay，首先構造的推導S?xAy?匹配?進一步推導對A可選擇A→ab替換，得S?xAy?xabyxayxaby?匹配?xa都已匹配，當前面臨輸入符為y與b不能匹配，所以將輸入串指針退回到a，對A的替換重新選用下一個產(chǎn)生式A→a進行試探，S?xAy?xay輸入串中當前符a得到匹配，指針向前移動到y(tǒng)，與語法樹中y匹配，匹配成功。由于相同左部的產(chǎn)生式的右部開始符號相同而引起回溯。105.3非LL(1)文法的改造消除左遞歸提左公因子將產(chǎn)生式Ａ??β
17、??變換為：Ａ??BB?β
18、
19、?11E→E+T｜TT→T*F｜FF→i｜(E)FIRST(E)=｛(,i｝FIRST(T)=｛(,i｝FIRST(F)=｛(,i｝消左遞歸E–>TE’E’–>+TE’E’–>?E→T+E｜TT→F*T｜FF→i｜(E)FIRST(E)=FIRST(T)=FIRST(F)=｛(,i｝提左公因子E→T(+E｜?)T→F(*T｜?)12消除左遞歸和提左公因子并不一定都能將非LL(1)文法改造為LL(1)的S→ifCtS
20、ifCtSeSC→b提左因子S→ifCtSAA→eS
21、?First集Follow集Sif#,e
22、Ae,?#,eCbtM[A,e]={A→eSA→?}13LL(1)分析中的一種錯誤處理辦法發(fā)現(xiàn)錯誤1棧頂?shù)慕K結符與當前輸入符不匹配2非終結符A于棧頂，面臨的輸入符為a，但分析表M的M[A,a]為空“應急”恢復策略跳過輸入串中的一些符號直至遇到“同步符號”為止。同步符號的選擇1把FOLLOW(A)中的所有符號作為A的同步符號。跳過輸入串中的一些符號直至遇到這些“同步符號”，把A從棧中彈出，可使分析繼續(xù)2把FIRST(A)中的符號加到A的同步符號集，當FIRST(A)中的符號在輸入中出現(xiàn)時，可根據(jù)A恢復分析14G
23、[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>?(4)T–>FT’(5)T’–>*FT’(6)T’–>?(7)F–>(E)(8)F–>aa+*()#E(1)(1)E’(2)(3)(3)T(4)(4)T’(6)(5)(6)(6)F(8)(7)synsyn15練習1.對文法G［S］S→a
24、∧
25、(T)T→T,S
26、S（1）給出(a,(a,a))和(((a,a),∧,(a)),a)的最左推導。
