3.5自下而上語(yǔ)法分析1自上而下分析的方法是產(chǎn)生語(yǔ)言的自然過(guò)程。但是對(duì)于分析語(yǔ)言來(lái)講，自下而上分析的方法更自然因?yàn)檎Z(yǔ)法分析處理的對(duì)象一開(kāi)始都是終結(jié)符組成的串，而不是文法的開(kāi)始符號(hào)。同時(shí)，自下而上分析中最一般的方法，LR方法的能力比自上而下分析的LL方法要強(qiáng)，從而使得LR分析成為最為實(shí)用的語(yǔ)法分析方法。兩種主要的自下而上分析方法：算符優(yōu)先分析（不討論）LR分析3.5.1自下而上分析的基本方法2思路：從句子ω開(kāi)始，從左到右掃描ω，反復(fù)用產(chǎn)生式的左部替換產(chǎn)生式的右部、謀求對(duì)ω的匹配，最終得到文法的開(kāi)始符號(hào)，或者發(fā)現(xiàn)一個(gè)錯(cuò)誤。3.5.1.1規(guī)范歸約與“剪句柄”定義3.13設(shè)αβδ是文法G的一個(gè)句型，若存在S=*>αAδ，A=+>β，則稱β是句型αβδ相對(duì)于A的短語(yǔ)，特別的，若有A→β，則稱β是句型αβδ相對(duì)于產(chǎn)生式A→β的直接短語(yǔ)。一個(gè)句型的最左直接短語(yǔ)被稱為句柄。

■①直觀上，句型是一個(gè)完整結(jié)構(gòu)，短語(yǔ)是句型中的某部分(針對(duì)某非終結(jié)符)。S是一個(gè)句型，而不是一個(gè)短語(yǔ)(樹(shù)根不是短語(yǔ))。②短語(yǔ)形成的兩個(gè)要素：1．從S可以推導(dǎo)出A，即S=*>αAδ；2．從A至少一次推導(dǎo)出β，即A=+>β。例3.25

文法、分析樹(shù)與短語(yǔ)3.5.1.1規(guī)范歸約與“剪句柄”（續(xù)1）文法：E→E+T|TT→T*F|FF→id分析樹(shù)：id2*id3(F1)(F3)(F2)直接短語(yǔ)：id1id2id3

句柄：id1(F1)柄是唯一的）。特征：①短語(yǔ)：以非終結(jié)符為根子樹(shù)中所有從左到右排列的葉子；②直接短語(yǔ)：只有父子關(guān)系的樹(shù)中所有從左到右排列的葉子（樹(shù)高為2）；③句柄：最左邊父子關(guān)系樹(shù)中所有從左到右排列的葉子（句短語(yǔ)：id1+id2*id3

(E1)問(wèn)題：id1+id2是句型(T1)id1+id2*id3的短語(yǔ)嗎？句型：id1+id2*id3，id1

(E2,T2,F1)答案：不是。id2 (T3,

F3)

為什么？id3

(F2)①?zèng)]有一個(gè)E的子樹(shù)，它的全部葉子是id1+id2；或者②找不到某個(gè)E，使得E=*>E*id3，E=＋>id1+id233.5.1.1規(guī)范歸約與“剪句柄”（續(xù)2）定義3.14若α是文法G的句子且滿足下述條件，則稱序列αn，αn-1，...，α0是α的一個(gè)最左歸約。4αn=αα0=S（S是G的開(kāi)始符號(hào)）對(duì)任何i(0<i<=n)，αi-1是從αi將句柄替換為相應(yīng)產(chǎn)生式左部非終結(jié)符得到的。

■提醒：最左歸約的逆過(guò)程是一個(gè)最右推導(dǎo)，分別稱最右推導(dǎo)和最左

歸約為規(guī)范推導(dǎo)和規(guī)范歸約。例3.26

文法(1)

S→aABe (2)

A→b (3)

A→Abc (4)B→d對(duì)句子：abbcde的最左歸約：（2）

（3）

（4）

（1）abbcde

<=

aAbcde

<=

aAde

<=

aABe

<=

S問(wèn)題：如何直觀地看出句柄并進(jìn)行歸約？3.5.1.1規(guī)范歸約與“剪句柄”（續(xù)3(2)

A→b (3)

A→Abc (4)

B→d“剪句柄”：文法(1)S→aABe句子：abbcde假設(shè)已經(jīng)有了句子的分析樹(shù)，則：(1)

S→aABe5(2)

A→b (3)

A→Abc（2）

（3）

（4）(4)

B→d（1）abbcde<=aAbcde<=aAde<=aABe<=S需要解決的問(wèn)題：①確定右句型中將要?dú)w約的子串（確定句柄）；②確定如何選擇正確的產(chǎn)生式進(jìn)行歸約。移進(jìn)-歸約：用一個(gè)?！坝涀　睂⒁?dú)w約句柄的前綴，句柄未形成前移進(jìn)，形成后歸約。3.5.1.2移進(jìn)-歸約分析器工作模式移進(jìn)-歸約分析器的工作模式：

與預(yù)測(cè)分析對(duì)比：分析方法：格局與格局變換分析表驅(qū)動(dòng)器（模擬算法）預(yù)測(cè)分析表的構(gòu)造LL（文法、語(yǔ)言、分析器）6移進(jìn)-歸約分析器：

預(yù)測(cè)分析器：分析方法：格局與格局變換分析表驅(qū)動(dòng)器（模擬算法）LR（文法、語(yǔ)言、分析器）SLR分析表的構(gòu)造工作方法：放幻燈，每個(gè)幻燈片是一個(gè)格局。格局：（#棧，當(dāng)前剩余輸入#，改變格局的動(dòng)作）改變格局的動(dòng)作：①移進(jìn)(shift)：輸入序列中的終結(jié)符進(jìn)棧。(匹配終結(jié)符)②歸約(reduce)：將棧頂句柄替換為對(duì)應(yīng)非終結(jié)符。(最左歸約)③接受(accept)：宣告分析成功。④報(bào)錯(cuò)(error)：發(fā)現(xiàn)語(yǔ)法錯(cuò)誤，調(diào)用錯(cuò)誤恢復(fù)例程。73.5.1.2移進(jìn)-歸約分析器工作模式（續(xù)1）對(duì)照預(yù)測(cè)分析：①匹配終結(jié)符（彈出）②最左推導(dǎo)（展開(kāi)非終結(jié)符）可以看出：①句柄總是在棧頂形成。這是因?yàn)樵诜治龅倪^(guò)程中一旦形成某產(chǎn)生式的右部就立即進(jìn)行歸約，而從左到右掃描輸入，最早形成的自然是最左的直接短語(yǔ)；② 棧中保留的總是一個(gè)右句型的前綴（加上若干終結(jié)符形成句型），稱為活前綴；③如果將每次歸約邏輯上認(rèn)為是構(gòu)造對(duì)應(yīng)產(chǎn)生式的樹(shù)，則分析的全過(guò)程邏輯上就是從下到上構(gòu)造一棵分析樹(shù)；反之，如果將每次歸約邏輯上認(rèn)為是剪去假想分析樹(shù)上對(duì)應(yīng)產(chǎn)生式的孩子，則分析的全過(guò)程邏輯上就是從下到上為分析樹(shù)剪句柄。3.5.1.2移進(jìn)-歸約分析器工作模式（續(xù)2）例3.27

用移進(jìn)-歸約方法分析abbcde：(1)S→aABe

(2)A→b(4)B→d棧剩余輸入改變格局的動(dòng)作#abbcde#移進(jìn)#abbcde#移進(jìn)#abbcde#歸約，(2)A→b#aAbcde#移進(jìn)#aAbcde#移進(jìn)#aAbcde#歸約，(3)A→Abc#aAde#移進(jìn)#aAde#歸約，(4)B→d#aABe#移進(jìn)#aABe#歸約，(1)S→aABe#S#接受abbcde

<=

aAbcde

<=

aAde

<=

aABe

<=

S

(3)A→Abc可以看出：①②③需要解決的問(wèn)題：（由分析表確定）①如何保證棧中總是活前綴(指導(dǎo)移進(jìn))；②如何確定棧頂已經(jīng)形成句柄并選擇正確的產(chǎn)生式進(jìn)行歸約(指導(dǎo)歸約)。83.5.2

LR分析9LR分析的特點(diǎn)：①采用最一般的無(wú)回溯移進(jìn)-歸約方法；②可分析的文法是LL文法的真超集；③能夠及時(shí)發(fā)現(xiàn)錯(cuò)誤，快到從左到右掃描輸入序列的最大可能；④分析表較復(fù)雜，難以手工構(gòu)造。LR分析的核心：

移進(jìn)-歸約分析表＋驅(qū)動(dòng)器首先了解工作原理（分析表的組成、分析算法）然后推論分析表的構(gòu)造討論依據(jù)的文法：E→E-T（1）|T（2）T→T*F（3）|F（4）F→-F（5）|id（6）3.5.2.1

LR分析與LR文法E→E-T|TT→T*F|F F→-F|idid-*#ETF0s4s51231s6acc2r2s7r23r4r4r44r6r6r65s4s586s4s5937s4s5108r5r5r59r1s7r110r3r3r3<1>

移進(jìn)-歸約分析表 <2>

格局與改變格局的動(dòng)作開(kāi)始格局：(#0，ω#，移進(jìn))結(jié)束格局：(#0S，#， 接受)出錯(cuò)格局：(#δ，ω"#，報(bào)錯(cuò))改變格局的四個(gè)動(dòng)作：①action[s,a]=si：(移進(jìn))10②

=rj：用第j個(gè)產(chǎn)生式的左部替換棧中的句柄③④=acc：接收=blank：報(bào)錯(cuò)⑤goto[s,A]=s"：s狀態(tài)下遇到A轉(zhuǎn)移到狀態(tài)s"。提示：②和⑤共同完成歸約。動(dòng)作表(action) 轉(zhuǎn)移表(goto)action[s,a]確定改變格局的動(dòng)作(與輸入有關(guān))goto[s,A]指示非終結(jié)符的狀態(tài)轉(zhuǎn)移3.5.2.1

LR分析與LR文法（續(xù)1）算法3.8

LR分析輸入

輸入序列ω和文法G的LR分析表（action與goto）輸出若ω屬于L(G)，得到ω的規(guī)范歸約，否則指出一個(gè)錯(cuò)誤方法

初始格局為：（#0，ω#，移進(jìn)），其中0是初始狀態(tài)ip指向ω#中的第一個(gè)終結(jié)符，top指向棧頂初始狀態(tài)；loop s

:=

top^;

a

:=

ip^;case

action[s，a]

isshift

s":push(a);push(s");next(ip);--移進(jìn)reduce

by

A→β:pop(2*|β|);s"

:=

top^;push(A);--彈出句柄和相應(yīng)狀態(tài)--暴露出當(dāng)前棧頂狀態(tài)s"--產(chǎn)生式左部符號(hào)進(jìn)棧push(goto(s"，A));--新棧頂狀態(tài)進(jìn)棧write(A→β);accept:

return;--完成歸約，跟蹤分析軌跡--成功返回--出錯(cuò)處理others:

error;end

case;end

loop;

■習(xí)慣上：實(shí)際的算法中僅存放狀態(tài)，而在分析的格局中，僅顯示文法符號(hào)。（為什么？）11分析過(guò)程應(yīng)板書(shū)，內(nèi)容包括：1.分析表2.算法中的移進(jìn)、歸約動(dòng)作3.文法的產(chǎn)生式4.具體分析步驟id-*#ETF0s4s51231s6acc2r2s7r23r4r4r44r6r6r65s4s586s4s5937s4s5108r5r5r59r1s7r1r3

r3s1h0ifts"r:3push(a);

push(s");

next(ip);reduce

by

A→β:pop(2*|β|);

s":=top^;push(A);

push(goto(s"，A));write(A→β);3.5.2.1

LR分析與LR文法（續(xù)2）E→E-T|T

T→T*F|F F→-F|id棧剩余輸入動(dòng)作#0id--id*id#s4#0id4--id*id#r6(F→id)#0F3--id*id#r4(T→F)#0T2--id*id#r2(E→T)#0E1--id*id#s5#0E1-6-id*id#s5#0E1-6-5id*id#s4#0E1-6-5id4

*id#r6(F→id)#0E1-6-5F8

*id#r5(F→-F)#0E1-6F3

*id#r4(T→F)#0E1-6T9

*id#s7#0E1-6T9*7

id#s4#0E1-6T9*7id4

#r6(F→id)#0E1-6T9*7F10

#r3(T→T*F)#0E1-6F3

#r4(T→F)#0E1-6T9

#r1(E→E-T)#0E1#acc123.5.2.1

LR分析與LR文法（續(xù)3）定義3.15若為文法G構(gòu)造的移進(jìn)-歸約分析表中不含多重定義的條目則稱G為L(zhǎng)R(k)文法，分析器被稱為是LR(k)分析器，它所識(shí)別的語(yǔ)言被稱為L(zhǎng)R(k)語(yǔ)言。L表示從左到右掃描輸入序列，R表示逆序的最右推導(dǎo)，k表示為確定下一動(dòng)作向前看的終結(jié)符個(gè)數(shù)，一般情況下k<=1。當(dāng)k=1時(shí)，簡(jiǎn)稱LR。

■LR分析器是一類(lèi)分析器根據(jù)分析表的構(gòu)造，有LR(0)、SLR(1)、LALR(1)和LR(1)分析器它們功能的強(qiáng)弱和構(gòu)造的難度依次遞增。當(dāng)k>1后，分析器的構(gòu)造趨于復(fù)雜，一般情況下并不構(gòu)造k>1的LR(k)分析器。我們僅構(gòu)造SLR(1)分析器。13結(jié)

束14上節(jié)主要內(nèi)容：自下而上分析的基本方法：歸約（短語(yǔ)、直接短語(yǔ)、句柄、規(guī)范（最左）歸約）規(guī)范歸約的形象表示－剪句柄；移進(jìn)-歸約分析工作模式：格局與格局變換LR分析與LR文法：<1>分析表：動(dòng)作表與轉(zhuǎn)移表<2>模擬算法：改變格局的兩個(gè)重要?jiǎng)幼鳎七M(jìn)與歸約<3>LR分析器的實(shí)例分析<4>LR文法3.5.2.2構(gòu)造SLR(1)分析器思路：首先構(gòu)造一個(gè)可以識(shí)別文法G中所有活前綴的DFA，然后根據(jù)DFA和簡(jiǎn)單的向前看信息構(gòu)造SLR分析表。<1>活前綴與LR（0）項(xiàng)目集族定義3.16出現(xiàn)在移進(jìn)-歸約分析器棧中的右句型的前綴，被稱為文法G的活前綴（viable

prefix）。

■活前綴的兩個(gè)要素：右句型的前綴；

（#0E1-6-5

id*id#

s4）已在分析棧中即：活前綴＋若干剩余輸入（不在棧中）＝>右句型。這意味著：在移進(jìn)-歸約分析中，只要保證已掃描過(guò)的輸入序列可以歸約為一個(gè)活前綴，則分析到目前為止沒(méi)有錯(cuò)誤。構(gòu)造SLR分析器的關(guān)鍵：為文法G構(gòu)造一個(gè)識(shí)別它的所有活前綴的DFA。步驟：NFA→DFA問(wèn)題：識(shí)別活前綴的NFA是什么？153.5.2.2構(gòu)造SLR(1)分析器（續(xù)1）回顧產(chǎn)生式與產(chǎn)生式(E→E+T和T→T*F)的狀態(tài)轉(zhuǎn)換圖：它們是FA，而且是NFA。因?yàn)閺臓顟B(tài)1經(jīng)+既到達(dá)狀態(tài)2也到達(dá)狀態(tài)4（為什么？）；如何表示NFA的狀態(tài)？在產(chǎn)生式的右部加入一個(gè)點(diǎn)“.”，用它在右部的位置表示一個(gè)NFA的狀態(tài)。定義3.17一個(gè)LR(0)項(xiàng)目（簡(jiǎn)稱項(xiàng)目）是這樣一個(gè)產(chǎn)生式，在它右部的某個(gè)位置有一個(gè)點(diǎn)“.”。對(duì)于A→ε，它僅有一個(gè)項(xiàng)目A→.。■16對(duì)于文法G：E→E-T|T

T→T*F|F3.5.2.2構(gòu)造SLR(1)分析器（續(xù)2）F→-F|id它的全部LR(0)項(xiàng)目：E→.E-T E→E.-T E→E-.T E→E-T.T→T*.FF→-F.E→.TT→.T*FT→.FF→.-FF→.idE→T.T→T.*FT→F.F→-.FF→id.項(xiàng)目A→α.β顯示了分析過(guò)程中看到(移進(jìn))了產(chǎn)生式的多少。β不為空的項(xiàng)目稱為可移進(jìn)項(xiàng)目，β為空的項(xiàng)目稱為可歸約項(xiàng)目。項(xiàng)目如何識(shí)別活前綴：若T→.T*F是識(shí)別活前綴α的狀態(tài)，產(chǎn)生式T→T*F是識(shí)別活前綴αT*F的NFA。即：每個(gè)產(chǎn)生式是一個(gè)識(shí)T→T*F.別活前綴的NFA；每個(gè)項(xiàng)目是NFA的一個(gè)狀態(tài)；于是：所有產(chǎn)生式構(gòu)成文17法G識(shí)別活前綴的NFA集合，將其確定化即得到識(shí)別活前綴的DFA。則T→T.*F是識(shí)別活前綴αT的狀態(tài)。3.5.2.2構(gòu)造SLR(1)分析器（續(xù)3）18<2>拓廣文法與識(shí)別活前綴的DFAa．拓廣文法G"G"

=

G∪{S"→S}其中：S"→.S是識(shí)別S的初態(tài)， S"→S.是識(shí)別S的終態(tài)。

目的是使最終構(gòu)造的DFA狀態(tài)集中具有唯一初態(tài)和唯一終態(tài)文法G：

E→E-T|T

T→T*F|F F→-F|id的拓廣文法：

G"

=

G∪{E"→E}唯一初態(tài)與終態(tài)：

E"→.E

E"→E.b．NFA（項(xiàng)目）→DFA（項(xiàng)目集）詞法分析器－“子集法”：①ε

閉包(I)：從狀態(tài)集I不經(jīng)任何字符能到達(dá)的狀態(tài)全體；②smove（I，a）：所有從I經(jīng)字符a能直接到達(dá)的狀態(tài)全體。類(lèi)似的兩個(gè)過(guò)程：①closure(I)：從項(xiàng)目集I不經(jīng)任何文法符號(hào)到達(dá)的項(xiàng)目全體；②goto(I，x)：所有從I經(jīng)文法符號(hào)x能直接到達(dá)的項(xiàng)目全體。3.5.2.2構(gòu)造SLR(1)分析器（續(xù)4）定義3.18

項(xiàng)目集I的閉包c(diǎn)losure(I)是這樣一個(gè)項(xiàng)目集I中的所有項(xiàng)目屬于closure(I)；若A→α.Bβ屬于closure(I)，則所有形如B→.γ的項(xiàng)目屬于closure(I)；其它任何項(xiàng)目不屬于closure(I)。

■定義3.19

對(duì)所有屬于項(xiàng)目集I、且形如[A→α.Xβ]的項(xiàng)目，令X∈N∪T，則goto（I，X）是所有形如[A→αX.β]的項(xiàng)目。

■設(shè)J=goto(I，X)，K=closure(J)，則K中項(xiàng)目A→α.β分為兩類(lèi)：1.J=goto(I，X)：α非空，因?yàn)橹辽儆幸粋€(gè)X。2.

K-J：α=ε，即"."在產(chǎn)生式右部最左邊；可由某個(gè)J計(jì)算而來(lái)（K-J=closure(J)-J）。定義3.20項(xiàng)目[S"→.S]和所有“.”不在產(chǎn)生式右部最左邊的項(xiàng)目稱為核心項(xiàng)目(kernelitems)，其它所有“.”在產(chǎn)生式右部最左的項(xiàng)目(不包括[S"→.S])稱為非核心項(xiàng)目（nonkernel

items）。核心項(xiàng)目：J=goto(I，X)加S"→.S（作為項(xiàng)目集的代表）非核心項(xiàng)目：K-J=closure(J)-J（特點(diǎn)：可由某J計(jì)算得到）

193.5.2.2構(gòu)造SLR(1)分析器（續(xù)5）算法3.9

計(jì)算文法G的、基于LR(0)項(xiàng)目的、識(shí)別活前綴的DFA輸入：拓廣文法G"輸出：DFA=(C,

Dtran) --

C是狀態(tài)集，Dtran是狀態(tài)轉(zhuǎn)移方法：I

:=

closure(S"→

.S);

加入I到C中,且未標(biāo)記;

--

初態(tài)while

C中還有未標(biāo)記狀態(tài)I --

考察所有未標(biāo)記狀態(tài)loop

標(biāo)記I;for

I狀態(tài)下的每個(gè)文法符號(hào)x --

考察所有xloop

if

J

:=

closure(goto(I,x))非空

--下一狀態(tài)then

Dtran[I,x]:=

J; --

下一狀態(tài)轉(zhuǎn)移if

J不在C中 --

若為新?tīng)顟B(tài)則待考察20then加入J到C，且未標(biāo)記；end

if;end

if;end

loop;end

loop;■此DFA構(gòu)造應(yīng)先板書(shū)，然后再重復(fù)播放一次，以強(qiáng)調(diào)過(guò)程、幫助理解、加深記憶。3.5.2.2構(gòu)造SLR(1)分析器（續(xù)6）構(gòu)造DFA：①計(jì)算DFA的初態(tài)，I0=closure({E"→.E})（略）②計(jì)算所有狀態(tài)的所有狀態(tài)轉(zhuǎn)移，即考察每個(gè)未標(biāo)記狀態(tài)Ii的(closure(goto(Ii,x)))。初態(tài)：I0終態(tài)：I121這一堂課應(yīng)該板書(shū)!!!<3>如何識(shí)別活前綴223.5.2.2構(gòu)造SLR(1)分析器（續(xù)7定義3.21

若存在最右推導(dǎo)S"=*>αAω=>αβ1β2ω，則稱項(xiàng)目[A→■β1.β2]對(duì)活前綴αβ1有效。活前綴αβ1對(duì)項(xiàng)目A→β1.β2有效，具有兩層含意：①?gòu)奈姆ㄩ_(kāi)始符號(hào)，經(jīng)αβ1可到達(dá)該項(xiàng)目(項(xiàng)目所在狀態(tài))；②在當(dāng)前活前綴的情況下，該項(xiàng)目可指導(dǎo)下一步分析動(dòng)作(αAω=>αβ1β2ω)。活前綴與項(xiàng)目的關(guān)系：①一個(gè)項(xiàng)目可能對(duì)若干個(gè)活前綴有效（例1）項(xiàng)目A→β1.β2對(duì)所有從初態(tài)出發(fā)可以到達(dá)此項(xiàng)目的路徑上的標(biāo)記均有效（一個(gè)路徑標(biāo)記是一個(gè)活前綴）。②若干個(gè)項(xiàng)目可能對(duì)同一個(gè)活前綴有效（例2）項(xiàng)目集中的所有項(xiàng)目對(duì)同一活前綴均有效。綜合①②可知：同一項(xiàng)目集中的所有項(xiàng)目，對(duì)此項(xiàng)目集的所有活前綴均有效。即，項(xiàng)目集中的每個(gè)項(xiàng)目均有同等權(quán)利指導(dǎo)下一步動(dòng)作。<3>如何識(shí)別活前綴（續(xù)1）③有效項(xiàng)目的意義到目前為止分析是正確的；指導(dǎo)下一步的分析：A→β1.β2（可移進(jìn)項(xiàng)）：移進(jìn)β2中第一個(gè)終結(jié)符B→β.（可歸約項(xiàng)）：按產(chǎn)生式B→β歸約④項(xiàng)目集中的沖突和解決沖突的簡(jiǎn)單方法：SLR(1)當(dāng)一個(gè)項(xiàng)目集中同時(shí)存在：A→β1.β2和B→β1.：既可移進(jìn)又可歸約，移進(jìn)/歸約沖突。A→α.和B→α.：均可指導(dǎo)下一步分析，歸約/歸約沖突。解決方法：簡(jiǎn)單向前看一個(gè)終結(jié)符a：移進(jìn)/歸約沖突：若FIRST(β2)∩FOLLOW(B)=Φ，沖突可解決歸約/歸約沖突：若FOLLOW(A)∩FOLLOW(B)=Φ，沖突可解決若沖突可以解決，則稱文法為SLR(1)文法，構(gòu)造的分析表為SLR(1)分析表。否則需尋求能力更強(qiáng)的文法，即尋求新的項(xiàng)目集(LR(1)項(xiàng)目集)23FIRST(F)={-,id}FIRST(T)={-,id}FIRST(E)={-,id}FOLLOW(E")={#}FOLLOW(E)

={-,#}FOLLOW(T)={*,-,#}FOLLOW(F)={*,-,#}FIRST(E")=

{-,

id}考察：I1、I2、I9，均有移進(jìn)/歸約沖突。但是：I1：

FIRST(-T)∩FOLLOW(E")=ΦI2、I9：FIRST(*F)∩FOLLOW(E)=Φ所以：此文法是SLR(1)文法。

<3>

如何識(shí)別活前綴（續(xù)2）24本節(jié)主要內(nèi)容：構(gòu)造SLR(1)分析器25識(shí)別活前綴的DFA<1>活前綴<2>一個(gè)產(chǎn)生式是一個(gè)識(shí)別活前綴的NFA<3>LR(0)項(xiàng)目、識(shí)別活前綴的

NFA的狀態(tài)<4>LR(0)項(xiàng)目集、

DFA的狀態(tài)NFA到DFA的“子集法”算法：<1>closure(I)與closure(I)的構(gòu)造<2>goto(I,x)與goto(I,x)的構(gòu)造<3>算法的關(guān)鍵步驟closure(goto(I,x))DFA如何識(shí)別活前綴<1>對(duì)活前綴有效的項(xiàng)目<2>有效項(xiàng)目的意義<3>項(xiàng)目集中的沖突與解決沖突的方法結(jié)

束<4>SLR分析表的構(gòu)造26算1法.i3f.10

D構(gòu)FA造中S有LR不分能析解表決的移進(jìn)/歸約和歸約/歸約沖突輸入th基en于eGr的roLrR;(0)項(xiàng)目集的、識(shí)別活前綴的DFA=(C,Dtran)輸出el若seG是foSrLR每(1個(gè))的狀，態(tài)得轉(zhuǎn)到移aDctriaon[和i,gxo]t=oj，否則指出一個(gè)錯(cuò)誤方法

按下l述oo步p驟if構(gòu)x造∈分T析表then

action[i,x]:=Sj;else

goto[i,x]:=j;end

if;end

loop;for 狀態(tài)i的每個(gè)可歸約項(xiàng)A→α.loop

if S"→

S.then

action[i,#]:=acc;else

for每個(gè)a∈FOLLOW(A)loop

action[i,a]:=Rk;

end

loop;end

if;end

loop;end

if;2.DFA的初態(tài)（S"→.S所在的狀態(tài)），是分析表的開(kāi)始狀態(tài)。■此部分應(yīng)板書(shū)：1.算法2.識(shí)別活前綴的DFA3.非終結(jié)符的FOLLOW集合4.從DFA上看終態(tài)轉(zhuǎn)移的方法（如何填寫(xiě)action和goto信息）5.具體填寫(xiě)分析表的內(nèi)容，得到前邊已經(jīng)給出的分析表。分析表的構(gòu)造 <4>

SLR分析表的構(gòu)造（續(xù)1）for每個(gè)狀態(tài)轉(zhuǎn)移Dtran[i,x]=jloop

if

x∈T

then

action[i,x]:=Sj;

else

goto[i,x]:=j;

end

if;end

loop;for 狀態(tài)i的每個(gè)可歸約項(xiàng)A→α.loop

if S"→

S.then

action[i,

#]:=acc;else

for每個(gè)a∈FOLLOW(A)loop

action[i,a]:=Rk;end

loop;end

if;end

loop;id-*#ETF0s4s51231s6acc2r2s7r23r4r4r44r6r6r65s4s586s4s5937s4s5108r5r5r59r1s7r110r3r3r327I0－I2－I5－I6－I9：走過(guò)的路徑是iCtS，到達(dá)的狀態(tài)中存在移進(jìn)/歸約沖突，此路徑上各狀態(tài)的構(gòu)造應(yīng)板書(shū)3.5.2.3非SLR(1)文法“懸空”else文法：A→SS→iCtSS"|aS"→eS|ε經(jīng)過(guò)路徑iCtS達(dá)到的狀態(tài)中存在移進(jìn)/歸約沖突，因?yàn)橥瑫r(shí)有項(xiàng)目：S"→.eS

S"→.因?yàn)閑屬于FOLLOW(S")所以沖突無(wú)法解決。（不是SLR(1)文法）28<1>二義文法不是SLR(1)文法FIRST(C)=FIRST(S")

={e,ε}FIRST(S)FIRST(A)={i,

a}={i,

a}FOLLOW(A)

={#}FOLLOW(S)

={#,

e}FOLLOW(S")={#,

e}FOLLOW(C)

={t}I0－I4：經(jīng)路徑L達(dá)到狀態(tài)I4，存在移進(jìn)歸約沖突，此路徑應(yīng)板書(shū)<2>不是二義文法的非SLR(1)文法R→L文法：S→L=R|R L→*R|id識(shí)別活前綴的DFA：考察I4：29存在移進(jìn)/歸約沖突，不是LR(0)文法；又由于"="屬于FOLLOW(R)，故也不是SLR(1)文法。非二義文法：可以增加向前看終結(jié)符個(gè)數(shù)解決沖突，如LL(2)或LR(2)二義文法：無(wú)論向前看多少個(gè)終結(jié)符，也無(wú)法解決二義性。結(jié)論：二義文法不是上下文無(wú)關(guān)文法。3.5.2.4基于LR分析的語(yǔ)法分析器生成器簡(jiǎn)介（略）利用YACC設(shè)計(jì)語(yǔ)法分析器，關(guān)鍵也是了解和掌握兩點(diǎn)：①YACC提供什么形式的產(chǎn)生式，如何運(yùn)用它們?cè)O(shè)計(jì)語(yǔ)法分析器所需的文法；②YACC提供什么樣的機(jī)制支持語(yǔ)義動(dòng)作的嵌入，如何運(yùn)用這些機(jī)制進(jìn)行語(yǔ)義處理，如算術(shù)表達(dá)式值的計(jì)算、構(gòu)造所分析句子的語(yǔ)法樹(shù)等。303.6本章小結(jié)31<1>程序設(shè)計(jì)語(yǔ)言與文法正規(guī)式與正規(guī)文法上下文無(wú)關(guān)文法：CFG=(S,N,T,P)文法分類(lèi)：0型、1型、2型和3型<2>有關(guān)推導(dǎo)的基本概念產(chǎn)生語(yǔ)言的基本方法-推導(dǎo)：句子與句型、直接推導(dǎo)與推導(dǎo)、最左推導(dǎo)與左句型分析樹(shù)與語(yǔ)法樹(shù)：分析樹(shù)記錄推導(dǎo)過(guò)程并反映語(yǔ)言結(jié)構(gòu)語(yǔ)法樹(shù)僅反映語(yǔ)言結(jié)構(gòu)而忽略推導(dǎo)過(guò)程（樹(shù)