yacc.cpp

编译原理实验中的yacc源码

// yacc.cpp: implementation of the YaccLike class.
//
//////////////////////////////////////////////////////////////////////
#include <iostream.h>
#include <string.h>
#include <fstream.h>
#include <assert.h>
#include <ctype.h>
#include "yacc.h"

//初始化内存，读入文法，建立终结符二查树
YaccLike::YaccLike(char* fileName){
	numUTSymbol = numProd = 0 ;
	//内存初始化
	memset(prodution, 0 , sizeof(prodution)) ;
	memset(firstSet, 0, sizeof(firstSet)) ;
	memset(followSet, 0, sizeof(followSet)) ;
	//读入原方法并建立产生式的TOKEN字序列
	readCFGFile(fileName) ; 
	//根据产生式的TOKEN字序列建立文法树
	Tree = new SymbolTree(this) ;  
	//为LL1分析表申请空间,并初始化为0
	tableLL1 = new int*[numUTSymbol] ;
	for(int i=0; i<numUTSymbol; i++){ 
		tableLL1[i] = new int[numTSymbol+1] ;
		memset(tableLL1[i], 0, sizeof(int)*(numTSymbol+1)) ;
	}
	
}

//--------------------------------------------------------------------
YaccLike::~YaccLike(){
	delete Tree ;					//删除方法符号二查树
	Delete(firstSet, numUTSymbol) ;	//删除FIRST集
	Delete(followSet, numUTSymbol) ;//删除FOLLOW集
	Delete(prodution, numProd) ;	//删除产生式
	//删除LL1表
	for(int i=0; i<numUTSymbol; i++) delete []tableLL1[i] ;
	delete []tableLL1 ;
}

//--------------------------------------------------------------------
//一些清理工作
template <class T>
void YaccLike::Delete(T p, int k){
	for(int i=0; i<k; i++){
		CFGSymbol *s, *t ;
		t = s = p[i].firstSymbol ;
		while(s){
			t = s ;
			s = s->next ;
			delete t ;
		}
	}
}//Delete() 

//--------------------------------------------------------------------
//读入原文法
void YaccLike::readCFGFile(char* fileName){
	ifstream inFile(fileName, ios::in) ;
	assert(inFile) ;
	int i = 0 ;
	char buf[128], *p ;
	CFGSymbol *s, *t ;
	while(inFile.getline(buf, 128, '\n')){	
		int j=0 ;
		strcpy(prod[i], buf) ;
		//以空格为分隔符，产生TOKEN字，建立产生式链表
		for(p=strtok(buf, " "); p!=NULL; p=strtok(NULL, " "),j++){
			if(j==0) { 
				strcpy(prodution[i].symbol, p) ;
			}else if(j>1){
				s = new CFGSymbol ;
				strcpy(s->symbol, p) ;
				s->next = NULL ;
				if(j==2) t = prodution[i].firstSymbol = s ;
				else t = t->next = s ;
			}//if		
		}
		if( j==3 && strcmp((prodution[i].firstSymbol)->symbol, "epsilon") == 0 )
			prodution[i].eps = true ;
		i++ ;
	}
	numProd = i ;
}

//--------------------------------------------------------------------
//判断一个方法符号是不是非终结符
int YaccLike::isUTSymbol(char* s){
	return Tree->lookup(s, Tree->utTree) ;
}

//--------------------------------------------------------------------
//建立FIRST集
void YaccLike::first(){
	while(1){
		int larged = 0 ; //每一轮加入到FIRST集合中的终结符的个数
		for(int i=0; i<numProd; i++){
			int index = Tree->lookup(prodution[i].symbol, Tree->utTree) ;
			CFGSymbol *p = prodution[i].firstSymbol ; 
			while(p){
				int idx = isUTSymbol(p->symbol) ; 
				if( idx == -1 ){  //当前文法符号是终结符 
					if( strcmp(p->symbol, "epsilon") != 0 ){ //且不是epsilon
						larged += addToSet(firstSet, index, p->symbol) ;
						break ;
					}
				}else{
					CFGSymbol *q = firstSet[idx].firstSymbol ;
					bool eps = false ;
					while(q){
						if( strcmp(q->symbol, "epsilon") != 0 ) 
							larged += addToSet(firstSet, index, q->symbol) ;
						else eps = true ;
						q = q->next ;
					}
					if(!eps) break ;
				}
				p = p->next ;
			}//while
			if(p == NULL) 
				larged += addToSet(firstSet, index, "epsilon") ;
		}//for
		if(larged == 0) break ; //没有新的终结符加入，退出循环
	}//while
}//first()

//--------------------------------------------------------------------
//建立FOLLOW表
void YaccLike::follow(){
	addToSet(followSet, 0, "$") ;	//把$放入开始符的FOLLOW集中
	while(1){ //while0
		int larged = 0 ;
		for(int i=0; i<numProd; i++){
			int index = Tree->lookup(prodution[i].symbol, Tree->utTree) ;
			CFGSymbol* p = prodution[i].firstSymbol ;
			while(p){//while1
				int idx = Tree->lookup(p->symbol, Tree->utTree) ; 
				if(idx != -1){ //当前文法符号是非终结符,则进行如下处理
					if(p->next == NULL){//是最后一个文法符号
						CFGSymbol* q = followSet[index].firstSymbol ;
						//产生式A->alpha B 则把FOLLOW(A)中所有符号放入FOLLOW(B)　
						while(q){
							larged += addToSet(followSet, idx, q->symbol) ;
							q = q->next ;
						}
					}else{ //不是最后一个文法符号,对于产生式A -> alpha B beta 　
						CFGSymbol* q = p->next ;
						//把FIRST(beta)中的除epsilon的符号放入FOLLOW(B) 
						while(q){//while2
							int dx = isUTSymbol(q->symbol) ;
							if(dx==-1){ //当前文法符号是终结符
								if( strcmp(p->symbol, "epsilon") != 0 ){ //且不是epsilon
									larged += addToSet(followSet, idx, q->symbol) ;
									break ;
								}
							}else{
								CFGSymbol *r = firstSet[dx].firstSymbol ;
								bool eps = false ;
								while(r){
									if(strcmp(r->symbol, "epsilon")!=0) 
										larged += addToSet(followSet, idx, r->symbol) ;
									else eps = true ;
									r = r->next ;
								}
								if(!eps) break ;
							}//if
							q = q->next ;
						}//while2
						if(q==NULL){//说明FIRST(beta)中包含epsilon,则把FOLLOW(A)中的全部符号放入FOLLOW(B)
							CFGSymbol* t = followSet[index].firstSymbol ;
							while(t){
								larged += addToSet(followSet, idx, t->symbol) ;
								t = t->next ;
							}
						}
					}//if
				}
				p = p->next ;
			}//while1
		}//for
		if(larged == 0) break ;
	}//while0
}//follow()

//--------------------------------------------------------------------
//把终结符添加到FIRST集中去，若终结符已经存在，
//那么不加入而返回0,否则返回1,返回值用作计数
int YaccLike::addToSet(Set* point, int index, char* s){
	CFGSymbol *t ;
	t = point[index].firstSymbol ;
	while(t){
		if(strcmp(t->symbol, s)==0) return 0 ;
		t = t->next ;
	}
	t = new CFGSymbol ;
	strcpy(t->symbol, s) ;
	t->next = point[index].firstSymbol ;
	point[index].firstSymbol = t ;
	return 1 ;
}

//--------------------------------------------------------------------
//把first , follow集写入文件
void YaccLike::writeToFile(char* filename, char* s, Set* point){
	ofstream outFile(filename, ios::out) ;
	CFGSymbol *t, *tmp ;
	outFile<<s<<'\t'<<"终结符"<<endl ;
	for(int i=0; i<numUTSymbol; i++){
		outFile<<utSymbol[i]<<'\t' ;
		t = point[i].firstSymbol ;
		while(t){
			outFile<<t->symbol<<'\t' ;
			tmp = t ;
			t = t->next ;
		}
		outFile<<'\n' ;
	}
}

//--------------------------------------------------------------------
//建立LL1分析表
bool YaccLike::LL1Table(){
	for(int i=0; i<numProd; i++){//产生式A->alpha
		int index = Tree->lookup(prodution[i].symbol, Tree->utTree) ;
		CFGSymbol* p = prodution[i].firstSymbol ;
		while(p){
			int idx = isUTSymbol(p->symbol) ;
			if(idx == -1){//当前文法符号是终结符
				int dx = Tree->lookup(p->symbol, Tree->tTree) ;
				if( dx != -1 ){ //不是epsilon
					if(tableLL1[index][dx] == 0) tableLL1[index][dx] = i+1 ;
					else {
						cout << "ERROR1 : " << "产生式" << i+1 << prod[i] << "发生不可修正冲突" ;
						return false ;
					}
					break ;
				}
			}else{//当前文法符号不是终结符
				CFGSymbol *r = firstSet[idx].firstSymbol ;
				bool eps = false ;
				while(r){
					int dx = Tree->lookup(r->symbol, Tree->tTree) ;
					if( dx != -1 ){//不是epsilon
						if(tableLL1[index][dx] == 0) tableLL1[index][dx] = i+1 ;
						else{
							cout << "ERROR1 : " << "产生式" << i+1 << prod[i] << "发生不可修正冲突" ;
							return false ;
						}
					}
					else eps = true ;
					r = r->next ;
				}
				//当前方法符号的FIRST集不含有epslion , 则结束循环
				if(!eps) break ; 
			}
			p = p->next ;
		}//while
		//p = NULL , 则说明epsilon在FIRST(alpha)中，
		//把产生式加入FOLLOW(A)中的LL1分析表中每个终结符所在列
		if(p == NULL){
			CFGSymbol* t = followSet[index].firstSymbol ;
			while(t){
				int dx = Tree->lookup(t->symbol, Tree->tTree) ;
				if(tableLL1[index][dx] == 0) tableLL1[index][dx] = i+1 ;
				else{//发生冲突
					 //若此时欲填入的是一个空产生式，则简单删除之以消除重复项
					 //若此时表中有一个空产生式，则删除已有空产生式，填入该产生式
					if(prodution[i].eps){ 
						cout << "ERROR2 : " << "产生式" << i+1 << prod[i] << "发生可修正冲突, "  ;
						cout << "在LL1表中删除此空产生式" << endl ;
					}else if(prodution[tableLL1[index][dx]].eps){
						cout << "ERROR2 : " << "产生式" << i+1 << prod[i] << "发生可修正冲突, "  ;
						cout << "在LL1表中删除空产生式" << prod[tableLL1[index][dx]] << endl ;
					}else{
						cout << "ERROR1 : " << "产生式" << i+1 << prod[i] << "发生不可修正冲突" ;
						return false ;
					} 
				}
				t = t->next ;
			}
		}
	}//for
	return true ;
}

//----------------------------------------------------------------------
void YaccLike::writeLL1File(char* filename){
	ofstream out(filename) ;
	out << "终结符\t输入符号\n\t" ;
	for(int i=0; i<numTSymbol; i++) 
		out << tSymbol[i] << '\t' ;
	out << '\n' ;
	
	for(i=0; i<numUTSymbol; i++){
		out << utSymbol[i] << '\t' ;
		for(int j=0; j<numTSymbol; j++)
			out << (int)tableLL1[i][j] << '\t' ;
		out << '\n' ;
	}
}

//--------------------------------------------------------------------
//YACC程序开始
void YaccLike::start(){
	first() ;
	writeToFile("firstSet.xls", "First集", firstSet) ;
	cout << "\nFirst集生成结束,见firstSet.xls" << endl << endl;

	follow() ;
	writeToFile("followSet.xls", "Follow集", followSet) ;
	cout << "Follow集生成结束,见followSet.xls" << endl << endl ;

	if( !LL1Table() ) return ;
	cout << endl ;
	writeLL1File("LL1.xls") ;
	cout << "LL1预测分析表成功生成,见LL1.xls" << endl << endl ;
}