算符优先分析文法
一、写在前面
算符优先分析文法是一种工具，在编译的过程中，隶属于语法分析环节，却又与中间代码的生成息息相关，编译可以分为五个阶段：词法分析、语法分析、语义分析（中间代码的生成）、代码优化、目标代码生成。语法分析是指：在词法分析基础上，将单词符号串转化为语法单位（语法范畴）（短语、子句、句子、程序段、程序），并确定整个输入串是否构成语法上正确的程序。也就是说语法分析是检验输入串的语法是否正确，注意这里的语法正确，只是简单地符合自己定义的规范，而不能检测出运行时错误，比如"X/0"，空指针错误，对象未初始化等错误。在这一个实验中，我将通过算符优先分析文法这一个工具，在语法分析的时候，顺便进行语义分析，也就是识别出语法单位，同时简要的将识别出的中间代码进行计算（目标代码的生成+运行），得到相应的结果，来检验自己设计的正确性。可以说题目虽然叫做算符优先分析文法，其实却是一个贯穿了“词法分析+语法分析+语义分析+中间代码优化+目标代码生成+运行”全过程的一个极具概括性的程序。如果能将这个程序得心应手的完成出来，我相信诸位对编译原理的掌握也算是炉火纯青了。时隔将近两年再来整理自己以前写过的实验报告，还是挺有感慨的，对一件东西感兴趣，原来影响还会如此深远，还记得自己当时连续六个小时全神贯注写出的实验报告，现在看看竟然写了五六十页，核心内容也有三四十页，不觉的感慨当年充满热情的时代慢慢的竟走出许久~~
二、算符优先分析文法实验
2.1、任务 实验目的： 1.了解掌握算符优先分析的基本方法、内容； 2.学会科学思考并解决问题，提高程序设计能力。 实验内容与要求： 用算符优先分析方法设计一个分析解释程序，对输入的赋值语句、输出语句、清除语句进行词法分析、语法分析、表达式求值并存储于指定变量中；若存在错误，提示错误相关信息。 文法表示： S→v=E|E?|clear E→E+T|E-T|T T→T*F|T/F|F F→ (E)|v|c 单词种别码设计： = 1 ？ 2 + 3 - 4 * 5 / 6 （ 7 ） 8 v 9 c 10 clear 11 # 12 N 13 可归约串语义解释： 变量归约；常量归约；运算归约；括号归约； 赋值语句；输出语句;清除语句。 演示示例： a=5 b=a+10 b? b+a*a? a=a+b
2.2、分析与设计
首先，这是一个很好的题目，从知识的理解、将形式化的东西转化成具体的过程、编程能力、编程技巧、调试改错能力等多个方面考察了我们的学习情况。 算符优先文法是一种自下而上的文法分析方法，这种方法的用处十分广泛，虽然有的文法不能用算符优先分析文法，如类似…PQ…..（P，Q为非终结符）这样形式的产生式，但是对于大部分文法这种分析方法还是十分有用的。 其次，对于本程序中的文法，实质上是算数表达式的计算。用这种文法就是再好不过了，作为从算符文法抽象出来的算符优先文法当然继承了算符文法的特性。下面就切入正题了，我将详细介绍一下我对于这个文法的思考出发点和分层分析的方法。
模块一：构建firstVT()和lastVT()这两个集合
基于“优先”这两个字，有效的回避了左递归（自上而下文法分析）和二义性的问题。关键是如何体现“优先”这两个字。这就需要firstVT()和lastVT()集合了。firstVT(E)={a|E→a…..|E→Qa….|firstVT(Q)},从这个定义可以看到，firstVT()主要找到是本产生式中的第一个非终结符和若第一个是非终结符则包含该非终结符的firstVT()集，因为firstVT有可能要求Q的firstVT()集，因此有可能要用递归才能求尽所有的firstVT()集。同理，lastVT(E)={a|E→….a|E→…….aQ},可见这两个关系好像反对称的影像。说了这么多，还是没有说到这两个集合要干什么用。让我们想象一个句型…aQ….. 在这个句型中我们知道只有等Q的短语规约为Q了，才有可能将…aQ….再次向上规约，因此a的优先级要小于Q产生式的firstVT(Q)集，因为我们可以断定a必定是比Q中第一个出现的终结符优先级低的，也就是说优先级a<优先级firstVT(Q)，至于第二个，第三个终结符。。。我们不敢判定。于是才要费尽心思地构造firstVT()这样的一个集合。同理，对于lastVT()，让我们想一下这种情况…..Qa…..,对于这个句型我们知道只有当Q的短语归约成了Q，我们才敢将….Qa……向上归约。这样的话就是说Q的产生式中最后出现的一个终结符的优先级必定是比a的优先级高的，也就是优先级lastVT(Q)>优先级a，同样的对于倒数第二个，倒数第三个终结符。。。我们不敢判定。说了这么多我想应该能够理解这两个集合存在的必要性和决定性了。
因为是程序，我就说一下程序如何实现这两个集合的求解。 首先是一些数据结构和意义： char FIRSTVT[20][20]; 存储firstVT()集，第二维代表第几个产生式，第一维代表集合中的第几个元素 char LASTVT[20][20]; 存储lastVT()集，第二维代表第几个产生式，第一维代表集合中的第几个元素 char INPUT[20][20]; 按照一定的形式存储文法中的所有产生式。 然后是几个函数： 1. void setFIRSTVT(char X,int T)； 这个函数的目的是将求出的终结符X，存放到第T条产生式的左部对应的firstVT集合中。 2. void getFIRSTVT(char X,int S) S标记产生式的位置，X为将要计算的产生式的左部。这个函数就比较复杂了，它将完成求出一个产生式左部的firstVT的终结符的重要任务，可以说是主控程序了。它的算法是逐个遍历产生式，对每个产生式求出该产生式的直接a,并且若有E→Qa…还要递归的求出Q的firstVT()将其并入firstVT(E)的集合中。 3. 同理void setLASTVT(char X,int T) 4. void getLASTVT(char X,int S)和上面类似。 5. void DisplayFirstVT_LasVT() 这个函数也是主程序开始时要进入的位置。它主要提示用户输入文法（产生式组），然后调用上面的函数计算并显示两种集合。 下面是void getFIRSTVT(char X,int S)的函数。
1 //找出FIRSTVT集元素 2 void getFIRSTVT(char X,int S) 3 { 4 int i,j=0,k;//j当前数组指针 5 int T=0;//X position 6 int L=0;//X offspring length 7 char C[20]; 8 9 for(i=0;i<20;i++)10 {11 if(INPUT[i][0]==X)//找到将要处理的产生式12 {13 T=i; //标记产生式的位置14 break;15 }16 }17 //按照规则从产生式的右部第一个字符开始处理，直至遇上'/n'18 //每一次都判断指针j指向的字符若满足p-->w中w的规定则放进C[]19 //若遇上‘|’或'\n'则求这段右部对应的firstVT()20 for(i=4;i<20;i++)21 {22 if(INPUT[T][i]=='|'||INPUT[T][i]=='\n')23 { //刚开始走不到这里24 L=j;//j指针所指位置为C[]中字符串的长度25 j=0;//交给L后就清零，以供下一次使用26 for(k=0;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]=='=')34 { //只能用一次,因是算符优先文法，故前两个中必会至少存在一个终结符35 setFIRSTVT(C[k],S);//存入FIRSTVT中，S标记产生式的位置36 break;//跳出循环保证存入的是最左边的终结符37 }38 }39 if(C[0]>=65&&C[0]<=90&&C[0]!=X)40 { //若C[0]中为A~Z,并且C[0]不是X(否则将无限循环)，则递归的进行填充41 int flag=0,count;42 for(count=0;count<20;count++)43 {44 if(INPUT[count][0]==C[0])//找到将要处理的产生式45 {46 flag=1;//若存在，则填充47 }48 }49 if(flag==1)50 { //递归，所用极妙，画龙点睛51 getFIRSTVT(C[0],S);//S为子集中的元素填入父集中指明了方向52 }53 }54 }55 else if(INPUT[T][i]!='|'&&INPUT[T][i]!='\0')//该行没结束，过滤'\0'56 {57 C[j]=INPUT[T][i];//j从0开始58 j++;//移进59 }60 if(INPUT[T][i]=='\n')61 { //该行结束62 break;63 }64 } 65 } 比如说对于这个文法分析出的集合如下：
模块二：构建优先符号表
为了体现“优先”的关系，只是构建出了上面的两种集合是不够的，由上面分析我们知道了这两个集合的用处。说白了就是为了构造出算符优先分析表。因为关系无非四类1.等于，2.大于，3.小于，4没有关系。注意这里的“没有关系”也是一种关系。 而由第一个阶段产生的两个集合就可以找到所有的大于和小于关系，那就只剩下了等于关系，如果等于关系找到了，剩余的没有填写的关系就是没有关系。等于关系是这样的：如果存在这样的句型.....ab....或.......aQb.....则关系(a==b)。这样的结果也是显而易见的，因为a和b注定要共同归约，没有谁先谁后，因此是等于关系。 好了现在所有关系都搞请了，就可以建表了。 还是首先解释一下新定义的一个数据结构: char PriorityTable[20][20]; 优先关系表，其中存放着终结符以及终结符对应的关系。 然后是一些函数： 1.int IsVT(char ch) 判断ch是否为终结符，若是则返回1，否则返回0 2.int SearchTbl(char ch) 搜索终结符ch在符号表中的行列数，用来定位将要填写的位置。 3.int FL_map(char ch) 这个映射既是查找产生式左部的位置，若存在则返回该产生式的条数，即是第几个产生式，失败则返回-1这个出错标记。 4.void createPriorityTable() 这个是建表的主控程序，用来填写所有关系与表中。遍历所有的产生式，填写所有的关系。这里主要解释一下程序是如何找到横纵坐标并且将关系填写进去的。对于简单的情况只要拿一个终结符来使用SearchTbl(终结符)就可以找到横（纵）坐标了，但是因为对于大小关系我们往往要填的是“终结符<firstVT()”或“lastVT()>终结符”这样的情况，因此势必要从集合中取出终结符，并用该终结符来映射坐标，即是用到了类似这样的转换： temp_column=FIRSTVT[FL_map(C[2])][count_1]; tbl_column=SearchTbl(temp_column);//将上述结果再次转换 或者temp_row=LASTVT[FL_map(C[1])][reg]; tbl_row=SearchTbl(temp_row);//map 这样的映射。知道了这些程序不难读懂。 5.void DisplayPriorityTable() 这个函数就是显示优先关系表的内容的。 下面是 void createPriorityTable() 函数的实现过程： 1 void createPriorityTable() 2 { //创建并填写优先级表 3 //对每个产生式遍历，求出四种关系1.=,2.<,3.>,4.没有关系 4 char temp[13]={ '+','-','*','/','(',')','v','c','=','?','#','\0'}; 5 int j,L,i; 6 int tbl_row,tbl_column;//表的元素坐标 7 char C[20]; 8 for(int r=1;r<12;r++) 9 { 10 PriorityTable[0][r]=temp[r-1];//初始化行头，第0行 11 PriorityTable[r][0]=temp[r-1];//初始化第0列 12 } 13 //扫描产生式的右部，如果发现终结符且该终结符周围有其他字符 14 //若该其他字符为终结符，则这两者关系为相等 15 //若该其他字符为非终结符，则根据非终结符的firstVT,LastVt填表 16 for(int p=0;p<4;p++) 17 { 18 j=0; 19 for(i=4;i<20;i++) 20 { //注意，此处因为时间有限考虑不是很全面，只是对老师给定的文法进行了周密的部署 21 //在别的文法上可能需要少许加工，不是问题 22 if(INPUT[p][i]=='|'||INPUT[p][i]=='\n') 23 { //刚开始走不到这里 24 L=j;//j指针所指位置为C[]中字符串的长度 25 j=0;//交给L后就清零，以供下一次使用 26 if(L>1)//大于一则处理，否则不关心 27 { //对于清零指令l自动忽略 28 if(IsVT(C[0])&&IsVT(C[1])||(L==3)&&IsVT(C[0])&&IsVT(C[2])&&(FL_map(C[1])!=-1)) 29 { //若为终结符因至少有两个,若出现两个终结符则C[0]'=='C[1]||C[2]，注意这是此文法的情况 30 //则需要填表，查表找到C[0]的行数，C[1],C[2]的列数进行填表 31 tbl_row=SearchTbl(C[0]);//记录行数 32 if(IsVT(C[1])) 33 { //列数，若是终结符 v= 34 tbl_column=SearchTbl(C[1]); 35 } 36 if(IsVT(C[2])&&(L==3)) 37 { //列数 (E) 38 tbl_column=SearchTbl(C[2]); 39 } 40 PriorityTable[tbl_row][tbl_column]='=';//填表 41 42 if((L==3)&&IsVT(C[0])&&IsVT(C[1])&&(FL_map(C[2])!=-1)) 43 { //v=E,这种情况 44 int count_1=0; 45 char temp_column; 46 tbl_row=SearchTbl(C[1]);// = ')' 73 temp_row=LASTVT[FL_map(C[1])][reg]; 74 tbl_row=SearchTbl(temp_row);//map 75 PriorityTable[tbl_row][tbl_column]='>'; 76 reg++; 77 } 78 reg=0;//reset 79 } 80 } 81 else if((FL_map(C[0])!=-1)&&IsVT(C[1])) 82 { //C[0]肯定为非终结符lastVT(C[0])>C[1] 83 //填写大于关系 84 char temp_row,temp_column; 85 int count=0; 86 tbl_column=SearchTbl(C[1]); 87 while(LASTVT[FL_map(C[0])][count]!='\0') 88 { //填写大于关系 89 temp_row=LASTVT[FL_map(C[0])][count]; 90 tbl_row=SearchTbl(temp_row);//同上 91 PriorityTable[tbl_row][tbl_column]='>'; 92 count++; 93 } 94 count=0; 95 if(L==3) 96 { //在这种情况下C[2]必为非终结符，求C[2]的firstVT(),填写小于关系 97 //E+T,E-T,T*F,T/F等情况 98 tbl_row=SearchTbl(C[1]); 99 while(FIRSTVT[FL_map(C[2])][count]!='\0')100 { //填写小于关系101 temp_column=FIRSTVT[FL_map(C[2])][count];102 tbl_column=SearchTbl(temp_column);//map103 PriorityTable[tbl_row][tbl_column]='<';104 count++;105 }106 count=0;107 }//end if108 }109 }110 }111 else if(INPUT[p][i]!='|'&&INPUT[p][i]!='\0')//该行没结束，过滤'\0'112 {113 C[j]=INPUT[p][i];//j从0开始114 j++;//移进115 }116 if(INPUT[p][i]=='\n')117 { //该行结束118 break;119 }120 }121 }122 //补上#的关系123 for(int m1=1;m1<11;m1++)124 {125 PriorityTable[SearchTbl('#')][m1]='<';//这个容易理解，补行126 }127 for(int m2=1;m2<11;m2++)128 {129 PriorityTable[m2][SearchTbl('#')]='>';//补列130 }131 PriorityTable[SearchTbl('#')][SearchTbl('#')]='=';132 } 比如说对于这个文法分析出来的优先关系表如下：
模块三：构建词法分析的程序
做好了上面两步运算已经累得不行了，下面还要继续进行分析，那就是词法分析程序，多亏这个程序在实验一已经完成过，这里就拿出那里的代码进行必要的改进和删除，保留适合本文法要求的部分即可。其实想来无非是用到了识别标识符、识别常数、识别+、-、*、/、？、#、（、）、保留字clear等符号的算法罢了。还是比较好写的。但考虑到后面的运算，也就是最精彩的部分a=3;b=a+3;这样的句子，我们不得不在进行词法分析的时候将这些标识符登记到标识符表中，将句子打碎成二元组存放到符号表中。注意这里的符号表没有什么其他意义，就是存放将句子解释成的有序序列罢了。综上所述，词法分析这一过程就是识别字符串，若正确则填表，若错误，则报错。两个任务：填表、报错。由此也可以看到表格处理和错误处理在整个编译过程中无处不在。这里新增了一些数据结构和全局变量：typedef struct { char IDentifier[30];//标识符长度 int value;//定义标识符代表的数值}IDentifierTable;typedef struct { int syn;//种别码 int value;//数值或者标识符入口指针}SymbolTbl;IDentifierTable idTbl[30];//定义全局标识符表SymbolTbl symbol[100];//定义符号表，记录输入的程序片段下面是这一模块的具体的函数：1.void InsertID(char name[],int entry,int value) 功能是将标识符的名字和数值插入到以entry为标识符入口地址的标识符表中。2.int ScanEntry(char name[]) 查找标识符表中是否有空闲位置，若有则返回入口地址，若无则报错。3.void Insert_Into_SymbolTbl(int syn,int value,int &pointer) 将句子打散成的所有的二元组（名字和数值）插入到以pointer为符号表入口地址的符号表中。4.bool IsExist(char id[]) 查找表中是否已经存在该标识符5.int Search_Free_Entity( ) 这个函数即是在标识符表中申请一个可用的存储空间，若有则返回入口地址，否则报错，申请失败。6.bool IsLetter(char letter) 判断是否为字母7.bool IsDigit(char digit) 判断是否为数字8.void Scanner(char sentence[],char name[],int &syn,int &scan_point,int &value) 扫描子程序，识别正规式。对句子进行扫描，抛出一个个单词。scan_point为扫描的总指针，name和value用来记录返回值；sentence即是要分析的句子；syn为种别码。这个程序是词法分析的核心，在上一实验中已详细介绍过，再次不必赘述。9.bool Check_Is_Right(char sentence[]) 检查句子是不是#。。。#的形式，因为程序的需要，输入的句子规定必须是这样的形式。10.void LexicalAnalysisCtl() 词法分析的主控程序，也就是老师上课一再讲的那个主控程序。这个程序控制着Scanner(char sentence[],char name[],int &syn,int &scan_point,int &value)产生不同的正规式，并且负责着登记数据和错误处理。11.void Clear_Symbol_Tbl() 这个函数负责着清除符号表中的句子，以便接下来的句子输入。12.void Clear_IDentifier_Tbl() 这个函数的功能是清楚标识符表的所有内容。一般会在“清除语句”中使用。下面是Scanner的程序： 1 void Scanner(char sentence[],char name[],int &syn,int &scan_point,int &value) 2 { 3 char token[30],ch; 4 int p_token=0;//token的指针 5 int digit_value=0;//记录常数的大小 6 for(int n=0;n<30;n++) 7 { 8 token[n]='\0';//对字符数组清零 9 }10 ch=sentence[scan_point]; //读入一个字符11 if(ch=='#'&&scan_point==0)12 { //该字符的种别码已经在主程序中登记了13 scan_point++;//刚开始的第一个字符一定为‘#’14 ch=sentence[scan_point];//指针下移，扫描下一字符15 }16 if(IsLetter(ch)) //ch是否为字母17 {18 while(IsLetter(ch)||IsDigit(ch)) //ch是否为字母或数字19 {20 token[p_token++]=ch;21 scan_point++;22 ch=sentence[scan_point]; //读入一个字符23 }24 token[p_token]='\0';25 syn=9;//代表找到了标识符26 if(strcmp(token,"clear")==0)27 { //代表找到了保留字“clear”28 syn=11;29 }30 strcpy(name,token);//带回标识符31 }32 else if(IsDigit(ch)) //ch是否为数字33 { 34 digit_value=0;35 while(IsDigit(ch))36 { //此处假设只是整数37 digit_value=digit_value*10+ch-'0'; 38 scan_point++;39 ch=sentence[scan_point]; //读入一个字符40 }41 value=digit_value;//带回整数值42 syn=10;43 }44 else 45 { 46 switch(ch)47 {48 case'=':syn=1; break;49 case'?':syn=2; break;50 case'+':syn=3; break;51 case'-':syn=4; break;52 case'*':syn=5; break;53 case'/':syn=6; break; 54 case'(':syn=7; break;55 case')':syn=8; break;56 case'#':syn=12; break;57 default:printf("输入句子有误！\n");exit(0);break;58 }59 scan_point++;//保持指针始终指向待判断的字符60 ch=sentence[scan_point]; //读入一个字符61 }62 } 下面是主控程序：
1 void LexicalAnalysisCtl() 2 { //主控程序 3 char sentence[100]="\0"; 4 int syn=-1; 5 char name[30]=""; 6 int value; 7 int scan_point=0;//从开始处扫描 8 int id_pointer;//定义标识符表入口指针 9 int sym_pointer=0,entry;10 do11 {12 printf("请输入句子,以#开始并且以#结束\n");13 scanf("%s",sentence);14 }while(!Check_Is_Right(sentence));15 Insert_Into_SymbolTbl(12,-1,sym_pointer);16 printf("(%d , )\n",12); 17 while(syn!=12)18 { //直到扫描到第二个‘#’为止19 Scanner(sentence,name,syn,scan_point,value); 20 switch(syn)21 { //若是单词22 case 9:printf("(%d , %s)\n",syn,name); 23 //登记到表中24 if(!IsExist(name))25 { //不存在则插入26 //查找可插入位置27 id_pointer=Search_Free_Entity();28 InsertID(name,id_pointer,-1);//-1代表还没被赋值29 }30 //搜索该标识符的入口地址放入value中31 entry=ScanEntry(name);32 Insert_Into_SymbolTbl(syn,entry,sym_pointer);33 break;34 case 10://常数35 Insert_Into_SymbolTbl(syn,value,sym_pointer);36 printf("(%d , %d)\n",syn,value);37 break; 38 default:printf("(%d , )\n",syn); 39 Insert_Into_SymbolTbl(syn,-1,sym_pointer);//-1代表该处不需要值40 }41 }42 printf("--------------------词法分析正确！！！-------------------------\n");43 //打印出符号表和标识符表44 printf("标识符的入口地址 标识符 标识符的值(-1代表没被赋值)\n"); 45 for(int m1=0;m1<30;m1++)46 { //标识符表47 if(!(strcmp(idTbl[m1].IDentifier,"")==0))48 {49 printf("\t%d %s %d\n",m1,idTbl[m1].IDentifier,idTbl[m1].value);50 }51 }52 printf("符号表的入口地址 种别码 具体的值(或标识符入口)\n"); 53 for(int m2=0;m2 
比如说对于#temp=2+(3*(2+4))#这个句子的词法分析结果为：
模块四：核心功能模块------算符优先分析
前面做了那么多铺垫就是为了算符优先分析做准备。到了这一步，真的很不容易，因此我们更要对今天的编译器的处理能力感到惊叹，的确不是一个人可以完成的，就算一个人可以完成那所用的时间也真的不值。但是对于我们来说，学习一些《编译原理》上的一些处理问题的办法和角度，对我们未来的工作和生活绝对是大有裨益的。好了，就说一说这个费了我两天才完成的核心程序吧。 其实，核心程序并没有那么难以理解！只要我们举几个简单的例子，模拟一下计算机在处理这个句子的过程，便不难写出程序。 首先分析我们现在有什么？ 1.现在的情况是已经分析出了句子的单词，并且变成了单词块，存放在SymbolTbl symbol[100]中，单词的形式是（种别码，常数值）（种别码，标识符入口地址）、（种别码，用-1表示无意义）这是三大类。 2.并且分析出了标识符存放在了IDentifierTable idTbl[30]中。标识符的形式是（标识符名字，标识符的值），用-1表示暂未被赋值（这里就凑合一点，时间比较紧，待改进）。 3.分析出了算符优先分析的优先关系表存放在char PriorityTable[20][20]中。 4.已经编码出了种别码表，放在char SymbolTbl_Define[15]中，这个是老师要求的次序，便于一致。但又需要一次转换，以后再说。
好了，我们已经有了这么多数据和方法（函数function），是不是马上就可以进行下去了呢？！还不行，因为我们迫切需要一个后进先出的存储结构来保存我们的数据，来完成我们的移进，归约。那就是——栈。我们需要构造一个这样的栈：它的每个元素的数据结构都是符号表中元素的数据结构，即为（种别码，--），--处即为上面分析的三种情况。栈的能力主要有：template <typename T>1.T gettop() 获得栈顶元素2.int getTopPointer() 得到栈顶指针的数值3.T traverseStack(int pointer) 定义遍历整个栈的能力4. void push(T num) 将元素压栈的能力5.T pop() 将元素弹出栈的能力6.Stack(){top=-1;} 初始化的能力7.void Clear_Stack() 清空堆栈的能力数据对象：Stack<SymbolTbl> Reource_Symbol;//定义堆栈还有几个分析将使用的函数：char SearchSyn(int syn)根据种别码返回相应字符，因为我们是在对种别码进行大小比较，需要先将该种别码映射成具体的终结符。然后再将该终结符映射成优先关系表中的横纵坐标。int Search_Priority_Setxy(char ch)搜索一个字符在优先符表中的位置，这就是我说的“将该终结符映射成优先关系表中的横纵坐标。”的映射方法。void Print_Context(int Stack_Top,int Sym_Pointer)打印出当前堆栈和符号表的上下文void MainProc_Analysis()主分析函数，整个算法的核心。 好了，有了这些东西，我们的分析总算可以一马平川了。 1.首先将符号表的第一个元素#,对应的（种别码，-1）压栈，即 SymbolTbl temp_sym; temp_sym.syn=12; temp_sym.value=-1;//-1代表这个地方不需要 Reource_Symbol.push(temp_sym);//将#压栈 2.对于堆栈定义两个指针，一个指针pStackTop始终指向栈顶，在栈被修改（push,pop）之后都要修改。另一个堆栈指针是pScanStack，负责对整个堆栈的扫描，不断地查找可归约串的结束位置。 对于符号表，定义Sym_scan_pointer指针，从一开始，对符号表进行扫描。 3.因为现在不仅是语法分析，还包含了语义分析，我们要定义好语义子程序，比如说“清除语句”，#clear#，我们遇到这个东西时，就要1.清空符号表和标识符表；2.清除屏幕（我自己理解的，清除应该就是这些吧。。。） 因此，我们在进行其他分析之前，先把这个清除语句搞定。 if(sym_length>=3&&(symbol[1].syn==11)) {//清除语句，清除屏幕并且清空标号表中的值 Clear_IDentifier_Tbl(); Clear_Symbol_Tbl(); system("cls"); goto end; } 4.扫除了这些障碍，我们总算可以进行真正的分析了。 首先栈扫描指针和栈顶指针同时指向栈顶开始分析：下面进行永真循环：*******************************************************************{ 查看栈扫描指针pScanStack所指的元素和符号表指针所指元素的关系。4.1若为小于： 则将符号表指针所指元素压栈，修改栈的两个指针都指向栈顶。符号表指针下移。4.2若为等于： 此时要分两种情况：
@1.若是栈扫描指针pScanStack所指的元素和符号表指针所指元素都是#，则查看栈中是否只有两个元素且栈顶元素是否为N，若为真，则说明归约成功，输出栈顶的值，然后结束分析。否则，则报错。 @2.若不是上面的情况，则按照小于关系处理。4.3若为大于： 这个时候，就是激动人心的时候了，因为要进行归约了。 首先对齐pStackTop，pScanStack这两个指针，虽然这个时候肯定是对齐的（自己想），然后进入小循环 while(Prior_Relation=='>')，小循环的内容是： ****************小循环开始************************ 判断现在栈扫描指针所指元素的种别码，该种别码所对应元素即是大于符号表中指针所指的元素。 4.3.1、若该元素为标识符：语义分析：判断标识符是否已定义；弹出栈顶元素，将N（13，标识符的值）压入栈中，这里取了一次巧，即是让N来承载归约的结果，更加方便。重新修改栈顶指针，栈扫描指针，将栈扫描指针指向从栈顶数第一个终结符的位置，即下移。
pScanStack=Reource_Symbol.getTopPointer()-1;
重新定位行列指针（列不变），修改关系。
row_prior=Search_Priority_Setxy(SearchSyn(Reource_Symbol.traverseStack(pScanStack).syn)); Prior_Relation=PriorityTable[row_prior][column_prior];
4.3.2、若该元素为常量，则分析的过程和标识符极其相似，唯一不同的是，N(13,值）中的‘值’，一个是从标识符表中查到的，另一个是直接就有的。 4.3.3、若该元素为‘=’，这时根据文法的要求，出现等号就应该满足“v=N”这种情况。首先判断是否满足，若不满足则报错，若满足，则将这三个元素归约为一个元素N（13，旧N.value),并且要反填符号表，将该变量的值赋为旧N.value。这一步语义分析十分重要，直接关系着以后引用这个变量时是否能够找到它的值。
idTbl[Reource_Symbol.traverseStack(pScanStack-1).value].value=Reource_Symbol.gettop().value;//此时栈顶必为E
然后就是修改栈的两个指针，重新定位行列（列不变），修改关系。 4.3.4、若该元素为+、-、*、/，则这四个的处理方式一样。首先判断栈顶是否满足N op N,op={+|-|*|/},若满足则归约，否则认为是错误的，进行报错处理。规约之后，同样的将N op N归约为N，并且将 “新N.value=(N1.value op N1.value)” ------语义分析
然后就是修改栈的两个指针，重新定位行列（列不变），修改关系。 4.3.5、若该元素为‘）’，这个时候栈顶一定为（N），若不是，则句子出错，进行错误处理，又因为’(‘是大于任何终结符的，因此（N）就构成了“鱼眼睛”，“< = >”,所以需要归约将（N）归约为N，做相应的语义分析子程序: N.value=（N1.value），然后就是修改栈的两个指针，重新定位行列（列不变），修改关系。 因为’(‘小于任何终结符，因此不会出现在这里。 然后就是修改栈的两个指针，重新定位行列（列不变），修改关系。 4.3.6、若该元素为‘？’根据文法，出现这个东西，就是要打印N?中N的值了，因此先查看栈顶是否满足N？若满足，则归约，并作相应的语义动作，打印。 然后就是修改栈的两个指针，重新定位行列（列不变），修改关系。 满足大于关系的就这些终结符，我已一一分析了它们的语法分析和语义的动作。若该元素不是上面的终结符，则认为句子错误。否则将进行 while(Prior_Relation=='>')，的判断，若满足继续循环，否则，进入永真大循环中。
****************小循环结束*********************}//永真循环结尾
*******************************************************************
上面就是整个算符优先算法的精髓了。比如说对于上文的#temp=2+(3*(2+4))#分析的过程和结果为：
经过这么长时间的分析又浪费了一个晚上的时间，但觉得还是一气呵成，并且又理了一遍思路，还是值得的。
通过上面的叙述，整个程序的结构呼之欲出：
五.总控模块
最后的main()函数直接调用各个模块就可以了。代码如下：
int main(){ char ch;//是否继续的标记 //计算并显示firstVT()和LastVT() DisplayFirstVT_LasVT(); //创建算符优先关系表 createPriorityTable(); //打印算符优先关系表 DisplayPriorityTable(); //cout<<"请输入语句的个数"< >ch; if(!(ch=='y')&&!(ch=='Y')) { cout<<"the procedure is end"< 好了，这次的实验分析就到这里了。
2.3．程序架构设计 根据上面的思路，我采用了分文件的形式，这样思路比较清晰，程序比较简洁。下面的四个头文件中分别存放的是四个模块的代码。 #include "firstVT_lastVT.h"//计算firstVT()和LastVT()的程序 #include "GetPriorityTable.h"//创建算符优先关系表的程序 #include "Simple_Lexical_Analysis.h"//词法分析的程序 #include "MainProc_Analysis.h" //主分析程序，用来进行语法和语义分析 再加上最后的总控程序，整个程序的架构就是这个样子了。 2.4．测试 此处使用老师给的范例：演示示例： a=5 b=a+10 b? b+a*a? a=a+b
这里试验一下“清除语句”的作用：
比若说输入#a=3#:
这里归约的结果为3，即a=3,此时用清除语句，将清屏，并清除标识符表。#clear#
回车之后：
此时输入#b=2#，可以看到表示表中只有b,没有a
则说明a被清除。
2.5、感想 这次的实验花费了我不少时间，但也从中学到了很多，从最初的第一个模块一路走来，也遇到许多挫折，特别是明明逻辑都对却找不到错误的原因的时候，多亏了调试工具。 编写这个程序一部分来自于学习的课程要求，另一部分也来自于自己对编程的喜爱，或许正是这种感觉一直支持我到现在吧。代码虽然写完了，对于老师给的文法绝对是没问题的，可是毕竟也有它的局限性。即便如此，编译原理的处理问题的思想，思考问题的角度，都让我大受启发。这个程序其实是很全面的，它从词法分析-->语法分析-->语义分析---->问题求解，基本上走完了编译器的大部分生命周期。对于我们理解编译的过程和具体的实现都是很有帮助的。当然，编译原理博大精深，比如说对于数组的处理、中间代码的生成等很多方面，都值得我们认真揣摩。
2.6、源代码（所有）
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,int T) 21 { //X为终结符，T标记产生式id 22 int i,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,int S) 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 =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,int T) 111 { //X为终结符，T标记产生式id 112 int i,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,int S) 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==X 163 //若是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 void DisplayFirstVT_LasVT() 203 { 204 int i,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(char ch) 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(char ch) 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(char ch) 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 void createPriorityTable() 317 { //创建并填写优先级表 318 //对每个产生式遍历，求出四种关系1.=,2.<,3.>,4.没有关系 319 char temp[13]={ '+','-','*','/','(',')','v','c','=','?','#','\0'}; 320 int j,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 char temp_column; 361 tbl_row=SearchTbl(C[1]);// = ')' 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 char temp_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]='<'; 419 count++; 420 } 421 count=0; 422 }//end if 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 void DisplayPriorityTable() 450 { //显示优先关系表查看是否正确 451 int i,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 namespace std; 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 = 1 494 ？ 2 495 + 3 496 - 4 497 * 5 498 / 6 499 （ 7 500 ） 8 501 v 9 502 c 10 503 clear 11 504 # 12 505 N 13 506 */ 507 //此处简单起见，就只考虑标识符，运算符，数字 508 //定义一个结构存储（种别码、单词的入口地址）或者（种别码，常数值）或者（种别码） 509 void InsertID(char name[],int entry,int value) 510 { //插入到标识符表中 511 strcpy(idTbl[entry].IDentifier,name);//插入名字 512 idTbl[entry].value=value;//插入数值 513 } 514 515 int ScanEntry(char name[]) 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(char id[]) 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 int Search_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(char letter) 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(char digit) 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(char sentence[]) 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 void LexicalAnalysisCtl() 664 { //主控程序 665 char sentence[100]="\0"; 666 int syn=-1; 667 char name[30]=""; 668 int value; 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 764 class Stack{ 765 public: 766 Stack(){top=-1;}//构造函数，进行初始化操作 767 ~Stack(){}//析构函数 768 bool IsEmpty(){ 769 if(top==-1) 770 return true; 771 else 772 return false; 773 }//判断栈是否为空 774 775 //返回栈顶元素 776 T gettop() 777 { 778 return a[top]; 779 } 780 //得到栈顶指针的数值 781 int getTopPointer() 782 { 783 return top; 784 } 785 //定义遍历整个栈的能力 786 T traverseStack(int pointer) 787 { 788 //若pointer<0则报错 789 if(pointer<0) 790 { 791 cout<<"已到栈底，溢出!"< top) 795 { 796 cout<<"试图访问栈外元素，超界!"< =MAXSIZE) 805 return; 806 a[++top]=num; 807 } 808 //将元素弹出栈 809 T pop() 810 { 811 if(top==-1) 812 { 813 cout<<"栈已空，不能再弹"< Reource_Symbol;//定义堆栈 863 void Print_Context(int Stack_Top,int Sym_Pointer) 864 { //打印出当前堆栈和符号表的上下文 865 int syn,value,sym_length; 866 cout<<"\t当前堆栈情况为"< =3&&(symbol[1].syn==11)) 915 { //清除语句，清除屏幕并且清空标号表中的值 916 Clear_IDentifier_Tbl(); 917 Clear_Symbol_Tbl(); 918 Reource_Symbol.Clear_Stack(); 919 system("cls"); 920 goto end; 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=='<'||(Prior_Relation=='='&&(column_prior!=11||row_prior!=11))) 932 { //要是为小于或等于关系，则进栈 933 //这里的等于关系可能为(N),v=,这两种关系 934 Reource_Symbol.push(symbol[Sym_scan_pointer]);//栈顶++ 935 //扫描指针后移，不能回头 936 Sym_scan_pointer++; 937 //注意此时还要改变堆栈指针的值，让我调试了好久。。。 938 pStackTop=Reource_Symbol.getTopPointer();//得到变动后的栈顶指针，始终指向栈顶 939 pScanStack=pStackTop;//进行下一次判断，此时扫描指针指向新移进来的元素 940 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 int judge; 979 judge=Reource_Symbol.traverseStack(pScanStack).syn;//判断该种别码 980 //若是单个变量或常量则规约为N 981 //此处还要进行语义分析，对于标识符要查标识符表判断是否存在，若不存在则为错 982 if(judge==9) 983 { 984 if(idTbl[Reource_Symbol.traverseStack(pScanStack).value].value==-1) 985 { 986 cout<<"此变量可能没被定义，按照-1处理"< ')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|F 1291 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'};//定义各个终结符的syn1305 1306 int main()1307 {1308 char ch;//是否继续的标记1309 //计算并显示firstVT()和LastVT()1310 DisplayFirstVT_LasVT();1311 //创建算符优先关系表1312 createPriorityTable();1313 //打印算符优先关系表1314 DisplayPriorityTable();1315 //cout<<"请输入语句的个数"< >ch;1326 if(!(ch=='y')&&!(ch=='Y'))1327 {1328 cout<<"the procedure is end"<