南大面試課程編譯課件chapter 4

第四章語法分析戴新宇2013-31概要語法分析器上下文無關(guān)文法語法分析技術(shù)自頂向下自底向上語法分析器生成工具2引言程序設(shè)計語言源程序的構(gòu)成文法：一種用于描述程序設(shè)計語言語法的表示方法，能夠自然地描述程序設(shè)計語言構(gòu)造的層次化語法結(jié)構(gòu)。文法給出了一個程序設(shè)計語言的精確易懂的語法規(guī)約可以基于文法構(gòu)造語法分析器，幫助確定源程序的語法結(jié)構(gòu)語法結(jié)構(gòu)有助于把源程序翻譯為正確的目標代碼，以及檢測導(dǎo)語法錯誤。文法的擴展性StandardC++GrammarJavaSE7Grammar3語法分析器（What）輸入：詞法分析器輸出的詞法單元序列輸出：語法樹表示語法分析器的類型：通用型(CKY，Earley)自頂向下：通常處理LL文法自底向上：通常處理LR文法4語法分析器（Why）語法分析器功能：驗證輸入源程序的合法性，并輸出良構(gòu)程序的語法結(jié)構(gòu)對于病構(gòu)的程序，能夠報告語法錯誤，并進行錯誤回復(fù)寫入符號表，類型檢查，語義分析，翻譯生成中間代碼等往往和語法分析過程交錯完成，實踐中往往和語法分析放入一個模塊，圖上用“前端的其余部分”表示上述活動。5文法本書特指上下文無關(guān)文法（ContextFreeGrammar,CFG）程序設(shè)計語言中往往存在嵌套結(jié)構(gòu)上下文無關(guān)文法是一種能夠很好描述程序設(shè)計語言的表示方法

stmt→if(expr)stmtelsestmtexpr→……

stmt→……6CFG的定義一個CFG由以下幾個部分構(gòu)成終結(jié)符號組成串的基本符號，與“詞法單元名字”同義非終結(jié)符號語法變量，表示特定串的集合給出了語言的層次結(jié)構(gòu)，這種層次結(jié)構(gòu)是語法分析和翻譯的關(guān)鍵一個開始符號某個特定的非終結(jié)符號，其表示的串集合是這個文法生成的語言一組產(chǎn)生式描述將終結(jié)符合和非終結(jié)符號組合成串的方法產(chǎn)生式左部（頭）是一個非終結(jié)符號符號“→”一個由零個或多個終結(jié)符號與非終結(jié)符號組成的產(chǎn)生式右部（體）7用于描述算術(shù)表達式的文法定義8S->NPVPVP->VNPNP->NAMENP->ARTNNAME->JohnV->ateART->theN->cat符號表示約定終結(jié)符號：ab+3id…非終結(jié)符號:ABC…,S,stmt文法符號:XY…終結(jié)符號串:uvw…文法符號串:α

β…不同可選體:

α1

α2

α3…開始符號:S9推導(dǎo)產(chǎn)生式又可稱為重寫規(guī)則（Rewritingrule）從開始符號出發(fā)，每個重寫步驟把一個非終結(jié)符號替換為它的某個產(chǎn)生式的體。e.g.E-E–(E)–(id)，稱為從E到-(id)的推導(dǎo)。這個推導(dǎo)說明了–(id)是表達式E的一個實例，或者說由E產(chǎn)生。推導(dǎo)的一般性定義：假設(shè)一個產(chǎn)生式A

→γ，αAβ

αγβ，符號表示“通過一步推導(dǎo)出”。10推導(dǎo)（續(xù)）推導(dǎo)序列α1α2…αn，稱為α1推導(dǎo)到αn。記作α1

αn，指經(jīng)過零步或多步推導(dǎo)。對于任意串如果表示經(jīng)過一步或多步推導(dǎo)出句型：如果從文法的開始符號S開始，，則稱α是G的一個句型。句子，不包括非終結(jié)符號的句型。語言：句子的集合{w|Sw}，由文法G生成的語言被稱為上下文無關(guān)語言L(G)。文法的等價性：兩個文法生成相同語言，則兩文法等價11推導(dǎo)例子12推導(dǎo)中的問題從推導(dǎo)的角度看，語法分析的任務(wù)是：接受一個終結(jié)符號串作為輸入，找出從文法的開始符號推導(dǎo)出這個串的方法。推導(dǎo)中可能遇到的兩個問題每一步替換哪個非終結(jié)符號若以這個非終結(jié)符號為頭的產(chǎn)生式有多個，用哪個產(chǎn)生式的右部替換13非終結(jié)符號的替換順序通常使用兩種方式進行推導(dǎo)最左推導(dǎo)：總是選擇每個句型的最左非終結(jié)符號。記作最右推導(dǎo)：總是選擇最右邊的非終結(jié)符號。記作每個最左推導(dǎo)步驟可以寫成，,是應(yīng)用的產(chǎn)生式如果經(jīng)過最左推導(dǎo)得到，記作最左句型：S是文法G的識別符號，如果，則是G的最左句型14語法分析樹是推導(dǎo)的圖形表示形式，樹上看不出來推導(dǎo)的順序能夠反映串的語法層次結(jié)構(gòu)語法分析樹內(nèi)部節(jié)點：對應(yīng)于一個非終結(jié)符號子節(jié)點：對應(yīng)于其父節(jié)點為頭的產(chǎn)生式體葉子節(jié)點：可以是終結(jié)符號或非終結(jié)符號，從左到右排列可以得到一個句型，稱為這棵樹的結(jié)果。15SNPVPNAMEJohnVNPateARTNthecatS->NPVPVP->VNPNP->NAMENP->ARTNNAME->JohnV->ateART->theN->cat推導(dǎo)和語法樹對于推導(dǎo)中的每個句型，我們都可以構(gòu)造出一個結(jié)果為的語法樹17推導(dǎo)與語法樹例子18二義性文法如果一個文法可以為一個句子生成多顆不同的語法分析樹，則該文法為二義性文法。通常情況下，我們需要無二義性的文法19詞法分析和語法分析比較

階段輸入輸出描述體系詞法分析源程序符號串詞法單元序列正則表達式句法分析詞法單元序列語法樹上下文無關(guān)文法20文法比正則表達式描述能力更強正則表達式描述詞法單元比較簡潔基于正則表達式構(gòu)造的詞法分析器效率更高正則表達式適合描述詞法結(jié)構(gòu)，文法適合描述嵌套結(jié)構(gòu)補充文法的類別，Chomsky文法類0型文法(短語結(jié)構(gòu)文法)，α→β

1型文法(上下文相關(guān)文法)，αAβ→αγβ2型文法(上下文無關(guān)文法)，A→γ3型文法(正則文法)，A→t,A→tB21上下文無關(guān)文法和正則表達式CFG的表達能力更強每個正則表達式都可以用一個上下文無關(guān)文法來描述，反之不成立每個正則語言都是一個上下文無關(guān)語言，反之不成立正則表達式(a|b)*abb等價于文法22Ａ０→ａＡ０｜ｂＡ０｜ａＡ１Ａ１→ｂＡ２Ａ２→ｂＡ３Ａ３→ε為NFA構(gòu)造等價文法23文法及其生成的語言語言是由文法的開始符號出發(fā)，能夠推導(dǎo)得到的所有句子的集合。文法G:S→aS|a|b,L(G)={ai(a|b),i>=0}文法G：S→aSb|ab,L(G)={anbn,n>=1}文法G：S→(S)S|ε,L(G)={所有具有對稱括號對的串}如何驗證文法G所確定的語言L證明G生成的每個串都在L中證明L中的每個串都能被G生成實質(zhì)上回歸到了原始的定義，證明采用數(shù)學(xué)歸納法24文法的設(shè)計在進行高效的語法分析之前，需要對文法做以下處理消除二義性文法的二義性：文法可以為一個句子生成多顆不同的樹消除左遞歸左遞歸：文法中一個非終結(jié)符號A使得對某個串α，存在一個推導(dǎo)，則稱這個文法是左遞歸的。提取左公因子25消除文法的二義性把二義性文法改寫成無二義性文法26消除文法的二義性（續(xù)）27消除文法的二義性（續(xù)）改寫文法，基本思想:在一個then和一個else之間出現(xiàn)的語句必須是“已匹配的”。也就是說then和else中間的語句不能以一個尚未匹配的then結(jié)尾。解決方案：引入新的非終結(jié)符號，用來區(qū)分是否是成對的then/else。28消除左遞歸左遞歸：文法中一個非終結(jié)符號A使得對某個串α，存在一個推導(dǎo)，則稱這個文法是左遞歸的如果存在A→Aα,則稱為立即左遞歸自頂向下的語法分析技術(shù)不能處理左遞歸的文法立即左遞歸消除：29

A→Aα|βA→βA’A’→αA’|ε立即左遞歸消除示例30消除立即左遞歸步驟首先對A產(chǎn)生式分組(所有αi不等于ε，βi不以A開頭)：然后將這些產(chǎn)生式替換為：31消除多步左遞歸消除立即左遞歸的方法并不能消除因為兩步或多步推導(dǎo)而產(chǎn)生的左遞歸文法：S→Aa|b,A→Ac|Sd|εS=>

Aa=>Sda如何消除？32消除算法算法原理：給非終結(jié)符號排序，A1,A2…,An如果只有Ai-->Aj(i<j)，則不會有左遞歸如果發(fā)現(xiàn)Ai-->Aj(i>j),代入Aj的當前產(chǎn)生式，若替換后有Ai的直接左遞歸，再消除輸入：沒有環(huán)AiAi和A→ε輸出：一個等價的無左遞歸的文法33消除算法（示例）S→Aa|b,A→Ac|Sd|ε排序

SAi=1，沒有處理i=2,替換A→Sd中的S，得到A→Ac|Aad|bd|ε消除立即左遞歸34提取左公因子在推導(dǎo)的時候，不知道該如何選擇（自頂向下算法會詳細描述）35A→αβ1\αβ2A→αA’A’→β1\β2提取左公因子算法輸入：文法G輸出：一個等價的提取了左公因子的文法方法：對于每個非終結(jié)符號A，找出它的兩個或多個可選項之間的最長公共前綴α，且α≠ε，那么將A所有的產(chǎn)生式

A→αβ1\αβ2\...\αβn\γ

替換為

A→αA’\γA’→β1\β2\...\βn36提取左公因子37自頂向下分析技術(shù)自頂向下分析可以被看作是為輸入串構(gòu)造語法分析樹的問題。也可以看作一個尋找輸入串的最左推導(dǎo)的過程。問題：在推導(dǎo)的每一步，對非終結(jié)符號A，應(yīng)用哪個產(chǎn)生式，以可能產(chǎn)生于輸入串相匹配的終結(jié)符號串。38id+id*id的自頂向下分析39問題：對于非終結(jié)符號A，選擇哪一個產(chǎn)生式？自頂向下語法分析一種通用的遞歸下降分析框架由一組過程組成，每個非終結(jié)符號對應(yīng)一個過程程序的執(zhí)行從開始符號對應(yīng)的過程開始每個過程的功能是：選擇一個產(chǎn)生式體，掃描相應(yīng)的句子。若遇到非終結(jié)符號，調(diào)用該符號對應(yīng)的過程。40問題：對于非終結(jié)符號A，選擇哪一個產(chǎn)生式？遞歸下降分析過程示例輸入串w=cad文法：S→cAdA→ab|a41遞歸下降過程示例(續(xù))可能需要回溯?；蛘哒f，可能需要重復(fù)掃描輸入。“在回到A時，我們必須把輸入指針重新設(shè)置到位置2，即我們第一次嘗試展開A時該指針指向的位置。這意味著A的過程必須將輸入指針存放在一個局部變量中。”如果文法中存在左遞歸……回溯（盲目的試）顯然是最愚蠢的辦法42預(yù)測分析技術(shù)一種確定性的、無回溯的分析技術(shù)在每一步選擇正確的產(chǎn)生式43例1：文法G(S)：S→pAS→qBA→cAdA→a輸入串W=pccadd預(yù)測分析技術(shù)（續(xù)）44例2：文法G(S)為：

S→ApS→BqA→a∣cAB→b∣dB輸入W=ccap預(yù)測分析技術(shù)（續(xù)）通過在輸入中向前看固定多個符號來選擇正確的產(chǎn)生式通常情況下，我們只需要向前看一個符號給出兩個與文法相關(guān)的兩個函數(shù)FIRSTFOLLOW基于上述兩個函數(shù)，可以根據(jù)下一個輸入符號來選擇應(yīng)用哪個產(chǎn)生式45FIRST(α)定義：可從α推導(dǎo)得到的串的首符號的集合，其中α是任意的文法符號串。如果α

ε，那么ε也在FIRST(α)中。FIRST函數(shù)的意義如果兩個A產(chǎn)生式A→α|β，其中First(α)和First(β)是不相交的集合。下一個輸入符號是a，若a∈First(α)，則選擇A→α，若a∈First(β)，則選擇A→β。46First的計算對于文法符號X的FIRST(X)，通過不斷應(yīng)用下列規(guī)則，直到?jīng)]有新的終結(jié)符號或者ε可以加入到任何FIRST集合為止。如果X是終結(jié)符號，那么FIRST(X)={X}如果X是非終結(jié)符號，且有規(guī)則X→a…,那么將a添加到FIRST(X)中。如果X→

，那么也在FIRST(X)中。對于產(chǎn)生式X→Y1Y2…Yn,把FIRST(Y1)中的非符號添加到FIRST(X)中。如果在FIRST(Y1)中，把FIRST(Y2)中的非符號添加到FIRST(X)中…；如果在FIRST(Yn)中，把添加到FIRST(X)中。47First的計算（續(xù)）對于文法符號串X1X2…Xn的First集合向First(X1X2…Xn)加入First(X1)中所有的非ε符號。如果ε在First(X1)中，再加入First(X2)中的所有非ε符號。如果ε在First(X1)和First(X2)中，再加入First(X3)中的所有非ε符號。依次類推。如果對所有的i（1到n），ε都在First(Xi)中，則ε加入First(X1X2…Xn)中。48First的計算示例First(F)=First(T)=First(E)={(,id}First(E’)={+,ε}First(T’)={*,ε}First(TE’)=First(T)={(,id}First(+TE’)={+}……49FOLLOW函數(shù)對于非終結(jié)符號A，F(xiàn)OLLOW(A)定義為可能在某些句型中緊跟在A右邊的終結(jié)符號的集合。S

αAaβ，終結(jié)符號a∈Follow(A)。如果A是某些句型的最右符號，那么$∈Follow(A)。$是特殊的輸入串“結(jié)束標記”FOLLOW函數(shù)的意義：如果A→α，當α→

或α

時，F(xiàn)OLLOW(A)可以幫助我們做出選擇恰當?shù)漠a(chǎn)生式例如：ifA→α,b屬于FOLLOW(A)，如果α

，則若當前輸入符號是b，可以選擇A→α，因為A最終到達了

，而且后面跟著b。50文法G[S],輸入bcdS→AB|CDA→aD|εC→cDB→bCD→dFOLLOW計算計算各個非終結(jié)符號A的FOLLOW(A)集合，不斷應(yīng)用下列規(guī)則，直到?jīng)]有新的終結(jié)符號可以被加入到任意FOLLOW集合中。將$放入FOLLOW(S)，S是開始符號。而$是輸入串的結(jié)束標記。如果存在產(chǎn)生式A→αBβ，那么First(β)中除ε之外的所有符號都在Follow(B)中。如果存在一個產(chǎn)生式A→αB，或存在產(chǎn)生式A→αBβ且First(β)包含ε，那么Follow(A)中的所有符號都在Follow（B）中。51Follow的計算示例52文法 E→TE’ E’

→+TE’| T→FT’

T’→*FT’| F

→(E)|iFOLLOW(E)={)，$}FOLLOW(E’)={)，$}FOLLOW(T)={+，)，$}FOLLOW(T’)={+，)，$}FOLLOW(F)=(*，+，)，$)

←FIRST())U{$}

←FOLLOW(E)

←FIRST(E’)UFOLLOW(E’)

←FOLLOW(T)

←FIRST(T’)UFOLLOW(T)LL(1)文法如果對于文法G的任意兩個不同的產(chǎn)生式A→α|β滿足下列條件：First(α)

First(β)

=

α

和β

不能同時成立如果β

，那么FIRST(α)FOLLOW(A)=滿足上述條件的文法稱為LL(1)文法，第一個L表示自左向右掃描，第二個L指產(chǎn)生最左推導(dǎo)，而1則表示向前看一個輸入符號LL(1)文法可以利用不回溯的確定性的預(yù)測分析技術(shù)，因為只需要檢查當前輸入符號就可以為一個非終結(jié)符號選擇正確的產(chǎn)生式53預(yù)測分析技術(shù)前提：無左遞歸&LL(1)文法將first和follow集合中的信息放入一個預(yù)測分析表M[A,a]，該預(yù)測表告訴我們當非終結(jié)符號為A，當前輸入符號為a時，要選擇哪條產(chǎn)生式。預(yù)測分析表的構(gòu)造思想：若當前輸入符號a在First(α)中，選擇產(chǎn)生式A→α。若α

，如果a在Follow(A)中，選擇產(chǎn)生式A→α;或如果當前符號a是$，且$在Follow(A)中，則選擇產(chǎn)生式A→α。54預(yù)測分析表構(gòu)造輸入：文法G輸出：預(yù)測分析表M方法：對于文法G的每個產(chǎn)生式A→α，進行如下處理：對于First(α)中的每個終結(jié)符號a，將A→α加入到M[A,a]如果

在First(α)中，那么對于Follow(A)中的每個終結(jié)符號b，將A→α加入到M[A,b]中如果

在First(α)中，且$在Follow(A)中，將A→α加入到M[A,$]中完成上述操作后，若M[A,a]中沒有產(chǎn)生式，填為error55預(yù)測分析表構(gòu)造示例文法：E→TE’ E’→+TE’| T→FT’ T’→*FT’| F→(E)|i56FIRST(TE’)={(，i}FIRST(＋TE’)={＋}FIRST(FT’)={(，i}FIRST(*FT’)={*}FIRST((E))={(}FIRST(i)＝{i}FOLLOW(E)={)，$}FOLLOW(E’)={)，$}FOLLOW(T)={+，)，$}FOLLOW(T’)={+，)，$}FOLLOW(F)=(*，+，)，$)

FT’T

E’E

$

)

(*

+

iE→TE’E→TE’E’→+TE’E’→εE’→εT→FT’T→FT’T’→*FT’T’→εT’→εT’→εF→(E)F→i預(yù)測分析表（續(xù)）對于任何文法G，都可以構(gòu)造預(yù)測分析表。但是對于LL(1)文法，預(yù)測表中每個條目都唯一地指定了一個產(chǎn)生式，或者標明error對于LL(1)文法，如何改造遞歸下降程序，使之能夠避免回溯？57二義性文法的預(yù)測分析表對于某些文法，表中可能會有一些多重定義的條目，比如左遞歸或二義性文法。58非遞歸的預(yù)測分析技術(shù)文法符號棧輸入緩沖區(qū)控制程序在任何時刻，棧頂符號X與當前輸入符號a決定了控制程序所應(yīng)執(zhí)行的分析動作。四種可能的動作如果X=a=$，則分析成功結(jié)束如果X=a≠$，則從棧中退去X，并把輸入指針推進到指向下一個輸入符號；如果X是一個非終結(jié)符號，且分析表M的元素M[X，a]=“X→X1X2…Xk”，則把棧頂?shù)腦替換為XkX2…X1（反向下推入棧，使得X1在棧頂）。除上述情況外的其它情況，調(diào)出出錯程序。59表驅(qū)動的非遞歸的預(yù)測語法分析輸入：一個串w，文法G的預(yù)測分析表M。輸出：如果w在L(G)中，輸出w的一個最左推導(dǎo)；否則報錯。方法：初始化輸入緩沖區(qū)為w$,棧頂是G的開始符號S，下面是$

。60預(yù)測分析示例61自底向上句法分析概述移進-規(guī)約技術(shù)LR語法分析技術(shù)簡單LR技術(shù)LR技術(shù)62自底向上句法分析概述自底向上語法分析過程對應(yīng)于為一個輸入串構(gòu)造語法分析樹的過程。從葉子節(jié)點（底部）開始逐漸向上到達根節(jié)點（頂部）Bottom-UpParsing63自底向上句法分析概述-歸約Bottom-upparsing–將一個串w歸約為文法符號的過程在每一步的歸約中，一個與某產(chǎn)生式體相匹配的特定子串被替換為該產(chǎn)生式頭部的非終結(jié)符號。一次歸約實質(zhì)上是一個推導(dǎo)的反向操作。Bottom-upparsing–將一個串w歸約為文法符號的過程–反向構(gòu)造一個推導(dǎo)的過程問題：何時進行歸約應(yīng)用哪個產(chǎn)生式進行歸約64自底向上句法分析概述–句柄剪枝Bottom-UpParsing–歸約過程–反向最右推導(dǎo)過程–句柄剪枝過程句柄：和某個產(chǎn)生式體相匹配的子串，對它的歸約代表了相應(yīng)的最右推導(dǎo)的一個反向步驟。65最右句型句柄歸約用產(chǎn)生式id1*id2id1F→idF*id2FT→FT*id2id2F→idT*FT*FT→T*FTTE→T句柄剪枝句柄的形式定義：SαAwαβw，那么緊跟α的β可以一步歸約到A。w是終結(jié)符號串。注意：歸約前后都是最右句型和某個產(chǎn)生式匹配的最左子串不一定是句柄無二義性的文法，其每個右句型都有且只有一個句柄

自底向上句法分析概述–句柄剪枝（續(xù)）通過“句柄剪枝”可以得到一個反向的最右推導(dǎo)。從句子w開始，令w=γn,γn是未知最右推導(dǎo)的第n個最右句型。以相反的順序重構(gòu)這個推導(dǎo)（實際上是重構(gòu)歸約序列），我們在γn中尋找句柄βn，并將替換為相應(yīng)產(chǎn)生式A→βn的頭部，得到前一個最右句型γn-1。重復(fù)這個過程，直到S。問題轉(zhuǎn)變?yōu)椋喝绾握业骄浔浚〝R置一下這個問題先）67移進歸約語法分析框架一種自底向上的分析形式使用一個棧保存文法符號，一個輸入緩沖區(qū)存放將要進行分析的剩余符號初始棧：$初始輸入w$對輸入串的一次從左到右的掃描過程中，語法分析器將零個或多個輸入符號移到棧的頂端，直到它可以對棧頂?shù)囊粋€文法符號串進行歸約為止。它將歸約為某個產(chǎn)生式的頭。不斷重復(fù)這個循環(huán)，直到它檢測到一個語法錯誤，或者棧中包含了開始符號且輸入緩沖區(qū)為空。分析成功時：棧$S,輸入$68移進歸約語法分析框架（續(xù)）移進歸約分析器的四種可能動作移入(Shift)：將下一個輸入符號移到棧頂歸約(Reduce)：被歸約的符號串（句柄）的最右端必然是棧頂，語法分析器在棧中確定它的最左端，將句柄從棧中推出，將歸約得到的非終結(jié)符號壓入棧。接受：分析結(jié)束并成功報錯：發(fā)現(xiàn)語法分析錯誤69移進歸約語法分析框架（續(xù)）可行性分析：句柄總是出現(xiàn)在棧的頂端，絕不會出現(xiàn)在棧的中間。語法分析器進行一次歸約以后，都必須接著移入零個或多個符號才能在棧頂找到下一個句柄。不需要去棧中間去尋找句柄70移進歸約沖突移入-歸約技術(shù)并不能處理所有上下文無關(guān)文法某些上下文無關(guān)文法（比如二義性文法）：移入/歸約沖突：棧中的內(nèi)容和接下來的k個輸入符號，都不能確定進行移入還是歸約操作。不能確定是否是句柄。歸約/歸約沖突：存在多個可能的歸約到不同非終結(jié)符號的歸約。不能確定句柄歸約到那個非終結(jié)符號。71移入/歸約沖突72歸約/歸約沖突73沖突問題讓詞法分析區(qū)分id和procid用[]表示數(shù)組，用()表示函數(shù)……但是并不能完全解決沖突問題有一類文法可以解決句柄查找及歸約唯一性的問題74ReviewofBottom-upParsing從輸入串出發(fā)構(gòu)造一個反向最右推導(dǎo)序列（歸約）每一步是對句柄進行歸約--尋找句柄一種移進-歸約的分析框架一個棧存放文法符號，一個輸入緩沖區(qū)移進or歸約總是能夠在棧的頂端找到句柄通過證明是可行的有時候會有沖突，是移進還是歸約？怎么歸約？75LR語法分析技術(shù)只要存在一個從左到右掃描的移進-歸約語法分析器，它總能在某文法的最右句型的句柄出現(xiàn)在棧頂時識別出這個句柄，那么這個文法就是LR的。表格驅(qū)動，如果能夠用某個方法為一個文法構(gòu)造出移進-歸約語法分析表，那么就稱為LR文法LR(k)分析：目前最流行的無回溯的移入-歸約分析技術(shù)，并且高效L：從左往右掃描輸入R:反向構(gòu)造一個最右推導(dǎo)序列k:向前看k個符號（通常k<=1,缺省為1）以幫助做出移入或歸約的決定LR語法分析技術(shù)很有吸引力用于描述程序設(shè)計語言的上下文無關(guān)文法，通常均可以使用LR分析技術(shù)對輸入進行掃描時可以盡早檢測到錯誤能用該技術(shù)的文法類是使用預(yù)測方法或LL方法的文法類的真超集。（能處理更多的文法）76LR分析相關(guān)概念移入-歸約語法分析器如何知道何時該移入、何時該歸約呢？LR語法分析器試圖用一些狀態(tài)來表明我們在移進歸約語法分析過程中所處的位置，從而做出移入-歸約決定。LR(0)項(item)：一個文法G的一個LR(0)項是G的一個產(chǎn)生式再加上一個位于它的體中某處的點。項的意義：指明在語法分析過程中的給定點上，我們已經(jīng)看到了一個產(chǎn)生式的哪些部分?；蛘哒f，如果我們想用這個產(chǎn)生式進行歸約，還需要看到哪些文法符號。項的集合（項集）對應(yīng)于一個狀態(tài)77LR(0)項集規(guī)范族三個相關(guān)定義：增廣文法項集閉包GOTO函數(shù)增廣文法G’：在文法G上增加一個產(chǎn)生式S’→S。意義：引入的目的是告訴語法分析器何時宣布接受輸入符號串。即用S’→S進行歸約時，表明分析結(jié)束。78LR(0)項集規(guī)范族--項集閉包項集的閉包CLOSURE：如果I是文法G的一個項集，那么CLOSURE(I)就是根據(jù)下列兩條規(guī)則從I構(gòu)造得到的項集將I中的各個項加入到CLOSURE(I)中如果A→α·Bβ在CLOSURE(I)中，B→γ是一個產(chǎn)生式，并且項B→·γ不在CLOSURE(I)中，就將該項加入其中。不斷應(yīng)用這條規(guī)則，直到?jīng)]有新項可以加入到CLOSURE(I)為止。意義：A→α·Bβ，表示接下來希望看到由Bβ推導(dǎo)出的串，那首先要看到由B推導(dǎo)得到的子串，因此加上B的各個產(chǎn)生式對應(yīng)的項。79項集閉包計算示例及算法I={[E’→·E]}CLOSURE(I)={[E’→·E],[E→·E+T],[E→·T],[T→·T*F],[T→·F],[F→·(E)],[F→·id]}80LR(0)項集規(guī)范族–GOTO函數(shù)GOTO函數(shù)：I是一個項集，X是一個文法符號，GOTO(I,X)定義:I中所有形如[A→α·Xβ]的項所對應(yīng)的項[A→αX·β]的集合的閉包。示例：I={[E’→E·],[E→

E·+T]}GOTO(I,+)={[E→

E+·T],[T→·T*F],[T→·F],[F→·(E)],[F→·id]}81LR(0)項集規(guī)范族的構(gòu)造為文法G構(gòu)造LR(0)項集規(guī)范族C步驟一：構(gòu)造增廣文法G’:S’→S……步驟二：構(gòu)造I0=CLOSURE(S’→·S)，I0是C的初始項集步驟三：對C中的每個項集Ii及每個文法符號Xj，將GOTO(Ii,Xj)加入到C中重復(fù)步驟三，直到?jīng)]有新的項集可以加入82Voiditems(G’){

C={CLOSURE({[S’→·S]})};repeatfor(C中的每個項集I)for(每個文法符號X)if(GOTO(I,X)非空且不在C中)

將GOTO(I,X)加入C中until在某一輪中沒有新的項集被加入到C中；}LR(0)項集規(guī)范族構(gòu)造示例83LR(0)項集規(guī)范族→LR(0)自動機基于規(guī)范LR(0)項集族可以構(gòu)造一個確定性的LR(0)自動機規(guī)范LR(0)項集族中的一個項集對應(yīng)于LR(0)自動機中的一個狀態(tài)。GOTO函數(shù)則定義了LR(0)自動機中的狀態(tài)轉(zhuǎn)換。GOTO(I,X)描述了當輸入為X時離開狀態(tài)I的轉(zhuǎn)換。84LR(0)自動機通過構(gòu)造LR(0)項集規(guī)范族可以得到LR(0)自動機LR(0)自動機的開始狀態(tài)是CLOSURE({[S’→·S]})。狀態(tài)j是指對應(yīng)于項集Ij的狀態(tài)每個狀態(tài)對應(yīng)于一個文法符號，GOTO(Ii,X)=Ij，則到達j狀態(tài)的轉(zhuǎn)換一定對應(yīng)于同一個文法符號X85利用LR(0)自動機進行移進歸約語法分析簡單LR語法分析技術(shù)（SLR分析）的中心思想：根據(jù)文法構(gòu)造出LR(0)自動機，通過自動機的運行進行語法分析。假設(shè)文法符號串γ使LR(0)自動機從開始狀態(tài)0運行到某個狀態(tài)j，LR(0)自動機按照如下方式?jīng)Q定移入或歸約：如果下一個輸入符號為a，且j上有a的轉(zhuǎn)換，就移入a否則就歸約，狀態(tài)j中的項會告訴我們使用那個產(chǎn)生式進行歸約86LR(0)運行語法分析示例87棧中只保留了狀態(tài)，文法符號可以從相應(yīng)的狀態(tài)中獲取LR語法分析算法框架一個輸入、一個輸出、一個棧、一個驅(qū)動程序和一個語法分析表語法分析表包括ACTION和GOTO兩個部分。棧中存放狀態(tài)序列s0…sm,sm在棧頂，在SLR中，這些狀態(tài)就是LR(0)自動機中的狀態(tài)88LR語法分析表由語法分析動作函數(shù)ACTION和轉(zhuǎn)換函數(shù)GOTO組成，幫助確定移入或歸約動作及狀態(tài)轉(zhuǎn)換：ACTION函數(shù)：狀態(tài)i和終結(jié)符號a（或$）決定四種動作形式移入j，j是一個狀態(tài)。語法分析器采取的動作是把輸入符號a移入棧中，實際上是移入狀態(tài)j。因為j可以和a相關(guān)聯(lián)。歸約A→β

，語法分析器的動作是把棧頂?shù)摩職w約為產(chǎn)生式頭A接受報錯GOTO函數(shù)如果GOTO(Ii,X)=Ij，即GOTO把狀態(tài)i和一個非終結(jié)符號A映射到狀態(tài)j。89LR語法分析器的格局在分析過程中的中間分析狀態(tài)，稱為格局(SoS1...Sm,aiai+1...an$)

stack RestofInput對應(yīng)于句型X1X2…Xmaiai+1…an因為棧中存放的是狀態(tài)，因此需要從狀態(tài)中復(fù)原出與其相關(guān)聯(lián)的的文法符號。Xi是Si所關(guān)聯(lián)的文法符號。

S0不代表任何文法符號。90LR語法分析程序行為基于某個格局，語法分析器根據(jù)當前輸入符號ai和棧頂?shù)臓顟B(tài)sm，然后在分析動作表中查詢條目ACTION[sm，ai]，做完一個動作，分別進入以下格局：如果ACTION[sm，ai]=移入s，將狀態(tài)s移入棧中，進入格局(sos1...sms,ai+1...an$)；如果ACTION[sm，ai]=歸約A→β，執(zhí)行歸約動作，進入格局(sos1...sm-rs,ai...an$)，r是β的長度，s=GOTO[sm-r,A]；如果ACTION[sm，ai]=接受，那么語法分析順利結(jié)束；如果ACTION[sm，ai]=報錯，那么發(fā)現(xiàn)語法錯誤，并進行出錯處理。91LR語法分析算法輸入：一個輸入串w和一個LR語法分析表輸出：如果w在L(G)中，則輸出w的自底向上語法分析過程中的歸約步驟，否則報錯。棧中初始狀態(tài)：S0，輸入緩沖區(qū)：w$92LR分析示例si表示移入并將狀態(tài)i壓入棧rj表示按照編號為j的產(chǎn)生式進行歸約Acc表示接受空白表示報錯93SLR分析表構(gòu)造以LR(0)項和LR(0)自動機為基礎(chǔ)，基于文法G的規(guī)范項集族C和GOTO函數(shù)就可以構(gòu)造出SLR的語法分析表。94SLR分析表構(gòu)造算法輸入：一個增廣文法G’輸出：G’的SLR語法分析表函數(shù)ACTION和GOTO方法： 1）構(gòu)造G’LR(0)項集規(guī)范族C={I0,I1,…In,}2）對于狀態(tài)i中的項：[A→α·aβ]且GOTO[Ii,a]=Ij,那么ACTION[i,a]=移入j。這里的a是終結(jié)符號[A→α·]，那么對于FOLLOW(A)中的所有a，ACTION[i,a]=歸約A→α[S’→S·],那么ACTION[i,$]=接受3）狀態(tài)i對于非終結(jié)符號A的轉(zhuǎn)換規(guī)則：如果GOTO[Ii,A]=Ij，那么GOTO[i,A]=j

4)規(guī)則2)和3)沒有定義的所有條目設(shè)置為“報錯”95SLR（1）根據(jù)上一算法構(gòu)造的語法分析表，若表中各位置沒有多個條目，則稱為文法G的SLR(1)分析表。使用該分析表的分析器，稱為G的SLR(1)語法分析器。G稱為SLR(1)文法若表中某位置存在多個條目（多個可選的動作，沖突），則該文法是非SLR(1)文法96構(gòu)造示例97LR(0)自動機進行語法分析的基本原理語法分析的棧中內(nèi)容一定是某個最右句型的前綴。但是不會跨過句柄。可行前綴：可以出現(xiàn)在一個移入-歸約語法分析器的棧中的最右句型前綴。LR(0)自動機能夠識別可行前綴。如果存在一個推導(dǎo)過程SαAwαβ1β2w，項A→β1·β2是可行前綴αβ1的有效項。有效項的意義：語法分析棧中發(fā)現(xiàn)αβ1時，如果β2≠

，表示句柄還沒有全部移入到棧，因此選擇移入。如果β2=，那么β1就是句柄，可以歸約到A。同一個可行前綴可能會有不同的有效項，要求做不同的事情，這樣的沖突需要向前看輸入符號來解決。后面會有更一般的解決方案。LR語法分析理論的核心思想：如果我們在某個文法的LR(0)自動機中從初始狀態(tài)開始沿著標號為某個可行前綴的路徑到達一個狀態(tài)，那么該狀態(tài)對應(yīng)的項集就是的有效項集。98可行前綴示例可行前綴E+T＊對應(yīng)的有效項：T→T＊·FF→·(E)F→·id分析表沖突狀態(tài)2，輸入符號為=時，選擇移入還是歸約……沒有參考更多的上下文信息為什么歸約出錯？Follow集合？100更強大的LR語法分析器規(guī)范LR方法。充分利用向前看符號。這種方法是用了一個更大的項集，稱為LR(1)項集向前看LR，又稱LALR101LR(1)項在SLR中，如果項集Ii中包含項[A→α·]，且當前符號a在FOLLOW(A)中，那么就可以按照A→α進行歸約。有時，在任何最右句型中a都不可能跟在βA之后，這時輸入為a不能按照A→α進行歸約。如上面的示例二。FOLLOW集提供的可歸約條件過松每個狀態(tài)能否明確指出哪些輸入符號可以跟在句柄α后面，從而使句柄α可能被歸約為A。102LR(1)項(續(xù))形式如[A→α·β,a]，其中A→αβ是一條產(chǎn)生式，a是一個終結(jié)符號或者$符a是向前看符號，長度為1。其意義是若棧頂狀態(tài)中存在LR(1)項[A→α·,a]，在輸入符號為a時才會進行歸約a的集合總是FOLLOW(A)的子集β≠ε時，a沒有任何作用a指出能夠進行歸約的準確判斷103向前看符號與確定歸約有關(guān)LR(1)項(續(xù))從可行前綴和有效項的角度看：LR(1)項[A→α·β,a]對于一個可行前綴δα有效的條件是存在一個推導(dǎo)SδAwδαβw，其中a∈First(w)。當w為ε，a=$104LR(1)項集構(gòu)造過程類似于LR(0)項集構(gòu)造多了一個向前看符號分量的計算CLOSUREGOTO105LR(1)項集閉包CLOSURECLOSURE(I)=IU{[B→.γ，b]|[A

→α·Bβ,a]∈CLOSURE(I)，b∈First(βa)，且B→γ為文法規(guī)則}106LR(1)項集GOTO函數(shù)107LR(1)項集規(guī)范族構(gòu)造算法108LR(1)項集規(guī)范組構(gòu)造示例109規(guī)范LR(1)語法分析表輸入：一個增廣文法G’輸出：G’的規(guī)范LR語法分析表函數(shù)ACTION和GOTO方法： 1）構(gòu)造G’LR(0)項集規(guī)范族C={I0,I1,…In}2）對于狀態(tài)i中的項：[A→α·aβ，b]且GOTO[Ii,a]=Ij,那么ACTION[i,a]=移入j[A→α·，a]，且A≠S’，ACTION[i,a]=歸約A→α[S’→S·,$],那么ACTION[i,$]=接受3）狀態(tài)i對于非終結(jié)符號A的轉(zhuǎn)換規(guī)則：如果GOTO[Ii,A]=Ij，那么GOTO[i,A]=j

4)規(guī)則2)和3)沒有定義的所有條目設(shè)置為“報錯”110語法分析表示例111LR(1)文法通過上述算法構(gòu)造的LR(1)語法分析表中若不存在沖突條目，則給定的文法稱為LR(1)文法。112LR(1)語法分析器狀態(tài)再觀察在(3,6)(4,7)(8,9)中，項的第一個分量是一樣的，實質(zhì)上它們來自于同樣的LR(0)狀態(tài)113LALR分析LR(1)語法分析器的狀態(tài)過多但LR(1)的分析能力強于SLR(1)LALR分析狀態(tài)和SLR一樣多能力又比SLR稍微強一些114項集合并將LR(1)項集中具有相同核心的項集合并為一個項集項集核心是指LR(1)項集中第一個分量的集合被合并項集的GOTO目標顯然也可以被合并I3={[C→c·C,c/d],[C→·cC,c/d],[C→·d,c/d]}I6={[C→c·C,$],[C→·cC,$],[C→·d,$]}合并后：I36={[C→c·C,c/d/$],[C→·cC,c/d/$],[C→·d,c/d]/$}GOTO(I3,C)和GOTO(I6,C)顯然也可以合并……115合并可能產(chǎn)生的沖突合并引起的沖突是指：本來的LR(1)項集沒有沖突，而合并具有相同核心的項集后有沖突。不可能引入歸約-移入型沖突。假定合并后有移入_歸約沖突，就是說：有項[A→α·,a]和項[B→β·aγ,b]。顯然，原來的項集中都有[B→β·aγ,?]。而[A→α·,a]必然也在某個原來的項集中。這樣，合并前的LR(1)項集已經(jīng)存在移入-歸約沖突。但是可能引起歸約_歸約沖突。116歸約-歸約沖突語言{acd，ace，bcd，bce}可行前綴ac的有效項集{[Ac·,d],[Bc·,e]}可行前綴bc的有效項集{[Ac·,e],[Bc·,d]}合并之后的項集為{[Ac·,d/e],[Bc·,d/e]}當輸入為d或e時，用哪個歸約？從引起新的沖突可以看出：LALR的分析能力比規(guī)范LR弱一些117LALR語法分析表構(gòu)造方法最樸素的方法高效的方法118LALR語法分析表構(gòu)造方法–樸素的方法基本思想：先構(gòu)造出LR(1)項集，如果沒有出現(xiàn)沖突，就將先通核心的項集進行合并。然后根據(jù)合并后得到的項集規(guī)范組構(gòu)造語法分析表。輸入：一個增廣文法G’輸出：文法G’的LALR語法分析表方法：得到的分析表成為LALR語法分析表。構(gòu)造得到LR(1)項集族C={I0,I1,…,In}。對于LR(1)項集中的每個核心，找出所有具有這個核心的項集，并把這些項集替換為它們的并集令C’={J0,J1,…,Jn}是得到的LR(1)項集族。按照LR(1)分析表的構(gòu)造方法得到ACTION表。（注意檢查若存在沖突，則這個文法不是LALR的）GOTO表的構(gòu)造：若J是一個或者多個LR(1)項集的并集，即J=I1∪I2

∪…∪IK，令K是所有和GOTO(I1,X)具有相同核心的項集的并集，那么GOTO(J,X)=K。119LALR分析表構(gòu)造示例120LALR分析器和LR分析器若構(gòu)造出的LALR分析表中沒有沖突，則可以用LALR分析表進行語法分析。如果是正確的輸入串LALR和LR分析器執(zhí)行完全相同的移入和歸約動作序列，只是棧中的狀態(tài)名字有所不同如果是錯誤的輸入串則LALR分析器可能會比LR分析器晚一點報錯LALR分析器不會在LR分析器報錯后再移入任何符號，但是可能會繼續(xù)執(zhí)行一些歸約。121LALR技術(shù)本質(zhì)對LR(1)項集規(guī)范族中所謂的同心項集進行合并，從而使得分析表既保持了LR(1)項中向前看符號的信息，又使狀態(tài)數(shù)減少到與SLR分析表的一樣多。122二義性文法的自底向上分析二義性文法都不是LR的二義性文法卻有其存在的必要對于某些二義性文法可以通過消除二義性規(guī)則來保證每個句子只有一棵語法分析樹且可以在LR分析器中實現(xiàn)這個規(guī)則優(yōu)先級/結(jié)合性消除沖突二義性文法的優(yōu)點：容易修改算符的優(yōu)先級和結(jié)合性。簡潔：較少的非終結(jié)文法符號高效：不需要處理ET這樣的歸約。二義性表達式文法的LR(0)項集I7，I8中有沖突，在輸入+或*時，不能確定是歸約還是移入。且不可能通過向前看符號解決基于優(yōu)先級解決沖突如果*的優(yōu)先級大于+，且+是左結(jié)合的下一個符號為+時，我們應(yīng)該將E+E歸約為E下一個符號為*時，我們應(yīng)該移入*，期待移入下一個符號。解決沖突之后的SLR(1)分析表對于狀態(tài)7，輸入+時歸約*時移入對于狀態(tài)8執(zhí)行歸約懸空else的二義性棧中內(nèi)容ifexprthenstmt,是輸入else，還是歸約？答案是移入文法比較129語法錯誤的處理錯誤難以避免編譯器需要具有處理錯誤的能力程序中可能存在不同層次的錯誤詞法錯誤語法錯誤語義錯誤邏輯錯誤語法錯誤相同容易發(fā)現(xiàn)，語義和邏輯錯誤較難精確的檢測到語法分析器中錯誤處理程序的設(shè)計目標：清晰準確地報告出現(xiàn)錯誤，并指出錯誤的位置能從當前錯誤中恢復(fù)，以繼續(xù)檢測后面的錯誤盡可能減少處理正確程序的開銷預(yù)測分析中的錯誤恢復(fù)錯誤恢復(fù)當預(yù)測分析器報錯時，表示輸入的串不是句子。對于使用者而言，希望預(yù)測分析器能夠進行恢復(fù)處理后繼續(xù)語法分析過程，以便在一次分析中找到更多的語法錯誤。但是有可能恢復(fù)得并不成功，之后找到的語法錯誤有可能是假的。進行錯誤恢復(fù)時可用的信息：棧里面的符號，待分析的符號兩類錯誤恢復(fù)方法：恐慌模式短語層次的恢復(fù)恐慌模式基本思想語法分析器忽略輸入中的一些符號，直到出現(xiàn)由設(shè)計者選定的某個同步詞法單元；解釋：語法分析過程總是試圖在輸入的前綴中找到和某個非終結(jié)符號對應(yīng)的串