/*********************************************************************
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_)