LR(0)文法分析報(bào)告

1、標(biāo)準(zhǔn)實(shí)用實(shí)驗(yàn)名稱： LR（0）文法分析一、 實(shí)驗(yàn)?zāi)康?：輸入：任意的壓縮了的上下文無(wú)關(guān)文法。輸出：相應(yīng)的 LR（0）分析表。二、 實(shí)驗(yàn)原理：對(duì)于 LR文法，我們可以自動(dòng)構(gòu)造相應(yīng)的 LR 分析表。為了構(gòu)造 LR 分析表，我們需要定義一個(gè)重要概念文法的規(guī)范句型“活前綴” 。這種句柄之后不含任何符號(hào)的前綴稱為活前綴。在 LR 分析工作過(guò)程中的任何時(shí)候，棧里的文法符號(hào)（自棧底而上） X1X2 Xm 應(yīng)該構(gòu)成活前綴， 把輸入串的剩余部分配上之后即應(yīng)成為規(guī)范句型 （如果整個(gè)輸入串確實(shí)構(gòu)成一個(gè)句子） 。因此，只要輸入串的已掃描部分保持可歸約成一個(gè)活前綴，那就意味著所掃描過(guò)的部分沒(méi)有錯(cuò)誤。對(duì)于一個(gè)文法 G，我

2、們可以構(gòu)造一個(gè)有限自動(dòng)機(jī)， 它能識(shí)別 G的所有活前綴，然后把這個(gè)自動(dòng)機(jī)轉(zhuǎn)變成 LR 分析表，按照該 LR 分析表進(jìn)行 LR 分析，就能保證在分析的過(guò)程中，如果分析的句子是正確的，棧里的文法符號(hào)（自棧底而上）始終構(gòu)成活前綴。假若一個(gè)文法 G的拓廣文法 G 的活前綴識(shí)別自動(dòng)機(jī)中的每個(gè)狀態(tài)（項(xiàng)目集）不存在下述情況：（1）既含移進(jìn)項(xiàng)目又含歸約項(xiàng)目； （ 2）含有多個(gè)歸約項(xiàng)目，則稱 G是一個(gè) LR（0）文法。該自動(dòng)機(jī)的狀態(tài)集合即為該文法的 LR（0）項(xiàng)目集規(guī)范族。構(gòu)造識(shí)別文法活前綴 DFA有 3 種方法：（1）根據(jù)形式定義求出活前綴的正則表達(dá)式，然后由此正則表達(dá)式構(gòu)造 NFA 再確定為 DFA；（2）求

3、出文法的所有項(xiàng)目，按一定規(guī)則構(gòu)造識(shí)別活前綴的 NFA再確定化為DFA；（3）使用閉包函數(shù)（ CLOSURE）和轉(zhuǎn)向函數(shù) (GO(I,X) 構(gòu)造文法 G的 LR(0) 的項(xiàng)目集規(guī)范族，再由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系來(lái)得到識(shí)別活前綴的DFA。符號(hào)串的前綴是指該符號(hào)串的任意首部， 包括空串。例如，對(duì)于符號(hào)串 abc，其前綴有， a，ab，abc。如果輸入串沒(méi)有錯(cuò)誤的話，一個(gè)規(guī)范句型的活前綴是該句型的一個(gè)前綴， 但它不含句柄之后的任何符號(hào)。 之所以稱為活前綴， 是因?yàn)樵谠撉熬Y后聯(lián)接尚未輸入的符號(hào)串可以構(gòu)成一個(gè)規(guī)范句型?；钋熬Y與句柄的關(guān)系如下：（1）活前綴已含有句柄的全部符號(hào)，表明產(chǎn)生式 A的右部已

4、出現(xiàn)在棧頂。（2）活前綴只含句柄的一部分符號(hào)，表明 A 1 2的右部子串 1已出現(xiàn)在棧頂，期待從輸入串中看到 2推出的符號(hào)。（3）活前綴不含有句柄的任何符號(hào)， 此時(shí)期望 A的右部所推出的符號(hào)串。在文法 G的每個(gè)產(chǎn)生式的右部（候選式）的任何位置上添加一個(gè)圓點(diǎn)，所構(gòu)成的每個(gè)產(chǎn)生式稱為 LR（0）項(xiàng)目。如產(chǎn)生式 A xyz 有如下項(xiàng)目： A .xyz ， A x.yz ，A xy.z ，A xyz. 。為刻劃分析過(guò)程中的文法的每一個(gè)產(chǎn)生式的右部文案大全標(biāo)準(zhǔn)實(shí)用符號(hào)已有多大一部分被識(shí)別 （出現(xiàn)在棧頂） ，可以用這種標(biāo)有圓點(diǎn)的產(chǎn)生式來(lái)確定。（ 1） A . 刻劃產(chǎn)生式 A的右部已出現(xiàn)在棧頂。（2）A 1

5、. 2 刻劃 A 1 2的右部子串 1已出現(xiàn)在棧頂，期待從輸入串中看到 2推出的符號(hào)。（3）A. 刻劃沒(méi)有句柄的任何符號(hào)在棧頂，此時(shí)期望 A的右部所推出的符號(hào)串。（ 4）對(duì)于 A的 LR(0) 項(xiàng)目只有 A。*設(shè)文法 G=（VT，VN，S，P）是一個(gè)上下文無(wú)關(guān)文法，若存在一個(gè)規(guī)范推導(dǎo)Srm錯(cuò)誤！未找到引用源。 Aw 錯(cuò)誤！未找到引用源。錯(cuò)誤！ 未找到引用源。 1錯(cuò)誤！未找到引用源。 2w（其中 A錯(cuò)誤！未找到引用源。錯(cuò)誤！未找到引用源。 1錯(cuò)誤！未找到引用源。 2錯(cuò)誤！未找到引用源。 P），則稱項(xiàng)目 A錯(cuò)誤！未找到引用源。錯(cuò)誤！未找到引用源。 1? 錯(cuò)誤！未找到引用源。 2對(duì)活前綴 錯(cuò)誤！未找

6、到引用源。=錯(cuò)誤！未找到引用源。錯(cuò)誤！未找到引用源。 1是有效的，即 LR(0) 有效項(xiàng)目。從直觀意義上講，一個(gè) LR(0) 項(xiàng)目指明了在分析過(guò)程中的某一步我們看到產(chǎn)生式的多大部分被識(shí)別， LR(0) 項(xiàng)目中的圓點(diǎn)可看成是分析棧棧頂與輸入串的分界線，圓點(diǎn)左邊為已進(jìn)入分析棧的部分，右邊是當(dāng)前輸入或繼續(xù)掃描的符號(hào)串。不同的 LR(0) 項(xiàng)目，反映了分析棧頂?shù)牟煌闆r。我們根據(jù) LR(0) 項(xiàng)目的作用不同，將其分為四類：（1）歸約項(xiàng)目：表現(xiàn)形式： Aa.這類 LR(0) 項(xiàng)目表示句柄 a 恰好包含在棧中，即當(dāng)前棧頂?shù)牟糠謨?nèi)容構(gòu)成了所期望的句柄，應(yīng)按 Aa 進(jìn)行歸約。（2）接受項(xiàng)目：表現(xiàn)形式： S a

7、.其中 S 是文法惟一的開(kāi)始符號(hào)。這類 LR(0) 項(xiàng)目實(shí)際是特殊的歸約項(xiàng)目，表示分析棧中內(nèi)容恰好為 a，用 S a 進(jìn)行歸約，則整個(gè)分析成功。（3）移進(jìn)項(xiàng)目：表現(xiàn)形式： Aa. b（ bVT）這類 LR(0) 項(xiàng)目表示分析棧中是不完全包含句柄的活前綴，為構(gòu)成恰好有句柄的活前級(jí)，需將 b 移進(jìn)分析棧。（4）待約項(xiàng)目：表現(xiàn)形式： A .B （ B VN）這類 LR(0) 項(xiàng)目表示分析棧中是不完全包含句柄的活前綴，為構(gòu)成恰好有句柄的活前綴，應(yīng)把當(dāng)前輸入字符串中的相應(yīng)內(nèi)容先歸約到B。在給出 LR(0) 項(xiàng)目的定義和分類之后，我們從這些LR(0) 項(xiàng)目出發(fā)，來(lái)構(gòu)造能識(shí)別文法所有前綴的有限自動(dòng)機(jī)。 其步

8、驟是：首先構(gòu)造能識(shí)別文法所有活前綴的非確定的有限自動(dòng)機(jī)， 再將其確定化和最小化， 最終得到所需的確定的有限自動(dòng)機(jī)。由文法 G的 LR(0) 項(xiàng)目構(gòu)造識(shí)別文法 G的所有活前綴的非確定有限自動(dòng)機(jī)的方法：文案大全標(biāo)準(zhǔn)實(shí)用（1）規(guī)定含有文法開(kāi)始符號(hào)的產(chǎn)生式（設(shè)S A）的第一個(gè) LR(0) 項(xiàng)目（即S .A ）為 NFA的惟一初態(tài)。（2）令所有 LR(0) 項(xiàng)目分別對(duì)應(yīng) NFA的一個(gè)狀態(tài)且 LR(0) 項(xiàng)目為歸約項(xiàng)目的對(duì)應(yīng)狀態(tài)為終態(tài)。（3）若狀態(tài) i 和狀態(tài) j 出自同一文法 G的產(chǎn)生式且兩個(gè)狀態(tài) LR(0) 項(xiàng)目的圓點(diǎn)只相差一個(gè)位置，即：若 i 為 XX1X2· Xi-1 ·Xi

9、Xn， j 為 X X1X2 Xi ·Xi+1 Xn，則從狀態(tài) i 引一條標(biāo)記為 Xi 的弧到狀態(tài) j 。（4）若狀態(tài) i 為待約項(xiàng)目（設(shè) X· A），則從狀態(tài) i 引弧到所有 A · r 的狀態(tài)。為了使“接受”狀態(tài)易于識(shí)別，我們通常將文法G進(jìn)行拓廣。假定文法 G 是一個(gè)以 S 為開(kāi)始符號(hào)的文法，我們構(gòu)造一個(gè) G ，它包含了整個(gè) G，但它引進(jìn)了一個(gè)不出現(xiàn)在 G中的非終結(jié)符 S ，并加進(jìn)一個(gè)新產(chǎn)生式 S S，以 S SG 為開(kāi)始符號(hào)。那么，我們稱 G 是 G的拓廣文法。這樣，便會(huì)有一個(gè)僅含項(xiàng)目 S S 的狀態(tài)，這就是惟一的“接受”態(tài)。如果 I 是文法 G的一個(gè)項(xiàng)目集

10、，定義和構(gòu)造 I 的閉包 CLOSURE(I)如下：（1）I 的項(xiàng)目都在 CLOSURE(I)中。（2）若A .B 屬于 CLOSURE(I)，則每一形如 B.的項(xiàng)目也屬于CLOSURE(I)。（3）重復(fù)（ 2）直到 CLOSURE(I)不再擴(kuò)大。定義轉(zhuǎn)換函數(shù)如下：GO（ I ， X） = CLOSURE（ J）其中： I 為包含某一項(xiàng)目集的狀態(tài)，X為一文法符號(hào)， J= A X .| A .XI 。圓點(diǎn)不在產(chǎn)生式右部最左邊的項(xiàng)目稱為核，惟一的例外是 S .S ，因此用GOTO（I ，X）狀態(tài)轉(zhuǎn)換函數(shù)得到的 J為轉(zhuǎn)向后狀態(tài)閉包項(xiàng)目集的核。使用閉包函數(shù) （CLOSURE）和轉(zhuǎn)換函數(shù) (GO(I,X

11、) 構(gòu)造文法 G的LR(0) 的項(xiàng)目集規(guī)范族，步驟如下：（1）置項(xiàng)目 S .S 為初態(tài)集的核，然后對(duì)核求閉包 CLOSURE（S .S ）得到初態(tài)的閉包項(xiàng)目集。（2）對(duì)初態(tài)集或其他所構(gòu)造的項(xiàng)目集應(yīng)用轉(zhuǎn)換函數(shù)GO(I，X)= CLOSURE(J)求出新?tīng)顟B(tài) J的閉包項(xiàng)目集。（3）重復(fù)（ 2）直到不出現(xiàn)新的項(xiàng)目集為止。計(jì)算 LR（0）項(xiàng)目集規(guī)范族 C=I 0，I 1 , . In 的算法偽代碼如下：Procedure itemsets(G );Begin C := CLOSURE (S.S)RepeatFor C中每一項(xiàng)目集 I 和每一文法符號(hào) XDo if GO(I,X)非空且不屬于 CThen

12、把 GO(I,X)放入 C中Until C不再增大End;文案大全標(biāo)準(zhǔn)實(shí)用一個(gè)項(xiàng)目集可能包含多種項(xiàng)目，若移進(jìn)和歸約項(xiàng)目同時(shí)存在，則稱移進(jìn) - 歸約沖突，若歸約和歸約項(xiàng)目同時(shí)存在，則稱歸約- 歸約沖突。下面看一個(gè)具體的例子：我們希望能根據(jù)識(shí)別文法的活前綴的 DFA建立 LR分析器，因此，需要研究這個(gè) DFA的每個(gè)項(xiàng)目集（狀態(tài)）中的項(xiàng)目的不同作用。我們說(shuō)項(xiàng)目A 1. 2 對(duì)活前綴 1 是有效的，其條件是存在規(guī)范推導(dǎo)SA12。一般而言，同一項(xiàng)目可能對(duì)幾個(gè)活前綴都是有效的（當(dāng)一個(gè)項(xiàng)目出現(xiàn)在幾個(gè)不同的集合中時(shí)便是這種情形）。若歸約項(xiàng)目A 1 . 對(duì)活前綴1 是有效的，則它告訴我們應(yīng)把符號(hào)串1 歸約為 A

13、，即把活前綴1 變成 A。若移進(jìn)項(xiàng)目 A . 對(duì)活前綴1 是有效的，則它告訴我們，句柄尚未形成，12因此，下一步動(dòng)作應(yīng)是移進(jìn)。但是，可能存在這樣的情形，對(duì)同一活前綴，存在若干項(xiàng)目對(duì)它都是有效的。而且它們告訴我們應(yīng)做的事情各不相同，互相沖突。這種沖突通過(guò)向前多看幾個(gè)輸入符號(hào)，或許能夠獲得解決。對(duì)于每個(gè)活前綴， 我們可以構(gòu)造它的有效項(xiàng)目集。 實(shí)際上，一個(gè)活前綴的有效項(xiàng)目集正是從上述的 DFA的初態(tài)出發(fā)，經(jīng)讀出后而到達(dá)的那個(gè)項(xiàng)目集 （狀態(tài)）。換言之，在任何時(shí)候，分析棧中的活前綴 X1X2 Xm 的有效項(xiàng)目集正是棧頂狀態(tài) Sm所代表的那個(gè)集合。這是 LR 分析理論的一條基本定理。實(shí)際上，棧頂?shù)捻?xiàng)目集（

14、狀態(tài)）體現(xiàn)了棧里的一切有用信息歷史。前面我們已經(jīng)對(duì) LR（0）文法進(jìn)行了定義 , 下面我們來(lái)看一下 LR（0）分析表是如何構(gòu)造的。對(duì)于 LR（0）文法，我們可以直接從它的項(xiàng)目集規(guī)范族 C 和活前綴識(shí)別自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換函數(shù) GO構(gòu)造出 LR 分析表。下面是構(gòu)造 LR（0）分析表的算法。假定 C=I 0, I 1, ， In ，令每個(gè)項(xiàng)目集 I k的下標(biāo) k為分析器的一個(gè)狀態(tài)，因此， G'的 LR(0) 分析表含有狀態(tài) 0，1， ， n。令那個(gè)含有項(xiàng)目 S' S的I k的下標(biāo) k為初態(tài)。 ACTION子表和 GOTO子表可按如下方法構(gòu)造：（1）若項(xiàng)目 A .a 屬于 I k 且 G

15、O(I k, a)= I j , a 為終結(jié)符，則置 ACTIONk, a 為“把狀態(tài) j 和符號(hào) a 移進(jìn)?！保?jiǎn)記為“ sj ”；（2）若項(xiàng)目 A屬于 I k，那么，對(duì)任何終結(jié)符 a，置 ACTIONk，a 為“用產(chǎn)生式 A進(jìn)行規(guī)約”，簡(jiǎn)記為“ r j ”；其中，假定 A為文法 G' 的第 j 個(gè)產(chǎn)生式；（3）若項(xiàng)目 S' S屬于 I k,則置 ACTIONk, # 為“接受” ，簡(jiǎn)記為 “acc”；（4）若 GO (I k, A)= Ij , A為非終結(jié)符，則置 GOTOk, A=j ；（5）分析表中凡不能用上述 1至4填入信息的空白格均置上“出錯(cuò)標(biāo)志”。按上述算法構(gòu)造的

16、含有 ACTION和GOTO兩部分的分析表，如果每個(gè)入口不含多重定義，則稱它為文法 G的一張 LR(0) 分析表。具有 LR(0) 表的文法 G稱為一個(gè) LR（ 0）文法， LR(0) 文法是無(wú)二義的。例如，文法 G（E）的拓廣文法如下：(0)S' E(1)E aA(2)E bB(3)A cA(4)A d(5)B cB文案大全標(biāo)準(zhǔn)實(shí)用三、實(shí)驗(yàn)內(nèi)容及其代碼如下所示：#include<iostream>#include<stdio.h>#include<fstream>#include<malloc.h>using namespace std

17、;#define OK 1#define ERROR 0#define N 50#define Y 20int vtnum,vnnum,pronum;/依次是終結(jié)符個(gè)數(shù)，非終結(jié)符個(gè)數(shù)，產(chǎn)生式個(gè)數(shù)char vtN;/終結(jié)符集char vnN;/非終結(jié)符集char oldNN='/0'/用于存儲(chǔ)文法char oldzNN='/0'/用于存儲(chǔ)增廣文法int ACTIONNN=0;/動(dòng)作表int GOTONN=0;/狀態(tài)轉(zhuǎn)換表typedef struct SqEint t;/狀態(tài)編號(hào)char c1;SqE;/ 堆棧元素typedef struct itemint f;/

18、項(xiàng)目前部，表示產(chǎn)生式編號(hào)int l;/項(xiàng)目后部，表示停頓點(diǎn)在產(chǎn)生式的位置item;/定義項(xiàng)目typedef struct linkint f;/ 連接前部，表示所用符號(hào)的編號(hào)，非終結(jié)符編號(hào) =在 vn 中的下標(biāo) +100int l;/連接后部，即狀態(tài)編號(hào)link;/定義狀態(tài)之間的連接typedef struct cdint item_num;/狀態(tài)中的項(xiàng)目數(shù)int link_num;/狀態(tài)的連接數(shù)item wN;/項(xiàng)目集link uN;/連接集cd;/定義狀態(tài)文案大全標(biāo)準(zhǔn)實(shí)用typedef struct DFAint cd_num;/狀態(tài)個(gè)數(shù)cd sN+1;/狀態(tài)集DFA;/ 定義規(guī)范 LR(

19、0) 項(xiàng)目族 ,D.sN 用作狀態(tài)轉(zhuǎn)換函數(shù) go_switch() 的存儲(chǔ)空間DFA D;void dfa();/求規(guī)范 LR(0) 項(xiàng)目族void closure(int);/求閉包void go_switch(int,int);/求轉(zhuǎn)換int test_go_switch();void add_go_switch();/增加新?tīng)顟B(tài)void del_go_switch();/清空狀態(tài)轉(zhuǎn)換函數(shù)的存儲(chǔ)空間void action();/構(gòu)造 ACTION表void go_answer();/構(gòu)造 GOTO表int control();/總控程序int length(int);/返回增廣文法產(chǎn)生式右

20、部的長(zhǎng)度int test(char);void printf_ag();/輸出 ACTION表和 GOTO表bool test_link(int i,int num);void main()int i,j;ifstreamin("input1.txt",ios_base:in);/讀 文 件 , 從 文 件 中 讀 入pronum,vtnum,vnnum 以及產(chǎn)生式in>>pronum>>vnnum>>vtnum;in>>vn;in>>vt;for(i=1;i<=pronum;i+)in>>old

21、i;/將產(chǎn)生式存入 old,old1為第一個(gè)產(chǎn)生式for(i=1;i<=pronum;i+)for(j=0;oldij!='/0'j+)oldzij=oldij;/將產(chǎn)生式從 old錄入 oldzoldz00='P'oldz01=old10;/加入 P->S，將原文法擴(kuò)充，使其變?yōu)樵鰪V文法vtvtnum='$'/把結(jié)束符 '$' 加入終結(jié)符集D.cd_num=0;for(i=0;i<=N;i+)D.si.item_num=0;D.si.link_num=0;/初始化狀態(tài)個(gè)數(shù)、連接個(gè)數(shù)、項(xiàng)目個(gè)數(shù)文案大全標(biāo)準(zhǔn)實(shí)用df

22、a();action();go_answer();printf_ag();control();/ 求一個(gè)狀態(tài)的閉包void closure(int i)int j,k,m,x,flag;doj=D.si.item_num;/j 是本輪循環(huán)開(kāi)始前的項(xiàng)目數(shù) for(k=0;k<D.si.item_num;k+)for(m=0;m<=pronum;m+)if(oldzm0=oldzD.si.wk.fD.si.wk.l)/對(duì) 當(dāng)前狀態(tài) i 中的每個(gè)項(xiàng)目，查詢每個(gè)產(chǎn)生式，例如：A->a.Ab 應(yīng)找到 A->.flag=0;/判斷該項(xiàng)是否在當(dāng)前狀態(tài)i 中, 即檢查 (m,1) 是否

23、存在于狀態(tài) i 中, 保證求閉包時(shí)加入的新項(xiàng)目和原項(xiàng)目集不重合for(x=0;x<D.si.item_num;x+)if(D.si.wx.f=m&&D.si.wx.l=1)flag=1;break;if(flag=0)/如果該項(xiàng)不在當(dāng)前狀態(tài)i 中，將其加入狀態(tài) iD.si.wD.si.item_num.f=m;D.si.wD.si.item_num.l=1;D.si.item_num+;while(j!=D.si.item_num);/當(dāng)一輪沒(méi)有新的項(xiàng)目加入i 時(shí)，結(jié)束循環(huán)文案大全標(biāo)準(zhǔn)實(shí)用/ 狀態(tài)轉(zhuǎn)換函數(shù)，i 是狀態(tài)編號(hào)，num是符號(hào)編號(hào)，狀態(tài)轉(zhuǎn)換函數(shù)的結(jié)果存于 sN v

24、oid go_switch(int i,int num) int j; for(j=0;j<D.si.item_num;j+)if(test(oldzD.si.wj.fD.si.wj.l)=num)D.sN.wD.sN.item_num.f=D.si.wj.f; D.sN.wD.sN.item_num.l=D.si.wj.l+1; D.sN.item_num+;closure(N);/ 返回終結(jié)符和非終結(jié)符的標(biāo)號(hào) , 判斷符號(hào)的類型 ,0<= 終結(jié)符返回值 <100,100<= 非終結(jié)符返回值 <200, 錯(cuò)誤符號(hào)返回值 =200int test(char c)

25、int i,j;for(i=0;i<vtnum;i+) if(vti=c) break;if(i<vtnum)return i;elsefor(j=0;j<vnnum;j+)if(vnj=c)break;if(j<vtnum) return (100+j);elsereturn 200;/ 檢驗(yàn)狀態(tài)轉(zhuǎn)換函數(shù)的結(jié)果 int test_go_switch()int i,j,k,flag;if(D.sN.item_num=0)/判斷狀態(tài)轉(zhuǎn)換的結(jié)果是否為空， 即當(dāng)前狀態(tài)可否接收該字符return 0;else文案大全標(biāo)準(zhǔn)實(shí)用 for(i=0;i<D.cd_num;i+)/

26、選定一狀態(tài)，對(duì)sN 中的每個(gè)項(xiàng)目進(jìn)行循環(huán)，如果存在一個(gè)項(xiàng)目在當(dāng)前狀態(tài)中未找到，即flag=0 ，立即跳至下一狀態(tài)flag=1;/判斷狀態(tài)轉(zhuǎn)換函數(shù)的結(jié)果是否已經(jīng)完全包含于某一現(xiàn)有狀態(tài)中，例如 go_switch( 狀態(tài) 4, 符號(hào) a) 依然存在于狀態(tài) 4 中，go_switch( 狀態(tài) 4, 符號(hào) c) 已經(jīng)存在于狀態(tài) 5 中for(j=0;j<D.sN.item_num;j+)/如果在當(dāng)前狀態(tài) i 中找不到 sN的當(dāng)前項(xiàng)目 j, 就跳至下一狀態(tài)for(k=0;k<D.si.item_num;k+)if(D.si.wk.f=D.sN.wj.f&&D.si.wk.l=

27、D.sN.wj.l)break;if(k>=D.si.item_num) flag=0; break; if(flag=1)return 1000+i;return 1;/ 狀態(tài)轉(zhuǎn)換函數(shù)的結(jié)果未被任何現(xiàn)有狀態(tài)完全包含，完全滿足建立新?tīng)顟B(tài)的條件/ 把狀態(tài)轉(zhuǎn)換函數(shù)的結(jié)果加入 DFA，即當(dāng)建立新?tīng)顟B(tài)的條件符合時(shí)，建立新的狀態(tài) sD.cd_numvoid add_go_switch()int i;for(i=0;i<D.sN.item_num;i+)D.sD.cd_num.wD.sD.cd_num.item_num.f=D.sN.wi.f; D.sD.cd_num.wD.sD.cd_num

28、.item_num.l=D.sN.wi.l; D.sD.cd_num.item_num+;D.cd_num+;/ 清空狀態(tài)轉(zhuǎn)換函數(shù)的存儲(chǔ)空間void del_go_switch()D.sN.item_num=0;文案大全標(biāo)準(zhǔn)實(shí)用/ 構(gòu)造規(guī)范 LR(0) 項(xiàng)目族void dfa()int i,j,k;D.s0.w0.f=0;D.s0.w0.l=1;D.cd_num+;D.s0.item_num+;closure(0);/ 把 P->S 加入初狀態(tài)，并求其閉包 do i=D.cd_num;/ 本輪循環(huán)開(kāi)始時(shí)狀態(tài)數(shù)for(j=0;j<D.cd_num;j+)/對(duì)每個(gè)狀態(tài)進(jìn)行循環(huán)for(k

29、=0;k<vnnum;k+)/對(duì)當(dāng)前狀態(tài)，每個(gè)非終結(jié)符if(!test_link(j,k+100)/檢驗(yàn)當(dāng)前狀態(tài)用當(dāng)前非終結(jié)符構(gòu)造的連接是否已經(jīng)存在，若存在，則跳至下一非終結(jié)符，這樣可以防止 do_while() 二次執(zhí)行時(shí)，將連接集重新加入當(dāng)前狀態(tài)，比如 s0go_switch(j,k+100);/對(duì)當(dāng)前狀態(tài)，當(dāng)前符號(hào)調(diào)用狀態(tài)轉(zhuǎn)換if(test_go_switch()=1)/如果符合建立新?tīng)顟B(tài)的條件add_go_switch();D.sj.uD.sj.link_num.f=k+100;/建立當(dāng)前狀態(tài)和新?tīng)顟B(tài)的連接D.sj.uD.sj.link_num.l=D.cd_num-1;D.sj

30、.link_num+;elseif(test_go_switch()>=1000)/如果狀態(tài)轉(zhuǎn)換的結(jié)果包含于某一現(xiàn)有狀態(tài)D.sj.uD.sj.link_num.f=k+100;/建立當(dāng)前狀態(tài)和該現(xiàn)有狀態(tài)的連接D.sj.uD.sj.link_num.l=test_go_switch()-1000;D.sj.link_num+;del_go_switch();/清空f(shuō)or(k=0;k<vtnum;k+)/對(duì)當(dāng)前狀態(tài)，每個(gè)終結(jié)符文案大全標(biāo)準(zhǔn)實(shí)用if(!test_link(j,k)go_switch(j,k);if(test_go_switch()=1)add_go_switch();D.

31、sj.uD.sj.link_num.f=k;D.sj.uD.sj.link_num.l=D.cd_num-1;D.sj.link_num+;elseif(test_go_switch()>=1000)D.sj.uD.sj.link_num.f=k;D.sj.uD.sj.link_num.l=test_go_switch()-1000;D.sj.link_num+;del_go_switch();while(i!=D.cd_num);/當(dāng)一輪沒(méi)有新的狀態(tài)產(chǎn)生時(shí)，結(jié)束/ 構(gòu)造 ACTION表void action() int i,j,k;for(i=0;i<D.cd_num;i+)/對(duì)

32、每個(gè)狀態(tài)循環(huán)for(j=0;j<D.si.link_num;j+)/S，對(duì)每個(gè)狀態(tài)的每個(gè)連接循環(huán)，如果找到當(dāng)前狀態(tài)用終結(jié)符建立的連接，則ACTION當(dāng)前狀態(tài)號(hào) 對(duì)應(yīng)終結(jié)符編號(hào) = 連接另一端狀態(tài)號(hào)if(D.si.uj.f<100)ACTIONiD.si.uj.f=D.si.uj.l;for(j=0;j<D.si.item_num;j+)/r，對(duì)每個(gè)狀態(tài)的每個(gè)項(xiàng)目循環(huán)， 如果找到一個(gè)終結(jié)項(xiàng)目，例如A->c.則 ACTION當(dāng)前狀態(tài) 所有 vt和 $= 產(chǎn)生式文案大全標(biāo)準(zhǔn)實(shí)用A->c 的編號(hào)if(oldzD.si.wj.fD.si.wj.l='/0')

33、for(k=0;k<=vtnum;k+)ACTIONik=D.si.wj.f+100;for(j=0;j<D.si.item_num;j+)/acc，對(duì)每個(gè)狀態(tài)的每個(gè)項(xiàng)目循環(huán)， 如果找到 P->S. 所在狀態(tài)，則ACTION當(dāng)前狀態(tài) $=300 ，即 accif(D.si.wj.f=0&&D.si.wj.l=2)ACTIONivtnum=300; break;/ 構(gòu)造 GOTO表void go_answer() int i,j;for(i=0;i<D.cd_num;i+)for(j=0;j<D.si.link_num;j+)/對(duì)每個(gè)狀態(tài)的每個(gè)連接循

34、環(huán)， 如果找到當(dāng)前狀態(tài)用非終結(jié)符建立的連接， 則 GOTO當(dāng)前狀態(tài)號(hào) 對(duì)應(yīng)非終結(jié)符編號(hào) = 連接另一端狀態(tài)號(hào)if(D.si.uj.f>=100)GOTOiD.si.uj.f-100=D.si.uj.l;/ 總控程序int control()int i,j,num;char cY='/0'/ 初始化帶分析字符串的存儲(chǔ)空間 SqE stackN;文案大全標(biāo)準(zhǔn)實(shí)用int p1=0,p2=0;/p1是待 分析 字符串 指 針 ,p2是 棧頂 下一位 元素的指針 ,stack0 是棧底vtnum+;/把'$' 加入終結(jié)符集for(i=0;i<N;i+)stac

35、ki.c1='/0'/初始化符號(hào)棧stackp2.t=0;stackp2.c1='$'/把(0,$) 壓棧p2+;/指針更新printf("/n請(qǐng)輸入要分析的字符串 ( 以$結(jié)尾 ):");cin>>c;printf("/n棧中狀態(tài)棧中符號(hào)輸入串分析動(dòng)作 /n");while(ACTIONstackp2-1.ttest(cp1)!=300)/ACTION棧 頂 狀 態(tài)號(hào) 當(dāng)前字符編號(hào) for(i=0,j=0;stacki.c1!='/0'i+)printf("%d",stac

36、ki.t);j+;for(i=0;i<14-j;i+)printf(" ");/輸出棧中狀態(tài)for(i=0,j=0;stacki.c1!='/0'i+)printf("%c",stacki.c1);j+;for(i=0;i<14-j;i+)printf(" ");/輸出棧中符號(hào)for(i=p1,j=0;ci!='/0'i+)printf("%c",ci);j+;for(i=0;i<14-j;i+)printf(" ");/ 輸出剩余字符串 if(

37、ACTIONstackp2-1.ttest(cp1)>0&&ACTIONstackp2-1.ttest(cp1)<100)/Sprintf("S%d/n",ACTIONstackp2-1.ttest(cp1);/輸出 分析動(dòng)作stackp2.t=ACTIONstackp2-1.ttest(cp1);/將狀態(tài)壓棧stackp2.c1=cp1;/將當(dāng)前字符壓棧p2+;p1+;/更新兩個(gè)指針文案大全標(biāo)準(zhǔn)實(shí)用elseif(ACTIONstackp2-1.ttest(cp1)>100&&ACTIONstackp2-1.ttest(cp

38、1)<200)/r,歸約num=ACTIONstackp2-1.ttest(cp1)-100;/num是歸約所用的產(chǎn)生式編號(hào)printf("r%d/n",num);p2=p2-length(num);/彈出 length(num) 個(gè)元素stackp2.t=GOTOstackp2-1.ttest(oldznum0)-100;/若 T 是彈出后的棧頂元素中的狀態(tài)號(hào)，把GOTOToldznum0壓棧，注意 -100stackp2.c1=oldznum0;/把 oldznum0壓棧p2+;stackp2.c1='/0'/封頂elseif(ACTIONstackp2-1.ttest(cp1)=0)/Errorprintf("Error/n/nError,您輸入的句型和文法不符!/n");return ERROR;printf("01$%c$acc/n",oldz10);printf("/nSucceed,您輸入句型和文法匹配 !/n");return OK;/ 返回增