【正文】 用 A a產(chǎn)生式進(jìn)行歸約 .但是在某種情況下 ,當(dāng)狀態(tài) k呈現(xiàn)于棧頂時(shí) ,棧里的符號(hào)串所構(gòu)成的活前綴 ba未必允許把 a規(guī)約成 沒(méi)有一個(gè)規(guī)范句型含有前綴 A a產(chǎn)生式進(jìn)行歸約未必有效 . ? 我們可以從上例中看到這個(gè)問(wèn)題 規(guī)范 LR分析表的構(gòu)造 ● 對(duì) SLR分析的思考 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 93） 5:L i? 0:S’ ?S S ?L=R S ?R L ?*R L ?I R ?L 3:S R? 4: L *?R R ?L L ?i L ?i 6:S L=?R R ?L L ?*R L ?i 8:R L? 7:L *R? 2:S L?=R R L? 1:S’ S ? 9:S L=R? = i S * * i R i * L L R R 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 91） L 規(guī)范 LR分析表的構(gòu)造 ● 結(jié)論 : ? 一由此看出 ,并非隨符都出現(xiàn)在規(guī)范句型中 . ? 對(duì)策 : 一給每個(gè) LR(0)項(xiàng)目添加展望信息 ,即添加句柄之后可能跟的終結(jié)符 ,因?yàn)檫@些終結(jié)符確實(shí)是規(guī)范句型中跟在句炳之后的 .這就是 LR(1)的方法 . ● 可能引起的問(wèn)題 一故 ,LR(1)項(xiàng)目是對(duì) LR(0)項(xiàng)目的分裂 ,若文法中終結(jié)符的數(shù)目為 n,則每個(gè) LR(0)項(xiàng)目都可以分裂成 n個(gè)LR(1)項(xiàng)目 .這可能會(huì)引起分析表的膨脹 . 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 95） 規(guī)范 LR分析表的構(gòu)造 ? 一、相關(guān)定義 LR(1)項(xiàng)目：形如（ A a?b,a)的二元式稱為L(zhǎng)R(1)項(xiàng)目，其中， A ab是文法的一個(gè)產(chǎn)生式，a是終結(jié)符，稱為搜索符。 2）二義文法決不是 LR文法 3） SLR分析法包含的展望信息是體現(xiàn)在利用了Follow(A)信息，可以解決 “ 歸約 —?dú)w約 ” 沖突。則對(duì)任何終結(jié)符a∈ Follow(A) ，置 ACTION[k,a]=rj；其中 j為產(chǎn)生式 A a的編號(hào)，即根據(jù) j號(hào)產(chǎn)生式 A a進(jìn)行歸約 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 84） SLR分析表的構(gòu)造 SLR分析表的構(gòu)造 二、構(gòu)造 SLR分析表的算法 3）若項(xiàng)目 S’ S?屬于 Ik，則 ACTION[k,]=acc； 4）若 GO(Ik,A)=Ij， A是非終結(jié)符，則 GoTo[k,A]=j； 5）分析表中凡不能用步驟 1至 4填入信息的空白項(xiàng)，均置上 “ 出錯(cuò)標(biāo)志 ” 。 ? 二、構(gòu)造 SLR分析表的算法 ? 設(shè) C={I0,I1,… ..In}以各項(xiàng)目集 Ik(k=0,… ...n)作的k為狀態(tài)序號(hào)，并以 S’ ?S包含的項(xiàng)目集作為初始狀態(tài)，同時(shí)將產(chǎn)生式進(jìn)行編號(hào)，然后按下列步驟填寫(xiě) ACTION表和 GOTO表： 1）若項(xiàng)目 A a?ab屬于 Ik狀態(tài)且 Go(Ik,a)=Ij， a為終結(jié)符，則置 ACTION[k,a]=Sj；即：移進(jìn) a，并轉(zhuǎn)向Ij狀態(tài)。 ? 一般而言，對(duì)于任何形如 I={X d ?bb, A a?, B a? }的 LR(0)項(xiàng)目集，若Follow(A)∩ Follow(B)= 且 b∈ Follow(A)，b∈ Follow(B),則可以根據(jù)當(dāng)前讀頭下符號(hào) a來(lái)消除沖突，即在構(gòu)造分析表的算法中做一些改變 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 60） SLR分析表的構(gòu)造 ?一、消除沖突 ?1)若當(dāng)前輸入符 a=b,做移進(jìn) 。 一、消除沖突 ? 一個(gè)有沖突的項(xiàng)目集。 LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 二、 LR(0)分析表的構(gòu)造算法 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 56） 例如：下面的文法是 LR(0)文法，但對(duì)這個(gè)文法的各個(gè)產(chǎn)生式給予編號(hào)并寫(xiě)成： ’ E aA bB cA d cB d 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 57） 確定化后 1:S’ E? 0:S’ ?E E ?aA E ?bB 4:A c?A A ?cA A ?d 2: E a?A A ?cA A ?d 3:E b?B B ?cB B ?d 5:B c?B B ?cB B ?d 6:E aA? 10:A d? 8:A cA? 7:E bB? 11:B d? 9:B cB? c c b E c c a B d d B A d A d 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 47） ?例如：下面文法 G的 LR(0)項(xiàng)目集規(guī)范族中含有如下一個(gè)項(xiàng)目集（狀態(tài)） I : — I={X d ?bb /*移進(jìn)項(xiàng)目 */ — A a ? /*歸約項(xiàng)目 */ — B a ? /*歸約項(xiàng)目 */ —— 這三個(gè)項(xiàng)目告訴我們應(yīng)做的動(dòng)作各不相同，出現(xiàn)了移進(jìn) —— 歸約沖突和歸約 ——?dú)w約沖突。 LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 二、 LR(0)分析表的構(gòu)造算法 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 55） (0)文法 ?定義：若文法 G按上面算法構(gòu)造出來(lái)的分析表不包含多重定義項(xiàng)，則該文法 G是 LR(0)文法。即根據(jù) j號(hào)產(chǎn)生式進(jìn)行歸約。即移進(jìn) a，并轉(zhuǎn)向 Ij狀態(tài)。 — B,直到 CLOSURE(I)不再擴(kuò)大為止 LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)項(xiàng)目集規(guī)范族的構(gòu)造 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 49） 0:S’ ?E E ?aA E ?bB 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 67） 0:S’ ?E E ?aA E ?bB 2: E a?A A ?cA A ?dc 1:S’ E? 3:E b?B B ?cB B ?d a E b 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 68） 0:S’ ?E E ?aA E ?bB 2: E a?A A ?cA A ?d 1:S’ E? 3:E b?B B ?cB B ?d a E b 4:A c?A A ?cA A ?d 10:A d? 6:E aA? c d A 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 69） 1:S’ E? 0:S’ ?E E ?aA E ?bB 4:A c?A A ?cA E ?d 2: E a?A A ?cA E ?dc 3:E b?B B ?cB B ?d 5:B c?B B ?cB B ?d 6:E aA? 10:A d? 7:E bB? 11:B d? c b E c a d B A d 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 70） 確定化后 1:S’ E? 0:S’ ?E E ?aA E ?bB 4:A c?A A ?cA A ?d 2: E a?A A ?cA A ?d 3:E b?B B ?cB B ?d 5:B c?B B ?cB B ?d 6:E aA? 10:A d? 7:E bB? 11:B d? 9:B cB? c c b E c a B d d B A d 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 71） 確定化后 1:S’ E? 0:S’ ?E E ?aA E ?bB 4:A c?A A ?cA A ?d 2: E a?A A ?cA A ?d 3:E b?B B ?cB B ?d 5:B c?B B ?cB B ?d 6:E aA? 10:A d? 8:A cA? 7:E bB? 11:B d? 9:B cB? c c b E c c a B d d B A d A 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 72） 3 8 6 7 4 9 10 1 5 2 11 15 14 12 16 13 18 17 e a E e c e A b e d B e c B d e e e e A e 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 46） ? 構(gòu)造 LR(0)分析表 —設(shè) C={I0,I1… ..In},以各項(xiàng)目集 Ik（ k=0,… .n) 的 k作為狀態(tài)符號(hào)，并以包含 S’ ?S的項(xiàng)目集作為初始狀態(tài)，同時(shí)將 G’文法的產(chǎn)生式進(jìn)行編號(hào)，然后按下列步驟填寫(xiě) ACTION表和GOTO表； 1）若項(xiàng)目 A a?ab 屬于 Ik的狀態(tài)且 GO(Ik,a)=Ij。 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 52） 例如：有一拓廣的文法 NFA S E E aA|bB A cA|d B cB|d 解： 這個(gè)文法的項(xiàng)目有： ’ ?E ’ E? ?aA a?A aA? ?cA c?A cA? ?d d? ?bB b?B bB? ?cB c?B cB? ?d d 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 45） 3. LR(0)項(xiàng)目集規(guī)范族的機(jī)器構(gòu)造 2）定義和構(gòu)造項(xiàng)目集的閉包 ? 設(shè) I是拓廣文法 G’的一個(gè)項(xiàng)目集，定義和構(gòu)造 I的閉包 CLOSURE(I) ? 構(gòu)造文法： — CLOSURE(I)。 ? 3）若在項(xiàng)目集中存在 A e?，不應(yīng)再做 GO函數(shù)轉(zhuǎn)向其它項(xiàng)目集，因?yàn)?A ?e和 A e?是同一項(xiàng)目，都是 A ?項(xiàng)目，它本身是歸約項(xiàng)目，不存在后繼項(xiàng)目。就擴(kuò)大一次 C中的項(xiàng)目集數(shù)，直到項(xiàng)目集數(shù)不再增加為止。 — B,直到 CLOSURE(I)不再擴(kuò)大為止 LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)項(xiàng)目集規(guī)范族的構(gòu)造 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 49） 3. LR(0)項(xiàng)目集規(guī)范族的機(jī)器構(gòu)造 3）狀態(tài)轉(zhuǎn)換函數(shù) GO ?GO(I,X)定義為 CLOSURE(J),其中 I,J都是項(xiàng)目集， X∈(V N∪V T), J={任何形如 A aX?b的項(xiàng)目 |A a?Xb∈I} —注：其含義是對(duì)于任意項(xiàng)目集 I,由于 I中有 A a?Xb項(xiàng)目， J中有 A aX?b項(xiàng)目，表示識(shí)別活前綴又移進(jìn)一個(gè)符號(hào) X LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)項(xiàng)目集規(guī)范族的構(gòu)造 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 50） 3. LR(0)項(xiàng)目集規(guī)范族的機(jī)器構(gòu)造 ? 4)構(gòu)造 LR(0)項(xiàng)目集規(guī)范族的算法 —過(guò)程如下： —{ C={CLOSURE(S’ ?S)} /*初態(tài)項(xiàng)目集 */ — DO —{for (對(duì) C中每個(gè)項(xiàng)目集 I和 G’中每個(gè)文法符號(hào) X) — IF ( GO(I,X)非