计算机编译原理---语法分析预测分析法

1、编译原理实验报告语法分析2预测分析法目录 TOC o 1-5 h z 1.摘要：32、实验目的：33、任务概述34、实验依据的原理35、程序设计思想56、实验结果分析9 HYPERLINK l bookmark14 o Current Document 7、总结18 HYPERLINK l bookmark16 o Current Document 8、程序代码18所有非终结符的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所有产生式的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词法分析结果(1)假设词法分析无误，那么显示如下列图所示并进行语法分析:词法分析词法分析共查找到o个错误(2)假设词法分析有误，那么显示如下列图所示，即指出错误之处，但不能进行语法 分析。text内容：口 test.txt -记事本文件(E)编辑()格式(Q)查

14、看M program helloworld;beginwrite (1);n:=22y: =2end.结果如下：I左日混在了业不0ROGRAM HELLOWORLD;BEGINWRITE (1);N:=22Y:=2END.词法分析一词法分析共查找到1个错误第5行：Y出现错误语法分析结果(1)假设语法分析无误，那么显示如下列图所示:语法分析；吾法分析共查找到0个错误(2)假设语法分析有误，那么显示如下列图所示，即指出错误之处:i)栈中终结符与输入串中终结符不相匹配时的情况：text内容：_ J test.txt -记事本文件(E)编辑(E)格式(Q)查看。program helloworld;

15、beginwrite (1;n:=2end.结果显示: 、后工口一日2. 混在仔业不PROGRAM HELLOWORLD;3EGINWRITE (1;N:=2END. -RJ /Z* 9T1/1- 词法分析共查找到o个错误 第3行：；多余 第3行:在；前缺少字符ii)栈中非终结符与输入串中终结符所对应的预测分析表中的数值为同步符时的情况：text内容：_ I test.txt -记事本文件()编辑()格式(Q)查反program helloworld;beginwrite ( D;n:=2end.结果显示:源程序显示PROGRAM HELLOWORLD;BEGINWRITE ();N:=2EN

16、D. -WJ i/T- 词法分析共查找到o个错误 第3行:于)前缺少字符 语法分析共查找到1个错误iii)栈中非终结符与输入串中终结符所对应的预测分析表中的数值为不存在时的情况：text内容：,test.txt -记事本文件任)编辑()格式(Q)查看program helloworld;def ine|beginwrite ();n:=2end.结果显示:源程序显示PROGRAM HELLOWORLD;DEFINEBEGINWRITE ();N:=2END.词法分析一词法分析共查找到0个错误语法分析一第2行：DEFINE多余第2行:在DEFINE前缺少字符第2行:在DEFINE前缺少字符7、总

17、结(1)本次实验完成了语法分析器-预测分析法的算法分析到实现的全部过 程，结果满足设计要求，验证无误。通过本次实验让我了解了如何设计、编制并 调试预测分析法的语法分析程序，在设计、实现、调试自己的语法分析器的同时, 加深了我对语法分析器原理的理解；熟悉了预测分析法构造语法分析器的方法和 相关原理，并能基本使用C语言直接编写语法分析器。(2)通过这次实验使我懂得了理论与实际相结合的重要性，只有理论知识 是远远不够的，只有把所学的理论知识与实践相结合起来，才能更好地理解、消 化、掌握所学知识，同时也可以提高自己的实际动手能力和独立思考的能力。在 设计的过程中遇到很多问题，可以说是困难重重，毕竟很多

18、问题是无法预料和避 免的，所以难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不 足之处，对课程所学的知识理解得不够深刻，掌握得不够牢固等等。(3)在本实验中，我锻炼了自己的上机操作能力及编程能力，并对理论知 识有了进一步的了解。程序的难点是分析表的构造，解决实验中遇到的问题也花 费了一局部的时间，增长了处理程序错误的能力。虽然这个程序还有许许多多的 缺乏和欠缺，但它包含了我的想法和努力。总的来说，和成员一次完成这个语法 分析器的设计很有意义。8、程序代码#include#include#include#include#includeusing namespace std;#defi

19、neMAX_l 1000#define MAX_2 100000/产生式的左右部以及右部的长度 typedef struct productionint left;int rightMAX_l;int length;PRO;程序每个字符的对应内码以及所在行数 typedef struct character(string ch;int code;int row;CHAR;词法分析时发现的错误typedef struct error(char ch;int row;ERR;集合结构typedef struct aggregate(int strMAX_l;intlen;AGG;PRO *p=ne

20、w PRO MAX;/产生式CHAR charaMAX_2;程序字符流ERR errorMAX_2;词法分析时发现的错误AGG FirstMAX;用于存放每个非终结符的First集AGG FoHowMAX_l;用于存放每个非终结符的Follow集intNONEMAX_l=0;求每个非终结符的Follow集时防止死循环的变量AGG Pro_FirstMAX;用于存放每个产生式右部的First集intTableMAX_lMAX_l;预测分析表,-1表示不匹配，-2表示同步符号synchintN;/产生式的个数char setMAX_2;用于存储初始代码char strMAX_2;用于存储初步处理后

21、的代码int errorNum=0;/词法分析发现错误数int errorNum2=0;/语法分析发现错误数int k=0;程序字符流数int Program。w=l;程序初始行数stack Stack;符号栈非终结符stringkey 15= “PROGRAM” JCONST” JVAR”, “INTEGER” JLONG”, “PROCEDURE” JIF”THEN”/WHILE” JDO”READ”/WRITE” JBEGIN/END” JODD”;stringpunctuation17=”+Jv二”J)/判断字符串是否是关键字，假设是，那么返回该关键字对应的内码；假设不是，那么返 回。

22、int IsKeyWord(string c)(int i;for(i=0;i15;i+)(if(keyi pare(c)=0)return i+1;)return 0;)/判断字符串c是否是符号，假设是，那么返回该符号对应的内码；假设不是，那么返回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;程序代码储存数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函数带回一个字符，赋给ch setn=ch;将文件的每一个字符都放入set数组中 n+;f

24、close;关闭文件setn-l-Of;i=0;while(seti!=,O,)(if(seti=* *)(while(seti=，)扫描到有连续的空格i+;strm=;用一个空格代替扫描到的连续空格放入str m+;)else if(seti=n)while(seti=，)扫描到有连续的换行符i+；strm=，;/用一个换行符代替扫描到的连续换行符放入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;将源程序转换成字符流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+;)所有产生式void production()(N=67;产生式共有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无符号整数I （表达式）加型运算符一+|-乘型运算型一*|/关系运算符 一 =|

38、=|=4.2内码对照表1-1终结符的内部码对照表内码单词内码单词内码单词内码单词1PROGRAM2CONST3VAR4INTEGER5LONG6PROCEDURE7IF8THEN9WHILE10DO11READ12WRITE13BEGIN14END15ODD16+17-18*19/20二21222325=26*272829*30 *31(32)33无符号整数34标识符35#表1-2非终结符和内码对照表内码非终结符内码非终结符内码非终结符128程序129程序首部130分程序131常量说明局部132常量定义133常量定义后缀134变量说明局部135变量定义136变量定义后缀137类型138过程说明

39、局部139过程首部140过程说明局部后缀141语句142赋值或调用语句143后缀144条件语句145当型循环语句146读语句147标识符后缀148写语句149表达式后缀150复合语句151语句后缀152条件153表达式154项后缀155项156因子后缀157因子158参数局部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所在的数组下标;否那么返回大数,设定该大数为 MAXint search(AGG set,int t)(int i;for(i=0;iset.len;i+)(if(set.stri-t)return i;)return MAX 1;)对每个非终结符A求First集AGG Character_First(PRO *p,int code)(int k#ag=l;/假设某个产生式的右侧字符均为非终结符，且所有非终结符的Fi

47、rst集中均含有 ,那么flag的值为1遍历所有产生式求该非终结符A的First集for(int i=0;i=l&pi.right0k=35)该非终结符 A 所在的产生式的右侧第一个字符是终结符，那么将此终结符加入该非终结符的First集(if(search(Firstcode ,pi .right0)MAX_ 1)/ 该 非 终结符 A 的First集无此终结符，那么将此终结符加入该非终结符的First集(Firstcode .strFirstcode .len=pi .right0;Firstcode.len+;)if(pi.rightO=O)该非终结符所在的产生式的右侧是，那么将此终 结

48、符加入该非终结符的First集(if(search(Firstcode ,pi .right 0 )=MAX_ 1)Firstcode.strFirstcode.len =pi.rightO;Firstcode.len+;)if(pi.right=128&pi.right0v=161)该非终结符 A 所在的产 生式的右侧第一个字符是非终结符(if(piength=l)该非终结符A所在的产生式的右侧仅有一 个非终结符B,那么将非终结符B的First集加入到非终结符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/该非终结符A所在的产生式的右侧符号数大于1(for(int j=0;j= 128&pi.rightj= 161)/ 该 非 终 结 符A所在的产生式的右侧第j符号为非终结符(set=Character_First(p,pi.rightj|);if(search(set,O)MAX_l)非终结符 pi.rightj的 First集中含有(for(k=0;ks

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

51、中(First code .str Firstcode .len=set.strk;Firstcode.len+;) break; )else/该非终结符所在的产生式的右侧符号中遇到终 结符(flag=0;if(search(First code ,p i .right j )=MAX_ 1)(Firstcode.strFirstcode.len=pi.rightj;Firstcode.len+;)break;)/该非终结符所在的产生式的右侧符号均为非终结符，且所 有非终结符的First集中均含有，那么将0加入该非终结符的First集中，其中0表 示空集&if(flag-l)(Firstcod

52、e.strFirstcode.len=0;Firstcode.len+;)return Firstcode;)求每个非终结符A的Follow集AGG Character_Follow(PRO *p,int code)intt,k,flag=l;假设该非终结符A的右侧字符均为非终结符，且所有非终结符的First集中均含有 ,那么flag的值为1NONEcode+;防止死循环的变量值自增if(NONEcode=2)当出现所求非终结符的Follow集需要将自身加入时，将 防止死循环的变量值设为3并跳出死循环(NONEcode=0;return Followcode;遍历所有产生式求该非终结符A的Fo

53、llow集for(int i=0;iN;i+)(for(int j=O;jpi .length;j+)(if(pi.rightj=code)在产生式的右部找到该非终结符A(if(j+l=piength)该非终结符A在其所在的产生式的最右侧(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非终结符 A 的Follow集无此终结符，那么将此终结符加入该非终结符A而Follow集(Followcode.strFol

54、lowcode.len=setl.strk;Followcode.len+;else/该非终结符A不在其所在的产生式，即非终结符A的右侧还 有符号(AGG set2;sct2.1cn=0;for(int q=j+1 ；q=l&pi.rightq=128&pi.rightqv=161)该非终结 符A右侧的符号是非终结符(set3=Character_First(p,pi.rightq);if(search(set3,0)MAX_l) 该非终结符A右侧的非终 结符pi.rightq的First集中含有(for(t=0;tset3.1en;t+) (if(seach(set2,set3.strt)=

55、MAX_l&set3.strt!=0)/将非终结符pi.rightq的First集中除e之外的元素均加入set2集中(set2.strset2.1en=set3.strt;set2.1en+; )else/该非终结符A右侧的非终结符pi.rightq的First集中不含有(flag=O;for(t=0;tset3.1en;t+) (if(search(set2,set3.strt)=MAX_l)将 非 终结符pi.rightq的First集中所有元素均加入set2集中(set2.strset2.1en=set3.strt;sct2.1cn+;) ) break;该非终结符所在的产生式的右侧符号

56、均为非终结符，且所有非终结符的First集中均含有 ,那么将0加入set2集中，其中0表示空集 if(flag-l)(set2.strset2.1en=0;set2.1en+;)if(search(set2,0)=MAX_l)/set2 集中不含 ,那么将 set2 集中 的所有元素均加入该非终结符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集中除之外的元素均加入 该非终结符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求非终结符的First集的方法：.直接收取：假设U a(其中a是终结符)，把a收入到First (U)中;.反复传送：假设UP(其中P是非终结符)，应把First (P)中的全部内 容传送到First (U)中。if(sear

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