Parser 4

From DaveWiki

Jump to: navigation, search

Before we continue to create the actual compiler for our expressions we have to implement a number of minor things:

  1. Predefined Constants
  2. Variables
  3. Array Variables
  4. Functions

Contents

Parser Environment

We could easily have variables/functions belong to the parser object/class but a better design is to create a shared "environment" which can be used by multiple parsers. All identifier variables, including constants and arrays, and functions will be stored in this environment which will be referenced by the parser class, for example:

class CParserEnvironment 
{
   //...
};
 
class CExpressionParser
{
protected:
   CParserEnvironment& m_Environment;
 
public:
   CExpressionParser (CParserEnvironment& Env) : m_Environment(Env) {}
 
};

Defining an environment using a reference (rather than a pointer) forces every CExpressionParser object to have a valid environment and avoids the issue of having to check for a valid environment everywhere it is used.

Base Identifier Class

All identifiers for our expression parser will be floating point types which makes things pretty simple. We will use an object oriented design (for no reason in particular) to handle the various types of identifiers with an abstract base class:

/*
 * Identifier types
 */
enum parsertype_t
{
	PARSETYPE_UNDEFINED = -1,
	PARSETYPE_NONE = 0,
	PARSETYPE_FLOAT,
	PARSETYPE_FLOATARRAY,
};
 
 
/*
 * Abstract base class
 */
class CParserBaseID
{
protected:
	parsertype_t	m_Type;
	size_t		m_UseCount;
 
 
public:
 
	CParserBaseID()
	{
		m_Type = PARSETYPE_UNDEFINED;
		m_UseCount = 0;
	}
 
	virtual parsenum_t* GetValuePtr (void) = 0;
	virtual bool        IsArray     (void) const = 0;
	virtual const char* GetName     (void) const = 0;
	virtual bool	    IsName      (const char* pString) const = 0;
 
	virtual void   IncArrayPos   (void)	{}
	virtual void   ResetArrayPos (void)	{}
	virtual size_t GetArraySize  (void) const { return (0); }
 
	size_t GetUseCount (void) const
	{
		return (m_UseCount);
	}
 
	parsertype_t GetType (void) const 
	{ 
		return (m_Type); 
	}
 
	bool IsType (const parsertype_t Type) const 
	{ 
		return (m_Type == Type); 
	}
 
	void ResetUseCount (void)
	{
		m_UseCount = 0;
	}
 
	void IncUseCount (void)
	{
		++m_UseCount;
	}
 
};
 
typedef std::vector<CParserBaseID *> CParserIDArray;

Note the use of pure virtual methods which will have to be implemented in all the derived classes. To use this in our environment is simply to include it along with some basic manipulation methods:

class CParserEnvironment
{
protected:
	CParserIDArray	m_IDArray;
 
	/*
	 * Called when there is a parsing error. Always returns PARSE_ERROR.
	 */
	parseresult_t OnError (const char* pString, ...)
	{
		va_list Args;
 
		va_start(Args, pString);
		davelib::LogFile.VPrintf(pString, Args);
		va_end(Args);
 
		return (PARSE_ERROR);
	}
 
public:
 
	/*
	 * Removes all identifiers in the environment.
	 */
	void DestroyParserIDs (void)
	{
		CParserBaseID* pID;
 
		while (m_IDArray.size() > 0)
		{
			pID = m_IDArray.back();
			m_IDArray.pop_back();
 
			delete pID;
		}
	}
 
	/*
	 * Tries to find an identifier by name (case insensitive). Returns the identifier object
	 * on success or NULL on failure.
	 */
	CParserBaseID* FindIdentifier (const char* pName)
	{
		CParserIDArray::iterator iter = m_IDArray.begin();
 
		while (iter != m_IDArray.end())
		{
			if ((*iter)->IsName(pName)) return (*iter);
			++iter;
		}
 
		return (NULL);
	}
 
	/*
	 * Finds an identifier by its value pointer.
	 */
	CParserBaseID* FindIDValuePtr (const parsenum_t* pValue)
	{
		CParserIDArray::iterator iter = m_IDArray.begin();
 
		while (iter != m_IDArray.end())
		{
			if ((*iter)->GetValuePtr() == pValue) return (*iter);
			++iter;
		}
 
		return (NULL);
	}
 
	/*
	 * Checks if the given identifier name is valid.
	 */
	parseresult_t IsValidIdentifier (const char* pName)
	{
		if (pName == NULL) return OnError("Undefined identifier name!");
 
		if (!isalpha(*pName)) return OnError("Error: Identifier '%s' must start with a letter!", pName);
 
		for (const char* pString = pName; *pString != 0; ++pString)
		{
			if (!iscsym(*pString)) return OnError("Error: Identifier '%s' must contain only letters, numbers and underscores!", pName);
		}
 
		return (PARSE_OK);
	}
};

Constants

We need to consider how to store constant float values for our expression parser. For example, in the trivial expression:

  Result = 2.1

at some point in the compiling the string "2.1" will have to be converted to a floating number and stored somewhere. We will use the following CConstantFloatID class for storing all constant values encountered in an expression:

class CConstantFloatID : public CParserBaseID
{
protected:
 
	parsenum_t m_Value;
 
public:
 
	CConstantFloatID (const parsenum_t Value)
		: m_Value(Value)
	{
		m_Type = PARSETYPE_FLOAT;
	}
 
	virtual const char* GetName (void) const
	{
		return ("");
	}
 
	virtual bool IsName (const char* pString) const
	{
		return (false);
	}
 
	virtual parsenum_t* GetValuePtr (void) 
	{
		return (&m_Value);
	}
 
	virtual bool IsArray (void) const
	{
		return (false);
	}
 
};

To some extent you can consider constants as variables without a name. Note that this method does not reuse constants. For example, in the expression:

  Result = 2 + 2 + 2

the constant "2" would be stored three times. For our purposes this use of extra memory is not a big deal since our expressions will be small. It wouldn't be too hard to create an environment where the constants were reused. Later on when we develop the actual Virtual Machine we'll end up not actually using this identifier class and hard coding the numbers directly into the VM code.


Variables

The variable identifier class CFloatID will hold a single floating point number and is defined as:

class CFloatID : public CParserBaseID
{
protected:
	std::string		m_Name;
	parsenum_t*		m_pValue;
 
public:
 
	CFloatID (const char* pName, parsenum_t* pValue)
		: m_Name(pName), m_pValue(pValue)
	{
		m_Type = PARSETYPE_FLOAT;
	}
 
	const char* GetName (void) const
	{
		return (m_Name.c_str());
	}
 
	virtual parsenum_t* GetValuePtr (void) 
	{
		return (m_pValue);
	}
 
	virtual bool IsArray (void) const
	{
		return (false);
	}
 
	/*
	 * Performs a case insensitive comparison to the given string. Returns
	 * true if they match.
	 */
	virtual bool IsName (const char* pString) const
	{ 
		return _stricmp(m_Name.c_str(), pString) == 0; 
	}
 
	void SetName (const char* pString)
	{
		m_Name = pString;
	}
 
};


Array Variables

As the name suggests, array variables are simply an array of floating point numbers and use the CFloatArrayID derived class:

class CFloatArrayID : public CParserBaseID
{
protected:
	std::string		m_Name;
	parsenum_t*		m_pValue;
	parsenum_t*		m_pOrigValue;
	size_t			m_Size;
	size_t			m_Position;
 
public:
 
	CFloatArrayID (const char* pName, parsenum_t* pValue, const size_t Size) :
					m_Name(pName), m_Size(Size), m_pValue(pValue), m_pOrigValue(pValue)
	{
		m_Position = 0;
		m_Type = PARSETYPE_FLOATARRAY;
	}
 
	virtual void IncArrayPos (void)	
	{
		++m_Position;
		++m_pValue;
	}
 
	virtual void ResetArrayPos (void)
	{
		m_Position = 0;
		m_pValue = m_pOrigValue;
	}
 
	size_t GetArraySize (void) const
	{
		return (m_Size);
	}
 
	const char* GetName (void) const
	{
		return (m_Name.c_str());
	}
 
	virtual parsenum_t* GetValuePtr (void) 
	{
		return (m_pValue);
	}
 
	virtual bool IsArray (void) const
	{
		return (true);
	}
 
	/*
	 * Performs a case insenstive comparison to the given string. Returns
	 * true if they match.
	 */
	virtual bool IsName (const char* pString) const
	{ 
		return _stricmp(m_Name.c_str(), pString) == 0; 
	}
 
	void SetSize (const size_t Size)
	{
		m_Size = Size;
	}
 
	void SetValuePtr (parsenum_t* pValue)
	{
		m_pValue = pValue;
		m_pOrigValue = pValue;
	}
 
	void SetName (const char* pString)
	{
		m_Name = pString;
	}
 
};


Functions

The last thing we need to add to our parser environment are predefined functions. The implementation used here is close to the simplest method for a singly typed parser but will be hard to modify to if we ever wish to add other types. Since the only type is "float" all our functions will take 0 or more floating point numbers as input and return a single number. Only functions with zero and one parameters are shown in the following code but it should be trivial to figure out how to add functions with more parameters:

/*
 * Define the custom function types used in the expression.
 */
typedef parsenum_t (*PARSE_FUNCTION ) (void);
typedef parsenum_t (*PARSE_FUNCTION1) (const parsenum_t);
       //etc...
 
 
/*
 * Holds the definition of one function for possible use in the expression.
 */
class CParserFunction
{
public:
	std::string		m_Name;			/* The function name */
 
	PARSE_FUNCTION		m_pFunction;		/* The function objects (only one will ever be defined) */
	PARSE_FUNCTION1		m_pFunction1;
 
	size_t			m_NumParams;		/* Number of parameters this function requires */
 
	/*
	 * Class Constructor 
	 */
	CParserFunction()
	{
		m_pFunction  = NULL;
		m_pFunction1 = NULL;
		m_NumParams = 0;
	}
 
	/*
	 * Performs the no-argument function, if defined, and returns the result.
	 */
	float Do (void)
	{
		if (m_pFunction) return m_pFunction();
		return (UNDEF_PARSE_NUMBER);
	}
 
	/*
	 * Performs the one argument function, if defined, and returns the result.
	 */
	float Do1 (const parsenum_t Value1)
	{
		if (m_pFunction1) return m_pFunction1(Value1);
		return (UNDEF_PARSE_NUMBER);
	}
 
        //etc...
};

Adding functions now to the parser environment is a relative simple matter:

#define MAX_PARSE_FUNCTION 1000  //Can't 'easily' use std::vector as function objects are referenced externally
 
class CParserEnvironment
{
protected:
 
	CParserFunction	m_Functions[MAX_PARSE_FUNCTION+1];
	size_t		m_NumFunctions;
 
	void AddPreDefinedFunctions (void);
 
public:
 
	/*
	 * Class Constructor
	 */
	CParserEnvironment()
	{
		m_NumFunctions   = 0;
		AddPreDefinedFunctions();
	}
 
	/*
	 * Adds a new function definition.
	 */
	virtual parseresult_t AddFunction (const char* pName, PARSE_FUNCTION Func)
	{
		if (m_NumFunctions >= MAX_PARSE_FUNCTION) return OnError("Error: Exceeded the maximum number of functions %d!", MAX_PARSE_FUNCTION);
 
		m_Functions[m_NumFunctions].m_Name		 = pName;
		m_Functions[m_NumFunctions].m_pFunction  = Func;
		m_Functions[m_NumFunctions].m_NumParams  = 0;
 
		++m_NumFunctions;
		return (PARSE_OK);
	}
 
	/*
	 * Adds a new function definition.
	 */
	virtual parseresult_t AddFunction1 (const char* pName, PARSE_FUNCTION1 Func)
	{
		if (m_NumFunctions >= MAX_PARSE_FUNCTION) return OnError("Error: Exceeded the maximum number of functions %d!", MAX_PARSE_FUNCTION);
 
		m_Functions[m_NumFunctions].m_Name		 = pName;
		m_Functions[m_NumFunctions].m_pFunction1 = Func;
		m_Functions[m_NumFunctions].m_NumParams  = 1;
 
		++m_NumFunctions;
		return (PARSE_OK);
	}
 
	//etc...
 
	/*
	 * Override to provide the actual find function implementation.
	 */
	virtual CParserFunction* FindFunction (const char* pString)
	{
		size_t i;
 
		for (i = 0; i < m_NumFunctions; ++i)
		{
			if (_stricmp(m_Functions[i].m_Name.c_str(), pString) == 0) return (&m_Functions[i]);
		}
 
		return (NULL);
	}
 
	/*
	 * Takes the start and end of a string and tries to find a matching
	 * function definition. Returns NULL if not found.
	 */
	CParserFunction* FindFunction (const char* pStart, const char* pEnd)
	{
		std::string Buffer(pStart, pEnd-pStart+1);
		return FindFunction(Buffer.c_str());
	}
 
	/*
	 * Finds a function by its actual pointer value.
	 */
	CParserFunction* FindFunctionPtr (const void* pPtr)
	{
		size_t i;
		void*  pFunc;
 
		for (i = 0; i < m_NumFunctions; ++i)
		{
			switch (m_Functions[i].m_NumParams)
			{
			case 0:
				pFunc = m_Functions[i].m_pFunction;
				break;
			case 1:
				pFunc = m_Functions[i].m_pFunction1;
				break;
			case 2:
				pFunc = m_Functions[i].m_pFunction2;
				break;
			case 3:
				pFunc = m_Functions[i].m_pFunction3;
				break;
			case 4:
				pFunc = m_Functions[i].m_pFunction4;
				break;
			case 5:
				pFunc = m_Functions[i].m_pFunction5;
				break;
			default:
				pFunc = NULL;
				break;
			}
 
			if (pFunc == pPtr) return (&m_Functions[i]);
		}
 
		return (NULL);
	}
};
 
 
/*
 * Basic macros to convert to/from radians and degrees
 */
#define R2D(radians) ((radians)*57.29577951472)
#define D2R(degrees) ((degrees)*0.017453292519)
 
/*
 * Predefined functions available to the parser. Note that all trig functions
 * take and return angles in degrees.
 */
parsenum_t Func_cos (const parsenum_t Value)	{ return (parsenum_t) cos(D2R(Value)); }
parsenum_t Func_sin (const parsenum_t Value)	{ return (parsenum_t) sin(D2R(Value)); }
parsenum_t Func_tan (const parsenum_t Value)	{ return (parsenum_t) tan(D2R(Value)); }
 
 
void CParserEnvironment::AddPreDefinedFunctions (void)
{
	AddFunction1("cos", Func_cos);
	AddFunction1("sin", Func_sin);
	AddFunction1("tan", Func_tan);
}


Next: Parser_5

Personal tools