編譯原理第五章

自頂向下語(yǔ)法分析第五章5.0概述語(yǔ)法分析是編譯程序的核心部分語(yǔ)法分析的任務(wù)：1、識(shí)別由詞法分析給出的單詞符號(hào)序列是否是給定文法的正確句子；2、按照語(yǔ)言既定的語(yǔ)法規(guī)則，對(duì)字符串形式的源程序進(jìn)行語(yǔ)法檢查，并識(shí)別出相應(yīng)的語(yǔ)法成分。語(yǔ)法分析的處理依據(jù)是語(yǔ)言的文法規(guī)則分析結(jié)果是識(shí)別出的無(wú)語(yǔ)法錯(cuò)誤的語(yǔ)法成分，可以與語(yǔ)法樹的形式來(lái)表示。語(yǔ)法分析的關(guān)鍵是句型識(shí)別問(wèn)題設(shè)給定文法G和字符串（句子），檢查、判斷句子是否是文法G所能產(chǎn)生的合法的句子，同時(shí)檢查和處理語(yǔ)法錯(cuò)誤。語(yǔ)法分析器的作用及在編譯程序中的作用scanner語(yǔ)法分析器語(yǔ)義分析。。。。。。。。。。。。。中間代碼生成源程序源程序取下一個(gè)單詞分析樹源程序語(yǔ)法分析的方法分成兩大類語(yǔ)法分析自頂向下分析方法自底向上分析方法確定的自頂向下分析方法不確定的自頂向下分析方法算符優(yōu)先分析方法LR分析方法自頂向下語(yǔ)法分析也稱面向目標(biāo)的分析方法：從文法的開(kāi)始符號(hào)出發(fā)推導(dǎo)出與輸入的單詞串完全相匹配的句子，若輸入串是給定文法的句子，則必能推出，否則出錯(cuò)。確定的分析方法：對(duì)文法有一定的限制，方法簡(jiǎn)單、直觀，便于實(shí)現(xiàn)，是常用的方法。不確定的分析方法：帶回溯的分析方法，是一種窮舉的試探方法，效率低、代價(jià)高，較少使用。5．1確定的自頂向下分析思想給定的條件是：1、已知文法條件；2、給出輸入的字符串。判斷該輸入的字符串是已知文法的句子。判定的思路是：從文法開(kāi)始符號(hào)出發(fā)，根據(jù)輸入的符號(hào)唯一地確定選用哪個(gè)產(chǎn)生式替換相應(yīng)的非終結(jié)符往下推導(dǎo)。最終與輸入字符串相匹配。實(shí)際上，根據(jù)文法的特點(diǎn)（確切地講根據(jù)產(chǎn)生式的不同特點(diǎn)），推導(dǎo)過(guò)程的復(fù)雜程度也不一樣。如果文法有如下的特點(diǎn)：（1）每個(gè)產(chǎn)生式的右部都由終結(jié)符開(kāi)始。（2）如果兩個(gè)產(chǎn)生式有相同的左部，那么它們的右部由不同的終結(jié)符開(kāi)始。對(duì)于這樣的文法顯然在推導(dǎo)過(guò)程中完全可以根據(jù)當(dāng)前的輸入符號(hào)決定選擇那個(gè)產(chǎn)生式往下推導(dǎo)，也就是說(shuō)分析過(guò)程是唯一確定的。例5.1若有文法G[S]:S→pA│qBA→cAd│aB→dB│b若輸入串為pccadd。推導(dǎo)判斷是否合法？文法是確定性的文法，但是被識(shí)別的句子可能是不符合文法的！如果文法有如下特點(diǎn)：產(chǎn)生式的右部不全是由終結(jié)符開(kāi)始。如果兩個(gè)產(chǎn)生式有相同的左部，它們的右部是由不同的終結(jié)符或非終結(jié)符開(kāi)始。文法中無(wú)空產(chǎn)生式。如果左部相同，右部不同，但是右部的符號(hào)串可以推導(dǎo)出的首符號(hào)集不相交，因而，可以根據(jù)輸入符號(hào)串判定相應(yīng)的產(chǎn)生式進(jìn)行推導(dǎo)。這樣的推導(dǎo)過(guò)程仍然是確定的。例5-2：若有文法G[S]：S→ApS→BqA→aA→cAB→bB→dB判斷符號(hào)串ccap表面看不確定，實(shí)際上確定！例5.2的推導(dǎo)過(guò)程如下：開(kāi)始符號(hào)S的兩個(gè)產(chǎn)生式的右部都不是以終結(jié)符開(kāi)始；根據(jù)右部非終結(jié)符所推導(dǎo)出的首字符集，判斷選擇那個(gè)產(chǎn)生式；FIRST（Ap）={a,c}；FIRST(Bq)={b,d}；兩個(gè)字符集不相交；唯一確定S→Ap作為選擇。S→Ap→cAp→ccAp→ccap為推導(dǎo)過(guò)程。輸入串ccap為可以接受。存在一個(gè)回溯的問(wèn)題，即在替換某個(gè)非終結(jié)符時(shí)，存在多種選擇，當(dāng)選擇某個(gè)推導(dǎo)到后面可能無(wú)解，必須退回重新選擇。消除回溯或者避免回溯可以通過(guò)求解首字符集，判斷首字符集不相交。

定義：設(shè)G=(VT，VN，S，P)是上下文無(wú)關(guān)文法。FIRST(α)={a│α*aβ，a∈VT，α，β∈V*}若α*ε，則規(guī)定ε∈FIRST(α)稱FIRST(α)為α的開(kāi)始符號(hào)集合或首字符集。文法G[S]：S→ApS→BqA→aA→cAB→bB→dB產(chǎn)生式左部分相同的右部分的首字符集都不相交。所以，該文法可以進(jìn)行自頂向下的確定性分析。那么如果在產(chǎn)生式中存在空產(chǎn)生式，如何判定它可以確定的進(jìn)行語(yǔ)法分析？例5．3若有文法G[S]：S→aA；S→d；A→bAS；A→ε。判斷字符串：abd推導(dǎo)過(guò)程：SaAabASabεSabSabd當(dāng)某個(gè)非終結(jié)符的產(chǎn)生式中含有空產(chǎn)生式時(shí)，它的非空產(chǎn)生式右部的首字符集兩兩不相交，并且在推導(dǎo)過(guò)程中緊跟在該非終結(jié)符右邊可能出現(xiàn)的終結(jié)符也不相交，則仍可以構(gòu)造確定的語(yǔ)法分析。這種情況下就要看該非終結(jié)符的后跟符號(hào)集（FOLLOW）。通常情況下，只需要考慮FIRST集合就可以了。但是，當(dāng)產(chǎn)生式右部出現(xiàn)ε或者能夠推導(dǎo)出ε，則應(yīng)該考慮該產(chǎn)生式左部的非終結(jié)符的后跟字符集。后跟符號(hào)集（FOLLOW）定義：設(shè)G=(VT,VN,S,P)是上下文無(wú)關(guān)文法，A∈VN，S是開(kāi)始符號(hào)。FOLLOW(A)={a│S*….Aa….，a∈VT，}若有S*….A，則規(guī)定#∈FOLLOW(A)#作為輸入串的結(jié)束符號(hào)。假設(shè)文法中有形如下的產(chǎn)生式：A→αA→β若α和β不能同時(shí)推導(dǎo)為ε。如α不為ε，β可以為ε。在推導(dǎo)過(guò)程中，可以確定地替換A的條件是FIRST(α)∩(FIRST(β)UFOLLOW(A))=Φ事實(shí)上，在語(yǔ)法分析上還是追求確定的自上而下的分析方法。當(dāng)確定首字符集和后跟字符集，就可以形成一個(gè)新的字符集：選擇字符集SELECT。根據(jù)對(duì)選擇字符集的判斷就可以判定語(yǔ)法分析是否可以為確定的。給定上下文無(wú)關(guān)文法的產(chǎn)生式A→aA∈Vn,a∈V*，若α為非空的產(chǎn)生式，SELECT（A→α）=FIRST（α）若α包含空產(chǎn)生式，SELECT（A→α）=（FIRST（α）-{ε}）∪FOLLOW(A)通過(guò)FIRST（α）和FOLLOW(A)就可以求出SELECT（A→α）從而就可以判定針對(duì)這個(gè)非終結(jié)符是否可以進(jìn)行確定的語(yǔ)法分析。我們將滿足自頂向下分析技術(shù)條件的文法為L(zhǎng)L（1）文法。一個(gè)上下文無(wú)關(guān)文法是LL（1）文法的充分必要條件是，對(duì)每個(gè)非終結(jié)符A的兩個(gè)不同產(chǎn)生式，A→α；A→β，滿足：SELECT（A→α）∩SELECT（A→β）=Φ；其中，α、β不能同時(shí)包含空產(chǎn)生式。LL（1）文法含義是：第一個(gè)L表明自頂向下分析是從左向右掃描輸入串，第二個(gè)L表明分析過(guò)程是用最左推導(dǎo)，1表明只需向右看一個(gè)符號(hào)便可以決定如何推導(dǎo)即選擇哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)。選擇集合SELECT：例：S→aAS→dA→εA→bASSELECT(S→aA)=FIRST（α）={a}SELECT(S→d)=FIRST（d）=goulbcdSELECT(A→bAS)=SELECT(A→ε)={a,d,#}SELECT(S→aA)∩SELECT(S→d)=SELECT(A→bAS)∩SELECT(A→ε)=可知文法為L(zhǎng)L（1）文法，可用確定的自頂向下分析。例題S→pAS→qBA→cAdA→aB→dBB→b每個(gè)產(chǎn)生式右部都由終結(jié)符開(kāi)始如果兩個(gè)產(chǎn)生式有相同的左部,那么它們的右部由不同的終結(jié)符開(kāi)始這是直觀的、確定的分析方法的文法例題S→ApS→BqA→cAA→aB→dBB→b產(chǎn)生式右部不都由終結(jié)符開(kāi)始如果兩個(gè)產(chǎn)生式有相同的左部,那么它們的右部由不同的終結(jié)符或非終結(jié)符開(kāi)始如果左部相同，右部的符號(hào)串可以推導(dǎo)出的首字符集合不相交文法中無(wú)空產(chǎn)生式這是隱蔽的，但是是確定的分析方法的文法例題S→aAS→dA→bASA→ε當(dāng)某個(gè)非終結(jié)符的產(chǎn)生式中含有空產(chǎn)生式時(shí)，它的非空產(chǎn)生式右部的首字符集合兩兩不相交并且在推導(dǎo)過(guò)程中緊跟該非終結(jié)符右邊可能出現(xiàn)的終結(jié)符集合也不相交仍然是確定的分析方法的文法后跟字符集合的求解一定要注意：它是針對(duì)某個(gè)非終結(jié)符的計(jì)算；它將來(lái)要用到以這個(gè)非終結(jié)符作為左部，并且能夠推導(dǎo)出空的產(chǎn)生式在推導(dǎo)過(guò)程中，有可能出現(xiàn)在該非終結(jié)符后面的終結(jié)符。因?yàn)槭峭茖?dǎo)，所以一定要從開(kāi)始符號(hào)出發(fā)。特別要注意#，什么時(shí)候?qū)儆诤蟾址?。例題S→aASS→bA→bAA→ε最后一個(gè)產(chǎn)生式可以推導(dǎo)出空，在將來(lái)分析過(guò)程中，就很有可能用到它的這個(gè)特點(diǎn)，因此，需要求出產(chǎn)生式左部非終結(jié)符的后跟字符集。這個(gè)產(chǎn)生式的SELECT集合，除了包括首字符集以外，還應(yīng)考慮A的后跟字符集A的后跟字符集中不包括#，這是因?yàn)?，從S出發(fā)進(jìn)行推導(dǎo)，永遠(yuǎn)不會(huì)出現(xiàn)S→……A這樣的形式5．2LL（1）文法的判別當(dāng)我們需選用自頂向下分析技術(shù)時(shí)，首先必須判定所給文法是否是LL（1）文法。我們對(duì)任給文法需要計(jì)算FIRST、FOLLOW、SELECT集合，進(jìn)而判別文法是否為L(zhǎng)L（1）文法。SELECT是關(guān)于產(chǎn)生式的；FIRST包含兩個(gè)情況：一是產(chǎn)生式右部；另一個(gè)是非終結(jié)符；FOLLOW是關(guān)于能推出空的產(chǎn)生式左部的非終結(jié)符的；求出能推出ε的非終結(jié)符利用一個(gè)以文法的非終結(jié)符個(gè)數(shù)為上界，每個(gè)非終結(jié)符為元素的一維數(shù)組。逐步掃描，確定能夠推出ε的非終結(jié)符。計(jì)算FIRST集根據(jù)定義計(jì)算FIRST(α)={a│α*aβ,a∈VT,α、β∈V*}若α*ε，則規(guī)定ε∈FIRST(α)；對(duì)每個(gè)文法符號(hào)X∈V計(jì)算FIRST(X),有：若X∈VT,則FIRST(X)={X}；若X∈VN,且有產(chǎn)生式X→a……，a∈VT,則a∈FIRST(X)；若X∈VN,且X→ε

，則ε

∈FIRST(X)；若X∈VN,Y1,Y2,……,Yi都∈VN,且有產(chǎn)生式X→Y1,Y2,……,Yn,當(dāng)Y1,Y2,……,Yi-1都*ε，則FIRST(Y1)-{ε}，F(xiàn)IRST(Y2)-{ε}，……，F(xiàn)IRST(Yi-1)-{ε}，F(xiàn)IRST(Yi)都包含在FIRST(X)中；當(dāng)d)中的所有的Yi*ε，（i=1，2，…，n），則FIRST(X)=FIRST(Y1)FIRST(Y2)……FIRST(Yn){ε}.通常情況下，我們要求出所有非終結(jié)符的FIRST集合，這是為了將來(lái)求FOLLOW集合是用得上；重要的是求產(chǎn)生式右部符號(hào)串的FIRST集合，這是求SELECT集合的重要元素。S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c計(jì)算FIRST集根據(jù)關(guān)系圖法計(jì)算每個(gè)文法符號(hào)對(duì)應(yīng)圖中一個(gè)節(jié)點(diǎn)，對(duì)應(yīng)終結(jié)符的節(jié)點(diǎn)時(shí)用符號(hào)本身標(biāo)記，對(duì)應(yīng)非終結(jié)符的節(jié)點(diǎn)時(shí)用FIRST(A)標(biāo)記。（這里A表示非終結(jié)符）如果文法中有產(chǎn)生式A→αXβ,且α*ε，則從對(duì)應(yīng)A的節(jié)點(diǎn)到對(duì)應(yīng)X的節(jié)點(diǎn)連一條射線??；凡是從FIRST(A)節(jié)點(diǎn)有路徑可到達(dá)的終結(jié)符節(jié)點(diǎn)所標(biāo)記的終結(jié)符都為FIRST(A)成員；ε是否為FIRST(A)成員由直接方法判斷。bcaFIRST(S)FIRST(B)FIRST(D)FIRST(A)FIRST(C)S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→cX可能是終結(jié)符，也可能是非終結(jié)符。計(jì)算FOLLOW集根據(jù)定義計(jì)算對(duì)文法中的每一個(gè)非終結(jié)符A∈VN,計(jì)算FOLLOW(A):設(shè)S為文法的開(kāi)始符號(hào)，把{#}加入 FOLLOW(S)中；若A→αBβ是一個(gè)產(chǎn)生式，則把FIRST(β)的非空元素加入到FOLLOW(A)中；反復(fù)使用b)直到每個(gè)非終結(jié)符的FOLLOW集合不再擴(kuò)大為止。這里要特別注意：當(dāng)β*ε時(shí)，則FOLLOW(A)的內(nèi)容也加入到FOLLOW(B)中，這是因?yàn)榧偃缬校篋→α1Aβ2A→αBβ的兩個(gè)產(chǎn)生式，在推導(dǎo)過(guò)程中有：S*…α1Aβ2…

…α1αBβ

β2…事實(shí)上，往往我們先求出所有的非終結(jié)符的FOLLOW集合，然后根據(jù)產(chǎn)生式是否能推導(dǎo)出空來(lái)決定是否采用計(jì)算FOLLOW集根據(jù)關(guān)系圖法計(jì)算文法G中的每個(gè)符號(hào)和“#”對(duì)應(yīng)圖中的一個(gè)節(jié)點(diǎn)，對(duì)應(yīng)終結(jié)符的節(jié)點(diǎn)用符號(hào)本身標(biāo)記，對(duì)應(yīng)非終結(jié)符的節(jié)點(diǎn)，則用FOLLOW(A)或FIRST(A)標(biāo)記；從開(kāi)始符號(hào)S的FOLLOW(S)節(jié)點(diǎn)到“#”號(hào)的節(jié)點(diǎn)連接一個(gè)射線??；如果文法中有產(chǎn)生式A→αBβX，且β*ε，則從FOLLOW(B)節(jié)點(diǎn)到FIRST(X)節(jié)點(diǎn)連接一射線弧，當(dāng)X∈VT,則與X相連；如果文法中有產(chǎn)生式A→αBβ，且β*ε，則從FOLLOW(B)節(jié)點(diǎn)到FOLLOW(A)節(jié)點(diǎn)連接一射線弧；對(duì)每一個(gè)FIRST(A)節(jié)點(diǎn)，如果有產(chǎn)生式A→αXβ，且α

*ε，則從FIRST(A)到FIRST(X)連一射線弧，若X∈VT,則與X相連；凡是從FOLLOW(A)節(jié)點(diǎn)有路徑可以到達(dá)的終結(jié)符或“#”號(hào)的節(jié)點(diǎn)，其所標(biāo)記的終結(jié)符或“#”號(hào)即為FOLLOW(A)的成員。S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c#caFOLLOW(S)FIRST(B)FIRST(D)FOLLOW(A)FOLLOW(C)FOLLOW(B)FOLLOW(D)計(jì)算SELECT集根據(jù)FIRST集和FOLLOW集求SELECT集需要判斷每個(gè)終結(jié)符是否可推導(dǎo)出空產(chǎn)生式。例題S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c首先，判斷能推出ε的非終結(jié)符。求這個(gè)非中符的后跟字符集。有些，能夠直觀判斷，有些，需要推導(dǎo)；求FIRST集合，這里需要兩個(gè)步驟。先計(jì)算每個(gè)非終結(jié)符的FIRST集合；然后，再求每個(gè)產(chǎn)生式右部符號(hào)串的FIRST集合。我們需要結(jié)果是后者，但前者在計(jì)算后者是會(huì)用到；求FOLLOW集合，需要注意：FOLLOW集合一定是針對(duì)非終結(jié)符的；有些可以直觀計(jì)算；有些要注意推導(dǎo)，A→αBβ形式時(shí)，如果β能推導(dǎo)出ε，則FOLLOW（A）也屬于FOLLOW（B）例題S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c非終結(jié)符名稱是否推出εFIRST集合FOLLOW集合S是b,a,ε#A是b,εa,c,#B是a,ε#C否b,a,c#D否a,c#例題產(chǎn)生式SELECT集合S→ABb,a,#S→bCbA→εa,c,#A→bbB→ε#B→aDaC→ADa,b,cC→bbD→aSaD→ccabc#S→AB→AB;→bC→ABA→εA→b→ε→εB→aD→εC→AD→AD;→b→ADD→aS→c5.3某些非LL（1）文法到LL（1）文法的等價(jià)交換確定的自頂向下分析要求對(duì)給定語(yǔ)言的文法必須是LL（1）形式。但是，不是所有的語(yǔ)言都有LL（1）文法。不是LL（1）文法的原因，要么是直接或間接左遞歸；要么含有左公共因子。左公共因子：文法中形如A→αβ|αγ直接左遞歸：A→Aβ；間接左遞歸：A→Bβ；B→Aα消除左遞歸或左公共因子，能否將非LL（1）文法轉(zhuǎn)換成LL（1）文法？提取左公共因子若文法中含有形如：A→αβ|αγ的產(chǎn)生式，這導(dǎo)致了對(duì)相同左部的產(chǎn)生式其右部的FIRST集相交，不滿足LL（1）文法的充分必要條件。將產(chǎn)生式A→αβ|αγ等價(jià)變換為：A→α（β|γ）引進(jìn)新的非終結(jié)符A’，使產(chǎn)生式變換為：A→αA’；A’→β|γ一般形式為：A→αβ1|αβ2|αβ3|….|αβn提取左公因子：A→α（β1|β2|β3|….|βn）引進(jìn)新非終結(jié)符A’：A→αA’；A’→β1|β2|….|βn若β1β2β3….βn中仍含有左公共因子，可再次提取，這樣反復(fù)進(jìn)行提取，直到引進(jìn)新非終結(jié)符的有關(guān)產(chǎn)生式再無(wú)左公共因子為止。例5.6（提取左公共因子后為非LL（1））若文法G1的產(chǎn)生式為：（1）S→αSb（2）S→αS（3）S→ε；對(duì)（1）（2）提取左公共因子后得：S→αS（b|ε）S→ε；進(jìn)一步變換為文法G‘1S→αSAA→bA→εS→ε；例5.7（提取左公共因子后為L(zhǎng)L（1））若文法G2的產(chǎn)生式為：1、A→ad；2、A→Bc3、B→aA；4、B→bB產(chǎn)生式2的右部以非終結(jié)符開(kāi)始，因此，左公共因子可能是隱含的。用其相同左部而右部以終結(jié)符開(kāi)始的產(chǎn)生式進(jìn)行相應(yīng)替換。1、A→ad；2、A→aAc；3、A→bBc4、B→aA；5、B→bB提取1、2的左公共因子得：A→a（d|Ac）；A→bBc；B→aA；B→bB引進(jìn)新非終結(jié)符A’，得文法G‘2A→aA’；A→bBc；A‘→d；A‘→Ac；B→aA；B→bB例5.8（提取左公共因子后，產(chǎn)生無(wú)用產(chǎn)生式，必須化簡(jiǎn)文法）若有文法G3的產(chǎn)生式為：1、S→aSd；2、S→Ac；3、A→aS；4、A→b用3、4中的右部替換2中的右部的A，得1、S→aSd；2、S→aSc；3、S→bc；4、A→aS；5、A→b對(duì)1、2提取左公共因子

S→aS（d|c）；引進(jìn)新的非終結(jié)符A’后得1、S→aSA‘；2、S→bc；3、A’→d|c；4、A→aS；5、A→b非終結(jié)符A變成不可到達(dá)的符號(hào)，產(chǎn)生式4、5為無(wú)用的產(chǎn)生式。例5.9（不能在有限步驟內(nèi)提取完左公共因子）若有文法G4的產(chǎn)生式為1、S→Ap|Bq；2、A→aAp|d；3、B→aBq|e用2、3的右部替換1中的A、B得1、S→aApp|aBqq；2、S→dp|eq3、A→aAp|d；4、B→aBq|e對(duì)1提取左共因子的S→a（App|Bqq）；引入新的非終結(jié)符S‘后得1、S→aS’；2、S→dp|eq；3、S’→App|Bqq；4、A→aAp|d；5、B→aBq|e；用4、5中的右部替換3中的A、B，再提取左共因子，不斷進(jìn)行。不一定每個(gè)文法的左公共因子都能在有限步驟內(nèi)替換無(wú)左公共因子的文法。一個(gè)文法提取了左公共因子后，只解決了相同左部產(chǎn)生式右部的FIRST集不相交問(wèn)題，當(dāng)改寫后的文法不含空產(chǎn)生式，且無(wú)左遞歸時(shí)，則改寫后的文法是LL（1）文法，否則還需要用LL（1）文法的判別方式進(jìn)行判斷才能確定是否為L(zhǎng)L（1）文法。消除左遞歸一個(gè)文法含有下列形式的產(chǎn)生式時(shí)：a)A→Aβb)A→Bβ；B→Aα在a)中可稱為含有左遞歸的規(guī)則或稱為直接左遞歸；在b)中為文法中含有左遞歸或間接左遞歸；文法中只要含有a)或b)或者二者皆有均認(rèn)為文法是左遞歸的。文法是左遞歸時(shí)不能采用自頂向下分析方法。例5.11有文法G6為：1、A→aB；2、A→Bb；3、B→Ac；4、B→d；若有輸入串為adbcbcbc#，則分析過(guò)程的語(yǔ)法樹如下：AaBAcBbdAaBAcBbAc……利用這樣的推導(dǎo)不是不能推導(dǎo)出匹配，而是要不斷地進(jìn)行回溯。不是確定的分析方法。含有左遞歸的文法絕對(duì)不是LL（1）文法。不能用確定的自頂向下分析法。為了使某些含有左遞歸的文法經(jīng)等價(jià)變換消除左遞歸后可能變成LL（1）文法，可采用下列變換公式：a)消除直接左遞歸，把直接左遞歸改寫為右遞歸b）消除間接左遞歸，先將間接變直接，然后，按a）c）消除文法中一切左遞歸的算法。消除直接左遞歸，把直接左遞歸改寫為右遞歸對(duì)文法：S→Sa；S→b可改寫為：S→bS’；S’→aS’|ε新舊文法的語(yǔ)句集都為:{ban|n>=0}所以文法等價(jià).消除間接左遞歸對(duì)文法：A→aB；A→Bb；B→Ac；B→d包含間接左遞歸：用1、2的右部代替產(chǎn)生式3的非終結(jié)符A得B→aBc；B→Bbc；B→d消除左遞歸后得B→（aBc|d）B’；B‘→bcB‘|ε

再把原來(lái)的1、2產(chǎn)生式加入得A→aB；A→Bb；B→（aBc|d）B’；B‘→bcB‘|ε

消除文法中一切左遞歸的算法1、把文法中的所有非終結(jié)符按某個(gè)順序排序；如：A1，A2，A3，……，An2、從A1開(kāi)始消除左部為A1的產(chǎn)生式的直接左遞歸，然后把左部為A1的所有規(guī)則的右部逐個(gè)替換左部為A2右部為A1開(kāi)始的產(chǎn)生式中的A1，并消除左部為A2的產(chǎn)生式中的直接左遞歸。以此類推。3、去掉無(wú)用產(chǎn)生式。例有文法產(chǎn)生式為：（1）S→Qc|c；（2）Q→Rb|b；（3）R→Sa|a；該文法的每個(gè)非終結(jié)符互為間接左遞歸。一、若非終結(jié)符按S、Q、R排序左部為S的產(chǎn)生式無(wú)直接左遞歸，2中又不含S，所以將1的右部代入3中得到：4、R→Qca|ca|a；（至此1號(hào)非終結(jié)符解決完畢）解決2號(hào)非終結(jié)符Q，將2中的右部代入4得到：5、R→Rbca|ca|a；對(duì)5消除直接左遞歸得：R→（bca|ca|a）R’；R‘→bcaR’|ε最終文法變?yōu)椋海?）S→Qc|c；（2）Q→Rb|b；（2）R→（bca|ca|a）R’；（4）R‘→bcaR’|ε二、若非終結(jié)符按R、Q、S排序則把3代入2：Q→Sab|ab|b；再將該產(chǎn)生式代入1得：S→Sabc|abc|bc|c；消除直接左遞歸，最終文法變?yōu)椋篠→（abc|bc|c）S’；S‘→abcS’|ε；Q→Rb|b；R→Sa|a5.4不確定的自頂向下分析思想由于相同左部的產(chǎn)生式的右部FIRST集交集不為空而引起回溯。由于相同左部非終結(jié)符的右部存在能推導(dǎo)出空產(chǎn)生式，且該非終結(jié)符FOLLOW集中含有其他右部FIRST集的元素。由于文法含有左遞歸而引起回溯5.5確定的自頂向下分析方法預(yù)測(cè)分析方法一個(gè)預(yù)測(cè)分析器由三個(gè)部分組成：預(yù)測(cè)分析程序、先進(jìn)后出棧、預(yù)測(cè)分析器表。其中只有預(yù)測(cè)分析器表與文法有關(guān)。表驅(qū)動(dòng)預(yù)測(cè)分析程序模型

Input#總控程序預(yù)測(cè)分析表stack預(yù)測(cè)分析表可用一個(gè)矩陣M(或稱二維數(shù)組)表示。矩陣元素M[A,a]中的下標(biāo)A表示非終結(jié)符，a為終結(jié)符或句子括號(hào)“#”，矩陣元素M[A,a]中的內(nèi)容為存放著一條關(guān)于A的產(chǎn)生式，表明當(dāng)用非終結(jié)符A向下推導(dǎo)時(shí)，面臨輸入符號(hào)a時(shí)，應(yīng)采取的候選產(chǎn)生式，若無(wú)產(chǎn)生式，元素內(nèi)容轉(zhuǎn)向出錯(cuò)處理的信息。預(yù)測(cè)分析表構(gòu)造算法1.對(duì)文法G的每個(gè)產(chǎn)生式Ａ

,若每個(gè)終結(jié)符或“#”用a表示；若aSELECT(Ａ

)，把Ａ

加至[A,a]中，2.把所有無(wú)定義的[A,a]標(biāo)上“出錯(cuò)標(biāo)志”。為了使表簡(jiǎn)化，其產(chǎn)生式左部可以不寫入表中，表中空白處為出錯(cuò)?？梢宰C明，一個(gè)文法G的予測(cè)分析表不含多重入口，當(dāng)且僅當(dāng)該文法是LL(1)的例：G[E]:E→E+T|TT→T*F|FF→i|(E)

解：(1)判斷文法是否為L(zhǎng)L(1)文法由于文法中含有左遞歸，所與必須先消除左遞歸，使文法變?yōu)椋篏[E]:(1)E→TE’(2)E’

→