算符优先分析方法

实验三：自底向上分析：算符优先分析方法

一、实验原理：算符优先分析算法

二、实验内容：

1、了解语法分析的其中一种自底向上分析算符优先分析；

2、学会构造算符优先矩阵；

3、上机实现算符优先分析器的工作流程。

三、实验要求：

要求能对下列文法所产生的符号串进行语法分析：

①EE+T|E-T|T

②TT*F|T/F|F

③F(E)|num|id

对输入的符号在分析完之后，如果正确就报告，有误就停止。

四、实验步骤：

1、 求出该文法所有非终结符的leadvt以及lastvt表；

2、 根据所求出的表，再构造相应的算符优先矩阵；

3、 根据参考程序（见课本P137 程序4-5），实现算符优先分析器的工作流程。

五、程序设计指导：

1、 本次实验要完成的程序功能为：用程序实现算符优先分析器的工作流程，根据不断地查找指定文法得出的算符优先矩阵，最终判断输入串是否符合该文法的语法要求；

2、 首先，在本次实验的预习报告中要先完成实验原理部分以及实验步骤中的前面两条；

3、 程序中用到的关键函数的说明：

 IsHigherThan（）：用来返回两个终结符之间是否有大于关系；

 IsLowerThan（）：用来返回两个终结符之间是否有小于关系；

 IsEqualTo（）：用来返回两个终结符之间是否有等于关系；

 Reduce（）：把满足当前应被规约的最左子串条件的字符串进行规约；

 parser（）：根据算符优先分析算法设计的分析函数。

六、实验代码：

// priority.cpp : 定义控制台应用程序的入口点。

//

//#include "stdafx.h"

#include

#include

#include

#include

# define SUCCESS 1

# define ERROR 0

# define MAXINPUT 300 # define MAXSTACK 100

char stack[MAXSTACK],a[MAXINPUT];

struct relations

{

char row; //行

char colum; //列

char rel; //大小关系

}table[70]={

{'+','+','>'},//1

{'+','-','>'},//2

{'+',')','>'},//3

{'+','#','>'},//4

{'-','+','>'},//5

{'-','-','>'},//6

{'-',')','>'},//7

{'-','#','>'},//8

{'*','+','>'},//9

{'*','-','>'},//10

{'*',')','>'},//11

{'*','#','>'},//12

{'*','*','>'},//13

{'*','/','>'},//14

{'/','+','>'},//15

{'/','-','>'},//16

{'/',')','>'},//17

{'/','#','>'},//18

{'/','*','>'},//19

{'/','/','>'},//20

{')','+','>'},//21

{')','-','>'},//22

{')',')','>'},//23

{')','#','>'},//24

{')','*','>'},//25

{')','/','>'},//26

{'n','+','>'},//27

{'n','-','>'},//28 {'n',')','>'},//29

{'n','#','>'},//30

{'n','*','>'},//31

{'n','/','>'},//32

{'i','+','>'},//33

{'i','-','>'},//34

{'i',')','>'},//35

{'i','#','>'},//36

{'i','*','>'},//37

{'i','/','>'},//38

{'+','*','<'},//39

{'+','/','<'},//40

{'+','(','<'},//41

{'+','n','<'},//42

{'+','i','<'},//43

{'-','*','<'},//44

{'-','/','<'},//45

{'-','(','<'},//46

{'-','n','<'},//47

{'-','i','<'},//48

{'*','(','<'},//49

{'*','n','<'},//50

{'*','i','<'},//51

{'/','(','<'},//52

{'/','n','<'},//53

{'/','i','<'},//54

{'(','+','<'},//55

{'(','-','<'},//56

{'(','*','<'},//57

{'(','/','<'},//58

{'(','(','<'},//59

{'(',')','='},//60

{'(','n','<'},//61

{'(','i','<'},//62

{'#','+','<'},//63

{'#','-','<'},//64

{'#','*','<'},//65 {'#','/','<'},//66

{'#','(','<'},//67

{'#','n','<'},//68

{'#','i','<'},//69

{'#','#','='} //70新增

};

char vt[9]={'+','-','*','/','(',')','n','i','#'};

struct anlysis

{

char vn;

char rs[4];

}productions[21]={

{'E',"F+F"},//0

{'E',"E+T"},//1

{'E',"T+F"},//2

{'E',"T+T"},//3

{'E',"E+F"},//4

{'E',"F+T"},//5

{'E',"E-T"},//6

{'E',"T-F"},//7

{'E',"T-T"},//8

{'E',"E-F"},//9

{'E',"F-T"},//10

{'E',"F-F"},//11

{'E',"T"},//12

{'T',"T*F"},//13

{'T',"F*F"},//14

{'T',"T/F"},//15

{'T',"F/F"},//16

{'T',"F"},//17

{'F',"(E)"},//18

{'F',"n"},//19

{'F',"i"}//20

};

int IsHigherThan(char stk,char cmp) // >返回1，否则返回0 {

for(int i=0;i<=69;i++)

{

if((table[i].row==stk)&&(table[i].colum==cmp)&&(table[i].rel=='>'))

return 1;

}

return 0;

}

int IsLowerThan(char stk,char cmp) //

{

for(int i=0;i<=69;i++)

{

if((table[i].row==stk)&&(table[i].colum==cmp)&&(table[i].rel=='<'))

return 1;

}

return 0;

}

int IsEqualTo(char stk,char cmp) // =返回1，否则返回0

{

for(int i=0;i<=69;i++)

{

if((table[i].row==stk)&&(table[i].colum==cmp)&&(table[i].rel=='='))

return 1;

}

return 0;

}

char Reduce(int begin,int end,int len) //归约

{

char token[10];

for(int i=0;i

{

token[i]=stack[begin+i];

}

token[i]='\0';

//查找归约表，返回归约值

for(int j=0;j<21;j++)

{