《編譯原理》課件第3章

第3章語法分析3.1文法和語言

3.2推導與語法樹

3.3自頂向下的語法分析

3.4自底向上的語法分析

3.5規(guī)范規(guī)約的自底向上語法分析方法習題三

語法分析是編譯過程的核心部分，其基本任務(wù)是根據(jù)語言的語法規(guī)則進行語法分析，若不存在語法錯誤則給出正確的語法結(jié)構(gòu)并為語義分析和代碼生成做準備。在描述程序語言的語法結(jié)構(gòu)時，需借助于上下文無關(guān)文法，而文法是描述程序語言的依據(jù)。語法分析的方法通常分為兩類，即自頂向下分析方法和自底向上分析方法。所謂自頂向下分析法，就是從文法的開始符號出發(fā)，根據(jù)文法的規(guī)則進行推導，最終推導出給定的句子來。自底向上的分析法則是從給定的輸入串開始，根據(jù)文法規(guī)則逐步進行歸約，直至歸約到文法的開始符號為止。3.1文法和語言

3.1.1文法和語言的概念

1．語言通常我們用Σ表示字母表，字母表中的每個元素稱為字符或符號。不同語言的字母表可能是不同的，程序語言的字母表通常是ASCII字符集。由字母表Σ中的字符所組成的有窮系列稱為Σ上的字符串或字，字母表Σ上的所有字符串(包括空串)組成的集合用Σ*表示。那么，對字母表Σ來說，Σ*上的任意一個子集都稱為Σ上的一個語言，記為L(LΣ*)，該語言的每一個字符串稱為語言L的一個語句或句子。例如，設(shè)Σ={a,b,c}，則L={ε,a,aa,ab,aaa,aab,aba,abb,…}為Σ上的一個語言。如果a表示字母、b表示數(shù)字、c看作其它符號，則L即是程序語言中的標識符集，其中的每個標識符就是標識符集中的一個句子。

2．文法文法通常表示成四元組G[S]=(VT，VN，S，ξ)，其中：

(1)?VT為終結(jié)符號集，這是一個非空有限集，它的每個元素稱為終結(jié)符號；

(2)?VN為非終結(jié)符集，它也是一個非空有限集，其每個元素稱為非終結(jié)符號，且有VT∩VN=Φ；

(3)?S為一文法開始符，是一個特殊的非終結(jié)符號，即S∈VN；

(4)?ξ是產(chǎn)生式的非空有限集，其中每個產(chǎn)生式(或稱規(guī)則)是一序偶(α，β)，通常寫作α→β或α::=β讀作“α是β”或“α定義為β”。在此，α為產(chǎn)生式的左部，而β為產(chǎn)生式的右部，α、β是由終結(jié)符和非終結(jié)符組成的符號串，α∈(VT∪VN)+且至少有一個非終結(jié)符，而β∈(VT∪VN)*。終結(jié)符號是指語言不可再分的基本符號，通常是一個語言的字母表；終結(jié)符代表了語法的最小元素，是一種個體記號。非終結(jié)符號也稱語法變量，它代表語法實體或語法范疇；非終結(jié)符代表一個一定的語法概念，因此，一個非終結(jié)符是一個類、一個集合。例如，在程序語言中，可以把變量、常數(shù)、“+”、“*”等看作是終結(jié)符，而像“算術(shù)表達式”這個非終結(jié)符則代表著一定算術(shù)式組成的類，如i*(i+i)、i+i+i等；也即每個非終結(jié)符代表著由一些終結(jié)符和非終結(jié)符且滿足一定規(guī)則的符號串組成的集合。文法開始符號是一個特殊的非終結(jié)符，它代表文法所定義的語言中我們最終感興趣的語法實體，即語言的目標，而其它語法實體只是構(gòu)造語言目標的中間變量。如表達式文法的語言目標是表達式，而程序語言的目標通常為程序。

產(chǎn)生式(也稱產(chǎn)生規(guī)則或規(guī)則)是定義語法實體的一種書寫規(guī)則。一個語法實體的相關(guān)規(guī)則可能不止一個。例如，有：P→α1P→α2P→αn為書寫方便，可將這些有相同左部的產(chǎn)生式合并為一個，即縮寫成P→α1∣α2∣…∣αn其中，每個αi(i=1,2,…,n)稱為P的一個候選式，直豎“∣”讀為“或”，它與“→”一樣是用來描述文法的元語言符號(即不屬于Σ的字符)。

例3.1

試構(gòu)造產(chǎn)生標識符的文法。

[解答]首先，標識符是以字母開頭的字母數(shù)字串，我們用L表示“字母”類非終結(jié)符，用D表示“數(shù)字”類非終結(jié)符，而用T表示“字母或數(shù)字”類非終結(jié)符，則有：

L→a∣b∣…∣z D→0∣1∣…∣9 T→L∣D其次，如果用S表示“字母數(shù)字串”類，則T是一字母或數(shù)字，ST也是字母數(shù)字串，即有

S→T∣ST其中，產(chǎn)生式S→T∣ST是一種左遞歸形式，由它可以產(chǎn)生一串T。最后，作為“標識符”的非終結(jié)符I，它或者是一單個字母，或者為一字母后跟字母數(shù)字串，即

I→L∣LS因此，產(chǎn)生標識符的文法G[I]為：

G[I]=({a,b,…,z,0,…,9},{I,S,T,L,D},I,ξ) ξ:I→L∣LS S→T∣ST T→L∣D L→a∣b∣…∣z D→0∣1∣…∣9例3.2

寫一文法，使其語言是奇數(shù)集合，但不允許出現(xiàn)以0打頭的奇數(shù)。

[解答]根據(jù)題意，我們可以將奇數(shù)劃分為如圖3–1所示的三個部分，即最高位允許出現(xiàn)1～9，用非終結(jié)符B表示；中間部分可以出現(xiàn)任意多位數(shù)字0～9，每一位用非終結(jié)符D表示；最低位只允許出現(xiàn)1、3、5、7、9等奇數(shù)，用A表示。圖3–1奇數(shù)劃分示意由于中間部分可出現(xiàn)任意位，所以另引入了一個非終結(jié)符M，它包括最高位和中間位部分。假定開始符為N，則可得到文法G[N]為

G[N]=({0,1,…,9},{N,A,M,B,D},N,ξ) ξ:N→A∣MA/*一位數(shù)字│多位數(shù)字*/? M→B∣MD

/*僅兩位數(shù)字(無中間位)│多于兩位數(shù)字*/? A→1∣3∣5∣7∣9? B→1∣2∣3∣4∣5∣6∣7∣8∣9? D→0∣B注意：在每一步推導過程中，只能對其中的一個非終結(jié)符用其對應(yīng)的產(chǎn)生式右部的一個候選式來替換。

假定G[S]?是一個文法，S是它的開始符號，如果，則稱α是文法G[S]?的一個句型；如果，則稱α是文法G[S]?的一個句子。僅含終結(jié)符的句型是一個句子。因此，句型和句子的定義如下：（1）句型：由文法的開始符S出發(fā)，經(jīng)過0步或有限步推導出來的符號串。（2）句子：由文法的開始符S出發(fā)，經(jīng)過1步或有限步推導出來的符號串α且該符號串α全部由終結(jié)符組成。

由定義可知，開始符S本身只能是文法的一個句型而不可能是一個句子。此外，上面推導出的i+i*i是文法G[E]?的一個句子（當然也是一個句型），而E+E、E+E*E、E+E*i和E+i*i都是文法G[E]?的句型。對于文法G[S]，它所產(chǎn)生的句子的全體稱為由文法G[S]?產(chǎn)生的語言，記為L[G]，即有

在此需要注意：（1）S至少進行一次推導；（2）S所推導出的α必須全部由終結(jié)符組成。3.1.2形式語言分類語言學家NoamChomsky于1956年首先建立了形式語言的描述，定義了四類文法及相應(yīng)的形式語言，并分別與相應(yīng)的識別系統(tǒng)相聯(lián)系，它對程序語言的設(shè)計、編譯方法、計算復雜性等方面都產(chǎn)生了重大影響。

1．0型文法與0型語言(對應(yīng)圖靈機)如果文法G[S]的每一個產(chǎn)生式具有下列形式：

α→β其中，，即至少含有一個非終結(jié)符；β∈V*；則稱文法G[S]為0型文法或短語文法，記為PSG。0型文法相應(yīng)的語言稱為0型語言或稱遞歸可枚舉集，它的識別系統(tǒng)是圖靈(Turing)機。

2．1型文法與1型語言(對應(yīng)線性界限自動機，自然語言)文法G[S]的每一個產(chǎn)生式α→β，均在0型文法的基礎(chǔ)上增加了字符長度上滿足∣α∣≤∣β∣的限制，則稱文法G[S]為1型文法或上下文有關(guān)文法，記為CSG。1型文法相應(yīng)的語言稱為1型語言或上下文有關(guān)語言，它的識別系統(tǒng)是線性界限自動機。

1型文法的另一種定義方法是文法G[S]的每一個產(chǎn)生式具有下列形式：

αAδ→αβδ其中，。顯然，它滿足前述定義的長度限制，但它更明確地表達了上下文有關(guān)的特性，即A必須在α、δ的上下文環(huán)境中才能被β所替換。

3．2型文法與2型語言(對應(yīng)下推自動機，程序設(shè)計語言)文法G[S]的每一個產(chǎn)生式具有下列形式：A→α其中，A∈VN，，則稱文法G[S]為2型文法或上下文無關(guān)文法，記為CFG。2型文法相應(yīng)的語言稱為2型語言或上下文無關(guān)語言，它的識別系統(tǒng)是下推自動機。

4．3型文法與3型語言(對應(yīng)有限自動機)文法G[S]的每個產(chǎn)生式具有下列形式：A→a或A→aB其中，A、B∈VN，a∈VT*，則文法G[S]稱為3型文法、正規(guī)文法或右線性文法，記為RG。3型文法相應(yīng)的語言為3型語言或正規(guī)語言，它的識別系統(tǒng)是有限自動機。3型文法還可以呈左線性形式：A→a或A→Ba

5．四類文法的關(guān)系與區(qū)別由四類文法的定義可知，從0型文法到3型文法逐漸增加限制。1～3型文法都屬于0型文法，2、3型文法不一定屬于1型文法(如果存在形如A→ε的產(chǎn)生式，則不屬于1型文法)，3型文法屬于2型文法。四類文法的區(qū)別如下：

(1)1型文法中不允許有形如“A→ε”的產(chǎn)生式存在，而2、3型文法則允許形如“A→ε”的產(chǎn)生式存在；

(2)?0、1型文法的產(chǎn)生式左部存在含有終結(jié)符號的符號串或兩個以上的非終結(jié)符，而2型和3型文法的產(chǎn)生式左部只允許是單個的非終結(jié)符號。

例3.3

試判斷下列產(chǎn)生式集所對應(yīng)的文法和產(chǎn)生的語言：(1) ①S→ACaB(2)①S→aSBC(3)①S→Ac(4)①S→aS ②Ca→aaC ②S→aBC ②S→Sc ②S→aA ③CB→DB ③CB→DB ③A→ab ③A→bA ④CB→E ④DB→DC ④A→aAb ④A→bB ⑤aD→Da ⑤DC→BC⑤B→cB ⑥AD→AC ⑥aB→ab⑥B→c ⑦aE→Ea ⑦bB→bb ⑧AE→ε⑧bC→bc

⑨cC→cc

例3.4

給出字母表Σ={a,b}上的同時只有奇數(shù)個a和奇數(shù)個b的所有字符串集合的正規(guī)文法。

[解答]

為了構(gòu)造字母表Σ={a,b}上同時只有奇數(shù)個a和奇數(shù)個b的所有字符串的正規(guī)表達式，我們畫出如圖3–2所示的DFA，即由開始符S出發(fā)，經(jīng)過奇數(shù)個a到達狀態(tài)A，或經(jīng)過奇數(shù)個b到達狀態(tài)B。再由狀態(tài)A出發(fā)，經(jīng)過奇數(shù)個b到達狀態(tài)C(終態(tài))；同樣，由狀態(tài)B出發(fā)，經(jīng)過奇數(shù)個a到達終態(tài)C。圖3–2例3.4的DFA由圖3–2可直接得到正規(guī)文法G[S]如下：

G[S]:S→aA?∣bB A→aS?∣bC∣b B→bS?∣aC∣a C→bA?∣aB∣ε3.1.3正規(guī)表達式與上下文無關(guān)文法

1．正規(guī)表達式到上下文無關(guān)文法的轉(zhuǎn)換正規(guī)表達式所描述的語言結(jié)構(gòu)均可以用上下文無關(guān)文法描述，反之則不一定。由正規(guī)表達式構(gòu)造上下文無關(guān)文法的一種方法如下：

(1)構(gòu)造正規(guī)表達式的NFA；

(2)若0為初始狀態(tài)，則A0為開始符號；

(3)如果存在映射關(guān)系f(i,a)=j，則定義產(chǎn)生式Ai→aAj；

(4)如果存在映射關(guān)系f(i,ε)=j，則定義產(chǎn)生式Ai→Aj；

(5)若i為終態(tài)，則定義產(chǎn)生式Ai→ε。例3.5

用上下文無關(guān)文法描述正規(guī)表達式(a∣b)*abb。

[解答]首先構(gòu)造識別正規(guī)表達式(a∣b)*abb的NFAM如圖3–3所示。由構(gòu)造上下文無關(guān)文法的方法得到上下文無關(guān)文法G[A0]如下：

G[A0]:A0→aA0∣bA0∣aA1 A1→bA2 A2→bA3 A3→ε圖3–3例3.5的NFAM事實上，由正規(guī)表達式構(gòu)造上下文無關(guān)文法還可以采用另一種方法，即通過分析正規(guī)表達式的特性憑經(jīng)驗直接構(gòu)造。如可把(a∣b)*abb看作由(a∣b)*和abb兩部分組成，第一部分是由0個或若干個a和b組成的字符串，而第二部分則僅由abb字符串組成，由此得到上下文無關(guān)文法G[A]如下：

G[A]:?A→HT H→aH∣bH∣ε?? T→abb

2．正規(guī)表達式與上下文無關(guān)文法描述的對象上下文無關(guān)文法既可以描述程序語言的語法，又可以描述程序語言的詞法，但基于下述原因，應(yīng)采用正規(guī)表達式描述詞法：

(1)詞法規(guī)則簡單，采用正規(guī)表達式已足以描述；

(2)正規(guī)表達式的表示比上下文無關(guān)文法更加簡潔、直觀和易于理解；

(3)有限自動機的構(gòu)造比下推自動機簡單且分析效率高。貫穿詞法分析和語法分析始終如一的思想是：語言的描述和語言的識別是表示一個語言的兩個不同的側(cè)面，二者缺一不可。用正規(guī)表達式和上下文無關(guān)文法描述語言時的識別方法(即自動機)不同。通常，正規(guī)表達式適合于描述線性結(jié)構(gòu)，如標識符、關(guān)鍵字和注釋等；而上下文無關(guān)文法則適合于描述具有嵌套(層次)性質(zhì)的非線性結(jié)構(gòu)，如不同結(jié)構(gòu)的語句if-else、while等。3.2推導與語法樹在此后的討論中，我們用大寫字母A、B、S、E等表示非終結(jié)符，用小寫字母a、b、i、j等表示終結(jié)符，并用希臘字母等表示文法符號串，即α、β、δ、γ等均屬于(VT∪VN)*。3.2.1推導與短語

1．規(guī)范推導在3.1.1節(jié)中，所給句子i+i*i推導序列中的每一步推導都是對句型中的最右非終結(jié)符用相應(yīng)產(chǎn)生式的右部進行替換，這樣的推導稱為最右推導。如果每一步推導都是對句型中的最左非終結(jié)符用相應(yīng)產(chǎn)生式的右部進行替換，則稱為最左推導。例如句子i+i*i按文法(3.1)的最左推導是從一個句型到另一個句型的推導過程并不是惟一的，為了對句子的結(jié)構(gòu)進行確定性分析，我們往往只考慮最左推導或最右推導，并且稱最右推導為規(guī)范推導。規(guī)范推導的逆過程便是規(guī)范歸約。3.2.2語法樹與二義性

1．語法樹對程序語言來說，有兩個問題需要解決：其一是判別程序在語法上是否正確；其二是句子的識別或分析。在編譯方法中，為了便于識別或分析句子而引入了語法樹這一重要的輔助工具。語法樹以圖示化的形式把句子分解成各個組成部分來描述或分析句子的語法結(jié)構(gòu)，這種圖示化的表示與所定義的文法規(guī)則完全一致，但更為直觀和完整。對文法G[S]=(VT,VN,S,ξ)，滿足下列條件的樹稱為G[S]的語法樹：

(1)每個結(jié)點用G[S]的一個終結(jié)符或非終結(jié)符標記；

(2)根結(jié)點用文法開始符S標記；

(3)內(nèi)部結(jié)點(指非樹葉結(jié)點)一定是非終結(jié)符，如果某內(nèi)部結(jié)點A有n個分支，它的所有子結(jié)點從左至右依次標記為x1、x2、…、xn，則A→x1x2…xn一定是文法G[S]的一條產(chǎn)生式；

(4)如果某結(jié)點標記為ε，則它必為葉結(jié)點且是其父結(jié)點的惟一子結(jié)點。相應(yīng)于一個句型的語法樹是以文法的開始符S作為根結(jié)點的，并隨著推導逐步展開；當某個非終結(jié)符被它對應(yīng)的產(chǎn)生式右部的某個候選式所替換時，這個非終結(jié)符所對應(yīng)的結(jié)點就產(chǎn)生出下一代新結(jié)點，即候選式中從左至右的每一個符號都依次順序?qū)?yīng)一個新結(jié)點，且每個新結(jié)點與其父結(jié)點之間都有一條連線(樹枝)。在一棵語法樹生長過程中的任何時刻，所有那些沒有后代的樹葉結(jié)點自左至右排列起來就是一個句型。例如，與文法(3.1)的句子i+i*i相應(yīng)的語法樹如圖3–4所示。圖3-4句子i+i*i的語法樹在構(gòu)造語法樹時可以發(fā)現(xiàn)，一個句型的最左推導及最右推導只決定先生長左子樹還是先生長右子樹，句型推導結(jié)束時相應(yīng)的語法樹也隨之完成，這時已不能看出是先生長左子樹還是先生長右子樹，所呈現(xiàn)的僅僅是已經(jīng)長成的這個句子或句型的語法樹。這與使用文法規(guī)則進行推導是有差異的，即使用文法規(guī)則的推導過程是有先后之分的。因此，一棵語法樹表示了一個句型種種可能的(但未必是所有的——見下面文法的二義性)不同推導過程，包括最左(最右)推導。如果我們堅持使用最左(或最右)推導，那么一棵語法樹就完全等價于一個最左(或最右)推導，這種等價性也包括語法樹的每一步生長和推導的每一步展開的這種完全一致性。

2．子樹和短語語法樹的某個內(nèi)部結(jié)點（即非樹葉結(jié)點）連同它的所有后代組成了一棵子樹，子樹的根結(jié)點即為此內(nèi)部結(jié)點。只含有單層分枝的子樹稱為簡單子樹。子樹與短語的關(guān)系十分密切，根據(jù)子樹的概念，句型的短語、直接短語、句柄和素短語的直觀解釋如下：

(1)短語：子樹的末端結(jié)點(即樹葉)組成的符號串是相對于子樹根的短語；

(2)直接短語：簡單子樹的末端結(jié)點組成的符號串是相對于簡單子樹根的直接短語；

(3)句柄：最左簡單子樹的末端結(jié)點組成的符號串為句柄；

(4)素短語：子樹的末端結(jié)點組成的符號串含終結(jié)符，且在該子樹中不再有包含含有終結(jié)符的更小子樹。

短語和直接短語的進一步解釋是：（1）短語：由內(nèi)部結(jié)點向下生長的全部樹葉自左至右的排列。每個內(nèi)部結(jié)點都有一個短語，也可能有些內(nèi)部結(jié)點的短語是同一個。（2）直接短語：內(nèi)部結(jié)點直接一步生長出來的結(jié)點全部都由樹葉組成（即以該內(nèi)部結(jié)點為根的子樹是簡單子樹），該全部樹葉自左至右的排列即為直接短語。因此，直接短語是在短語基礎(chǔ)上增加了只能向下生長一步且向下生長一步所產(chǎn)生的結(jié)點全部都由樹葉組成這一限制；而句柄則是在直接短語的基礎(chǔ)上增加了“最左”這一條件限制。對素短語來說，首先要求素短語本身必須是一個短語，并在短語基礎(chǔ)上又增加了兩條限制（求素短語的另一種方法見本章3.4.2節(jié)）：①?構(gòu)成短語的全部樹葉中至少含有一個終結(jié)符；②?該短語的全部樹葉中不得含有其它素短語。顯然，從語法樹出發(fā)尋找短語、直接短語、句柄和素短語要直觀得多。此外，要注意的是子樹末端結(jié)點組成的符號串是指由該子樹根開始向下生長的所有末端結(jié)點（即樹葉）自左至右的排列，該子樹的部分末端結(jié)點并不是該子樹的短語。對圖3-5所示的關(guān)于句型E+E*i的語法樹來說，它有3個內(nèi)部結(jié)點（對應(yīng)3棵子樹），即有3個短語，分別為i、E*i和E+E*i；直接短語、句柄和素短語均為i；而E+E由于在句型E+E*i的限制下只是樹根E的部分末端結(jié)點，因而不是短語。但是，在圖3-6中給出的E+E+E*i的句型下，E+E卻是子結(jié)點E的一個直接短語。圖3–5E+E*i的語法樹

例如，對本節(jié)下面將要介紹的無二義性算術(shù)表達式文法：

G[E]：E→E+T∣TT→T*F∣F? F→?(E)∣i句型?(T+T)*i對應(yīng)的語法樹如圖3-7所示。對圖3-7所示關(guān)于句型?(T+T)*i的語法樹，它有7個內(nèi)部結(jié)點（對應(yīng)7棵子樹），相應(yīng)就有7個短語；但根結(jié)點（內(nèi)部結(jié)點）E和第二層內(nèi)部結(jié)點T向下生長出來的是同一樹葉序列，故兩者短語相同，都是?(T+T)*i。第三層的內(nèi)部結(jié)點T和第四層的內(nèi)部結(jié)點F向下生長的也是同一樹葉序列，即兩者短語也相同，均為?(T+T)。其余內(nèi)部結(jié)點對應(yīng)的短語各不相同，因此該句型（語法樹）共有5個短語：T、T+T、(T+T)、i、(T+T)*i。圖3–7(T+T)*i對應(yīng)的語法樹

圖3-7對應(yīng)的直接短語有兩個：一個是最下面的內(nèi)部結(jié)點E直接一步生長成的樹葉T，另一個是第三層的內(nèi)部結(jié)點F直接一步生長成的樹葉i。由于T在i的左邊，故T為句柄。素短語首先必須是一個短語，其次要至少含有一個終結(jié)符并且該素短語中不再含有其它更小的素短語。因此，直接短語T因其是非終結(jié)符（即該短語不含終結(jié)符）而不是素短語；直接短語i因其本身是終結(jié)符且不含其它更小的素短語，故為素短語；短語T+T滿足至少含有一個終結(jié)符的條件且T+T中不含其它更小的素短語，故為素短語；短語?(T+T)?雖然滿足至少含有一個終結(jié)符的條件，但因其含有更小的素短語T+T而不是素短語；短語?(T+T)*i也因同樣的原因不是素短語。

3．文法的二義性文法G[S]的一個句子如果能找到兩種不同的最左推導(或最右推導)，或者存在兩棵不同的語法樹，則稱這個句子是二義性的。一個文法如果包含二義性的句子，則這個文法是二義文法，否則是無二義文法。例如，對文法(3.1)，句子i+i*i存在著兩種最左推導或最右推導，所形成的兩棵不同的語法樹如圖3–8所示。圖3–6E+E+E*i的語法樹

圖3–8句子i+i*i的兩棵不同的語法樹再如，條件語句的文法G[S]為

G[S]:S→ifBS S→ifBSelseS S→A/*A指其它語句*/其中，VN={B,S,A}，VT={if,else}，則句型ifBifBSelseS所對應(yīng)的兩棵不同語法樹見圖3–9。因此，文法G[S]是二義性文法。圖3–9句型ifBifBSelseS的兩棵不同語法樹顯然，二義性文法將給編譯程序的執(zhí)行帶來麻煩。對于二義性文法的句子，當編譯程序?qū)λ慕Y(jié)構(gòu)進行語法分析時，就會產(chǎn)生兩種甚至多種不同的解釋；由于語法結(jié)構(gòu)的這種不確定性，因而必將導致語義處理上的不確定性。

4．文法二義性的消除一個文法是二義性的，并不說明該文法所描述的語言也是二義性的。也即，對于一個二義性文法G[S]，如果能找到一個非二義性文法G'[S]，使得L(G')=L(G)，則該二義性文法的二義性是可以消除的。如果找不到這樣的G'[S]，則二義性文法描述的語言為先天二義性的。文法二義性消除的方法如下：

(1)不改變文法中原有的語法規(guī)則，僅加進一些語法的非形式規(guī)定。如對文法(3.1)，不改變已有的四條規(guī)則(即四個產(chǎn)生式)，僅加進運算符的優(yōu)先順序和結(jié)合規(guī)則，即*優(yōu)先于+，且*、+都服從左結(jié)合。這樣，對文法(3.1)中的句子i+i*i就只有如圖3–7(a)所示的惟一一棵語法樹。

(2)構(gòu)造一個等價的無二義性文法，即把排除二義性的規(guī)則合并到原有文法中，改寫原有的文法。方法（2）是通過添加新的非終結(jié)符來消除文法中的二義性，以達到將原文法改造成一個等價的無二義性文法的目的。

那么，如何才能將文法（3.1）改寫為無二義性的文法呢？在構(gòu)造算術(shù)表達式文法時可以按運算符的優(yōu)先級將產(chǎn)生式分為三個層次：“+”、“-”類為一層，“*”、“/”類為一層，而括號“(?)”和運算對象“i”為另一層；這三層的優(yōu)先級依次遞增。由此，我們在文法（3.1）原有的非終結(jié)符E基礎(chǔ)上再兩個非終結(jié)符T和F，即以E、T、F來分別代表三個層次的劃分。并且，我們可以由后面將要介紹的歸約看出：離根結(jié)點越遠的短語先被歸約，離根結(jié)點越近的短語后被歸約。體現(xiàn)在文法上就是離開始符（對應(yīng)根結(jié)點）越遠的產(chǎn)生式其優(yōu)先級越高，離開始符越近的產(chǎn)生式其優(yōu)先級越低，開始符所在的產(chǎn)生式其優(yōu)先級最低。

據(jù)此，我們可以將文法(3.1)改寫為無二義性的文法G‘[E]如下：

G'[E]:E→E+T∣TT→T*F∣F? F→(E)∣i此時，句子i+i*i就只有如圖3–10所示的惟一一棵語法樹。圖3–10句子i+i*i的語法樹例3.6

試將如下的二義性文法G[S]的二義性消除:G[S]:S→ifbS∣ifbSelseS∣A

[解答]消除G[S]的二義性可采用如下兩種方法：

(1)不改變已有規(guī)則，僅加進一項非形式的語法規(guī)定：else與離它最近的if匹配(即最近匹配原則)，這樣，文法G[S]的句子ifbifbAelseA只對應(yīng)惟一的一棵語法樹(見圖3–11)。

圖3–11復合if語句的語法樹

(2)改寫文法G[S]為G'[S]:S→S1∣S2 S1→ifbS1elseS1∣A? S2→ifbS∣ifbS1elseS2這是因為引起二義性的原因是if-else語句的if后可以是任意if型語句，所以改寫文法時規(guī)定if和else之間只能是if-else語句或其它語句。這樣，改寫后文法G'[S]的句子ifbifbAelseA只對應(yīng)惟一的一棵語法樹(如圖3–12所示)。圖3–12G'[S]的復合if語句的語法樹

我們總希望一個文法是無二義性的，這樣，句子的分析可以按惟一確定的方式進行。但是，文法的二義性是不可判定的，即不存在一種算法，能夠在有限步內(nèi)判定一個文法是否為二義性的。有時候，二義性文法也可帶來一定的好處，如語法分析中二義性文法的應(yīng)用。3.3自頂向下的語法分析自定向下分析就是從文法的開始符出發(fā)并尋找出這樣一個推導序列：推導出的句子恰為輸入符號串；或者說，能否從根結(jié)點出發(fā)向下生長出一棵語法樹，其葉結(jié)點組成的句子恰為輸入符號串。顯然，語法樹的每一步生長(每一步推導)都以能否與輸入符號串匹配為準，如果最終句子得到識別，則證明輸入符號串為該文法的一個句子；否則，輸入符號串不是該文法的句子。3.3.1遞歸下降分析法遞歸下降分析法是一種自上而下的分析方法，文法的每個非終結(jié)符對應(yīng)一個遞歸過程。分析過程就是從文法開始符出發(fā)執(zhí)行一組遞歸過程，這樣向下推導直到推出句子；或者說從根結(jié)點出發(fā)，自上而下為輸入串尋找一個最左匹配序列，建立一棵語法樹。

1．自頂向下分析存在的不確定性假定文法G[S]為S→xAy

A→ab∣a若輸入串為xay，則其分析過程如下：

(1)首先建立根結(jié)點S。

(2)文法關(guān)于S的產(chǎn)生式只有一個，也即由S生長的語法樹如圖3–13(a)所示，它的第一個終結(jié)符x與輸入串待分析的字符x匹配。此時，下一個待分析的字符為a，期待著與語法樹中在x右側(cè)且與x相鄰的葉結(jié)點A匹配。圖3–13試探分析對應(yīng)的語法樹

(3)非終結(jié)符A有兩個候選式，先選用第一個候選式生長的語法樹(如圖3–13(b)所示)；這時語法樹的第二個葉結(jié)點a恰與待分析的字符a匹配。

(4)輸入串中下一個待分析的字符為y，它期待與第三個葉結(jié)點b匹配，但匹配時發(fā)現(xiàn)這兩個字符是不同的，即匹配失敗，這是因為生成A的子樹時所選用的是其第一個候選式，即（3）中對字符a的匹配是虛假匹配。

(5)因不匹配而將A所生成的這棵子樹注銷，即把匹配指針回退到輸入串的第二個字符a，也就是恢復與A匹配時的現(xiàn)場，即(3)之前。

(6)此時A選用第二個候選式并生長語法樹如圖3–13(c)所示，這時第二個葉結(jié)點a與輸入串的第二個葉結(jié)點a匹配。

(7)此時輸入串的下一個待分析字符指向y，而語法樹的下一個未匹配的葉結(jié)點也為y，兩者恰好匹配。因此，圖3–13(c)所示的語法樹即為輸入串xay的語法樹。顯然，這種自上而下的分析是一個不斷試探的過程；也即，在分析過程中，如果出現(xiàn)多個產(chǎn)生式(即候選式)可供選擇，則逐一試探每一候選式進行匹配，每當一次試探失敗，就選取下一候選式再進行試探；此時，必須回溯到這一次試探的初始現(xiàn)場，包括注銷已生長的子樹及將匹配指針調(diào)回到失敗前的狀態(tài)。這種帶回溯的自上而下分析方法實際上是一種窮舉的試探方法，其分析效率極低，在實用的編譯程序中很少使用。

2．確定的自頂向下分析為了實現(xiàn)確定的(即無回溯的)自上而下分析，則要求文法滿足下述兩個條件：

(1)文法不含左遞歸，即不存在這樣的非終結(jié)符號A：有A→A…存在或者有AAα；

(2)無回溯，對文法的任一非終結(jié)符號，當其產(chǎn)生式右部有多個候選式可供選擇時，各候選式所推出的終結(jié)符號串的首字符集合要兩兩不相交。左遞歸是程序語言的語法規(guī)則中并不少見的形式，例如前述消除了二義性的算術(shù)表達式文法的一個規(guī)則：

E→E+T//簡單表達式→簡單表達式+項如果對該左遞歸文法采用自上而下分析法，即首先以“E+T”中的E為目標對“E+T”進行試探，進而又以其中的E為目標再對選擇“E+T”進行試探；也即E+T

E+T+T

E+T+T+T

…，這種左遞歸的文法使自上而下分析工作陷入無限循環(huán)。也就是說，當試圖用E去匹配輸入符號串時會發(fā)現(xiàn)：在沒有吃進任何輸入符號的情況下，又得重新要求E去進行新的匹配。因此，使用自上而下分析法首先要消除文法的左遞歸性。對于回溯，由上述不確定的自上而下分析示例可知，由于回溯的存在，可能在已經(jīng)做了大量的語法分析工作之后，才發(fā)現(xiàn)走了一大段錯路而必須回頭，要把已經(jīng)做的一大堆語義工作(指中間代碼產(chǎn)生工作和各種表格的簿記工作)推倒重來。回溯使得自上而下語法分析只具有理論意義而無實際使用的價值。因此，要使自上而下語法分析具有實用性，就必須要消除回溯。例如，含有直接左遞歸的表達式文法G[E]為

G[E]:?E→E+T∣T?? T→T*F∣F?? F→(E)∣i經(jīng)過消去直接左遞歸后得到文法G'[E]為

G'[E]:E→TE'??? E'→+TE'∣ε??? T→FT'??? T'→*FT'∣ε??? F→(E)∣i

(3.2)

(3)化簡由(2)所得的文法，即去掉那些從開始符號S出發(fā)，在推導中無法出現(xiàn)的非終結(jié)符的產(chǎn)生式(去掉多余產(chǎn)生式)。注意消除左遞歸之前的文法不允許有ε產(chǎn)生式，否則無法得到等效的無左遞歸文法。因此，如果原文法中有ε的產(chǎn)生式，則需將文法改寫為無ε的產(chǎn)生式的文法。此外，此算法并未對非終結(jié)符的排列順序加以規(guī)定，不同的排列可能得到不同的結(jié)果，但彼此是等價的。例如，將文法(3.3)的非終結(jié)符排序為R、Q、S。對R來說，它不存在直接左遞歸；把R代入到Q的有關(guān)候選式后得到改變的Q產(chǎn)生式為

Q→Sab∣ab∣b現(xiàn)在的Q同樣不含直接左遞歸，再把它代入到S的有關(guān)候選式后得到改變的S產(chǎn)生式為

S→Sabc∣abc∣bc∣c經(jīng)過消除了S的直接左遞歸后，即得到了整個文法G'[S]為

G'[S]:S→abcS'∣bcS'∣cS' S'→abcS'∣ε Q→Sab∣ab∣b R→Sa∣a顯然，關(guān)于Q和R的產(chǎn)生式已為多余，因此化簡后的最終文法G''[S]為

G''[S]:S→abcS'∣bcS'∣cS'? S'→abcS'∣ε(3.4)實際上，我們也可以用數(shù)學中的分配律來消除文法中的左遞歸。對文法(3.3)，首先將R的產(chǎn)生式代入到Q的產(chǎn)生式中并按分配律展開(注：“(”和“)”為元語言符號)得

Q→(Sa∣a)b∣b 展開后：Q→Sab∣ab∣b再將改變后Q的產(chǎn)生式代入到S的產(chǎn)生式中并按分配律展開得 S→(Sab∣ab∣b)c∣c展開后：S→Sabc∣abc∣bc∣c在消除S的直接左遞歸后同樣得到文法(3.4)。

4．消除回溯回溯發(fā)生的原因在于候選式存在公共的左因子，如產(chǎn)生式A如下：A→αβ1∣αβ2此時，如果輸入串待分析的字符串前綴為α，則選用哪個候選式以尋求與輸入串匹配就難以確定。倘若候選式不含公共左因子，則推導出的首字符能與輸入串匹配的那個候選式便是惟一的匹配。在文法G[S]中的每個非終結(jié)符相應(yīng)的產(chǎn)生式右部其候選式均不含公共左因子的情況下，語法分析的匹配過程都是惟一匹配，無需試探；這時若匹配失敗，則意味著輸入串不是句子。我們也可以用數(shù)學中提取公共因子的辦法來提取公共左因子。如對式(3.5)提取公共(左)因子后得

A→δ(β1∣β2∣…∣βi)∣βi+1∣…∣βj

(注：“(”與“)”為元語言符號)將產(chǎn)生式中由“(”和“)”括起的部分以非終結(jié)符A'命名則得到式(3.6)。例如，對文法G[A]:A→aAB∣a∣b提取公共左因子后的文法G'[A]為

G‘[A]:A→aA'∣b? A'→AB∣ε

5．遞歸下降分析器在不含左遞歸和每個非終結(jié)符的所有候選終結(jié)首符集都兩兩不相交的條件下，我們就可能構(gòu)造一個不帶回溯的自上而下的分析程序，這個分析程序是由一組遞歸過程(或函數(shù))組成的，每個過程(或函數(shù))對應(yīng)文法的一個非終結(jié)符。這樣的一個分析程序稱為遞歸下降分析器。例如，文法(3.2)對應(yīng)的遞歸下降分析器如下：

voidmatch(tokent){if(lookahead==t)lookahead=nexttoken;elseerror(?);}voidE(?){T(?);E'(?);}

voidE'(?){if(lookahead=='+'){match('+');T(?);E'(?);}}voidT(?){F(?);T'(?);}voidT'(?){if(lookahead=='*'){match('*');F(?);T'(?);}}voidF(?){if(lookahead=='i')match('i');elseif(lookahead=='('){match('(');E(?);if(lookahead==')')match(')');elseerror(?);}elseerror(?);}我們知道，關(guān)于E'的產(chǎn)生式是E'→+TE'∣ε即E'只有兩個候選式：第一個候選式的開頭終結(jié)符為+，第二個候選式為ε。這就是說，當E'面臨輸入符號“+”時就令第一個候選式進入工作，而當面臨任何其它符號時，E'就自動認為獲得了匹配。遞歸函數(shù)E'就是根據(jù)這一原則設(shè)計的。例如，我們將遞歸函數(shù)的調(diào)用以棧的形式模擬來分析輸入串#i1*(i2+i3)#的語法分析過程；在此，“#”為輸入串i1*(i2+i3)的分隔符。進行語法分析時，首先將“#”和文法開始符E壓入棧中，當語法分析進行到棧中僅?！?”而輸入串掃描指針已指向輸入串尾部的“#”時，則語法分析成功，分析過程如圖3–14所示。圖3–14輸入串i1*(i2+i3)的語法分析注意：圖3–14中第(5)步執(zhí)行函數(shù)F(?)時，因當前掃描的字符為“(”，故匹配后應(yīng)執(zhí)行E(?)(用棧模擬即為將E壓棧)；并且，在執(zhí)行完E(?)后還應(yīng)執(zhí)行其后的判斷“)”與匹配“)”語句，這在棧的模擬中則是標出此時E壓棧之前的位置(見圖3–12的第(7)～(14)步)，即彈棧至此時(第(14)步結(jié)束時)應(yīng)執(zhí)行這個判斷“)”與匹配“)”語句。我們還可以用另一種表示法得到遞歸下降分析器，即將文法的每一個非終結(jié)符用VT∪VN上的一個正規(guī)表達式來定義，然后將其用狀態(tài)轉(zhuǎn)換圖表示，并借助于這種轉(zhuǎn)換圖來得到遞歸下降分析器。這種方法的特點是可以不消除文法的左遞歸。文法(3.2)的每個非終結(jié)符可由下面的正規(guī)表達式定義：

E→T{+T} T→F{*F} F→i│‘(’E‘)’

(3.7)在此，“{α}”表示閉包運算α*，且文法(3.2)與文法(3.7)是等價的，文法(3.7)不含左遞歸。根據(jù)文法(3.7)可得到圖3–15所示的一組描述非終結(jié)符E、T和F的狀態(tài)轉(zhuǎn)換圖。圖3–15非終結(jié)符對應(yīng)的狀態(tài)轉(zhuǎn)換圖圖3–15中三個狀態(tài)轉(zhuǎn)換圖的工作是以一種相互遞歸的方式進行的；因此，每個狀態(tài)轉(zhuǎn)換圖的作用就如同一個遞歸過程(函數(shù))。這時，前面的遞歸下降分析器程序可刪除函數(shù)E'(?)和T'(?)，而將E(?)和T(?)改為voidE(?){T(?);while(lookahead=='+'){match('+');T(?);}}voidT(?){F(?);while(lookahead=='*'){match('*');F(?);}}3.3.2LL(1)分析法

LL(1)分析法又稱預測分析法，是一種不帶回溯的非遞歸自上而下分析法。LL(1)的含義是：第一個L表明自上而下分析是從左至右掃描輸入串的；第二個L表明分析過程中將用最左推導；“1”表明只需向右查看一個符號就可決定如何推導(即可知用哪個產(chǎn)生式進行推導)。類似地，也可以有LL(k)文法，也就是向前查看k個符號才能確定選用哪個產(chǎn)生式，不過LL(k)(k>1)在實際中極少使用。

1．表驅(qū)動的LL(1)分析器

LL(1)分析法的基本思想是根據(jù)輸入串的當前輸入符號來惟一確定選用某條規(guī)則(產(chǎn)生式)來進行推導；當這個輸入符號與推導的第一個符號相同時，再取輸入串的下一個符號，繼續(xù)確定下一個推導應(yīng)選的規(guī)則；如此下去，直到推導出被分析的輸入串為止。一個LL(1)分析器由一張LL(1)分析表(也稱預測分析表)、一個先進后出分析棧和一個控制程序(表驅(qū)動程序)組成，如圖3–16所示。圖3–16LL(1)分析器對圖3–16所示的LL(1)分析器說明如下：

(1)輸入串是待分析的符號串，它以界符‘#’作為結(jié)束標志。(注：#∈VT但不是文法符號，是由分析程序自動添加的。)

(2)分析棧中存放分析過程中的文法符號。分析開始時棧底先放入一個‘#’，然后再壓入文法的開始符號；當分析棧中僅剩‘#’，輸入串指針也指向串尾的‘#’時，分析成功。

(3)分析表用一個矩陣(或二維數(shù)組)M表示，它概括了相應(yīng)文法的全部信息。矩陣的每一行與文法的一個非終結(jié)符相關(guān)聯(lián)，而每一列與文法的一個終結(jié)符或界符‘#’相關(guān)聯(lián)。對M[A,a]來說，A為非終結(jié)符，而a為終結(jié)符或‘#’。分析表元素M[A,a]中的內(nèi)容為一條關(guān)于A的產(chǎn)生式，表明當A面臨輸入符號a時當前推導所應(yīng)采用的候選式；當元素內(nèi)容為空白(空白表示“出錯標志”)時，則表明A不應(yīng)該面臨這個輸入符號a，即輸入串含有語法錯誤。

(4)控制程序根據(jù)分析棧頂符號x和當前輸入符號a來決定分析器的動作：①若x＝a＝‘#’，則分析成功，分析器停止工作。②若x＝a≠‘#’，即棧頂符號x與當前掃描的輸入符號a匹配；則將x從棧頂彈出，輸入指針指向下一個輸入符號，繼續(xù)對下一個字符進行分析。③若x為一非終結(jié)符A，則查M[A,a]：

i．若M[A,a]中為一個A的產(chǎn)生式，則將A自棧頂彈出，并將M[A,a]中的產(chǎn)生式右部符號串按逆序逐一壓入棧中；如果M[A,a]中的產(chǎn)生式為A→ε，則只將A自棧頂彈出。

ii．若M[A,a]中為空，則發(fā)現(xiàn)語法錯誤，調(diào)用出錯處理程序進行處理。控制程序描述如下：將‘#’和文法開始符依次壓入棧中；把第一個輸入符號讀入a；do{把棧頂符號彈出并放入x中；if(x∈VT){if(x＝＝a){if?(a!＝‘#’)?將下一輸入符號讀入a;}elseerror(?);}elseif(M[x,a]＝“x→y1y2…yk”){按逆序依次把yk、yk?1、…、y1壓入棧中;輸出“x→y1y2…yk”;}elseerror(?);}while(x!=‘#’)例3.7例3.7算術(shù)表達式文法（3.2）的LL(1)?分析表如表3.1所示，試給出輸入串i1+i2*i3的分析過程。

[解答]輸入串i1+i2*i3按控制程序進行的分析過程如表3.2所示。

(1)FIRST集構(gòu)造方法：對文法中的每一個非終結(jié)符X構(gòu)造FIRST(X)，其方法是連續(xù)使用下述規(guī)則，直到每個集合的FIRST不再增大為止。(注：對終結(jié)符a而言，F(xiàn)IRST(‘a(chǎn)’)={a}，因而無需構(gòu)造。)①若有產(chǎn)生式X→a…，且a∈VT，則把a加入到FIRST(X)中；若存在X→ε，則將ε也加入到FIRST(X)中。②若有X→Y…，且Y∈VN，則將FIRST(Y)中的所有非ε元素(記為“\{ε}”)都加入到FIRST(X)中；若有X→Y1Y2…Yk，且Y1～Yi都是非終結(jié)符，而Y1～Yi－1的候選式都有ε存在，則把FIRST(Yj)(j=1,2,…,i)的所有非ε元素都加入到FIRST(X)中；特別是當Y1～Yk均含有ε產(chǎn)生式時，應(yīng)把ε也加到FIRST(X)中。

(3)構(gòu)造分析表M。①對文法G[S]的每個產(chǎn)生式A→α執(zhí)行以下②、③步。②對每個終結(jié)符a∈FIRST(A)，把A→α加入到M[A,a]中，其中α為含有首字符a的候選式或為惟一的候選式。③若ε∈FIRST(A),?則對任何屬于FOLLOW(A)的終結(jié)符b，將A→ε加入到M[A,b]中。④把所有無定義的M[A,a]標記為“出錯”。

條件（1）意味著A的每個候選式都不存在相同的首字符，由LL(1)?分析表的構(gòu)造方法可知：它避免了在分析表的同一欄目內(nèi)出現(xiàn)多個產(chǎn)生式的情況，即避免了多重入口。條件（2）是避免了在分析表的同一欄目內(nèi)出現(xiàn)A→α和A→ε（這同樣是多重入口）。例如對文法：

G[S]：S→Aa∣bA→a∣ε

則有FIRST(A)?={a,ε}、FOLLOW(A)?={a}，此時文法對應(yīng)的中M[A,?a]?欄里必然有兩個產(chǎn)生式A→α和A→ε存在，即形成了多重入口；而此時由條件(2)也可以得知：

FIRST(‘a(chǎn)’)∩FOLLOW(A)?={a}≠Φ。注意：LL(1)文法首先是無二義的，這一點可以從分析表不含多重定義入口得知；并且，含有左遞歸的文法絕不是LL(1)文法，所以必須首先消除文法的一切左遞歸。其次，應(yīng)該消除回溯(即提取公共左因子)。但是，文法中不含左因子只是LL(1)文法的必要條件，一個文法提取了公共左因子后，只解決了非終結(jié)符對應(yīng)的所有候選式不存在相同首字符的問題(即每個候選式的FIRST集互不相交)，只有當改寫后的文法不含ε產(chǎn)生式且無左遞歸時才可立即斷定該文法是LL(1)文法，否則必須用上面LL(1)文法的充要條件進行判定（或者看LL(1)?分析表中是否存在多重入口來判定）。例3.8

試構(gòu)造表達式文法G[E]的LL(1)分析表，其中：

G[E]:E→TE' E'→+TE'∣ε T→FT' T'→*FT'∣ε F→(E)∣i最后得到文法G[E]?的LL(1)?分析表如表3.1所示。

例3.9

程序語言中if-else語句的文法G[S]為

G[S]:S→iESeS∣iES∣a E→b其中，e遵從最近匹配原則。試改造文法G[S]并為之構(gòu)造LL(1)分析表。

[解答]提取公共左因子后得到文法G'[S]：

G'[S]:S→iESS'∣a??? S'→eS∣ε??? E→b求出每個非終結(jié)符的FIRST集和FOLLOW集。構(gòu)造分析表見表3.3。表3.3例3.9的分析表我們看到，分析表M含有多重入口沖突項M[S',?e]，因此文法G[S]?不是LL(1)?文法（實際上G[S]?是一個二義文法，二義文法構(gòu)造的LL(1)?分析表必定含有沖突項）。我們可以通過圖3-17來解決M[S',?e]?欄的沖突。對圖3-17，iES面臨輸入符號e時絕不能用ε匹配；如果用ε匹配，則認為iES是一個句型而丟掉了其后的eS（這樣做將認為eS是一個新的句型，而eS本身卻無法構(gòu)成一個句型），即最終不可能得到句型iESeS。因此，應(yīng)繼續(xù)掃描eS以便形成最終的句型iESeS；這也意味著，在分析表的M[S',e]欄內(nèi)應(yīng)舍棄S'→ε而保留S'→eS。由此得到無二義的LL(1)?分析表見表3.4。圖3-17iES面臨輸入符號e時可能出現(xiàn)的情況例3.10

證明下述文法G[S]不是LL(1)?文法，并給出其等價的LL(1)?文法。

G[S]：S→LAL→i?:∣εA→i=e[解答]FIRST集構(gòu)造：（1）FIRST(S)?=FIRST(L)?={i,?ε};FIRST(A)?={i};

（2）由S→L…得FIRST(L)\{ε}FIRST(S)，即FIRST(S)?={i};

又由S→LA和L→ε推出S→A，則FIRST(A)\{ε}FIRST(S)，即FIRST(S)?={i}FOLLOW集構(gòu)造：（1）FOLLOW(S)?={#};

（2）由S→LA得：FIRST(A)\{ε}FOLLOW(L)，即FOLLOW(L)?={i};

（3）由S→LA得：FOLLOW(S)FOLLOW(A)，即FOLLOW(A)?={#};對產(chǎn)生式L→i:∣ε，由于有FIRST(i:)∩FOLLOW(L)?={i}∩{i}≠Φ，所以文法G[S]?不是LL(1)?文法。為了滿足LL(1)文法的條件，需對文法G[S]?進行如下改造：（1）消去非終結(jié)符L和A，得到：

G'[S]：S→i?:?i=e∣i=e由此我們也可以看出G'[S]?存在著回溯（即含有最左公因子），故不是LL(1)?文法。（2）提取公共左因子i得到：

G''[S]：S→iAA→:i=e∣=e這時有：FIRST(S)?={i}；FIRST(A)?={:?,?=}；

FOLLOW(S)?={#}；由S→iA得：FOLLOW(S)FOLLOW(A)，即FOLLOW(A)?={#};而此時有：FIRST(iA)∩FOLLOW(S)?={i}∩{#}=Φ。故文法G''[S]?是與G[S]?等價的LL(1)?文法。3.4自底向上分析方法

自底向上的語法分析與自頂向下的語法分析相比，它無需消除左遞歸和回溯；對某些二義文法，也可以采用自底向上分析方法。因此，自底向上分析的適用范圍更大。

3.4.1自底向上分析原理所謂自下而上分析就是自左至右掃描輸入串，自下而上進行分析；通過反復查找當前句型的句柄(最左直接短語)，并使用產(chǎn)生式規(guī)則將找到的句柄歸約為相應(yīng)的非終結(jié)符。這樣逐步進行“歸約”，直到歸到文法的開始符號；或者說，從語法樹的末端開始，步步向上“歸約”，直到根結(jié)點。自下而上分析法是一種“移進—歸約”法，這是因為在自下而上分析過程中采用了一個先進后出的分析棧。分析開始后，把輸入符號自左至右逐個移進分析棧，并且邊移入邊分析，一旦棧頂?shù)姆柎纬赡硞€句型的句柄就進行一次歸約，即用相應(yīng)產(chǎn)生式的左部非終結(jié)符替換當前句柄。接下來繼續(xù)查看棧頂是否形成新的句柄，若為句柄則再進行歸約；若棧頂不是句柄則繼續(xù)向棧中移進后續(xù)輸入符號。不斷重復這一過程，直到將整個輸入串處理完畢。若此時分析棧只剩有文法的開始符號則分析成功，即確認輸入串是文法的一個句子；否則，即認為分析失敗。我們舉一個簡單的例子來說明這種分析過程。假設(shè)一文法G[S]為

G[S]:S→aAbB A→c∣Ac B→d試對輸入串a(chǎn)ccbd進行分析，檢查該符號串是否是G[S]的一個句子。我們?nèi)詫ⅰ?”作為輸入串的界符(括號)，并將輸入串前的“#”放入分析棧，接著將輸入串的符號依次進棧，具體分析過程如表3.6所示。上述語法分析過程可以用一棵分析樹來表示。在自下而上分析過程中，每一步歸約都可以畫出一棵子樹來，隨著歸約的完成，這些子樹被連成一棵完整的分析樹。根據(jù)表3.6構(gòu)造分析樹的過程如圖3–18所示。圖3–18自下而上構(gòu)造分析樹的過程

從建立分析樹的過程可以清楚地看出，自下而上分析過程的每一步歸約確實都是歸約當前句型的句柄；也就是說句柄一旦形成，則它總是出現(xiàn)在分析棧的棧頂而不會出現(xiàn)在棧的中間。由于每一步歸約都是把棧頂?shù)囊淮栍媚硞€產(chǎn)生式的左部符號替換，因而可以把棧頂?shù)倪@樣一串符號稱為“可歸約串”。初看起來，“移進—歸約”似乎很簡單，其實不然。在上例分析進行到第6步時，如果我們不是選擇規(guī)則A→Ac而是選擇規(guī)則A→c進行歸約，也即把c看作句柄的話，則最終就無法達到歸約到S的目的，從而也就無法得知輸入串a(chǎn)ccbd是一個符合文法的句子。為什么知道此時棧頂?shù)腁c形成“可歸約串”而c不是“可歸約串”呢？這就需要精確定義“可歸約串”這個直觀概念，這也是自下而上分析的關(guān)鍵問題。

進一步指出：如果文法G[S]是無二義的，那么規(guī)范推導(最右推導)的逆過程必是規(guī)范歸約(最左歸約)。請注意句柄的“最左”特征，這一點對于“移進—歸約”來說很重要，因為句柄的“最左”性和分析棧的棧頂兩者是相關(guān)的。對于規(guī)范句型(規(guī)范推導所得的句型)來說，句柄的后面不會出現(xiàn)非終結(jié)符(也即句柄的后面只能出現(xiàn)終結(jié)符)?；谶@一點，我們可用句柄來刻畫“移進－歸約”過程的“可歸約串”。因此，規(guī)范歸約的實質(zhì)是，在移進過程中，當發(fā)現(xiàn)棧頂呈現(xiàn)句柄時就用相應(yīng)產(chǎn)生式的左部符號進行替換(即歸約)。注意：如果一個樹葉序列由左至右的排列可以向上歸結(jié)到某一個結(jié)點(比如說A)，并且由結(jié)點A向下生長出的全部樹葉也恰是這個樹葉序列，則這個樹葉序列就是結(jié)點A的短語。如果這種向上歸結(jié)只需要一層(即樹葉與結(jié)點A都為父子關(guān)系)，則該樹葉序列為直接短語。需要說明的是，如果一個樹葉序列最終無法全部歸結(jié)到一個結(jié)點上，或者歸結(jié)到某結(jié)點上的樹葉序列并不完整，則該樹葉序列不是短語。例如，對圖3–18(d)所示的語法樹，我們采用修剪語法樹的方法來實現(xiàn)歸約，也即每次尋找當前語法樹的句柄(在語法樹中用虛線勾出)，然后將句柄中的樹葉剪去(即實現(xiàn)一次歸約)；這樣不斷地修剪下去，當剪到只剩下根結(jié)點時，就完成了整個歸約過程，如圖3–19所示。圖3–19修剪語法樹實現(xiàn)歸約

至此，我們簡單地討論了“句柄”和“規(guī)范歸約”這兩個基本概念，但并沒有解決規(guī)范歸約的問題，因為我們并沒有給出尋找句柄的算法。事實上，規(guī)范歸約的中心問題就是如何尋找或確定一個句型的句柄。給出了尋找句柄的不同算法就給出了不同的規(guī)范歸約方法，這一點我們將在LR分析器中討論。3.4.2算符優(yōu)先分析法所謂算符優(yōu)先分析，就是依照算術(shù)表達式的四則運算過程來進行語法分析，即這種分析方法要預先規(guī)定運算符(確切地說是終結(jié)符)之間的優(yōu)先關(guān)系和結(jié)合性質(zhì)，然后借助于這種關(guān)系來比較相鄰運算符的優(yōu)先級，以確定句型的“可歸約串”來進行歸約。因此，算符優(yōu)先分析法不是一種規(guī)范歸約，在整個歸約過程中起決定性作用的是相繼兩個終結(jié)符的優(yōu)先關(guān)系。

1．算符優(yōu)先文法如果一個文法存在…QR…的句型(Q和R都是非終結(jié)符)，則這種形式的句型意味著兩個算符之間操作數(shù)的個數(shù)是不定的，也就意味著每個算符的操作數(shù)是不定的。因此，我們首先定義一個任何產(chǎn)生式的右部都不含兩個相繼(并列)的非終結(jié)符的文法為算符文法，即算符優(yōu)先文法首先應(yīng)是一個算符文法；其次，我們還要定義任何兩個可能相繼出現(xiàn)的終結(jié)符a與b?(它們之間最多插有一個非終結(jié)符)的優(yōu)先關(guān)系。圖3–20不同優(yōu)先關(guān)系的語法樹示意

注意：與LL(1)文法所求的FIRST集相比，F(xiàn)IRST(A)是推導出的第一個終結(jié)符集，而FIRSTVT是首先遇到的終結(jié)符集；FOLLOW(A)是指緊跟非終結(jié)符A后的終結(jié)符集，而LASTVT是最后遇到的終結(jié)符集。由此，得到FIRSTVT集的構(gòu)造方法如下：

(1)若有產(chǎn)生式P→a…或P→Qa…，則a∈FIRSTVT(P)；

(2)若a∈FIRSTVT(Q)，且產(chǎn)生式P→Q…，則a∈FIRSTVT(P)。得到LASTVT集的構(gòu)造方法如下：

(1)若有產(chǎn)生式P→…a或P→…aQ，則a∈LASTVT(P)；

(2)若a∈LASTVT(Q)，且P→…Q，則a∈LASTVT(P)。

(2)構(gòu)造LASTVT集。①根據(jù)規(guī)則(1)知：由E→…+T得LASTVT(E)={+}；由T→…*F得LASTVT(T)={*}；由F→…)和F→i得LASTVT(F)={)，i}。②根據(jù)規(guī)則(2)知：由LASTVT(F)和T→F得LASTVT(T)={*，)，i}；由LASTVT(T)和E→T得LASTVT(E)={+，*，)，i}。

3．算符優(yōu)先分析法的設(shè)計由于算符優(yōu)先分析法不是一種規(guī)范歸約的分析方法，它僅在終結(jié)符之間定義了優(yōu)先關(guān)系而未對非終結(jié)符定義優(yōu)先關(guān)系，這樣就無法使用優(yōu)先關(guān)系表去識別由單個非終結(jié)符組成的可歸約串(如E→T)。因此，算符優(yōu)先分析法實際上不是用句柄來刻畫“可歸約串”，而是用最左素短語來刻畫“可歸約串”。在3.2.1節(jié)我們已經(jīng)給出了素短語的定義，并在3.2.2節(jié)給出了素短語的求解方法。在此，我們須再次強調(diào)：所謂句型的素短語，是指這樣一種短語，它至少包含一個終結(jié)符，并且除自身之外，不再包含其它更小的素短語。最左素短語則是指處于句型最左邊的那個素短語。下面，我們給出求解素短語的另一種方法。實際上，我們通過拓展圖3–20(b)可得到素短語所對應(yīng)的語法樹如圖3–21所示。由圖3–21可以看出，需要進行的歸約是將符號串NjajNj+1aj+1…aiNi+1歸約為P，而這個符號串恰好就是素短語，并且存在優(yōu)先關(guān)系：aj－1??aj，ajaj+1，…，ai－1ai，ai??ai+1。圖3–21素短語對應(yīng)的語法樹示意注意：素短語要素僅包含了構(gòu)成素短語的終結(jié)符序列，再添加構(gòu)成該短語的非終結(jié)符則形成了一個素短語；而最左素短語就是該句型中找到的最左邊的那個素短語要素與該要素有關(guān)的非終結(jié)符所組成的短語。最左素短語必須具備三個條件：

(1)至少包含一個終結(jié)符(是否包含非終結(jié)符則按短語的要求確定)；

(2)除自身外不得包含其它素短語(最小性)；

(3)在句型中具有最左性。此外，一定要注意最左素短語與句柄的區(qū)別。例3.13

已知文法G[E]為

G[E]：E→T∣E+T T→F∣T*F F→(E)∣i試確定F+T*i的最左素短語。

[解答]畫出對應(yīng)句型F+T*i的語法樹并根據(jù)語法樹確定相鄰終結(jié)符之間的優(yōu)先關(guān)系(見圖3–22)。根據(jù)最左素短語必須具備的條件及短語的要求(即必須包含某結(jié)點下的全部樹葉)得到最左素短語為i(該句型的最左直接短語為F，注意兩者的區(qū)別)。圖3–22F+T*i的語法樹及其優(yōu)先關(guān)系根據(jù)上