dn转换.cpp

编译原理 ：预测分析

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<ctype.h>
#include<process.h>
#include<bitset>
#include<vector>
using namespace std;

//边结点
typedef struct Node{
	int verIndex;
	char st[100];
	struct Node* nextArc;
}Edge;

//状态节点类型
#define START_NODE 1
#define END_NODE 2
#define NORMAL_NODE 3

//状态结点
typedef struct{
	char ver;
	int type;
	Edge* firstArc;
}Vertex;

//最大的顶点数
#define MAX_VERTEX_NUM 100

//最大的字母数
#define MAX_LETTER_NUM 400

#define MAX_TALBE_SIZE 100

typedef bitset<MAX_VERTEX_NUM> VertexSet;

//图类型
typedef struct{
	Vertex vertexs[MAX_VERTEX_NUM];
	int vertexNum;

	char alphaBeta[MAX_LETTER_NUM];
	int letterNum;
	char st[400]; //存放输入的正则表达式
	
	//产生状态集合表
	VertexSet table[MAX_TALBE_SIZE];
	int row;  //表的行数
	char charTable[MAX_TALBE_SIZE];
	bool isEnd[MAX_TALBE_SIZE]; //记录表中每行首结点是否为终结点
}Graph;

//初始化图
void Init(Graph* G){
	for(int i = 0 ; i < MAX_VERTEX_NUM;i++)
		G->vertexs[i].firstArc = NULL;
	G->vertexNum = 0;

}

//返回图中第i个结点字符
char LocateVer(Graph* G,int i){
	if(i <0 || i>=G->vertexNum) return '\0';
	return G->vertexs[i].ver;
}

//图搜索时的访问标志
#define VISITED 1
#define NONVISITED 0
//访问标志数组
int visited[MAX_VERTEX_NUM];

//深度优先输出
void DFS(Graph* G,int startVer){
	visited[startVer] = VISITED;
	Edge* p;
	p = G->vertexs[startVer].firstArc;
	while(p != NULL){
		if(!visited[p->verIndex]){
			printf("%c --->\" %s \" ---->%c\n",
				LocateVer(G,startVer),p->st,LocateVer(G,p->verIndex));
			DFS(G,p->verIndex);
		}
		p = p->nextArc;
	}
}

//深度优先搜索
void DFS_output(Graph* G){
	for(int i = 0 ; i < G->vertexNum;i++)
		visited[i] = NONVISITED;
	for(i = 0 ; i< G->vertexNum;i++)
		if(!visited[i]) DFS(G,i);
}

//按顶点顺序打印图中每一条边
void printGraph(Graph* G){
	printf("\n\n1. 转换成NFA如下 \n");
	for(int i = 0; i < G->vertexNum;i++){
		Edge* p = G->vertexs[i].firstArc;
		while(p != NULL){
			printf("%c --->\" %s \" ---->%c\n",
				LocateVer(G,i),p->st,LocateVer(G,p->verIndex));
			p = p->nextArc;
		}
	}
	printf("\n\n\n");

}

//向图中位置pos处，插入一个名称为c,类型为type的顶点
void InsertVertext(Graph* G,int pos,char c,int type){
	if(pos < 0 || pos > G->vertexNum) {
		printf("****** 插入位置不合法! ***********\n");
		return;
	}
	if(G->vertexNum == MAX_VERTEX_NUM){
		printf("****** 图中节点数已达到最大值，无法插入! *********\n");
		return;
	}

	for(int i = 0 ; i < G->vertexNum;i++){
		Edge* p = G->vertexs[i].firstArc;
		while(p != NULL){
			if(p->verIndex >= pos) p->verIndex ++;
			p = p->nextArc;
		}
	}

	G->vertexNum++;
	for(i = G->vertexNum; i >pos ;i--)
		G->vertexs[i] = G->vertexs[i-1];
	G->vertexs[pos].firstArc = NULL;
	G->vertexs[pos].ver = c;
	G->vertexs[pos].type = type;
}

//输出状态集合set
void outputSet(Graph* G,VertexSet set){
	printf("{");
	for(int i = 0 ; i < G->vertexNum;i++)
		if(set.test(i)) printf(" %c ",LocateVer(G,i));
	printf("}");
}

//用深度优先搜索返回 ver 的ε闭包
VertexSet CloserDFS(Graph* G,int ver){
	VertexSet result;
	Edge* p = G->vertexs[ver].firstArc;
	visited[ver] = VISITED;
	result.set(ver);
	while(p != NULL){
		if(strcmp(p->st,"ε") == 0){			
			if(!visited[p->verIndex]) 
				result |= CloserDFS(G,p->verIndex);
		}
		p = p->nextArc;
	}
	return result;
}

//返回顶点ver的ε闭包
VertexSet Closer(Graph* G,int ver){
	for(int i = 0 ; i < G->vertexNum;i++)
		visited[i] = NONVISITED;
    return CloserDFS(G,ver);	 
}

//返回图G中顶点集合s通过一次ch弧所能到达的顶点集
VertexSet SetThrough(Graph* G,const VertexSet& s,char ch){
	VertexSet result;
	for(int i = 0 ; i < G->vertexNum;i++){
		if(s.test(i)) {
			Edge* p = G->vertexs[i].firstArc;
			while(p != NULL){
				if(p->st[0] == ch)
					result.set(p->verIndex);
				p = p->nextArc;
			}
		}
	}
	return result;
}

//集合b关于字符ch的Ich闭包
VertexSet Move(Graph* G,VertexSet& b,char ch){
	VertexSet  result;

	//存放G中每个状态的?闭包
	vector<VertexSet> v(G->vertexNum,result);
	for(int i = 0 ; i < G->vertexNum;i++)
		v[i] = Closer(G,i);
	
	result = SetThrough(G,b,ch);
	VertexSet tmpSet;
	for( i = 0 ; i < G->vertexNum;i++)
		if(result.test(i)) tmpSet |= v[i];
	result |= tmpSet;

	return result;
}

//输出图G的状态表
void outputStatesTable(Graph* G){
	int col = G->letterNum + 1;
	for(int i = 0; i < G->row ; i++){
		for(int j = 0 ; j < col;j++){
			int index = i * col + j;
			outputSet(G,G->table[index]);
			printf("\t");
		}
		printf("\n");
	}
}

//建图的DFA状态表
void BuildSituTable(Graph* G){
	int col = G->letterNum + 1;
	int row = 0;
	int k = 0;
	G->table[0] = Closer(G,0);
	while(1){
		//处理一行
		G->table[row*col] = G->table[k];
		for(int i = 1; i < col;i++)
			G->table[row*col + i] = Move(G,G->table[k],G->alphaBeta[i-1]);
		row++;

		//判断是否要结束
		int next = k;
		bool find = false;
		for(int j = k + 1; j < row*col && !find; j++){
			if(G->table[j].count() == 0) continue;
			for(int m = 0; m < row ; m++)
				if(G->table[m*col] == G->table[j]) break;
			if(m == row) find = true;
		}
		if(!find) break;
		k = j - 1;
	}
	G->row = row;
}

//去掉字符串中的空格
void Trim(char st[]){
	for(int i = 0 ; st[i];)
		if(isspace(st[i])){
			for(int j = i;st[j];j++)
				st[j] = st[j+1];
		}
		else i++;
}

//去掉字符串最外层多余的括号
void DeleteBrackets(char st[]){
	int a = 0;
	int b = strlen(st) - 1;
	int k = 0;

	while(st[0] == '('){
		int k = 1;
		for(int i = 1 ; st[i] && k != 0; i++){
			if(st[i] == '(') k++;
			if(st[i] == ')') k--;
		}
		if(st[i-1] != ')' || st[i] != '\0') break;
		st[i - 1] = '\0';
		strcpy(st,st+1);
	}
}

//判断顶点下标是否合法
bool isLegal(Graph* G,int ver){
	return ver>=0 && ver< G->vertexNum;
}

//在图中添加一条 ver-->toVer的边
void AddEdge(Graph* G,int ver,int toVer,char st[]){
	if(!isLegal(G,ver) || !isLegal(G,toVer)){
		printf("***** (%d-->%d) 顶点下标越界! **********\n",ver,toVer);
		return;
	}


	Edge* p = (Edge*)malloc(sizeof(Edge));
	strcpy(p->st,st);
	p->verIndex = toVer;
	p->nextArc = G->vertexs[ver].firstArc;
	G->vertexs[ver].firstArc = p;
}

//在图中删除一条边
void DeleteEdge(Graph* G,int pos,Edge* p){
	if(!isLegal(G,pos)) {
		printf("***** (%d) 顶点下标越界! **********\n",pos);
		return;
	}
	
	if(G->vertexs[pos].firstArc == NULL) return;
	if(G->vertexs[pos].firstArc == p){
		G->vertexs[pos].firstArc = p->nextArc;
	}
	else{
		for(Edge* q = G->vertexs[pos].firstArc;q->nextArc != NULL && q->nextArc != p;q = q->nextArc);
		if(q->nextArc != NULL) q->nextArc = p->nextArc;
		else {
			printf("**** 没有找到要删除的边! *****\n");
			return;
		}
	}
	free(p);
}

//分解字符串
char DivideStr(char st[],char firstSt[],char secondSt[]){
	int FI = 0;
	int k = 0;

	DeleteBrackets(st);
	if(isalnum(st[k])){
		while(isalnum(st[k])){
			firstSt[FI++] = st[k++];
		}
	}
	else if(st[0] == '('){				//n用来表示括号是否匹配
		int n = 1;
		firstSt[FI++] = '(';
		for(k = 1;n != 0; k++){
			if(st[k] == '(') n++;
			else if(st[k] == ')') n--;
			firstSt[FI++] = st[k];
		}
	}
	else{
		printf("******  %s 非法开头字符 %c ***********\n",st,st[k]);
		return '!';
	}

	if(st[k] == '\0'){
		firstSt[0] = st[0];
		firstSt[1] = '\0';
		strcpy(secondSt,st+1);
		return '+';
	}

	if(st[k] == '*' ){
		k++;		
		if(st[k] == '\0'){
			firstSt[FI] = '\0';
			if(firstSt[FI - 1] == ')'){
				firstSt[--FI] = '\0';
				strcpy(firstSt,firstSt+1);
			}
			secondSt[0] = '\0';
			return '*';