編譯原理算符優(yōu)先分析法研究源程序

1、編譯原理算符優(yōu)先分析法研究源程序目 錄1 課程設(shè)計(jì)的目的和要求21.1 課程設(shè)計(jì)的目的21.2 課程設(shè)計(jì)的要求22 系統(tǒng)描述22.1 自底向上分析方法的描述:22.2 算符優(yōu)先文法的描述：23）輸入符號(hào)串，進(jìn)行移進(jìn)-規(guī)約分析。33 概要設(shè)計(jì)33.1 設(shè)計(jì)思路33.2 系統(tǒng)功能結(jié)構(gòu)43.3 技術(shù)路線或?qū)崿F(xiàn)方法53.4 開發(fā)環(huán)境54 詳細(xì)設(shè)計(jì)54.1 模塊劃分54.2主要算法的流程圖74.3 數(shù)據(jù)分析與定義84.4 系統(tǒng)界面設(shè)計(jì)85 測(cè)試方法和測(cè)試結(jié)果95.1 測(cè)試用例195.2 測(cè)試用例2105.3測(cè)試用例3115.4 測(cè)試用例4126 結(jié)論和展望13結(jié)論13展望13學(xué)習(xí)編譯技術(shù)課程的體會(huì)和對(duì)本

2、門課程的評(píng)價(jià)137 參考文獻(xiàn)138 源代碼141 課程設(shè)計(jì)的目的和要求1.1 課程設(shè)計(jì)的目的本次設(shè)計(jì)的時(shí)間為1周，目的是通過使用高級(jí)語言實(shí)現(xiàn)部分算法加強(qiáng)對(duì)編譯技術(shù)和理論的理解。設(shè)計(jì)的題目要求具有一定的規(guī)模，應(yīng)涵蓋本課程內(nèi)容和實(shí)際應(yīng)用相關(guān)的主要技術(shù)。1.2 課程設(shè)計(jì)的要求1、文法使用產(chǎn)生式來定義；2、用大寫字母和小寫字母分別表示非終結(jié)符和終結(jié)符；產(chǎn)生式使用->；3、文法中的空字符串統(tǒng)一使用表示；4、分別給出每一個(gè)非終結(jié)符的FIRSTVT集和LASTVT集；5、畫出算符優(yōu)先關(guān)系表6、判定給定的文法是否是算符優(yōu)先文法；7、給定符號(hào)串判定是否是文法中的句子，分析過程用分析表格的方式打印出來。2

3、系統(tǒng)描述本次實(shí)驗(yàn)使用windows vista操作系統(tǒng)下visual C+6.0平臺(tái)，使用C語言，利用讀文件方式將待分析的文法讀入到程序中，通過定義數(shù)組和結(jié)構(gòu)體作為具有一定意義或關(guān)系的表或棧，存放FIRSTVT、LASTVT、算符優(yōu)先關(guān)系表的元素。系統(tǒng)能夠?qū)τ晌募x入的文法進(jìn)行分析，構(gòu)造出FIRSTVT表和LASTVT表以及算符優(yōu)先關(guān)系表。可以根據(jù)構(gòu)造的優(yōu)先關(guān)系表對(duì)輸入的任意符號(hào)串進(jìn)行分析，判斷是否為本文法的句子，若是則打印規(guī)約過程。結(jié)果顯示到DOS界面上。2.1 自底向上分析方法的描述:對(duì)輸入的符號(hào)串自左向右進(jìn)行掃描，并將輸入符逐個(gè)移入棧中，邊移入邊分析，一旦棧頂符號(hào)串形成某個(gè)句型的句柄時(shí)（

4、該句柄對(duì)應(yīng)某個(gè)產(chǎn)生式的右部），就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號(hào)串，這一過程稱為規(guī)約。重復(fù)這一過程，直到棧中只剩下文法的開始符則分析成功。2.2 算符優(yōu)先文法的描述：只規(guī)定算符之間的優(yōu)先關(guān)系，也就是說只考慮終結(jié)符之間的優(yōu)先關(guān)系。由于算富有先分析不考慮非終結(jié)符之間的優(yōu)先關(guān)系，在規(guī)約過程中只要找到最左素短語就可以規(guī)約。如給定一個(gè)文法GS：S->#E#E->E+TE->TT->T*FT->FF->P/FF->PP->(E)P->i利用算符優(yōu)先文法分析過程處理如下：1）計(jì)算給定文法中任意兩個(gè)終結(jié)符對(duì)(a,b)之間的優(yōu)先關(guān)系，首先計(jì)算兩

5、個(gè)集合FIRSTVT(B)=b|B->b或B->CbLASTVT(B)=a|B->a或B->aC表2-1FIRSTVT集和LASTVT集 SETFPFIRSTVT#+*/i(*/i(/i(i(LASTVT#+*/i)*/i)/i)i)2）計(jì)算三種優(yōu)先關(guān)系，求出算符優(yōu)先關(guān)系表：表2-2算符優(yōu)先關(guān)系表+*/i()#+*/I()#3）輸入符號(hào)串，進(jìn)行移進(jìn)-規(guī)約分析。3 概要設(shè)計(jì)3.1 設(shè)計(jì)思路1）首先在源程序相同的目錄下創(chuàng)建一個(gè)txt文檔，并在文檔中輸入待分析的文法。然后定義一個(gè)輸入流文件，調(diào)用這個(gè)流文件中的open函數(shù)打開該txt文件，再定義一個(gè)二維數(shù)組通過循環(huán)接收讀入的產(chǎn)

6、生式。2）接著開始構(gòu)造FIRSTVT、LASTVT、算符優(yōu)先關(guān)系表。在構(gòu)造表的時(shí)候首先定義了兩個(gè)重要的結(jié)構(gòu)體。一個(gè)結(jié)構(gòu)體作為存放具有一定關(guān)系的一對(duì)非終結(jié)符和終結(jié)符，另一個(gè)結(jié)構(gòu)體作為存放上述元素的棧，包括棧頂指針、棧底指針、棧的長(zhǎng)度。既然定義了棧，就存在對(duì)棧的初始化、棧是否為空的判斷、入棧、出棧操作，利用循環(huán)和指針的操作來定義這些函數(shù)，以完成元素的進(jìn)棧和彈出。定義了這兩個(gè)結(jié)構(gòu)體，就可以用來構(gòu)造FIRSTVT、LASTVT、算符優(yōu)先關(guān)系表。在構(gòu)造FIRSTVT表時(shí)，通過循環(huán)找出每條產(chǎn)生式中的非終結(jié)符的FIRSTVT集，并把該非終結(jié)符和終結(jié)符壓棧，設(shè)置標(biāo)志位，標(biāo)志一對(duì)非終結(jié)符和終結(jié)符具有對(duì)應(yīng)關(guān)系。L

7、ASTVT表的構(gòu)造則是將求FIRSTVT的過程翻轉(zhuǎn)過來，可以僅僅將函數(shù)中的參數(shù)稍作修改就能夠完成。3）構(gòu)造算符優(yōu)先關(guān)系表。算符優(yōu)先關(guān)系表是一個(gè)二維數(shù)組，用來存放任意兩個(gè)終結(jié)符之間的優(yōu)先關(guān)系。首先構(gòu)造表頭，通過掃描所有產(chǎn)生式將終結(jié)符不重復(fù)的存放在一個(gè)一維數(shù)組中并置為優(yōu)先關(guān)系表的行和列，并將優(yōu)先關(guān)系表其他內(nèi)容全部初始化為空。接著遍歷所有產(chǎn)生式，找出任意兩個(gè)終結(jié)符之間存在的關(guān)系（可以沒有關(guān)系），并判斷任意兩終結(jié)符是否至多存在一種優(yōu)先關(guān)系，如發(fā)現(xiàn)優(yōu)先關(guān)系表不為空，則證明該文法不是算符優(yōu)先文法，否則，將相應(yīng)的關(guān)系填入到相應(yīng)的行列對(duì)應(yīng)的單元中。4）輸入串分析過程的設(shè)計(jì)。首先將大于、小于、等于和無關(guān)系分別定

8、義成一種類型的數(shù)據(jù)表示，通過查詢符號(hào)棧棧頂以及當(dāng)前符號(hào)之間的優(yōu)先關(guān)系來判斷移進(jìn)和規(guī)約的操作。3.2 系統(tǒng)功能結(jié)構(gòu)圖3-1 系統(tǒng)功能結(jié)構(gòu)圖函數(shù)功能：Main()函數(shù)：調(diào)用主函數(shù)，運(yùn)行程序；FirstVt()函數(shù)：構(gòu)造FIRSTVT表；LastVt()函數(shù)：構(gòu)造LASTVT表；OpPrioTable()函數(shù)：構(gòu)造算符優(yōu)先關(guān)系表；InputAnalyse()函數(shù)：分析輸入串是否為文法中的句子，并給出規(guī)約過程。3.3 技術(shù)路線或?qū)崿F(xiàn)方法算符優(yōu)先分析法的具體過程如下：1、首先先輸入文件的路徑，在readfile(char sencol)函數(shù)中，將需要分析的文法通過輸入流文件打開函數(shù)open()復(fù)制到se

9、nrowcol中。2、然后利用FirstVt( )構(gòu)造產(chǎn)生式senrowcol的FirstVt表。先找出形如A->a（a為第一個(gè)終結(jié)符）的產(chǎn)生式，把（A,a）壓入Operator棧中。從Operator棧頂拋出項(xiàng)（A，a），填入first表相應(yīng)位置。在找出形如B->A的產(chǎn)生式，把（B,a）壓入Operator棧中。循環(huán)直到Operator棧為空，此時(shí)FirstVt表構(gòu)造完畢。3、然后把產(chǎn)生式右部翻轉(zhuǎn)，調(diào)用FirstVt函數(shù)求出LastVt表。4、接著調(diào)用OpPriotable（）構(gòu)造算符優(yōu)先關(guān)系表opTable。先把產(chǎn)生式中所有終結(jié)符填入opTable表第一行和第一列，然后利用產(chǎn)生

10、式和FirstVt表LastVt表分別找出滿足=關(guān)系、<關(guān)系、>關(guān)系的算符填表。若相應(yīng)位已有關(guān)系，說明兩個(gè)終結(jié)符之間至少有兩種優(yōu)先關(guān)系，該文法不是算符優(yōu)先文法。5、最后調(diào)用InputAnalyse（）對(duì)輸入串進(jìn)行分析。初始化分析棧S，依次判斷當(dāng)前輸入符a和分析棧中離棧頂最近的終結(jié)符S j 的關(guān)系，若S j < a ，則a移近，若S j < a ，則往前找到第一個(gè)S j >a，將S j -1到棧頂S k 規(guī)約，若S j = a ，如果S j =#，則接受，如果S j ！=#，則移進(jìn)。直到接受或者出錯(cuò)，算符優(yōu)先分析結(jié)束。3.4 開發(fā)環(huán)境實(shí)驗(yàn)使用windows vist

11、a操作系統(tǒng)下的Microsoft Visual C+ 6.0平臺(tái)，用C語言完成。4 詳細(xì)設(shè)計(jì)4.1 模塊劃分實(shí)驗(yàn)分為五個(gè)模塊，分別是：1、文件的導(dǎo)入：readfile（sen）；2、FirstVt、LastVt集的構(gòu)造：FirstVt（sen,first,sen_len,frist_len）；LastVt（sen,last，sen_len,frist_len）；3、 算符優(yōu)先關(guān)系表OpPriotable的構(gòu)造：OpPriotable（sen,first,last,opTable,sen_len,first_len,&opTable_len）；4、算符優(yōu)先分析過程的實(shí)現(xiàn)：InputAna

12、lyse（opTablecol,stringcol,opTable_len）；5、主函數(shù)：main（）。4.2 主要算法的流程圖圖4-1 算符優(yōu)先分析法程序流程圖4.3 數(shù)據(jù)分析與定義1、文法（產(chǎn)生式）：文法使用產(chǎn)生式來定義char senrowcol：用二維數(shù)組表示產(chǎn)生式；int sen_len：產(chǎn)生式的個(gè)數(shù)；2、FIRSTVT集：char firstrowcol：用二維數(shù)組構(gòu)造FIRSTVT表int frist_len：FIRSTVT表的行數(shù)；3、LASTVT集：char lastrowcol：用二維數(shù)組構(gòu)造LASTVT表；int frist_len：LASTVT表的行數(shù)；4、算符優(yōu)先關(guān)系

13、表：char opTablerowcol：用二維數(shù)組表示算符優(yōu)先關(guān)系表；int opTable_len：算符優(yōu)先關(guān)系表的行數(shù)和列數(shù)；5、算符優(yōu)先分析表char stringcol：用一維數(shù)組記錄輸入串；char SSIZE：用一維數(shù)組表示分析棧 ；char a：當(dāng)前輸入字符；6、其他數(shù)據(jù)結(jié)構(gòu)：typedef structchar nonterm; /非終結(jié)符char term; /終結(jié)符StackElement;FIRSTVT表或LASTVT表中一個(gè)表項(xiàng)（A,a）；7、typedef struct StackElement *top;StackElement *bottom;int stack

14、size;stack;以形如表項(xiàng)（A,a）為元素的棧，在構(gòu)造FirstVt集的過程中用到；4.4 系統(tǒng)界面設(shè)計(jì)本實(shí)驗(yàn)沒有考慮界面設(shè)計(jì)，將結(jié)果直接打印輸出在DOS界面下。5 測(cè)試方法和測(cè)試結(jié)果5.1 測(cè)試用例1測(cè)試目的：使用算符優(yōu)先分析法對(duì)一個(gè)算符文法中的句子進(jìn)行分析。讀入一個(gè)算符優(yōu)先文法進(jìn)行分析，給出文件路徑D:coursesC_source_file成品算符優(yōu)先文法1.txt。結(jié)果如下：圖5-1 測(cè)試用例1運(yùn)行截圖1輸入一個(gè)字符串，使得該字符串是該文法的一個(gè)句子。則輸入字符串i+i*i/(i+i)#時(shí)運(yùn)行結(jié)果為：圖5-2 測(cè)試用例1運(yùn)行截圖25.2 測(cè)試用例2測(cè)試目的：使用算符優(yōu)先分析法，分

15、析一個(gè)字符串不是該文法的句子，并輸出出錯(cuò)信息。輸入一個(gè)字符串，使得該字符串不是文法的句子。圖5-3 測(cè)試用例2運(yùn)行截圖5.3 測(cè)試用例3測(cè)試目的：讀入一個(gè)文法，判斷該文法不是算符優(yōu)先文法。讀入一個(gè)非算符優(yōu)先文法進(jìn)行分析，給出文件路徑：D:coursesC_source_file成品非算符優(yōu)先文法1.txt。運(yùn)行結(jié)果如下：圖5-4 測(cè)試用例3運(yùn)行截圖5.4 測(cè)試用例4測(cè)試目的：輸入一個(gè)非算符文法，判斷該文法不是算符文法。讀入一個(gè)非算符文法，給出路徑：D:coursesC_source_file成品非算符文法.txt。運(yùn)行結(jié)果如下：圖5-5 測(cè)試用例4運(yùn)行截圖6 結(jié)論和展望結(jié)論本次實(shí)驗(yàn)我們基本完成

16、了實(shí)驗(yàn)題目的要求。求出了一個(gè)文法中每一個(gè)非終結(jié)符的FIRSTVT集和LASTVT集，畫出算符優(yōu)先關(guān)系表，并判定出給定的文法是否是算符優(yōu)先文法。當(dāng)給定一個(gè)符號(hào)串時(shí)，能夠判定是否是文法中的句子，并能夠?qū)⒎治鲞^程打印出來。通過算符優(yōu)先分析方法，可以對(duì)任意一個(gè)文法進(jìn)行自底向上的分析。同時(shí)，算符優(yōu)先分析法也存在不足之處，由于忽略文法中的非終結(jié)符，會(huì)將本不屬于文法的句子正確規(guī)約，從而引起錯(cuò)誤。展望本次實(shí)驗(yàn)完成了題目的要求，準(zhǔn)確把握了將文法通過讀文件形式、手動(dòng)輸入分析字符串的題目要求，并在滿足要求的基礎(chǔ)上進(jìn)行了創(chuàng)新，添加了對(duì)算符文法的判斷功能。實(shí)驗(yàn)中，小組成員的分工與合作充分體現(xiàn)了軟件工程的思想。需求分析理

17、解準(zhǔn)確，小組成員任務(wù)明確，統(tǒng)一函數(shù)頭、參數(shù)，各自完成分內(nèi)工作，整合工作快速、高效。同時(shí)，實(shí)驗(yàn)中還存在很多不足。調(diào)試程序中的錯(cuò)誤占用了大部分時(shí)間，以至于沒有考慮使用界面展示結(jié)果。雖然使用C+開發(fā)工具，但實(shí)質(zhì)上還是在使用C編代碼。在今后的實(shí)踐中還需注意。學(xué)習(xí)編譯技術(shù)課程的體會(huì)和對(duì)本門課程的評(píng)價(jià)在上編譯課的時(shí)候，小組成員都覺得自己對(duì)算符優(yōu)先文法已經(jīng)掌握了，但等真正用程序去實(shí)現(xiàn)時(shí)，才發(fā)現(xiàn)有很多細(xì)節(jié)我當(dāng)時(shí)沒有注意到。也正以為沒有注意到這些細(xì)節(jié)，導(dǎo)致成員們編程時(shí)會(huì)出現(xiàn)各種錯(cuò)誤，大部分都是在循環(huán)時(shí)下標(biāo)或者循環(huán)次數(shù)的控制上出錯(cuò)。在進(jìn)行到一定階段后發(fā)現(xiàn)犯的低級(jí)錯(cuò)誤越來越少了，對(duì)算符優(yōu)先文法也愈發(fā)的吃透了，編程水

18、平也有了進(jìn)一步的提高。編譯原理如果要深入研究，那會(huì)是一門非常深?yuàn)W的學(xué)問，對(duì)于現(xiàn)階段只有60多學(xué)時(shí)的本科生來說，只能涉及到它一些最基本的原理，和最宏觀的方法，要想微觀的去研究，還需要在以后的時(shí)間里去鉆研。在這次實(shí)驗(yàn)中，小組成員也只是用高級(jí)語言模擬了編譯的一個(gè)小方法，在完成實(shí)驗(yàn)的過程中，小組成員對(duì)編譯原理有了進(jìn)一步的了解，更提高了動(dòng)手編程能力，是一次經(jīng)驗(yàn)和知識(shí)的積累。7 參考文獻(xiàn) 1 張素琴編譯原理（第2版）M. 北京：清華大學(xué)出版社，2005.6，102-121.2 陳維興C+面向?qū)ο蟪绦蛟O(shè)計(jì)教程M. 北京：清華大學(xué)出版社，2004.8，258-272.8 源代碼#include<iost

19、ream.h>#include<stdlib.h>#include <fstream.h>#define row 50#define col 50#define SIZE 50/兩個(gè)重要結(jié)構(gòu)體的定義/FIRSTVT表或LASTVT表中一個(gè)表項(xiàng)（A,a）結(jié)構(gòu)體的初始化typedef structchar nonterm; /非終結(jié)符char term; /終結(jié)符StackElement;/存放（A,a）的棧的初始化typedef struct StackElement *top;StackElement *bottom;int stacksize;stack;/初始

20、化（A,a）棧void InitStack(stack &S) S.bottom = new StackElementSIZE; if(!S.bottom) cout<<"存儲(chǔ)空間分配失?。?quot;<<endl; S.top = S.bottom; S.stacksize = SIZE;/判斷（A,a）棧是否為空bool ifEmpty(stack S)if(S.top=S.bottom) return true; /如果棧為空，則返回trueelse return false; /否則不為空，返回false/插入棧頂（A,a）元素void Ins

21、ert(stack &S,StackElement e)if(S.top-S.bottom>=S.stacksize)cout<<"棧已滿，無法插入！"<<endl;elseS.top->nonterm=e.nonterm;S.top->term=e.term;S.top+;/彈出棧頂（A,a）元素StackElement Pop(stack &S)StackElement e;e.nonterm = '0'e.term = '0'if(S.top=S.bottom)cout<&

22、lt;"棧為空，無法進(jìn)行刪除操作！"<<endl; return e;elseS.top-; e.nonterm=S.top->nonterm;e.term=S.top->term;return e;/終結(jié)符與非終結(jié)符的判斷函數(shù)（布爾類型）bool TerminalJud(char c)if(c>='A'&&c<='Z')return false; /非終結(jié)符返回falseelse return true; /終結(jié)符返回true/判斷非終結(jié)符在first表中是否已存在bool ItemJud

23、(char firstcol,int frist_len,char C)for(int i=0;i<frist_len;i+)if(firsti0=C) return true; /如果first表中已存在此非終結(jié)符，則返回true return false;/讀文件函數(shù)int readfile(char sencol)char addr50;cout<<"請(qǐng)輸入要讀文件的地址（用表示）："<<endl;cin>>addr;ifstream fin;fin.open(addr,ios:in);if(!fin)cout<<

24、"Cannot open file!n"<<endl;for(int i=0;!fin.eof();i+)fin>>seni;cout<<seni<<endl;return i;/FIRSTVT表和LASTVT表中表項(xiàng)（非終結(jié)符）的初始化void ItemInit(char sencol,char firstcol,char lastcol,int sen_len,int &frist_len)int i;frist_len=1;first00=sen00;last00=sen00;for(i=1;i<sen_l

25、en;i+)if(TerminalJud(seni0)=false && ItemJud(first,frist_len,seni0)=false) /k是當(dāng)前first和last表的長(zhǎng)度firstfrist_len0=seni0;lastfrist_len0=seni0;frist_len+;void FirstVt(char sencol,char firstcol,int sen_len,int frist_len) / frist_len 是 first 表的行數(shù) sen_len是產(chǎn)生式的個(gè)數(shù)StackElement DFS,recordSIZE;stack Opera

26、tor; /創(chuàng)建存放（A，a）的棧InitStack(Operator); int i,j,r=0;for(i=0;i<sen_len;i+) /第一次掃描，將能直接得出的first（A，a）放進(jìn)棧中for(j=3;senij!='0'j+)if(TerminalJud(senij)=true) /遇到的第一個(gè)終結(jié)符壓入int exist=0;DFS.nonterm=seni0;DFS.term=senij;for(int i1=0;i<r;i+)if(recordi1.nonterm=seni0&&recordi1.term=senij)exist

27、=1;break;recordr.nonterm=seni0;recordr.term=senij;if(exist=0)Insert(Operator,DFS);/A-aB A-aC (A,a)壓棧兩次?recordr.nonterm=seni0;recordr.term=senij;r+;break;int locationcol; /輔助數(shù)組，用來記錄first表中放入終結(jié)符的位置for(i=0;i<frist_len;i+) locationi=1;while(!ifEmpty(Operator)int exist=0; /標(biāo)志位，記錄即將入棧的元素是否已經(jīng)存在StackElem

28、ent IDElement,DElement;DElement=Pop(Operator); /彈出棧頂元素for(i=0;i<frist_len;i+)if(firsti0=DElement.nonterm)int n=locationi;firstin=DElement.term; /將終結(jié)符填入相應(yīng)的first表中l(wèi)ocationi+;break;for(j=0;j<sen_len;j+) if(senj3=DElement.nonterm) /找出能推出當(dāng)前非終結(jié)符的產(chǎn)生式的左部 IDElement.nonterm=senj0;IDElement.term=DElement

29、.term;/判斷將要放進(jìn)棧里的元素曾經(jīng)是否出現(xiàn)過，若沒有，才壓入棧for(int r0=0;r0<r;r0+) /r記錄record數(shù)組中的元素個(gè)數(shù)if(recordr0.nonterm=IDElement.nonterm && recordr0.term=IDElement.term) exist=1;break; if(exist=0)Insert(Operator,IDElement);recordr.nonterm=IDElement.nonterm;recordr.term=IDElement.term;r+;/if/for/whilevoid LastVt(

30、char sencol,char lastcol,int sen_len,int frist_len) /firstvt表與lastvt表行數(shù)一樣 first_len表示last 表的行數(shù)int i,j,i1,j1;char c,recordrowcol='0'for(i=0;i<sen_len;i+) for(j=0;senij!='0'j+)recordij=senij;j=j-1; for(i1=3,j1=j;i1<j1;i1+,j1-) /做翻轉(zhuǎn)，就可以用求first的方法求lastc=recordii1;recordii1=recordij

31、1;recordij1=c;/forFirstVt(record,last,sen_len,frist_len);/判斷非終結(jié)符在term表中是否已存在bool TermTableJud(char termcol,int term_len,char C) for(int i=0;i<term_len;i+)if(termi=C) return true; /如果first表中已存在此非終結(jié)符，則返回1 return false;/構(gòu)造算符優(yōu)先關(guān)系表bool OpPriotable(char sencol,char firstcol,char lastcol,char opTablecol

32、,int sen_len,int first_len,int &opTable_len) int i,j,term_len=0;int i2,i3,opr,opc;char c1,c2,c3;char termSIZE='0'for(i=0;i<sen_len;i+) /一維數(shù)組term記錄關(guān)系表中存在的所有終結(jié)符for(j=3;senij!='0'j+)if(TerminalJud(senij)=true) if(TermTableJud(term,term_len,senij)=false) /term_len記錄term表的長(zhǎng)度 termte

33、rm_len=senij; term_len+; /得到終結(jié)符表 for(i=0;i<term_len+1;i+) /給優(yōu)先關(guān)系表賦初值，都等于空for(j=0;j<term_len+1;j+)opTableij=' 'for(i=1;i<term_len+1;i+) /設(shè)置優(yōu)先關(guān)系表的表頭opTablei0=termi-1; opTable0i=termi-1; for(i=0;i<sen_len;i+) /找等于關(guān)系for(j=5;senij!='0'j+)if(TerminalJud(senij-2)=true&&T

34、erminalJud(senij-1)=false&&TerminalJud(senij)=true)c1=senij-2; c2=senij; for(opr=1;opr<term_len+1;opr+) /在opTable表中找到該存入的行標(biāo)oprif(opTableopr0=c1)break;for(opc=1;opc<term_len+1;opc+) /在opTable表中找到該存入的列標(biāo)opcif(opTable0opc=c2)break;if(opTableopropc!=' ')cout<<"不是算符優(yōu)先文法！&q

35、uot;<<endl;return false;elseopTableopropc='='/if/for(j)for(j=4;senij!='0'j+)if(TerminalJud(senij-1)=true&&TerminalJud(senij)=true)c1=senij-1;c2=senij;for(opr=1;opr<term_len+1;opr+) /在opTable表中找到該存入的行標(biāo)oprif(opTableopr0=c1)break;for(opc=1;opc<term_len+1;opc+) /在opTa

36、ble表中找到該存入的列標(biāo)j2if(opTable0opc=c2)break;if(opTableopropc!=' ')cout<<"不是算符優(yōu)先文法！"<<endl;return false;elseopTableopropc='='/for(i)for(i=0;i<sen_len;i+) /找小于關(guān)系for(j=3;senij!='0'j+)if(TerminalJud(senij)=true&&TerminalJud(senij+1)=false)c1=senij; /c1

37、記錄終結(jié)符c2=senij+1; /c2記錄非終結(jié)符 for(opr=1;opr<term_len+1;opr+) /在opTable表中找到該存入的行標(biāo)oprif(opTableopr0=c1)break;for(opc=0;opc<first_len;opc+) /找出非終結(jié)符在first表中的列標(biāo)opcif(firstopc0=c2)break;for(i2=1;firstopci2!='0'i2+)c3=firstopci2;for(i3=1;i3<term_len+1;i3+)if(opTable0i3=c3)if(opTableopri3!=

38、9; ')cout<<"不是算符優(yōu)先文法！"<<endl;return false;elseopTableopri3='<'break;/if/for(j)/for(i)for(i=0;i<sen_len;i+) /找大于關(guān)系for(j=3;senij!='0'j+)if(TerminalJud(senij)=false&&senij+1!='0'&&TerminalJud(senij+1)=true)c1=senij; /c1記錄非終結(jié)符c2=sen

39、ij+1; /c2記錄終結(jié)符 for(opr=1;opr<term_len+1;opr+) /在opTable表中找到該存入的列標(biāo)j1if(opTable0opr=c2)break;for(opc=0;opc<first_len;opc+) /找出非終結(jié)符在last表中的行標(biāo)j2if(lastopc0=c1)break;for(i2=1;lastopci2!='0'i2+)c3=lastopci2;for(i3=1;i3<term_len+1;i3+)if(opTablei30=c3)if(opTablei3opr!=' ')cout<&

40、lt;"不是算符優(yōu)先文法！"<<endl;return false;elseopTablei3opr='>'break;/if/for(j)/for(i)opTable_len=term_len+1;return true;/判斷兩算符優(yōu)先關(guān)系并給出類型供構(gòu)造分析表int RelationshipJud(char c1,char c2,char opTablecol,int opTable_len)int i,j;for(i=1;i<opTable_len;i+)if(opTablei0=c1)break;for(j=1;j<o

41、pTable_len;j+)if(opTable0j=c2)break;if(opTableij='<')return 1;else if(opTableij='=')return 2;else if(opTableij='>') return 3;else return 4;/判斷輸入串是不是優(yōu)先文法bool PrioGramJud(char sencol,int sen_len)int i,j;for(i=0;i<sen_len;i+)for(j=4;senij!='0'j+)if(TerminalJud(s

42、enij-1)=false&&TerminalJud(senij)=false)cout<<"輸入的不是算符文法!"<<endl;return false;return true;/開始分析輸入串void InputAnalyse(char opTablecol,char stringcol,int opTable_len) /opTable_len是opTable表的長(zhǎng)度char a,Q,SSIZE='0' /S是分析棧 char cho1,cho2;int i,j,relation;int k=0;Sk='

43、#'cho2='y'cout<<"tttt分析過程如下："<<endl;cout<<"-"<<endl;/cout<<" 棧t當(dāng)前字符t優(yōu)先關(guān)系t移進(jìn)或規(guī)約"<<endl;/cout<<"分析過程如下："<<endl;cout.width(10);cout<<"棧"cout.width(15);cout<<"當(dāng)前字符"cout.wid

44、th(20);cout<<"剩余符號(hào)串"cout.width(15);cout<<"優(yōu)先關(guān)系"cout.width(15);cout<<"移進(jìn)或規(guī)約"<<endl;char* p;p=string;p+;for(i=0;stringi!='0'&&cho2='y'i+,p+)a=stringi; /讀入當(dāng)前字符cho1='n' /可否接受while(cho1='n') if(TerminalJud(Sk)=t

45、rue)j=k; /規(guī)約使棧內(nèi)有非終結(jié)符 else j=k-1; relation=RelationshipJud(Sj,a,opTable,opTable_len); if(relation=3) /Sj>a/cout<<" "<<S<<"t"<<" "<<a<<"tt >tt"cout.setf(ios:left);cout.width(10);cout<<S;cout.unsetf(ios:left);cout.w

46、idth(15);cout<<a;cout.width(20);cout<<p;cout.width(15);cout<<">"do Q=Sj; if(TerminalJud(Sj-1)=true) j=j-1; else j=j-2;while(RelationshipJud(Sj,Q,opTable,opTable_len)!=1);/cout<<" "<<Sj<<"歸約"<<endl;cout.width(11);cout<<S

47、j;cout.width(4);cout<<"歸約"<<endl;k=j+1; Sk='N'for(int l=k+1;l<SIZE;l+)Sl='0' else if(relation=1) /Sj<a cho1='y' /cout<<" "<<S<<"t"<<" "<<a<<"tt <tt 移進(jìn)"<<endl; cout.setf(ios:left);cout.width(10); cout<<S;cout.unsetf(ios:left);cout.width(15);cout<<a;cout.width(20);cout<<p;cout.width(