mathlex.cpp

来自「这是在wince下面可以跑的一个画函数的软件」· C++ 代码 · 共 398 行

//////////////////////////////////////////////////////////////////////
//
//	Graphite For WinCE(Pocket PC)
//  Initially Written By Hyouck "Hawk" Kim, [e-mail]
//	2002, All Rights Reserved
//
//	This is GPLed, open source based, software development project.
//	For more question about GPL,
//	visit http://www.gnu.org/licenses/gpl.txt
//
//	
//	Revision History
//	Nov/30/2002,		Initial Release		hkim	
//
//
//////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////
//
// This file has implementation for Mathematical Parser and
// Lexical Analizer.
//
// Lexical Analyzer is implemented as CMathLex.
// It is state-machine based lexical analyzer.
// For every token recognized, the scanner creates and
// returns a CMathToken type object.
// So, the user of this lexical analyzer should FREE the token
// or he or she will get some memory leak.
//
// Mathematical Parser is implemented as CMathParser.
// Since YACC is not available on WinCE,
// CMathParser is implemented using simple RDP technique.
// For syntax validation, it's using typical syntax.
// For semantic analysis, all it does is convert infix to postfix and
// make the postfix linked list, which is just a chain of CMathToken objects.
//
// Right now, CMathParser is the only user of CMathLexer.
//
// During development, one interesting/challenging thing I confronted was
// it's quite difficult to de-allocate useless CMathToken returned by scanner.
// The problem might be partly due to the syntax of the grammar and
// partly due to the awkward implementation of the parser.
// Anyway, to prevent worst case scenario, as you know, the memory leak
// What I did is
// keep track of all tokens created by scanner in a list and
// after parsing completes, release all tokens.
// that's it.
// 
// In future release,
// probably, we may need to completely re-write those parser and lexer.
//
// Happy Graphying!!!
// H.Kim
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "mathlex.h"
#include "stackmachine.h"

CMathToken::CMathToken(CString& str, MathTokenType type)
{
	m_str	=	str;
	m_type	=	type;
}

CMathToken::CMathToken(const CMathToken& rhs)
{
	this->m_str = rhs.m_str;
	this->m_type = rhs.m_type;
}


CMathLex::CMathLex(CString& str)
{
	m_input = str;
	m_ndx	= 0;
}

CMathLex::~CMathLex(void)
{
}

typedef enum mathLexState
{
	MATH_LEX_STATE_IDLE		= 0xfff0,
	MATH_LEX_STATE_NUMBER,
	MATH_LEX_STATE_FUNC_VAR,
} MathLexState;

CMathToken* CMathLex::getNextToken(void)
{
	CMathToken* token = NULL;
	MathLexState state = MATH_LEX_STATE_IDLE;
	CString tmp = "";
	bool dot_appeared = false;

	while(m_ndx < m_input.GetLength())
	{
		switch(state)
		{
		case MATH_LEX_STATE_IDLE:
			state = (MathLexState)m_input.GetAt(m_ndx);
			if(isalpha(state))
			{
				state = MATH_LEX_STATE_FUNC_VAR;
			}
			else if(isdigit(state))
			{
				state = MATH_LEX_STATE_NUMBER;
			}
			else if(state == ' ' || state == '\t')
			{
				m_ndx++;
				state = MATH_LEX_STATE_IDLE;
			}
			break;

		case '-':
		case '+':
		case '*':
		case '/':
		case '^':			
			tmp += m_input.GetAt(m_ndx++);
			token = new CMathToken(tmp, MATH_TOKEN_TYPE_OP);
			return token;
		case '(':
			tmp += m_input.GetAt(m_ndx++);
			token = new CMathToken(tmp, 
				MATH_TOKEN_TYPE_OPENING_PAREN);
			return token;
		case ')':
			tmp += m_input.GetAt(m_ndx++);
			token = new CMathToken(tmp, 
				MATH_TOKEN_TYPE_CLOSING_PAREN);
			return token;

		case MATH_LEX_STATE_NUMBER:
			if(isdigit(m_input.GetAt(m_ndx)))
			{
				tmp += m_input.GetAt(m_ndx++);
			}
			else if(m_input.GetAt(m_ndx) == '.' && !dot_appeared)
			{
				tmp += m_input.GetAt(m_ndx++);
				dot_appeared = true;

			}
			else
			{
				token = new CMathToken(tmp, MATH_TOKEN_TYPE_NUM);
				return token;
			}
			break;

		case MATH_LEX_STATE_FUNC_VAR:
			if(isalpha(m_input.GetAt(m_ndx)))
			{
				tmp += m_input.GetAt(m_ndx++);
			}
			else
			{
				if(isReservedFunc(tmp))
					token = new CMathToken(tmp, MATH_TOKEN_TYPE_FUNC);
				else
					token = new CMathToken(tmp, MATH_TOKEN_TYPE_VAR);
				return token;
			}
			break;
		default:
			tmp += m_input.GetAt(m_ndx++);
			token = new CMathToken(tmp, MATH_TOKEN_TYPE_UNRECOGNIZED);
			return token;
		}
	}

	switch(state)
	{
	case MATH_LEX_STATE_FUNC_VAR:
		if(isReservedFunc(tmp))
			token = new CMathToken(tmp, MATH_TOKEN_TYPE_FUNC);
		else
			token = new CMathToken(tmp, MATH_TOKEN_TYPE_VAR);
		return token;

	case MATH_LEX_STATE_NUMBER:
		return new CMathToken(tmp, MATH_TOKEN_TYPE_NUM);
	}

	return token;
}


static struct reservedFunc
{
	TCHAR* str;
} reserved[] = 
{
	L"sin",
	L"cos",
	L"tan",
	L"sqrt",
	L"abs",
	L"neg",
	NULL,
};

bool CMathLex::isReservedFunc(CString& str)
{
	int i = 0;

	while(reserved[i].str != NULL)
	{
		if(str.Compare(reserved[i].str) == 0)
			return true;
		i++;
	}
	return false;
}


CMathParser::CMathParser(CString& str,CTokenList* list)
	: m_scanner(str)
{
	m_list = list;
	m_tokenParsed = NULL;
}

bool CMathParser::parse(void)
{
	m_tokenParsed = new CTokenList();

	m_success = true;
	arith();

	delete m_tokenParsed;
	m_tokenParsed = NULL;

	return m_success;
}

#define SET_PARSE_ERROR(b)\
	m_success = false;\
	m_errString = b;

//
// See Below
// Why I create a new Token
// Instead of using existing one.
//
#define LIST_ADD(_token)\
	if(m_list != NULL)\
	{\
		CMathToken* _nToken = new CMathToken(*_token);\
		m_list->addTail(_nToken);\
	}

#define MATCH(_var)\
	if(!match(_var))\
		return;

//
// With this kind of parser,
// Looks like this is the easiest way to prevent memory leak.
// Here, the concept is
// queue all the tokens parsed
// and when parsing ends, destroy all.
//
#define GET_NEXT_TOKEN()\
	{\
		m_lookahead = m_scanner.getNextToken();\
		if(m_lookahead)\
			m_tokenParsed->addTail(m_lookahead);\
	}


void CMathParser::arith(void)
{
	//m_lookahead = m_scanner.getNextToken();
	GET_NEXT_TOKEN();
	expr();
}

void CMathParser::expr(void)
{
	bool opPresent = false;

	term();
	while(1)
	{
		if(m_lookahead == NULL)
			return;

		switch(m_lookahead->m_type)
		{
		case MATH_TOKEN_TYPE_OP:
			if(m_lookahead->m_str.Compare(L"+") == 0 ||
				m_lookahead->m_str.Compare(L"-") == 0)
			{
				CMathToken* tmp;

				tmp = m_lookahead;
				MATCH(m_lookahead->m_str);
				term();
				LIST_ADD(tmp);
				opPresent = true;
				continue;
			}
		}
		return;
	}
}

void CMathParser::term()
{
	factor();
	while(1)
	{
		if(m_lookahead == NULL)
			return;

		switch(m_lookahead->m_type)
		{
		case MATH_TOKEN_TYPE_OP:
			if(m_lookahead->m_str.Compare(L"*") == 0 ||
				m_lookahead->m_str.Compare(L"/") == 0 ||
				m_lookahead->m_str.Compare(L"^") == 0)
			{
				CMathToken* tmp = m_lookahead;
				MATCH(m_lookahead->m_str);
				factor();
				LIST_ADD(tmp);
				continue;
			}
		}
		return;
	}
}

void CMathParser::factor()
{
	if(m_lookahead == NULL)
			return;

	switch(m_lookahead->m_type)
	{
	case MATH_TOKEN_TYPE_OPENING_PAREN:
		{
			CString s = ")";

			MATCH(m_lookahead->m_str);
			expr();
			MATCH(s);
		}
		break;

	case MATH_TOKEN_TYPE_NUM:
	case MATH_TOKEN_TYPE_VAR:
		LIST_ADD(m_lookahead);
		MATCH(m_lookahead->m_str);
		break;

	case MATH_TOKEN_TYPE_FUNC:
		{
			CString str2 = "(", str = ")";
			CMathToken* tmp = m_lookahead;

			MATCH(m_lookahead->m_str);
			MATCH(str2);
			expr();
			MATCH(str);
			LIST_ADD(tmp);
		}
		break;
	default:
		SET_PARSE_ERROR("Syntax Error");
	}
}

bool CMathParser::match(CString& str)
{
	if(m_lookahead == NULL)
	{
		SET_PARSE_ERROR("Syntax Error");
		return false;
	}

	if(m_lookahead->m_str.Compare(str) == 0)
	{
		GET_NEXT_TOKEN();
		//m_lookahead = m_scanner.getNextToken();
		return true;
	}
	else
	{
		SET_PARSE_ERROR("Syntax Error");
		return false;
	}
}