計算機編譯原理---語法分析預測分析法

1、編譯原理實驗報告語法分析2預測分析法目錄 TOC o 1-5 h z 1.摘要：32、實驗目的：33、任務概述34、實驗依據(jù)的原理35、程序設計思想56、實驗結(jié)果分析9 HYPERLINK l bookmark14 o Current Document 7、總結(jié)18 HYPERLINK l bookmark16 o Current Document 8、程序代碼18所有非終結(jié)符的Follow集Follow集128=35129= 2, 3, 6, 13130= 26, 28131=3, 6,13132= 27, 28133=28134= 6,13135= 34, 6,13136= 6,13137

2、=28, 32138=13139= 2, 3, 6, 13140=13141=28,14142=28,14143=28,14144= 28,14145= 28,14146=28,14147= 29, 32148= 28,14149=32150= 26, 28,14151=14152=8,10153= 28, 14, 32, 27, 20,21, 22, 23,24, 25,8, 10154= 28,14, 32, 27, 20,21, 22, 23,24, 25,8,10155=16,17, 28,14, 32,27, 20, 21,22, 23,24, 25, 8,10156=16,17,

3、28,14, 32,27, 20, 21,22, 23,24, 25, 8,10157=18,19,16,17, 28,14, 32, 27, 20, 21, 22, 23, 24, 25, 8,10158=28159= 34, 33,31160-34, 33,31161=16,17, 34, 33,31所有產(chǎn)生式的First集Pro_First集= 11=12= 2, 3, 6,13 3X2= 0= 27 7=0= 3 = 010=34 11= 3412= 0 13=414=5 15=6 16=0 17=6 18=6 19=0 20二347 2= 923二11 24=12 25=136 二0

4、 27=34 28二30 29二31。二0 1=7 2= 9 33=11 34=275=06二 7=27 8二09二1340= 2841=042=16, 17, 34, 33,3143=1544二1645=1746=34, 33,3147=16, 1748=049二34, 33,3150=18,1951=052=3453= 3354 =3155=3156-057=1658=1759= 1860=1961=2062=2163=2264=2365=2466=25預測分析表一一 一- -一一 - 預測力m衣-一 -一-11234567891011121314151617181920212223242

5、5262728293031323334351280-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-21291-2-2-1-1-2-1-1-1-1-1-1-2-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1130-122-1-12-1-1-1-1-1-12-1-1-1-1-1-1-1-1-1-1-1-1-2-1-2-1-1-1-1-1-1-1131-134-1-14-1-1-1-1-1-14-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-

6、1-1132-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-2-2-1-1-1-1-15-1133-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-167-1-1-1-1-1-1-1134-1-18-1-19-1-1-1-1-1-19-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1135-1-1-1-1-1-2-1-1-1-1-1-1-2-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-2-1136-1-1-1-1

7、-112-1-1-1-1-1-112-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-111-1137-1-1-11314-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-2-1-1-1-2-1-1-1138-1-1-1-1-115-1-1-1-1-1-116-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1139-1-2-2-1-1-2-1-1-1-1-1-1-2-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1140-1-1-1-1-118-1-1

8、-1-1-1-119-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1141-1-1-1-1-1-121-122-123242526-1-1-1-1-1-1-1-1-1-1-1-1-126-1-1-1-1-120-1142-1-1-1-1-1-1-1-1-1-1-1-1-1-2-1-1-1-1-1-1-1-1-1-1-1-1-1-2-1-1-1-1-127-1143-1-1-1-1-1-1-1-1-1-1-1-1-130-1-1-1-1-1-1-1-1-1-1-1-1-130-12829-1-1-1-1144-1-1-1-1-1-131-1-1-1-1-1

9、-1-2-1-1-1-1-1-1-1-1-1-1-1-1-1-2-1-1-1-1-1-1-1145-1-1-1-1-1-1-1-132-1-1-1-1-2-1-1-1-1-1-1-1-1-1-1-1-1-1-2-1-1-1-1-1-1-1146-1-1-1-1-1-1-1-1-1-133-1-1-2-1-1-1-1-1-1-1-1-1-1-1-1-1-2-1-1-1-1-1-1-1147-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-134-135-1-135-1-1-1148-1-1-1-1-1-1-1-1-1-1-136-1-2-1-1

10、-1-1-1-1-1-1-1-1-1-1-1-2-1-1-1-1-1-1-1149-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-137-1-1-1-138-1-1-1150-1-1-1-1-1-1-1-1-1-1-1-139-2-1-1-1-1-1-1-1-1-1-1-1-2-1-2-1-1-1-1-1-1-1151-1-1-1-1-1-1-1-1-1-1-1-1-141-1-1-1-1-1-1-1-1-1-1-1-1-140-1-1-1-1-1-1-1152-1-1-1-1-1-1-1-2-1-2-1-1-1-1434242-1-1-1

11、-1-1-1-1-1-1-1-1-1-142-14242-1153-1-1-1-1-1-1-1-2-1-2-1-1-1-2-14445-1-1-2-2-2-2-2-2-1-2-2-1-146-24646-1154-1-1-1-1-1-1-148-148-1-1-148-14747-1-1484848484848-14848-1-1-148-1-1-1155-1-1-1-1-1-1-1-2-1-2-1-1-1-2-1-2-2-1-1-2-2-2-2-2-2-1-2-2-1-149-24949-1156-1-1-1-1-1-1-151-151-1-1-151-1515150505151515151

12、51-15151-1-1-151-1-1-1157-1-1-1-1-1-1-1-2-1-2-1-1-1-2-1-2-2-2-2-2-2-2-2-2-2-1-2-2-1-154-25352-1158-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-156-1-155-1-1-1-1159-1-1-1-1-1-1-1-1-1-1-1-1-1-1-15758-1-1-1-1-1-1-1-1-1-1-1-1-1-2-1-2-2-1160-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-15960-1-1-1-1-1-1-1-1-1

13、-1-1-2-1-2-2-1161 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -2 2 1 -1 61 62 63 64 65 66 1 1 1 -1 -1 一2 -1 一2 2 -1源程序顯示源程序顯示PROGRAM HELLOWORLD;BEGINWRITE (1);N:=2END.626詞法分析結(jié)果(1)假設詞法分析無誤，那么顯示如下列圖所示并進行語法分析:詞法分析詞法分析共查找到o個錯誤(2)假設詞法分析有誤，那么顯示如下列圖所示，即指出錯誤之處，但不能進行語法 分析。text內(nèi)容：口 test.txt -記事本文件(E)編輯()格式(Q)查

14、看M program helloworld;beginwrite (1);n:=22y: =2end.結(jié)果如下：I左日混在了業(yè)不0ROGRAM HELLOWORLD;BEGINWRITE (1);N:=22Y:=2END.詞法分析一詞法分析共查找到1個錯誤第5行：Y出現(xiàn)錯誤語法分析結(jié)果(1)假設語法分析無誤，那么顯示如下列圖所示:語法分析；吾法分析共查找到0個錯誤(2)假設語法分析有誤，那么顯示如下列圖所示，即指出錯誤之處:i)棧中終結(jié)符與輸入串中終結(jié)符不相匹配時的情況：text內(nèi)容：_ J test.txt -記事本文件(E)編輯(E)格式(Q)查看。program helloworld;

15、beginwrite (1;n:=2end.結(jié)果顯示: 、后工口一日2. 混在仔業(yè)不PROGRAM HELLOWORLD;3EGINWRITE (1;N:=2END. -RJ /Z* 9T1/1- 詞法分析共查找到o個錯誤 第3行：；多余 第3行:在；前缺少字符ii)棧中非終結(jié)符與輸入串中終結(jié)符所對應的預測分析表中的數(shù)值為同步符時的情況：text內(nèi)容：_ I test.txt -記事本文件()編輯()格式(Q)查反program helloworld;beginwrite ( D;n:=2end.結(jié)果顯示:源程序顯示PROGRAM HELLOWORLD;BEGINWRITE ();N:=2EN

16、D. -WJ i/T- 詞法分析共查找到o個錯誤 第3行:于)前缺少字符 語法分析共查找到1個錯誤iii)棧中非終結(jié)符與輸入串中終結(jié)符所對應的預測分析表中的數(shù)值為不存在時的情況：text內(nèi)容：,test.txt -記事本文件任)編輯()格式(Q)查看program helloworld;def ine|beginwrite ();n:=2end.結(jié)果顯示:源程序顯示PROGRAM HELLOWORLD;DEFINEBEGINWRITE ();N:=2END.詞法分析一詞法分析共查找到0個錯誤語法分析一第2行：DEFINE多余第2行:在DEFINE前缺少字符第2行:在DEFINE前缺少字符7、總

17、結(jié)(1)本次實驗完成了語法分析器-預測分析法的算法分析到實現(xiàn)的全部過 程，結(jié)果滿足設計要求，驗證無誤。通過本次實驗讓我了解了如何設計、編制并 調(diào)試預測分析法的語法分析程序，在設計、實現(xiàn)、調(diào)試自己的語法分析器的同時, 加深了我對語法分析器原理的理解；熟悉了預測分析法構(gòu)造語法分析器的方法和 相關原理，并能基本使用C語言直接編寫語法分析器。(2)通過這次實驗使我懂得了理論與實際相結(jié)合的重要性，只有理論知識 是遠遠不夠的，只有把所學的理論知識與實踐相結(jié)合起來，才能更好地理解、消 化、掌握所學知識，同時也可以提高自己的實際動手能力和獨立思考的能力。在 設計的過程中遇到很多問題，可以說是困難重重，畢竟很多

18、問題是無法預料和避 免的，所以難免會遇到過各種各樣的問題，同時在設計的過程中發(fā)現(xiàn)了自己的不 足之處，對課程所學的知識理解得不夠深刻，掌握得不夠牢固等等。(3)在本實驗中，我鍛煉了自己的上機操作能力及編程能力，并對理論知 識有了進一步的了解。程序的難點是分析表的構(gòu)造，解決實驗中遇到的問題也花 費了一局部的時間，增長了處理程序錯誤的能力。雖然這個程序還有許許多多的 缺乏和欠缺，但它包含了我的想法和努力?？偟膩碚f，和成員一次完成這個語法 分析器的設計很有意義。8、程序代碼#include#include#include#include#includeusing namespace std;#defi

19、neMAX_l 1000#define MAX_2 100000/產(chǎn)生式的左右部以及右部的長度 typedef struct productionint left;int rightMAX_l;int length;PRO;程序每個字符的對應內(nèi)碼以及所在行數(shù) typedef struct character(string ch;int code;int row;CHAR;詞法分析時發(fā)現(xiàn)的錯誤typedef struct error(char ch;int row;ERR;集合結(jié)構(gòu)typedef struct aggregate(int strMAX_l;intlen;AGG;PRO *p=ne

20、w PRO MAX;/產(chǎn)生式CHAR charaMAX_2;程序字符流ERR errorMAX_2;詞法分析時發(fā)現(xiàn)的錯誤AGG FirstMAX;用于存放每個非終結(jié)符的First集AGG FoHowMAX_l;用于存放每個非終結(jié)符的Follow集intNONEMAX_l=0;求每個非終結(jié)符的Follow集時防止死循環(huán)的變量AGG Pro_FirstMAX;用于存放每個產(chǎn)生式右部的First集intTableMAX_lMAX_l;預測分析表,-1表示不匹配，-2表示同步符號synchintN;/產(chǎn)生式的個數(shù)char setMAX_2;用于存儲初始代碼char strMAX_2;用于存儲初步處理后

21、的代碼int errorNum=0;/詞法分析發(fā)現(xiàn)錯誤數(shù)int errorNum2=0;/語法分析發(fā)現(xiàn)錯誤數(shù)int k=0;程序字符流數(shù)int Program。w=l;程序初始行數(shù)stack Stack;符號棧非終結(jié)符stringkey 15= “PROGRAM” JCONST” JVAR”, “INTEGER” JLONG”, “PROCEDURE” JIF”THEN”/WHILE” JDO”READ”/WRITE” JBEGIN/END” JODD”;stringpunctuation17=”+Jv二”J)/判斷字符串是否是關鍵字，假設是，那么返回該關鍵字對應的內(nèi)碼；假設不是，那么返 回。

22、int IsKeyWord(string c)(int i;for(i=0;i15;i+)(if(keyi pare(c)=0)return i+1;)return 0;)/判斷字符串c是否是符號，假設是，那么返回該符號對應的內(nèi)碼；假設不是，那么返回0int IsPunctuation(string c)(int i;for(i=0;ia&cv=z)|(c=A&c=()&c=9)return true;elsereturn false;判斷該詞法錯誤是否已被檢測bool test(int errorNum,int row,char ch)(int i;for(i=0;ierrorNum;i+)

23、i f(error i. row =row&errori .ch =ch)return false;return true;詞法分析void lexical_analysis()(FILE *f;string tem=nn;char ch;int n=0,m=0;程序代碼儲存數(shù)int i;if(f=fopen(ntest.txt,；,rn)=NULL)(printf(Hcan not open the file!nH);exit(O);elsewhile(!feof(f)(ch=getc(f);/getc函數(shù)帶回一個字符，賦給ch setn=ch;將文件的每一個字符都放入set數(shù)組中 n+;f

24、close;關閉文件setn-l-Of;i=0;while(seti!=,O,)(if(seti=* *)(while(seti=，)掃描到有連續(xù)的空格i+;strm=;用一個空格代替掃描到的連續(xù)空格放入str m+;)else if(seti=n)while(seti=，)掃描到有連續(xù)的換行符i+；strm=，;/用一個換行符代替掃描到的連續(xù)換行符放入str m+;)else假設當前字符不為空格或換行符就直接放入strstrm=seti-32;elsestrm=seti;m+;i+；)strm=,0,;/顯示源程序源程序顯示printf(nnfor(i=0;im;i+)printf(n%cn

25、9stri);printf(Hnn);i=0;將源程序轉(zhuǎn)換成字符流for(i=0;i0)(charak.ch=tem;charak.code=IsKeyWord(tem);charak.row =Program_row; k+; else(charak.ch =tem;charak.code =34;charak.row =Program_row; k+;)else if(IsFigure(stri)(while(IsFigure(stri)(tem=tem+stri;i+；)if(IsLetter(stri)(crrorfcrrorNum .row=Program_row;error err

26、orNum .ch =stri; errorNum+;elsecharak.ch=tem;charak.code=33;charak.row =Program_row; k+;)tem=”；tem=tem+stri;switch(strfi)(case1:1:case：i+；if(stri=-*) tem=tem+stri;elsei-；charak.ch =tem;charak.code =IsPunctuation(tem);charak.row =Program_row;k+;break;case) tem=tem+stri;elsei-；charak.ch =tem;charak .c

27、ode =IsPunctuation(tem);charak.row =Program_row;k+；break;case;:case,:case.:case。：case):casc+:case-1:case*:case/:case-f:charak.ch =tem;charak.code =IsPunctuation(tem);charak.row =Program_row;k+;break;case#:charak.ch =tem;charak.code =35;charak.row =Program_row;k+;break;casebreak;casen:Program_row+;br

28、eak;default:if(test(errorNum,Program_row,stri)(errorferrorNum .row =Program_row;error errorNum .ch =stri; errorNum+;)所有產(chǎn)生式void production()(N=67;產(chǎn)生式共有67個/128-129 130 26 0p0.left=128;p0.right0=129;p0.rightl=130;p0.right2=26;p0.length=3; 129fl 34 28 0pl.lcft=129;pl.rightO=l;pl.rightl=34;pl.right2=28;p

29、l.length=3;130131 134 138 150 0 p2.left=130;p2.right0=131;p2.rightl=134;p2.right2=138;p2.right3=150;p2.length=4;131 一2 132 133 28 0p3.left=131;p3.right0=2;p3.rightl=132;p3.right2=133;p3.right3=28;p3.length=4;131 一 ()p4.left=131;p4.right0=0;p4.length=l;/13234 20 33 0p5.left=132;p5.right0=34;p5.rightl

30、=20;p5.right2=33;p5.length=3;133-27 132 133 0p6.left=133;p6.right0=27;p6.rightl=132;p .right =133;p6.length=3;/133-0p7.left=133;p7.right0=0;p7.lcngth=l;1343 135 136 0p8.left=134;p8.right0=3;p8.rightl=135;p8.right2=136;p8.length=3;/134-0p9.left=134;p9.right0=0;p9.length=l;13534 147 29 137 28 0p10.lef

31、t=135;p10.right0=34;p10.rightl=147;p10.right2=29;p10.right3=137;p10.right4=28;p10.length=5;136135 136 0pll.left=136;pll.right0=135;pll.rightl=136;pll.length=2; 136fop12.left=136;p12.right0=0;p12.length=l;137-4 0p13.left=137;p13.right0=4;p13.length=l;137-5 0p14.left=137;p14.right0=5;p14.length=l; 138

32、fl39 130 28 140 0p15.left=138;p15.right0=139;p15.rightl=130;p15.right2=28;p15.right3=140;p15.length=4; 138fop16.left=138;p16.right0=0;p16.length=l; 139f 6 34 158 28 0 p17.left=139;p17.right0=6;p17.rightl=34; p17.right2=158;p17.right3=28; p17.length=4;140139 130 28 140 0p18.left=140;p18.right0=139;p1

33、8.rightl=130;p18.right2=28;p18.right3=140;p18.length=4; 140fop19J.left=140;p19.right0=0;p19.length=l; 141fl42 0p20.left=141;p20.right0=142;p20.length=l;/141144 0 p21.left=141; p21.right0=144;p21.length=l;/141-145 0 p22.left=141; p22.right0=145;p22.length=l;一 1460p23.left=141; p23.right0=146; p23.len

34、gth=l; 148 0 p24.left=141; p24.right0=148; p24.length=l;141 一 1500 p25.left=141; p25.right0=150; p25.length=l;一 0 p26.left=141; p26.right0=0; p26.length=l;/142 - 34 143 0 p27.left=142; p27.right0=34;p27.rightl=143; p27.length=2;/143-30 153 0 p28.left=143; p28.right0=30; p28.rightl=153; p28.length=2;

35、/14331 153 32 0 p29.left=143;p29.right0=31; p29.rightl=153; p29.right2=32;p29.length=3; 143fo p30.left=143; p30.right0=0; p30.length=l;1447 152 8 141 0p31.left=144;p31.right0=7;p31.rightl=152;p31.right2=8;p31.right3=141;p31.length=4;1459 152 10 141 0p32.left=145;p32.right0=9;p32.rightl=152;p32.right

36、2=10;p32.right3=141;p32.length=4;146一 11 31 34 147 32 0p33.left=146;p33.right0=ll;p33.rightl=31;p33.right2=34;p33.right3=147;p33.right4=32;p33.length=5;147 - 27 34 147 0p34.left=147;p34.right0=27;p34.rightl=34;p34.right2=147;p34.length=3;147 一 0p35.left=147;p35.right0=0;p35.length=l;14812 31 153 149

37、 32 0p36.left=148;p36.right0=12;p36.rightl=31;p36.right2=153;p36.right3=149;p36.right4=32;p36.length=5;表達式后綴一，表過式X表達式后綴| 復合語句f BEGIN語句X語句后綴END語句后綴一；語句語句后綴|條件一表達式X關系運算符X表達式 | ODD表達式表達式一+項X項后綴 | Y項X項后綴|項X項后綴項后綴一（加型運算符X項 項后綴1 項f因子X因子后綴因子后綴一乘型運算符X因子X因子后綴| e因子一標識符I無符號整數(shù)I （表達式）加型運算符一+|-乘型運算型一*|/關系運算符 一 =|

38、=|=4.2內(nèi)碼對照表1-1終結(jié)符的內(nèi)部碼對照表內(nèi)碼單詞內(nèi)碼單詞內(nèi)碼單詞內(nèi)碼單詞1PROGRAM2CONST3VAR4INTEGER5LONG6PROCEDURE7IF8THEN9WHILE10DO11READ12WRITE13BEGIN14END15ODD16+17-18*19/20二21222325=26*272829*30 *31(32)33無符號整數(shù)34標識符35#表1-2非終結(jié)符和內(nèi)碼對照表內(nèi)碼非終結(jié)符內(nèi)碼非終結(jié)符內(nèi)碼非終結(jié)符128程序129程序首部130分程序131常量說明局部132常量定義133常量定義后綴134變量說明局部135變量定義136變量定義后綴137類型138過程說明

39、局部139過程首部140過程說明局部后綴141語句142賦值或調(diào)用語句143后綴144條件語句145當型循環(huán)語句146讀語句147標識符后綴148寫語句149表達式后綴150復合語句151語句后綴152條件153表達式154項后綴155項156因子后綴157因子158參數(shù)局部159加型運算符160乘型運算符161關系運算符 149f 27 153 149 0 p37.left=149;p37.right0=27;p37.rightl=153; p37.right2=149;p37.length=3;149 一 0 p38.left=149;p38.right0=0; p38.length=l;

40、15013 141 151 14 0 p39.left=150;p39.right0=13; p39.rightl=141;p39.right2=151; p39.right3=14;p39J.length=4;一 28 141 151 0 p40.left=151;p40.right0=28; p40.rightl=141;p40.right2=151; p40.length=3; 151fo p41.left=151; p41.right0=0; p41.length=l;152153 161 153 0 p42.left=152;p42.right0=153; p42.rightl=16

41、1; p42.right2=153;p42.lcngth=3; 152fl5 153 0 p43.left=152; p43.right0=15; p43.rightl=153;p43.length=2;153 - 16 155 154 0 p44.left=153;p44.right0=16;p44.rightl=155;p44.right2=154; p44.length=3;153 17 155 154 0 p45.left=153;p45.right0=17;p45.rightl=155; p45.right2=154; p45.length=3;153 155 154 0 p46.l

42、eft=153; p46.right0=155; p46J.rightl=154; p46.length=2;154159 155 154 0 p47jeft=154;p47.right0=159;p47.rightl=155;p47.right2=154; p47.length=3;:1540 p48.left=154; p48.right0=0; p48.length=l;155 - 157 156 0 p49.left=155; p49.right0=157;p49.rightl=156; p49.lcngth=2;156160 157 156 0 p50.left=156;p50.ri

43、ght0=160;p50.rightl=157;p50.right2=156;p50.length=3; 156fo p51.left=156; p51.right0=0; p51.length=l;15734 0 p52.left=157;p52.right0=34; p52.length=l;157 一 33 0 p53.left=157;p53.right0=33; p53.length=l;15731 153 32 0 p54.left=157;p54.right0=31; p54.rightl=153;p54.right2=32; p54.length=3;/158-31 34 29

44、 137 32 0 p55.left=158;p55.right0=31;p55.rightl=34;p55.right2=29; p55.right3=137; p55.right4=32; p55.length=5;158 一 0 p56.left=158; p56.right0=0; p56.length=l;/159-16 0 p57.left=159; p57.right0=16; p57.length=l;159 17 0 p58.left=159; p58.right0=17; p58.length=l;/160-18 0 p59.left=160; p59.right0=18;

45、p59.length=l;/160 - 19 0 p60.left=160; p60.right0=19;p60.length=l;161 - 20。p61.left=161;p61.right0=20;p61.length=l;/161-21 0 p62.left=161; p62.right0=21;p62.length=l;161 22 0 p63.left=161; p63.right0=22; p63.length=l;161-23 0 p64.left=161; p64.right0=23;p64.length=l;/161-24 0 p65.left=161; p65.right

46、0=24;p65.lcngth=l;161-25。p66.left=161;p 66 .right0 =25;p66.length=l;)在str口中查找t,假設找到t,那么返回t所在的數(shù)組下標;否那么返回大數(shù),設定該大數(shù)為 MAXint search(AGG set,int t)(int i;for(i=0;iset.len;i+)(if(set.stri-t)return i;)return MAX 1;)對每個非終結(jié)符A求First集AGG Character_First(PRO *p,int code)(int k#ag=l;/假設某個產(chǎn)生式的右側(cè)字符均為非終結(jié)符，且所有非終結(jié)符的Fi

47、rst集中均含有 ,那么flag的值為1遍歷所有產(chǎn)生式求該非終結(jié)符A的First集for(int i=0;i=l&pi.right0k=35)該非終結(jié)符 A 所在的產(chǎn)生式的右側(cè)第一個字符是終結(jié)符，那么將此終結(jié)符加入該非終結(jié)符的First集(if(search(Firstcode ,pi .right0)MAX_ 1)/ 該 非 終結(jié)符 A 的First集無此終結(jié)符，那么將此終結(jié)符加入該非終結(jié)符的First集(Firstcode .strFirstcode .len=pi .right0;Firstcode.len+;)if(pi.rightO=O)該非終結(jié)符所在的產(chǎn)生式的右側(cè)是，那么將此終 結(jié)

48、符加入該非終結(jié)符的First集(if(search(Firstcode ,pi .right 0 )=MAX_ 1)Firstcode.strFirstcode.len =pi.rightO;Firstcode.len+;)if(pi.right=128&pi.right0v=161)該非終結(jié)符 A 所在的產(chǎn) 生式的右側(cè)第一個字符是非終結(jié)符(if(piength=l)該非終結(jié)符A所在的產(chǎn)生式的右側(cè)僅有一 個非終結(jié)符B,那么將非終結(jié)符B的First集加入到非終結(jié)符A的First集(AGG setl;setl.len=O;set l=Character_First(p,pi.right 10);f

49、or(int j=0;jsetl.len;j+)(if(search(Firstcode,setl .strj)MAX_l)(Firstcode.strFirstcode.len=setl.strj;Firstcode.len+;)else/該非終結(jié)符A所在的產(chǎn)生式的右側(cè)符號數(shù)大于1(for(int j=0;j= 128&pi.rightj= 161)/ 該 非 終 結(jié) 符A所在的產(chǎn)生式的右側(cè)第j符號為非終結(jié)符(set=Character_First(p,pi.rightj|);if(search(set,O)MAX_l)非終結(jié)符 pi.rightj的 First集中含有(for(k=0;ks

50、et.len;k+)(if(search(Firstcode,set.strk)=MAX_l&set.strk!=0)將非終結(jié)符 pi.rightj 的First集中康之外的元家均加入所求非終結(jié)符A的First集中(Firstcode.strFirstcode.len=set.strk;Firstcode.len+;)else/非終結(jié)符pi.rightj的First集中不含flag=O;for(k=0;kset.len;k+)(if(search(Firstcode,set.strk)=MAX_l)/將非終結(jié)符 pi.rightj的 First 集中所有 元素均加入所求非終結(jié)符A的First集

51、中(First code .str Firstcode .len=set.strk;Firstcode.len+;) break; )else/該非終結(jié)符所在的產(chǎn)生式的右側(cè)符號中遇到終 結(jié)符(flag=0;if(search(First code ,p i .right j )=MAX_ 1)(Firstcode.strFirstcode.len=pi.rightj;Firstcode.len+;)break;)/該非終結(jié)符所在的產(chǎn)生式的右側(cè)符號均為非終結(jié)符，且所 有非終結(jié)符的First集中均含有，那么將0加入該非終結(jié)符的First集中，其中0表 示空集&if(flag-l)(Firstcod

52、e.strFirstcode.len=0;Firstcode.len+;)return Firstcode;)求每個非終結(jié)符A的Follow集AGG Character_Follow(PRO *p,int code)intt,k,flag=l;假設該非終結(jié)符A的右側(cè)字符均為非終結(jié)符，且所有非終結(jié)符的First集中均含有 ,那么flag的值為1NONEcode+;防止死循環(huán)的變量值自增if(NONEcode=2)當出現(xiàn)所求非終結(jié)符的Follow集需要將自身加入時，將 防止死循環(huán)的變量值設為3并跳出死循環(huán)(NONEcode=0;return Followcode;遍歷所有產(chǎn)生式求該非終結(jié)符A的Fo

53、llow集for(int i=0;iN;i+)(for(int j=O;jpi .length;j+)(if(pi.rightj=code)在產(chǎn)生式的右部找到該非終結(jié)符A(if(j+l=piength)該非終結(jié)符A在其所在的產(chǎn)生式的最右側(cè)(AGG setl;setl.len=O;set l=Character_Follow(p,pi.left);for(k=0;kset 1 .len;k+)(if(search(Followcode,setl.strk)=MAX_l)/i非終結(jié)符 A 的Follow集無此終結(jié)符，那么將此終結(jié)符加入該非終結(jié)符A而Follow集(Followcode.strFol

54、lowcode.len=setl.strk;Followcode.len+;else/該非終結(jié)符A不在其所在的產(chǎn)生式，即非終結(jié)符A的右側(cè)還 有符號(AGG set2;sct2.1cn=0;for(int q=j+1 ；q=l&pi.rightq=128&pi.rightqv=161)該非終結(jié) 符A右側(cè)的符號是非終結(jié)符(set3=Character_First(p,pi.rightq);if(search(set3,0)MAX_l) 該非終結(jié)符A右側(cè)的非終 結(jié)符pi.rightq的First集中含有(for(t=0;tset3.1en;t+) (if(seach(set2,set3.strt)=

55、MAX_l&set3.strt!=0)/將非終結(jié)符pi.rightq的First集中除e之外的元素均加入set2集中(set2.strset2.1en=set3.strt;set2.1en+; )else/該非終結(jié)符A右側(cè)的非終結(jié)符pi.rightq的First集中不含有(flag=O;for(t=0;tset3.1en;t+) (if(search(set2,set3.strt)=MAX_l)將 非 終結(jié)符pi.rightq的First集中所有元素均加入set2集中(set2.strset2.1en=set3.strt;sct2.1cn+;) ) break;該非終結(jié)符所在的產(chǎn)生式的右側(cè)符號

56、均為非終結(jié)符，且所有非終結(jié)符的First集中均含有 ,那么將0加入set2集中，其中0表示空集 if(flag-l)(set2.strset2.1en=0;set2.1en+;)if(search(set2,0)=MAX_l)/set2 集中不含 ,那么將 set2 集中 的所有元素均加入該非終結(jié)符A的Follow集中(B-aAC,把 First(C)去掉 加入到 Follow(A)中(FirstQ) 不含 )for(k=0;kset2.1en;k+)(if(search(Followcode, set2. str k )=M AX_ 1)(Followcode.strFollowcode.l

57、en=set2.strk;Followcode.len+;)else/set2集中含有e ,那么將set2集中除之外的元素均加入 該非終結(jié)符A的Follow集中(B-aAC,把 First(C)去掉 加入到 Follow(A)中(First(C)含 )for(k=0;kaAC, 在 First(C)中，把 Follow(B)加入到 Follow(A) 中AGG set4;set4.1en=0;set4=Character_Follow(p,pi.left);for(k=0;k13 141 151 14 0152153 161 153 015317 155 154 0154-0156-0157一

58、31 153 32 0159fl6 016019 016122 0161-25 0131-0133-0135-34 147 29 137 28 0137-4 0138-0140-0141-145 0141-150 014330 153 0144-7 152 8 141 0147-27 34 147 0149f 27 153 149 0151f 28 141 151 015215 153 0153155 154 0155-157 156 015734 015831 34 29 137 32159fl7 016120 016123 013234 20 33 01343 135 136 0136-1

59、35 136 0137-5 0139 6 34 158 28141一142 0141一146 0141-014331 153 32 0145-9 152 10 141147-0149 一 0151-015316 155 154 0154-159 155 154 0156160 157 156 0157- 33 00158-016018 0161-21 0161f 24 0求非終結(jié)符的First集的方法：.直接收?。杭僭OU a(其中a是終結(jié)符)，把a收入到First (U)中;.反復傳送：假設UP(其中P是非終結(jié)符)，應把First (P)中的全部內(nèi) 容傳送到First (U)中。if(sear

60、ch(Followcode,set4.strk)=MAX_l)Followcode .strFollowcode .len=set4.strk;Followfcode.len+;)return Follow code;)/求所有非終結(jié)符的First集 void Keep_Character_First() (int i=0;for(i= 128;i= 161 ;i+) (AGG set;set.len=0;set=Character_First(p,i);)求所有非終結(jié)符的Follow集 void Keep_Character_Follow() (int i;for(i= 128;i= 16