1 源代码2 模块一：3 /****************#include"firstVT_lastVT.h"************************/

4

5 //程序功能大意说明6 //该子程序主要是求算符优先文法中的firstVT()和lastVT()7 //因为求firstVT()和lastVT(),可能造成的递归性，我们需要慎重对待。8 //直至求完所有集合的元素为止9 //这里要注意递归的运用和FirstVT(),LastVT()的定义10 //firstVT(E)为a...或Qa....中的终结符a,以及firstVT(Q)中的所有元素。11 //lastVT(E)为...a或....aQ中的终结符a,以及lastVT(Q)中的所有元素。12

13 //引用外部变量

14 extern char FIRSTVT[20][20];15 extern char LASTVT[20][20];16 extern char PriorityTable[20][20];17 extern char INPUT[20][20];18

19 //填写firstVT集合

20 void setFIRSTVT(char X,intT)21 {//X为终结符，T标记产生式id

22 inti,j;23 for(i=0;i<20;i++)24 {25 if(i==T)26 {27 for(j=0;j<20;j++)28 {//扫描判断是否加入

29 if(X==FIRSTVT[i][j])30 {//若集合中已出现，则不加

31 return;32 }33 else if(FIRSTVT[i][j]=='\0')34 {35 FIRSTVT[i][j]=X;//填入数组最后

36 break;37 }38 }39 break;40 }41 }42 }43 //找出FIRSTVT集元素

44 void getFIRSTVT(char X,intS)45 {46 int i,j=0,k;//j当前数组指针

47 int T=0;//X position

48 int L=0;//X offspring length

49 char C[20];50

51 for(i=0;i<20;i++)52 {53 if(INPUT[i][0]==X)//找到将要处理的产生式

54 {55 T=i; //标记产生式的位置

56 break;57 }58 }59 //按照规则从产生式的右部第一个字符开始处理，直至遇上'/n'60 //每一次都判断指针j指向的字符若满足p-->w中w的规定则放进C[]61 //若遇上‘|’或'\n'则求这段右部对应的firstVT()

62 for(i=4;i<20;i++)63 {64 if(INPUT[T][i]=='|'||INPUT[T][i]=='\n')65 {//刚开始走不到这里

66 L=j;//j指针所指位置为C[]中字符串的长度

67 j=0;//交给L后就清零，以供下一次使用

68 for(k=0;k

74

75 if((C[k]>=97&&C[k]<=122)||C[k]=='+'||C[k]=='*'||C[k]=='-'||C[k]=='/'||C[k]=='!'||C[k]=='('||C[k]==')'||C[k]=='#'||C[k]=='\?'||C[k]=='=')76 {//只能用一次,因是算符优先文法，故前两个中必会至少存在一个终结符

77 setFIRSTVT(C[k],S);//存入FIRSTVT中，S标记产生式的位置

78 break;//跳出循环保证存入的是最左边的终结符

79 }80 }81 if(C[0]>=65&&C[0]<=90&&C[0]!=X)82 {//若C[0]中为A~Z,并且C[0]不是X(否则将无限循环)，则递归的进行填充

83 int flag=0,count;84 for(count=0;count<20;count++)85 {86 if(INPUT[count][0]==C[0])//找到将要处理的产生式

87 {88 flag=1;//若存在，则填充

89 }90 }91 if(flag==1)92 {//递归，所用极妙，画龙点睛

93 getFIRSTVT(C[0],S);//S为子集中的元素填入父集中指明了方向

94 }95 }96 }97 else if(INPUT[T][i]!='|'&&INPUT[T][i]!='\0')//该行没结束，过滤'\0'

98 {99 C[j]=INPUT[T][i];//j从0开始

100 j++;//移进

101 }102 if(INPUT[T][i]=='\n')103 {//该行结束

104 break;105 }106 }107 }108

109 //存储LASTVT集

110 void setLASTVT(char X,intT)111 {//X为终结符，T标记产生式id

112 inti,j;113 for(i=0;i<20;i++)114 {115 if(i==T)116 {117 for(j=0;j<20;j++)118 {119 if(X==LASTVT[i][j])120 {//若集合中已出现，则不加

121 break;122 }123 else if(LASTVT[i][j]=='\0')124 {125 LASTVT[i][j]=X;//填入数组最后

126 return;127 }128 }129 break;130 }131 }132 }133

134 //找出LASTVT集元素

135 void getLASTVT(char X,intS)136 {137 int i,j=0,k;//j当前数组指针

138 int T=0;//X position

139 int L=0;//X offspring length

140 char C[20];141

142 for(i=0;i<20;i++)143 {144 if(INPUT[i][0]==X)//找到将要处理的产生式

145 {146 T=i; //标记产生式的位置

147 break;148 }149 }150 //按照规则从产生式的右部第一个字符开始处理，直至遇上'/n'151 //每一次都判断指针j指向的字符若满足p-->w中w的规定则放进C[]152 //若遇上‘|’或'\n'则求这段右部对应的LASTVT()

153 for(i=4;i<20;i++)154 {155 if(INPUT[T][i]=='|'||INPUT[T][i]=='\n')156 {//刚开始走不到这里

157 L=j;//j指针所指位置为C[]中字符串的长度

158 j=0;//交给L后就清零，以供下一次使用

159 for(k=L-1;k>=0;k--)160 {//要是数组C[]中的终结符，如小写字母'a'~'z'，加减乘除，乘方，#161 //则归入LASTVT集中162 //若是Aab...则a成为F()一部分，b被忽略,A也不用求first集？？？需要求！！！除非A==X163 //若是QRa...，则不是算符优先文法，故不可能164 //若是a...则只是填进a

165

166 if((C[k]>=97&&C[k]<=122)||C[k]=='+'||C[k]=='*'||C[k]=='-'||C[k]=='/'||C[k]=='!'||C[k]=='('||C[k]==')'||C[k]=='#'||C[k]=='\?'||C[k]=='=')167 {//只能用一次

168 setLASTVT(C[k],S);//存入LASTVT中，S标记产生式的位置

169 break;//跳出循环保证存入的是最左边的终结符

170 }171 }172 if(C[L-1]>=65&&C[L-1]<=90&&C[L-1]!=X)173 {//若C[0]中为A~Z,并且C[]中没有终结符，则递归的进行填充

174 int flag=0,count;175 for(count=0;count<20;count++)176 {177 if(INPUT[count][0]==C[L-1])//找到将要处理的产生式

178 {179 flag=1;180 }181 }182 if(flag==1)183 {//同firstVT()

184 getLASTVT(C[L-1],S);//S为子集中的元素填入父集中指明了方向

185 }186 }187 }188 else if(INPUT[T][i]!='|'&&INPUT[T][i]!='\0')//该行没结束，过滤'\0'

189 {190 C[j]=INPUT[T][i];//j从0开始

191 j++;//移进

192 }193 if(INPUT[T][i]=='\n')194 {//该行结束

195 break;196 }197 }198 }199

200

201

202 voidDisplayFirstVT_LasVT()203 {204 inti,j;205 printf("\t*-------------------------------------------------------*\n");206 printf("\t|\t欢迎使用算符优先文法分析器...... |\n");207 printf("\t|\t因时间有限，适用范围可能有限！ |\n");208 printf("\t|\t请输入算符优先文法，按两次回车代表输入完成: |\n");209 printf("\t|\t版权所有：软件工程2班，朱彦荣，20132184 |\n");210 printf("\t*-------------------------------------------------------*\n");211 for(i=0;i<20;i++)212 {//获得产生式放入input[][]中

213 for(j=0;j<20;j++)214 {215 scanf("%c",&INPUT[i][j]);216 if(INPUT[i][j]=='\n')217 break;//每行接收一个产生式

218 }219 if(INPUT[i][0]=='\n')220 break;//遇到又一次回车，结束输入

221 }222 //保存FIRSTVT集

223 for(i=0;INPUT[i][0]!='\n';i++)224 {//对所有的产生式

225 getFIRSTVT(INPUT[i][0],i);//第i+1个产生式，求fistvt()，核心算法

226 }227 printf("FIRSTVT SET:\n");228 for(i=0;INPUT[i][0]!='\n';i++)229 {//对所有产生式，进行输出fistvt集，最大处理能力20个产生式

230 printf("FIRSTVT(");231 printf("%c",INPUT[i][0]);232 printf(")={");233 for(j=0;FIRSTVT[i][j]!='\0';j++)234 {235 printf("%c",FIRSTVT[i][j]);236 if(FIRSTVT[i][j+1]!='\0')237 {238 printf(",");//添加逗号

239 }240 }241 printf("}\n");242 }243

244 printf("\n");245 for(i=0;INPUT[i][0]!='\n';i++)246 {//对所有的产生式

247 getLASTVT(INPUT[i][0],i);//第i+1个产生式，求lastvt()，核心算法

248 }249 for(i=0;INPUT[i][0]!='\n';i++)250 {251 printf("LASTVT(");252 printf("%c",INPUT[i][0]);253 printf(")={");254 for(j=0;LASTVT[i][j]!='\0';j++)255 {//逐次输出

256 printf("%c",LASTVT[i][j]);257 if(LASTVT[i][j+1]!='\0')258 printf(",");259 }260 printf("}\n");261 }262 printf("\n");263 }264 /*******************end #include "firstVT_lastVT.h"************************/

265

266 模块二：267 /**************#include "GetPriorityTable.h"**********************/

268 //此分程序主要是计算优先关系表269 //优先分析表是算符优先文法的关键，因此应该慎重对待270 //如何建表，建什么类型的表，表的使用是不是方便都是我们要考虑的情况

271

272 extern char FIRSTVT[20][20];273 extern char LASTVT[20][20];274 extern char PriorityTable[20][20];275 extern char INPUT[20][20];276

277 int IsVT(charch)278 {//判断是否是终结符

279 if((ch>=97&&ch<=122)||ch=='+'||ch=='*'||ch=='-'||ch=='/'||ch=='!'||ch=='('||ch==')'||ch=='#'||ch=='\?'||ch=='=')280 {281 return 1;//为终结符

282 }283 return 0;//不是终结符

284 }285

286 int SearchTbl(charch)287 {//返回符号所在的行列

288 int index=-1;289 //该排列即为优先关系表中元素的排列情况290 //行和列的排列相同便于查找和引用291 //因此即可以查行又可以查列

292 char temp[13]={'+','-','*','/','(',')','v','c','=','?','#','\0'};293 for(int i=0;i<11;i++)294 {295 if(ch==temp[i])296 {297 index=i+1;//之所以是i+1，因为该顺序从一开始

298 break;299 }300 }301 return index;//返回所查找的横(纵)坐标

302 }303

304 int FL_map(charch)305 {//这个映射既是查找产生式左部的位置

306 switch(ch)307 {308 case 'S': return 0;break;309 case 'E': return 1;break;310 case 'T': return 2;break;311 case 'F': return 3;break;312 default: return -1;break;//查找失败

313 }314 }315

316 voidcreatePriorityTable()317 {//创建并填写优先级表318 //对每个产生式遍历，求出四种关系1.=,2.,4.没有关系

319 char temp[13]={'+','-','*','/','(',')','v','c','=','?','#','\0'};320 intj,L,i;321 int tbl_row,tbl_column;//表的元素坐标

322 char C[20];323 for(int r=1;r<12;r++)324 {325 PriorityTable[0][r]=temp[r-1];//初始化行头，第0行

326 PriorityTable[r][0]=temp[r-1];//初始化第0列

327 }328 //扫描产生式的右部，如果发现终结符且该终结符周围有其他字符329 //若该其他字符为终结符，则这两者关系为相等330 //若该其他字符为非终结符，则根据非终结符的firstVT,LastVt填表

331 for(int p=0;p<4;p++)332 {333 j=0;334 for(i=4;i<20;i++)335 {//注意，此处因为时间有限考虑不是很全面，只是对老师给定的文法进行了周密的部署336 //在别的文法上可能需要少许加工，不是问题

337 if(INPUT[p][i]=='|'||INPUT[p][i]=='\n')338 {//刚开始走不到这里

339 L=j;//j指针所指位置为C[]中字符串的长度

340 j=0;//交给L后就清零，以供下一次使用

341 if(L>1)//大于一则处理，否则不关心

342 { //对于清零指令l自动忽略

343 if(IsVT(C[0])&&IsVT(C[1])||(L==3)&&IsVT(C[0])&&IsVT(C[2])&&(FL_map(C[1])!=-1))344 {//若为终结符因至少有两个,若出现两个终结符则C[0]'=='C[1]||C[2]，注意这是此文法的情况345 //则需要填表，查表找到C[0]的行数，C[1],C[2]的列数进行填表

346 tbl_row=SearchTbl(C[0]);//记录行数

347 if(IsVT(C[1]))348 {//列数，若是终结符 v=

349 tbl_column=SearchTbl(C[1]);350 }351 if(IsVT(C[2])&&(L==3))352 {//列数 (E)

353 tbl_column=SearchTbl(C[2]);354 }355 PriorityTable[tbl_row][tbl_column]='=';//填表

356

357 if((L==3)&&IsVT(C[0])&&IsVT(C[1])&&(FL_map(C[2])!=-1))358 {//v=E,这种情况

359 int count_1=0;360 chartemp_column;361 tbl_row=SearchTbl(C[1]);//=

362 while(FIRSTVT[FL_map(C[2])][count_1]!='\0')363 {//填写小于关系

364 temp_column=FIRSTVT[FL_map(C[2])][count_1];//映射，仔细体会

365 tbl_column=SearchTbl(temp_column);//将上述结果再次转换

366 PriorityTable[tbl_row][tbl_column]='

367 count_1++;//准备填写下一个

368 }369 count_1=0;//清零

370 }371 if((L==3)&&IsVT(C[0])&&IsVT(C[2])&&(FL_map(C[1])!=-1))372 {//弥补(E)，针对本文法373 //首先填写

374 chartemp_row,temp_column;375 int reg=0;376 tbl_row=SearchTbl(C[0]);377 while(FIRSTVT[FL_map(C[1])][reg]!='\0')378 {//填写小于关系 '('

379 temp_column=FIRSTVT[FL_map(C[1])][reg];380 tbl_column=SearchTbl(temp_column);//皆是映射

381 PriorityTable[tbl_row][tbl_column]='

385 tbl_column=SearchTbl(C[2]);386 while(LASTVT[FL_map(C[1])][reg]!='\0')387 {//填写大于关系 lastVT(E)>')'

388 temp_row=LASTVT[FL_map(C[1])][reg];389 tbl_row=SearchTbl(temp_row);//map

390 PriorityTable[tbl_row][tbl_column]='>';391 reg++;392 }393 reg=0;//reset

394 }395 }396 else if((FL_map(C[0])!=-1)&&IsVT(C[1]))397 {//C[0]肯定为非终结符lastVT(C[0])>C[1]398 //填写大于关系

399 chartemp_row,temp_column;400 int count=0;401 tbl_column=SearchTbl(C[1]);402 while(LASTVT[FL_map(C[0])][count]!='\0')403 {//填写大于关系

404 temp_row=LASTVT[FL_map(C[0])][count];405 tbl_row=SearchTbl(temp_row);//同上

406 PriorityTable[tbl_row][tbl_column]='>';407 count++;408 }409 count=0;410 if(L==3)411 {//在这种情况下C[2]必为非终结符，求C[2]的firstVT(),填写小于关系412 //E+T,E-T,T*F,T/F等情况

413 tbl_row=SearchTbl(C[1]);414 while(FIRSTVT[FL_map(C[2])][count]!='\0')415 {//填写小于关系

416 temp_column=FIRSTVT[FL_map(C[2])][count];417 tbl_column=SearchTbl(temp_column);//map

418 PriorityTable[tbl_row][tbl_column]='

423 }424 }425 }426 else if(INPUT[p][i]!='|'&&INPUT[p][i]!='\0')//该行没结束，过滤'\0'

427 {428 C[j]=INPUT[p][i];//j从0开始

429 j++;//移进

430 }431 if(INPUT[p][i]=='\n')432 {//该行结束

433 break;434 }435 }436 }437 //补上#的关系

438 for(int m1=1;m1<11;m1++)439 {440 PriorityTable[SearchTbl('#')][m1]='

441 }442 for(int m2=1;m2<11;m2++)443 {444 PriorityTable[m2][SearchTbl('#')]='>';//补列

445 }446 PriorityTable[SearchTbl('#')][SearchTbl('#')]='=';447 }448

449 voidDisplayPriorityTable()450 {//显示优先关系表查看是否正确

451 inti,j;452 printf("构造的算符优先关系表如下：\n");453 for(i=0;i<12;i++)454 {455 for(j=0;j<12;j++)456 {457 printf("%c",PriorityTable[i][j]);458 }459 printf("\n");460 }461 }462 /*****************#include "GetPriorityTable.h"*******************/

463

464

465

466 模块三：467

468 /***************#include"Simple_Lexical_Analysis.h"*******************/

469 #include "stdlib.h"

470 #include "string.h"

471 #include "math.h"

472 #include "iostream"

473 using namespacestd;474

475 typedef struct

476 {477 char IDentifier[30];//标识符长度

478 int value;//定义标识符代表的数值

479 }IDentifierTable;480

481 typedef struct

482 {483 int syn;//种别码

484 int value;//数值或者标识符入口指针

485 }SymbolTbl;486 extern char FIRSTVT[20][20];487 extern char LASTVT[20][20];488 extern char PriorityTable[20][20];489 extern char INPUT[20][20];490 extern IDentifierTable idTbl[30];491 extern SymbolTbl symbol[100];//定义符号表

492 /*单词种别码设计：493 = 1494 ？ 2495 + 3496 - 4497 * 5498 / 6499 ( 7500 ) 8501 v 9502 c 10503 clear 11504 # 12505 N 13506 */

507 //此处简单起见，就只考虑标识符，运算符，数字508 //定义一个结构存储(种别码、单词的入口地址)或者(种别码，常数值)或者(种别码)

509 void InsertID(char name[],int entry,intvalue)510 {//插入到标识符表中

511 strcpy(idTbl[entry].IDentifier,name);//插入名字

512 idTbl[entry].value=value;//插入数值

513 }514

515 int ScanEntry(charname[])516 {//查找符号表中是否有空闲位置

517 for(int i=0;i<30;i++)518 {519 if(strcmp(idTbl[i].IDentifier,name)==0)520 {521 return i;//返回入口地址

522 }523 }524 return -1;//失败返回失败码

525 }526

527

528 void Insert_Into_SymbolTbl(int syn,int value,int &pointer)529 {//插入到符号表中

530 symbol[pointer].syn =syn;531 symbol[pointer].value =value;532 pointer++;533 }534

535 bool IsExist(charid[])536 {//查找表中是否已经存在该标识符

537 int i=0;538 for(i=0;i<30;i++)539 {540 if(strcmp(idTbl[i].IDentifier,id)==0)541 {542 return true;543 }544 }545 return false;546 }547

548

549 intSearch_Free_Entity( )550 {//查找表中是否已经存在该标识符

551 int i=0;552 for(i=0;i<30;i++)553 {554 if(strcmp(idTbl[i].IDentifier,"")==0)555 {556 return i;//返回空闲入口

557 }558 }559 return -1;//查找失败

560 }561

562 /*********************判断是否为字母********************/

563 bool IsLetter(charletter)564 {//注意C语言允许下划线也为标识符的一部分可以放在首部或其他地方

565 if (letter >= 'a'&&letter <= 'z' || letter >= 'A'&&letter <= 'Z' || letter=='_')566 {567 return true;568 }569 else

570 {571 return false;572 }573 }574 /*********************判断是否为字母********************/

575

576

577 /*****************判断是否为数字************************/

578 bool IsDigit(chardigit)579 {580 if (digit >= '0'&&digit <= '9')581 {582 return true;583 }584 else

585 {586 return false;587 }588 }589 /*****************判断是否为数字************************/

590

591 void Scanner(char sentence[],char name[],int &syn,int &scan_point,int &value)592 {593 char token[30],ch;594 int p_token=0;//token的指针

595 int digit_value=0;//记录常数的大小

596 for(int n=0;n<30;n++)597 {598 token[n]='\0';//对字符数组清零

599 }600 ch=sentence[scan_point]; //读入一个字符

601 if(ch=='#'&&scan_point==0)602 {//该字符的种别码已经在主程序中登记了

603 scan_point++;//刚开始的第一个字符一定为‘#’

604 ch=sentence[scan_point];//指针下移，扫描下一字符

605 }606 if(IsLetter(ch)) //ch是否为字母

607 {608 while(IsLetter(ch)||IsDigit(ch)) //ch是否为字母或数字

609 {610 token[p_token++]=ch;611 scan_point++;612 ch=sentence[scan_point]; //读入一个字符

613 }614 token[p_token]='\0';615 syn=9;//代表找到了标识符

616 if(strcmp(token,"clear")==0)617 {//代表找到了保留字“clear”

618 syn=11;619 }620 strcpy(name,token);//带回标识符

621 }622 else if(IsDigit(ch)) //ch是否为数字

623 {624 digit_value=0;625 while(IsDigit(ch))626 { //此处假设只是整数

627 digit_value=digit_value*10+ch-'0';628 scan_point++;629 ch=sentence[scan_point]; //读入一个字符

630 }631 value=digit_value;//带回整数值

632 syn=10;633 }634 else

635 {636 switch(ch)637 {638 case'=':syn=1; break;639 case'?':syn=2; break;640 case'+':syn=3; break;641 case'-':syn=4; break;642 case'*':syn=5; break;643 case'/':syn=6; break;644 case'(':syn=7; break;645 case')':syn=8; break;646 case'#':syn=12; break;647 default:printf("输入句子有误！\n");exit(0);break;648 }649 scan_point++;//保持指针始终指向待判断的字符

650 ch=sentence[scan_point]; //读入一个字符

651 }652 }653 bool Check_Is_Right(charsentence[])654 {//检查句子是不是#。。。#的形式

655 int len=strlen(sentence)-1;656

657 if(sentence[0]=='#'&&sentence[len]=='#')658 {//&&sentence[strlen[sentence]-1]=='#'

659 return true;660 }661 return false;662 }663 voidLexicalAnalysisCtl()664 {//主控程序

665 char sentence[100]="\0";666 int syn=-1;667 char name[30]="";668 intvalue;669 int scan_point=0;//从开始处扫描

670 int id_pointer;//定义标识符表入口指针

671 int sym_pointer=0,entry;672 do

673 {674 printf("请输入句子,以#开始并且以#结束\n");675 scanf("%s",sentence);676 }while(!Check_Is_Right(sentence));677 Insert_Into_SymbolTbl(12,-1,sym_pointer);678 printf("(%d , )\n",12);679 while(syn!=12)680 {//直到扫描到第二个‘#’为止

681 Scanner(sentence,name,syn,scan_point,value);682 switch(syn)683 {//若是单词

684 case 9:printf("(%d , %s)\n",syn,name);685 //登记到表中

686 if(!IsExist(name))687 {//不存在则插入688 //查找可插入位置

689 id_pointer=Search_Free_Entity();690 InsertID(name,id_pointer,-1);//-1代表还没被赋值

691 }692 //搜索该标识符的入口地址放入value中

693 entry=ScanEntry(name);694 Insert_Into_SymbolTbl(syn,entry,sym_pointer);695 break;696 case 10://常数

697 Insert_Into_SymbolTbl(syn,value,sym_pointer);698 printf("(%d , %d)\n",syn,value);699 break;700 default:printf("(%d , )\n",syn);701 Insert_Into_SymbolTbl(syn,-1,sym_pointer);//-1代表该处不需要值

702 }703 }704 printf("--------------------词法分析正确！！！-------------------------\n");705 //打印出符号表和标识符表

706 printf("标识符的入口地址 标识符 标识符的值(-1代表没被赋值)\n");707 for(int m1=0;m1<30;m1++)708 {//标识符表

709 if(!(strcmp(idTbl[m1].IDentifier,"")==0))710 {711 printf("\t%d %s %d\n",m1,idTbl[m1].IDentifier,idTbl[m1].value);712 }713 }714 printf("符号表的入口地址 种别码 具体的值(或标识符入口)\n");715 for(int m2=0;m2

717 printf("\t%d %d %d\n",m2,symbol[m2].syn ,symbol[m2].value);718 }719 printf("---------------------------------------------------------------\n");720 }721

722

723 voidClear_Symbol_Tbl()724 {725 //将符号表的syn全部设置为0

726 for(int i=0;i<100;i++)727 {728 symbol[i].syn=0;//代表没定义

729 symbol[i].value=-1;//指定为-1

730 }731 }732

733

734 voidClear_IDentifier_Tbl()735 {//清空标识符表

736 for(int i=0;i<30;i++)737 {738 strcpy(idTbl[i].IDentifier,"");739 idTbl[i].value=-1;740 }741 }742 /*************#include"Simple_Lexical_Analysis.h"****************/

743

744

745 模块四：746

747 /***********#include "MainProc_Analysis.h"********************/

748

749 #include"iostream"

750 using namespacestd;751

752 extern char FIRSTVT[20][20];753 extern char LASTVT[20][20];754 extern char PriorityTable[20][20];755 extern char INPUT[20][20];756 extern IDentifierTable idTbl[30];//定义全局标识符表

757 extern SymbolTbl symbol[100];//定义符号表

758 extern char SymbolTbl_Define[15];759

760 //创建堆栈，准备对数据进行处理

761 #define MAXSIZE 300

762 //创建模板栈

763 template

764 classStack{765 public:766 Stack(){top=-1;}//构造函数，进行初始化操作

767 ~Stack(){}//析构函数

768 boolIsEmpty(){769 if(top==-1)770 return true;771 else

772 return false;773 }//判断栈是否为空774

775 //返回栈顶元素

776 T gettop()777 {778 returna[top];779 }780 //得到栈顶指针的数值

781 intgetTopPointer()782 {783 returntop;784 }785 //定义遍历整个栈的能力

786 T traverseStack(intpointer)787 {788 //若pointer<0则报错

789 if(pointer<0)790 {791 cout<

793 }794 if(pointer>top)795 {796 cout<

798 }799 return a[pointer];//返回元素值

800 }801 //将元素压栈

802 voidpush(T num)803 {804 if(top>=MAXSIZE)805 return;806 a[++top]=num;807 }808 //将元素弹出栈

809 T pop()810 {811 if(top==-1)812 {813 cout<

820 top=-1;821 }822 private:823 T a[MAXSIZE];824 inttop;825 };826 /*单词种别码设计：827 = 1828 ？ 2829 + 3830 - 4831 * 5832 / 6833 ( 7834 ) 8835 v 9836 c 10837 clear 11838 # 12839 N 13840 */

841 //char SymbolTbl_Define[15]={'=','\?','+','-','*','/','(',')','v','c','l','#','N','\0'};

842

843

844 /********经过以下连个函数就可以知道种别码对应的字符在符号表中的位置************/

845 char SearchSyn(intsyn)846 {//根据种别码返回相应字符

847 return SymbolTbl_Define[syn-1];848 }849 char Prior_Position[13]={'+','-','*','/','(',')','v','c','=','?','#','\0'};850 int Search_Priority_Setxy(charch)851 {//搜索一个字符在优先符表中的位置

852 for(int i=0;i<11;i++)853 {854 if(ch==Prior_Position[i])855 {856 return i+1;//返回该位置

857 }858 }859 return -1;//失败则提示错误

860 }861 /*******************************************************************/

862 Stack Reource_Symbol;//定义堆栈

863 void Print_Context(int Stack_Top,intSym_Pointer)864 {//打印出当前堆栈和符号表的上下文

865 intsyn,value,sym_length;866 cout<

870 syn=Reource_Symbol.traverseStack(i).syn;871 value=Reource_Symbol.traverseStack(i).value;872 cout<

878 sym_length=i+1;//长度，最后一个为#，从1开始数

879 for(int j=Sym_Pointer;j

881 syn=symbol[j].syn;882 value=symbol[j].value;883 cout<

892

893 cout<

896 char Prior_Relation;//优先关系

897 int sym_length;//符号表长度

898 int pStackTop;//栈顶指针

899 int pScanStack;//定义扫描堆栈指针

900 int Statement_count=0;//记录步骤序号901

902 //现在的算法是1.初始化栈，在栈中放入#(12，),然后开始分析

903 SymbolTbl temp_sym;904 temp_sym.syn=12;905 temp_sym.value=-1;//-1代表这个地方不需要

906 Reource_Symbol.push(temp_sym);//将#压栈907

908 //对symbol中的内容定义指针，并且略过第一个#

909 int Sym_scan_pointer=1;//从一开始

910 for(i=1;symbol[i].syn!=12;i++)911 ;//计算符号表的长度i

912 sym_length=i+1;//长度，最后一个为#，从1开始数913 //判断符号表第一个元素的syn==11?即是否为clear

914 if(sym_length>=3&&(symbol[1].syn==11))915 {//清除语句，清除屏幕并且清空标号表中的值

916 Clear_IDentifier_Tbl();917 Clear_Symbol_Tbl();918 Reource_Symbol.Clear_Stack();919 system("cls");920 gotoend;921 }922 //下面比较栈中元素和符号表中元素的大小关系

923 pStackTop=Reource_Symbol.getTopPointer();924 pScanStack=pStackTop;//扫描指针从栈顶开始

925 Print_Context(Reource_Symbol.getTopPointer(),Sym_scan_pointer);926 while(1)927 {928 row_prior=Search_Priority_Setxy(SearchSyn(Reource_Symbol.traverseStack(pScanStack).syn));//栈扫描指针

929 column_prior=Search_Priority_Setxy(SearchSyn(symbol[Sym_scan_pointer].syn));//符号表扫描指针

930 Prior_Relation=PriorityTable[row_prior][column_prior];931 if(Prior_Relation=='

934 Reource_Symbol.push(symbol[Sym_scan_pointer]);//栈顶++935 //扫描指针后移，不能回头

936 Sym_scan_pointer++;937 //注意此时还要改变堆栈指针的值，让我调试了好久。。。

938 pStackTop=Reource_Symbol.getTopPointer();//得到变动后的栈顶指针，始终指向栈顶

939 pScanStack=pStackTop;//进行下一次判断，此时扫描指针指向新移进来的元素

940 cout<

946 intfinal_value;947 if(Reource_Symbol.gettop().syn==13&&(Reource_Symbol.getTopPointer()==1))948 {//若满足#N的情况，则归约成功！

949 cout<

955 }956 else

957 {958 cout<')963 {//注意下面两句话要放在循环之前!!!

964 pStackTop=Reource_Symbol.getTopPointer();//得到栈顶指针

965 pScanStack=pStackTop;//扫描指针从栈顶开始

966 while(Prior_Relation=='>')967 { //若优先关系始终为大于，则堆栈指针前移，不断寻找可归约串968 //因为可归约串始终在栈顶的某段区域，那么就要试探着先看一下栈顶元素是不是969 //若栈顶元素可归约则直接归约为N(13,),否则查看栈顶方向的两个元素同样道理970 //因为文法的产生式右部最多只有三个元素，因此若是到了三个元素还没有搜索到971 //可归约串，则视为语法错误，停止分析972 //此处构建两个指针，一个既是栈顶指针，另一个为扫描可归约串的指针973

974

975 //这里不可能出现'('976

977 //判断栈顶元素是否可归约

978 intjudge;979 judge=Reource_Symbol.traverseStack(pScanStack).syn;//判断该种别码980 //若是单个变量或常量则规约为N981 //此处还要进行语义分析，对于标识符要查标识符表判断是否存在，若不存在则为错

982 if(judge==9)983 {984 if(idTbl[Reource_Symbol.traverseStack(pScanStack).value].value==-1)985 {986 cout<

990 cout<

994 {//否则将该标识符规约为N

995 temp_sym.syn=13;996 //获得符号表中关于该变量的值

997 temp_sym.value=idTbl[Reource_Symbol.traverseStack(pScanStack).value].value;998 Reource_Symbol.pop();//先弹出栈顶元素

999 Reource_Symbol.push(temp_sym);//将N压栈

1000 pStackTop=Reource_Symbol.getTopPointer();//得到变动后的栈顶指针，始终指向栈顶1001 //扫描指针要前移，因为要分析终结符，而栈顶已变成非终结符

1002 pScanStack=Reource_Symbol.getTopPointer()-1;//进行下一次判断

1003 if(pScanStack<0)1004 {1005 cout<

1010 cout<

1016 temp_sym.syn=13;1017 temp_sym.value=Reource_Symbol.traverseStack(pScanStack).value;1018 Reource_Symbol.pop();//先弹出栈顶元素

1019 Reource_Symbol.push(temp_sym);//将N压栈

1020 pStackTop=Reource_Symbol.getTopPointer();1021 pScanStack=Reource_Symbol.getTopPointer()-1;//进行下一次判断

1022 if(pScanStack<0)1023 {1024 cout<

1029 cout<

1034 if(Reource_Symbol.traverseStack(pScanStack-1).syn==9)//一定为9

1035 {//若前面为标识符则正确，应该为该变量赋值1036 //语义分析

1037 idTbl[Reource_Symbol.traverseStack(pScanStack-1).value].value=Reource_Symbol.gettop().value;//此时栈顶必为E

1038 temp_sym.syn=13;1039 temp_sym.value=Reource_Symbol.gettop().value; //N中的值永远为真正的值，而不是地址1040 //开始归约

1041 Reource_Symbol.pop();1042 Reource_Symbol.pop();1043 Reource_Symbol.pop();//弹出三个元素

1044 Reource_Symbol.push(temp_sym);//规约为N

1045 pStackTop=Reource_Symbol.getTopPointer();1046 pScanStack= Reource_Symbol.getTopPointer()-1;//始终指向规约后的第一个非终结符

1047 if(pScanStack<0)1048 {1049 cout<

1054 cout<

1058 {1059 cout<

1063 else if(judge==3)1064 {//+，此时栈顶应该为N+N的形式1065 //只需把两个数相加，并且把结果放在N中即可

1066 if(Reource_Symbol.traverseStack(pScanStack-1).syn==13&&Reource_Symbol.traverseStack(pScanStack+1).syn==13)//一定为13

1067 {//若前面为N并且栈顶为N则正确1068 //语义分析,newtemp()

1069 temp_sym.syn=13;1070 temp_sym.value=Reource_Symbol.traverseStack(pScanStack-1).value+Reource_Symbol.traverseStack(pScanStack+1).value; //N中的值永远为真正的值，而不是地址1071 //开始归约

1072 Reource_Symbol.pop();1073 Reource_Symbol.pop();1074 Reource_Symbol.pop();//弹出三个元素

1075 Reource_Symbol.push(temp_sym);//规约为N

1076 pStackTop=Reource_Symbol.getTopPointer();1077 pScanStack= Reource_Symbol.getTopPointer()-1;//始终指向规约后的第一个非终结符

1078 if(pScanStack<0)1079 {1080 cout<

1085 cout<

1089 {1090 cout<

1096 if(Reource_Symbol.traverseStack(pScanStack-1).syn==13&&Reource_Symbol.traverseStack(pScanStack+1).syn==13)//一定为13

1097 {//若前面为N并且栈顶为N则正确 N-N1098 //语义分析,newtemp()

1099 temp_sym.syn=13;1100 //注意运算的顺序

1101 temp_sym.value=Reource_Symbol.traverseStack(pScanStack-1).value-Reource_Symbol.traverseStack(pScanStack+1).value; //N中的值永远为真正的值，而不是地址1102 //开始归约

1103 Reource_Symbol.pop();1104 Reource_Symbol.pop();1105 Reource_Symbol.pop();//弹出三个元素

1106 Reource_Symbol.push(temp_sym);//规约为N

1107 pStackTop=Reource_Symbol.getTopPointer();1108 pScanStack= Reource_Symbol.getTopPointer()-1;//始终指向规约后的第一个非终结符

1109 if(pScanStack<0)1110 {1111 cout<

1116 cout<

1120 {1121 cout<

1127 if(Reource_Symbol.traverseStack(pScanStack-1).syn==13&&Reource_Symbol.traverseStack(pScanStack+1).syn==13)//一定为13

1128 {//若前面为N并且栈顶为N则正确 N*N1129 //语义分析,newtemp()

1130 temp_sym.syn=13;1131 //注意运算的顺序

1132 temp_sym.value=Reource_Symbol.traverseStack(pScanStack-1).value*Reource_Symbol.traverseStack(pScanStack+1).value; //N中的值永远为真正的值，而不是地址1133 //开始归约

1134 Reource_Symbol.pop();1135 Reource_Symbol.pop();1136 Reource_Symbol.pop();//弹出三个元素

1137 Reource_Symbol.push(temp_sym);//规约为N

1138 pStackTop=Reource_Symbol.getTopPointer();1139 pScanStack= Reource_Symbol.getTopPointer()-1;//始终指向规约后的第一个非终结符

1140 if(pScanStack<0)1141 {1142 cout<

1147 cout<

1151 {1152 cout<

1158 if(Reource_Symbol.traverseStack(pScanStack-1).syn==13&&Reource_Symbol.traverseStack(pScanStack+1).syn==13)//一定为13

1159 {//若前面为N并且栈顶为N则正确 N*N1160 //语义分析,newtemp()

1161 temp_sym.syn=13;1162 //注意运算的顺序

1163 temp_sym.value=Reource_Symbol.traverseStack(pScanStack-1).value / Reource_Symbol.traverseStack(pScanStack+1).value; //N中的值永远为真正的值，而不是地址1164 //开始归约

1165 Reource_Symbol.pop();1166 Reource_Symbol.pop();1167 Reource_Symbol.pop();//弹出三个元素

1168 Reource_Symbol.push(temp_sym);//规约为N

1169 pStackTop=Reource_Symbol.getTopPointer();1170 pScanStack= Reource_Symbol.getTopPointer()-1;//始终指向规约后的第一个非终结符

1171 if(pScanStack<0)1172 {1173 cout<

1178 cout<

1182 {1183 cout<

1190 if(Reource_Symbol.traverseStack(pScanStack-1).syn==13&&Reource_Symbol.traverseStack(pScanStack-2).syn==7)1191 {//若前面为(N 则正确1192 //语义分析,newtemp()

1193 temp_sym.syn=13;1194 //N

1195 temp_sym.value=Reource_Symbol.traverseStack(pScanStack-1).value; //N中的值永远为真正的值，而不是地址1196 //开始归约

1197 Reource_Symbol.pop();1198 Reource_Symbol.pop();1199 Reource_Symbol.pop();//弹出三个元素

1200 Reource_Symbol.push(temp_sym);//规约为N

1201 pStackTop=Reource_Symbol.getTopPointer();1202 pScanStack= Reource_Symbol.getTopPointer()-1;//始终指向规约后的第一个非终结符

1203 if(pScanStack<0)1204 {1205 cout<

1210 cout<

1214 {1215 cout<

1221 if(Reource_Symbol.traverseStack(pScanStack-1).syn==13)1222 {1223 //语义分析,newtemp()

1224 temp_sym.syn=13;1225 temp_sym.value=Reource_Symbol.traverseStack(pScanStack-1).value;1226 //开始归约

1227 Reource_Symbol.pop();1228 Reource_Symbol.pop();//弹出2个元素

1229 Reource_Symbol.push(temp_sym);//规约为N

1230 pStackTop=Reource_Symbol.getTopPointer();1231 pScanStack= Reource_Symbol.getTopPointer()-1;//始终指向规约后的第一个非终结符

1232 if(pScanStack<0)1233 {1234 cout<

1239 cout<

1243 {1244 cout<

1249 {1250 cout<')

1254 }//end else if(Prior_Relation=='>')

1255 }//end while(1)

1256 end: ;1257 }//end

1258

1259 /*单词种别码设计：1260 = 11261 ？ 21262 + 31263 - 41264 * 51265 / 61266 ( 71267 ) 81268 v 91269 c 101270 clear 111271 # 121272 N 131273 */

1274

1275 /**********#include "MainProc_Analysis.h"*****************/

1276

1277

1278

1279

1280

1281 主程序：1282 #include "stdio.h"

1283 #include "firstVT_lastVT.h"//计算firstVT()和LastVT()的程序

1284 #include "GetPriorityTable.h"//创建算符优先关系表的程序

1285 #include "Simple_Lexical_Analysis.h"//词法分析的程序

1286 #include "MainProc_Analysis.h" //主分析程序，用来进行语法和语义分析

1287 /*注意此处l是clear的缩写，简略标记，因为在后续算符优先分析中它和其他任何非终结符(除#外)没任何关系，故分别对待1288 S-->v=E|E?|l1289 E-->E+T|E-T|T1290 T-->T*F|T/F|F1291 F-->(E)|v|c1292 10个终结符，需要构造priorTable[12][12]大小的表1293 + - * / ( ) v c = ? # 外加一个结束符#1294 */

1295

1296 //设置为全局变量，则字符串开始时被全部初始化为'\0'1297 //用于存储FIRSTVT集

1298 char FIRSTVT[20][20];1299 char LASTVT[20][20];1300 char PriorityTable[20][20];//优先符表

1301 char INPUT[20][20]; //文法记录表

1302 IDentifierTable idTbl[30];//定义全局标识符表

1303 SymbolTbl symbol[100];//定义符号表，记录输入的程序片段

1304 char SymbolTbl_Define[15]={'=','\?','+','-','*','/','(',')','v','c','l','#','N','\0'};//定义各个终结符的syn

1305

1306 intmain()1307 {1308 char ch;//是否继续的标记1309 //计算并显示firstVT()和LastVT()

1310 DisplayFirstVT_LasVT();1311 //创建算符优先关系表

1312 createPriorityTable();1313 //打印算符优先关系表

1314 DisplayPriorityTable();1315 //cout<

1316 while(1)1317 {1318 //首先要清空符号表，这样才能进行下一轮分析

1319 Clear_Symbol_Tbl();1320 //词法分析，登记符号表

1321 LexicalAnalysisCtl();1322 //语法语义分析，产生运行结果

1323 MainProc_Analysis();1324 cout<>ch;1326 if(!(ch=='y')&&!(ch=='Y'))1327 {1328 cout<