Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Tokenizer and analyzer package supporting precedence prioritized rules

, 1 Jan 2002
A library allowing you to conveniently build a custom tokenizer and analyzer supporting precedence priorized rules
cxtpackagetut_win32vc.zip
cxTokenizer
cxTokenizer.dsp
cxTokenizer.plg
cxtPackage
cxtPackage.plg
cxtPackage.dsp
mathTok
mathTok.plg
mathTok.dsp
simpleCalc
simpleCalc.bmp
simpleCalc.dsp
simpleCalc.plg
tkCommon
cxAnalyzer
cxAnalyzer.dsp
cxAnalyzer.plg
cxtpackage_win32vc.zip
cxTokenizer.dsp
cxTokenizer.plg
Debug
cxAnalyzer.dsp
cxAnalyzer.plg
cxtPackage.plg
cxtPackage.dsp
grammaride.zip
pkgcomplete.zip
cxTokenizerMatchTokenRule.inl
cxTokenizer.dsp
cxtPackage.dsp
emptyTestApp
emptyTestApp.clw
res
emptyTestApp.ico
emptyTestApp.dsp
grammarIDE
grammarIDE.clw
res
grammarIDEDoc.ico
icon1.ico
zoomable.ico
Toolbar.bmp
grammarIDE.ico
vssver.scc
grammarIDE.dsp
simpleCalc.bmp
simpleCalc.dsp
vssver.scc
cxaToken.inl
cxAnalyzer.dsp
pkgsrconly.zip
cxTokenizerMatchTokenRule.inl
cxTokenizer.dsp
cxtPackage.dsp
emptyTestApp.clw
emptyTestApp.ico
emptyTestApp.dsp
vssver.scc
cxaToken.inl
cxAnalyzer.dsp
/*********************************************************************
	Copyright (C) 2001 by

		Alexander Berthold, alexander-berthold@web.de.
		Hoegestr. 54
		79108 Freiburg i. Breisgau
		Germany

    -- This file is part of cxAnalyzer --

    "cxAnalyzer" is free software; you can redistribute it and/or 
	modify it under the terms of the GNU Lesser General Public 
	License as published by the Free Software Foundation; either 
	version 2 of the License, or any later version.

    "cxAnalyzer" is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public
	License along with "cxAnalyzer"; if not, write to the Free 
	Software  Foundation, Inc., 59 Temple Place, Suite 330, 
	Boston, MA  02111-1307  USA

    ---------------------------------------------------------------
      If you find any bugs or if you make other corrections/
	  enhancements, i'd appreciate if you'd let me know about 
	  that. My email is
  
       alexander-berthold@web.de
  
      If you share this code, do not remove this text.
    ---------------------------------------------------------------

*********************************************************************/

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

#include "stdafx.h"

#include "cxaToken.h"
#include "cxAnalyzerTypeMap.h"
#include "cxAnalyzerExpression.h"
#include "cxAnalyzerMain.h"
#include "cxAnalyzerTree.h"
#include "cxAnalyzerException.h"
#include "cxaParseTree.h"

#ifndef _DEBUG
#undef TRACE
#define TRACE printf
#endif

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

cxaParseTree::cxaParseTree()
	{
	m_papbRoot		=new cxaParseBranch(-1,-1,32767,false,false);
	m_papbCurBranch	=m_papbRoot;
	}

cxaParseTree::~cxaParseTree()
	{
	if(m_papbRoot)
		delete m_papbRoot;
	}


void	cxaParseTree::vBeginRule(int nAtmType, int nIDValue, int nPrecPrio, bool fLeftBound, bool fRightBound)
	{
	cxaParseBranch	*papbNew = new cxaParseBranch(
										nAtmType,
										nIDValue,
										nPrecPrio,
										fLeftBound,
										fRightBound);

	m_papbCurBranch->push_back(papbNew);
	m_papbCurBranch	=papbNew;
	}

void	cxaParseTree::vEndRule()
	{
	m_papbCurBranch	=m_papbCurBranch->papbGetParent();
	ASSERT(m_papbCurBranch!=NULL);
	}

void	cxaParseTree::vToken(const cxaToken* patToken)
	{
	cxaParseNode	*papnNew = new cxaParseNode(
										patToken);
	m_papbCurBranch->push_back(papnNew);
	}

void	cxaParseTree::vDump(int nSpaces, const cxaParseBranch *papbBranch)
	{
	if(papbBranch==NULL)
		papbBranch=m_papbRoot;

	cxaParseBranch::const_iterator	it;

	for(it=papbBranch->begin();it!=papbBranch->end();it++)
		{
		const cxaParseElement	*pape = (*it);
		if(pape->fIsBranch())
			{
			cxaParseBranch	*papb = ((cxaParseBranch*)pape);
			char c1,c2;
			if(papb->fIsLeftBound()) c1='('; else c1='[';
			if(papb->fIsRightBound()) c2=')'; else c2=']';

//			spaces(nSpaces);
			TRACE(_T("<< BEGIN %c%d%c {id=%d,atm=%d}\n"), c1, ((cxaParseBranch*)pape)->nGetPrecPrio() , c2, 
				  papb->nGetIDValue(),papb->nGetAtmType());
			vDump(nSpaces+1, (cxaParseBranch*)pape);
//			spaces(nSpaces);
			TRACE(_T("END >>\n"));
			}
		else
			{
//			spaces(nSpaces);
			const cxaToken* pat=((cxaParseNode*)pape)->patGetToken();
			if(pat)
				TRACE(_T("* %s\n"), pat->lpszTokenText);
			else
				TRACE(_T("* NULL\n"));
			}
		}
	}

void	cxaParseTree::vRebalance(cxaParseBranch *papbBranch, int nAtmType)
	{
	// Use depth-first algorithm
	cxaParseBranch::iterator	it;

	for(it=papbBranch->begin();it!=papbBranch->end();it++)
		{
		cxaParseElement	*pape = (*it);
		if(pape->fIsBranch())
			vRebalance( (cxaParseBranch*)pape , nAtmType);
		}

	cxaParseBranch::iterator	istart = papbBranch->begin();
	bool	fRepeat = true;
	while(fRepeat)
		{
		fRepeat		= false;
		cxaParseBranch::iterator	_start = papbBranch->end();
		cxaParseBranch::iterator	_end = papbBranch->end();
		for(it=istart;it!=papbBranch->end();it++)
			{
			cxaParseElement	*pape = (*it);
			cxaParseBranch		*papbCur = NULL;
			
			if(pape->fIsBranch())
				papbCur	=(cxaParseBranch*)pape;

			if(papbCur)
				{
				if(papbCur->nGetAtmType()==nAtmType)
					{
					if(_start==papbBranch->end())
						_start=it;
					}
				else
					{
					if(_start!=papbBranch->end())
						_end=it;
					}
				}
			else
				{
				if(_start!=papbBranch->end())
					_end=it;
				}

			if(_end!=papbBranch->end())
				{
				fRepeat = true;
				break;
				}
			}

		if(fRepeat==false && _start!=papbBranch->end() && _end==papbBranch->end())
			{
			fRepeat	= true;
			_end	= papbBranch->end();
			}

		if(fRepeat)
			{
			fRebalancePart(papbBranch,nAtmType,_start,_end);
			istart=_end;
			}
		}
	}

void	cxaParseTree::vSwapElements(cxaParseElement *papeOne,
									 cxaParseElement *papeTwo)
	{
	ASSERT(papeOne!=NULL);
	ASSERT(papeTwo!=NULL);

	cxaParseBranch		*papbPOne, *papbPTwo;
	cxaParseElement	*papeOneBefore, *papeTwoBefore;

	papbPOne	=(cxaParseBranch*)papeOne->tGetParent();
	papbPTwo	=(cxaParseBranch*)papeTwo->tGetParent();

	ASSERT(papbPOne!=NULL);
	ASSERT(papbPTwo!=NULL);

	papbPOne->vUnlink(papeOne,papeOne,&papeOneBefore,NULL,true);
	papbPTwo->vUnlink(papeTwo,papeTwo,&papeTwoBefore,NULL,true);

	if(papeOneBefore==NULL)
		papbPOne->vPushFront(papeTwo);
	else
		papbPOne->vInsertAfter(papeOneBefore,papeTwo);

	if(papeTwoBefore==NULL)
		papbPTwo->vPushFront(papeOne);
	else
		papbPTwo->vInsertAfter(papeTwoBefore,papeOne);
	}

void	cxaParseTree::vSiblingAppendAfterAndUnlink(
									  cxaParseBranch* papbWhere,
									  cxaParseBranch* papbWhat)
	{
	ASSERT(papbWhere!=NULL);
	ASSERT(papbWhat!=NULL);

	cxaParseBranch	*papbPWhere = papbWhere->papbGetParent();
	cxaParseBranch *papbPWhat = papbWhat->papbGetParent();

	ASSERT(papbPWhere!=NULL);
	ASSERT(papbPWhat!=NULL);

	papbPWhat->vUnlink(papbWhat,papbWhat,NULL,NULL,true);
	papbPWhere->vInsertAfter(papbWhere,papbWhat);
	}

void	cxaParseTree::vChildAppendAfterAndUnlink(
									  cxaParseBranch* papbWhere,
									  cxaParseBranch* papbWhat)
	{
	ASSERT(papbWhere!=NULL);
	ASSERT(papbWhat!=NULL);

	cxaParseBranch *papbPWhat = papbWhat->papbGetParent();

	ASSERT(papbPWhat!=NULL);

	papbPWhat->vUnlink(papbWhat,papbWhat,NULL,NULL,true);
	papbWhere->vPushBack(papbWhat);
	}

void	cxaParseTree::vChildPrependBefore(
									  cxaParseBranch* papbWhere,
									  cxaParseBranch* papbWhat)
	{
	ASSERT(papbWhere!=NULL);
	ASSERT(papbWhat!=NULL);

	cxaParseBranch *papbPWhat = papbWhat->papbGetParent();

	ASSERT(papbPWhat!=NULL);

	papbPWhat->vUnlink(papbWhat,papbWhat,NULL,NULL,true);
	papbWhere->vPushFront(papbWhat);
	}

cxaParseBranch	*cxaParseTree::papbGetParentWithPrio(
									  cxaParseBranch *papbStart,
									  int nPrecPrio,
									  cxaParseBranch *papbLimit)
	{
	ASSERT(papbStart!=NULL);
	cxaParseBranch	*papbParent, *papbTemp;

	papbParent		=papbStart;
	for(;;)
		{
		papbTemp		=papbParent->papbGetParent();

		if(papbTemp==papbLimit)
			break;

		if(papbTemp->nGetPrecPrio()>nPrecPrio)
			break;

		papbParent		=papbTemp;
		}

	if(papbParent->nGetPrecPrio()==nPrecPrio)
		return papbParent;

	cxaParseBranch		*papbNew;
	cxaParseElement	*papeBefore;

	papbNew			=new cxaParseBranch(
							papbStart->nGetAtmType(),
							IDVALUE_REORDER,nPrecPrio,
							false,false);
	papbTemp		=papbParent->papbGetParent();
	papbTemp->vUnlink(papbParent,papbParent,&papeBefore,NULL,true);
	papbNew->vPushBack(papbParent);

	if(papeBefore)
		papbTemp->vInsertAfter(papeBefore,papbNew);
	else
		papbTemp->vPushFront(papbNew);

	return papbNew;

/*	papbParent		=NULL;
	papbTemp		=papbStart->papbGetParent();
	while(papbTemp!=NULL)
		{
		if(papbTemp->nGetAtmType()!=papbStart->nGetAtmType())
			break;

		if(papbTemp->nGetPrecPrio()<=nPrecPrio)
			papbParent	=papbTemp;

		if(papbTemp->nGetPrecPrio()>=nPrecPrio)
			break;

		papbTemp	=papbTemp->papbGetParent();
		}

	ASSERT(papbParent!=NULL);

	// Test if we have found a parent with _equal_ priority to
	// 'nPrecPrio'
	if(papbParent->nGetPrecPrio()==nPrecPrio)
		{
		// Yes, everything is done
		return papbParent;
		}

	// No parent with equal priority -> create one
	ASSERT(papbParent->nGetPrecPrio()>nPrecPrio);

	cxaParseBranch	*papbNew;

	papbNew			=new cxaParseBranch(
							papbStart->nGetAtmType(),
							IDVALUE_REORDER,nPrecPrio,
							false,false);
	papbTemp		=papbParent->papbGetParent();
	papbTemp->vUnlink(papbParent,papbParent,NULL,NULL,true);
	papbNew->vPushBack(papbParent);

	return papbNew;*/
	}

cxaParseBranch *cxaParseTree::papbReverseSearchWithEqualPrio(
									  cxaParseBranch *papbElem)
	{
	ASSERT(papbElem!=NULL);

	cxaParseElement *papeTemp;
	cxaParseBranch	 *papbTemp;

	int		nPrecPrio = papbElem->nGetPrecPrio();
	int		nAtmType = papbElem->nGetAtmType();

	while(papbElem!=NULL)
		{
		papeTemp	=papbElem->tGetPrev();

		if(papeTemp==NULL)
			break;
		if(!papeTemp->fIsBranch())
			break;
		papbTemp	=(cxaParseBranch*)papeTemp;
		if(papbTemp->nGetAtmType()!=nAtmType)
			break;
		if(papbTemp->nGetPrecPrio()!=nPrecPrio)
			break;

		papbElem	=papbTemp;
		}

	return papbElem;
	}

cxaParseBranch *cxaParseTree::papbMoveToSubbranch(
									  cxaParseBranch *papbFirst,
									  cxaParseBranch *papbLast)
	{
	ASSERT(papbFirst!=NULL);
	ASSERT(papbLast!=NULL);
	ASSERT(papbFirst->papbGetParent()==papbLast->papbGetParent());
	ASSERT(papbFirst->papbGetParent()!=NULL);

	cxaParseBranch	*papbParent = papbFirst->papbGetParent();
	cxaParseElement *papeBefore = NULL;
	papbParent->vUnlink(papbFirst,papbLast,&papeBefore,NULL,true);

	cxaParseBranch *papbNew = new cxaParseBranch(
									papbFirst->nGetAtmType(),
									IDVALUE_REORDER,papbFirst->nGetPrecPrio(),
									false,false);

	cxaParseElement *papeCur = papbFirst;
	while(true)
		{
		papbNew->vPushBack(papeCur);
		if(papeCur==papbLast)
			break;
		papeCur		=papeCur->tGetNext();
		ASSERT(papeCur!=NULL);
		}

	if(papeBefore==NULL)
		papbParent->vPushFront(papbNew);
	else
		papbParent->vInsertAfter(papeBefore,papbNew);

	return papbNew;
	}

bool	cxaParseTree::fRebalancePart(cxaParseBranch * /*papbParent*/, 
									  int nAtmType,
									  cxaParseBranch::iterator _start,
									  cxaParseBranch::iterator _end)
	{
	cxaParseBranch::iterator	it;
	cxaParseBranch *papbNest = NULL;	// the 'real' predecessor of 'papbCur',
										// child of 'papbPrev'
	bool			fDone = false;
	
	for(it=_start;it!=_end;)
		{
		cxaParseBranch	*papbCur = (cxaParseBranch*)(*it);
		it++;

		if(papbNest == NULL)
			{
			papbNest	=papbCur;
			continue;
			}

		// 1. If the adjacent elements 'papbNest' and 'papbCur' are right/left
		//    bound and one of both has a 'hole' (i.e. a NULL token) to the
		//	  respective sides the one with the higher priority receives
		//    the non-NULL element.
		if(	(papbNest->fIsRightBound() && papbCur->fIsLeftBound()) &&
			(papbNest->nGetPrecPrio() != papbCur->nGetPrecPrio()) )
			{
			bool		fSwap = false;
			bool		fAssignToLeft = 
							(papbNest->nGetPrecPrio())<(papbCur->nGetPrecPrio());

			if(fAssignToLeft && papbNest->fIsBackNULLToken())
				fSwap	=true;
			if(!fAssignToLeft && papbCur->fIsFrontNULLToken())
				{
				ASSERT(fSwap==false);
				fSwap	=true;
				}

			if(fSwap)
				vSwapElements(papbNest->papeGetBackElement(),papbCur->papeGetFrontElement());

			if(fAssignToLeft)
				{
				ASSERT(!papbNest->fIsBackNULLToken());
				}
			else
				{
				ASSERT(!papbCur->fIsFrontNULLToken());
				}
			}

		// 2. Examine the priority of the two adjacent elements 'papbNest' and
		//	  'papbCur'. If it is equal, 'papbCur' must be inserted right after
		//	  'papbNest'. If 'papbNest's priority is higher (numerically lower)
		//	  all precessors of 'papbNest' having the same priority are inserted
		//	  to the front of the child elements of 'papbCur'.
		//	  If 'papbCur's priority is higher, 'papbCur' is inserted as child
		//	  element of 'papbNest' at the back of its child elements.
		bool	fSkip = false;
		if(papbNest->nGetPrecPrio()==papbCur->nGetPrecPrio())
			{
			vSiblingAppendAfterAndUnlink(papbNest,papbCur);
			papbNest	=papbCur;
			fSkip		=true;
			}
		if(!fSkip && papbNest->nGetPrecPrio()>papbCur->nGetPrecPrio())
			{
			vChildAppendAfterAndUnlink(papbNest,papbCur);
			papbNest	=papbCur;
			fDone		=true;
			fSkip		=true;
			}
		if(!fSkip && papbNest->nGetPrecPrio()<papbCur->nGetPrecPrio())
			{
			cxaParseBranch	*papbParent;

			papbParent	=papbGetParentWithPrio(	papbNest,
												papbCur->nGetPrecPrio(),
												papbCur->papbGetParent());

			vSiblingAppendAfterAndUnlink(papbParent,papbCur);
			papbNest	=papbCur;
			fDone		=true;
			}

		// To avoid doing multiple levels of nested branches
		if(papbCur->papbGetParent()->nGetIDValue()!=IDVALUE_REORDER)
			{
			cxaParseBranch *papbCurParent = papbCur->papbGetParent();
			cxaParseBranch	*papbFirst = papbReverseSearchWithEqualPrio(papbCur);
			ASSERT(papbFirst!=NULL);
			ASSERT(papbFirst->papbGetParent() == papbCurParent);
			if(papbFirst != papbCur)
				{
				cxaParseBranch		*papbNew;
				cxaParseElement	*papbBefore = NULL;

				papbCurParent->vUnlink(papbFirst,papbCur,&papbBefore,NULL,true);

				papbNew	=new cxaParseBranch(nAtmType,IDVALUE_REORDER,
											 papbCur->nGetPrecPrio(),
											 false,false);

				cxaParseElement *papeCur = papbFirst, *papeNext;
				while(true)
					{
					papeNext	=papeCur->tGetNext();
					papbNew->vPushBack(papeCur);
					if(papeCur==papbCur)
						break;
					papeCur		=papeNext;
					ASSERT(papeCur!=NULL);
					}

				if(papbBefore!=NULL)
					papbCurParent->vInsertAfter(papbBefore,papbNew);
				else
					papbCurParent->vPushFront(papbNew);
				}
			}
		}

	return fDone;
	}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

About the Author

Alexander Berthold
Web Developer
Germany Germany
No Biography provided

| Advertise | Privacy | Mobile
Web01 | 2.8.140721.1 | Last Updated 2 Jan 2002
Article Copyright 2001 by Alexander Berthold
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid