首页 > 代码库 > 编译原理——算符优先分析文法(附源代码)

编译原理——算符优先分析文法(附源代码)

算符优先分析文法

一、写在前面

      算符优先分析文法是一种工具,在编译的过程中,隶属于语法分析环节,却又与中间代码的生成息息相关,编译可以分为五个阶段词法分析、语法分析、语义分析(中间代码的生成)、代码优化、目标代码生成。语法分析是指:在词法分析基础上,将单词符号串转化为语法单位(语法范畴)(短语、子句、句子、程序段、程序),并确定整个输入串是否构成语法上正确的程序。也就是说语法分析是检验输入串的语法是否正确,注意这里的语法正确,只是简单地符合自己定义的规范,而不能检测出运行时错误,比如"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<L;k++)
27            {//要是数组C[]中的终结符,如小写字母‘a‘~‘z‘,加减乘除,乘方,#
28             //则归入fisrstVT集中
29                //若是Aab...则a成为F()一部分,b被忽略,A也不用求first集???需要求!!!除非A==X
30                //若是QRa...,则不是算符优先文法,故不可能
31                //若是a...则只是填进a
32 
33              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]===)
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 }
View Code

  比如说对于这个文法分析出的集合如下:

技术分享

                                                   模块二:构建优先符号表
     为了体现“优先”的关系,只是构建出了上面的两种集合是不够的,由上面分析我们知道了这两个集合的用处。说白了就是为了构造出算符优先分析表。因为关系无非四类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]);// =<firstVT(E)
 47                               while(FIRSTVT[FL_map(C[2])][count_1]!=\0)
 48                               {//填写小于关系
 49                                 temp_column=FIRSTVT[FL_map(C[2])][count_1];//映射,仔细体会
 50                                 tbl_column=SearchTbl(temp_column);//将上述结果再次转换
 51                                 PriorityTable[tbl_row][tbl_column]=<;//填写关系
 52                                 count_1++;//准备填写下一个
 53                               }
 54                               count_1=0;//清零
 55                           }
 56                            if((L==3)&&IsVT(C[0])&&IsVT(C[2])&&(FL_map(C[1])!=-1))
 57                            {//弥补(E),针对本文法
 58                             //首先填写<关系
 59                               char temp_row,temp_column;
 60                               int reg=0;
 61                               tbl_row=SearchTbl(C[0]);
 62                               while(FIRSTVT[FL_map(C[1])][reg]!=\0)
 63                               {//填写小于关系 ‘(‘<firstVT(E)
 64                                 temp_column=FIRSTVT[FL_map(C[1])][reg];
 65                                 tbl_column=SearchTbl(temp_column);//皆是映射
 66                                 PriorityTable[tbl_row][tbl_column]=<;
 67                                 reg++;
 68                               }
 69                               reg=0;//清零
 70                               tbl_column=SearchTbl(C[2]);
 71                               while(LASTVT[FL_map(C[1])][reg]!=\0)
 72                               {//填写大于关系 lastVT(E)>‘)‘
 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);//map
103                                 PriorityTable[tbl_row][tbl_column]=<;
104                                 count++;
105                               }
106                               count=0;
107                           }//end if
108                       }
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 }
View Code

 比如说对于这个文法分析出来的优先关系表如下:

技术分享

                                                            模块三:构建词法分析的程序
     做好了上面两步运算已经累得不行了,下面还要继续进行分析,那就是词法分析程序,多亏这个程序在实验一已经完成过,这里就拿出那里的代码进行必要的改进和删除,保留适合本文法要求的部分即可。其实想来无非是用到了识别标识符、识别常数、识别+、-、*、/、?、#、(、)、保留字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=http://www.mamicode.com/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=http://www.mamicode.com/0;
35        while(IsDigit(ch))
36        { //此处假设只是整数
37          digit_value=http://www.mamicode.com/digit_value*10+ch-0;    
38          scan_point++;
39          ch=sentence[scan_point];  //读入一个字符
40        }
41        value=http://www.mamicode.com/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 }
View Code

 下面是主控程序:

技术分享
 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     do
11     {
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<sym_pointer;m2++)
54     {//符号表
55         printf("\t%d       %d     %d\n",m2,symbol[m2].syn ,symbol[m2].value);
56     }
57     printf("---------------------------------------------------------------\n");
58 }
View Code

技术分享

比如说对于#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=http://www.mamicode.com/-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=http://www.mamicode.com/Reource_Symbol.gettop().value;//此时栈顶必为E
      然后就是修改栈的两个指针,重新定位行列(列不变),修改关系。
   4.3.4若该元素为+、-、*、/,则这四个的处理方式一样。首先判断栈顶是否满足N op N,op={+|-|*|/},若满足则归约,否则认为是错误的,进行报错处理。规约之后,同样的将N op N归约为N,并且将  “新N.value=http://www.mamicode.com/(N1.value op N1.value)” ------语义分析

   然后就是修改栈的两个指针,重新定位行列(列不变),修改关系。
     4.3.5若该元素为‘)’,这个时候栈顶一定为(N),若不是,则句子出错,进行错误处理,又因为’(‘是大于任何终结符的,因此(N)就构成了“鱼眼睛”,
“< = >”,所以需要归约将(N)归约为N,做相应的语义分析子程序:
        N.value=http://www.mamicode.com/(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<<"请输入语句的个数"<<endl;
    while(1)
    {
        //首先要清空符号表,这样才能进行下一轮分析
        Clear_Symbol_Tbl();
        //词法分析,登记符号表
        LexicalAnalysisCtl();
       //语法语义分析,产生运行结果
           MainProc_Analysis();
        cout<<"continue? y or n"<<endl;
        cin>>ch;
        if(!(ch==y)&&!(ch==Y))
        {
            cout<<"the procedure is end"<<endl;
            exit(0);
        }
    }
    return 0;
}
View Code

  好了,这次的实验分析就到这里了。
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<L;k++)
  69            {//要是数组C[]中的终结符,如小写字母‘a‘~‘z‘,加减乘除,乘方,#
  70             //则归入fisrstVT集中
  71                //若是Aab...则a成为F()一部分,b被忽略,A也不用求first集???需要求!!!除非A==X
  72                //若是QRa...,则不是算符优先文法,故不可能
  73                //若是a...则只是填进a
  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,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]);// =<firstVT(E)
 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                               char temp_row,temp_column;
 375                               int reg=0;
 376                               tbl_row=SearchTbl(C[0]);
 377                               while(FIRSTVT[FL_map(C[1])][reg]!=\0)
 378                               {//填写小于关系 ‘(‘<firstVT(E)
 379                                 temp_column=FIRSTVT[FL_map(C[1])][reg];
 380                                 tbl_column=SearchTbl(temp_column);//皆是映射
 381                                 PriorityTable[tbl_row][tbl_column]=<;
 382                                 reg++;
 383                               }
 384                               reg=0;//清零
 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                           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=http://www.mamicode.com/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 =http://www.mamicode.com/ 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=http://www.mamicode.com/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=http://www.mamicode.com/0;
 625        while(IsDigit(ch))
 626        { //此处假设只是整数
 627          digit_value=http://www.mamicode.com/digit_value*10+ch-0;    
 628          scan_point++;
 629          ch=sentence[scan_point];  //读入一个字符
 630        }
 631        value=http://www.mamicode.com/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<sym_pointer;m2++)
 716     {//符号表
 717         printf("\t%d       %d     %d\n",m2,symbol[m2].syn ,symbol[m2].value);
 718     }
 719     printf("---------------------------------------------------------------\n");
 720 }
 721 
 722 
 723 void Clear_Symbol_Tbl()
 724 {
 725     //将符号表的syn全部设置为0
 726     for(int i=0;i<100;i++)
 727     {
 728         symbol[i].syn=0;//代表没定义
 729         symbol[i].value=http://www.mamicode.com/-1;//指定为-1
 730     }
 731 }
 732 
 733 
 734 void Clear_IDentifier_Tbl()
 735 {//清空标识符表
 736     for(int i=0;i<30;i++)
 737     {
 738         strcpy(idTbl[i].IDentifier,"");
 739         idTbl[i].value=http://www.mamicode.com/-1;
 740     }
 741 }
 742 /*************#include"Simple_Lexical_Analysis.h"****************/
 743 
 744 
 745 模块四:
 746 
 747 /***********#include "MainProc_Analysis.h"********************/
 748 
 749 #include"iostream"
 750 using namespace std;
 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 <typename T>
 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<<"已到栈底,溢出!"<<endl;
 792                 exit(0);//退出,分析失败
 793             }
 794             if(pointer>top)
 795             {
 796                 cout<<"试图访问栈外元素,超界!"<<endl;
 797                 exit(0);//退出,分析失败
 798             }
 799             return a[pointer];//返回元素值
 800         }
 801         //将元素压栈
 802         void push(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<<"栈已空,不能再弹"<<endl;
 814                 exit(0);
 815             }
 816             return  a[top--];
 817         }
 818         void Clear_Stack()
 819         {//清空堆栈的能力
 820             top=-1;
 821         }
 822 private:
 823       T  a[MAXSIZE];
 824       int top;
 825 };
 826 /*单词种别码设计:
 827         =   1
 828         ?  2
 829         +   3
 830         -   4
 831         *   5
 832         /   6
 833        (   7
 834         )  8
 835         v   9
 836         c   10
 837       clear 11
 838         #   12
 839         N   13
 840 */
 841 //char SymbolTbl_Define[15]={‘=‘,‘\?‘,‘+‘,‘-‘,‘*‘,‘/‘,‘(‘,‘)‘,‘v‘,‘c‘,‘l‘,‘#‘,‘N‘,‘\0‘};
 842 
 843 
 844 /********经过以下连个函数就可以知道种别码对应的字符在符号表中的位置************/
 845 char SearchSyn(int syn)
 846 {//根据种别码返回相应字符
 847     return SymbolTbl_Define[syn-1];
 848 }
 849 char  Prior_Position[13]={+,-,*,/,(,),v,c,=,?,#,\0};
 850 int Search_Priority_Setxy(char ch)
 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<SymbolTbl>  Reource_Symbol;//定义堆栈
 863 void  Print_Context(int Stack_Top,int Sym_Pointer)
 864 {//打印出当前堆栈和符号表的上下文
 865     int syn,value,sym_length;
 866     cout<<"\t当前堆栈情况为"<<endl;
 867     cout<<"\t\t";
 868     for(int i=0;i<=Stack_Top;i++)
 869     {//打印出堆栈
 870         syn=Reource_Symbol.traverseStack(i).syn;
 871         value=http://www.mamicode.com/Reource_Symbol.traverseStack(i).value;
 872         cout<<"("<<syn<<","<<value<<")  ";
 873     }
 874     cout<<endl<<"\t当前符号表情况为"<<endl;
 875     cout<<"\t\t";
 876     for(i=1;symbol[i].syn!=12;i++)
 877         ;//计算符号表的长度i
 878      sym_length=i+1;//长度,最后一个为#,从1开始数
 879     for(int j=Sym_Pointer;j<sym_length;j++)
 880     {//打印出堆栈
 881         syn=symbol[j].syn;
 882         value=http://www.mamicode.com/symbol[j].value;
 883         cout<<"("<<syn<<","<<value<<")  ";
 884     }
 885     cout<<endl;
 886 }
 887 void  MainProc_Analysis()
 888 {//现在的情况是已经分析出了句子的单词,并且变成了单词块,存放在SymbolTbl symbol[100];中
 889  //并且分析出了标识符存放在了IDentifierTable  idTbl[30];中
 890  //分析出了算符优先分析的优先关系表存放在char PriorityTable[20][20];中
 891  //已经编码出了种别码表,放在char SymbolTbl_Define[15];中
 892  
 893     cout<<"下面开始核心算法:"<<endl;
 894     int i;
 895     int row_prior,column_prior;//行列定位指针
 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=http://www.mamicode.com/-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        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<<Statement_count++<<".这里是小于、等于关系,压栈!"<<endl;
 941           Print_Context(Reource_Symbol.getTopPointer(),Sym_scan_pointer);
 942        }
 943        else if(Prior_Relation===&&column_prior==11&&row_prior==11)
 944        {//规约到最后#N,查看栈中是否满足情况
 945            //输出N的数值并结束
 946            int  final_value;
 947            if(Reource_Symbol.gettop().syn==13&&(Reource_Symbol.getTopPointer()==1))
 948            {//若满足#N的情况,则归约成功!
 949                cout<<Statement_count++<<"."<<"归约成功!!!"<<endl;
 950                Print_Context(Reource_Symbol.getTopPointer(),Sym_scan_pointer);
 951                final_value=http://www.mamicode.com/Reource_Symbol.gettop().value;
 952                printf("最后的结果为  %d  \n",final_value);
 953                Reource_Symbol.Clear_Stack();
 954                break;//退出大循环,唯一的正确出口
 955            }
 956            else
 957            {
 958                cout<<"句子错误,程序结束!"<<endl;
 959                exit(0);
 960            }
 961        }
 962        else if(Prior_Relation==>)
 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=http://www.mamicode.com/=-1)
 985                    {
 986                        cout<<"此变量可能没被定义,按照-1处理"<<endl;
 987                    }
 988                    if(Reource_Symbol.traverseStack(pScanStack).value<0)
 989                    {//若该变量的符号表入口地址为负值,则说明查无此元素,则认为语法出错,变量未定义
 990                        cout<<"该变量未定义"<<endl;
 991                        exit(0);
 992                    }
 993                    else 
 994                    {//否则将该标识符规约为N
 995                         temp_sym.syn=13;
 996                         //获得符号表中关于该变量的值
 997                         temp_sym.value=http://www.mamicode.com/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<<"句子错误,程序结束!"<<endl;
1006                            exit(0);
1007                         }
1008                         row_prior=Search_Priority_Setxy(SearchSyn(Reource_Symbol.traverseStack(pScanStack).syn));
1009                         Prior_Relation=PriorityTable[row_prior][column_prior];//此处列是不会变的,因为大于关系
1010                         cout<<Statement_count++<<"."<<"此处将变量规约为N"<<endl;
1011                         Print_Context(Reource_Symbol.getTopPointer(),Sym_scan_pointer);
1012                    }
1013                }
1014                else if(judge==10)
1015                {//若是常量,则要记住该常量值以便进行规约时赋值
1016                    temp_sym.syn=13;
1017                    temp_sym.value=http://www.mamicode.com/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<<"句子错误,程序结束!"<<endl;
1025                         exit(0);
1026                    }
1027                    row_prior=Search_Priority_Setxy(SearchSyn(Reource_Symbol.traverseStack(pScanStack).syn));
1028                    Prior_Relation=PriorityTable[row_prior][column_prior];//同标识符
1029                    cout<<Statement_count++<<"."<<"此处将常量规约为N"<<endl;
1030                    Print_Context(Reource_Symbol.getTopPointer(),Sym_scan_pointer);
1031                }
1032                else if(judge==1)
1033                {//v=E,此时要进行赋值操作,然后规约
1034                    if(Reource_Symbol.traverseStack(pScanStack-1).syn==9)//一定为9
1035                    {//若前面为标识符则正确,应该为该变量赋值
1036                        //语义分析
1037                        idTbl[Reource_Symbol.traverseStack(pScanStack-1).value].value=http://www.mamicode.com/Reource_Symbol.gettop().value;//此时栈顶必为E
1038                        temp_sym.syn=13;
1039                        temp_sym.value=http://www.mamicode.com/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<<"句子错误,程序结束!"<<endl;
1050                            exit(0);
1051                        }
1052                        row_prior=Search_Priority_Setxy(SearchSyn(Reource_Symbol.traverseStack(pScanStack).syn));
1053                        Prior_Relation=PriorityTable[row_prior][column_prior];//进行下次判断
1054                        cout<<Statement_count++<<"."<<"此处遇到等号要将v=E规约为N,程序面临结束!"<<endl;
1055                        Print_Context(Reource_Symbol.getTopPointer(),Sym_scan_pointer);
1056                    }
1057                    else  
1058                    {
1059                        cout<<"等号前面应该有变量!"<<endl;
1060                        exit(0);
1061                    }
1062                }//end if(judge==1)
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=http://www.mamicode.com/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<<"句子错误,程序结束!"<<endl;
1081                            exit(0);
1082                        }
1083                        row_prior=Search_Priority_Setxy(SearchSyn(Reource_Symbol.traverseStack(pScanStack).syn));
1084                        Prior_Relation=PriorityTable[row_prior][column_prior];//进行下次判断
1085                        cout<<Statement_count++<<"."<<"此处为加法运算,将N+N规约为N,并进行语义分析!"<<endl;
1086                        Print_Context(Reource_Symbol.getTopPointer(),Sym_scan_pointer);
1087                    }
1088                    else  
1089                    {
1090                        cout<<"加号两边应该都有变量,句子错误!"<<endl;
1091                        exit(0);
1092                    }
1093                }
1094                else  if(judge==4)
1095                {//-
1096                     if(Reource_Symbol.traverseStack(pScanStack-1).syn==13&&Reource_Symbol.traverseStack(pScanStack+1).syn==13)//一定为13
1097                     {//若前面为N并且栈顶为N则正确   N-N
1098                        //语义分析,newtemp()
1099                        temp_sym.syn=13;
1100                        //注意运算的顺序
1101                        temp_sym.value=http://www.mamicode.com/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<<"句子错误,程序结束!"<<endl;
1112                            exit(0);
1113                        }
1114                        row_prior=Search_Priority_Setxy(SearchSyn(Reource_Symbol.traverseStack(pScanStack).syn));
1115                        Prior_Relation=PriorityTable[row_prior][column_prior];//进行下次判断
1116                        cout<<Statement_count++<<"."<<"此处为减法运算,将N-N规约为N,并进行语义分析!"<<endl;
1117                        Print_Context(Reource_Symbol.getTopPointer(),Sym_scan_pointer);
1118                    }
1119                    else  
1120                    {
1121                        cout<<"减号两边应该都有变量,句子错误!"<<endl;
1122                        exit(0);
1123                    }
1124                }
1125                else  if(judge==5)
1126                {//*
1127                     if(Reource_Symbol.traverseStack(pScanStack-1).syn==13&&Reource_Symbol.traverseStack(pScanStack+1).syn==13)//一定为13
1128                     {//若前面为N并且栈顶为N则正确   N*N
1129                        //语义分析,newtemp()
1130                        temp_sym.syn=13;
1131                        //注意运算的顺序
1132                        temp_sym.value=http://www.mamicode.com/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<<"句子错误,程序结束!"<<endl;
1143                            exit(0);
1144                        }
1145                        row_prior=Search_Priority_Setxy(SearchSyn(Reource_Symbol.traverseStack(pScanStack).syn));
1146                        Prior_Relation=PriorityTable[row_prior][column_prior];//进行下次判断
1147                        cout<<Statement_count++<<"."<<"此处为乘法运算,将N*N规约为N,并进行语义分析!"<<endl;
1148                        Print_Context(Reource_Symbol.getTopPointer(),Sym_scan_pointer);
1149                    }
1150                    else  
1151                    {
1152                        cout<<"乘号两边应该都有变量,句子错误!"<<endl;
1153                        exit(0);
1154                    }
1155                }
1156                else  if(judge==6)
1157                {// /除
1158                     if(Reource_Symbol.traverseStack(pScanStack-1).syn==13&&Reource_Symbol.traverseStack(pScanStack+1).syn==13)//一定为13
1159                     {//若前面为N并且栈顶为N则正确   N*N
1160                        //语义分析,newtemp()
1161                        temp_sym.syn=13;
1162                        //注意运算的顺序
1163                        temp_sym.value=http://www.mamicode.com/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<<"句子错误,程序结束!"<<endl;
1174                            exit(0);
1175                        }
1176                        row_prior=Search_Priority_Setxy(SearchSyn(Reource_Symbol.traverseStack(pScanStack).syn));
1177                        Prior_Relation=PriorityTable[row_prior][column_prior];//进行下次判断
1178                        cout<<Statement_count++<<"."<<"此处为除法运算,将N/N规约为N,并进行语义分析!"<<endl;
1179                        Print_Context(Reource_Symbol.getTopPointer(),Sym_scan_pointer);
1180                    }
1181                    else  
1182                    {
1183                        cout<<"除号两边应该都有变量,句子错误!"<<endl;
1184                        exit(0);
1185                    }
1186                }
1187                else if(judge==8)
1188                {// ) 若为右括号,这种情况一旦出现就要将(N)规约为N
1189                    //判断前面是不是“(N”
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<-(N),N.value=http://www.mamicode.com/(N).value
1195                        temp_sym.value=http://www.mamicode.com/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<<"句子错误,程序结束!"<<endl;
1206                            exit(0);
1207                        }
1208                        row_prior=Search_Priority_Setxy(SearchSyn(Reource_Symbol.traverseStack(pScanStack).syn));
1209                        Prior_Relation=PriorityTable[row_prior][column_prior];//进行下次判断
1210                        cout<<Statement_count++<<"."<<"此处为),将(N)规约为N,并进行语义分析!"<<endl;
1211                        Print_Context(Reource_Symbol.getTopPointer(),Sym_scan_pointer);
1212                    }
1213                    else  
1214                    {
1215                        cout<<"括号不匹配,句子错误!"<<endl;
1216                        exit(0);
1217                    }
1218                }
1219                else if(judge==2)
1220                {// ? 则问号前面必为N
1221                     if(Reource_Symbol.traverseStack(pScanStack-1).syn==13)
1222                     {
1223                        //语义分析,newtemp()
1224                        temp_sym.syn=13;
1225                        temp_sym.value=http://www.mamicode.com/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<<"句子错误,程序结束!"<<endl;
1235                            exit(0);
1236                        }
1237                        row_prior=Search_Priority_Setxy(SearchSyn(Reource_Symbol.traverseStack(pScanStack).syn));
1238                        Prior_Relation=PriorityTable[row_prior][column_prior];//进行下次判断
1239                        cout<<Statement_count++<<"."<<"此处将 N? 规约为N"<<endl;
1240                        Print_Context(Reource_Symbol.getTopPointer(),Sym_scan_pointer);
1241                    }
1242                    else  
1243                    {
1244                        cout<<"问号前面必须有N!"<<endl;
1245                        exit(0);
1246                    }
1247                }
1248                else 
1249                {
1250                    cout<<"暂时还未定义"<<endl;
1251                    exit(0);
1252                }
1253           }// end while(Prior_Relation==‘>‘)
1254        }//end else if(Prior_Relation==‘>‘)
1255    }//end while(1)
1256   end: ;
1257 }//end 
1258 
1259 /*单词种别码设计:
1260         =   1
1261         ?  2
1262         +   3
1263         -   4
1264         *   5
1265         /   6
1266        (   7
1267         )  8
1268         v   9
1269         c   10
1270       clear 11
1271         #   12
1272         N   13
1273 */
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?|l
1289 E-->E+T|E-T|T
1290 T-->T*F|T/F|F 
1291 F-->(E)|v|c
1292 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 int  main()
1307 {
1308     char ch;//是否继续的标记
1309     //计算并显示firstVT()和LastVT()
1310     DisplayFirstVT_LasVT();
1311     //创建算符优先关系表
1312     createPriorityTable();
1313     //打印算符优先关系表
1314     DisplayPriorityTable();
1315     //cout<<"请输入语句的个数"<<endl;
1316     while(1)
1317     {
1318         //首先要清空符号表,这样才能进行下一轮分析
1319         Clear_Symbol_Tbl();
1320         //词法分析,登记符号表
1321         LexicalAnalysisCtl();
1322        //语法语义分析,产生运行结果
1323            MainProc_Analysis();
1324         cout<<"continue? y or n"<<endl;
1325         cin>>ch;
1326         if(!(ch==y)&&!(ch==Y))
1327         {
1328             cout<<"the procedure is end"<<endl;
1329             exit(0);
1330         }
1331     }
1332     return 0;
1333 }
View Code

编译原理——算符优先分析文法(附源代码)