《編譯原理》課件第3章

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

3.2推導(dǎo)與語法樹

3.3自頂向下的語法分析

3.4自底向上的語法分析

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

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

3.1.1文法和語言的概念

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

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

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

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

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

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

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

例3.1

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

[解答]首先，標(biāo)識(shí)符是以字母開頭的字母數(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。最后，作為“標(biāo)識(shí)符”的非終結(jié)符I，它或者是一單個(gè)字母，或者為一字母后跟字母數(shù)字串，即

I→L∣LS因此，產(chǎn)生標(biāo)識(shí)符的文法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所示的三個(gè)部分，即最高位允許出現(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)任意位，所以另引入了一個(gè)非終結(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注意：在每一步推導(dǎo)過程中，只能對(duì)其中的一個(gè)非終結(jié)符用其對(duì)應(yīng)的產(chǎn)生式右部的一個(gè)候選式來替換。

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

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

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

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

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

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

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

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

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

4．3型文法與3型語言(對(duì)應(yīng)有限自動(dòng)機(jī))文法G[S]的每個(gè)產(chǎn)生式具有下列形式：A→a或A→aB其中，A、B∈VN，a∈VT*，則文法G[S]稱為3型文法、正規(guī)文法或右線性文法，記為RG。3型文法相應(yīng)的語言為3型語言或正規(guī)語言，它的識(shí)別系統(tǒng)是有限自動(dòng)機(jī)。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é)符號(hào)的符號(hào)串或兩個(gè)以上的非終結(jié)符，而2型和3型文法的產(chǎn)生式左部只允許是單個(gè)的非終結(jié)符號(hào)。

例3.3

試判斷下列產(chǎn)生式集所對(duì)應(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í)只有奇數(shù)個(gè)a和奇數(shù)個(gè)b的所有字符串集合的正規(guī)文法。

[解答]

為了構(gòu)造字母表Σ={a,b}上同時(shí)只有奇數(shù)個(gè)a和奇數(shù)個(gè)b的所有字符串的正規(guī)表達(dá)式，我們畫出如圖3–2所示的DFA，即由開始符S出發(fā)，經(jīng)過奇數(shù)個(gè)a到達(dá)狀態(tài)A，或經(jīng)過奇數(shù)個(gè)b到達(dá)狀態(tài)B。再由狀態(tài)A出發(fā)，經(jīng)過奇數(shù)個(gè)b到達(dá)狀態(tài)C(終態(tài))；同樣，由狀態(tài)B出發(fā)，經(jīng)過奇數(shù)個(gè)a到達(dá)終態(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ī)表達(dá)式與上下文無關(guān)文法

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

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

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

(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ī)表達(dá)式(a∣b)*abb。

[解答]首先構(gòu)造識(shí)別正規(guī)表達(dá)式(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事實(shí)上，由正規(guī)表達(dá)式構(gòu)造上下文無關(guān)文法還可以采用另一種方法，即通過分析正規(guī)表達(dá)式的特性憑經(jīng)驗(yàn)直接構(gòu)造。如可把(a∣b)*abb看作由(a∣b)*和abb兩部分組成，第一部分是由0個(gè)或若干個(gè)a和b組成的字符串，而第二部分則僅由abb字符串組成，由此得到上下文無關(guān)文法G[A]如下：

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

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

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

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

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

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

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

(1)每個(gè)結(jié)點(diǎn)用G[S]的一個(gè)終結(jié)符或非終結(jié)符標(biāo)記；

(2)根結(jié)點(diǎn)用文法開始符S標(biāo)記；

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

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

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

(1)短語：子樹的末端結(jié)點(diǎn)(即樹葉)組成的符號(hào)串是相對(duì)于子樹根的短語；

(2)直接短語：簡(jiǎn)單子樹的末端結(jié)點(diǎn)組成的符號(hào)串是相對(duì)于簡(jiǎn)單子樹根的直接短語；

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

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

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

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

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

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

3．文法的二義性文法G[S]的一個(gè)句子如果能找到兩種不同的最左推導(dǎo)(或最右推導(dǎo))，或者存在兩棵不同的語法樹，則稱這個(gè)句子是二義性的。一個(gè)文法如果包含二義性的句子，則這個(gè)文法是二義文法，否則是無二義文法。例如，對(duì)文法(3.1)，句子i+i*i存在著兩種最左推導(dǎo)或最右推導(dǎo)，所形成的兩棵不同的語法樹如圖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所對(duì)應(yīng)的兩棵不同語法樹見圖3–9。因此，文法G[S]是二義性文法。圖3–9句型ifBifBSelseS的兩棵不同語法樹顯然，二義性文法將給編譯程序的執(zhí)行帶來麻煩。對(duì)于二義性文法的句子，當(dāng)編譯程序?qū)λ慕Y(jié)構(gòu)進(jìn)行語法分析時(shí)，就會(huì)產(chǎn)生兩種甚至多種不同的解釋；由于語法結(jié)構(gòu)的這種不確定性，因而必將導(dǎo)致語義處理上的不確定性。

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

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

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

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

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

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

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

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

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

圖3–11復(fù)合if語句的語法樹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

E→E+T//簡(jiǎn)單表達(dá)式→簡(jiǎn)單表達(dá)式+項(xiàng)如果對(duì)該左遞歸文法采用自上而下分析法，即首先以“E+T”中的E為目標(biāo)對(duì)“E+T”進(jìn)行試探，進(jìn)而又以其中的E為目標(biāo)再對(duì)選擇“E+T”進(jìn)行試探；也即E+T

E+T+T

E+T+T+T

…，這種左遞歸的文法使自上而下分析工作陷入無限循環(huán)。也就是說，當(dāng)試圖用E去匹配輸入符號(hào)串時(shí)會(huì)發(fā)現(xiàn)：在沒有吃進(jìn)任何輸入符號(hào)的情況下，又得重新要求E去進(jìn)行新的匹配。因此，使用自上而下分析法首先要消除文法的左遞歸性。對(duì)于回溯，由上述不確定的自上而下分析示例可知，由于回溯的存在，可能在已經(jīng)做了大量的語法分析工作之后，才發(fā)現(xiàn)走了一大段錯(cuò)路而必須回頭，要把已經(jīng)做的一大堆語義工作(指中間代碼產(chǎn)生工作和各種表格的簿記工作)推倒重來。回溯使得自上而下語法分析只具有理論意義而無實(shí)際使用的價(jià)值。因此，要使自上而下語法分析具有實(shí)用性，就必須要消除回溯。例如，含有直接左遞歸的表達(dá)式文法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)化簡(jiǎn)由(2)所得的文法，即去掉那些從開始符號(hào)S出發(fā)，在推導(dǎo)中無法出現(xiàn)的非終結(jié)符的產(chǎn)生式(去掉多余產(chǎn)生式)。注意消除左遞歸之前的文法不允許有ε產(chǎn)生式，否則無法得到等效的無左遞歸文法。因此，如果原文法中有ε的產(chǎn)生式，則需將文法改寫為無ε的產(chǎn)生式的文法。此外，此算法并未對(duì)非終結(jié)符的排列順序加以規(guī)定，不同的排列可能得到不同的結(jié)果，但彼此是等價(jià)的。例如，將文法(3.3)的非終結(jié)符排序?yàn)镽、Q、S。對(duì)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è)文法G'[S]為

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

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

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此時(shí)，如果輸入串待分析的字符串前綴為α，則選用哪個(gè)候選式以尋求與輸入串匹配就難以確定。倘若候選式不含公共左因子，則推導(dǎo)出的首字符能與輸入串匹配的那個(gè)候選式便是惟一的匹配。在文法G[S]中的每個(gè)非終結(jié)符相應(yīng)的產(chǎn)生式右部其候選式均不含公共左因子的情況下，語法分析的匹配過程都是惟一匹配，無需試探；這時(shí)若匹配失敗，則意味著輸入串不是句子。我們也可以用數(shù)學(xué)中提取公共因子的辦法來提取公共左因子。如對(duì)式(3.5)提取公共(左)因子后得

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

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

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

5．遞歸下降分析器在不含左遞歸和每個(gè)非終結(jié)符的所有候選終結(jié)首符集都兩兩不相交的條件下，我們就可能構(gòu)造一個(gè)不帶回溯的自上而下的分析程序，這個(gè)分析程序是由一組遞歸過程(或函數(shù))組成的，每個(gè)過程(或函數(shù))對(duì)應(yīng)文法的一個(gè)非終結(jié)符。這樣的一個(gè)分析程序稱為遞歸下降分析器。例如，文法(3.2)對(duì)應(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'只有兩個(gè)候選式：第一個(gè)候選式的開頭終結(jié)符為+，第二個(gè)候選式為ε。這就是說，當(dāng)E'面臨輸入符號(hào)“+”時(shí)就令第一個(gè)候選式進(jìn)入工作，而當(dāng)面臨任何其它符號(hào)時(shí)，E'就自動(dòng)認(rèn)為獲得了匹配。遞歸函數(shù)E'就是根據(jù)這一原則設(shè)計(jì)的。例如，我們將遞歸函數(shù)的調(diào)用以棧的形式模擬來分析輸入串#i1*(i2+i3)#的語法分析過程；在此，“#”為輸入串i1*(i2+i3)的分隔符。進(jìn)行語法分析時(shí)，首先將“#”和文法開始符E壓入棧中，當(dāng)語法分析進(jìn)行到棧中僅剩“#”而輸入串掃描指針已指向輸入串尾部的“#”時(shí)，則語法分析成功，分析過程如圖3–14所示。圖3–14輸入串i1*(i2+i3)的語法分析注意：圖3–14中第(5)步執(zhí)行函數(shù)F(?)時(shí)，因當(dāng)前掃描的字符為“(”，故匹配后應(yīng)執(zhí)行E(?)(用棧模擬即為將E壓棧)；并且，在執(zhí)行完E(?)后還應(yīng)執(zhí)行其后的判斷“)”與匹配“)”語句，這在棧的模擬中則是標(biāo)出此時(shí)E壓棧之前的位置(見圖3–12的第(7)～(14)步)，即彈棧至此時(shí)(第(14)步結(jié)束時(shí))應(yīng)執(zhí)行這個(gè)判斷“)”與匹配“)”語句。我們還可以用另一種表示法得到遞歸下降分析器，即將文法的每一個(gè)非終結(jié)符用VT∪VN上的一個(gè)正規(guī)表達(dá)式來定義，然后將其用狀態(tài)轉(zhuǎn)換圖表示，并借助于這種轉(zhuǎn)換圖來得到遞歸下降分析器。這種方法的特點(diǎn)是可以不消除文法的左遞歸。文法(3.2)的每個(gè)非終結(jié)符可由下面的正規(guī)表達(dá)式定義：

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

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

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

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

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

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

(2)分析棧中存放分析過程中的文法符號(hào)。分析開始時(shí)棧底先放入一個(gè)‘#’，然后再壓入文法的開始符號(hào)；當(dāng)分析棧中僅?！?’，輸入串指針也指向串尾的‘#’時(shí)，分析成功。

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

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

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

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

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

(1)FIRST集構(gòu)造方法：對(duì)文法中的每一個(gè)非終結(jié)符X構(gòu)造FIRST(X)，其方法是連續(xù)使用下述規(guī)則，直到每個(gè)集合的FIRST不再增大為止。(注：對(duì)終結(jié)符a而言，F(xiàn)IRST(‘a(chǎn)’)={a}，因而無需構(gòu)造。)①若有產(chǎn)生式X→a…，且a∈VT，則把a(bǔ)加入到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)中；特別是當(dāng)Y1～Yk均含有ε產(chǎn)生式時(shí)，應(yīng)把ε也加到FIRST(X)中。

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

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

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

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

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

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

證明下述文法G[S]不是LL(1)?文法，并給出其等價(jià)的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)?={#};對(duì)產(chǎn)生式L→i:∣ε，由于有FIRST(i:)∩FOLLOW(L)?={i}∩{i}≠Φ，所以文法G[S]?不是LL(1)?文法。為了滿足LL(1)文法的條件，需對(duì)文法G[S]?進(jìn)行如下改造：（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這時(shí)有：FIRST(S)?={i}；FIRST(A)?={:?,?=}；

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

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

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

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

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

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

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

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

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

(1)至少包含一個(gè)終結(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的最左素短語。

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