Click here to Skip to main content
15,868,149 members
Articles / Programming Languages / C++

Tokenizer and analyzer package supporting precedence prioritized rules

Rate me:
Please Sign up or sign in to vote.
5.00/5 (4 votes)
1 Jan 20023 min read 180.2K   2.8K   54  
A library allowing you to conveniently build a custom tokenizer and analyzer supporting precedence priorized rules
/*********************************************************************
	Copyright (C) 2001 by

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

    -- This file is part of cxTokenizer --

    "cxTokenizer" 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.

    "cxTokenizer" 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 "cxTokenizer"; 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.
    ---------------------------------------------------------------

Class:      cxaParseTree
Author:     Alexander Berthold
Copyright:  Alexander Berthold
Date:       2001/06/12
Version:	0.1.07
Purpose:    Helper class for constructing/optimizing the parse tree.
			Is used by cxAnalyzerTree, cxAnalyzerMain, cxAnalyzer
			- In conjunction w/ cxAnalyzerTree::papTBuildTreeInteranals
			  builds up the parse tree
			- Rearranges the tree such with respect to the precedence priorities

Version history:

	-	2001/05/19
		Released the current version 0.1.05

	-	2001/05/23
		Fixed bug w/ unordered items
		Works with test grammar as expected (with minor problems, see
		ToDo list)

	-	2001/06/12
		Current source labeled version 0.1.07

ToDo:
	-	Current algorithm produces unnecessary deep nest levels.
		(papbGetParentWithPrio has to be fixed)
	-	Improve speed (sometimes a reordering of two items is done 
		even if the result of the reordering is the same as the
		original state)
	-	Test for certain configurations (left-handed operators,
		right-handed operators, ...)
*********************************************************************/

// cxaParseTree.h: interface for the cxaParseTree class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_CXAPARSETREE_H__0CD5BF48_9045_4916_B780_68258BC9D524__INCLUDED_)
#define AFX_CXAPARSETREE_H__0CD5BF48_9045_4916_B780_68258BC9D524__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

class cxaParseBranch;
class cxaParseNode;

class cxaParseTree  
{
// Construction/Destruction
public:
	cxaParseTree();
	virtual ~cxaParseTree();

// Attributes
protected:
	cxaParseBranch		*m_papbRoot;
	cxaParseBranch		*m_papbCurBranch;

// Operations
public:
	static void			vRebalance(cxaParseBranch *papbCurBranch, int nAtmType);
	cxaParseBranch		*papbDetach()
		{
		ASSERT(m_papbRoot!=NULL);
		cxaParseBranch	*papbTemp = m_papbRoot;
		m_papbRoot		=NULL;
		return papbTemp;
		}

// Protected operations
protected:
	void				vBeginRule(int nAtmType, int nIDValue, int nPrecPrio,
								   bool fIsLeftBound, bool fIsRightBound);
	void				vEndRule();
	void				vToken(const cxaToken* patToken);
	void				vDump(int nSpaces=0, const cxaParseBranch *papbBranch = NULL);

	static bool			fRebalancePart(cxaParseBranch *papbCurBranch, int nAtmType,
									   cxaParseBranch::iterator _start,
									   cxaParseBranch::iterator _end);

	static void			vSwapElements(cxaParseElement *papeOne,
									  cxaParseElement *papeTwo);
	static void			vSiblingAppendAfterAndUnlink(
									  cxaParseBranch* papbWhere,
									  cxaParseBranch* papbWhat);
	static void			vChildAppendAfterAndUnlink(
									  cxaParseBranch* papbWhere,
									  cxaParseBranch* papbWhat);
	static void			vChildPrependBefore(
									  cxaParseBranch* papbWhere,
									  cxaParseBranch* papbWhat);
	static cxaParseBranch*	papbGetParentWithPrio(
									  cxaParseBranch *papbStart,
									  int nPrecPrio,
									  cxaParseBranch *papbLimit);
	static cxaParseBranch*	papbReverseSearchWithEqualPrio(
									  cxaParseBranch *papbElem);
	static cxaParseBranch*	papbMoveToSubbranch(
									  cxaParseBranch *papbFirst,
									  cxaParseBranch *papbLast);


/*	static void			vDoRebalance(cxaParseBranch* papbParent,
									 cxaParseBranch::iterator *_pstart,
									 cxaParseBranch::iterator *_pend,
									 cxaParseBranch **ppapbLeft,
									 cxaParseBranch **ppapbCur,
									 bool fLeft);*/

	friend class cxAnalyzerTree;
};

#endif // !defined(AFX_CXAPARSETREE_H__0CD5BF48_9045_4916_B780_68258BC9D524__INCLUDED_)

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


Written By
Web Developer
Germany Germany
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions