【文章內(nèi)容簡(jiǎn)介】 注： 1）構(gòu)造出的 NFA是包含有 e串的 NFA，可以使用子集法使之確定化，使之成為一個(gè)以項(xiàng)目集為狀態(tài)的DFA，這個(gè) DFA就是建立 LR分析算法的基礎(chǔ) 2）相應(yīng) DFA的每個(gè)狀態(tài)是一個(gè)項(xiàng)目集，稱(chēng)作 LR(0)項(xiàng)目集，整個(gè)狀態(tài)集稱(chēng)為 LR(0)項(xiàng)目集規(guī)范簇 3）在 DFA的一個(gè)狀態(tài)對(duì)應(yīng)的項(xiàng)目集內(nèi)，每個(gè)項(xiàng)目是 “ 等價(jià) ” 的，即從期待歸約的角度看相同 LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)分析表構(gòu)造 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 43） 2）由項(xiàng)目構(gòu)造 NFA的構(gòu)造方法 注： 4）有一個(gè)唯一的初態(tài)和一個(gè)唯一的接受態(tài)，但有若干個(gè)歸約態(tài)，表示有若干種活前綴的識(shí)別狀態(tài) 5）狀態(tài)反映了識(shí)別句柄的情況，既句柄的大多部分已進(jìn)棧，即知道了歷史情況 6）手工構(gòu)造文法的項(xiàng)目集規(guī)范簇很困難 LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)分析表構(gòu)造 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 44） 例如：有一拓廣的文法 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） NFA 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） 確定化后 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） LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)項(xiàng)目集規(guī)范族的構(gòu)造 3. LR(0)項(xiàng)目集規(guī)范族的機(jī)器構(gòu)造 ? 1）拓廣文法： 增加 S’ S產(chǎn)生式 ,使文法的開(kāi)始符號(hào)不出現(xiàn)在任何產(chǎn)生式右部，從而保證有唯一的接受項(xiàng)目 ? —注：即使原開(kāi)始符號(hào) S不出現(xiàn)在任何產(chǎn)生式右部，為了統(tǒng)一起見(jiàn)也要增加該產(chǎn)生式 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 48） 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)。 — A a?Bb屬于 CLOSURE(I),B是非終結(jié)符 ,那么，對(duì)于任何關(guān)于 B的產(chǎn)生式 B g,項(xiàng)目 B ?g也屬于 CLOSURE(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） 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)非空且不屬于 C) — {把 GO(I,X)加入 C中 } —} WHILE C 仍然在擴(kuò)大 —} 注：其中 C是集合，用于存放全部項(xiàng)目集 LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 一、 LR(0)項(xiàng)目集規(guī)范族的構(gòu)造 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 51） LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 ? 注： 1）此算法是迭代算法。置了 C的初態(tài)（初態(tài)僅包含第一個(gè)項(xiàng)目集）后，每經(jīng)過(guò)一次 FOR語(yǔ)句。就擴(kuò)大一次 C中的項(xiàng)目集數(shù)，直到項(xiàng)目集數(shù)不再增加為止。 ? 2）此算法是從 I0開(kāi)始，按該項(xiàng)目集內(nèi)的項(xiàng)目順序依次求出所有后繼項(xiàng)目集，由這樣一層一層向下生成的所有項(xiàng)目集的方法避免了項(xiàng)目集的遺漏。 ? 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)目。 ? 4）由這個(gè)項(xiàng)目集規(guī)范族 C中各個(gè)狀態(tài)及狀態(tài)函數(shù) GO可構(gòu)造一張識(shí)別活前綴的 DFA圖。 第六章 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)。 — A a?Bb屬于 CLOSURE(I),B是非終結(jié)符 ,那么，對(duì)于任何關(guān)于 B的產(chǎn)生式 B g,項(xiàng)目 B ?g也屬于 CLOSURE(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。a為終結(jié)符，則置 ACTION[k,a]=sj。即移進(jìn) a，并轉(zhuǎn)向 Ij狀態(tài)。 2）若項(xiàng)目 A a?∈I k,則對(duì)任何終結(jié)符 a（包括語(yǔ)句結(jié)束符 ），置 ACTION[k,a]=rj。即根據(jù) j號(hào)產(chǎn)生式進(jìn)行歸約。 LR(0)項(xiàng)目集族和 LR(0)分析表的構(gòu)造 二、 LR(0)分析表的構(gòu)造算法 第六章 LR分析法及分析程序自動(dòng)構(gòu)造（ 54） 確定化后 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