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

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

，則ε

∈FIRST(X)；若X∈VN,Y1,Y2,……,Yi都∈VN,且有產生式X→Y1,Y2,……,Yn,當Y1,Y2,……,Yi-1都*ε，則FIRST(Y1)-{ε}，FIRST(Y2)-{ε}，……，FIRST(Yi-1)-{ε}，FIRST(Yi)都包含在FIRST(X)中；當d)中的所有的Yi*ε，（i=1，2，…，n），則FIRST(X)=FIRST(Y1)FIRST(Y2)……FIRST(Yn){ε}.通常情況下，我們要求出所有非終結符的FIRST集合，這是為了將來求FOLLOW集合是用得上；重要的是求產生式右部符號串的FIRST集合，這是求SELECT集合的重要元素。S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c計算FIRST集根據關系圖法計算每個文法符號對應圖中一個節點，對應終結符的節點時用符號本身標記，對應非終結符的節點時用FIRST(A)標記。（這里A表示非終結符）如果文法中有產生式A→αXβ,且α*ε，則從對應A的節點到對應X的節點連一條射線?。环彩菑腇IRST(A)節點有路徑可到達的終結符節點所標記的終結符都為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可能是終結符，也可能是非終結符。計算FOLLOW集根據定義計算對文法中的每一個非終結符A∈VN,計算FOLLOW(A):設S為文法的開始符號，把{#}加入 FOLLOW(S)中；若A→αBβ是一個產生式，則把FIRST(β)的非空元素加入到FOLLOW(A)中；反復使用b)直到每個非終結符的FOLLOW集合不再擴大為止。這里要特別注意：當β*ε時，則FOLLOW(A)的內容也加入到FOLLOW(B)中，這是因為假如有：D→α1Aβ2A→αBβ的兩個產生式，在推導過程中有：S*…α1Aβ2…

…α1αBβ

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

*ε，則從FIRST(A)到FIRST(X)連一射線弧，若X∈VT,則與X相連；凡是從FOLLOW(A)節點有路徑可以到達的終結符或“#”號的節點，其所標記的終結符或“#”號即為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集根據FIRST集和FOLLOW集求SELECT集需要判斷每個終結符是否可推導出空產生式。例題S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c首先，判斷能推出ε的非終結符。求這個非中符的后跟字符集。有些，能夠直觀判斷，有些，需要推導；求FIRST集合，這里需要兩個步驟。先計算每個非終結符的FIRST集合；然后，再求每個產生式右部符號串的FIRST集合。我們需要結果是后者，但前者在計算后者是會用到；求FOLLOW集合，需要注意：FOLLOW集合一定是針對非終結符的；有些可以直觀計算；有些要注意推導，A→αBβ形式時，如果β能推導出ε，則FOLLOW（A）也屬于FOLLOW（B）例題S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c非終結符名稱是否推出εFIRST集合FOLLOW集合S是b,a,ε#A是b,εa,c,#B是a,ε#C否b,a,c#D否a,c#例題產生式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）文法轉換成LL（1）文法？提取左公共因子若文法中含有形如：A→αβ|αγ的產生式，這導致了對相同左部的產生式其右部的FIRST集相交，不滿足LL（1）文法的充分必要條件。將產生式A→αβ|αγ等價變換為：A→α（β|γ）引進新的非終結符A’，使產生式變換為：A→αA’；A’→β|γ一般形式為：A→αβ1|αβ2|αβ3|….|αβn提取左公因子：A→α（β1|β2|β3|….|βn）引進新非終結符A’：A→αA’；A’→β1|β2|….|βn若β1β2β3….βn中仍含有左公共因子，可再次提取，這樣反復進行提取，直到引進新非終結符的有關產生式再無左公共因子為止。例5.6（提取左公共因子后為非LL（1））若文法G1的產生式為：（1）S→αSb（2）S→αS（3）S→ε；對（1）（2）提取左公共因子后得：S→αS（b|ε）S→ε；進一步變換為文法G‘1S→αSAA→bA→εS→ε；例5.7（提取左公共因子后為LL（1））若文法G2的產生式為：1、A→ad；2、A→Bc3、B→aA；4、B→bB產生式2的右部以非終結符開始，因此，左公共因子可能是隱含的。用其相同左部而右部以終結符開始的產生式進行相應替換。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引進新非終結符A’，得文法G‘2A→aA’；A→bBc；A‘→d；A‘→Ac；B→aA；B→bB例5.8（提取左公共因子后，產生無用產生式，必須化簡文法）若有文法G3的產生式為：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）；引進新的非終結符A’后得1、S→aSA‘；2、S→bc；3、A’→d|c；4、A→aS；5、A→b非終結符A變成不可到達的符號，產生式4、5為無用的產生式。例5.9（不能在有限步驟內提取完左公共因子）若有文法G4的產生式為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）；引入新的非終結符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，再提取左共因子，不斷進行。不一定每個文法的左公共因子都能在有限步驟內替換無左公共因子的文法。一個文法提取了左公共因子后，只解決了相同左部產生式右部的FIRST集不相交問題，當改寫后的文法不含空產生式，且無左遞歸時，則改寫后的文法是LL（1）文法，否則還需要用LL（1）文法的判別方式進行判斷才能確定是否為LL（1）文法。消除左遞歸一個文法含有下列形式的產生式時：a)A→Aβb)A→Bβ；B→Aα在a)中可稱為含有左遞歸的規則或稱為直接左遞歸；在b)中為文法中含有左遞歸或間接左遞歸；文法中只要含有a)或b)或者二者皆有均認為文法是左遞歸的。文法是左遞歸時不能采用自頂向下分析方法。例5.11有文法G6為：1、A→aB；2、A→Bb；3、B→Ac；4、B→d；若有輸入串為adbcbcbc#，則分析過程的語法樹如下：AaBAcBbdAaBAcBbAc……利用這樣的推導不是不能推導出匹配，而是要不斷地進行回溯。不是確定的分析方法。含有左遞歸的文法絕對不是LL（1）文法。不能用確定的自頂向下分析法。為了使某些含有左遞歸的文法經等價變換消除左遞歸后可能變成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的右部代替產生式3的非終結符A得B→aBc；B→Bbc；B→d消除左遞歸后得B→（aBc|d）B’；B‘→bcB‘|ε

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

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

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

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

)，把Ａ

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

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

→