編譯程序構(gòu)造與實(shí)踐教程第五章

第五章語法分析——自底向上分析技術(shù)5.1自底向上分析技術(shù)概況5.1.1討論前提1.基本思想從語法分析樹的角度，自底向上分析過程將以輸入符號串為語法分析樹的末端結(jié)點(diǎn)符號串，試圖向著根結(jié)點(diǎn)方向往上構(gòu)造語法分析樹，使識別符號正是根結(jié)點(diǎn)。按自底向上分析技術(shù)，句型分析的過程是一個不斷（直接）歸約的過程。分析（識別）技術(shù)、識別算法、識別程序識別程序功能：進(jìn)行句型分析(識別)討論的前提處理對象（輸入）是符號串(中間表示形式)

基礎(chǔ)文法是壓縮了的上下文無關(guān)文法分析過程是從左到右逐個符號地進(jìn)行規(guī)范分析自底向上句型分析的基礎(chǔ)文法是壓縮了的上下文無關(guān)文法，其中，壓縮了的文法是這樣的文法，其中每個重寫規(guī)則都用于句子的生成中，即，每個重寫規(guī)則U::=u滿足下列兩個條件：(1)Z=>*

U(U出現(xiàn)在句型中)，(2)u=>+t,tVT+(u能推導(dǎo)到終結(jié)符號串)。3.輸入和輸出輸入：詞法分析程序的輸出(屬性字序列)

輸出：識別出是句子時(shí)，輸出語法分析樹或其他內(nèi)部中間表示；出錯時(shí)報(bào)錯。4.要解決的基本問題自底向上分析技術(shù)要解決的基本問題：在每一分析步的當(dāng)前句型中，

·找出要被(直接)歸約的(簡單)短語u·確定(直接)歸約到哪個非終結(jié)符號U作為分析技術(shù)，重要的是如何自動、機(jī)械地解決上述基本問題。

為什么自底向上分析技術(shù)可行？對于上下文無關(guān)文法的任一句子，都存在規(guī)范分析。5.1.2基本實(shí)現(xiàn)方法1.基本思想分析過程中，當(dāng)分析棧頂部分形成可以(直接)歸約的(簡單)短語時(shí)進(jìn)行(直接)歸約，當(dāng)還未形成時(shí)便移入，因此稱為移入-歸約法。分析動作4個：移入歸約成功報(bào)錯2.基本實(shí)現(xiàn)工具：分析棧3.例

G[E]：E∷=E+E|E*E|(E)|i

輸入符號串：i+i*iE=>E+E=>E+E*E=>E+E*i=>E+i*i=>i+i*i

使用移入-歸約法的分析過程如下。

移入-歸約法分析過程：步驟棧輸入其余部分動作規(guī)則（1）#i+i*i#移入（2）#i+i*i#歸約E::=i

（3）#E+i*i#移入（4）#E+i*i#移入（5）#E+i

*i#歸約E::=i

（6）#E+E*i#移入

（7）#E+E*i#移入（8）#E+E*i#歸約

E::=i（9）#E+E*E#歸約E::=E*E（10）#E+E#歸約E::=E+E（11）#E#成功所以，輸入符號串i+i*i是該文法的句子。

4.是規(guī)范分析嗎？為什么？

5.移入-歸約法解決了自底向上分析技術(shù)的2個基本問題？

·找出要被(直接)歸約的(簡單)短語u·確定歸約到哪個非終結(jié)符號U

答案：不！

移入-歸約法是自底向上分析技術(shù)？答案：不！

6.自底向上分析技術(shù)分類

LR分析技術(shù)（歸約句柄，即最左簡單短語）優(yōu)先分析技術(shù)：算符優(yōu)先分析技術(shù)(歸約最左質(zhì)短語)

簡單優(yōu)先分析技術(shù)（歸約句柄）5.2LR(1)分析技術(shù)5.2.1LR(1)分析技術(shù)與LR(1)文法1.LR(1)分析技術(shù)的基本思想概況

LR(k)分析技術(shù)設(shè)想：從左向右地掃描輸入符號串中的符號，且向前看確定個數(shù)（k個）的符號，一點(diǎn)不回溯地識別給定的符號串（嚴(yán)格地從左到右地進(jìn)行分析）?！癓R(k)”的含義是：可以以k為界從左到右地翻譯。

LR(1)，即k=1，句型分析時(shí)向前看1個符號。討論前提：輸入(討論對象)是符號串以壓縮了的上下文無關(guān)文法為基礎(chǔ)文法從左到右的規(guī)范分析基本實(shí)現(xiàn)方法：移入-歸約法基本實(shí)現(xiàn)工具：分析棧(2)一個文法是LR(k)文法，條件是：

在句型的識別過程中,任一句柄由其左部的符號串及其右部的k個符號所唯一地確定。

LR(k)文法的另一種說法是：應(yīng)用LR(k)分析技術(shù)進(jìn)行句型識別過程中，每一步的分析動作由可能句柄左部的符號串及其右部向前看的k個符號所唯一地確定。

LR(k)文法是無二義性的文法,LR(1)文法當(dāng)然也是。一個語言能由LR(k)文法生成，就能由LR(1)文法生成，因此只需關(guān)心LR(1)文法。

(3)基于LR分析技術(shù)的識別程序稱為LR識別程序。LR識別程序示意圖如下圖所示?？梢奓R識別程序由驅(qū)動程序與LR分析表兩部分組成。分析棧(Sm,Xm)...(S2,X2)(S1,X1)(S0,#)分析棧狀態(tài)S對應(yīng)于LR(1)項(xiàng)集（

LR(1)項(xiàng)組成的集合）。設(shè)p號規(guī)則：Up::=Xp1…XpjXp

j+1…Xp

npLR(1)項(xiàng)：

[p,j;α]（足標(biāo)表示法）

[Up→Xp1…Xpj.Xpj+1…Xp

np;α]（圓點(diǎn)表示法）

歷史信息向前看信息棧頂分析棧中元素結(jié)構(gòu)：狀態(tài)S符號X例G［E］：

1：E∷=E+T2：E∷=T3：T∷=T*F4：T∷=F5：F∷=(E)6：F∷=iLR(0)項(xiàng)

E.E+TEE.+TEE+.TEE+T.T.T*FTT.*FTT*.FTT*F.LR(1)項(xiàng)：a.[1，0；+][1，0；#][3，3；*][5，1；+]b.[E.E+T;+][E.E+T;#][TT*F.;*][F(.E);+]LR項(xiàng)指明在關(guān)于某重寫規(guī)則歸約時(shí)正處理到哪里，可能掃描到的輸入符號將是什么。如何構(gòu)造LR（0）項(xiàng)？如何構(gòu)造LR（1）項(xiàng)？LR(0)項(xiàng)簡單地從重寫規(guī)則得到，關(guān)于LR(1)項(xiàng)，構(gòu)造語法分析樹，例如，可構(gòu)造下列LR(1)項(xiàng)

E#[E.E+T,#]

E+T[E.E+T,+]E+TF[F.i,#]

TFi[T.F,+]Fii

LR(k)分析表由ACTION部分和GOTO部分組成。ACTION部分指明分析動作(移入、歸約、接受、報(bào)錯)GOTO部分指明狀態(tài)的轉(zhuǎn)換例文法G[E]：

E::=E+T|TT::=T*F|FF::=(E)|i的LR(1)分析表(k=1)見下頁。狀態(tài)ACTIONGOTO+*()i#ETF0

S4

S51231S6

acc2r2S7

r2

r23r4r4

r4

r44

S4

S5

8235r6r6

r6

r66

S4

S5

937

S4

S5108

S6

S119

r1S7

r1

r110

r3r3

r3

r311

r5r5

r5

r5文法G[E]的LR(1)分析表文法G[E]：

1:E::=E+T2:E::=T3:T::=T*F4:T::=F5:F::=(E)6:F::=i的LR(1)分析表(k=1)中，

si:把{狀態(tài)i，輸入符號}下推入棧,

rj:按規(guī)則j歸約，

acc:接受空白：報(bào)錯當(dāng)歸約時(shí)，從分析棧棧頂處上退去形成句柄（最左簡單短語）的部分，以新棧頂?shù)臓顟B(tài)與直接歸約成的非終結(jié)符號配對查GOTO部分，得到轉(zhuǎn)換到的狀態(tài)，把

{轉(zhuǎn)換到的狀態(tài)，直接歸約成的非終結(jié)符號}下推入分析棧。2.應(yīng)用LR分析技術(shù)句型分析例G[E]：E::=E+T|TT::=T*F|FF::=(E)|i該文法的LR(1)分析表見前面。

用數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)分析棧，棧頂計(jì)數(shù)器為top，應(yīng)用LR分析技術(shù)句型分析的識別過程大致如下。

步驟1置初值，把{S0，#}下推入棧，其中S0是初始狀態(tài)。步驟2把R置為下一(當(dāng)前)輸入符號。步驟3執(zhí)行動作ACTION[分析棧[top].狀態(tài)][R]

·動作是Si，即移入，把狀態(tài)i與輸入符號R一起下推入分析棧，重復(fù)步驟2?！幼魇莚j，即歸約，按規(guī)則j進(jìn)行歸約，把分析棧頂形成句柄的部分符號串（連同狀態(tài)）上退去，以這時(shí)的分析棧頂狀態(tài)與所歸約成的非終結(jié)符號配對，查GOTO部分，得到轉(zhuǎn)換成的狀態(tài)，把此狀態(tài)與所歸約成的非終結(jié)符號一起下推入分析棧，重復(fù)步驟3?！幼魇莂cc，即接受，識別出輸入符號串是相應(yīng)文法的句子而結(jié)束分析?！幼魇荅RROR(空白元素)，給出報(bào)錯信息，進(jìn)行出錯處理。

LR(k)識別程序的控制流程示意圖如下面。說明：當(dāng)k=1時(shí)，無需引進(jìn)變量y，當(dāng)前掃描到的便是向前看符號。輸入符號串：i*(i+i),對該輸入符號串i*(i+i)進(jìn)行句型分析的過程見下面的表。

請注意分析動作的執(zhí)行。LR識別程序][y]執(zhí)行ACTION[TOP(S).狀態(tài)][y]步驟棧輸入動作說明

0

0

i*(i+i)#

S5移入i

1

0i5*(i+i)#

r6歸約iF::=i

2

0F3*(i+i)#

r4歸約FT::=F

3

0T2*(i+i)#

S7移入*

4

0T2*7

(i+i)#

S4移入(

5

0T2*7(4

i+i)#

S5移入i

6

0T2*7(4i5

+i)#

r6歸約iF::=i

7

0T2*7(4F3

+i)#

r4歸約FT::=F

8

0T2*7(4T2

+i)#

r2歸約TE::=T

9

0T2*7(4E8

+i)#

S6移入+

10

0T2*7(4E8+6

i)#

S5移入i

11

0T2*7(4E8+6i5

)#

r6歸約iF::=i

12

0T2*7(4E8+6F3

)#

r4歸約FT::=F

13

0T2*7(4E8+6T9

)#

r1歸約E+TE::=E+T

140T2*7(4E8

)#S11移入)

15

0T2*7(4E8)11

#

r5歸約(E)F::=(E)

16

0T2*7F10

#

r3歸約T*FT::=T*F

17

0T2

#

r2歸約TE::=T

18

0E1

#

acc接受

因此，i*(i+i)是該文法的句子。

E=>T=>T*F=>T*(E)=>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*(T+i)=>T*(F+i)=>T*(i+i)=>F*(i+i)=i*(i+i)

結(jié)點(diǎn)序號

文法符號

父結(jié)點(diǎn)

左兄結(jié)點(diǎn)

右子結(jié)點(diǎn)

1 i 8 0 02 * 17

9 03 ( 16 0 04 i 10 0 05 + 15

12 06 i

13 0 07 ) 16

15

08 F 9 0

19 T 17 0 810 F 11 0 411 T 12 0 1012 E 15

0 1113 F

14 0 6

14T1551315E1641416F173717T1801618

E0017重要概念：

構(gòu)型：S0X1S1X2S2…XmSm|Y1…Ykw

(當(dāng)前分析棧從底到頂?shù)膬?nèi)容，(尚未掃描部分)

除了#)

初始構(gòu)型：S0|T1…Tn#k

最終構(gòu)型：S0ZSr|#k

活前綴：X1X2…Xm活前綴是一個規(guī)范句型中這樣一個前綴子符號串，它不包含句柄之后的任何符號。構(gòu)型刻畫了句型分析過程中一個分析步的狀況，而分析棧中從底到頂?shù)姆柎偸窍鄳?yīng)規(guī)范句型的活前綴，在其右部添加若干個輸入符號時(shí)將可能構(gòu)成規(guī)范句型。

初始構(gòu)型是（k=1，是1-句型，僅一個#）

S0|i*(i+i)#最終識別出句子時(shí)的構(gòu)型是：

S0ES1|#這里E是文法的識別符號。

3.應(yīng)用LR(1)分析技術(shù)句型分析時(shí)生成語法分析樹

語法分析不僅要識別一個輸入符號串是否是某文法的句子，必要的是還需生成相應(yīng)的內(nèi)部中間表示作為輸出，提供給下一階段（語義分析）作為輸入。這中間表示可以是語法分析樹，也可以是推導(dǎo)等。這里討論如何建立語法分析樹。分析過程中，每當(dāng)分析棧頂部分符號串構(gòu)成句柄，因而執(zhí)行直接歸約動作時(shí)建立新的結(jié)點(diǎn)(分支名字結(jié)點(diǎn)),并建立相應(yīng)分支結(jié)點(diǎn)的父子結(jié)點(diǎn)關(guān)系和它們相互之間的兄弟結(jié)點(diǎn)關(guān)系，并作出狀態(tài)的轉(zhuǎn)換。具體實(shí)現(xiàn)如下:

先設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)注意：充分利用C語言置初值設(shè)施

實(shí)現(xiàn)控制部分注意：置初值的內(nèi)容分析動作的判別和處理語法分析樹的生成分析棧的數(shù)據(jù)結(jié)構(gòu)：typedef

struct{int

狀態(tài);

int

結(jié)點(diǎn)序號;}棧元素類型；棧元素類型分析棧[MaxStackDepth]；int

分析棧棧頂指針;/*通常以top為名*/語法分析樹的數(shù)據(jù)結(jié)構(gòu)：typedef

struct{int

結(jié)點(diǎn)序號;int

文法符號序號;

int

父結(jié)點(diǎn)序號;

int

左兄結(jié)點(diǎn)序號;int

右子結(jié)點(diǎn)序號：}語法樹結(jié)點(diǎn)類型；語法樹結(jié)點(diǎn)類型語法分析樹[MaxNodeNum]；int

結(jié)點(diǎn)計(jì)數(shù)器；識別程序：驅(qū)動程序（部分）R=當(dāng)前輸入符號在VT中的序號；act=ACTION[分析棧[top].狀態(tài)][R];

if(act>0)/*

移入動作

*/{top=top+1;

分析棧[top]={act,k};/*k對應(yīng)于輸入符號結(jié)點(diǎn)序號

*/}elseif(act<0)/*歸約動作*/{act=－act;m=文法[act].右部長度；

if(m==0)/*建立結(jié)點(diǎn)*/{N=N+1;語法分析樹[N]={N，0，0，0，0}；

top=top+1;分析棧[top]={0,N};

m=1;}

右子結(jié)點(diǎn)序號=分析棧[top].結(jié)點(diǎn)序號；U=文法[act].左部符號序號；N=N+1；語法分析樹[N]={N,U，0，0，右子結(jié)點(diǎn)序號}；

左兄結(jié)點(diǎn)序號=0;

for(j=1;j<=m;j++){分支結(jié)點(diǎn)序號=分析棧[top－(m－j)].結(jié)點(diǎn)序號；語法分析樹[分支結(jié)點(diǎn)序號].父結(jié)點(diǎn)序號=N；語法分析樹[分支結(jié)點(diǎn)序號].左兄結(jié)點(diǎn)序號=左兄結(jié)點(diǎn)序號；左兄結(jié)點(diǎn)序號=分支結(jié)點(diǎn)序號；

}top=top－m;

NewState=GOTO[分析棧[top].狀態(tài)][U－100]；

top=top+1;分析棧[top]={NewState,N}；}

注意：C語言中結(jié)構(gòu)類型變量的賦值方式。

賦值語句：

分析棧[top]={初始狀態(tài)0,結(jié)點(diǎn)序號0};

實(shí)際上需由下列兩個賦值語句實(shí)現(xiàn)：

分析棧[top].狀態(tài)=初始狀態(tài)0;

分析棧[top].結(jié)點(diǎn)序號=結(jié)點(diǎn)序號0;

其他的類似。

4.LR(1)分析表的構(gòu)造

(1)思路

為了構(gòu)造LR(1)分析表，首先需理解狀態(tài)是什么、狀態(tài)轉(zhuǎn)換的含義又是什么。在LR(1)分析技術(shù)中，狀態(tài)對應(yīng)于LR(1)項(xiàng)所組成的集合，即，LR(1)項(xiàng)集。如前所述，LR(1)項(xiàng)呈下形：

[UpXp1Xp2XpjXpj+1Xpnp;a]

它意指正按規(guī)則p:Up::=Xp1Xp2Xpnp進(jìn)行歸約，當(dāng)前已處理到Xpj，即尚未被掃描的輸入符號串部分要（廣義）歸約到Xpj+1。當(dāng)輸入符號串已歸約到Up時(shí)，則Up在句型中的后繼符號將是符號a。

現(xiàn)在看LR(1)項(xiàng)[EE+.T；a]，如果分析過程正按規(guī)則1:E::=E+T歸約,輸入符號串左邊部分已歸約到E+,當(dāng)前待掃描的輸入符號串部分正待歸約到非終結(jié)符號T。由于T::=T*F與T::=F，不言而喻,要?dú)w約到T必須先歸約到T*F或F。而如果要?dú)w約到F，又必須先(廣義)歸約到(E)或i，因此LR(1)項(xiàng)[T.T*F;a]與[T.F;a]都同[EE+.T;a]緊密相關(guān)。而對于其中的[T.T*F;a]必須把尚待掃描的輸入符號串部分歸約成T*F，即，先歸約成T，這時(shí)句型中緊隨T的符號是*，于是有[T.T*F;*]。類似地，相關(guān)的又有[T.F;*]，為歸約成F，又有[F.(E);*]與[F.i;*]等。把所有這樣的相關(guān)LR(1)項(xiàng)放入一個集合中，形成LR(1)項(xiàng)集。

讓LR(1)項(xiàng)集對應(yīng)于狀態(tài)，狀態(tài)之間的轉(zhuǎn)換實(shí)質(zhì)上對應(yīng)于項(xiàng)集的后繼關(guān)系，引進(jìn)后繼項(xiàng)的概念。如果有一個LR(1)項(xiàng)：[Uu.Av;a]，其中AVNVT,則其后繼項(xiàng)是[UuA.v;a]，后繼項(xiàng)是把項(xiàng)中圓點(diǎn)右移一個符號位置所得的項(xiàng)。從句型識別的角度看，其含義是明顯的，即，當(dāng)掃描過的輸入符號部分已與規(guī)則右部的u相匹配（即歸約成u）時(shí)，應(yīng)期望后繼的那些輸入符號與u的后繼符號A相匹配。因此[Uu.Av;a]所在項(xiàng)集對應(yīng)的狀態(tài)，將轉(zhuǎn)換到其后繼項(xiàng)所在項(xiàng)集（即后繼項(xiàng)集）對應(yīng)的狀態(tài)。

如何確切地構(gòu)造各個LR(1)項(xiàng)集？通常，從初始項(xiàng)出發(fā)構(gòu)造初始項(xiàng)集，從初始項(xiàng)集開始逐個構(gòu)造后繼項(xiàng)集，再從后繼項(xiàng)集構(gòu)造后繼項(xiàng)集，最終構(gòu)造出一切LR(1)項(xiàng)集。讓各個項(xiàng)集對應(yīng)于狀態(tài)，后繼關(guān)系對應(yīng)于狀態(tài)轉(zhuǎn)換關(guān)系，然后填LR(1)分析表，即得所求。

一個LR識別程序由驅(qū)動程序及分析表兩部分組成。對于同一個k值的LR(k)文法，可以使用同一個驅(qū)動程序。但如上所述的（規(guī)范）LR分析表的構(gòu)造工作量甚大，阻礙了LR分析技術(shù)的推廣應(yīng)用。目前LR分析表的構(gòu)造有三種方法：規(guī)范LR分析表構(gòu)造法（LR）

簡單LR分析表構(gòu)造法（SLR）前視LR分析表構(gòu)造法（LALR）重點(diǎn)討論SLR分析表構(gòu)造方法。(2)SLR(k)方法a.基本思想：分析過程中，如果不向前看一個符號能確定分析動作，就不向前看任何符號，如果不能確定，再向前看一個符號。因此，基于LR(0)項(xiàng)集。

b.思路：引進(jìn)特征有窮狀態(tài)機(jī)CFSMLR(0)項(xiàng)

—LR(0)項(xiàng)集、后繼LR(0)項(xiàng)集

—LR(0)項(xiàng)集規(guī)范族、GO函數(shù)

—特征有窮狀態(tài)機(jī)CFSM

依據(jù)CFSM填LR分析表。

其中，GO函數(shù)：LR項(xiàng)集之后繼關(guān)系的抽象。特征有窮狀態(tài)機(jī)CFSM則是LR(0)項(xiàng)集規(guī)范族與GO函數(shù)的抽象。?LR(0)項(xiàng)如果U::=uv是一個規(guī)則，其中u或v可為空串，則U→u.v稱為文法G的一個LR(0)項(xiàng)，簡稱項(xiàng)。

設(shè)規(guī)則E::=E+T，可有相應(yīng)的4個LR(0)項(xiàng),即，

E→.E+TE→E.+TE→E+.TE→E+T.（Z→E.#）待約項(xiàng)移入項(xiàng)待約項(xiàng)歸約項(xiàng)接受項(xiàng)不完備項(xiàng)完備項(xiàng)初始LR（0）項(xiàng)：Z.Z，或Z.Z#，如Z→.E#

對LR(0)項(xiàng)的理解:它指明了在識別過程中以某非終結(jié)符號為目標(biāo)時(shí)，某時(shí)刻已進(jìn)行歸約到相應(yīng)規(guī)則右部多大部分。?LR(0)項(xiàng)集、初始LR(0)項(xiàng)集CLUSURE({Z→.E#})(項(xiàng)集閉包)

其中CLUSURE(I)=I∪{V->.w|U->u.Vv∈CLUSURE(I),

且V::=w是文法規(guī)則}如初始(LR(0))項(xiàng)集：{Z→.E#,E→.E+T,E→.T,T→.T*F,T→.F,F→.(E),F→.i}?后繼項(xiàng)

U→u.Av的后繼項(xiàng)：U→uA.v

如，E→.E+T的后繼項(xiàng)是E→E.+T?后繼LR（0）項(xiàng)集后繼LR（0）項(xiàng)的項(xiàng)集閉包?文法的LR（0）項(xiàng)集規(guī)范族從初始LR（0）項(xiàng)集出發(fā)構(gòu)造的后繼項(xiàng)集，以及后繼項(xiàng)集的后繼項(xiàng)集，直到不再生成新的LR（0）項(xiàng)集為止的所有項(xiàng)集。E→.E+T的后繼LR（0）項(xiàng)集（E-后繼）：

{E→E.+T}E→.T的后繼LR（0）項(xiàng)集（T-后繼）：

{E→T.}F→.(E)的后繼LR（0）項(xiàng)集（（-后繼）：

{F→(.E),E→.E+T,E→.T,T→.T*F,T→.F,F→.(E),F→.i}F→.i的后繼LR（0）項(xiàng)集（i-后繼）：

{F→i.}初始項(xiàng)集

項(xiàng)集0:{Z→.E#,E→.E+T,E→.T,T→.T*F,T→.F,F→.(E),F→.i}

E_后繼

項(xiàng)集1:{Z→E.#,E→E.+T}

T_后繼

項(xiàng)集2:{E→T.,T→T.*F}

F_后繼

項(xiàng)集3:{T→F.}

(_后繼

項(xiàng)集4:{F→(.E),E→.E+T,E→.T,T→.T*F,T→.F,F→.(E),F→.i}

i_后繼

項(xiàng)集5:{F→i.}

對于項(xiàng)集1，有#_后繼和+_后繼，

對于項(xiàng)集2，有歸約_后繼和*_后繼，

對于項(xiàng)集3，有歸約_后繼，

對于項(xiàng)集4，有E_后繼、T_后繼、F_后繼與i_后繼

對于項(xiàng)集5，有歸約_后繼，

構(gòu)造一切后繼項(xiàng)集,抽象成GO函數(shù),如GO(S0,E)=S1,GO(S0,i)=S5111012

613

7

3

8

5E

2

9

4特征有窮狀態(tài)機(jī)CFSMLR（0）項(xiàng)集規(guī)范族與GO函數(shù)的抽象。

##Z::=E#

0

1

+T#E::=E+T#E::=T

T

*

F#T::=T*F

F#T::=F

(

E

)#F::=(E)

i#F::=i12注意：?

項(xiàng)集1的#_后繼，可以省略。?

狀態(tài)2與狀態(tài)9，相應(yīng)項(xiàng)集如下：項(xiàng)集2={E→T.,T→T.*F}

項(xiàng)集9={T→T.*F,E→E+T.}

是不適定狀態(tài)。如果某項(xiàng)集中既包含完備項(xiàng)，又包括不完備項(xiàng)，則稱相應(yīng)的狀態(tài)為不適定狀態(tài)。

一個上下文無關(guān)文法G是LR（0）文法，當(dāng)且僅當(dāng)該文法的CFSM中無不適定狀態(tài)。應(yīng)用CFSM句型分析*基于對不適定狀態(tài)的處理，引進(jìn)SLR分析表的構(gòu)造方法，通常稱為SLR技術(shù)。引進(jìn)SLR（1）文法的概念。

SLR(1)技術(shù)用簡便方式解決不適定狀態(tài)問題，即，引進(jìn)簡單向前看1集合。簡單向前看1集合FT1(T)={T}，而簡單向前看1集合FT1(U)=Follow(U)

一個上下文無關(guān)文法G是SLR(1)文法，當(dāng)且僅當(dāng)與其CFSM每個不適定狀態(tài)的每個T-轉(zhuǎn)換和#U::=u轉(zhuǎn)換相聯(lián)系的簡單向前看1集合互不相交。對于狀態(tài)2，*_轉(zhuǎn)換，簡單向前看1集合是{*}

，而#E::=T轉(zhuǎn)換，簡單向前看1集合是FT1(E)=Follow(E)={#，+，)}

。不相交。對于狀態(tài)9，情況類似。因此，文法G[E]是SLR(1)文法。c.SLR(1)分析表的構(gòu)造基本思想：首先從文法構(gòu)造其增廣文法之CFSM，然后從該CFSM構(gòu)造SLR分析表。構(gòu)造步驟有3步。步驟1增廣文法等價(jià)變換:添加規(guī)則Z∷=Z#,以Z為新文法G的識別符號。步驟2構(gòu)造CFSM，即，構(gòu)造G的LR(0)項(xiàng)集規(guī)范族C={S0,S1,…,Sn}和GO函數(shù)。項(xiàng)集Sj對應(yīng)于狀態(tài)j，初始項(xiàng)集0對應(yīng)于初始狀態(tài)0。#歸約_后繼項(xiàng)集對應(yīng)于終止?fàn)顟B(tài)。步驟3填SLR(1)分析表。

步驟3填SLR(1)分析表。(i)如果移入項(xiàng)Ｕ→u.av∈Si,且GO(Si,a)=Sj，其中a∈VT，則置ACTION[i][a]=‘Sj’。(ii)如果歸約項(xiàng)Ｕ→u.∈Si，且Ｕ∷=u是增廣文法G'的規(guī)則j，則對任何輸入符號a,a∈FT1(Ｕ)，置ACTION[i][a]=‘rj’。(iii)如果項(xiàng)Z'→Z.#∈Si,則置ACTION[i][#]=‘a(chǎn)cc’(iv)如果GO(Si,U)=Sj,U∈VN,則置GOTO[i][U]=j(v)凡不能由上述4個規(guī)則確定的分析表元素，全置為報(bào)錯標(biāo)志(空白)。

簡單地，以表列方式構(gòu)造SLR分析表步驟如下：

1.以表列方式列出LR(0)項(xiàng)集規(guī)范族

2.計(jì)算Follow集合（即FT1集合）

3.填分析表注意：無需一下子計(jì)算所有的Follow集合，可僅當(dāng)需要時(shí)再計(jì)算。例G[E]：

E::=T+EE::=TT::=FF::=i項(xiàng)集編號

項(xiàng)集名

項(xiàng)

后繼關(guān)系

0

初始項(xiàng)集

基本項(xiàng)集Z→.E#

E1

T2

F3i4

閉包集合E→.T+EE→.TT→.FF→.i1E_后繼基本項(xiàng)集Z→E.#

#9992T_后繼

基本項(xiàng)集E→T.+EE→T.

+5#E::=T73F_后繼

基本項(xiàng)集T→F.#T::=F74i_后繼

基本項(xiàng)集F→i.#F::=i7

5

+_后繼

基本項(xiàng)集E→T+.E

E

6T2

F3

i4

閉包集合E→.T+EE→.TT→.FF→.i6E_后繼

基本項(xiàng)集E→T+E.#E::=T+E7G[E]：E::=T+EE::=TT::=FF::=i的SLR(1)分析表狀態(tài)ACTIONGOTO+i#ETF0S41231acc2S5r23r3r34r4r45S46236r1可基于該分析表對輸入符號串i+i+i進(jìn)行句型分析。5.為二義性文法構(gòu)造LR分析表

LR(1)文法必不是二義性的。為一個語言設(shè)計(jì)的文法,不一定是無二義性的，因此必須也能為二義性文法構(gòu)造LR分析表。其基本思想是：當(dāng)分析表構(gòu)造過程中，發(fā)現(xiàn)有移入-歸約沖突時(shí)，利用運(yùn)算符的優(yōu)先級與結(jié)合性等信息，解決沖突，確定分析表元素，使得LR分析表元素全為惟一的，從而對于二義性文法也能構(gòu)造LR分析表。

5.2.2LR(1)識別程序的計(jì)算機(jī)實(shí)現(xiàn)

LR識別程序由驅(qū)動程序和分析表組成。

LR(1)識別程序?qū)崿F(xiàn)之要點(diǎn)是：分析棧棧頂狀態(tài)和當(dāng)前向前看1符號決定分析表中的分析動作。

實(shí)際實(shí)現(xiàn)LR分析技術(shù)句型分析時(shí)，必須考慮的是LR分析表在計(jì)算機(jī)內(nèi)的存儲表示。再一個關(guān)鍵問題是如何在分析過程中生成分析結(jié)果—語法分析樹或推導(dǎo)。

分析表存儲表示的思路：用數(shù)值代替分析表中元素。

分析表由ACTION部分和GOTO部分組成，且顯然各自對應(yīng)一個二維數(shù)組，因此可引進(jìn)兩個二維數(shù)組ACTION和GOTO。

分析表的存儲表示：

intACTION[StateNum][VtNum+1];其中,狀態(tài)用狀態(tài)序號，終結(jié)符號用在VT中的序號表示。四類值：

“Si”：表示移入動作，對應(yīng)于正值：+i

“rj”：表示按規(guī)則j直接歸約，對應(yīng)于負(fù)值：－j(j<0)

“acc”：表示接受，對應(yīng)于特殊整值，如999

空白：表示錯誤，對應(yīng)于數(shù)值0

intGOTO[StateNum][VnNum+1];

狀態(tài)用狀態(tài)序號,非終結(jié)符號用在VN中的序號表示。例子見下面，注意：分析表中符號的排序必須與VN、VT中符號的順序一致。

狀態(tài)ACTIONGOTO+*()i#ETF0

S4

S51231S6

acc2r2S7

r2

r23r4r4

r4

r44

S4

S5

8235r6r6

r6

r66

S4

S5

937

S4

S5108

S6

S119

r1S7

r1

r110

r3r3

r3

r311

r5r5

r5

r5intACTION[][6]={{0,0,0,4,0,5},{999,6,0,0,0,0},{－2,－2,7,0,－2,0},{－4,－4,－4,0,－4,0},{0,0,0,4,0,5},{－6,－6,－6,0,－6,0},{0,0,0,4,0,5},{0,0,0,4,0,5},{0,6,0,0,11,0},{－1,－1,7,0,－1,0},{－3,－3,－3,0,－3,0},{－5,－5,－5,0,－5,0}}；intGOTO[][4]={{0,1,2,3},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,8,2,3},{0,0,0,0},{0,0,9,3},{0,0,0,10},{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}}；5.2.3識別程序自動構(gòu)造1.識別程序自動構(gòu)造的基本思想

基于LR(1)分析技術(shù)的識別程序之自動構(gòu)造，實(shí)質(zhì)上是LR(1)分析表的自動構(gòu)造。

SLR（1）分析表自動生成的程序控制流程示意圖

LR(1)文法必不是二義性的。以某種方式提供優(yōu)先級與結(jié)合性等的信息，解決沖突，使得即使對于二義性文法也能構(gòu)造LR分析表。

驅(qū)動程序

分析表輸入識別結(jié)果符號串入口

出口

輸入求求計(jì)算LR(0)項(xiàng)集文法規(guī)則first集合follow集合規(guī)范族填分析表識別程序2.LALR(1)分析表構(gòu)造方法背景：SLR構(gòu)造LR分析表方法有實(shí)用價(jià)值，但適用面有限制，存在一些文法，不能為它構(gòu)造SLR分析表，由于這時(shí)會發(fā)生移入-歸約沖突。(1)基本思想

基于LR（1）項(xiàng)集規(guī)范族，合并同心項(xiàng)集。

LR(1)項(xiàng)：形如[Uu.v,b],

其中Uu.v是LR(0)項(xiàng)，bVT{#}，是向前看符號，通常稱為搜索符。這時(shí)分析過程中，固定向前看一個符號。如果不計(jì)搜索符，兩個LR(1)項(xiàng)集完全相同，則這兩個項(xiàng)集稱為同心項(xiàng)集。(2)LR(1)項(xiàng)集規(guī)范族類似于LR(0)項(xiàng)集規(guī)范族。文法G[S]：1：S∷=L=R2：S∷=R3：L∷=*R4：L∷=i5：R∷=LLR(1)項(xiàng)集規(guī)范族C={I0,I1,…,I12,I13},GO函數(shù)見下頁。I0={[Z→.S,#],[S→.L=R,#],[S→.R,#],[L→.*R,=|#],[L→.i,=|#],[R→.L,#]}I1=GO(I0,S)=｛［Z→S.,#］｝I2=GO(I0,L)=｛［S→L.=R,#］,［R→L.,#］｝I3=GO(I0,R)=｛［S→R.,#］｝I4=GO(I0,*)=｛［L→*.R,=|#］,［R→.L,=|#］,

［L→.*R,=|#］,［L→.i,=|#］｝I5=GO(I0,i)=｛［L→i.,=|#］｝I6=GO(I2,=)=｛［S→L=.R,#］,［R→.L,#］,

［L→.*R,#］,［L→.i,#］｝I7=GO(I4,R)=｛［L→*R.,=|#］｝I8=GO(I4,L)=｛［R→L.,=|#］｝I9=GO(I6,R)=｛［S→L=R.,#］｝I10=GO(I6,L)=｛［R→L.,#］｝I11=GO(I6,*)=｛［L→*.R,#］,［R→.L,#］,

［L→.*R,#］,［L→.i,#］｝I12=GO(I6,i)=｛［L→i.,#］｝I13=GO(I11,R)=｛［L→*R.,#］｝可合并同心項(xiàng)集：

I4與I11，

I5與I12，

I7與I13，

I8與I10

合并同心項(xiàng)集后，項(xiàng)集的總數(shù)減少了，且正好等于文法之LR（0）項(xiàng)集規(guī)范族中項(xiàng)集的個數(shù)。因此，從這合并了同心項(xiàng)集后的LR（1）項(xiàng)集規(guī)范族來構(gòu)造分析表有與SLR（1）分析表同樣多的狀態(tài)數(shù)。因此，LALR方法介于SLR與規(guī)范LR方法之間。

合并同心項(xiàng)集后可能產(chǎn)生歸約-歸約沖突，相應(yīng)文法便不能應(yīng)用LALR分析表構(gòu)造方法。這是LALR方法不及規(guī)范LR方法之處。但合并后不可能發(fā)生移入-歸約沖突。

LALR(1)分析表見下頁。當(dāng)前語法分析程序自動生成系統(tǒng)YACC便是基于LALR分析表構(gòu)造方法的成功系統(tǒng)。

LALR（1）分析表如下：狀態(tài)ACTIONGOTO=*i#SLF0

S4S51231acc2S6r53

r24

S4S5

875r4

r46

S4S5

897r3r3

8r5r59

r1概括1.自底向上分析技術(shù)概況基本思想、討論前提、基礎(chǔ)文法、輸入輸出、要解決的基本問題基本實(shí)現(xiàn)方法、基本實(shí)現(xiàn)工具分析技術(shù)分類2.LR分析技術(shù)基本實(shí)現(xiàn)思想句型分析

LR分析表及其生成方法（規(guī)范LR、SLR、LALR）3.基本概念

LR(0)項(xiàng)、LR(1)項(xiàng)、特征有窮狀態(tài)機(jī)、

搜索符

構(gòu)型、活前綴5.3*

其他的自頂向下分析技術(shù)自底向上分析技術(shù)除了LR分析技術(shù)，還有優(yōu)先分析技術(shù)(簡單優(yōu)先分析技術(shù)與算符優(yōu)先分析技術(shù)，僅討論后者),共同地要解決下列兩個基本問題：

·找出被歸約的短語

·把被歸約的短語歸約為哪個非終結(jié)符號5.3.1算符優(yōu)先分析技術(shù)概況1.尋找被歸約短語的基本思想

·僅由終結(jié)符號決定歸約順序

·每次只查看兩個相鄰的終結(jié)符號：先找出被歸約短語的尾（終結(jié)）符號然后再找出被歸約短語的頭（終結(jié)）符號再確定歸約的規(guī)則（左部非終結(jié)符號）2.算符文法（OG）算符文法:

沒有形如U∷=…VW…的規(guī)則的文法，其中U、V、W∈VN。算符文法的句型必呈下形（不包含兩個相鄰非終結(jié)符號）:

[N1]T1[N2]T2[N3]…[Nm-1]Tm-1[Nm]Tm[Nm+1]

算符文法的基礎(chǔ)上才能應(yīng)用算符優(yōu)先分析技術(shù)。例G[E]：

E::=E+TE::=TT::=T*FT::=FF::=(E)F::=i例如下定義C語言的文法不是算符文法：

<函數(shù)定義>::=<函數(shù)首部><函數(shù)體><條件語句>::=if(<表達(dá)式>）<語句><否則部分><否則部分>::=else<語句>|εOG重要性質(zhì)：（設(shè)TVT，UVN

）如果某個終結(jié)符號被包含在某個短語中，則與其相鄰的非終結(jié)符號也必定被包含在同一個短語中:

如果句型w中包含TU，則w中任何包含其中之T的短語也必包含其中之U;類似地，如果句型w中包含UT，則w中任何包含其中之T的短語也必包含其中之U。概括之，在任何算符文法句型中，不存在其緊前與緊后是一個非終結(jié)符號的短語。3.算符優(yōu)先關(guān)系與算符優(yōu)先文法(1)算符優(yōu)先關(guān)系的定義與構(gòu)造算符優(yōu)先關(guān)系:<=>

UUU

…Tk

[N]Tl……Tk[N]Tl……Tk[N]Tl…

Tk

=Tl

Tk<Tl

Tk>Tl·定義（U、V、WVN

，TVT

）

Tj

=Ti

iffU::=…TjTi…或U::=…TjWTi…

Tj

<Ti

iffU::=…TjV…V=>+Ti…或V=>+WTi…

Tj

>Ti

iffU::=…VTi…V=>+…Tj

或V=>+…TjW

構(gòu)造算符優(yōu)先關(guān)系的方法

·畫語法分析樹，從語法分析樹找算符優(yōu)先關(guān)系。

G[E]：E::=E+T|TT::=T*F|FF::=(E)|i

EEE+TE+TTT*FE+TFFT*Fi(E)i

(=)+<(+>+*<ii>+*>*+<*

畫足夠多的、有代表性的語法分析樹可找出一切算符優(yōu)先關(guān)系。不足：易遺漏或重復(fù)?！ぐ炊x，對照定義找出一切算符優(yōu)先關(guān)系。

Tj

=Ti

iffU::=…TjTi…或U::=…TjWTi…

Tj

<Ti

iffU::=…TjV…V=>+Ti…或V=>+WTi…

Tj

>Ti

iffU::=…VTi…V=>+…Tj

或V=>+…TjWV=>U1t=>U2t=>…=>UTtVFirstTerm+TU::=…VTi…U::=…TjV…TTi?TjT?G[E]：E::=E+T|TT::=T*F|FF::=(E)|i

E=>*iE=>*(…T=>*iT=>*(…T=>T*Fi>++<i+<(+<*i>*

*>*

(<i(=)算符優(yōu)先矩陣:合并了一切三類算符優(yōu)先關(guān)系的矩陣。例G[E]：E::=E+T|TT::=T*F|FF::=(E)|i+＜i、+＜*、*＜(、(＜+、+＞+、+＜(

算符優(yōu)先矩陣：

+*()i+＞＜＜＞＜*＞＞＜＞＜

(＜＜＜=＜

)＞＞＞

i＞

＞＞(2)算符優(yōu)先文法定義：若一個算符文法，其任何兩個終結(jié)符號之間至多只有一種算符優(yōu)先關(guān)系成立，則該算符文法稱為算符優(yōu)先文法。例G[E]：E::=E+T|TT::=T*F|FF::=(E)|i是算符優(yōu)先文法。

+*()i+＞＜＜＞＜*＞＞＜＞＜

(＜＜＜=＜

)＞＞＞

i＞

＞＞5.3.2

應(yīng)用算符優(yōu)先分析技術(shù)句型分析1.質(zhì)短語質(zhì)短語：句型中至少包含一個終結(jié)符號，但不包含其他任何質(zhì)短語的短語。如文法G[E]：E::=E+T|TT::=T*F|FF::=(E)|i

的句型E+T*F*i+i中的T*F和i是質(zhì)短語。如何人工尋找句型中的質(zhì)短語？先找出一切短語，再從最短的找起。

E+T*F*i+i中的短語和質(zhì)短語?

句型分析中自動尋找質(zhì)短語的思路：先從左向右尋找質(zhì)短語的尾終結(jié)符號，再從右向左尋找質(zhì)短語的頭終結(jié)符號，即，先找優(yōu)先關(guān)系

(？)再找優(yōu)先關(guān)系

(？)2.識別過程關(guān)于文法G[E]，對輸入符號串i+(i+i)*i句型分析

步驟句型

關(guān)系最左質(zhì)短語歸約到符號1

i+(i+i)*i#＜i＞+iF2

F+(i+i)*i#＜+＜(＜i＞+iF3

F+(F+i)*i#＜+＜(＜+＜i＞)iF4F+(F+F)*i#＜+＜(＜+＞)F+FE5F+(E)*i#＜+＜(=)＞*(E)F6F+F*i#＜+＜*＜i＞#iF7F+F*F#＜+＜*＞#F*FT8F+T#＜+＞#F+TE所以輸入符號串i+(i+i)*i是文法G[E]的句子。步驟

棧關(guān)系下一符號其余輸入部分最左質(zhì)短語0#<

i

+i*i#1#i>+i*i#i2#N<+i*i#3#N+<i

*i#4#N+i

>

*i#i5#N+N

<

*i#

6#N+N*<i#7#N+N*i

>#

i8#N+N*N>#

N*N9#N+N>#

N+N10#N#

所以輸入符號串i+(i+i)*i是文法G[E]的句子。

開始

置初值

/*top=1,S[top]=#*/

當(dāng)前輸入符號R

top-1

jY

S[top]VN

N

topj

S[j]與R間無優(yōu)先關(guān)系

Y

輸出“非句子”

出口

N

S[j]>R

N

top+1topRS[top]

Y/*尋找質(zhì)短語尾*/

S[j]Qj-1j

Nj-1j

S[j]VT

Y

S[j]<Q

N

/*尋找質(zhì)短語頭*/Y

調(diào)用語義子程序處理最左質(zhì)短語Sj+1…Stopj+1topNS[top]