復(fù)習(xí)-編譯原理第4章

2025/1/7編譯原理1計算機學(xué)院厚德和諧礪學(xué)創(chuàng)新編譯原理

CompilerPrinciples

任課教師：鄭麗萍2014－2015第2學(xué)期2025/1/7編譯原理2句型分析：就是識別一個符號串是否為某文法的句型，是某個推導(dǎo)（歸約）的構(gòu)造過程。分析程序(識別程序)：在語言的編譯實現(xiàn)中，完成句型分析的程序。從左到右的分析算法：總是從左到右地識別輸入符號串，首先識別符號串中的最左符號，進(jìn)而依次識別右邊的一個符號，直到分析結(jié)束。

語法分析的方法一、基本概念2025/1/7編譯原理3自上而下分析法從文法的開始符號出發(fā)，反復(fù)使用文法的產(chǎn)生式，為待識別句子建立一個最左推導(dǎo)，以尋找與輸入符號串匹配的推導(dǎo)。自下而上分析法從輸入符號串開始，逐步進(jìn)行歸約，從葉子節(jié)點，由底上向上逐步建立一棵完整的語法樹，直至歸約到文法的開始符號（樹根）。二、語法分析的兩種方法2025/1/7編譯原理4自頂向下分析方法的基本缺點不能處理具有左遞歸性的文法文法G，存在U∈VN，ifU==>U…,則G為左遞歸文法+

一、左遞歸文法

左遞歸文法回溯問題一般方法面臨問題及解決2025/1/7編譯原理5

要實行自頂向下分析，必須要消除文法的左遞歸，不僅消除直接左遞歸，而且消除間接左遞歸。

直接左遞歸

若P→P

α|β

α、β∈V*且β不以P開頭串的特點 βα...α

間接左遞歸若P=>Pα

例如：S→Aa

A→Sb|b

*如果文法具有間接左遞歸，則也將發(fā)生上述問題。2025/1/7編譯原理6二、回溯問題1什么是回溯?

分析工作要部分地或全部地退回去重做叫回溯。

嚴(yán)重的效率低，只有在理論上的意義而無實際意義。U::=aβ1|a

β

2|a

β

32造成回溯的條件?3回溯帶來的問題?

文法中，對于某個非終結(jié)符號的規(guī)則其右部有多個選擇，并根據(jù)所面臨的輸入符號不能準(zhǔn)確的確定所要選擇時，就可能出現(xiàn)回溯。2025/1/7編譯原理71)語法分析要重做2)語法處理工作要推倒重來

因此自頂向下的一般分析方法不能處理左遞歸、復(fù)雜的回溯技術(shù)、回溯導(dǎo)致語義工作推倒重來、難以報告出錯的確切位置、效率低。欲采用此方法，必須：1、消除左遞歸；

2、消除回溯4效率低的原因2025/1/7編譯原理8消除文法的左遞歸產(chǎn)生式方法：改寫產(chǎn)生式，使產(chǎn)生式不含左遞歸。法一：P→Pα|β產(chǎn)生式的符號串為βα...α引入一元語言符號｛｝，{x}表示x可出現(xiàn)任意次。則：P→Pα|β改寫為P→β{α}例1：S→AcA→Aa|b

改為：S→AcA→b{a}一、消除直接左遞歸例2：E→E+T|TT→T*F|F

消除左遞歸：

E→T{+T}T→F{*F}2025/1/7編譯原理9法二：對左遞歸

A→Aα|β的非終結(jié)符A，引入一個新的非終結(jié)符A’，使得：

A→Aα|β

等價寫成：一般地：若其中βi均不以A打頭，則：A→βA’

A’→αA’|ε2025/1/7編譯原理10i)已知U→xy|xw|…|xz

解：U→x(y|w|…|z)

得：U→xU’U’→y|w|…|zii)已知U→x|xy

解：U→x(y|ε)法二步驟總結(jié)

使用提因子法，不僅有助于消除直接左遞歸。而且有助于壓縮文件的長度，使我們更加有效的分析句子。Step1：提因子2025/1/7編譯原理11若：P→P

|

則可改寫為：P→

P’P’→

P’|ε例

E

E+T|T T

T*F|F F

(E)|id消除左遞歸后文法

E

TE

E

+TE

|

T

FT

T

*FT

|

F

(E)|id注意：此方法只能消除出現(xiàn)在產(chǎn)生式的全部直接左遞歸，不能消除經(jīng)兩步或多步推導(dǎo)所出現(xiàn)的一切間接左遞歸。Step1：將左遞歸規(guī)則改為右遞歸2025/1/7編譯原理12二、消除間接左遞歸1間接左遞歸產(chǎn)生原因產(chǎn)生式右邊首符號為非終結(jié)符；(存在回路)前面非終結(jié)符引用后面非終結(jié)符，后面非終結(jié)符引用前面非終結(jié)符。例1：S→Ac|c(1)

A→Bb|b(2)B→Sa|a(3)對例1：

B→Sa|a帶入(2)，得A→Sab|ab|b

帶入S產(chǎn)生式，得S→Sabc|abc|bc|c

對S消除直接左遞歸得：

S→(abc|bc|c)S’S’→abcS’|ε2消除方法

找出所有引用前面非終結(jié)符的產(chǎn)生式進(jìn)行代換，即先變換成直接左遞歸。2025/1/7編譯原理13一、消除回溯的途徑

改寫文法對具有多個候選式右部反復(fù)提取左因子，使其具有不同首符號例1U→xV|xWU,V,W∈Vn,x∈Vt改寫為：

U→x(V|W)

更清楚表示

U→xZZ→V|W注意：要進(jìn)一步檢查V和W的首符號集是否相交，若相交，則要再次提取左因子。回溯的消除及LL(1)文法2025/1/7編譯原理14一般的，對于有公共左因子的文法A

a

1|a

2|…

a

k|γ，其中γ不以a開頭，

a∈V。提左因子：判斷adeS

aA

adA‘a(chǎn)de例：A

d|de|f改為：A

dA’|fA’

ε|e

A

aA

|γA

1|

2

|…

k若

1

2…

k還有某些候選式有相同首符號，則依次提取，直到每個候選式的首符號不同為止。注意：提取公因子會引入大量非終結(jié)符和ε產(chǎn)生式?；厮莸南癓L(1)文法2025/1/7編譯原理151定義

FIRST(X)={a|a∈VT且Xa，X，∈V*}

特別的：X

，則

FIRST(X)

對文法G的所有非終結(jié)符的每個候選式X其首符號集為FIRST(X)。對A的任何兩個不同的選擇

i

和

j，希望有

FIRST(

i)

FIRST(

j)=

此時，當(dāng)要求A匹配輸入串時，A就可根據(jù)所面臨第一個輸入符號a，準(zhǔn)確指派某個候選式推導(dǎo)，該候選式即為a∈FIRST(X)的X候選式。二、FIRST集**回溯的消除及LL(1)文法2025/1/7編譯原理162FIRST（X）構(gòu)造方法1).若X

V

，則FIRST(X)={X}；2).若X

VN，且有X

a…，則{a}∪FIRST(X)；a可為；3).若有X

Y1Y2…YK

，Yi

VN

(1≤i≤K)，則

(FIRST(Y1)－{

})

∪

FIRST(X);

若

FIRST(Y1)，則(FIRST(Y2)－{

})

∪

FIRST(X)；同樣，若

FIRST(Yj)(1≤j<K)，(FIRST(Yj＋1)－{

})

∪

FIRST(X)；特別的，若所有的FIRST(Yj)(j=1,2,…,K)均含有

，則把

加到FRIST(X)中。反復(fù)使用上述2、3步，直到每個符號的FIRST集不再增大為止。2025/1/7編譯原理171定義

FOLLOW(A)={a|S

…Aa…，a

VT}

特別的：若S

…A，則#

FOLLOW(A)

FOLLOW(A)={aS=>A且a∈

FRIST(),∈V*,

∈V*

}若S=>

uA，且

=>ε，則#∈FOLLOW(A)三、FOLLOW集對文法G的所有含有ε產(chǎn)生式的非終結(jié)符A定義它的FOLLOW(A)。對含有ε的A的所有候選式

i

，希望有

FIRST(

i

)

FOLLOW(A

)=

*****2025/1/7編譯原理181).文法的開始符號S，置{#}∪FOLLOW(S)；當(dāng)A∈VN為句型的尾符號時，則#∈FOLLOW（A）2).對于B

αAβ，則

(FIRST(β)－{})∪

FOLLOW(A)；3).對于B

αA，或B

αAβ而

FIRST(β)，則把FOLLOW（B）加至FOLLOW（A）中。反復(fù)使用2、3步，直到每個非終結(jié)符的FOLLOW集不再增大為止。2FOLLOW(A)構(gòu)造方法2025/1/7編譯原理19

四、LL(1)文法2、若β==>ε,則FIRST(α)∩FOLLOW(A)=Ф*定理：文法G是LL(1)文法的充分必要條件是：對于G的每一個非終結(jié)符A的任意兩條規(guī)則A→α|β,下列條件成立：1、FIRST(α)∩FIRST(β)=Ф2025/1/7編譯原理20

1LL(1)含義：

L：從左至右順序掃描輸入串；

L：按最左推導(dǎo)方式；

1：每一次推導(dǎo)均向前查看一個輸入符號準(zhǔn)確指派產(chǎn)生式。

2LL(1)文法性質(zhì):

沒有公共左因子；無二義性；不含左遞歸。對LL(1)文法，可構(gòu)造一個無回溯自頂向下語法分析程序，方法為：預(yù)測分析法（LL(1)分析法）2025/1/7編譯原理21LL(1)分析方法是一種比遞歸子程序法更有效的自頂向下分析方法。LL(1)分析使用一個下推棧而不是遞歸調(diào)用來完成分析。名稱中第一個L表示自左向右順序掃描輸入符號串，第二個L表示分析過程產(chǎn)生一個句子的最左推導(dǎo)。括號中的1表示每進(jìn)行一步推導(dǎo)，只需要向前查看一個輸入符號，便能確定當(dāng)前所應(yīng)選用的規(guī)則。

預(yù)測分析法2025/1/7編譯原理22LL(1)分析器由一個總控程序（表驅(qū)動程序）、一張分析表（預(yù)測分析表、LL(1)分析表）和一個分析棧組成。輸入符號串：分析棧a1a2…………an#

XZS#LL（1）總控程序分析表輸出流棧中存放文法的符號串，棧底符號是#待分析串，從左到右掃描是一個兩維數(shù)組M[A,a],A是非終結(jié)符，a是終結(jié)符或#LL(1)分析的基本方法2025/1/7編譯原理23輸入符號串:指要分析的輸入符號串，它以右界符#作為結(jié)尾。分析棧：用來存放一系列文法符號。分析開始時，先將#入棧，然后再將文法的開始符號入棧。輸出流：分析過程中使用的產(chǎn)生式序列。總控程序：分析器對輸入串的分析靠總控程序完成.根據(jù)分析棧的棧頂符號X和當(dāng)前的輸入符號a，總控程序按照分析表的指示來決定分析器的動作。工作過程如下：2025/1/7編譯原理24第一步初始化:分析開始時，首先將符號#及文法的開始符號S依次置于分析棧的底部，并把各指示器調(diào)整至起始位置，如圖1所示。然后，反復(fù)執(zhí)行第二步的操作。

輸入符號串：

a1a2…………an#分析棧：

S#圖1分析開始時狀況第二步假設(shè)分析的某一步，分析棧及余留的符號串如圖2：aiai+1…………an##X1X2…Xm-1Xm

圖2分析進(jìn)行中的狀況2025/1/7編譯原理25(1)若Xm∈Vn，則查分析表的Xm行ai列，假設(shè)M[Xm，ai]為產(chǎn)生式Xm→Y1Y2…Yk，則將Xm出棧，并將Y1Y2…Yk反序入棧，如圖3；若M[Xm，ai]為ERROR，則出錯。aiai+1…………an##X1X2…Xm-1YkYk-1…Y1

圖3反序入棧(2)若Xm=ai≠#，表示棧頂與掃描的符號匹配，則棧頂符號Xm出棧，輸入指示器指向下一個符號，否則(即Xm≠ai)出錯。(3)若Xm=ai=#，表示輸入串完全匹配，分析成功。2025/1/7編譯原理261分析表：可用一個二維數(shù)組表示，它的每一行與文法的一個非終結(jié)符相關(guān)聯(lián)，每一列則與文法的一個終結(jié)符號或界符“#”相關(guān)聯(lián)。元素：M[A，a]＝文法產(chǎn)生式|error（A∈VN，a∈VT∪{#}）基本思想

當(dāng)文法中某一非終結(jié)符呈現(xiàn)在棧頂時,根據(jù)當(dāng)前的輸入符號，分析表應(yīng)指示要用該非終結(jié)符的哪一條候選式匹配輸入串(即進(jìn)行下一步最左推導(dǎo))

根據(jù)這個思想，我們可以構(gòu)造分析表算法!預(yù)測分析表的構(gòu)造2025/1/7編譯原理27

分析表元素M[A,a](A∈VN,a∈VT∪#)，按下述規(guī)則確定：對于文法中的每個產(chǎn)生式A→γ1|γ2|……|γm1）若a∈First(γi)，則置M[A,a]=“A→γi”2）若

∈First(γj)，且a∈Follow(A)，則M[A,a]=“A→

”3）除上述兩種情況外，其余的一切表元素均置為error。2預(yù)測分析表構(gòu)造算法預(yù)測分析表各元素含義為：或指出當(dāng)前推導(dǎo)所應(yīng)使用的產(chǎn)生式，或指出輸入符號串中存在著語法錯誤.2025/1/7編譯原理28注：1）用分析表構(gòu)造算法可以為任意文法G構(gòu)造其分析表M2）若文法為非LL(1)文法，則構(gòu)造出的M包含有多重元素。則分析過程有回溯?？梢宰C明：一個文法G的預(yù)測分析表不含多重元素，當(dāng)且僅當(dāng)該文法是LL(1)的。2025/1/7編譯原理29五、結(jié)論對LL(1)文法，總能構(gòu)造預(yù)測分析表，且表中不含多重元素。對非LL(1)文法，盡管可為其建立預(yù)測分析表，但表中必出現(xiàn)多重元素。非LL(1)文法所造表中,必有沖突元素。事實上,是否有沖突元素也是判別一文法是否是LL(1)文法的方法之一。對某些非LL(1)文法，可通過消除左遞歸，反復(fù)提取左因子等方法將其改造成LL(1)文法。但是，并非所有的非LL(1)文法都能改造為LL(1)文法。六、非LL(1)文法的改造2025/1/7編譯原理30從輸入串開始，進(jìn)行最左歸約，直到到達(dá)文法的開始符號為止。大致過程：把輸入符號逐個移進(jìn)到一個棧里，當(dāng)棧頂形成某個產(chǎn)生式的右部（句柄）時，把棧頂?shù)倪@一部分替換成（歸約為）它的左部符號。稱作“移進(jìn)—歸約”分析。

自下而上分析過程語法分析程序查找規(guī)約串依據(jù)

a+b……#輸出帶#2025/1/7編譯原理31“移進(jìn)-歸約”分析對符號棧的使用有四類操作：移進(jìn)、歸約、接受和出錯處理?！耙七M(jìn)一歸約”分析器使用一個棧和一個存放輸入符號串w的緩沖器。工作過程：自左至右將串w的符號依次入棧，一旦棧頂形成句柄即歸約。歸約可持續(xù)多次，直至棧頂不再呈現(xiàn)句柄為止。然后，繼續(xù)移進(jìn)符號，重復(fù)這個過程，直至最終形成如下格局：

棧

輸入

#S

#分析過程的每一步，棧中符號串與剩余輸入符號串恰是一個規(guī)范句型。且棧中符號串為該句型的一個活前綴?？偨Y(jié)活前綴：是規(guī)范句型的一個前綴，且不含句柄之后的任何符號

，則稱為該規(guī)范句型的一個活前綴。2025/1/7編譯原理32算符優(yōu)先分析法一、算符文法定義

算符文法CFGG=（VN,VT,P,S）,U,V,W均為非終結(jié)符，x,y均為終結(jié)符。如果CFG(不含空產(chǎn)生式)G中沒有形如U

…VW…的產(chǎn)生式，則稱G為算符文法（OG）。推論：

算符文法的任何句型都不含兩個相鄰的非終結(jié)符。終結(jié)符號a與b之間的優(yōu)先關(guān)系有三種：

a

b表示a的優(yōu)先級低于ba

b表示a的優(yōu)先級等于b

a

b表示a的優(yōu)先級大于b2025/1/7編譯原理33二、算符優(yōu)先關(guān)系定義

在OG（算符優(yōu)先文法）中x?=y

G中有形如U

…xy…或U

…xVy…的產(chǎn)生式。x<?y

G中有形如U

…xW…的產(chǎn)生式,

而Wy….或WVy…x?>y

G中有形如U

…Wy…的產(chǎn)生式,

而W…x或W…xV規(guī)定：若Sx…或SVx…則#<?x

若S…x或S…xV則x?>#2025/1/7編譯原理34三、算符優(yōu)先關(guān)系計算及其表示1定義

FIRSTVT(W)={y|Wy…WVy…}LASTVT(W)={x|W…xW…xV}2三種關(guān)系計算x?=y：U

…xy…或U

…xVy…x<?y：每個非終結(jié)符B的FIRSTVT(B)，形如U

…xB…中，每個y∈FIRSTVT(B)，則有x<?y成立。x?>y：每個非終結(jié)符B的LASTVT(B)，形如U

…By…中，每個x∈LASTVT(B)，則有x?>y成立。2025/1/7編譯原理35對文法的每一非終結(jié)符號構(gòu)造FIRSTVT集和LASTVT集，算法分別如下ⅰ)構(gòu)造FIRSTVT集，置FIRSTVT(A)=φ

若文法中有形如A→b…或A→Bb…的規(guī)則，則b∈FIRSTVT(A)

若文法中有形如A→B…的規(guī)則，則FIRSTVT(B)∈FIRSTVT(A)2025/1/7編譯原理36ⅱ)構(gòu)造LASTVT集，置LASTVT(A)=φ

若文法中有形如A→…a或A→…aB的規(guī)則，則a∈LASTVT(A)

若文法中有形如A→…B的規(guī)則，則LASTVT(B)∈LASTVT(A)(2)ⅰ)形如…aA…的規(guī)則右部，a<FIRSTVT(A)ⅱ)形如…Ab…的規(guī)則右部，LASTVT(A)>bⅲ)形如…ab…或…aAb…的規(guī)則右部，a=b(3)#<FIRSTVT(S)LASTVT(S)>#2025/1/7編譯原理373、

算符優(yōu)先文法在OG文法G中，若任意兩個終結(jié)符間至多只有三種算符優(yōu)先關(guān)系=、<和>中的一種算符優(yōu)先關(guān)系存在，則稱G為算符優(yōu)先文法(OPG)。

算符優(yōu)先文法是無二義的。2025/1/7編譯原理381素短語：至少含有一個終結(jié)符號，并且除自身之外不再含有任何更小的帶有終結(jié)符號的短語，則稱為素短語。2最左素短語：句型最左邊的素短語。算符優(yōu)先文法句型的最左素短語是唯一的。EE+TE+TTT*FFi句型T+T*F+i的語法樹最左素短語不一定是當(dāng)前句型的句柄最左素短語可能不是相應(yīng)文法的任何產(chǎn)生式的右部。按算符優(yōu)先關(guān)系所確定的歸約串恰好是當(dāng)前句型的最左素短語2025/1/7編譯原理39LR分析器概述一、LR分析器構(gòu)成總控程序(驅(qū)動程序)。對所有LR分析器都相同。分析表(分析函數(shù))。不同文法分析表不同，同一文法采用的LR分析器不同時，分析表也將不同。分析棧。包括文法符號棧和相應(yīng)的狀態(tài)棧?？偪爻绦騩utputInput(#)LR分析表ACTIONGOTOS0#SmXm……

狀態(tài)棧符號棧2025/1/7編譯原理401分析表構(gòu)成

動作表(ACTION)

ACTION[S,a]：表示在當(dāng)前狀態(tài)S下，面臨掃描符號a所應(yīng)采取的動作。動作有四種：移進(jìn)、歸約、出錯、接受。

轉(zhuǎn)向表(GOTO)

GOTO[S，X]：若XVT，表示在當(dāng)前狀態(tài)下，讀入a應(yīng)轉(zhuǎn)向什么狀態(tài)；若XVN，表示當(dāng)前棧頂句柄歸約成X后，應(yīng)轉(zhuǎn)向什么狀態(tài)。

移進(jìn)ai和s=goto[sm,ai]進(jìn)棧action[sm,ai]=歸約rj:AXm-r+1Xm-r+2…Xm

接受s=goto[sm-r,A]

出錯2025/1/7編譯原理41注：對于終結(jié)符的轉(zhuǎn)向動作，可與其移進(jìn)動作合并在一起填在動作表中，這樣轉(zhuǎn)向表可進(jìn)行壓縮，只保留非終結(jié)符轉(zhuǎn)向部分。ACTIONGOTOa1a2…anS0S1…SkA1A2…AmS5r4acc282025/1/7編譯原理422LR分析器的總控程序

總控程序的動作由當(dāng)前棧頂狀態(tài)Sm和掃描符號ai查表決定。1）移進(jìn)

把(Sm,ai)的下一狀態(tài)S‘=GOTO[Sm，ai]連同掃描符號進(jìn)棧，棧頂成(S’,ai)，掃描指針后移；2）歸約

用產(chǎn)生式A

進(jìn)行歸約。若

的長度為，則彈出棧頂

項，使棧頂狀態(tài)變?yōu)镾m-，然后將(Sm-,A)的下一狀態(tài)S’=GOTO[Sm-,A]連同A一起入棧，棧頂變?yōu)?S’,A)。掃描指針不動，即不改變現(xiàn)行輸入符號。3）接受

4）報錯注：不管哪一類分析程序，總控程序的動作都一樣。2025/1/7編譯原理43LR分析總結(jié)

特征規(guī)范的；符號棧中的符號是規(guī)范句型的前綴，且不含句柄以后的任何符號(活前綴)；分析決策依據(jù)――棧頂狀態(tài)和現(xiàn)行輸入符號。識別活前綴的DFA.

四種技術(shù)

LR(0)SLR(1)LR(1)2025/1/7編譯原理44

在規(guī)范歸約的句型中，不含有句柄以后任何符號的前綴稱為活前綴。它有兩種情況：歸態(tài)活前綴和非歸態(tài)活前綴。

歸態(tài)活前綴

活前綴尾部正好是句柄之尾，這時可進(jìn)行歸約。歸約后又會成為另一句型的活前綴。

非歸態(tài)活前綴

句柄尚未形成，需要繼續(xù)移進(jìn)若干符號后才能形成。

活前綴2025/1/7編譯原理45一、LR(0)分析表的基本策略

狀態(tài)DFA狀態(tài)的轉(zhuǎn)換構(gòu)造文法G的一個DFA，用于識別所有活前綴。由若干LR(0)項目所組成的集合(項目集)來表示。由分析過程中的移進(jìn)－歸約操作引發(fā)。LR(0)分析表的構(gòu)造2025/1/7編譯原理46定義：對文法G的每個產(chǎn)生式右部添加一個圓點，稱為G的一個LR(0)項目(簡稱項目)。Aα?

或Aα?χβ

注：添加位置不同，叫做不同項目。用圓點“?”表示識別一個產(chǎn)生式右部符號到達(dá)的位置，項目記錄了當(dāng)前活前綴狀況。1文法G的LR(0)項目2025/1/7編譯原理47LR(0)項目分類移進(jìn)待歸約歸約接受接受項目：S’SS’S?歸約項目：A?待歸約項目：A?BBVN移進(jìn)項目：A?aaVT2025/1/7編譯原理481）定義項目集是相關(guān)項目的集合。是通過對某個基本項目集I通過closure(I)運算求得。2）closure(I)構(gòu)造設(shè)I是文法G的一個LR(0)項目集,

closure(I)是從I出發(fā)用下面三個規(guī)則構(gòu)造的項目集:1I中每一個項目都屬于closure(I)；2若項目A→α·Bβ

closure(I)且B∈VN，B→ηP，則將B→·η加進(jìn)closure(I)中。3重復(fù)執(zhí)行(2)直到closure(I)不再增大為止。

2文法G的LR(0)項目集2025/1/7編譯原理49

其中，I:項目集，x∈V，J={A

x?

|A

?

x

I}。含義：對于任意項目集I，轉(zhuǎn)換到項目J，是由于I中有A

?X

，J中有A

X?

，表示識別的活前綴增加了X。XAα?XβI：AαX?βJ:go(I,X)=Jclosure()1）定義3狀態(tài)轉(zhuǎn)換函數(shù)GO(I，X)2025/1/7編譯原理50二、識別所有規(guī)范句型全部活前綴的DFA1由項目構(gòu)成識別文法活前綴的DFA

1）對于一個文法G，可構(gòu)造一個DFA，由它的狀態(tài)（項目集）記住當(dāng)前活前綴狀況，該DFA能識別G的所有活前綴。

若狀態(tài)中項目為Aα?，則表示它已處于歸態(tài)活前綴。若為Aα?χβ則表示它處于非歸態(tài)活前綴。

2）DFA的整個狀態(tài)集稱為LR(0)項目集規(guī)范族。

項目、項目集、項目集規(guī)范族。目的：構(gòu)造LR(0)的項目集規(guī)范族。2025/1/7編譯原理51Step1拓廣文法G，形成新的文法G’。即增加產(chǎn)生式S’S，并令S’

?S作為G’的初態(tài)I0的基本項目2DFA構(gòu)造過程Step2定義和構(gòu)造項目集的閉包。設(shè)I是G’的一個項目集，構(gòu)造I的閉包CLOSURE(I)Step3確定狀態(tài)轉(zhuǎn)移。利用轉(zhuǎn)換函數(shù)GO實現(xiàn)。Step3構(gòu)造LR(0)項目集規(guī)范族Q。將所有項目集，以及所有狀態(tài)間轉(zhuǎn)移構(gòu)造出來。構(gòu)造算法：2025/1/7編譯原理52DFAM=(

VT∪VN∪{S},Q{項目集規(guī)范族}，I0=closure{S’→?S}，Q，

=go(I,X))DFA中每個狀態(tài)為終態(tài)，從I0出發(fā)，沿著有向邊可使DFA所經(jīng)歷的任何狀態(tài)終止其工作，將從I0出發(fā)到達(dá)該狀態(tài)所經(jīng)過的弧上的標(biāo)記依次連接，即可得到DFA到達(dá)該狀態(tài)時，所識別的某規(guī)范句型的一個活前綴。因此該DFA可識別所有活前綴。注意：當(dāng)M到達(dá)只含有歸約項目的項目集時，表明活前綴中已含有相應(yīng)句柄的全部符號，這些狀態(tài)稱為句柄的識別狀態(tài)。2025/1/7編譯原理53三、LR(0)分析表的構(gòu)造假定C={I0,I1,……，In}，用整數(shù)0，1，……，n表示狀態(tài)I0,I1,……，In，因此，G’的LR(0)分析表含有狀態(tài)0，1，……，n。令含有項目S’→．S的Ik的下標(biāo)k為初態(tài)。ACTION和GOTO可按如下方法構(gòu)造：若項目A→α．a(chǎn)β屬于Ii且GO(Ii,a)=Ij,a∈VT，則置ACTION[i,a]為“把狀態(tài)j和符號a移進(jìn)?！?，簡記為“sj”；若a∈VN，則置GOTO(i,a)=j;若規(guī)約項目A→α．∈Ii,則對任何終結(jié)符a,置ACTION[i,a]為“用產(chǎn)生式A→α進(jìn)行規(guī)約”，簡記為“rj”;其中，假定A→α為文法G`的第j個產(chǎn)生式；若接受項目S’→S．屬于Ik,則置ACTION[k,#]為“接受”，簡記為“acc”;分析表中凡不能用上述規(guī)則填入信息的空白格均置上“出錯標(biāo)志”。2025/1/7編譯原理54注意：一個LR(0)項目集中不能有下列情況存在：

1、移進(jìn)和歸約項目同時存在(移進(jìn)-歸約沖突)

形如：A→α·aβ，a∈VTB→γ·

2、歸約和歸約項目同時存在(歸約-歸約沖突)

形如：A→α·B→γ·§

4.4.2LR(0)分析表的構(gòu)造2025/1/7編譯原理55

對于沖突狀態(tài)I中的歸約項目A

，不管當(dāng)前輸入符號，都把ACTION表中的狀態(tài)行所有非終結(jié)符列置為rj，其中j為A產(chǎn)生式編號。產(chǎn)生沖突的根本原因？

構(gòu)造分析表時根據(jù)不同的掃描符號a，將I中各項目對應(yīng)的分析動作加以區(qū)別，沖突即可解決。

SLR(1)是LR(0)的一種改進(jìn)，對有沖突的狀態(tài)向前查看一個符號，以確定作何種動作。如何解決？一、問題分析SLR(1)分析表的構(gòu)造2025/1/7編譯原理56

定義：對于文法中的非終結(jié)符U∈VNFOLLOW(U)={a|S’?…Ua…，a∈VT∪{#}}

對含沖突的項目集I={X

b，A

，B}，若、FOLLOW(A)、FOLLOW(B)兩兩不相交，則面對當(dāng)前讀入符號a，狀態(tài)I的解決方法：

1.若a=b，則移進(jìn)。

2.若aFOLLOW(A)，則用A進(jìn)行歸約。3.若aFOLLOW(B)，則用B進(jìn)行歸約。4.此外，報錯。具體解決過程*2025/1/7編譯原理57二、構(gòu)造SLR(1)分析表的算法

設(shè)C={I0,I1,…In},以各項目集Ik(k＝0，…,n)的k作為狀態(tài)序號，并以包含S`?S的項目集作為初始狀態(tài)，同時將產(chǎn)生式進(jìn)行編號。然后按下列步驟填寫ACTION表和GOTO表：

1）若項目A

?a

屬于Ik狀態(tài)且GO(Ik,a)=Ij，a為終結(jié)符，則置ACTION[k,a]=Sj；即：移進(jìn)a，并轉(zhuǎn)向Ij狀態(tài)。

2）若項目A

?Ik，則對任何終結(jié)符a

Follow(A)，置ACTION[k,a]=rj；其中j是產(chǎn)生式A

的編號，即按該產(chǎn)生式進(jìn)行歸約。

3）若項目S`S?屬于Ik，則置ACTION[k,＃]=acc;4）若GO(Ik,A)=Ij，A是非終結(jié)符，則置GOTO[k,A]=j5）分析表中凡不能用步驟1至4填入信息的空白項，均置上“出錯標(biāo)志”。2025/1/7編譯原理58注意！1)若文法G按上面算法構(gòu)造出來的分析表不包含多重定義項，則該文法G是SLR(1)文法。

2)若項目集中存在A

?

項目，不應(yīng)設(shè)計相應(yīng)GO函數(shù)以轉(zhuǎn)到其他項目集，因為A

?和A

?

是同一項目，都是A

?項目，是歸約項目。

3)二義文法決不是LR文法。

4)每個SLR(1)文法都不是二義的，但是有很多非二義的文法，包括一些程序設(shè)計語言結(jié)構(gòu)，都不是SLR(1)的，這說明SLR(1)文法的描述能力有限。原因是SLR分析器的構(gòu)造方法沒有記住足夠多的上下文。2025/1/7編譯原理59失效原因：SLR(1)規(guī)則僅孤立地考察輸入符號是否屬于與歸約項目Aα·相關(guān)聯(lián)的集合FOLLOW(A)以確定是否應(yīng)按產(chǎn)生式Aα歸約，沒有考察符號串α所在規(guī)范句型的“環(huán)境”——沒有考察L在規(guī)范句型中的“上下文”，這就具有一定的片面性。請閱讀課本例4.82025/1/7編譯原理601）當(dāng)出現(xiàn)移進(jìn)-歸約沖突時，可選取移進(jìn)，這樣，這是一個自然的消除二義性的規(guī)則。

2）當(dāng)出現(xiàn)歸約-歸約沖突時（如課本例4.8）情形就較復(fù)雜，需要有新的解決方法——LR（1）。解決方法

給每個LR(0)項目添加展望信息，即：添加句柄之后可能跟的終結(jié)符，這些終結(jié)符確實跟在規(guī)范句型句柄之后。2025/1/7編譯原理61一、LR(1)項目定義1LR(1)項目：形如(A

?

，a)的二元式稱為LR(1)項目。其中A

是文法的一個產(chǎn)生式，a是終結(jié)符，稱為搜索符。

(A

?

，a）的含義：預(yù)期當(dāng)棧頂句柄

形成后，若掃描到符號a，即可進(jìn)行歸約。此時，

在棧內(nèi)，

還未入棧，即它展望了句柄后的一個符號。對于多數(shù)程序設(shè)計語言，向前展望一個符號就足以決定歸約與否，所以只研究LR(1)。

在LR(1)項目中有效的項目并不多。