精品資料（2021-2022年收藏的）編譯原理課程設(shè)計(jì)

1、編譯原理課程設(shè)計(jì) 自頂向下語法分析器學(xué) 院（系）： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 學(xué) 生 姓 名： xxxxxxxxx 學(xué) 號(hào)： xxxxxxxxx 班 級(jí)： 電計(jì)1102 大連理工大學(xué) Dalian University of Technology 目 錄1 系統(tǒng)概論12 需求分析23 系統(tǒng)設(shè)計(jì)24 系統(tǒng)實(shí)現(xiàn)45 使用說明45.1 程序運(yùn)行平臺(tái)45.2 程序中所有定義的函數(shù)55.3 文檔說明65.4 調(diào)試分析76 課程設(shè)計(jì)總結(jié)12參考文獻(xiàn)12附錄：重要代碼13I 編譯原理課程設(shè)計(jì)1 系統(tǒng)概論語法分析是編譯過程的核心部分。它的任務(wù)是在詞法分析識(shí)別出單詞符號(hào)串的基礎(chǔ)上，分析并判定程序的語法結(jié)構(gòu)是否符合語

2、法規(guī)則。語法分析器在編譯程序中的地位如圖1所示：圖1 語法分析器在編譯程序中的地位語言的語法結(jié)構(gòu)是用上下文無關(guān)文法描述的。因此，語法分析器的工作本質(zhì)上就是按文法的產(chǎn)生式，識(shí)別輸入符號(hào)串是否為一個(gè)句子。這里所說的輸入串是指由單詞符號(hào)（文法的終結(jié)符）組成的有限序列。對(duì)一個(gè)文法，當(dāng)給你一串（終結(jié)）符號(hào)時(shí)，怎樣知道它是不是該文法的一個(gè)句子呢？這就要判斷，看是否能從文法的開始符號(hào)出發(fā)推導(dǎo)出這個(gè)輸入串。或者，從概念上講，就是要建立一棵與輸入串相匹配的語法分析樹。自頂向下分析法就是語法分析辦法中的一類。顧名思義，自頂向下就是從文法的開始符號(hào)出發(fā)，向下推導(dǎo)，推出句子。這種方法是帶“回溯”的。自頂向下分析的主旨

3、是，對(duì)任何輸入串，試圖用一切可能的辦法，從文法開始符號(hào)（根結(jié)）出發(fā)，自上而下地為輸入串建立一棵語法樹。或者說，為輸入串尋找一個(gè)最左推導(dǎo)。這種分析過程本質(zhì)上是一種試探過程，是反復(fù)使用不同產(chǎn)生式謀求匹配輸入串的過程。實(shí)現(xiàn)這種自頂向下的帶回溯試探法的一個(gè)簡(jiǎn)單途徑是讓每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)遞歸子程序。每個(gè)這種子程序可作為一個(gè)布爾過程。一旦發(fā)現(xiàn)它的某個(gè)候選與輸入串相匹配，就用這個(gè)候選去擴(kuò)展語法樹，并返回“真”值；否則，保持原來的語法樹和IP值不變，并返回“假”值。2 需求分析以前，人們對(duì)語法的分析都建立在人工的基礎(chǔ)上，人工分析雖然能夠做到側(cè)類旁推，但終究人力有限，再精密的分析都會(huì)出現(xiàn)或多或少的錯(cuò)誤。為減少

4、因人為產(chǎn)生的錯(cuò)誤，并加快語法的分析，故設(shè)計(jì)了這個(gè)自頂向下的語法分析器。人們只要運(yùn)行程序，輸入幾個(gè)簡(jiǎn)單的命令或語法，就能求出人們所需要的各種結(jié)果。雖然程序設(shè)計(jì)有一定的局限性，但在這個(gè)局限中卻能如人們的要求對(duì)語法進(jìn)行分析，從而在一定程度上幫助人們更好的完成工作。3 系統(tǒng)設(shè)計(jì)自頂向下的分析算法通過在最左推導(dǎo)中描述出各個(gè)步驟來分析記號(hào)串輸入。之所以稱這樣的算法為自頂向下是由于分析樹隱含的編號(hào)是一個(gè)前序編號(hào)，而且其順序是由根到葉自頂向下的分析程序有兩類：回溯分析程序（backtracking parser）和預(yù)測(cè)分析程序（predictive parser）。預(yù)測(cè)分析程序試圖利用一個(gè)或多個(gè)先行記號(hào)來預(yù)測(cè)

5、出輸入串中的下一個(gè)構(gòu)造，而回溯分析程序則試著分析其他可能的輸入，當(dāng)一種可能失敗時(shí)就要求輸入中備份任意數(shù)量的字符。雖然回溯分析程序比預(yù)測(cè)分析程序強(qiáng)大許多，但它們都非常慢，一般都在指數(shù)的數(shù)量級(jí)上，所以對(duì)于實(shí)際的編譯器并不合適。遞歸下降程序分析和LL(1)分析一般地都要求計(jì)算先行集合，它們分別稱作First集合和Follow集合。由于無需顯式地構(gòu)造出這些集合就可以構(gòu)造出簡(jiǎn)單的自頂向下的分析程序。1、LL(1)文法LL(1)文法是一類可以進(jìn)行確定的自頂向下語法分析的文法。就是要求描述語言的文法是無左遞歸的和無回溯的。根據(jù)LL(1)文法的定義，對(duì)于同一非終結(jié)符A的任意兩個(gè)產(chǎn)生式A:=a和A:=b，都要滿

6、足：SELECT(A：=a )SELECT(A:=b)=Ø。這樣，當(dāng)前非終結(jié)符A面臨輸入符a時(shí)，如果aSELECT(A：=a)，則可以選擇產(chǎn)生式A:=a去準(zhǔn)確匹配。如本程序中舉例說明的a.txt的文法就是一個(gè)LL（1）文法： S:=aBc|bABA:=aAb|bB:=b|02、文法的左遞歸當(dāng)一個(gè)文法是左遞歸文法時(shí)，采用自頂向下分析法會(huì)使分析過程進(jìn)入無窮循環(huán)之中。所以采用自頂向下語法分析需要消除文法的左遞歸性。文法的左遞歸是指若文法中對(duì)任一非終結(jié)符A有推導(dǎo)AÞA，則稱該文法是左遞歸的。左遞歸又可以分為直接左遞歸和間接左遞歸。3、直接左遞歸若文法中的某一產(chǎn)生式形如AA，V*，則

7、稱該文法是直接左遞歸的。消除直接左遞歸的方法：設(shè)有產(chǎn)生式是關(guān)于非終結(jié)符A的直接左遞歸：AA| （,V*，且不以A開頭）對(duì)A引入一個(gè)新的非終結(jié)符A，把上式改寫為：A A AA| 4、間接左遞歸若文法中存在某一非終結(jié)符A，使得AÞA至少需要兩步推導(dǎo)，則稱該文法是間接左遞歸的。消除間接左遞歸的方法：【方法一】采用代入法把間接左遞歸變成直接左遞歸。 【方法二】直接改寫文法：設(shè)有文法G10S： SA| AS 因?yàn)镾ÞAÞS，所以S是一個(gè)間接遞歸的非終結(jié)符。為了消除這種間接左遞歸，將式代入式，即可得到與原文法等價(jià)的文法（可以證明）： SS| 式是直接左遞歸的，可以采用前面介紹

8、的消除直接左遞歸的方法，對(duì)文法進(jìn)行改寫后可得文法：SSSS|4 系統(tǒng)實(shí)現(xiàn) 系統(tǒng)流程圖5 使用說明5.1 程序運(yùn)行平臺(tái)Visual C+ 6.0Windows XP SP25.2 程序中所有定義的函數(shù)class Syntax_analysis public: char stotax3020; /存放文法規(guī)則 char soudocu1000; /用于存放打開的文件內(nèi)容 int sto_tax; /存放產(chǎn)生式總數(shù) char firstchars30; /某個(gè)串的first集(可能有重復(fù)) int first_num; /first集長(zhǎng)度 char followchars1000; /存放某個(gè)非終結(jié)

9、符的follow集(如果有(間接)右遞歸,可能有較大重復(fù)) int follow_num; /follow集長(zhǎng)度 int follownumkey; /用于判斷右遞歸或間接右遞歸 char followkey; char selectchars3030; /存放每條產(chǎn)生式的select集 char colec030; /存入所有能推導(dǎo)出0的非終結(jié)符 int colec0num; /能推導(dǎo)出0的非終結(jié)符個(gè)數(shù) char capital; /第一個(gè)未被使用的大寫字母 char preanatab13013020;/存放預(yù)測(cè)分析表,分別為非終結(jié)符(將字母轉(zhuǎn)化為數(shù)字)、終結(jié)符(將字母轉(zhuǎn)化為數(shù)字)、產(chǎn)生式

10、 char _stotax3020; /臨時(shí)的stotax備份 int _sto_tax; /臨時(shí)的_sto_tax備份 char startchar; /開始文法符號(hào) char keylr; char save1000; /保存結(jié)果到外存儲(chǔ)器 char lie20; int li; char hang20; int han; int ll_key; int input_key;Syntax_analysis()void openfile() /打開文件void getin() /對(duì)讀取出來的文件內(nèi)容,推導(dǎo)式分解并保存在stotax數(shù)組中void disp() /顯示方法推導(dǎo)式void get

11、_in() /輸入推導(dǎo)式,并保存stotax數(shù)組中void save_file(char p) /保存到外存儲(chǔ)器void Delpare() /消除左遞歸void findcapital() /查找未被使用的大寫字母,把第一個(gè)未被使用的大寫字母保存在capital中void First_Collection(char p) /求字符串p的first集,把結(jié)果保存在數(shù)組firstchars30中void Follow_Collection(char p) /求字符p的follow集,把結(jié)果保存在數(shù)組followchars中void Select_Collection() /求每條產(chǎn)生式的sele

12、ct集,存放在數(shù)組selectchars3030中void Estab_preanatab() /創(chuàng)建預(yù)測(cè)分析表void dispselect() /顯示選擇void base_()void disp_table() /打印預(yù)測(cè)分析表void Analyse_course() /分析過程void deduce0_colec() /將所有能推導(dǎo)出0的非終符放在數(shù)組colec030中void dispfirst() /顯示First集void dispfollow()5.3 文檔說明文檔文法句子a.txtLL(1)文法baabbb#、baaabbbb#.b.txt直接左遞歸abbbbb(可以任意多

13、少個(gè)b)c.txt間接左遞歸abbbbb(可以任意多少個(gè)b)d.txtLL(1)文法maebn#.5.4 調(diào)試分析程序運(yùn)行說明：適應(yīng)的文法類型：1、一切LL(1)文法2、含有直接左遞歸但可以轉(zhuǎn)化為L(zhǎng)L(1)文法的文法3、含有間接左遞歸但可以轉(zhuǎn)化為L(zhǎng)L(1)文法的文法說明：1、文法表達(dá)方式例如：S:=Aa|Bb，其中空串用數(shù)字0代替，每輸入一個(gè)表達(dá)式換行寫下一表達(dá)式2、文法輸入結(jié)束后，換行再按#結(jié)束3、需要輸入命令來執(zhí)行所需要的功能命令說明：Cmd命令功能open從外存儲(chǔ)器打開某文法input從鍵盤輸入文法lltab查看預(yù)測(cè)分析表select查看每條產(chǎn)生式的SELECT集first求所輸串的FI

14、RST集follow求所輸非終結(jié)符的FOLLOW集ll對(duì)某個(gè)輸入句子進(jìn)行分析exit退出程序程序運(yùn)行主界面：（1）open：打開文件打開附帶文檔a.txta.txt文檔中的文法為L(zhǎng)L(1)文法：S:=aBc|bABA:=aAb|bB:=b|0（2）input：輸入文法輸入文法過程中“”應(yīng)用“0”代替使用每輸入一條新文法需重新另起一行文法輸入結(jié)束后換行以“”結(jié)束輸入文法后若要保存文件，請(qǐng)按“y”鍵，并按提示輸入備份文件的路徑和名稱。若沒有輸入備份路徑，文法則保存在默認(rèn)路徑（程序所在文件夾）中；若不進(jìn)行保存，則鍵入除“y”鍵外的任意鍵退出當(dāng)前命令。打開a.bck.txt文檔，可以看到文法：（3）l

15、ltab：預(yù)測(cè)分析表打開文件a.txt，對(duì)文檔中語法進(jìn)行分析：（4）select：查看每條產(chǎn)生式的SELECT集打開文件a.txt，求文檔中語法的SELECT集（5）first：求所輸串的FIRST集打開文件a.txt，求文檔中語法的FIRST集若需要繼續(xù)求FIRST集，則按“y”鍵繼續(xù)；若想退出當(dāng)前命令，則鍵入除“y”鍵外的任意鍵退出當(dāng)前命令。（6）follow：求所輸非終結(jié)符的FOLLOW集打開文件a.txt，求文檔中語法的FOLLOW集若需要繼續(xù)求FOLLOW集，則按“y”鍵繼續(xù)；若想退出當(dāng)前命令，則鍵入除“y”鍵外的任意鍵退出當(dāng)前命令。（7）ll：對(duì)某個(gè)輸入句子進(jìn)行分析打開文件a.tx

16、t，輸入要分析的字符串進(jìn)行分析（8）exit：推出程序 輸入exit命令退出6 課程設(shè)計(jì)總結(jié)在三周的課程設(shè)計(jì)中，我設(shè)計(jì)了一個(gè)自頂向下的語法分析器。由于涉及大量的編譯原理知識(shí)，且編程過程復(fù)雜，代碼量大，完成的功能并不是很多，而且也不是很完善，設(shè)計(jì)過程難免出現(xiàn)或多或少的錯(cuò)誤。由于時(shí)間有限，無法對(duì)程序進(jìn)行很好的測(cè)試，只發(fā)現(xiàn)其中的一些小錯(cuò)誤并加以改進(jìn)和完善，對(duì)其他未發(fā)現(xiàn)的BUG，只能盡量避免其出現(xiàn)。倘若有足夠多的時(shí)間，我相信我可以做出需求分析中要求的功能，使其滿足人民的要求，減少人工操作，減少運(yùn)算時(shí)間，避免由于人工計(jì)算出現(xiàn)的錯(cuò)誤，最終加快人們對(duì)語法的分析，減少人們的工作量。雖然三周的課程設(shè)計(jì)時(shí)間短，但

17、卻使我受益匪淺，通過這次課程設(shè)計(jì)我把課本中的理論轉(zhuǎn)化成實(shí)際運(yùn)用，從中加深了理論認(rèn)識(shí)，為以后的后續(xù)學(xué)習(xí)奠定基礎(chǔ)；并且在編程過程的資料查找和程序編制中掌握了編程的一些基本思路和構(gòu)想，為以后的程序設(shè)計(jì)奠定了基礎(chǔ)。參考文獻(xiàn)1、陳火旺，劉春林. 程序設(shè)計(jì)語言 編譯原理(第3版）. 國(guó)防工業(yè)出版社. 2000年2、李建中，姜守旭. 編譯原理. 機(jī)械工業(yè)出版社. 2003年年12月.3、（美）阿佩爾，（美）金斯伯格. 現(xiàn)代編譯原理：C語言描述. 人民郵電出版社. 2005年09月.附錄：重要代碼#include"stdio.h"#include"string.h"#i

18、nclude"iostream.h"#include"ctype.h"#include"fstream.h"class Syntax_analysis public:char stotax3020; /存放文法規(guī)則char soudocu1000; /用于存放打開的文件內(nèi)容int sto_tax; /存放產(chǎn)生式總數(shù)char firstchars30; /某個(gè)串的first集(可能有重復(fù))int first_num; /first集長(zhǎng)度char followchars1000; /存放某個(gè)非終結(jié)符的follow集(如果有(間接)右遞歸,

19、可能有較大重復(fù))int follow_num; /follow集長(zhǎng)度int follownumkey; /用于判斷右遞歸或間接右遞歸char followkey;char selectchars3030; /存放每條產(chǎn)生式的select集char colec030; /存入所有能推導(dǎo)出0的非終結(jié)符int colec0num; /能推導(dǎo)出0的非終結(jié)符個(gè)數(shù)char capital; /第一個(gè)未被使用的大寫字母char preanatab13013020; /存放預(yù)測(cè)分析表,分別為非終結(jié)符(將字母轉(zhuǎn)化為數(shù)字)、終結(jié)符(將字母轉(zhuǎn)化為數(shù)字)、產(chǎn)生式 char _stotax3020; /臨時(shí)的stota

20、x備份 int _sto_tax; /臨時(shí)的_sto_tax備份char startchar; /開始文法符號(hào)char keylr;char save1000; /保存結(jié)果到外存儲(chǔ)器char lie20;int li;char hang20;int han;int ll_key;int input_key; Syntax_analysis()void openfile() /打開文件 input_key=0; int i=0; ifstream infile; char path255; cin>>path; infile.open(path); if (infile.is_ope

21、n() while (infile.good() soudocui+=(char)infile.get(); infile.close(); soudocui='#' else cout<<"Error opening file" void getin() /對(duì)讀取出來的文件內(nèi)容,推導(dǎo)式分解并保存在stotax數(shù)組中int cout=0;char c;char interim50;int i=0; sto_tax=0;again:c=soudocucout+;while(c!='#')if(c!='n')/把一行內(nèi)

22、容存放在interim數(shù)組里if(c!=' ') interimi+=c; c=soudocucout+;elseif(!isupper(interim0)|interim1!=':'|interim2!='=')/如果行首不是以大寫字母:=這種格式,則輸出錯(cuò)誤信息printf("The Syntax is wrong! please enter again:n"); i=0;goto again;else /字符數(shù)組加結(jié)束符interimi='0'int m=0;for(int j=0;j<strlen

23、(interim);j+)/把后選式進(jìn)行分解成一個(gè)個(gè)產(chǎn)生式 /如A:=a|b分解成A:=a,A:=b if(interimj!='|')stotaxsto_taxm+=interimj;continue;else stotaxsto_taxm='0'sto_tax+;stotaxsto_tax0=stotaxsto_tax-10;stotaxsto_tax1=stotaxsto_tax-11;stotaxsto_tax2=stotaxsto_tax-12;m=3;continue;stotaxsto_taxm='0'sto_tax+;i=0;c=

24、soudocucout+;startchar=stotax00;void disp() /顯示方法推導(dǎo)式for(int i=0;i<sto_tax;i+)cout<<stotaxi<<endl;void get_in() /輸入推導(dǎo)式,并保存stotax數(shù)組中char c;if(input_key=0) c=getchar();input_key=1;char interim50;int i=0; sto_tax=0;again:c=getchar();while(c!='#')if(c!='n')if(c!=' '

25、) interimi+=c; c=getchar();elseif(!isupper(interim0)|interim1!=':'|interim2!='=')printf("The Syntax is wrong! please enter again:n"); i=0;goto again;else interimi='0'int m=0;for(int j=0;j<strlen(interim);j+)if(interimj!='|')stotaxsto_taxm+=interimj;contin

26、ue;else stotaxsto_taxm='0'sto_tax+;stotaxsto_tax0=stotaxsto_tax-10;stotaxsto_tax1=stotaxsto_tax-11;stotaxsto_tax2=stotaxsto_tax-12;m=3;continue;stotaxsto_taxm='0'sto_tax+;i=0;c=getchar();startchar=stotax00;int sav=0;savesav='0'printf("save it? press 'y' to save o

27、r other to continuen");char command30;cin>>command;if(!strcmp(command,"y")for(int i=0;i<sto_tax;i+)strcat(save,stotaxi);sav=strlen(save);savesav='n'savesav+1='0'save_file(save);char g;g=getchar();void save_file(char p) /保存到外存儲(chǔ)器char filepath30; cout<<&quo

28、t;Please enter the path and file name"<<endl;cin>>filepath; ofstream ofs(filepath); ofs.write(p,strlen(p); ofs.close();void Delpare() /消除左遞歸ll_key=0;keylr=0;/復(fù)制推導(dǎo)式數(shù)組for(int i=0;i<sto_tax;i+) strcpy(_stotaxi,stotaxi);_sto_tax=sto_tax;int key;char p30;char key_c;for(i=0;i<_sto_t

29、ax;i+)/消除直接左遞歸key_c=_stotaxi0;if(_stotaxi0=_stotaxi3)/如果存在直接左遞歸,則消除/查找未被使用的大寫之母 findcapital(); for(int j=0;j<_sto_tax;j+)if(_stotaxj0=key_c)keylr=1;if(_stotaxj3=_stotaxj0)strcpy(&_stotaxj3,&_stotaxj4);_stotaxjstrlen(_stotaxj)=capital;_stotaxj0=capital; _stotaxjstrlen(_stotaxj)+1='0

30、9;_stotax_sto_tax0=capital;_stotax_sto_tax1=':'_stotax_sto_tax2='='_stotax_sto_tax3='0' _stotax_sto_tax4='0'_sto_tax+;else if(_stotaxj3!='0')int d;d=strlen(_stotaxj);_stotaxjd=capital; _stotaxjd+1='0'char keyc30;for(i=0;i<_sto_tax;i+)/消除間接左遞歸key=0;s

31、trcpy(keyc,_stotaxi);if(isupper(_stotaxi3)for(int j=0;j<=_sto_tax;j+) if(keyc0!=_stotaxj0)if(_stotaxj0=keyc3)if(key=0) strcpy(p,&_stotaxi4); strcpy(&_stotaxi3,&_stotaxj3); strcpy(&_stotaxistrlen(_stotaxi),p);key=1;else_stotax_sto_tax0=_stotaxi0;_stotax_sto_tax1=':'_stotax_

32、sto_tax2='=' strcpy(&_stotax_sto_tax3,&_stotaxj3); strcpy(&_stotax_sto_taxstrlen(_stotax_sto_tax),p);_sto_tax+; for(int n=0;n<_sto_tax;n+)key_c=_stotaxn0; if(_stotaxi0=_stotaxi3)keylr=1; findcapital(); for(int j=0;j<_sto_tax;j+)if(_stotaxj0=key_c)if(_stotaxj3=_stotaxj0)strc

33、py(&_stotaxj3,&_stotaxj4); _stotaxjstrlen(_stotaxj)=capital; _stotaxj0=capital; _stotaxjstrlen(_stotaxj)+1='0' _stotax_sto_tax0=capital; _stotax_sto_tax1=':' _stotax_sto_tax2='=' _stotax_sto_tax3='0' _stotax_sto_tax4='0' _sto_tax+; else if(_stotaxj3!=&

34、#39;0')int d; d=strlen(_stotaxj); _stotaxjd=capital; _stotaxjd+1='0'if(keylr=1)printf("該文法有直接或間接左遞歸,消除左遞歸后的文法為:n"); for(i=0;i<_sto_tax;i+) printf("%s",_stotaxi); printf("n"); for(i=0;i<_sto_tax;i+) strcpy(stotaxi,_stotaxi); sto_tax=_sto_tax;void findca

35、pital() /查找未被使用的大寫字母,把第一個(gè)未被使用的大寫字母保存在capital中int key;for(int i=65;i<=90;i+)key=0;for(int j=0;j<_sto_tax;j+)if(_stotaxj0=char(i) key=1;if(key=0)capital=char(i);break;void First_Collection(char p) /求字符串p的first集,把結(jié)果保存在數(shù)組firstchars30中if(islower(p0) firstcharsfirst_num+=p0;else if(isupper(p0)for(in

36、t i=0;i<sto_tax;i+)if(stotaxi0=p0)if(islower(stotaxi3) firstcharsfirst_num+=stotaxi3; for(i=0;i<strlen(p);i+)if(isupper(pi)char *q;for(int n=0;n<sto_tax;n+)if(pi=stotaxn0)q=&stotaxn3;First_Collection(q); int key=0; for(int j=0;j<colec0num;j+) if(colec0j=pi)key=1; break; if(key=0) bre

37、ak; else if(islower(pi) firstcharsfirst_num+=pi; break;void Follow_Collection(char p) /求字符p的follow集,把結(jié)果保存在數(shù)組followchars中if(p=stotax00) followcharsfollow_num+='#'for(int i=0;i<sto_tax;i+)for(int j=3;j<strlen(stotaxi);j+)if(p=stotaxij)if(islower(stotaxij+1)followcharsfollow_num+=stotaxij

38、+1; break;else if(stotaxij+1='0')if(follownumkey>=30) /如果follownumkey大于某個(gè)值,則可認(rèn)定求follow集陷入死循環(huán),即有右遞歸或間接右遞歸,此時(shí)跳出去,終止死循環(huán)follownumkey=0;break; follownumkey+;Follow_Collection(stotaxi0);break;else if(isupper(stotaxij+1)char *q;q=&stotaxij+1;first_num=0;First_Collection(q);for(int m=0;m<f

39、irst_num;m+) followcharsfollow_num+=firstcharsm;int key1=0;for(int n=j+1;n<strlen(stotaxi);n+)int key2=0;for(int r=0;r<colec0num;r+)if(stotaxin=colec0r) key2=1; if(key2=0)key1=1;break;if(key1=0)if(follownumkey>=30) /如果follownumkey大于某個(gè)值,則可認(rèn)定求follow集陷入死循環(huán),即有右遞歸或間接右遞歸,此時(shí)跳出去,終止死循環(huán) follownumkey=

40、0; break; follownumkey+;Follow_Collection(stotaxi0);break;void Select_Collection() /求每條產(chǎn)生式的select集,存放在數(shù)組selectchars3030中for(int i=0;i<sto_tax;i+)int select_num=0;int key1=0;int key2=0;for(int j=3;j<strlen(stotaxi);j+)for(int m=0;m<colec0num;m+)if(colec0m=stotaxij) key1=1; if(key1=0)key2=1;b

41、reak;if(stotaxi3='0') /產(chǎn)生式右邊為0,則把follow集加入select集中follownumkey=0;follow_num=0;Follow_Collection(stotaxi0);for(int r=0;r<follow_num;r+)int key5=0;for(int v=0;v<select_num;v+)if(followcharsr=selectcharsiv) key5=1;if(key5=0) selectcharsiselect_num+=followcharsr; selectcharsiselect_num=

42、9;0'break;if(key2=0) /表示產(chǎn)生式右邊能推出0,則把first集和follow集加入select集中first_num=0;First_Collection(&stotaxi3);for(int q=0;q<first_num;q+)int key3=0;for(int s=0;s<select_num;s+)if(firstcharsq=selectcharsis) key3=1;if(key3=0) selectcharsiselect_num+=firstcharsq;follownumkey=0;follow_num=0;Follow_C

43、ollection(stotaxi0);for(int p=0;p<follow_num;p+)int key4=0;for(int t=0;t<select_num;t+)if(followcharsp=selectcharsit) key4=1;if(key4=0)selectcharsiselect_num+=followcharsp; selectcharsiselect_num='0'else /表示產(chǎn)生式右邊不能推出0,則把first集加入select集中first_num=0;First_Collection(&stotaxi3);for(int q=0;q<first_num;q+)int key3=0;for(int s=0;s<select_num;s+)if(firstcharsq=selectcharsis) key3=1;if(key3=0) selectcharsiselect_num+=firstcharsq;selectcharsiselect_num='0'