编译原理—算符优先分析法C++代码实现

编译原理—算符优先分析法C++代码实现 前言：

      写算法的时候，也搜索了不少大佬的笔记，感觉有些复杂，不太容易看懂。但还是借鉴了不少思想，再结合自己的所学，成功运行。本次设计的存储结构简单易懂，且适合新手，目前实现了FirstVt集，LastVt以及算符优先分析表的构造，主要还是利用从各自的构造思想入手。

算符优先分析法是一种自底向上的语法分析方法。在算符文法中，任何一个规则右部都不存在两个非终结符相邻的情况。通过比较两个相继出现的终结符a，b的优先级，然后借助优先级关系，来确定句型的可归约串并进行归约。通过构造FIRSTVT集和LASTVT集来构造算符优先分析表，从表中可以看出各终结符的优先关系。

主要概念：

FirstVt集如何构造：

若P→a…或P→Qa…, 则a属于FIRSTVT(P)

若P→Q…, 则FIRSTVT(Q)加到FIRSTVT(P)

直至FIRSTVT(P)不再增大。

LastVt构造：

若P→...a或P→…aQ, 则a属于LASTVT(P);

若P→...Q, 则LASTVT(Q)含于LASTVT(P);

直至LASTVT(P)不再增大。

 算符优先分析表构造：

1) ‘=’关系

-若出现了A →…ab…或A →…aBb, 则a=b；

2)‘<’关系

-求出每个非终结符B的FIRSTVT(B)，

-若A→…aB…,则 任意b∈FIRSTVT(B),a

3)‘>’关系

-求出每个非终结符B的LASTVT(B)，

-若A→…Bb…,则 任意a∈LASTVT(B),a>b

存储结构设计 ：

#include
#include
using namespace std;
#include
struct inf{
	char ter;//首非终结符 
	bool e;//是否产生空字符 
	string nonter;
}; 
vector  v;//产生式集合 
char a[10];
string T="";//非终结符集合 
string Vt="";//终结符集合 
string firstvt[20];
string lastvt[20];
char table[50][50];//算符优先关系表 

源代码：

（涉及到将文法转化为产生式。即将  E->aB|c  变为    E->aB   E->c）

//选择20、填空20、判断10、程序阅读25、设计题25  数据可视化 nowpy应用于机器学习 文件 *** 作 pandas  
#include
#include
using namespace std;
#include
struct inf{
	char ter;//首非终结符 
	bool e;//是否产生空字符 
	string nonter;
}; 
vector  v;//产生式集合 
char a[10];
string T="";//非终结符集合 
string Vt="";//终结符集合 
string firstvt[20];
string lastvt[20];
char table[50][50];//算符优先关系表 
void add();
//将文法转为产生式 
string produce(string str){
	inf infi;
    infi.ter = str[0];
	infi.e=false;
	int i = 3;
	for(int k=i;k='!'&&str[k]<='/'&&str[k]!='|')||(str[k]>='a'&&str[k]<='z')){
		Vt+=str[k];
	} 
    }
	v.push_back(infi);
	T=T+str[0]; 
	return infi.nonter;
}
//求firstvt集
void add_firstvt(int p,char ch){//对每一行产生式求 
	for(int i=0;ia...,则a属于 firstvt(A)
		if((str >= 'a'&&str <= 'z')||(str>='('&&str<='+')){
			firstvt[p] += str;
		}
		//A->Qa... ,则a属于 firstvt(A)
		if(lo+1<=e.nonter.length()-1){
			str2=e.nonter[1];
		if(str>='A'&&str<='Z'){
			if((str2 >= 'a'&&str <= 'z')||(str2>='!'&&str2<='/'))
		    firstvt[p] += str2;
			}
		}
		//A->B...,则firstvt(A)+=firstvt(B) 
		else if((str >= 'A'&&str <= 'Z')&&str!=e.ter&&str!=e.ter){
			int j = T.find(str);
			add_firstvt(j,str);
			firstvt[p].append(firstvt[j].substr(0));
			firstvt[j]="";
		}
	}
	}
} 
求last集 
void add_lastvt(int p,char a){
for(int i=0;i...a,则a属于 lastvt(A)
		if((str >= 'a'&&str <= 'z')||(str>='('&&str<='+')){
			lastvt[p] += str;
		}
		//A->...aQ ,则a属于 lastvt(A)
		if(lo!=0){
			str2=e.nonter[e.nonter.length()-2];
		if(str>='A'&&str<='Z'){
			if((str2 >= 'a'&&str <= 'z')||(str2>='!'&&str2<='/'))
		    lastvt[p] += str2;
			}
		}
		//A->...B,则lastvt(A)+=lastvt(B) 
		else if((str >= 'A'&&str <= 'Z')&&str!=e.ter&&str!=e.ter){
			int j = T.find(str);
			add_lastvt(j,str);
			lastvt[p].append(lastvt[j].substr(0));
			lastvt[j]="";
		}
	}
	}
}

//将空转符去掉,添加新的产生式 
void add(){
	int vsize=v.size();
	for(int i=0;i=0){             //找到 
						inf ind;
						string str=v[j].nonter;
						ind.e=false;
						ind.ter=v[j].ter;
						ind.nonter.append(str.substr(0,n));
						v.push_back(ind);
						continue; 
						}
					}
					
			}	
	}	
	
}
void print(){	
	for(int i=0;i"<=2){
				if(IsVt(ind.nonter[1])){
					x = FindSub(ind.nonter[0]);
					y = FindSub(ind.nonter[1]);
					cout<=3&&ind.nonter[1]>='A'&&ind.nonter[1]<='Z'&&IsVt(ind.nonter[2])){ //aQb
					x = FindSub(ind.nonter[0]);
					y = FindSub(ind.nonter[2]);
					table[x][y] = '=';
					}
					}
				}//'='结束 
				//若A→…aB…,则 任意b∈FIRSTVT(B),a=2){
					if(IsVt(ind.nonter[j])){
					int x=FindSub(ind.nonter[j]);
					if(ind.nonter[j+1]>='A'&&ind.nonter[j+1]<='Z'){
							int lod = T.find(ind.nonter[j+1]);
							for (int m = 0; m < firstvt[lod].length(); m++) {
								int y = FindSub(firstvt[lod][m]);
								table[x][y] = '<';
				}
					}
				}
				}//'<'结束 
//				若A→…Bb…,则 任意a∈LASTVT(B),a>b
				if(ind.nonter[j]>='A'&&ind.nonter[j]<='Z'){
					if(j+1<=ind.nonter.length()-1){
					if(IsVt(ind.nonter[j+1])){
						int x=FindSub(ind.nonter[j+1]);
							int lod = T.find(ind.nonter[j]);
							for (int m = 0; m < lastvt[lod].length(); m++) {
								int y = FindSub(lastvt[lod][m]);
								table[y][x] = '>';//竖着看 
				}
					}
				}
	}
		}
	}
}
int main(){
	string BefSource[3]={{"E->E+T|T"},{"T->T*F|F"},{"F->(E)|i"}};
    for(int i=0;i<3;i++) {
	cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5670917.html