第05章語(yǔ)法分析-自底向上分析

1S.PO.P語(yǔ)義分析及生成中間代碼程序代碼生成程序代碼優(yōu)化程序語(yǔ)法分析程序詞法分析程序錯(cuò)誤處理符號(hào)表管理2第五章語(yǔ)法分析－自底向上分析教學(xué)目標(biāo)要求明確自底向上分析方法的一般過程。掌握LR分析方法。掌握構(gòu)造LR(0)、SLR(1)、LR(1)、LALR(1)分析表的方法，會(huì)使用LR分析法分析句子。35.1規(guī)范推導(dǎo)、規(guī)范句型和規(guī)范歸約5.2自底向上分析方法的一般過程5.3LR分析方法5.4LR(0)分析器5.5SLR(1)分析器5.6LR(1)分析器5.7LALR(1)分析器5.8語(yǔ)法分析程序的自動(dòng)生成工具－YACC教學(xué)內(nèi)容4任務(wù)：按照程序語(yǔ)言的語(yǔ)法規(guī)則，從由詞法分析輸出的源程序符號(hào)串中識(shí)別出各類語(yǔ)法成分，同時(shí)進(jìn)行語(yǔ)法檢查，為語(yǔ)義分析和代碼生成作準(zhǔn)備。語(yǔ)法分析的任務(wù)詞法分析器語(yǔ)法分析器單詞符號(hào)語(yǔ)法樹源程序輸入：Token序列輸出：語(yǔ)法成分及組成表現(xiàn)形式：語(yǔ)法樹錯(cuò)誤報(bào)告出錯(cuò)處理：定位、續(xù)編譯5語(yǔ)法分析的任務(wù)

遞歸子程序法自頂向下

LL(1)分析法TopDown

算符優(yōu)先分析法自底向上

LR(0)、SLR(1)[LR(1)、LALR]BottomUp文法產(chǎn)生語(yǔ)言自動(dòng)機(jī)識(shí)別語(yǔ)言6第5章語(yǔ)法分析——自底向上分析

在自底向上的分析方法中，分析過程從輸入符號(hào)串開始，通過反復(fù)查找當(dāng)前句型的句柄，并使用規(guī)則，將找到的句柄歸約成相應(yīng)的非終結(jié)符號(hào)，直到歸約到開始符號(hào)，從而為輸入符號(hào)串構(gòu)造一棵分析樹。開始符號(hào)字符串7概念回顧推導(dǎo)、歸約最右推導(dǎo)、最左歸約最左推導(dǎo)、最右歸約句型、句子規(guī)范句型短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄8概念回顧推導(dǎo)如：S=>AB=>=>AaBb=>=>aabb歸約如：aabb=>=>AaBb=>=>AB=>S最右推導(dǎo)與最左歸約如：S=>AB=>ABb=>Abb=>Aabb=>aabb最左推導(dǎo)與最右歸約如：S=>AB=>AaB=>aaB=>aaBb=>aabb文法：S::=ABA::=Aa|aB::=Bb|b9概念回顧句型從識(shí)別符號(hào)推導(dǎo)0步或多步產(chǎn)生的結(jié)果可由非終結(jié)符和終結(jié)符組成句子是特殊的句型完全由終結(jié)符號(hào)組成規(guī)范句型每個(gè)句子都有規(guī)范推導(dǎo)10概念回顧短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄例句型：Aabb文法：S::=ABA::=Aa|aB::=Bb|bSABAaBbb短語(yǔ)：Aabb、Aa、bb、b簡(jiǎn)單短語(yǔ)：Aa、b句柄：Aa115.1規(guī)范推導(dǎo)、規(guī)范句型和規(guī)范歸約

規(guī)范推導(dǎo)：最右推導(dǎo)規(guī)范句型：通過規(guī)范推導(dǎo)能夠得到的句型規(guī)范歸約：最左歸約文法S::=ABA::=Aa|aB::=Bb|b以下哪些句型是規(guī)范句型？aabb、Ab、Aab、aBb、Abb、AaBb125.1規(guī)范推導(dǎo)、規(guī)范句型和規(guī)范歸約例5.1，有文法G[S]：

S::=aAcBeA::=bA::=AbB::=d試分析符號(hào)串a(chǎn)bbcde是否為該文法的句子。

方法一：推導(dǎo)首先，我們從文法的開始符號(hào)進(jìn)行規(guī)范推導(dǎo)，依次使用1、4、3、2規(guī)則，就可得到符號(hào)串a(chǎn)bbcde。規(guī)范推導(dǎo)過程如下：S=>aAcBe=>aAcde=>aAbcde=>abbcde13方法二：歸約從符號(hào)串開始，向上歸約，如果最終能夠規(guī)約到文法的開始符號(hào)S，則同樣可以說明該輸入符號(hào)串是這個(gè)文法的句子。其歸約過程如圖5.1所示。ScBcAaAbdbScBcAaAbdScBcAadScBcAaS(a)b歸約為A(b)Ab歸約為A(c)d歸約為B(d)aAcBe歸約為S(e)圖5.1歸約過程

145.2自底向上分析方法的一般過程

基本思想從輸入符號(hào)串開始，通過重復(fù)查找當(dāng)前句型的“可歸約串”并利用有關(guān)規(guī)則進(jìn)行規(guī)約若能規(guī)約為文法的識(shí)別符號(hào),則表示分析成功,輸入符號(hào)串是文法的合法句子,否則有語(yǔ)法錯(cuò)誤.15【例】G[S]:SaAcBeAbAAb Bd分析句子abbcde#16文法G[S]：

(1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→dabbcde步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#abbcde#移進(jìn)2）#abbcde#移進(jìn)A3）#abbcde#歸約(A→b)4）#aAbcde#移進(jìn)A5）#aAbcde#歸約(A→Ab)6）#aAcde#移進(jìn)7）#aAcde#移進(jìn)B8）#aAcde#歸約(B→d)9）#aAcBe#移進(jìn)11）#S#接受S10）#aAcBe#歸約SaAcBeaAcdeaAbcdeabbcde17關(guān)鍵：找出當(dāng)前句型的“可歸約串”

從自底向上分析的一般過程可看出，如何尋找或確定一個(gè)句型的句柄，是構(gòu)造一個(gè)自左向右掃描、自底向上分析方法必須要解決的一個(gè)關(guān)鍵問題。185.3LR分析方法什么是LR(k)分析:

L：從左到右掃描

R：最右推導(dǎo)的逆過程（最左歸約）

k：是指為了作出分析決定而向前看的輸入符號(hào)的個(gè)數(shù)是一種規(guī)范歸約過程LR(k)分析技術(shù)Knuth于1965年首先提出19Knuth/~knuth/《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)第1卷基本算法》

98元《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)第2卷半數(shù)值算法》98元《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)第3卷排序與查找》98元205.3.1LR分析器邏輯結(jié)構(gòu)LR分析器有一個(gè)給定的輸入符號(hào)串，一個(gè)分析棧和一個(gè)有窮的控制系統(tǒng)。#…

…a2a1輸入符號(hào)串:分析棧:S0#......SnA有窮的控制系統(tǒng)：分析表(動(dòng)作、轉(zhuǎn)換)總控程序215.3.2LR分析表的構(gòu)成動(dòng)作部分,ACTION表示當(dāng)前狀態(tài)面臨輸入符號(hào)時(shí)應(yīng)采取的動(dòng)作;狀態(tài)轉(zhuǎn)換部分，GOTO表示當(dāng)前狀態(tài)面臨文法符號(hào)時(shí)應(yīng)轉(zhuǎn)向的下一個(gè)狀態(tài);。分析器的各個(gè)狀態(tài)文法的終結(jié)符號(hào)及右界符#文法的非終結(jié)符號(hào)225.3.2LR分析表的構(gòu)成分析表的動(dòng)作有下列四種：移進(jìn)(Sn)：將輸入符號(hào)aj移進(jìn)符號(hào)棧，將狀態(tài)n移進(jìn)狀態(tài)棧，輸入指針指向下一個(gè)輸入符號(hào)。歸約(R)：當(dāng)棧頂形成句柄時(shí)，按照相應(yīng)的產(chǎn)生式U→W進(jìn)行歸約。若產(chǎn)生式右部W的長(zhǎng)度為n，則將符號(hào)棧棧頂n個(gè)符號(hào)和狀態(tài)棧棧頂n個(gè)狀態(tài)出棧，然后將歸約后的文法符號(hào)U移入符號(hào)棧，并根據(jù)此時(shí)狀態(tài)棧頂?shù)臓顟B(tài)Si及符號(hào)棧頂?shù)姆?hào)U，查GOTO表，將GOTO[Si，U]移入狀態(tài)棧。235.3.2LR分析表的構(gòu)成分析表的動(dòng)作有下列四種：（續(xù)）接受(A)：當(dāng)輸入符號(hào)串到達(dá)右界符#時(shí)，且符號(hào)棧只有文法的開始符號(hào)時(shí)，則分析成功結(jié)束，接受輸入符號(hào)串并結(jié)束分析。報(bào)錯(cuò)(E)：在狀態(tài)棧的棧頂狀態(tài)為Si時(shí)，如果輸入符號(hào)為不應(yīng)該遇到的符號(hào)時(shí)，即ACTION[Si，aj]=空白，則報(bào)錯(cuò)，說明輸入符號(hào)串有語(yǔ)法錯(cuò)誤。24例：步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#abbcde#移進(jìn)2）#abbcde#移進(jìn)4）#aAbcde#移進(jìn)6）#aAcde#移進(jìn)7）#aAcde#移進(jìn)9）#aAcBe#移進(jìn)11）#S#接受3）#abbcde#歸約(A→b)5）#aAbcde#歸約(A→Ab)8）#aAcde#歸約(B→d)10）#aAcBe#歸約25LR分析器的關(guān)鍵就是構(gòu)造分析表。表5.2給出了文法G：

0)S→A，1)A→(A)，2)A→a的分析表。表5.3LR分析表265.3.3LR分析過程分析開始時(shí)，棧內(nèi)的初始狀態(tài)為0，符號(hào)棧為#。當(dāng)狀態(tài)棧頂為p，當(dāng)前輸入指針指向的符號(hào)是a時(shí)，查分析動(dòng)作表p行、a列。如果得到的動(dòng)作指示ACTION[p,a]是移進(jìn)Si，則將a壓入符號(hào)棧，將狀態(tài)i壓入狀態(tài)棧，然后將輸入指針指向輸入符號(hào)串的下一個(gè)符號(hào)；如果得到的動(dòng)作指示是歸約Ri，且歸約產(chǎn)生式為B→β，則從符號(hào)棧內(nèi)彈出|β|個(gè)符號(hào)，從狀態(tài)棧內(nèi)彈出|β|個(gè)狀態(tài)，假設(shè)此時(shí)出棧后的狀態(tài)棧棧頂為p，查狀態(tài)轉(zhuǎn)換表的p行、B列，得到下一個(gè)狀態(tài)GOTO[p,B]=q，并將該后繼狀態(tài)q壓入狀態(tài)棧；如果得到的動(dòng)作指示是接受，則接受輸入的符號(hào)串，分析成功結(jié)束；27開始初始狀態(tài)0和#入棧讀符號(hào)根據(jù)棧頂狀態(tài)和輸入符號(hào)查分析動(dòng)作表歸約?移進(jìn)?接受?查狀態(tài)轉(zhuǎn)換表新狀態(tài)入狀態(tài)棧

按產(chǎn)生式i歸約

根據(jù)產(chǎn)生式i的右部符號(hào)的個(gè)數(shù)，符號(hào)棧和狀態(tài)棧相應(yīng)元素出棧

產(chǎn)生式i的左部符號(hào)入棧

輸入符號(hào)入符號(hào)棧

狀態(tài)i入狀態(tài)棧讀符號(hào)分析結(jié)束錯(cuò)誤YYYNNN28例5.2，利用表5.3分析表分析符號(hào)串(a)。解：根據(jù)圖5.3所示的分析流程，表5.4列出了符號(hào)串(a)的整個(gè)分析過程。S2(a)##01S3a)##(0224R2)##(a0233S5)##(A02441R1##(A)02455ACCEPT##A016295.4LR(0)分析方法拓廣文法：使識(shí)別符號(hào)唯一例5.3,對(duì)文法G∶E→T|E+T|E－TT→i|(E)進(jìn)行拓廣。解：引入一個(gè)新的開始符號(hào)S，使得文法的開始符號(hào)所在的規(guī)則唯一。G[S]：S→EE→T|E+T|E－TT→i|(E)305.4.1活前綴和可歸前綴LR(k)分析法通過活前綴來幫助確定句柄前綴：句型的任意首部如：abc的前綴有ε,a,b,ab,abc規(guī)范句型：通過規(guī)范推導(dǎo)（規(guī)約）得到的句型活前綴：規(guī)范句型中不含句柄右邊任何符號(hào)的前綴可歸前綴：含有句柄的活前綴315.4.1活前綴和可歸前綴對(duì)于一個(gè)規(guī)范句型來說，其活前綴定義如下：設(shè)λβt是一個(gè)規(guī)范句型，即λβt是能用最右推導(dǎo)得到的句型，其中β表示句柄，t∈Vt*，如果λβ=u1u2…ur，那么稱符號(hào)串u1u2…ui(其中1≤i≤r)是句型λβt的活前綴。含有句柄的活前綴u1u2…ur稱為可歸前綴。對(duì)一個(gè)規(guī)范句型來說，活前綴可有多個(gè)，可歸前綴只有一個(gè)。32例：文法G∶E→T|E+T|E-TT→i|(E)，找規(guī)范句型E+(i-i)的活前綴和可歸前綴。ET+E）E（T－ETiiE+(i-i)的語(yǔ)法樹：活前綴為：E，E+，E+(，E+(i，可歸前綴：E+(i33課堂練習(xí)文法G[E]：

E→E+T|TT→T*F|FF→(E)|i1、拓廣文法？2、找規(guī)范句型:E+i*i的活前綴和可歸前綴？拓廣文法G[S]：

S→EE→E+T|TT→T*F|FF→(E)|i活前綴為：E，E+，E+i可歸前綴：E+i34課堂練習(xí)文法G[S]：S→A

A→(A)A→a找規(guī)范句型:（a）的活前綴和可歸前綴？活前綴為：（，（a可歸前綴：（aSA（A）a語(yǔ)法樹：35S2(a)##01S3a)##(0224R2)##(a0233S5)##(A02441R1##(A)02455ACCEPT##A016均為活前綴文法G[S]：S→A，A→(A)，A→a36LR分析器的工作過程逐步產(chǎn)生文法的規(guī)范句型活前綴的過程當(dāng)棧頂形成句柄時(shí)，立即進(jìn)行歸約375.4.2LR(0)項(xiàng)目1、項(xiàng)目的定義對(duì)某個(gè)文法G來說，如果A→α1α2為G的一條規(guī)則，那么，對(duì)規(guī)則的右部加上一個(gè)圓點(diǎn)，就成為一個(gè)項(xiàng)目。其形式為：A→α1·α2圓點(diǎn)是表示項(xiàng)目的一種標(biāo)記，也就是說，如果一條規(guī)則的右部標(biāo)有圓點(diǎn)，那么它就是項(xiàng)目。因?yàn)閳A點(diǎn)的位置不同，一條規(guī)則可以有幾個(gè)項(xiàng)目。項(xiàng)目的直觀意義:在分過程中的某一時(shí)刻已經(jīng)規(guī)約的部分和等待規(guī)約部分385.4.2LR(0)項(xiàng)目【例】

文法G[S]：S→aS|b寫出其所有的LR(0)項(xiàng)目。S→·aSS→a·SS→aS·

S→·b

S→b·395.4.2LR(0)項(xiàng)目【例】有文法S→E，E→T|E+T|E-T，T→i|(E)，規(guī)則S→E，有下面兩個(gè)項(xiàng)目：

S→·E，S→E·規(guī)則E→E－T，有下面四個(gè)項(xiàng)目∶E→·E－T，E→E·－T，E→E－·T，E→E－T·

一個(gè)產(chǎn)生式對(duì)應(yīng)的項(xiàng)目個(gè)數(shù)是右部符號(hào)長(zhǎng)度加1產(chǎn)生式A→ε的項(xiàng)目個(gè)數(shù)只有一個(gè)，即A→·

40根據(jù)項(xiàng)目中點(diǎn)的位置和后繼符號(hào)，項(xiàng)目分為四類：①移進(jìn)項(xiàng)目：E→E·－T圓點(diǎn)后面是終結(jié)符，表示棧內(nèi)是句柄的一部分，期待從輸入串中移進(jìn)一個(gè)符號(hào)，以形成句柄。②待約項(xiàng)目：E→E－·T圓點(diǎn)后面是非終結(jié)符的項(xiàng)目，表示棧內(nèi)是句柄的一部分，為了形成句柄，期待從剩余的輸入串中進(jìn)行歸約而得到Ｂ，然后才能繼續(xù)分析A的右部。41③歸約項(xiàng)目：E→E－T·④接受項(xiàng)目：S→E·特殊的歸約項(xiàng)目，使用產(chǎn)生式S’→α進(jìn)行歸約，表示整個(gè)句子已經(jīng)分析完畢，分析成功，也即輸入串為該文法的句子。圓點(diǎn)在最后，表示棧頂?shù)牟糠謨?nèi)容已構(gòu)成所期望的句柄，應(yīng)使用產(chǎn)生式A→α進(jìn)行歸約。422、項(xiàng)目有效性一個(gè)項(xiàng)目A→α1·α2對(duì)于某個(gè)活前綴λα1是有效的，當(dāng)且僅當(dāng)存在某個(gè)最右推導(dǎo)。

S|*=>λAt|=>

λα1·α2t

，其中t是終結(jié)符號(hào)串。43活前綴與句柄的關(guān)系①活前綴已含有句柄的全部符號(hào)表示符號(hào)棧頂已形成句柄，可以歸約例：產(chǎn)生式：A→α，活前綴：λα，項(xiàng)目A→α·

對(duì)活前綴λα有效。當(dāng)一個(gè)點(diǎn)在最后的項(xiàng)目對(duì)活前綴有效時(shí)，則可以進(jìn)行歸約，所以把點(diǎn)在最后的項(xiàng)目稱為歸約項(xiàng)目。44活前綴與句柄的關(guān)系②活前綴只含有句柄的部分符號(hào)正期待從剩余輸入串中看到句柄的其余符號(hào)例：產(chǎn)生式：A→α１α２，活前綴：λα１，項(xiàng)目A→α１·α２對(duì)活前綴λα１有效。45活前綴與句柄的關(guān)系③活前綴不含有句柄的任何符號(hào)需將余流的輸入符號(hào)移進(jìn)例：產(chǎn)生式：A→α，活前綴：λ，項(xiàng)目A→·α

對(duì)活前綴λ有效。一般來說，活前綴與有效項(xiàng)目是多對(duì)多關(guān)系。46例5.5，有文法S→E，E→T|E+T|E-T，T→i|(E)，列出該文法的所有項(xiàng)目，并找出對(duì)活前綴E－有效的項(xiàng)目。解：首先列出每條規(guī)則對(duì)應(yīng)的多個(gè)項(xiàng)目：S→E，有項(xiàng)目S→·E，S→E·E→T，有項(xiàng)目E→·T，E→T·E→E+T，有項(xiàng)目E→·E+T，E→E·+T，E→E+·T，E→E+T·E→E-T，有項(xiàng)目E→·E-T，E→E·-T，E→E-·T，E→E-T·T→i，有項(xiàng)目Ｔ→·i，Ｔ→i·T→(E)，有項(xiàng)目T→·(E)，T→(·E)，T→(E·)，T→(E)·

47例5.5，有文法S→E，E→T|E+T|E-T，T→i|(E)，列出該文法的所有項(xiàng)目，并找出對(duì)活前綴E－有效的項(xiàng)目。對(duì)活前綴E－有效的項(xiàng)目：E→E－·T，T→·i和T→·(E)S=>E=>E－TS=>E=>E－T=>E－iS=>E=>E－T=>E－(E)485.4.3構(gòu)造識(shí)別活前綴的有窮自動(dòng)機(jī)

回顧：有窮自動(dòng)機(jī)——一種識(shí)別裝置兩種：DFA－－確定的有窮自動(dòng)機(jī)NFA－－不確定的有窮自動(dòng)機(jī)0Ｓ13104

Ｚ151識(shí)別1(0|1)*101的NFA49正規(guī)文法NFA正規(guī)式654312DFA最小化8750有窮自動(dòng)機(jī)的輸入字符：終結(jié)符和非終結(jié)符狀態(tài)轉(zhuǎn)換：每把一個(gè)符號(hào)進(jìn)棧，就看成識(shí)別過了該符號(hào)，進(jìn)行狀態(tài)轉(zhuǎn)換。因?yàn)長(zhǎng)R分析時(shí)棧中始終保持是活前綴，所以有窮自動(dòng)機(jī)識(shí)別過的符號(hào)串也是活前綴。終態(tài)：當(dāng)識(shí)別到可歸約前綴（表明在棧中形成句柄），認(rèn)為到達(dá)了識(shí)別句柄的終態(tài)，執(zhí)行歸約5.4.3構(gòu)造識(shí)別活前綴的有窮自動(dòng)機(jī)515.4.3構(gòu)造識(shí)別活前綴的有窮自動(dòng)機(jī)有兩種方法：（1）求出文法的所有項(xiàng)目，按一定規(guī)則構(gòu)造NFA再確定化為DFA－－工作量大，不適用（2）直接構(gòu)造DFA－－分析DFA狀態(tài)的項(xiàng)目集之間、項(xiàng)目集內(nèi)的項(xiàng)目之間的規(guī)律性直接構(gòu)造出DFA（重點(diǎn)掌握）52直接構(gòu)造DFA若項(xiàng)目集中有Y→·X，另一項(xiàng)目集中有Y→X·，則這兩個(gè)項(xiàng)目集之間必有一條X弧。將一個(gè)活前綴的可能的無(wú)窮集對(duì)應(yīng)到一個(gè)有窮的有效項(xiàng)目集上。先給出兩個(gè)定義：項(xiàng)目集的閉包運(yùn)算狀態(tài)轉(zhuǎn)移函數(shù)GO比較（P43）：狀態(tài)集Ｐ的ε閉包狀態(tài)集Ｐ的α弧轉(zhuǎn)換集531、項(xiàng)目集的閉包運(yùn)算設(shè)I為一項(xiàng)目集，I的閉包運(yùn)算CLOSURE(I)定義如下：I中的每一個(gè)項(xiàng)目都屬于CLOSURE(I)。如項(xiàng)目A→α1·Xα2屬于CLOSURE(I)，且X為非終結(jié)符號(hào)，則將形式為X→·λ的項(xiàng)目添加到CLOSURE(I)中。重復(fù)(1)和(2)，直到CLOSURE(I)封閉為止。54例5.6，有文法：E’→E，E→E+T，E→T，T→T*F，T→F，F(xiàn)→(E)，F(xiàn)→i，設(shè)項(xiàng)目集I={E’→·E}，求CLOSURE(I)。解：根據(jù)閉包運(yùn)算的第1條，CLOSURE(I)={E’→·E}根據(jù)第2條，E→·E+T和E→·T，加進(jìn)CLOSURE(I)中：CLOSURE(I)={E’→·E，E→·E+T，E→·T}根據(jù)第3條，T→·T*F和T→·F，加進(jìn)CLOSURE(I)中：CLOSURE(I)={E’→·E，E→·E+T，E→·T，T→·T*F，T→·F}將F→·(E)和F→·i，加進(jìn)CLOSURE(I)中：CLOSURE(I)={E’→·E，E→·E+T，E→·T，T→·T*F，T→·F，F(xiàn)→·(E)，F(xiàn)→·i}至此，CLOSURE(I)封閉。55文法：

S'→S S→aS S→b例：I={S'→·S}closure(I)=？{S'→·S,S→·aS,S→·b}練習(xí)：I={S→a·S}closure(I)=？{S→a·S,S→·aS,S→·b}562、項(xiàng)目集之間的轉(zhuǎn)換函數(shù)GO假設(shè)有一項(xiàng)目為A→α·Xβ，令X是一個(gè)字匯表中的符號(hào)，則對(duì)項(xiàng)目A→α·Xβ進(jìn)行讀X操作，結(jié)果為項(xiàng)目A→αX·β。設(shè)I是一個(gè)項(xiàng)目集,X是任一文法符號(hào)，則項(xiàng)目集之間的轉(zhuǎn)換用GO[I,X]函數(shù)表示，定義為：GO[I,X]=CLOSURE(J)其中J={任何具有[A→αX·β]的項(xiàng)目|[A→α·Xβ]∈I}，即對(duì)項(xiàng)目集I中所有的項(xiàng)目進(jìn)行讀X操作的結(jié)果。572、項(xiàng)目集之間的轉(zhuǎn)換函數(shù)GOCLOSURE(J)為對(duì)J進(jìn)行了閉包運(yùn)算得到的項(xiàng)目集，稱為I的后繼項(xiàng)目集。令狀態(tài)I代表項(xiàng)目集I，狀態(tài)J代表后繼項(xiàng)目集CLOSURE(J)，用狀態(tài)圖表示則為：IJX58例5.7，文法：E’→E，E→E+T，E→T，T→T*F，T→F，F(xiàn)→(E)，F(xiàn)→i，有項(xiàng)目集I={E’→E·，E→E·+T},

求GO[I，+]解：在I中挑出點(diǎn)后是+的項(xiàng)目有：E→E·+T,將點(diǎn)移到+后面得J={E→E+·T}對(duì)J進(jìn)行閉包運(yùn)算得CLOSURE(J)={E→E+·T,T→·F,T→·T*F,F→·(E),F→·i}GO(I,+)={E→E+·T,T→·F,T→·T*F,F→·(E),F→·i}用狀態(tài)圖表示為：+I：E’→E·E→E·+TJ:E→E+·T,T→·FT→·T*F,F→·(E),F→·i59文法：

S'→S S→aS S→b求GO(I,b)=?GO(I,b)=closure({S→b·})={S→b·}求GO(I,a)=?GO(I,a)=closure({S→a·S})={S→a·S,S→·aS,S→·b}例：I={S'→·S,S→·aS,S→·b

}603、舉例說識(shí)別活前綴的有窮自動(dòng)機(jī)的構(gòu)造方法直接構(gòu)造DFA的思想從S‘→·S開始，得到DFA的初態(tài)項(xiàng)目集然后通過狀態(tài)轉(zhuǎn)換函數(shù)GO求其所有的后繼項(xiàng)目集61【例】文法：0)S→A1)A→(A)2)A→a1、構(gòu)造初態(tài)項(xiàng)目集C0C0＝closure（｛S→·A｝）＝｛S→·A，A→·(A)，A→·a｝2、通過狀態(tài)轉(zhuǎn)換函數(shù)GO求其所有的后繼項(xiàng)目集0:

S→·AA→·(A)A→·a1:

S→A·2:

A→(·A)A→·(A)A→·a

3:

A→a·A(a62R1

A→(A)·5GO[4，)]=5A→(A·)4R2

A→a·3GO[2，A]=4GO[2，(]=2GO[2，a]=3A→(·A)A→·(A)A→·a2ACCEPTS→A·1GO[0，A]=1GO[0，(]=2GO[0，a]=3S→·AA→·(A)A→·a0轉(zhuǎn)換函數(shù)項(xiàng)目集狀態(tài)3、繼續(xù)上述后繼項(xiàng)目構(gòu)造過程，直到?jīng)]有新的項(xiàng)目集產(chǎn)生。630:S→·AA→·(A)A→·a1:S→A·2:A→(·A)A→·(A)A→·a

3:A→a·A(a圖5.8識(shí)別活前綴的有窮自動(dòng)機(jī)

4:A→(A·)5:A→(A)·A)(a644、識(shí)別活前綴的有窮自動(dòng)機(jī)構(gòu)造算法給定一文法G，該文法的開始符號(hào)為S。C={C0,C1,…,Cn},其中C0是開始項(xiàng)目集，C稱為L(zhǎng)R(0)項(xiàng)目集規(guī)范族。構(gòu)造DFA的算法：C={closure({S’→·S})};do{for(C中的每個(gè)項(xiàng)目集I和每個(gè)符號(hào)X）

if(GO(I,X)非空,且不在C中)

把GO(I,X)加入C中;}while(C增大)returnC;655.4.4LR(0)分析表的構(gòu)造1)若項(xiàng)目A→α·aβ∈Ci且GO[i，a]=Cj，其中a為終結(jié)符，置ACTION[i，a]=“把狀態(tài)j和符號(hào)a移進(jìn)?！?，簡(jiǎn)記為“Sj”；

2)若項(xiàng)目A→α·∈Ci，則對(duì)于任何輸入符號(hào)a或結(jié)束符#，置ACTION[i，a]=“用產(chǎn)生式A→α進(jìn)行歸約”，簡(jiǎn)記為“Rj”(假定A→α是文法G’的第j條產(chǎn)生式)；

3)若項(xiàng)目S→δ·∈Ci，則置ACTION[i，#]=“接收”，簡(jiǎn)記為‘A’；

4)若GO[i，A]=Cj，A為非終結(jié)符，則置GOTO[i，A]=j；

5)分析表中凡不能用規(guī)則①-④添入信息的單元為空或均置上ERROR，表示有錯(cuò)。66R1

A→(A)·5GO[4，)]=5A→(A·)4R2

A→a·3GO[2，A]=4GO[2，(]=2GO[2，a]=3A→(·A)A→·(A)A→·a2ACCEPTS→A·1GO[0，A]=1GO[0，(]=2GO[0，a]=3S→·AA→·(A)A→·a0轉(zhuǎn)換函數(shù)項(xiàng)目集狀態(tài)（1）若A→α·aβ∈Ci，且GO[i，a]=Cj(a∈VT)，則置ACTION[i，a]=Sj；（2）若A→α·∈Ci，則對(duì)任意終結(jié)符a或#，置ACTION[i，a]=Rj；（3）若項(xiàng)目S→δ·∈Ci，則置ACTION[i，#]=ACC；（4）若GO[i，A]=Cj，A為非終結(jié)符，則置GOTO[i，A]=j；（5）凡不能用規(guī)則①-④添入信息的單元為空或均置ERROR。項(xiàng)目集規(guī)范族R1R1R1R15S54R2R2R2R234S3S22ACC11S3S20A#a)(GOTOACTION狀態(tài)LR(0)分析表67【例】文法G[S′]：（1）S′→S（2）S→aS|b構(gòu)造識(shí)別G所有活前綴的DFA。解題步驟：（1）寫出文法G的拓廣文法G′；（2）利用函數(shù)closure和GO，求出相應(yīng)的項(xiàng)目集規(guī)范族C；（3）根據(jù)項(xiàng)目集和轉(zhuǎn)換函數(shù)，構(gòu)造識(shí)別文法G′所有活前綴的DFA；68【例】文法G[S′]：（1）S′→S（2）S→aS|b構(gòu)造G的LR(0)分析表。解題步驟：（1）寫出文法G的拓廣文法G′；（2）利用函數(shù)closure和GO，求出相應(yīng)的項(xiàng)目集規(guī)范族C；（3）根據(jù)項(xiàng)目集和轉(zhuǎn)換函數(shù)，構(gòu)造LR(0)分析表。695.4.5LR(0)分析器的工作過程若ACTION[S，a]=Sj，a為終結(jié)符，則把a(bǔ)移入符號(hào)棧，狀態(tài)j移入狀態(tài)棧。若ACTION[S，a]=Rj，a為終結(jié)符或#號(hào)，則用第j個(gè)產(chǎn)生式歸約。設(shè)k為第j個(gè)產(chǎn)生式右部的符號(hào)串長(zhǎng)度，將符號(hào)棧和狀態(tài)棧頂?shù)膋個(gè)元素出棧，將產(chǎn)生式左部符號(hào)入符號(hào)棧。若ACTION[S，#]=ACC，則為接受，表示分析成功。若GOTO[S，A]=j，A為非終結(jié)符號(hào)并且是符號(hào)棧的棧頂，表示前一個(gè)動(dòng)作是歸約，A是歸約后移入符號(hào)棧的非終結(jié)符，則將狀態(tài)j移入狀態(tài)棧。若ACTION[S，a]=空白，則轉(zhuǎn)入錯(cuò)誤處理。70文法：0)S→A1)A→(A)2)A→a符號(hào)串“((a))”的分析過程如下：4R1)##((A)022456S5)##(A02471R1##(A)02458ACC##A019S5))##((A022454R2))##((a02234S3a))##((0223S2(a))##(022S2((a))##01GOTOACTION輸入符號(hào)串符號(hào)棧狀態(tài)棧步驟715.4.6LR(0)文法定義如果一個(gè)文法G的識(shí)別活前綴的DFA的每個(gè)狀態(tài)不存在任何沖突項(xiàng)目：（1）移進(jìn)項(xiàng)目和歸約項(xiàng)目并存；（2）多個(gè)歸約項(xiàng)目并存。則稱G是一個(gè)LR(0)文法。C0={S→·A,A→·(A),A→·a}：移進(jìn)項(xiàng)目和待約項(xiàng)目共存。C2={A→(·A),A→·(A),A→·a}：移進(jìn)項(xiàng)目和待約項(xiàng)目共存。{S→E·,E→E·+T}：移進(jìn)項(xiàng)目和歸約項(xiàng)目并存。{S→E·,E→E+E·}：多個(gè)歸約項(xiàng)目并存。72【例】文法G[S]：0)S→A1)A→ab2)A→a判斷文法G[S]是否為L(zhǎng)R(0)文法。構(gòu)造項(xiàng)目集規(guī)范族：移進(jìn)項(xiàng)目和歸約項(xiàng)目并存所以，該文法不是LR(0)文法。73LR(0)分析表：多重定義745.5SLR(1)分析法若LR(0)項(xiàng)目集規(guī)范族中有項(xiàng)目集Ck含移進(jìn)-歸約或歸約-歸約沖突，Ck={X→α·bβ,Aγ·，Bδ·}若FOLLOW(A)∩FOLLOW(B)=FOLLOW(A)∩=FOLLOW(B)∩=則解決沖突的SLR(1)技術(shù)：對(duì)于歸約項(xiàng)目向前查看一個(gè)符號(hào)a若a=b，則移進(jìn)a。若a∈FOLLOW(A)，則用產(chǎn)生式A→γ歸約。若a∈FOLLOW(B)，則用產(chǎn)生式B→δ歸約。其它報(bào)錯(cuò)當(dāng)文法的LR(0)項(xiàng)目集規(guī)范族中存在移進(jìn)-歸約沖突或歸約-歸約沖突，但能用SLR(1)技術(shù)解決沖突稱此文法為SLR(1)文法。75SLR解決方法FOLLOW(A)＝｛#｝FOLLOW(A)∩=

表中每個(gè)入口不含多重定義765.5.2SLR(1)分析表的構(gòu)造1、若A→α·aβ∈Ci且GO[i，a]=Cj，其中a為終結(jié)符，置ACTION[i，a]=“把狀態(tài)j和符號(hào)a移進(jìn)?！?，簡(jiǎn)記為“Sj”；2、若項(xiàng)目A→α·∈Ci，則對(duì)a(或#)∈FOLLOW(A)，置ACTION[i，a]=“用產(chǎn)生式A→α進(jìn)行歸約”，簡(jiǎn)記為“Rj”(假定A→α是文法G’的第j條產(chǎn)生式)；3、若項(xiàng)目S’→S·∈Ci，則置ACTION[i，#]＝“ACCEPT”；4、若GO[i，A]=Cj，A為非終結(jié)符，則置GOTO[i，A]＝j(luò)；5、分析表中凡不能用規(guī)則1-4添入信息的元素為空或均置上ERROR。77【例】文法G[S]：0)S→A1)A→ab2)A→aFOLLOW(A)＝｛#｝FOLLOW(A)∩=

78SLR分析法構(gòu)造SLR分析表的步驟如下：1)文法拓廣；2)構(gòu)造LR(0)項(xiàng)目集規(guī)范族；3)求出非終結(jié)符的FOLLOW集；4)由構(gòu)造SLR分析表的算法構(gòu)造SLR分析表79例5.11文法：0)S→E1)E→E+T2)E→T3)T→T*F4)T→F5)F→(E)6)F→i構(gòu)造LR(0)項(xiàng)目集規(guī)范族：80求出非終結(jié)符的FOLLOW集：文法：0)S→E1)E→E+T2)E→T3)T→T*F4)T→F5)F→(E)6)F→iFOLLOW(S)＝｛#｝FOLLOW(E)＝｛＋，），#｝FOLLOW(T)＝｛*，＋，），#｝FOLLOW(F)＝｛*，＋，），#｝81構(gòu)造SLR分析表：FOLLOW(S)＝｛#｝FOLLOW(E)＝｛＋，），#｝FOLLOW(T)＝｛*，＋，），#｝FOLLOW(F)＝｛*，＋，），#｝82符號(hào)串“i*(i+i)”的分析過程：8R2+i)##T*(T0274292R4+i)##T*(F027438

S5i+i)##T*(027463R6+i)##T*(i027457

S4(i+i)##T*0275

S7*(i+i)##T0242R4*(i+i)##F0333R6*(i+i)##i052

S5i*(i+i)##01GOTOACTION輸入符號(hào)串符號(hào)棧狀態(tài)棧步驟

S11)##T*(E027481510R5##T*(E)0274811168R1)##T*(E+T0274859149R4)##T*(E+F0274863133R6)##T*(E+i027486512

S5i)##T*(E+02748611

S6+i)##T*(E027481083課后習(xí)題2證明下面文法是SLR(1)文法，但不是LR(0)文法。S→AA→Ab|bBaB→aAc|a|aAb思路：1、構(gòu)造LR(0)項(xiàng)目集規(guī)范族，看是否有歸約－歸約沖突及歸約－移進(jìn)沖突。如有，則不是LR(0)文法，轉(zhuǎn)步驟2。2、求出非終結(jié)符的FOLLOW集，構(gòu)造SLR(1)分析表，如表中無(wú)重定義，則證明該文法是SLR(1)文法，但不是LR(0)文法。84項(xiàng)目集Ci含有項(xiàng)目A→α·，在i下，若a∈FOLLOW(A)，則用A→α歸約SLR分析法存在的問題因?yàn)镕OLLOW(A)是指所有可能推導(dǎo)出的句型中，可以跟隨在A后的終結(jié)符號(hào)集但LR分析法的歸約應(yīng)該僅對(duì)規(guī)范句型中跟隨在A后的終結(jié)符有效這種歸約可能導(dǎo)致歸約擴(kuò)大化？？？？？85LR(1)分析、LALR(1)分析通過尋找新的向前搜索符來解決A→α·Bβ∈I，則B→·γ∈IFOLLOW(B)FIRST(β)用FIRST(β)代替FOLLOW(B)作為用產(chǎn)生式B→γ進(jìn)行歸約的超前符號(hào)信息5.6LR(1)分析器86歸約－歸約沖突考慮如下拓廣文法：0)G→S1)S→E=E2)S→i3)E→T4)E→E+T5)T→i6)T→T*i

項(xiàng)目集規(guī)范族如下表：該文法不是SLR(1)文法FOLLOW(S)={#}FOLLOW(T)={#,+,=,*}8702134567891011i0SET=+T*iEi+iTi*圖5.9識(shí)別活前綴的自動(dòng)機(jī)FOLLOW(S)={#}FOLLOW(T)={#,+,=,*}R5面臨的輸入符號(hào)集是:T→i

{+,=,*}R2面臨的輸入符號(hào)集是: S→i{#}把即將面臨的輸入符號(hào)集稱為超前信息885.6.1LR(1)項(xiàng)目LR(1)項(xiàng)目定義：

一個(gè)LR(1)項(xiàng)目的形式為[A→α·β，u]其中第一部分是一個(gè)LR(0)項(xiàng)目，即帶有圓點(diǎn)的產(chǎn)生式A→α·β，稱為L(zhǎng)R(1)項(xiàng)目的核；第二部分u是一個(gè)超前掃描字符，且u∈Vt∪{ε}。對(duì)于一個(gè)LR(1)項(xiàng)目(A→α·β，u)，如果存在最右推導(dǎo) S|=*>λAt|=>λαβt其中λα是活前綴，且u是t的第一個(gè)符號(hào)或者是#，那么說這個(gè)LR(1)項(xiàng)目對(duì)活前綴λα有效。89例5.11有文法如下：0)G→S1)S→E=E2)S→i3)E→T4)E→E+T5)T→i6)T→T*i考慮哪些項(xiàng)目對(duì)活前綴E=T有效最右推導(dǎo)G|=*>E=T+i|=>E=T*i+i，所以項(xiàng)目[T→T·*i，+]對(duì)活前綴E=T是有效的。最右推導(dǎo)G|=*>E=T*i|=>E=T*i*i,所以項(xiàng)目[T→T·*i，*]對(duì)活前綴E=T是有效的。具有相同的核的項(xiàng)目,可以組合成復(fù)合項(xiàng)目。因此上兩項(xiàng)目復(fù)合成：[T→T·*i,+:*]。復(fù)合項(xiàng)目一般形式：

[A→α·β,α1:α2:…:αm]

905.6.2LR(1)項(xiàng)目集規(guī)范族構(gòu)造算法

1、LR(1)項(xiàng)目集的閉包運(yùn)算

設(shè)I為一LR(1)項(xiàng)目集，LR(1)閉包(closure)運(yùn)算CLOSURE(I)定義如下：

1)I中的任何LR(1)項(xiàng)目都屬于CLOSURE(I)。

2)如項(xiàng)目[A→α·Xβ，a]屬于CLOSURE(I)，且X為非終結(jié)符號(hào)，則所有形為[X→·δ，b]的項(xiàng)目均添加到CLOSURE(I)中，其中，b∈FIRST(βa)。

3)重復(fù)(1)和(2),直到CLOSURE(I)封閉為止。

91例5.12有文法如下：0)G→S1)S→E=E2)S→i3)E→T4)E→E+T5)T→i6)T→T*i對(duì)[E→·T,=]進(jìn)行閉包運(yùn)算因?yàn)橛挟a(chǎn)生式T→i,所以[T→·i,=]也屬于該項(xiàng)目集。有產(chǎn)生式T→T*i,所以[T→·T*i,=]也是該項(xiàng)目集成員。項(xiàng)目[T→·T*i,=]的閉包將產(chǎn)生兩個(gè)新項(xiàng)目[T→·i,*]和[T→·T*i,*]。最后對(duì)[E→.T,=]進(jìn)行閉包運(yùn)算得到的項(xiàng)目集為：CLOSURE（[E→·T,=]）＝{[E→·T,=]、[T→·i,=]、[T→.T*i,=]、[T→.i,*]、[T→.T*i,*]}

925.6.2LR(1)項(xiàng)目集規(guī)范族構(gòu)造算法2、LR(1)項(xiàng)目集轉(zhuǎn)換函數(shù)GO

設(shè)I是一個(gè)項(xiàng)目集，X是任一文法符號(hào)，則GO[I，X]定義為：GO[I，X]=CLOSURE(J)其中J={任何具有[A→αX·β,a]的項(xiàng)目|[A→α·Xβ,a]∈I},