資源描述：
《編譯原理 之 自頂向下語法分析方法.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。
1、第五章自頂向下語法分析方法本章要點LL(1)分析First集合和Follow集合使用遞歸下降分析算法進行自頂向下的分析預測分析程序非LL(1)文法的改造自上而下分析算法自頂向下分析法也稱面向目標的分析方法,也就是從文法的開始符號出發(fā)企圖推導出與輸入的單詞串完全匹配的句子,若輸入串是給定的句子,則必能推出,反之必然出錯。自頂向下分析法又分為確定的和不確定的兩種。5.1確定的自頂向下分析思想確定的自頂向下分析方法，首先要解決從文法的開始符號出發(fā)，如何根據(jù)當前的輸入符號（單詞符號）唯一地確定選用哪個產(chǎn)生式替換相應非終結符往下推導，或構造一棵相應的語法樹。例5.1若有文法G1[S
2、]：S?pA
3、qBA?cAd
4、aB?dB
5、b若輸入串W=pccadd。自頂向下推導過程為S=>pA=>pcAd=>pccAdd=>pccadd這個文法有以下兩個特點：每個產(chǎn)生式的右部都由終結符號開始。如果兩個產(chǎn)生式有相同的左部，那么它們的右部由不同的終結符開始。例5.2若有文法G2[S]為：S?ApS?BqA?aA?cAB?bB?db當輸入串W=ccap，那么試圖推出輸入串的推導過程為：S=>Ap=>cAp=>ccAp=>ccap例5.2文法的特點是：產(chǎn)生式的右部不全是由終結符開始如果兩個產(chǎn)生式有相同的左部，它們的右部是由不同的終結符或非終結符開始。文法中無空產(chǎn)生式定義5
6、.1設G=(VT,VN,P，S)是上下文無關文法FIRST（?）={a
7、?a?,a∈VT,?,?∈V*}若?ε則規(guī)定ε∈FRIST（?）不難求出在文法G2中FIRST(Ap)={a,c}FIRST(Bq)={b,d}例5.3若有文法G[S]:S?aAS?dA?bASA??若輸入串W=abd，則試圖推導出abd串的推導過程為：S=>aA=>abAS=>abS=>abd從例5.3可以得出下列結論當某一非終結符的產(chǎn)生式中含有空產(chǎn)生式時，它的非空產(chǎn)生式右部的首符號集兩兩不相交，并與在推導過程中緊跟該非終結符右邊可能出現(xiàn)的終結符集也不相交，則仍可構造確定的自頂向下分析。定義5.2設
8、G=(VT,VN,P，S)是上下文無關文法,A∈VN,S是文法開始符號FOLLOW(A)={a?S?A?且a∈VTa∈FRIST(?)，?∈V*，?∈V+}若S?A?,且?ε，則#∈FOLLOW(A)定義5.3給定上下文無關文法的產(chǎn)生式A??,A?VN,??V*,若??>*?，則SELECT(A??)=FIRST(?)如果??，則SELECT(A??)=(FIRST(?)-{?})?FOLLOW(A)定義5.4一個上下文無關文法是LL（1）文法的充分必要條件是，對每個非終結符A的兩個不同產(chǎn)生式，A??，A??，滿足SELECT(A??)?SELECT(A??)=?其中?、
9、?不能同時?。LL(1)文法的含義：第1個“L”指的是由左向右地處理輸入。第2個“L”指的是它為輸入串描繪出一個最左推導。括號中的數(shù)字1意味著它只需向右看一個符號便可決定如何推導即選擇哪個產(chǎn)生式（規(guī)則）進行推導。例5.3的文法S?aAS?dA?bASA??不難看出：SELECT(S?aA)={a}SELECT(S?d)=b1tklueSELECT(A?bAS)=SELECT(A??)={a,d,#}所以SELECT(S?aA)?SELECT(S?d)=?SELECT(A?bAS)?SELECT(A??)=?例5.4設文法G[S]為：S?aASS?bA?bAA??則SELEC
10、T(S?aAS)={a}SELECT(S?b)=SELECT(A?bA)=SELECT(A??)={a,b}SELECT(S?aAS)?SELECT(S?b)=?SELECT(A?bA)?SELECT(A??)??5.2LL(1)文法的判別1．求出推出?的非終結符2．計算FIRST集3．計算FOLLOW集4．計算SELECT集1．求出推出?的非終結符掃描文法中的產(chǎn)生式刪除所有右部含有終結符的產(chǎn)生式,若這使得以某個非終結符為左部的所有產(chǎn)生式都被刪除，說明該非終結符不能推出?.若某個非終結符的某個產(chǎn)生式的右部為?,說明該非終結符能推出?.刪除以該非終結符為左部的所
11、有產(chǎn)生式.掃描產(chǎn)生式右部的每一個符號若掃描到的非終結符能推出?,則刪除該非終結符，如這樣使產(chǎn)生式右部為空，說明該非終結符能推出?.刪除以該非終結符為左部的所有產(chǎn)生式.若掃描到的非終結符不能推出?,則刪除該產(chǎn)生式，如這樣使以該非終結符為左部的所有產(chǎn)生式都被刪除，說明該非終結符不能推出?.重復②，直到掃描完文法的產(chǎn)生式，數(shù)組中非終結符的特征在沒有改變?yōu)橹?例5.5若文法G[S]為：S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→cS→ABA→εB→εC→ADS→ABC→ADC→AD非終結符SABCD第一次掃描是
