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