symboltree.cpp

编译原理实验中的yacc源码

// SymbolTree.cpp: implementation of the SymbolTree class.
//
//////////////////////////////////////////////////////////////////////

#include <string.h>
#include <iostream.h>
#include "SymbolTree.h"

SymbolTree::SymbolTree(YaccLike* Yacc){
	tTree = utTree = NULL ;
	tIndex = utIndex = 0 ;
	yacc = Yacc ;
	constructT1() ;
	constructT2() ;
	yacc->numUTSymbol = utIndex ;
	yacc->numTSymbol = tIndex ;
}


SymbolTree::~SymbolTree(){
	Delete(tTree) ;
	Delete(utTree) ;
}

//往树中插入一个结点
bool SymbolTree::insert(BST& t, char* s, int& index){
	if(strcmp(s, "epsilon")==0) return false; //树(终结符树)中不包含epsilon
	if(t == NULL){
		t = new BSTNode ;
		strncpy(t->symbol, s, MAX_SMB_LEN) ;
	    t->left = t->right = NULL ;
		t->index = index ;
		return true ;
	}else{
		int m = strcmp(s, t->symbol) ;
		if(m==0) return false ;
		else if(m<0) return insert( t->left, s, index ) ;
		else return insert( t->right, s, index ) ;
	}
}

//查找文法所在的位置
int SymbolTree::lookup(char* s, BST T){
	BST t = T ;
	while(t!=NULL){
		int m = strcmp(s, t->symbol) ;
		if(m==0) return t->index ;
		else if(m<0) t = t->left ;
		else t = t->right ;
	}
	return -1 ;
}

//建立非终结符二元查找树
void SymbolTree::constructT1(){
	for(int i=0; i<yacc->numProd; i++){
		if( insert(utTree, yacc->prodution[i].symbol, utIndex) ) 
			strncpy(yacc->utSymbol[utIndex++], yacc->prodution[i].symbol, MAX_SMB_LEN) ;
	}
}

//建立终结符二元查找树
void SymbolTree::constructT2(){
	ifstream in("symbol.in") ;
	char buf[128] ;
	while(in.getline(buf, 128, '\n')){
		insert(tTree, buf, tIndex) ;
		strncpy(yacc->tSymbol[tIndex++], buf, MAX_SMB_LEN) ;
	}
	insert(tTree, "$", tIndex) ;
	strcpy(yacc->tSymbol[tIndex++], "$") ;
}

//删除树
void SymbolTree::Delete(BST t){
	if(t!=NULL){
		Delete(t->left) ;
		Delete(t->right) ;
		delete t ;
	}
}