/*********************************************************************
Copyright (C) 2001/2 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.
---------------------------------------------------------------
Class: cxaParseTree
Author: Alexander Berthold
Copyright: Alexander Berthold
Date: 2001/12/19
Version: 0.2.01
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
- 2001/06/12
Current source labeled version 0.1.07
- 2001/12/19
Rebalancing produces stable and expected results.
Labeled 0.2.01
ToDo:
- Check if there are still some constellations which are
rebalanced w/o necessity.
*********************************************************************/
// 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 vCleanupTree(cxaParseBranch *papbCurBranch);
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:
static void vRebalanceInner(cxaParseBranch *papbCurBranch, int nAtmType);
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_)