parser.cpp

图形软件,用QT编写的,可以用来学习软件的

	}catch(errBadConstant){
		// bad constant....
	}

	if(context.bForceUnknownTermExecption)throw errParseWrongExpression(3);

	{
		pti_vec ret;
		PTI_Unknown *unknown = new PTI_Unknown;
		trash[unknown] = 1;
		ret.push_back(unknown);
		unknown->str = string(start,end);
		unknown->parent = 0;
		return ret;
	}
}



void scan_trash(const pti_vec &pti_root,tpt_trash &trash){
	for(pti_vec::const_iterator i = pti_root.begin();i != pti_root.end();i++){
		trash.erase(*i);
		scan_trash((*i)->childs,trash);
	}
}

void free_trash(tpt_trash &trash){
	for(tpt_trash::const_iterator i = trash.begin();i != trash.end();i++){
		delete (*i).first;
//		cout << ".";
	}
	trash.clear();
}

void free_ptree(pti_vec &pti_root){
	for(pti_vec::const_iterator i = pti_root.begin();i != pti_root.end();i++){
		free_ptree((*i)->childs);
		delete *i;
	}
}
void free_ptree(bPTI *pti){
	pti_vec vec;
	vec.push_back(pti);
	free_ptree(vec);
}

pti_vec copy_ptree(const pti_vec &r){
	pti_vec ret;
	for(pti_vec::const_iterator i = r.begin();i != r.end();i++){
		ret.push_back((*i)->createCopy());
	}
	return ret;
}

bPTI *copy_ptree(const bPTI *p){
	return p->createCopy();
}

void undeclare_argument(ParsingContext &context,string name){
	int ok = 1;
	while(ok){
		ok = 0;
		for(vector<FunctionDeclaration>::iterator i = context.func_decl.begin();i != context.func_decl.end();i++){
			FunctionDeclaration &d = *i;
			if(d.name == name && d.nleft_Params == 0 && d.nright_Params == 0){
				context.func_decl.erase(i);
				ok = 1;
				break;
			}
		}
	}
	while(ok){
		ok = 0;
		for(vector<VariableDeclaration>::iterator i = context.var_decl.begin();i != context.var_decl.end();i++){
			VariableDeclaration &d = *i;
			if(d.name == name){
				context.var_decl.erase(i);
				ok = 1;
				break;
			}
		}
	}
}


// why C++ doesn't support functions inside another function???
// who knows... maybe it'll be better to make this and RParse
// functions inside Parse one.

static int cmpfuncs(FunctionDeclaration a,FunctionDeclaration b){
	return a.priority < b.priority;
}

pti_vec Parse(const char *equation,ParsingContext context){
	vector<BracketDeclaration> mybrck_decl = context.brck_decl;
	copy(context.fbrck_decl.begin(),context.fbrck_decl.end(),back_inserter(mybrck_decl));
	BracketCounter brkCnt(equation,mybrck_decl);

	sort(context.func_decl.begin(),context.func_decl.end(),cmpfuncs);

	tpt_trash trash;
	pti_vec ret;
	try{
		ret = RParse(equation,equation+strlen(equation),brkCnt,context,trash);
		scan_trash(ret,trash);
	}
        catch(...){
                free_trash(trash);
                throw;
        }
	free_trash(trash);
	return ret;
}


mashineCode &mashineCode::push_byte(byte x){push_back(x);return *this;}
mashineCode &mashineCode::code(byte x){return push_byte(x);}
mashineCode &mashineCode::push_bytes(byte *x,int len){for(int i = 0;i < len;i++)push_byte(x[i]);return *this;}
mashineCode &mashineCode::push_word(word x){push_bytes((byte *)&x,sizeof(x));return *this;}
mashineCode &mashineCode::push_dword(dword x){push_bytes((byte *)&x,sizeof(x));return *this;}
mashineCode &mashineCode::push_ptr(void *x){push_bytes((byte *)&x,sizeof(x));return *this;}

mashineCode::mashineCode(){
	mem = codes = 0;
}
mashineCode::~mashineCode(){
	Free();
}
//void mashineCode::execute(void){
//}
void mashineCode::Free(void){
	if(mem)delete mem;mem = 0;
}
void mashineCode::Init(void){
	Free();
	mem = new byte[size()+4];
	codes = mem;		
	copy(begin(),end(),codes);
//	while(((int)codes & 3))codes++;//DWORD aligment optimization	
}

int PreCalcOptimize(pti_vec &vec,FunctionExecutor &exec){
	int noptimizations = 0;
	pti_vec::iterator i;
	for(i = vec.begin();i != vec.end();i++)
		noptimizations += PreCalcOptimize((*i)->childs,exec);

	for(i = vec.begin();i != vec.end();i++){
		bPTI &bpti = *(*i);
		if(bpti.myType == bPTI::Function || bpti.myType == bPTI::Brackets){
			PTI_Function &myfunc = (PTI_Function &)(bpti);
			PTI_Brackets &mybrck = (PTI_Brackets &)(bpti);
			int ok = 1;
			stack<double> vals;
			for(pti_vec::iterator j = bpti.childs.begin();j != bpti.childs.end();j++){

				if((*j)->myType != bPTI::RealConstant){
					ok = 0;					
					break;
				}else{
					PTI_RealConstant* aconst =(PTI_RealConstant*)(*j);
					vals.push(aconst->value);
				}
			}
			if(bpti.myType == bPTI::Function && myfunc.declaration.skipPreCalcOptimization)
				ok = 0;
			if(ok){
				PTI_RealConstant *myconst = new PTI_RealConstant;
				myconst->value = 
					((bpti.myType == bPTI::Function) 
					? exec.Execute(myfunc.declaration,vals) 
					: exec.Execute(mybrck.declaration,vals));



				free_ptree(*i);

				*i = (bPTI *)myconst;
				noptimizations++;
			}
		}
	}
	return noptimizations;
}

void SubstituteVar(pti_vec &where,const string &varname,const bPTI *subst,set<bPTI *> *substituted = 0){
	for(pti_vec::iterator i = where.begin();i != where.end();i++){
		if(substituted == 0 || substituted->find(*i) == substituted->end()){
			if((*i)->myType == bPTI::Variable){
				PTI_Variable *v = (PTI_Variable *)(*i);
				if(v->declaration.name == varname){
					free_ptree(*i);
						bPTI *ptree_copy = copy_ptree(subst);
					if(substituted)
						substituted->insert(ptree_copy);
					(*i) = ptree_copy;

				}
			}else{
				SubstituteVar((*i)->childs,varname,subst,substituted);
			}
		}
	}
}
void SubstituteVar(bPTI *where,const string &varname,const bPTI *subst,set<bPTI *> *substituted = 0){
	pti_vec where2;
	where2.push_back(where);
	SubstituteVar(where2,varname,subst,substituted);
}

void SubstituteFunction(pti_vec &where,const UserFunction &function){
/*	cout << function.declaration.name << "\n";
	cout << function.declaration.nleft_Params << "\n";
	cout << function.declaration.nright_Params << "\n";
	cout << function.declaration.priority << "\n";*/
//	function.definition->print();
	//pti_vec::iterator i;
	unsigned int i = 0;
	for(i = 0;i < where.size();i++){
		if(where[i]->myType == bPTI::Function){
			PTI_Function *func = (PTI_Function *)where[i];
			if(func->declaration.name == function.declaration.name &&
				func->declaration.nleft_Params == function.declaration.nleft_Params &&
				func->declaration.nright_Params == function.declaration.nright_Params){
					pti_vec definition = copy_ptree(function.definition);
					set<bPTI *> substituted;
					for(int j = 0;j < func->declaration.nright_Params + func->declaration.nleft_Params;j++){
						SubstituteVar(definition,function.vars[j],func->childs[j],&substituted);
					}
					free_ptree(func);
					for(unsigned int k = 0;k < definition.size();k++){
						where.insert(where.begin()+i++,definition[k]);
					}
					where.erase(where.begin()+i--);
					//(*i) = definition;
				}
		}
	}
	for(i = 0;i < where.size();i++){
		SubstituteFunction(where[i]->childs,function);
	}
}


int ArithOptimizeHelper::IsFunction(bPTI &bpti,char *name,int left,int right){
	PTI_Function &myfunc = (PTI_Function &)(bpti);
	if(	bpti.myType							== BaseParsingTreeItem::Function &&
		myfunc.declaration.name				== name && 
		myfunc.declaration.nleft_Params		== left && 
		myfunc.declaration.nright_Params	== right)
	{
		return 1;
	}
	return 0;
}

int ArithOptimizeHelper::IsConstant(bPTI &bpti,double val)
{
	PTI_RealConstant &myconst = (PTI_RealConstant &)bpti;
	if(	bpti.myType							== BaseParsingTreeItem::RealConstant &&
		fabs(myconst.value - val) <= 0.000000000001)
///bad style - hardcoded constant
//but it's an optimization so it's allowed here
	{
		return 1;
	}
	return 0;
}

/*int ArithmeticOptimize(pti_vec &vec){
	return 0;
}*/
int ArithmeticOptimize(pti_vec &vec){
	using namespace ArithOptimizeHelper;
	int noptimizations = 0;
	pti_vec::iterator i;
	for(i = vec.begin();i != vec.end();i++)
		noptimizations += ArithmeticOptimize((*i)->childs);

	for(i = vec.begin();i != vec.end();i++){
		bPTI &bpti = *(*i);
		if(IsFunction(bpti,"-",0,1) && 
			IsFunction(*(bpti.childs[0]),"-",0,1) ) 
		{
			bPTI *node = &bpti;
			bPTI *mychild1 = node->childs[0];
			(*i) = mychild1->childs[0];
			delete mychild1;
			delete node;
			noptimizations++;
			continue;
		}

		if(IsFunction(bpti,"+",0,1))
		{
			bPTI *node = &bpti;
			(*i) = bpti.childs[0];
			delete node;
			noptimizations++;
			continue;
		}
		if(IsFunction(bpti,"+",1,1) || IsFunction(bpti,"-",1,1)){
			if(IsConstant(*(bpti.childs[0]),0.)){
				(*i) = bpti.childs[1];
				free_ptree(bpti.childs[0]);
				delete &bpti;
				noptimizations++;
				continue;
			}
			if(IsConstant(*(bpti.childs[1]),0.)){
				(*i) = bpti.childs[0];
				free_ptree(bpti.childs[1]);
				delete &bpti;
				noptimizations++;
				continue;
			}
		}
		if(IsFunction(bpti,"*",1,1)){
			if(IsConstant(*(bpti.childs[0]),1.)){
				(*i) = bpti.childs[1];
				free_ptree(bpti.childs[0]);
				delete &bpti;
				noptimizations++;
				continue;
			}
			if(IsConstant(*(bpti.childs[1]),1.)){
				(*i) = bpti.childs[0];
				free_ptree(bpti.childs[1]);
				delete &bpti;
				noptimizations++;
				continue;
			}
			if(IsConstant(*(bpti.childs[0]),0.)){
				(*i) = bpti.childs[0];
				free_ptree(bpti.childs[1]);
				delete &bpti;
				noptimizations++;
				continue;
			}
			if(IsConstant(*(bpti.childs[1]),0.)){
				(*i) = bpti.childs[1];
				free_ptree(bpti.childs[0]);
				delete &bpti;
				noptimizations++;
				continue;
			}
		}
	}
	return noptimizations;
}

// Context of execution
// Variables,temporaries and code goes here
ExecutionContext::ExecutionContext(){
	codes = 0;
}
ExecutionContext::~ExecutionContext(){
	Free();
}
void ExecutionContext::Free(void){
	while(tempTrash.size())tempTrash.pop();
	if(codes)delete codes;
	codes = 0;
}
double *ExecutionContext::AllocTemporary(double value){
	double *r = new double;
	*r = value;
	tempTrash.push(r);
	return r;
}

// When optimizer needs to do constant precalculation(like 1+2)
// then it calls +(1,1) throught this interface
FunctionExecutor::FunctionExecutor(){}
FunctionExecutor::~FunctionExecutor(){}
/*
+ Parser
+ Constant optimizer
+ Variables substitution
+ Function substitution
+ arithmetic optimizer
*/