编译原理预测分析表方法代码实现


预测分析表方法
一、目的
理解预测分析表方法的实现原理。
二、内容:
编写一通用的预测法分析程序,要求有一定的错误处理能力,出错后能够使程序继续运行下去,直到分析过程结束。可通过不同的文法(通过数据表现)进行测试。

二、内容提示
1.算法数据构造:
构造终结符数组:char Vt[10][5]={“id”,”+”……};
构造非终结符数组:char Vn[10]={ };
构造follow集数组:char *follow[10][10]={ } (可将follow集与预测分析表合并存放)
数据构造示例(使用的预测分析表构造方法1):
/*data1.h简单算术表达式数据*/
char VN[10][5]={“E”,”E'”,”T”,”T'”,”F”}; //非终结符表
int length_vn=5; //非终结符的个数

char VT[15][5]={“id”,”+”,”*”,”(“,”)”,”#”}; //终结符表
int length_vt=6; //终结符的个数

char Fa[15][10]={“TE'”,”+TE'”,””,”FT'”,”*FT'”,””,”(E)”,”id”};
//产生式表:0:E->TE’ 1:E’->+TE’ 2:E’->空
// 3:T->FT’ 4:T’->*FT’ 5:T’->空 6:F->(E) 7:F->id

int analysis_table[10][11]={0,-1,-1,0,-2,-2,0,0,0,0,0,
-1,1,-1,-1,2,2,0,0,0,0,0,
3,-2,-1,3,-2,-2,0,0,0,0,0,
-1,5, 4,-1,5, 5,0,0,0,0,0,
7,-2,-2,6,-2,-2,0,0,0,0,0};
//预测分析表,-1表示出错,-2表示该行终结符的follow集合,用于错误处理,正数表示产生式在数组Fa中的编号,0表示多余的列。

(1)预测分析表的构造方法1
给文法的正规式编号:存放在字符数组中,从0开始编号,正规式的编号即为该正规式在数组中对应的下标。如上述Fa数组表示存储产生式。
构造正规式数组:char P[10][10]={“E->TE’”,”E’->+TE’”,……..}; (正规式可只存储右半部分,如E->TE’可存储为TE’ ,正规式中的符号可替换,如可将E’改为M )
构造预测分析表:int analyze_table[10][10]={ } //数组元素值存放正规式的编号,-1表示出错
(2)预测分析表的构造方法2
可使用三维数组
Char analyze_table[10][10][10]={ }

Char *analyze_table[10][10]={ }

2.针对预测分析表构造方法1的查预测分析表的方法提示:
(1)查非终结符表得到非终结符的序号no1
(2)查终结符表得到终结符的序号no2
(3)根据no1和no2查预测分析表得到对应正规式的序号no3=analyze_table[no1][no2] ,如果no3=-1 表示出错。
(4)根据no3查找对应的正规式Fa[no3]
(5)对正规式进行处理
3.错误处理机制
紧急方式的错误恢复方法(抛弃某些符号,继续向下分析)
(1)栈顶为非终结符A,串中当前单词属于FOLLOW(A),则从栈中弹出A(此时可认为输入串中缺少A表示的结构),继续分析。 ———错误编号为1
(2)栈顶为非终结符A,串中当前单词不属于FOLLOW(A),则可使串指针下移一个位置(认为输入串中当前单词多余),继续分析。———-错误编号为2
(3)栈顶为终结符,且不等于串中当前单词,则从栈中弹出此终结符(认为输入串中缺少当前单词)或者将串指针下移一个位置(认为串中当前单词多余)。在程序中可选择上述两种 观点中的一种进行处理。————-错误编号3
因此error()函数的编写方式可按如下方式处理
Error(int errornum)
{
If(errornum==1)………………
Else if(errornum==2)……………
Else ………………..
//或者可用choose case语句处理
}
4.增加了错误处理的预测分析程序预测分析程序的算法:

将“#”和文法开始符依次压入栈中;
把第一个输入符号读入a;
do{
把栈顶符号弹出并放入x中;
if(x∈VT)
{
if(x==a) 将下一输入符号读入a;
else error(3);
}
else
if(M[x,a]=“x→y1y2…yk”)
{
按逆序依次把yk、yk−1、…、y1压入栈中;
输出“x→y1y2…yk”;
}
else if afollow(x)error(1); else error(2);
//在前述的数据定义中查表为-2表示afollow(x)
}while(x!=“#”)

三.要求
给定算术表达式文法,编写程序。
测试数据:
1.算术表达式文法
E→TE’
E’ → +TE’|- TE’|ε
T→FT’
T’ →*FT’ |/ FT’ |%FT’|ε
F→(E) |id|num

下面就是我的菜鸟代码,希望大家可以指点一番:
*****************************************************************************

#include
#include
#include
#include
using namespace std;

const int NUM =20;

char Var[5]={'E','M','T','G','F'};//非终结符表 M代替E'  G代替T' 
char Ter[10]={'+','-','*','/','%','(',')','I','N','#'};//终结符表,“~”表示空 I表示id  N表示num 

char Fa[12][5]={"TM","+TM","-TM","~","FG","*FG","/FG","%FG","~","(E)","I","N"};

 int analysis_table[5][10]{//预测分析表 
	{-2,-2,-2,-2,-2,0,-1,0,0,-1},
	{1,2,-1,-1,-1,-1,3,-1,-1,3},
	{-1,-1,-2,-2,-2,4,-2,4,4,-1},
	{3,3,5,6,7,-2,8,-2,-2,8},
	{-2,-2,-1,-1,-1,9,-2,10,11,-2}
} ;

typedef struct{//栈结构体
	char *top;
	char *base;
	int stacksize;
	int num;
}Stack;
void init(Stack *s) {//初始化栈 
	s->base=(char *)malloc(NUM*sizeof(char));
	if(!s->base){
		cout<<"初始化栈错误!!"<<endl; exit(1); } s->top=s->base;
	s->stacksize=NUM;
	s->num=0;
}
void push(Stack *s,char var){//入栈 
	if(s->top-s->base>=s->stacksize){
		cout<<"入栈失败,栈满!!"<<endl; exit(1); } *(s->top)=var;
	s->top++;
	s->num++;
} 
void pop(Stack *s){// 出栈
	if(s->top==s->base){
		cout<<"出栈失败,栈空!!"<<endl; exit(1); } s->top--;
	s->num--;
} 
char getTop(Stack *s){//获取栈顶元素 
	if(s->top==s->base){
		cout<<"获取栈顶元素失败,栈空!!"<<endl; exit(1); } return *(s->top-1);
} 
int judgeTer(char str){//判断是否为终结符 如果为终结符则返回对应终结符表Ter下标,反之返回10 
	int i;
	for(i=0;i<10;i++){
		if(Ter[i]==str){
			break;
		}
	} 
	return i;
}

string isInPred(char v,char t){//查找分析表,并返回右部 
	int i,j;
	 for(i=0;i<5;i++){
		if(Var[i]==v){
			break;
		}
	} 
	for(j=0;j<10;j++){ if(Ter[j]==t){ break; } } if(analysis_table[i][j]>-1){
		return Fa[analysis_table[i][j]];
	}
	else
		{
			if(analysis_table[i][j]==-1){
				return "-1";
			}
			if(analysis_table[i][j]==-2){
				return "-2";
			}
		}
}

void displayStack(Stack *stack){//输出栈中的内容 
	string str;
	Stack s=* stack;
	while(s.num!=0){
		str +=getTop(&s);
		pop(&s);
	}
	for(int i=str.length()-1;i>=0;i--){
		cout<<str.at(i);
	}
} 
void leadmain(Stack stack,string input){//分析总函数 
int inputNum=0,count=0,error=0;//inputNum标记字符串匹配的位置,count标记的为比较步数  error标记出错 
char  topC,inputC;//topC存栈顶字符 inputC当前字符 
cout<<"步骤"<<'\t'<<"栈"<<'\t'<<"剩余字符"<<'\t'<<"动作"<<endl;
cout<<"-----------------------------------------------------"<<endl; 
cout<<count++<<'\t';
displayStack(&stack);
cout<<'\t'<<input<<'\t'<<""<<endl; while(getTop(&stack)!='#'||input.at(inputNum)!='#')//判断栈顶是否为“#”,文法是否结束 { string produce=""; //记录动作信息 topC= getTop(&stack); inputC=input.at(inputNum); if(judgeTer(topC)==10) {//判断栈顶为非终结符 ,入栈 string str=isInPred(topC,inputC); if(!(str=="-1"||str=="-2")) { pop(&stack); if(str!="~"){ for(int j=str.length()-1;j>=0;j--)
						push(&stack,str.at(j));
				}
				produce+="展开非终结符"; 
				produce+=topC;
				produce+="->";
				produce+=str;
				}
			else{	
					if(str=="-1"){
						produce+="出错,串中当前单词属于FOLLOW(A),弹出栈顶符号:"; 
						produce+=topC;
						pop(&stack);
					}
					else{
						produce+="出错,串中当前单词不属于FOLLOW(A),跳过字符:"; 
						produce+=inputC;
						inputNum++;
					}
				}
			cout<<count++<<'\t';
			displayStack(&stack);
			cout<<'\t'<<input.substr(inputNum)<<'\t'<<produce<<endl;
		}
		else{//栈顶为终结符 
			if(topC==inputC) {
				pop(&stack);
				produce+="匹配成功终结符:";
				produce+=inputC;
				}
			else {//错误处理3 串指针下移一个位置
				produce+="出错,跳过字符:";
				produce+=inputC;
				}
			inputNum++;
			cout<<count++<<'\t';
			displayStack(&stack);
			cout<<'\t'<<input.substr(inputNum)<<'\t'<<produce<<endl;
		} 
	}
	cout<<count++<<'\t';
	displayStack(&stack);
	cout<<'\t'<<input.substr(inputNum)<<'\t'<<"结束"<<endl;
}

int main()
{
	while(1){
		string input;
		Stack stack;
		init(&stack);
		push(&stack,'#');
		push(&stack,'E');
		cout<<"-----------------文法如下---------------------"<<endl;
		cout<<"E->TE'"<<endl; 
		cout<<"E'->+TE'|-TE'|~"<<endl; 
		cout<<"T->FT'"<<endl; 
		cout<<"T'->*FT'|/FT'|%FT'|~"<<endl; 
		cout<<"F->(E)|id|num"<<endl; 
		cout<<"----------------------------------------------"<<endl; 
		cout<<" M代替E'  G代替T'  ~代替空  I代替id  N代替num "<<endl; 
		cout<<"**********************************************"<<endl;
		do{
			cout<<"请输入表达式(以#结尾):" ; cin>>input;
		}while(input.at(input.length()-1)!='#');
		leadmain(stack,input);
		system("pause");
		system("cls");
	}
	return 0;
 } 

说实话写这个预测分析表方法时候我被我自己写晕了,尤其是传递指针时候。char、char*与string转换时候感觉脑袋不够用了,要崩溃。最后发现实力不行,把终结表也一并改为char类型,才实现成功。但看代码还是不舒服,至此希望大佬可以在下面留言指导一番也可以直接发邮箱欢迎骚扰,感激不尽。在此与大家分享一个感觉有点厉害的代码:预测分析表生成

 

其他文章:流缓冲socket编程基础知识TCP/IP协议词法分析程序设计实现代码


更多资讯可收藏→→北华航天工业学院——小博主花生

发表评论

电子邮件地址不会被公开。 必填项已用*标注