編譯原理第5章自下而上語法分析方法安慶師范學(xué)院計算機(jī)與信息學(xué)院本章目標(biāo)闡明自下而上語法分析的一般思想和面臨的問題討論自下而上分析的核心問題及其分析方法介紹短語、直接短語、句柄、素短語和最左素短語的概念及其求解方法介紹算符文法和算符優(yōu)先文法的概念介紹FIRSTVT集和LASTVT集的含義及其構(gòu)造方法闡述算符優(yōu)先分析算法并探討其局限性解釋LR分析器的工作原理介紹LR(0)分析表、SLR分析表、LR(1)分析表、LALR分析表的構(gòu)造方法簡要介紹二義文法在LR分析中的應(yīng)用概述語法分析器的自動產(chǎn)生工具教學(xué)內(nèi)容5.1自下而上分析的一般思想和面臨的問題5.2算符優(yōu)先分析法5.3LR分析法5.4語法分析器的自動產(chǎn)生工具——YACC5.5本章小結(jié)5.1自下而上分析的一般思想和面臨的問題歸約和“移進(jìn)-歸約”分析法

1短語、句柄和最左素短語

2規(guī)范歸約與規(guī)范推導(dǎo)

3語法分析棧的使用與語法樹的表示

5自下而上分析的核心問題和分析方法

41、歸約和“移進(jìn)-歸約”分析法（1）歸約

所謂歸約就是推導(dǎo)的逆過程。

若是一條產(chǎn)生式，則其中推導(dǎo)歸約1、歸約和“移進(jìn)-歸約”分析法（2）“移進(jìn)—歸約”分析法

我們所討論的自下而上分析法是一種“移進(jìn)-歸約”法，其一般思想為：采用一個寄存符號的先進(jìn)后出棧，稱為分析棧，用來保存分析的歷史信息和指示分析的下一步動作。分析時，從左至右掃描輸入符號串，并將輸入符號逐個移進(jìn)分析棧中，邊移進(jìn)邊分析，一旦棧頂出現(xiàn)可歸約串（也就是棧的頂端符號串形成某個產(chǎn)生的右部）時，就將這個可歸約串歸約為相應(yīng)產(chǎn)生式的左部，即把棧頂部構(gòu)成可歸約串的那個符號串用相應(yīng)產(chǎn)生式的左部替代。接著，再檢查棧的頂部是否又形成了新的可歸約串，若是，則再進(jìn)行歸約，若未形成新的可歸約串，則再從輸入串中移進(jìn)新的符號，如此繼續(xù)下去，重復(fù)以上分析過程，即一邊移進(jìn)一邊歸約，直至輸入串分析完畢，此時，若棧中只剩下文法的開始符號，則表明所分析的輸入串是合法的，報告分析成功；否則，輸入串是不合法的。1、歸約和“移進(jìn)-歸約”分析法（3）算法流程

實際分析時，為了便于識別符號串，一般首先將“#”壓入分析棧，當(dāng)分析成功時，分析棧中只剩下文法的開始符號和“#”。這里，將“#”作為輸入串的結(jié)束符，并非文法中的符號。1、歸約和“移進(jìn)-歸約”分析法1、歸約和“移進(jìn)-歸約”分析法（4）舉例【例5.1】

設(shè)有文法：

給出輸入串a(chǎn)abbbc的“移進(jìn)-歸約”分析過程。

1、歸約和“移進(jìn)-歸約”分析法SABABa a b b b c #語法樹ip#分析棧abaAAbcSBB返回2、短語、句柄和最左素短語（1）短語和直接短語 令G是一個文法，S是文法的開始符號，假定αβδ是文法G的一個句型，如果有 且則稱β是句型ɑβδ相對于非終結(jié)符A的短語。 其中A∈VN，α，β，δ∈（VT∪VN）*。2、短語、句柄和最左素短語（1）短語和直接短語

特別地，如果有 且

則稱β是句型ɑβδ相對于規(guī)則A→β的直接短語，也稱為簡單短語。【注意】

作為“短語”的兩個條件均是不可缺少的。僅僅有，未必意味著β就是句型αβδ的一個短語。因為，還需要這一條件。2、短語、句柄和最左素短語（2）句柄 一個句型的最左直接短語稱為該句型的句柄。（3）素短語 所謂素短語是指這樣的一個短語，它至少含有一個終結(jié)符，并且，除它自身之外不再含任何更小的素短語。（4）最左素短語

最左素短語是指處于句型最左邊的那個素短語。2、短語、句柄和最左素短語（5）通過語法分析樹來尋找一個句型的短語、直接短語和句柄子樹和簡單子樹 語法樹的子樹是由該樹的某個結(jié)點（稱為子樹的根）及其所有分支構(gòu)成的部分樹稱為原樹的一棵子樹。語法樹的簡單子樹是只有單層分支的子樹——這棵子樹只有且必須有父子兩代，沒有第三代。2、短語、句柄和最左素短語（5）通過語法分析樹來尋找一個句型的短語、直接短語和句柄

【結(jié)論】每個句型（句子）都對應(yīng)一棵語法樹。每棵語法樹的葉子結(jié)點自左至右排列構(gòu)成一個句型（句子）。每棵子樹的葉子結(jié)點自左至右排列構(gòu)成一個相對于子樹根的短語。每棵簡單子樹的葉子結(jié)點自左至右排列構(gòu)成一個直接短語。最左簡單子樹的葉子結(jié)點自左至右排列構(gòu)成一個句柄。2、短語、句柄和最左素短語【例5.2】

文法：

計算句子i*(i+i)的所有短語、直接短語、句柄、素短語和最左素短語。解：為了加以區(qū)分，對句子i*(i+i)中的i加上下標(biāo)，即i1*(i2+i3)，其語法分析樹如右圖所示。①短語：i1*(i2+i3)，i1，(i2+i3)，i2+i3，i2，i3②直接短語：i1，i2，i3③句柄：i1④素短語：i1，i2，i3⑤最左素短語：i1ETTF*Fi1E()E+TTFi2Fi3返回3、規(guī)范歸約與規(guī)范推導(dǎo)（1）規(guī)范推導(dǎo)與規(guī)范句型

在形式語言中，最右推導(dǎo)通常被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。（2）規(guī)范歸約 假定α是文法G的一個句子，如果序列 滿足以下條件，則稱這個序列是α的一個規(guī)范歸約：αn=α；α0為文法的開始符號，即α0=S；對任何i，0<i≤n，αi-1是αi從經(jīng)把句柄替換為相應(yīng)產(chǎn)生式的左部符號而得到的。3、規(guī)范歸約與規(guī)范推導(dǎo)

容易看出，規(guī)范歸約是關(guān)于α的一個最右推導(dǎo)的逆過程。因此，規(guī)范歸約也稱為最左歸約。如果文法G是無二義的，則規(guī)范推導(dǎo)和規(guī)范歸約是一個互逆過程。（3）規(guī)范歸約的實質(zhì) 對于規(guī)范句型來說，句柄的后面不會出現(xiàn)非終結(jié)符號（即句柄的后面只能出現(xiàn)終結(jié)符）。基于這一點，可用句柄來刻畫“移進(jìn)-歸約”過程中的“可歸約串”。規(guī)范歸約的實質(zhì) 在移進(jìn)過程中，當(dāng)發(fā)現(xiàn)棧頂呈現(xiàn)句柄時就用相應(yīng)產(chǎn)生式的左部符號進(jìn)行替換。規(guī)范歸約的中心問題 如何尋找或確定一個句型的句柄。3、規(guī)范歸約與規(guī)范推導(dǎo)（4）修剪語法分析樹尋找規(guī)范歸約序列【方法】找出句子的一個推導(dǎo)，并畫出語法樹。將當(dāng)前句型的句柄歸約為相應(yīng)產(chǎn)生式的左部，得到新的句型。剪去語法樹的最左簡單子樹的葉子結(jié)點和分支，保留根結(jié)。重復(fù)步驟和，直至只剩下開始符號為止。3、規(guī)范歸約與規(guī)范推導(dǎo)【例5.3】

設(shè)有文法：

試通過修剪語法樹的方法來分析句子abbcde的規(guī)范歸約過程。3、規(guī)范歸約與規(guī)范推導(dǎo)SaBeAbdb規(guī)范推導(dǎo)：規(guī)范歸約：Ac返回4、自下而上分析的核心問題和分析方法（1）引例

自下而上分析是一種“移進(jìn)-歸約”分析法，在移進(jìn)的過程中一旦發(fā)現(xiàn)棧頂端出現(xiàn)“可歸約串”，即進(jìn)行“歸約”。這里，我們認(rèn)為可歸約串即為某個產(chǎn)生式的右部。 例如，針對以下文法，分析輸入串a(chǎn)bbcde的“移進(jìn)-歸約”過程。4、自下而上分析的核心問題和分析方法語法樹分析棧a b b c d e #ipA#abABSAbb和Ab都可以是可歸約串，如何歸約？方案一：按A→b進(jìn)行歸約。方案二：按A→Ab進(jìn)行歸約。AcdBe輸入串已到“#”，而棧內(nèi)并非“#S”，因此，分析失敗！bAcdBeS分析成功！分析失敗！4、自下而上分析的核心問題和分析方法（2）核心問題與分析方法

核心問題：如何尋找或界定“可歸約串”？

最左素短語句柄自下而上分析方法什么是可歸約串？算符優(yōu)先分析法LR分析法規(guī)范歸約非規(guī)范歸約返回5、語法分析棧的使用與語法樹的表示（1）“移進(jìn)-歸約”分析器基本構(gòu)成

分析器一般由分析棧、分析表、分析程序和輸入緩沖區(qū)組成。（2）分析器的結(jié)構(gòu)模型分析程序分析棧輸入串輸出分析表一般情形初始時刻成功結(jié)束X1Xm#.....S5、語法分析棧的使用與語法樹的表示（3）分析器的四種動作移進(jìn)：將輸入串的一個符號移進(jìn)分析棧。歸約：發(fā)現(xiàn)棧頂呈“可歸約串”，并用適當(dāng)?shù)南鄳?yīng)符號去替換這個串。接受：宣布最終分析成功，可看作是歸約的一種特殊形式。報錯：發(fā)現(xiàn)棧頂內(nèi)容與輸入串相悖，調(diào)用出錯處理程序進(jìn)行診察和校正，并對棧頂內(nèi)容和輸入符號進(jìn)行調(diào)整。（4）“移進(jìn)-歸約”分析法用棧實現(xiàn)的特點可歸約串必定位于棧頂，即可歸約串之后就是剩余的輸入串。棧內(nèi)符號串與剩余輸入串正好構(gòu)成一個句型。（5）語法分析樹的表示 具體實現(xiàn)時可以采用不同的數(shù)據(jù)結(jié)構(gòu)，如“穿線表”方法。作業(yè)5.1習(xí)題五（P150）：1（1）至（6）34（3）返回5.2算符優(yōu)先分析法

算符優(yōu)先分析是一種分析過程比較迅速的自下而上的分析方法，特別適用于表達(dá)式的分析，易于手工實現(xiàn)。算符優(yōu)先分析不是一種嚴(yán)格的最左歸約，即不是一種規(guī)范歸約方法。在算符優(yōu)先分析方法中，可歸約串就是最左素短語。 所謂算符優(yōu)先就是借鑒了表達(dá)式運(yùn)算不同優(yōu)先順序的概念，在終結(jié)符之間定義某種優(yōu)先歸約的關(guān)系，從而在句型中尋找可歸約串。由于終結(jié)符關(guān)系的定義和普通算術(shù)表達(dá)式的算符（如加減乘除）運(yùn)算的優(yōu)先關(guān)系相似，所以得名算符優(yōu)先分析方法。這種方法可以用于一大類上下文無關(guān)文法，GNUGCC中的Java編譯器GCJ就采用了算符優(yōu)先分析方法。5.2算符優(yōu)先分析法算符文法和算符優(yōu)先文法

1FIRSTVT集和LASTVT集

2算符優(yōu)先關(guān)系表及優(yōu)先函數(shù)

3算符優(yōu)先分析中的出錯處理

5算符優(yōu)先分析算法及其特點

41、算符文法和算符優(yōu)先文法（1）算符文法

如果一個文法G中的任何產(chǎn)生式的右部候選項都不含兩個連續(xù)的非終結(jié)符，即不含形如

的產(chǎn)生式，其中，則稱該文法為算符文法。 根據(jù)以上定義，算符文法的句型的一般形式顯然可寫成：

其中，；，可能出現(xiàn)也可能不出現(xiàn)。1、算符文法和算符優(yōu)先文法（2）終結(jié)符之間的關(guān)系

在下面的定義中，a、b代表任意的終結(jié)符；P、Q、R代表任意非終結(jié)符；“…”代表由終結(jié)符和非終結(jié)符組成的任意序列，包括空串。 假定G是一個不含ε產(chǎn)生式的算符文法，對任意一對終結(jié)符a,b，我們定義：

a=b，當(dāng)且僅當(dāng)文法G中含有形如P→…ab…或P→…aQb…的產(chǎn)生式；

a<b，當(dāng)且僅當(dāng)G中含有形如P→…aR…的產(chǎn)生式，而或；

a>b，當(dāng)且僅當(dāng)G中含有形如P→…Rb…的產(chǎn)生式，而或。1、算符文法和算符優(yōu)先文法（2）終結(jié)符之間的關(guān)系

【注意】

=、<、>稱為算符優(yōu)先關(guān)系（簡稱為優(yōu)先關(guān)系），它們表示算符文法G中任意兩個終結(jié)符之間的關(guān)系，與非終結(jié)符無關(guān)。優(yōu)先關(guān)系a=b表示a和b的歸約優(yōu)先關(guān)系相等，它們屬于同一個可歸約串，同時被某個非終結(jié)符替換掉；優(yōu)先關(guān)系a<b表示a的歸約優(yōu)先級比b的要低，只有b所在符號串歸約完之后，才能歸約包含a的符號串；優(yōu)先關(guān)系a>b則表示a的歸約優(yōu)先級比b的要高，在包含a的符號串歸約完之后，才能歸約包含b的符號串。1、算符文法和算符優(yōu)先文法（2）終結(jié)符之間的關(guān)系

【注意】

算符優(yōu)先關(guān)系是有序的，但不滿足對稱性和傳遞性，即對于文法G的終結(jié)符a、b和c：如果a<b，并不意味著b>a；如果存在a=b和b=c，不一定有b=a或a=c；如果存在a<b和b<c，也不能得出a<c。1、算符文法和算符優(yōu)先文法（3）算符優(yōu)先文法

如果一個算符文法G中的任何終結(jié)符對（a，b）至多只滿足下述三種關(guān)系之一：

=，>，<

則稱G是一個算符優(yōu)先文法。返回2、FIRSTVT集和LASTVT集（1）FIRSTVT(P)

對算符文法G的每個非終結(jié)符P，定義（2）集合FIRSTVT(P)的構(gòu)造方法規(guī)則一：若有產(chǎn)生式P→a…或P→Qa…，則a∈FIRSTVT(P)；規(guī)則二：若a∈FIRSTVT(Q)且有產(chǎn)生式P→Q…，則a∈FIRSTVT(P)；規(guī)則三：反復(fù)使用以上兩條規(guī)則，直到FIRSTVT(P)不再增大為止。2、FIRSTVT集和LASTVT集（3）LASTVT(P)

對算符文法G的每個非終結(jié)符P，定義（4）集合LASTVT(P)的構(gòu)造方法規(guī)則一：若有產(chǎn)生式P→…a或P→…aQ，則a∈LASTVT(P)；規(guī)則二：若a∈LASTVT(Q)且有產(chǎn)生式P→…Q，則a∈LASTVT(P)；規(guī)則三：反復(fù)使用以上兩條規(guī)則，直到LASTVT(P)不再增大為止。2、FIRSTVT集和LASTVT集【例5.4】

構(gòu)造以下文法的所有非終結(jié)符的FIRSTVT集和LASTVT集。（i+*↑（i↑（i*↑（i）i+*）i↑）i*↑）i↑2、FIRSTVT集和LASTVT集（5）構(gòu)造FIRSTVT(P)的形式化算法描述數(shù)據(jù)結(jié)構(gòu)二維布爾數(shù)組F[P,a]：F[P,a]=true，當(dāng)且僅當(dāng)a∈FIRSTVT(P)。棧STACK：壓入符號對(P，a)，當(dāng)且僅當(dāng)F[P,a]=true。所有終結(jié)符所有非終結(jié)符數(shù)組值為真假，為真的條件是，a∈FIRSTVT(P)2、FIRSTVT集和LASTVT集（5）構(gòu)造FIRSTVT(P)的形式化算法描述基本做法按規(guī)則一對每個數(shù)組元素F[P,a]賦初值。應(yīng)用第二條規(guī)則修改數(shù)組F的元素值，其修改方法如下：將所有初值為真的數(shù)組元素F[P,a]的符號對(P，a)全部壓入STACK之中。如果棧STACK不空，就將棧頂項彈出，記此項為(Q，a)。對每個形如P→Q…的產(chǎn)生式，若F[P,a]為假，則將其值變?yōu)檎媲覍?P，a)壓入STACK棧。重復(fù)步驟，直至STACK棧為空為止。從最終所得二維數(shù)組F中可得到任何非終結(jié)符P的FIRSTVT集，即2、FIRSTVT集和LASTVT集（5）構(gòu)造FIRSTVT(P)的形式化算法描述形式化算法描述voidFIRSTVT(P)//計算非終結(jié)符P的FIRSTVT集{for(每個非終結(jié)符P和終結(jié)符a){ F[P,a]=FALSE; }for(每個形如P→a…或P→Qa…的產(chǎn)生式){ Insert(P,a); }while(!StackEmpty())//棧STACK非空{(diào) Pop(Q,a); for(每條形如P→Q…的產(chǎn)生式) { Insert(P,a); }}}對數(shù)組初始化應(yīng)用規(guī)則一應(yīng)用規(guī)則二voidInsert(P,a){

if(F[P,a]==FALSE)

{

F[P,a]=TRUE;

Push(P,a);

}}2、FIRSTVT集和LASTVT集（5）構(gòu)造FIRSTVT(P)的形式化算法描述例如，求以下文法各非終結(jié)符的FIRSTVT集：111100000000000111T，*E，+F，(F，iT，i11T，(返回3、算符優(yōu)先關(guān)系表及優(yōu)先函數(shù)（1）算符優(yōu)先關(guān)系表

為方便比較算符文法中各終結(jié)符對之間的優(yōu)先關(guān)系，最簡單的辦法是先將各種可能相繼出現(xiàn)的終結(jié)符的優(yōu)先關(guān)系計算出來，并將其表示成一個矩陣形式，在分析過程中通過查詢矩陣元素而獲得終結(jié)符間的優(yōu)先關(guān)系，這個矩陣稱為算符優(yōu)先關(guān)系表。所有終結(jié)符所有終結(jié)符矩陣值為>、<、=或為空白3、算符優(yōu)先關(guān)系表及優(yōu)先函數(shù)（2）算符優(yōu)先關(guān)系表的構(gòu)造方法

利用文法G中的每個非終結(jié)符P的FIRSTVT集和LASTVT集，我們就能方便地構(gòu)造文法G的算符優(yōu)先關(guān)系表，其構(gòu)造方法如下： 規(guī)則一：對形如P→…ab…或P→…aQb…的產(chǎn)生式，有a=b；

規(guī)則二：對形如P→…aR…的產(chǎn)生式，若有b∈FIRSTVT(R)，則a<b；

規(guī)則三：對形如P→…Rb…的產(chǎn)生式，若有a∈LASTVT(R)，則a>b；

規(guī)則四：對于語句括號#，有#=#，且若a∈FIRSTVT(S)和b∈LASTVT(S)，則有#<a且b>#。3、算符優(yōu)先關(guān)系表及優(yōu)先函數(shù)（2）算符優(yōu)先關(guān)系表的構(gòu)造方法形式化算法描述voidOPRT()//構(gòu)造文法G的算符優(yōu)先關(guān)系表{ for(每條產(chǎn)生式P→X1X2…Xn) for(i=1;i<=n-1;i++) { if(Xi∈VT&&Xi+1∈VT)置Xi=Xi+1 if(i<=n-2&&Xi∈VT&&Xi+2∈VT&&Xi+1∈VN)置Xi=Xi+2 if(Xi∈VT&&Xi+1∈VN) for(每個a∈FIRSTVT(Xi+1))置Xi<a if(Xi∈VN&&Xi+1∈VT) for(每個a∈LASTVT(Xi))置a>Xi+1 }}3、算符優(yōu)先關(guān)系表及優(yōu)先函數(shù)（2）算符優(yōu)先關(guān)系表的構(gòu)造方法

【注意】

在以上算法描述中，為了能夠計算#與其它終結(jié)符之間的關(guān)系，一般在文法的產(chǎn)生式中添加一個新的產(chǎn)生式

其中，且。 按照以上方法構(gòu)造出來的算符優(yōu)先關(guān)系表中的每一項，若至多只有一種關(guān)系，則文法G是算符優(yōu)先文法。3、算符優(yōu)先關(guān)系表及優(yōu)先函數(shù)【例5.5】

構(gòu)造文法G[E]的算符優(yōu)先關(guān)系表。><=>>>><<<>>>><<<>><<<<<<<<>>>>><<<<<>>>>>=3、算符優(yōu)先關(guān)系表及優(yōu)先函數(shù)（3）優(yōu)先函數(shù)

把每個終結(jié)符a與兩個自然數(shù)f(a)和g(a)相對應(yīng)，若根據(jù)一個文法的算符優(yōu)先關(guān)系表，使得文法中每個終結(jié)符a和b滿足下述條件:若存在a=b，則有f(a)=g(b)；若存在a>b，則有f(a)＞g(b)；若存在a<b，則有f(a)＜g(b)。 則稱f和g為優(yōu)先函數(shù)，其中，f稱為入棧優(yōu)先函數(shù)，g稱為比較優(yōu)先函數(shù)。3、算符優(yōu)先關(guān)系表及優(yōu)先函數(shù)（3）優(yōu)先函數(shù)【注意】

對應(yīng)一個優(yōu)先關(guān)系表的優(yōu)先函數(shù)f和g不唯一，只要存在一對，就存在無窮多對。也有許多優(yōu)先關(guān)系表不存在對應(yīng)的優(yōu)先函數(shù)。 例如，以下優(yōu)先關(guān)系表不存在優(yōu)先函數(shù)。優(yōu)先表中若存在f和g,則有 f(a)=g(a); f(a)＞g(b) f(b)=g(a); f(b)=g(b)這將導(dǎo)致如下矛盾: f(a)＞g(b)=f(b)=g(a)=f(a)3、算符優(yōu)先關(guān)系表及優(yōu)先函數(shù)（3）優(yōu)先函數(shù)使用優(yōu)先函數(shù)的好處節(jié)省空間；便于進(jìn)行比較運(yùn)算。使用優(yōu)先函數(shù)的缺陷 原先不存在優(yōu)先關(guān)系的兩個終結(jié)符，由于與自然數(shù)相對應(yīng)，變成可比較的了。因而，可能會掩蓋輸入串中的某些錯誤。但是，我們可以通過檢查棧頂符號和輸入符號的具體內(nèi)容來發(fā)現(xiàn)那些不可比較的情形。3、算符優(yōu)先關(guān)系表及優(yōu)先函數(shù)（4）Bell方法構(gòu)造優(yōu)先函數(shù)

如果優(yōu)先函數(shù)存在，則可以利用有向圖來構(gòu)造優(yōu)先函數(shù)，這種方法稱為Bell方法。其具體步驟如下： ①對每個終結(jié)符a（包括“#”）,令其對應(yīng)兩個符號fa和ga, 畫一張以所有符號fa和ga為結(jié)點的方向圖：若a>b或a=b，畫一條從fa到gb的有向邊;若a<b或a=b，畫一條從gb到fa的有向邊;fafbgagbab>或=<或=3、算符優(yōu)先關(guān)系表及優(yōu)先函數(shù)（4）Bell方法構(gòu)造優(yōu)先函數(shù) ②對每個結(jié)點都賦予一個數(shù)，此數(shù)等于從該結(jié)點出發(fā)所能到達(dá)的結(jié)點（包括出發(fā)結(jié)點自身）的個數(shù)，賦給fa的數(shù)作為f(a)，賦給gb的數(shù)作為g(b)； ③檢查所構(gòu)造的函數(shù)f和g，看它們同原來的關(guān)系表是否有矛盾。若沒有矛盾，則f和g就是所求的優(yōu)先函數(shù)；若有矛盾，則不存在優(yōu)先函數(shù)。3、算符優(yōu)先關(guān)系表及優(yōu)先函數(shù)【例5.6】

求下述優(yōu)先關(guān)系表的優(yōu)先函數(shù)（不含“#”）。3、算符優(yōu)先關(guān)系表及優(yōu)先函數(shù)f＋f*fif)g＋g*gig(g)f( 解:①用Bell法構(gòu)造的優(yōu)先關(guān)系圖如下:3、算符優(yōu)先關(guān)系表及優(yōu)先函數(shù)

②由上圖求得優(yōu)先函數(shù)如下:返回4、算符優(yōu)先分析算法及其特點（1）定理

算符優(yōu)先分析法是一種自下而上分析法，在其“移進(jìn)-歸約”過程中，以最左素短語來刻畫“可歸約串”，即在分析過程中一旦發(fā)現(xiàn)棧頂端出現(xiàn)當(dāng)前句型的最左素短語，就立即采取歸約動作。那么，算符優(yōu)先分析器在分析過程中是如何識別最左素短語的呢？這主要基于以下定理：

定理5.1一個算符優(yōu)先文法G的任何句型#N1a1N2a2…NmamNm+1#的最左素短語是滿足如下條件的最左子串：Njaj…NiaiNi+1:（其中,ai是終結(jié)符,Ni是可有可無的非終結(jié)符）aj-1<ajaj=aj+1，aj+1=aj+2，…，ai-1=aiai>ai+14、算符優(yōu)先分析算法及其特點（1）定理句型的一般形式

最左邊： 中間： 最右邊：

算符優(yōu)先文法G的句型中的可歸約串就是最左素短語。該定理說明了最左素短語與周圍符號之間的關(guān)系。最左素短語4、算符優(yōu)先分析算法及其特點（2）算符優(yōu)先分析過程句型的一般形式分析的關(guān)鍵問題 尋找最左素短語（可歸約串）。處理方法 從左向右掃描各符號，依次查看算符優(yōu)先關(guān)系表，直至找到滿足ai>ai+1的終結(jié)符為止，一直移進(jìn)。再從ai開始往左掃描，直至找到滿足關(guān)系aj-1<aj的終結(jié)符為止，進(jìn)行歸約。4、算符優(yōu)先分析算法及其特點（3）算符優(yōu)先分析算法數(shù)據(jù)結(jié)構(gòu)符號棧S：寄存終結(jié)符和非終結(jié)符。k：代表符號棧S的使用深度S[k]：表示當(dāng)前棧頂元素S[j]：表示棧頂端的終結(jié)符a：存儲最新讀入的輸入符號S12…k-1k深度為k棧頂元素若S[k]∈VT,則S[j]=S[K]aiNi若S[k]∈VN,則S[j]=S[K-1]4、算符優(yōu)先分析算法及其特點k=1;S[k]='#';//k代表棧S的使用深度do{ Read(a);//把下一個輸入符號讀入a中 if(S[k]∈VT)j=k;//j表示棧頂終結(jié)符位置 elsej=k-1;/*任何兩終結(jié)符之間最多只有一個非終結(jié)符，故若S[k]∈VN，則S[k-1]∈VT*/ while(S[j]>a){//棧頂端已出現(xiàn)最左素短語，棧頂符號為其尾部 do{//自棧頂向棧底方向找出最左子串S[i]<S[i+1]…S[j]>a Q=S[j]; if(S[j-1]∈VT)j=j-1;//j從最左素短語末逐步移向首 elsej=j-2; }while(S[j]=Q);//S[j]<Q時表明找到了最左素短語的首部 把S[j+1]…S[k]歸約為某個N;//S[j+1]…S[k]為最左素短語 k=j+1; S[k]=N;//將歸約后的非終結(jié)符N置于原S[j+1]位置 } if((S[j]<a)||(S[j]=a)){//若棧頂S[j]<a或S[j]=a，則將a壓棧 k=k+1; S[k]=a; } elseerror();//調(diào)用出錯診察程序

}while(a!='#');4、算符優(yōu)先分析算法及其特點【注意】上述算法的工作過程中，若出現(xiàn)j減1后的值小于或等于0時，則意味著輸入串有錯。在正確的情況下，算法工作完畢時，符號棧S應(yīng)呈現(xiàn)#N#。在上述算法中，當(dāng)發(fā)現(xiàn)并找到最左素短語時，我們并未指出將其歸約為哪一個非終結(jié)符號‘N’。實際上，我們在文法中尋找這樣的產(chǎn)生式，它的右部形如:

其中每個終結(jié)符號與最左素短語對應(yīng)位置上的終結(jié)符號完全相同，而每一個非終結(jié)符號Pk應(yīng)與相應(yīng)位置上的非終結(jié)符號Nk相對應(yīng)，不必完全相同。

4、算符優(yōu)先分析算法及其特點【例5.7】有文法：試構(gòu)造句子i*i+i的算符優(yōu)先分析過程。解題步驟計算所有非終結(jié)符的FIRSTVT集和LASTVT集構(gòu)造算符優(yōu)先關(guān)系表構(gòu)造輸入串的算符優(yōu)先分析過程4、算符優(yōu)先分析算法及其特點NNNNi*i+i#語法樹ipN#1234kij1234QS[j]#i<N**#iiN++i成功結(jié)束S4、算符優(yōu)先分析算法及其特點（4）算符優(yōu)先分析的特點

對例5.7的文法的句子i*i+i的規(guī)范歸約語法樹和算符優(yōu)先分析所得的語法樹進(jìn)行比較，可得以下結(jié)論：規(guī)范歸約語法樹算符優(yōu)先語法樹算符優(yōu)先分析一般并不等價于規(guī)范歸約并不對文法的非終結(jié)符定義優(yōu)先關(guān)系，無法發(fā)現(xiàn)由單個非終結(jié)符組成的“可歸約串”。即無法使用單非產(chǎn)生式(如：TF)進(jìn)行歸約。算符優(yōu)先分析比規(guī)范歸約過程要快，跳過了所有的單非產(chǎn)生式。可能將本來不是句子的輸入串誤認(rèn)為是句子。返回5、算符優(yōu)先分析中的出錯處理（1）錯誤發(fā)生的情形

使用算符優(yōu)先分析法時，可在以下兩種情況下發(fā)現(xiàn)語法錯誤：棧頂終結(jié)符號與下一輸入符號之間不存在任何優(yōu)先關(guān)系；找到某一最左素短語，但不存在任一產(chǎn)生式，其右部與此最左素短語相匹配。（2）處理方法

在優(yōu)先矩陣中的每一空項中，可填入指示器，指向處理該項錯誤的子程序。不同的空項可填同一指示器，也就是運(yùn)用同樣的錯誤處理方法。錯誤一處理方式：通過改變、插入或刪除符號來使得棧頂符號和輸入符號之間存在優(yōu)先關(guān)系。錯誤二處理方式：打印錯誤信息，并確定該最左素短語與哪個產(chǎn)生式的右部最為相似。實驗三語法分析器設(shè)計之二——算符優(yōu)先分析程序（1）實驗?zāi)康暮鸵罄斫庾韵露戏治鏊惴ǖ臉?gòu)造思想。理解算符文法和算符優(yōu)先文法的概念。掌握FIRSTVT集、LASTVT集和算符優(yōu)先關(guān)系表的構(gòu)造方法。理解素短語和最左素短語的概念，并掌握其尋求方法。理解算符優(yōu)先分析算法，能夠使用某種高級語言實現(xiàn)一個算符優(yōu)先分析程序。（2）實驗內(nèi)容

編寫一個算符優(yōu)先分析程序，能實現(xiàn)以下功能：輸入文法，判斷是否為算符文法；構(gòu)造并輸出該文法的每個非終結(jié)符的FIRSTVT集和LASTVT集；構(gòu)造并輸出算符優(yōu)先分析表，判斷是否為算符優(yōu)先文法，若不是提示無法進(jìn)行分析；任意輸入一個輸入串，可得到成功的分析或錯誤的提示，輸出其分析過程或打印語法分析樹。作業(yè)5.2習(xí)題五（P151）：56返回5.3LR分析法二義文法在LR分析中的應(yīng)用

6LALR(1)分析器

5LR分析中的出錯處理

7LR分析器的工作原理

1LR(0)分析器

2SLR(1)分析器

3LR(1)分析器

41、LR分析器的工作原理（1）LR分析法的基本思想

LR分析法的基本思想可以用12個字來概括：記住歷史、展望未來、定奪現(xiàn)在。 在規(guī)范歸約過程中，一方面記住已移進(jìn)和歸約的整個符號串，即記住“歷史”；另一方面根據(jù)所用產(chǎn)生式推測未來可能碰到的輸入符號，即對未來進(jìn)行“展望”。當(dāng)一串貌似句柄的符號串呈現(xiàn)于分析棧棧頂時，根據(jù)“歷史”和“展望”以及“現(xiàn)實”的輸入符號等三方面的材料，來確定棧頂?shù)姆柎欠駱?gòu)成相對某一產(chǎn)生式的句柄。1、LR分析器的工作原理（2）LR分析器的邏輯模型及其組成LR總控程序分析棧輸入串分析表輸出1、LR分析器的工作原理（2）LR分析器的邏輯模型及其組成分析棧 一個LR分析器實際上是一個帶有先進(jìn)后出棧的確定有限自動機(jī)。將“歷史”和“展望”綜合成“狀態(tài)”，分析棧用來存放這些狀態(tài)，它們概括了從分析開始直到某一歸約階段的全部歷史和展望資料，不必象算符優(yōu)先分析法中要翻閱棧中的內(nèi)容才能決定是否要進(jìn)行歸約。只需根據(jù)棧頂狀態(tài)和輸入符號就可以唯一決定下一個動作。狀態(tài)棧：(S0,#)為預(yù)先放到棧中的初始狀態(tài)和符號。符號棧：X1X2…Xm是目前已移進(jìn)并歸約出的句型部分。其實它是多余的，已經(jīng)概括到狀態(tài)里。1、LR分析器的工作原理（2）LR分析器的邏輯模型及其組成分析表

LR分析表是LR分析器的核心部分。

LR分析表由ACTION表和GOTO表構(gòu)成。ACTION表：動作表，也稱為動作函數(shù)GOTO表：狀態(tài)轉(zhuǎn)換表，也稱為狀態(tài)轉(zhuǎn)換函數(shù)VT+#VNACTION[Si,aj]為一動作，表示當(dāng)前狀態(tài)Si面臨輸入符號aj時所完成的分析動作。GOTO[Si,Xj]為一狀態(tài)，表示當(dāng)前狀態(tài)Si面臨文法符號Xj時需轉(zhuǎn)移的下一個狀態(tài)。1、LR分析器的工作原理（2）LR分析器的邏輯模型及其組成分析動作

ACTION表中的元素ACTION[Si,aj]是一個動作，表示當(dāng)前狀態(tài)Si面臨輸入符號aj時所完成的分析動作。分析動作可分四類：移進(jìn)：將下一狀態(tài)Sk（Sk=GOTO[Si，aj]）和現(xiàn)行輸入符號aj移進(jìn)分析棧，下一輸入符號aj+1變成現(xiàn)行輸入符號。移進(jìn)動作表示當(dāng)前棧頂端符號串尚未形成句柄，正期待繼續(xù)移進(jìn)符號以形成句柄。Skajip1、LR分析器的工作原理（2）LR分析器的邏輯模型及其組成歸約：指用某一個產(chǎn)生式A→β進(jìn)行歸約。假若β的長度為L（L=|β|），則歸約的動作是去掉棧頂?shù)腖個項，即若當(dāng)前棧頂狀態(tài)為Sm，則將狀態(tài)Sm-L變成棧頂狀態(tài)，然后將狀態(tài)Sk（Sk=GOTO[Sm-L，A]）和文法符號A（A∈VN）移進(jìn)分析棧。歸約動作不改變現(xiàn)行輸入符號，執(zhí)行歸約動作意味著呈現(xiàn)于棧頂?shù)姆柎甔m-L+1…Xm（β=Xm-L+1…Xm）是一個相對于A的句柄。Xm…Sm-L+1Xm-L+1…SmAA→Xm-L+1…Xm為句柄SK1、LR分析器的工作原理（2）LR分析器的邏輯模型及其組成接受：宣布分析成功，停止分析器的工作。報錯：發(fā)現(xiàn)源程序含有錯誤，調(diào)用出錯處理程序進(jìn)行處理。1、LR分析器的工作原理

相關(guān)約定用Sk的下標(biāo)k表示狀態(tài)s表示執(zhí)行移進(jìn)動作6=GOTO[1,+]，表示下一狀態(tài)s6表示將(6,+)移進(jìn)分析棧r表示執(zhí)行歸約動作2表示產(chǎn)生式編號r2表示按第2個產(chǎn)生式進(jìn)行歸約acc表示接受空白表示出錯表示狀態(tài)，即

GOTO[0,E]=11、LR分析器的工作原理總控程序 LR分析器的總控程序本身的工作十分簡單，它的任何一步只需根據(jù)分析棧的棧頂狀態(tài)s和現(xiàn)行輸入符號a去執(zhí)行所規(guī)定的動作即可。初始化：將（0，#）壓入分析棧從輸入串中讀入當(dāng)前的輸入符號ai，根據(jù)當(dāng)前狀態(tài)棧棧頂狀態(tài)m與輸入符號ai查ACTION表：若ACTION[m,ai]=‘sj’，完成移進(jìn)動作；若ACTION[m,ai]=‘rj’，以文法的第j條規(guī)則完成歸約動作；若ACTION[m,ai]=‘a(chǎn)cc’，分析成功，結(jié)束；若ACTION[m,ai]=‘error’，出錯處理。重復(fù)②直到出錯或接受為止。1、LR分析器的工作原理（3）LR分析器的工作過程 用三元式（狀態(tài)棧，符號棧，輸入串）表示分析過程中狀態(tài)棧，符號棧，輸入符號的變化。初始時刻：將初始狀態(tài)0和#移進(jìn)分析棧。三元式為：(0, #, a1a2…an#)接受時刻：(01 ,#S ,#)任一時刻：(01…m, #X1X2…Xm, aiai+1…an#)分析器的下一步動作是由棧頂狀態(tài)m和當(dāng)前面臨的輸入符號ai唯一確定的。1、LR分析器的工作原理（3）LR分析器的工作過程任一時刻的移進(jìn)歸約過程：(01…m, #X1X2…Xm, aiai+1…an#)查ACTION[Sm,ai]=?="sj"：移進(jìn)（j，ai）(01…mj, #X1X2…Xmai, ai+1…an#)="rj"：按第j個產(chǎn)生式（A→Xm-L+1…Xm）歸約，k=GOTO[m-L，ai](01…m-Lk, #X1X2…Xm-LA, ai…an#)=“acc”：分析成功，終止分析。三元式不再變化。(01, #S, #)=“error”或空白：則三元式的變化過程終止，報告錯誤。 一個LR分析器的工作過程就是一步一步地變換三元式，直至執(zhí)行“接受”或“報錯”為止。1、LR分析器的工作原理（4）LR分析器的分析流程及分析算法1、LR分析器的工作原理（4）LR分析器的分析流程及分析算法相關(guān)變量和過程說明SymbolStack數(shù)組為符號棧StateStack數(shù)組為狀態(tài)棧k為棧的使用深度a存放當(dāng)前讀入的輸入符號GetNextSymbol過程為將當(dāng)前輸入符號指針?biāo)阜栕x入變量a中，并將輸入指針指向下一個輸入符號。ERROR為出錯處理程序。1、LR分析器的工作原理voidLR_Analyze(){//LR分析算法k=1;StateStack[k]=0;SymbolStack[k]=#;//初始化，將初態(tài)0和#分別移進(jìn)狀態(tài)棧和符號棧a=GetNextSymbol();//將下一個輸入符號讀進(jìn)a中;while(true){ s=StateStack[k];//s為當(dāng)前狀態(tài)棧棧頂狀態(tài) if(ACTION[s,a]=="sj"){//sj意味著執(zhí)行移進(jìn)動作

k=k+1;StateStack[k]=j;SymbolStack[k]=a;//將狀態(tài)j和符號a分別移進(jìn)狀態(tài)棧和符號棧 a=GetNextSymbol();//將下一個輸入符號讀進(jìn)a中; } elseif(ACTION[s,a]=="rj"){//rj意味著執(zhí)行歸約動作,第j個產(chǎn)生式為A→α，其中|α|=L， k=k-L;//狀態(tài)棧和符號棧分別彈出L個符號 tateStack[k];//s為當(dāng)前狀態(tài)棧棧頂狀態(tài) S'=GOTO[S,A];k=k+1;StateStack[k]=S';SymbolStack[k]=A;//將S'和A分別移進(jìn)狀態(tài)棧和符號棧 } elseif(ACTION[s,a]=="acc")//acc意味著分析成功 return;//結(jié)束分析過程 else//ACTION[s,a]為空白或出錯標(biāo)志 ERROR();//調(diào)用出錯處理程序進(jìn)行處理}}1、LR分析器的工作原理【例5.10】

根據(jù)下述文法G[E]及其LR分析表，分析輸入串i*i+i的LR分析過程。1、LR分析器的工作原理EE+TTT*FFiiFiip語法樹0#5i1F3T27*i5F10E16+5iF3T9成功結(jié)束1、LR分析器的工作原理（5）LR文法 對于一個文法，如果能夠構(gòu)造一張LR分析表，使得它的每個入口均是唯一確定的，則稱這個文法為LR文法。 一般而言，一個文法如果能用一個每步最多向前檢查k個輸入符號的LR分析器進(jìn)行分析，則這個文法就稱為LR(k)文法。但對多數(shù)的程序語言來說，k=0或1就足夠了。因此，我們只考慮k≤1的情形。【結(jié)論】LR文法肯定是無二義的，一個二義文法決不會是LR文法。但是，LR分析技術(shù)可以進(jìn)行適當(dāng)修改以適用于分析一定的二義文法。存在不是LR的上下文無關(guān)文法。對于一個LR文法，當(dāng)分析器對輸入串進(jìn)行自左至右掃描時，一旦句柄呈現(xiàn)于棧頂，就能及時對其實行歸約。LR分析法比預(yù)測分析法更加一般化。1、LR分析器的工作原理LR分析表是LR分析器的核心，主要有以下幾種分析表：LR(0)表：局限性極大，是建立其它LR分析表的基礎(chǔ)。SLR(1)表（即簡單LR表）：比較容易實現(xiàn)又極有使用價值。LR(1)表（即規(guī)范LR表）：能力最強(qiáng)，適用于大多數(shù)上下文無關(guān)文法，但分析表體積龐大。LALR表（即向前LR表）：能力介于SLR(1)表和LR(1)表之間 應(yīng)該指出，LR分析器分析時，不論采用上述哪一種分析表，其分析算法都是一樣的，即其總控程序都是一樣地工作。習(xí)慣上，我們說使用LR(0)表的分析器為LR(0)分析器，使用SLR(1)表的分析器為SLR(1)分析器，使用LR(1)表的分析器為LR(1)分析器，使用LALR表的分析器為LALR分析器。返回2、LR(0)分析器 我們希望僅由一種只概括“歷史”資料而不包含推測性“展望”材料的簡單狀態(tài)就能識別呈現(xiàn)在棧頂?shù)哪承┚浔R(0)分析法即是基于只根據(jù)“歷史”資料即可決定當(dāng)前分析棧是否已構(gòu)成句柄，從而確定分析動作。（1）LR(0)分析器的實現(xiàn)原理前綴、活前綴與可歸前綴字的前綴是指該字的任意首部。 如：字abc的前綴有ε、a、ab或abc。所謂活前綴是指規(guī)范句型的一個前綴，且這種前綴不含句柄之后的任何符號。之所以稱為活前綴，是因為在其右邊增添一些符號之后，就可以使它成為一個規(guī)范句型。2、LR(0)分析器

也就是說，若 是文法G的一個規(guī)范推導(dǎo)，并且符號串γ是αβ的前綴，則稱γ是G的一個活前綴，即γ是規(guī)范句型αβω的一個前綴，但它的右端不超過該句型句柄β的末端。在LR分析中，實際上是把αβ的前綴放在符號棧中，一旦在棧中出現(xiàn)αβ，即形成句柄β，就用產(chǎn)生式A→β歸約。2、LR(0)分析器活前綴與句柄間的三種關(guān)系：活前綴中已含有句柄的全部符號，這是一個特殊的活前綴，是當(dāng)前句型的最長活前綴，通常稱為可歸前綴。活前綴中只含有句柄的一部分符號。活前綴中不包含句柄的任何符號。 對于一個文法G，我們可以構(gòu)造一個有限自動機(jī)來識別G的所有活前綴，然后，我們再討論如何把這種自動機(jī)轉(zhuǎn)變成LR分析表。意味著期望從余留輸入串中看到某一產(chǎn)生式A→α中的α符號串。意味著形如A→β1β2的產(chǎn)生式右部的左子串β1已出現(xiàn)在棧頂，正期待著從余留輸入串中看到由β2推出的符號串。表明句柄β已出現(xiàn)在棧頂，分析動作應(yīng)是用產(chǎn)生式A→β進(jìn)行歸約。2、LR(0)分析器LR(0)項目在文法G的每個產(chǎn)生式的右部適當(dāng)位置添加一個圓點稱為G的一個LR(0)項目。 例如，產(chǎn)生式對應(yīng)有四個項目：若干個項目組成的集合稱為項目集。例如：對于左邊產(chǎn)生式的4個項目即構(gòu)成一個項目集。2、LR(0)分析器

【注意】產(chǎn)生式只對應(yīng)一個項目。從直觀意義上講，一個LR(0)項目指明了在分析過程中的某個產(chǎn)生式的多大部分被識別，LR(0)項目中的圓點可看成是分析棧棧頂與輸入串的分界線，圓點左邊為已進(jìn)入分析棧的部分，右邊是當(dāng)前輸入或繼續(xù)掃描的符號串。2、LR(0)分析器四類不同的項目 不同的LR(0)項目反映了分析棧的不同情況。我們根據(jù)LR(0)項目的作用不同，將其分為4類：2、LR(0)分析器【例5.11】

構(gòu)造以下文法的所有LR(0)項目，并指出每個項目的類型。解：歸約項目：(2)(5)(7)接受項目：(2)移進(jìn)項目：(3)(6) 待約項目：(1)(4) 2、LR(0)分析器從LR(0)項目構(gòu)造識別文法G的所有可歸前綴的有限自動機(jī) 可以使用LR(0)項目作為狀態(tài)構(gòu)造一個NFA，用來識別這個文法的所有活前綴。其步驟如下：令S是文法G的開始符號，向文法加入一個產(chǎn)生式S?→S，S?為新的文法的開始符號。然后，令項目S?→?S為NFA的唯一初態(tài)。令所有LR(0)項目分別對應(yīng)NFA的一個狀態(tài)，且LR(0)項目是歸約項目的對應(yīng)狀態(tài)為終態(tài)。若狀態(tài)i和狀態(tài)j出自文法G的同一產(chǎn)生式且這兩個狀態(tài)的LR(0)項目的圓點只相差—個位置，即：若則從狀態(tài)i引一條標(biāo)記為Xi的弧到狀態(tài)j。若Xi∈VN

，則從狀態(tài)i引ε弧到所有Xi→?α的狀態(tài)。

再使用第三章的方法將NFA確定化、最小化，得到一個識別該文法的最小化DFA。ij2、LR(0)分析器（2）LR(0)項目集規(guī)范族的構(gòu)造 構(gòu)成識別一個文法G可歸前綴的最小化DFA項目集（狀態(tài)）的全體稱為文法G的LR(0)項目集規(guī)范族。其構(gòu)造方法如下：拓廣文法 文法G是一個以S為開始符號的文法，拓廣G為G?（包含整個G），增加一個不出現(xiàn)在G中的非終結(jié)符S?，并加進(jìn)一個新產(chǎn)生式S?→S。S?為G?的開始符號，稱G?為G的拓廣文法。定義和構(gòu)造I的閉包

假定I是文法G的任一項目集，定義和構(gòu)造I的閉包CLOSURE(I)的方法是：I中的任何項目都屬于CLOSURE(I)；若A→α?Bβ（B∈VN）屬于CLOSURE(I)，那么，對任何關(guān)于B的產(chǎn)生式B→γ，項目B→?γ也屬于CLOSURE(I)；重復(fù)執(zhí)行上述兩步驟直至CLOSURE(I)不再增大為止。2、LR(0)分析器

例如，對于文法：若則2、LR(0)分析器GO函數(shù)（狀態(tài)轉(zhuǎn)換函數(shù)） 假設(shè)I是一個項目集，X是文法G的一個文法符號，則定義狀態(tài)轉(zhuǎn)換函數(shù)GO(I,X)如下：GO(I,X)=CLOSURE(J)其中J={任何形如A→αX?β的項目|A→α?Xβ屬于I}

例如，對于文法： 設(shè) 則2、LR(0)分析器LR(0)項目集規(guī)范族的構(gòu)造 通過函數(shù)CLOSURE和GO很容易構(gòu)造一個文法的拓廣文法的LR(0)項目集規(guī)范族C，步驟如下：

Step1：初始化：令C=CLOSURE({S?→?S})；

Step2：對C中每一個項目集I和文法中任意文法符號X應(yīng)用狀態(tài)轉(zhuǎn)換函數(shù)GO(I,X)，得到新的項目集J，若J非空且不在C中，則將其加入到C中；

Step3：重復(fù)Step2直到C不再增大為止。2、LR(0)分析器LR(0)項目集規(guī)范族的構(gòu)造 為了能夠有效地使用以上步驟計算LR(0)項目集規(guī)范族C，我們借助一個項目棧來存儲構(gòu)造過程中加入的每一個新的項目集，計算的每一步是先將棧頂項彈出，記為I，然后對文法中每個文法符號X，如果GO(I,X)非空且不屬于C中，則將GO(I,X)加入到C中，并將其壓入棧中，重復(fù)以上過程，直到棧空為止。形式化算法描述如下：2、LR(0)分析器形式化算法描述

voidItemSets(G?){//計算文法的項目集規(guī)范族C I=CLOSURE({S?→?S}); C={I}; //初始規(guī)范族C Push(I); //將項目集I壓入棧中 while(!Empty(ItemStack)){ //只要棧不空就執(zhí)行以下步驟 Pop(I); //將當(dāng)前棧頂項目集彈出并置于I中 for(G中每個文法符號X){ J=GO(I,X);//計算GO函數(shù) if(J非空且J不屬于C中){ 將J加入到C中; Push(J);//將項目集J壓入棧中 } } }}2、LR(0)分析器LR(0)分析表的構(gòu)造“移進(jìn)-歸約”沖突和“歸約-歸約”沖突若同時存在移進(jìn)項目和歸約項目，即有形如A→α?aβ和B→γ?的項目，則稱文法G含有移進(jìn)-歸約沖突。此時，當(dāng)面臨輸入符號a時，分析程序的控制器不能確定是把a(bǔ)移進(jìn)符號棧還是把γ歸約成B。若同時存在一個以上的歸約項目，即有形如A→ω?和B→γ?的項目，則稱文法G含有歸約-歸約沖突。此時，不論面臨什么樣的輸入符號，分析程序的控制器不能確定是把ω歸約成A，還是把歸γ約成B。 若一個文法G的拓廣文法G?的識別可歸前綴的DFA的每一個狀態(tài)（項目集）不存在任何沖突，即不存在移進(jìn)-歸約沖突和歸約-歸約沖突，則稱G是一個LR(0)文法。2、LR(0)分析器LR(0)分析表的構(gòu)造

假定C={I0,I1,…,In}，由于我們已經(jīng)習(xí)慣用數(shù)字表示狀態(tài)，因此，令每個項目集Ik的下標(biāo)k作為分析器的狀態(tài)。特別地，令那個包含項目S?→?S的集合Ik的下標(biāo)k為分析器的初態(tài)。分析表的ACTION子表和GOTO子表可按如下方法構(gòu)造： 規(guī)則一：若項目A→α?aβ（a∈VT）屬于Ik且GO(Ik,a)=Ij，則置ACTION[k,a]=sj，表示將(j,a)移進(jìn)分析棧。 規(guī)則二：若項目A→α?屬于Ik，且文法G?中產(chǎn)生式A→α的編號為j，則對任何終結(jié)符a（包括輸入串結(jié)束符#），置ACTION[k,a]=rj，表示按文法的第j個產(chǎn)生式（A→α）進(jìn)行歸約。 規(guī)則三：若項目S?→S?屬于Ik，則置ACTION[k,#]=acc，表示“接受”。 規(guī)則四：若GO(Ik,A)=Ij，A∈VN，則置GOTO[k,A]=j。 規(guī)則五：分析表中凡不能用規(guī)則1至4填入信息的空白格均置上“出錯標(biāo)志”。2、LR(0)分析器 由于假定LR(0)文法規(guī)范族的每個項目集不含任何沖突項目，因此按上述方法構(gòu)造的分析表的每個入口都是唯一的（即不含多重定義）。我們稱如此構(gòu)造的分析表是一張LR(0)表。使用LR(0)表的分析器叫做一個LR(0)分析器。【例5.12】

設(shè)文法G[S]為：試構(gòu)造文法G[S]的LR(0)分析表。2、LR(0)分析器解：(1)拓廣文法：將G[S]拓廣為G[S?]，并對各產(chǎn)生式進(jìn)行編號：S?→SS→aAS→bBA→cAA→dB→dBB→e2、LR(0)分析器(2)構(gòu)造LR(0)項目集規(guī)范族C和GO函數(shù):I0:S?→?SS→?aAS→?bBI1:S?→S?I2:S→a?AA→?cAA→?dI3:S→b?BB→?dBB→?eI4:S→aA?I5:A→c?AA→?cAA→?dI10:A→cA?I6:A→d?I7:S→bB?I8:B→d?BB→?dBB→?eI11:B→dB?I9:B→e?SabAcdAcdBdeedB①S?→S②S→aA③S→bB④A→cA⑤A→d⑥B→dB⑦B→e2、LR(0)分析器(3)構(gòu)造LR(0)分析表s2s31accs5s64s8s97r2r2r2r2r2r2s5s610r5r5r5r5r5r5r3r3r3r3r3r3s8s911r7r7r7r7r7r4r4r4r4r4r4r6r6r6r6r6r6r7①S?→S②S→aA③S→bB④A→cA⑤A→d⑥B→dB⑦B→e返回3、SLR(1)分析器

LR(0)文法是一類非常簡單的文法，它要求文法的識別可歸前綴DFA的每一個狀態(tài)（項目集）都不含沖突性的項目，這樣才能構(gòu)造出不含沖突動作的LR(0)分析表。因此，LR(0)文法的適用性受到很大的限制，對于通常的程序設(shè)計語言來說，一般都不能用LR(0)文法來描述。當(dāng)某個項目集中存在沖突項，就需要向前展望部分材料（一般只需向前查看一個符號）來解決沖突，不同的解決方法就產(chǎn)生了不同的分析算法，主要有SLR(1)和LR(1)方法。

SLR(1)分析法是一種帶有簡單展望材料的分析法，其中，“S”表示簡單的，“1”表示分析的每一步至多向前看一個輸入符號。3、SLR(1)分析器（1）引例【例5.13】試構(gòu)造文法的LR(0)分析表。解：(1)拓廣文法 S?→AA→aAA→a(2)構(gòu)造LR(0)項目集規(guī)范族I0:S?→?AA→?aAA→?aI1:S?→A?I2:A→a?AA→a?A→?aAA→?aI3:A→aA?s21accr3r33s2r2r2aAAa(3)構(gòu)造LR(0)分析表存在移進(jìn)——歸約沖突3、SLR(1)分析器（2）SLR(1)規(guī)則

一般而言，假定LR(0)項目集規(guī)范族的一個項目集I中含有m個移進(jìn)項目：同時含有n個歸約項目：3、SLR(1)分析器（2）SLR(1)規(guī)則

如果集合：{a1,a2,…,am}，F(xiàn)OLLOW(B1)，F(xiàn)OLLOW(B2)，…，F(xiàn)OLLOW(Bn)兩兩不相交（包括不得有兩個FOLLOW集合有#），則隱含在I中動作沖突可通過檢查現(xiàn)行輸入符號a屬于上述n+1個集合中的哪個集合而獲得解決。這就是： 規(guī)則一：若a=ai（i=1,2,…,m），則置ACTION[I,a]=“移進(jìn)”； 規(guī)則二：若a∈FOLLOW(Bj)（j=1,2,…,n），則置ACTION[I,a]=“用產(chǎn)生式Bj→α歸約”； 規(guī)則三：其余情況，則置ACTION[I,a]=“出錯標(biāo)志”。 這種用來解決分析動作沖突的方法稱為SLR(1)規(guī)則。3、SLR(1)分析器（3）SLR(1)分析表的構(gòu)造

首先將文法G拓廣為文法G?，再對G?構(gòu)造LR(0)項目集規(guī)范族C和識別可歸前綴DFA的轉(zhuǎn)換函數(shù)GO。然后，使用C和GO按下面的算法構(gòu)造SLR(1)分析表。 假定C={I0,I1,…,In}，令每個項目集Ik的下表k為分析器的一個狀態(tài)，因此，G?的SLR分析表含有狀態(tài)0,1,…,n。令那個含有項目S?→?S的Ik的下標(biāo)k為初態(tài)。分析表的ACTION子表和GOTO子表可按如下方法構(gòu)造：

規(guī)則一：若項目A→α?aβ（a∈VT）屬于Ik且GO(Ik,a)=Ij，則置ACTION[k,a]=sj，表示將(j,a)移進(jìn)分析棧。

3、SLR(1)分析器（3）SLR(1)分析表的構(gòu)造

規(guī)則二：若項目A→α?屬于Ik，且文法G?中產(chǎn)生式A→α的編號為j，對任何終結(jié)符a（包括輸入串結(jié)束符#），若a∈FOLLOW(A)，則置ACTION[k,a]=rj，表示按文法G?的第j個產(chǎn)生式（A→α）進(jìn)行歸約。

規(guī)則三：若項目S?→S?屬于Ik，則置ACTION[k,#]=acc，表示“接受”。

規(guī)則四：若GO[Ik,A]=Ij，A∈VN，則置GOTO[k,A]=j。

規(guī)則五：分析表中凡不能用規(guī)則1至4填入信息的空白格均置上“出錯標(biāo)志”。 按上述算法構(gòu)造的LR分析表，如果每個入口不含多重定義，則稱它為文法G的一張SLR(1)分析表，具有SLR(1)分析表的文法G稱為一個SLR(1)文法。使用SLR(1)分析表的分析器叫做一個SLR(1)分析器。 3、SLR(1)分析器

【例5.14】

試構(gòu)造表達(dá)式文法的SLR(1)分析表，并說明是否為SLR(1)文法。解：(1)拓廣文法

①E?→E ②E→E+T ③E→T ④T→T*F ⑤T→F ⑥F→(E) ⑦F→i

(2)構(gòu)造LR(0)項目集規(guī)范族和GO函數(shù)3、SLR(1)分析器I0:E?→?EE→?E+TE→?T

T→?T*FT→?FF→?(E)F→?iI1:E?→E?E→E?+TI2:E→T?

T→T?*FI3:T→F?I5:F→i?I6:E→E+?TT→?T*FT→?FF→?(E)F→?iI9:E→E+T?T→T?*FI8:F→(E?)E→E?+TI10:T→T*F?I11:F→(E)?EFT(i+I7:T→T*?FF→?(E)F→?iI4:F→(?E)E→?E+TE→?T

T→?T*FT→?FF→?(E)F→?i*EFi(TF(iF(i)+*①E?→E②E→E+T③E→T④T→T*F⑤T→F⑥F→(E)⑦F→iT3、SLR(1)分析器

(3)計算G[E?]的每個非終結(jié)符的FOLLOW集3、SLR(1)分析器

(4)構(gòu)造SLR(1)分析表①E?→E ②E→E+T ③E→T ④T→T*F⑤T→F ⑥F→(E) ⑦F→is5s4123s6accs7r3r3r3r5r5r5r5s5s4r7r7r7r7823s5s493s5s410s6s11r2s7r2r2r4r6r4r6r4r6r4r6單擊圖片可放大縮小返回4、LR(1)分析器

在SLR(1)沖突解決方案中，若項目集Ik中含有歸約項目“A→α?”，那么當(dāng)狀態(tài)k呈現(xiàn)于棧頂時，只要當(dāng)前所面臨的輸入符號a滿足條件a∈FOLLOW(A)，就確定采取“用產(chǎn)生式A→α進(jìn)行歸約”的動作。然而，在有些情況下，當(dāng)狀態(tài)k呈現(xiàn)于棧頂時，棧里的符號串所構(gòu)成的活前綴未必允許將α歸約為A，因為，可能沒有一個規(guī)范句型含有前綴βAa。因此，在這種情況下，用A→α進(jìn)行歸約未必有效。 因此，我們需要讓每個狀態(tài)含有更多的“展望”信息，這些信息將有助于克服動作沖突和排除那種用A→α所進(jìn)行的無效歸約，在必要時對狀態(tài)進(jìn)行分裂，使得LR分析器的每個狀態(tài)能夠確切地指出當(dāng)后跟哪些終結(jié)符時才允許把α歸約為A。4、LR(1)分析器（1）LR(k)項目 令每個項目都附帶有k個終結(jié)符，其一般形式為 此處，A→α?β是一個LR(0)項目，ai∈VT（i=1,2,…,k）。這樣的項目稱為一個LR(k)項目，項目中的a1a2…ak稱為它的向前搜索符串（或展望串）。向前搜索符串僅對歸約項目有意義。對于任何移進(jìn)或待約項目[A→α?β,a1a2…ak]，β≠ε，搜索符串a(chǎn)1a2…ak不起作用。歸約項目[A→α?,a1a2…ak]意味著當(dāng)它所屬的狀態(tài)呈現(xiàn)在棧頂且后續(xù)的k個輸入符號為a1a2…ak時，才可以把棧頂?shù)摩翚w約為A。這里，我們只對k≤1的情形感興趣，因為對多數(shù)程序語言的語法來說，向前搜索（展望）一個符號就基本可以確定“移進(jìn)”或“歸約”。4、LR(1)分析器（2）CLOSURE(I)的計算 假定I是一個LR(1)項目集，它的閉包CLOSURE(I)可按如下方法構(gòu)造： ①I中的任何項目都屬于CLOSURE(I)； ②若項目[A→α?Bβ，a]屬于CLOSURE(I)，B→γ是一個產(chǎn)生式，那么，對于FIRST(βa)中的每個終結(jié)符b，如果項目[B→?γ，b]原來不在CLOSURE(I)中，則把它加進(jìn)去。 ③重復(fù)執(zhí)行步驟②，直至CLOSURE(I)不再增大為止。 【注意】 b可能是從β推出的第一個終結(jié)符，若，則b=a。4、LR(1)分析器（3）GO函數(shù)的計算 令I(lǐng)是一個LR(1)項目集，X是一個文法符號，則函數(shù)GO(I,X)定義為

其中

J={任何形如[A→αX?β，a]的項目|[A→α?Xβ，a]∈I}4、LR(1)分析器（4）LR(1)項目集規(guī)范族C的構(gòu)造 通過函數(shù)CLOSURE和GO很容易構(gòu)造一個文法G的拓廣文法G?的LR(1)項目集規(guī)范族C，步驟如下：①初始化：令C=CLOSURE({[S?→?S，#]})；②對C中每一個項目集I和文法中任意文法符號X應(yīng)用狀態(tài)轉(zhuǎn)換函數(shù)GO(I,X)，得到新的項目集J，若J非空且不在C中，則將其加入到C中；③重復(fù)步驟②直到C不再增大為止。 類似于計算LR(0)項目集規(guī)范族，我們?nèi)匀唤柚粋€項目棧來存儲每一個新的項目集，計算的每一步是先將棧頂項彈出，記為I，然后對文法中每個文法符號X，如果GO(I,X)非空且不在C中，則將其加入到C中并壓入棧中，重復(fù)以上過程，直到棧空為止。4、LR(1)分析器形式化算法描述如下：voidItemSets(G?){//計算文法G?的項目集規(guī)范族C I=CLOSURE({[S?→?S，#]}); C={I}; //初始規(guī)范族C Push(I); //將項目集I壓入棧中 while(!Empty(ItemStack)){//只要棧不空就執(zhí)行以下步驟 Pop(I);//將當(dāng)前棧頂項目集彈出并置于I中 for(G中每個文法符號X){ J=GO(I,X);//計算GO函數(shù) if(J非空且J不屬于C中){ 將J加入到C中; Push(J);//將項目集J壓入棧中 } } }}4、LR(1)分析器（5）LR(1)分析表的構(gòu)造 假定C={I0,I1,…,In}，令每個項目集Ik的下標(biāo)k作為分析器的狀態(tài)。令那個包含項目[S?→?S，#]的集合Ik的下標(biāo)k為分析器的初態(tài)。分析表的ACTION子表和GOTO子表可按如下方法構(gòu)造：規(guī)則一：若項目[A→α?aβ，b]（a∈VT）屬于Ik且GO(Ik,a)=Ij，則置ACTION[k,a]=sj，表示將(j,a)移進(jìn)分析棧。規(guī)則二：若項目[A→α?，a]