parser.cpp

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

/*****************************************************************************
*******************************************************************************
**                                                                           **
**    equal III the graphic builder                                          **
**                                                                           **
**    Copyright (C) 2003 Oleksiy Pylypenko                                   **
**                                                                           **
** This file may be distributed and/or modified under the terms of the       **
** GNU General Public License version 2 as published by the Free Software    **
** Foundation and appearing in the file license included in the              **
** packaging of this file.                                                   **
**                                                                           **
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE   **
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. **
**                                                                           **
** Contact [e-mail] if any conditions of this licensing are         **
** not clear to you.                                                         **
**                                                                           **
**                                                                           **
*******************************************************************************
 *****************************************************************************/

#include "equal_headers.h"
#include "parser.h"
// Some classes declaration

// Base parsing tree item
BaseParsingTreeItem *BaseParsingTreeItem::createCopy(void) const{
	assert(0);
	return new BaseParsingTreeItem;
}
void BaseParsingTreeItem::print(int level){
	for(int j = 0;j < level;j++)cout << " ";
	cout << "\n";
	for(vector<BaseParsingTreeItem *>::iterator i = childs.begin();i != childs.end();i++){
		(*i)->print(level+1);
	}
}
BaseParsingTreeItem::~BaseParsingTreeItem(){
}

// Some parseing tree items(PTI)
PTI_Function::PTI_Function(){myType = Function;}
BaseParsingTreeItem *PTI_Function::createCopy(void) const{
	PTI_Function *pti = new PTI_Function;
	pti->myType = myType;
	pti->declaration = declaration;
	pti->parent = 0;
	for(pti_vec::const_iterator i = childs.begin();i != childs.end();i++){
		BaseParsingTreeItem *bpti = (*i)->createCopy();
		pti->childs.push_back(bpti);
		pti->parent = pti;
	}
	return pti;
}
void PTI_Function::print(int level){
	for(int j = 0;j < level;j++)cout << " ";
	cout << declaration.name <<  "(" << declaration.nleft_Params << "," << declaration.nright_Params << ")\n";
	for(vector<BaseParsingTreeItem *>::iterator i = childs.begin();i != childs.end();i++){
		(*i)->print(level+1);
	}
}



PTI_Variable::PTI_Variable(){myType = Variable;}
BaseParsingTreeItem *PTI_Variable::createCopy(void) const{
	PTI_Variable *pti = new PTI_Variable;
	pti->myType = myType;
	pti->declaration = declaration;
	pti->parent = 0;
	return pti;
}
void PTI_Variable::print(int level){
	for(int j = 0;j < level;j++)cout << " ";
	cout << declaration.name <<  "\n";
	assert(childs.size() == 0);
}


PTI_RealConstant::PTI_RealConstant(){myType = RealConstant;}
BaseParsingTreeItem *PTI_RealConstant::createCopy(void) const{
	PTI_RealConstant *pti = new PTI_RealConstant;
	pti->myType = myType;
	pti->parent = 0;
	pti->value = value;
	return pti;
}
void PTI_RealConstant::print(int level){
	for(int j = 0;j < level;j++)cout << " ";
	cout << value << "\n";
	assert(childs.size() == 0);
}

PTI_Brackets::PTI_Brackets(){myType = Brackets;}
BaseParsingTreeItem *PTI_Brackets::createCopy(void) const{
	PTI_Brackets *pti = new PTI_Brackets;
	pti->myType = myType;
	pti->declaration = declaration;
	pti->parent = 0;

	for(pti_vec::const_iterator i = childs.begin();i != childs.end();i++){
		BaseParsingTreeItem *bpti = (*i)->createCopy();
		pti->childs.push_back(bpti);
		pti->parent = pti;
	}
	return pti;
}
void PTI_Brackets::print(int level){
	for(int j = 0;j < level;j++)cout << " ";
	cout << declaration.open << "..." << declaration.close << "\n";
	assert(childs.size() == 1);
	childs[0]->print(level+1);
}

PTI_Unknown::PTI_Unknown(){myType = Unknown;}
BaseParsingTreeItem *PTI_Unknown::createCopy(void) const{
	PTI_Unknown *pti = new PTI_Unknown;
	pti->myType = myType;
	pti->parent = 0;
	for(pti_vec::const_iterator i = childs.begin();i != childs.end();i++){
		BaseParsingTreeItem *bpti = (*i)->createCopy();
		pti->childs.push_back(bpti);
		pti->parent = pti;
	}
	return pti;
}
void PTI_Unknown::print(int level){
	for(int j = 0;j < level;j++)cout << " ";
	cout << "\"" << str << "\"\n";
	assert(childs.size() == 0);
}


BracketCounter::BracketCounter(const char *expression,const tbrck_decl_vec& brckdecl){
	len = (int)strlen(expression);
	expr = expression;
	counters = 0;
	if(len > 0){
		int cnt = 0;
		counters = new int[len];
		poss = new const char *[len];
		stack<const char *> pos_stack;
		tbrck_decl_vec::const_iterator j;
		for(int i = 0;i < len;i++){
			counters[i] = cnt;
			for(j = brckdecl.begin();j != brckdecl.end();j++){
				if(expr[i] == (*j).open){
					pos_stack.push(i+expr);
					cnt++;
					break;
				}
			}
			poss[i] = 0;
			for(j = brckdecl.begin();j != brckdecl.end();j++){
				if(expr[i] == (*j).close){
					if(cnt <= 0)
						throw errBrackets();						
					assert(!pos_stack.empty());
					const char *ref = pos_stack.top();
					if(*ref != (*j).open)
						throw errBrackets();
					poss[ref-expr] = i+expr;
					poss[i] = ref;

					pos_stack.pop();
					cnt--;
					break;
				}
			}
		}
		if(cnt != 0)throw errBrackets(); // it should be correct bracket expression
	}
}
int BracketCounter::operator [](const char *i){		
	assert(expr <= i &&  i < expr + len);
	return counters[i - expr];
}
const char *BracketCounter::getPos(const char *i){
	return poss[i - expr];
}
BracketCounter::~BracketCounter(){
	if(counters)delete counters;
	if(poss)delete poss;
}

// Local bracket level changer
BracketCounterLevel::BracketCounterLevel(const char *start,BracketCounter *cnt){
	acounter = cnt;
	assert(acounter);
	level = (*acounter)[start];
}
int BracketCounterLevel::operator [](const char *i){
	return (*acounter)[i] - level;	
}	


int is_whitespace(char c){
	return (c == ' ') || (c == '\t') || (c == '\n');
}
int is_digit(char c){
	return (c >= '0') && (c <= '9');
}

//int stop_this_optimiztion_bugs = 0;

static pti_vec RParse(const char *start,const char *end,BracketCounter &brkCnt,const ParsingContext &context,tpt_trash &trash){

	while(start < end && is_whitespace(start[0]))start++; // trim whitespaces ' xxx ' => 'xxx'
	while(start < end && is_whitespace(end[-1]))end--;
	if(start == end)throw errParseWrongExpression(3);// nothing to parse

	BracketCounterLevel bracketLevel(start,&brkCnt); // to know our bracket level

	{
		tbrck_decl_vec::const_iterator j;
		for(j = context.brck_decl.begin();j != context.brck_decl.end();j++){
			if(*start == (*j).open && brkCnt.getPos(start) == end - 1){
				pti_vec parsed = RParse(start+1,end-1,brkCnt,context,trash);
				if(parsed.size() >= 1){
					return parsed;
				}
				throw errBrackets();
			}
		}
		for(j = context.fbrck_decl.begin();j != context.fbrck_decl.end();j++){
			if(*start == (*j).open && brkCnt.getPos(start) == end - 1){
				pti_vec parsed = RParse(start+1,end-1,brkCnt,context,trash);
				if(parsed.size() != 1){
					throw errBrackets();
				}
				pti_vec ret;
				PTI_Brackets *brackets = new PTI_Brackets;
				trash[brackets] = 1;
				brackets->declaration = *j;
				brackets->childs.push_back(parsed[0]);
				ret.push_back(brackets);
				return ret;
			}
		}
	}



	//brute force optimization:postfix - or + are disabled...
	// yeah, it's one point in this parser that isn't as
	// abstract as needed... but without it performance
	// goes down dramaticly
	if(end[-1] == '-' || end[-1] == '+')throw errParseWrongExpression(3); 

	// If we have x,y,z then parse x,y and z seperately. Then join them into result list
	for(const char *j = start;j < end;j++){
		if(*j == ',' && bracketLevel[j] == 0){
			pti_vec left = RParse(start,j,brkCnt,context,trash);
			pti_vec right = RParse(j+1,end,brkCnt,context,trash);
			copy(right.begin(),right.end(),back_inserter(left));
			return left;
		}
	}

	// Try to check for operators in incrasing priority order with special LR or RL scans
	const tfunc_decl_vec &func_decl =  context.func_decl; 
	const tvar_decl_vec &var_decl =  context.var_decl;

	for(tfunc_decl_vec::const_iterator i = func_decl.begin();i != func_decl.end();i++){
		const FunctionDeclaration &decl = *i;
		int namelen = (int)decl.name.size();
		const char *j = 0;
		if(decl.order == FunctionDeclaration::LR)j = end-namelen;
		if(decl.order == FunctionDeclaration::RL)j = start;
		while(1){
			if(decl.order == FunctionDeclaration::LR && j < start)break;
			if(decl.order == FunctionDeclaration::RL && j >= end - namelen)break;

			if(bracketLevel[j] == 0 && strncmp(j,decl.name.c_str(),namelen) == 0){
				const char *found = j;
				try
				{
					pti_vec left,right;
					if(decl.nleft_Params > 0)
						left = RParse(start,found,brkCnt,context,trash);
					else if(start != found)
						throw errParseWrongExpression(3);

					if(decl.nright_Params > 0)
						right = RParse(found+namelen,end,brkCnt,context,trash);
					else if(found+namelen != end)
						throw errParseWrongExpression(3);


					if(decl.nleft_Params != (int)left.size() || decl.nright_Params != (int)right.size()){
						throw errParseWrongExpression(3);
					}				
					pti_vec ret;
					PTI_Function *function = new PTI_Function;
					trash[function] = 1;
					ret.push_back(function);
					function->declaration = decl;
					function->parent = 0;
					copy(left.begin(),left.end(),back_inserter(function->childs));
					copy(right.begin(),right.end(),back_inserter(function->childs));
					for(vector<BaseParsingTreeItem *>::iterator k = function->childs.begin();k != function->childs.end();k++){
						BaseParsingTreeItem *item = *k;
						item->parent = function;
					}
//					pti_vec v;
//					for(int i = 0;i < ret.size();i++){
//						ret[i]->print();
//						v[i]->print();
//					}
//					stop_this_optimiztion_bugs = -1;
					return ret;
//					stop_this_optimiztion_bugs = 1;
				}catch(errParseWrongExpression){
//					stop_this_optimiztion_bugs = 2;
//					cout << x.num << "\n";
//					//skip...
				}
			}

			if(decl.order == FunctionDeclaration::LR)j--;
			if(decl.order == FunctionDeclaration::RL)j++;
		}
	}
//	if(stop_this_optimiztion_bugs){
//		cout << "bugs !!!!\n";
//	}

	// Try to catch some variables
	for(tvar_decl_vec::const_iterator k = var_decl.begin();k != var_decl.end();k++){
		const VariableDeclaration &decl = *k;
		if((int)decl.name.size() == end-start && strncmp(start,decl.name.c_str(),end-start)==0){
			pti_vec ret;
			PTI_Variable *variable = new PTI_Variable;
			trash[variable] = 1;
			variable->declaration = decl;
			variable->parent = 0;
			ret.push_back(variable);
			return ret;
		}
	}

	// Try to catch some constants
	try{
		int sign = 1;
		int info=0,point=0;

		const char *expr = start,*myexpr = start;
		/*		for(;*expr == '-' || *expr == '+' && expr < end;expr++)if(*expr)sign = -sign;

		myexpr = expr;*/

		while(is_digit(*expr) || *expr == '.' && expr < end){
			if(is_digit(*expr))info = 1;
			if(*expr == '.'){
				if(point)throw errBadConstant(); // 1.2.3
				point = 1;
			}
			expr++;
		}
		if(!info)throw errBadConstant(); // '.'
		if(*expr == 'E' || *expr == 'e'){
			int ok = 1;
			expr++;
			if(*expr == '+' || *expr == '-')expr++;
			while(expr < end){
				if(!is_digit(*expr++)){ok = 0;break;}
			}
			if(!ok)throw errBadConstant(); // '1E+ABC123'
		}
		if(expr != end)throw errBadConstant(); //'1.445E+10xxxx'

		pti_vec ret;
		PTI_RealConstant *constant = new PTI_RealConstant;
		trash[constant] = 1;
		ret.push_back(constant);
		char *myend = 0;
		constant->value = strtod(myexpr,&myend);
		if(myend != end)throw errBadConstant(); // other error
		constant->value *= (sign == -1 ? -1. : +1.);
		constant->parent = 0;
		return ret;