編譯原理第五章

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

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

…α1αBβ

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

*ε，則從FIRST(A)到FIRST(X)連一射線弧，若X∈VT,則與X相連；凡是從FOLLOW(A)節(jié)點有路徑可以到達的終結(jié)符或“#”號的節(jié)點，其所標(biāo)記的終結(jié)符或“#”號即為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)計算SELECT集根據(jù)FIRST集和FOLLOW集求SELECT集需要判斷每個終結(jié)符是否可推導(dǎo)出空產(chǎn)生式。例題S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c首先，判斷能推出ε的非終結(jié)符。求這個非中符的后跟字符集。有些，能夠直觀判斷，有些，需要推導(dǎo)；求FIRST集合，這里需要兩個步驟。先計算每個非終結(jié)符的FIRST集合；然后，再求每個產(chǎn)生式右部符號串的FIRST集合。我們需要結(jié)果是后者，但前者在計算后者是會用到；求FOLLOW集合，需要注意：FOLLOW集合一定是針對非終結(jié)符的；有些可以直觀計算；有些要注意推導(dǎo)，A→αBβ形式時，如果β能推導(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）文法的等價交換確定的自頂向下分析要求對給定語言的文法必須是LL（1）形式。但是，不是所有的語言都有LL（1）文法。不是LL（1）文法的原因，要么是直接或間接左遞歸；要么含有左公共因子。左公共因子：文法中形如A→αβ|αγ直接左遞歸：A→Aβ；間接左遞歸：A→Bβ；B→Aα消除左遞歸或左公共因子，能否將非LL（1）文法轉(zhuǎn)換成LL（1）文法？提取左公共因子若文法中含有形如：A→αβ|αγ的產(chǎn)生式，這導(dǎo)致了對相同左部的產(chǎn)生式其右部的FIRST集相交，不滿足LL（1）文法的充分必要條件。將產(chǎn)生式A→αβ|αγ等價變換為：A→α（β|γ）引進新的非終結(jié)符A’，使產(chǎn)生式變換為：A→αA’；A’→β|γ一般形式為：A→αβ1|αβ2|αβ3|….|αβn提取左公因子：A→α（β1|β2|β3|….|βn）引進新非終結(jié)符A’：A→αA’；A’→β1|β2|….|βn若β1β2β3….βn中仍含有左公共因子，可再次提取，這樣反復(fù)進行提取，直到引進新非終結(jié)符的有關(guān)產(chǎn)生式再無左公共因子為止。例5.6（提取左公共因子后為非LL（1））若文法G1的產(chǎn)生式為：（1）S→αSb（2）S→αS（3）S→ε；對（1）（2）提取左公共因子后得：S→αS（b|ε）S→ε；進一步變換為文法G‘1S→αSAA→bA→εS→ε；例5.7（提取左公共因子后為LL（1））若文法G2的產(chǎn)生式為：1、A→ad；2、A→Bc3、B→aA；4、B→bB產(chǎn)生式2的右部以非終結(jié)符開始，因此，左公共因子可能是隱含的。用其相同左部而右部以終結(jié)符開始的產(chǎ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引進新非終結(jié)符A’，得文法G‘2A→aA’；A→bBc；A‘→d；A‘→Ac；B→aA；B→bB例5.8（提取左公共因子后，產(chǎn)生無用產(chǎ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對1、2提取左公共因子

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

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

消除文法中一切左遞歸的算法1、把文法中的所有非終結(jié)符按某個順序排序；如：A1，A2，A3，……，An2、從A1開始消除左部為A1的產(chǎn)生式的直接左遞歸，然后把左部為A1的所有規(guī)則的右部逐個替換左部為A2右部為A1開始的產(chǎn)生式中的A1，并消除左部為A2的產(chǎn)生式中的直接左遞歸。以此類推。3、去掉無用產(chǎn)生式。例有文法產(chǎn)生式為：（1）S→Qc|c；（2）Q→Rb|b；（3）R→Sa|a；該文法的每個非終結(jié)符互為間接左遞歸。一、若非終結(jié)符按S、Q、R排序左部為S的產(chǎn)生式無直接左遞歸，2中又不含S，所以將1的右部代入3中得到：4、R→Qca|ca|a；（至此1號非終結(jié)符解決完畢）解決2號非終結(jié)符Q，將2中的右部代入4得到：5、R→Rbca|ca|a；對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ù)測分析方法一個預(yù)測分析器由三個部分組成：預(yù)測分析程序、先進后出棧、預(yù)測分析器表。其中只有預(yù)測分析器表與文法有關(guān)。表驅(qū)動預(yù)測分析程序模型

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

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

)，把Ａ

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

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

→