parsetree.c

編譯器的虛擬yacc工具

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

 What This Is:      Implementation of Parse Tree ADT
 Author:            Laura Deddens
 E-mail             [e-mail]
 Last Modified:     5 September 1996

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

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <parseTree.h>

typedef struct ParseTreeStruct
{
   ParseTreeHdl parent,
                leftChild,
                rightChild,
                leftLeaf,
                rightLeaf,
                rightSibling;
   int x,
       y;
   char *s;
   int sLength;
   int *orgValues;
   int numValues;
} ParseTreeStruct;

/*----------Functions local to this ADT----------*/
void SetParseTreeString(ParseTreeHdl tree, char* s, int sLength);
void SetParseTreeRightChild(ParseTreeHdl tree, ParseTreeHdl child);

/*----------Creation and deletion procedures----------*/
void CreateParseTree(ParseTreeHdl * tree, int numValues, char *s, int sLength, int x, int y)
{
   assert(*tree == NULL);
   assert(numValues > 0);

   *tree = (ParseTreeHdl)malloc(sizeof(ParseTreeStruct));
   (*tree)->parent = NULL;
   (*tree)->rightSibling = NULL;
   (*tree)->x = x;
   (*tree)->y = y;
   (*tree)->rightChild = NULL;
   (*tree)->leftChild = NULL;
   SetParseTreeRightChild(*tree, NULL);
   SetParseTreeString(*tree, s, sLength);
   (*tree)->numValues = numValues;
   (*tree)->orgValues = (int*)calloc(sizeof(int), numValues);
}
 
void DestroyParseTree(ParseTreeHdl * tree)
{
   ParseTreeHdl curChild,
                nextChild;

   assert(*tree != NULL);

   curChild = (*tree)->leftChild;
   while(curChild != NULL)
      {
      nextChild = curChild->rightSibling;
      DestroyParseTree(&curChild);
      curChild = nextChild;
      }
   free((*tree)->orgValues);
   (*tree)->orgValues = NULL;
   free(*tree);
   *tree = NULL;
}
/*----------Query functions----------*/
void GetParseTreePosition(ParseTreeHdl tree, int *x, int *y)
   {
   assert(tree != NULL);

   *x = tree->x;
   *y = tree->y;
   }

void GetParseTreeString(ParseTreeHdl tree, char* *s, int *sLength)
   {
   assert(tree != NULL);

   *s = tree->s;
   *sLength = tree->sLength;
   }

int GetParseTreeOrgValue(ParseTreeHdl tree, int which)
   {
   assert(tree != NULL);
   assert(which >= 0);
   assert(which < tree->numValues);

   return(tree->orgValues[which]);
   }

ParseTreeHdl GetLeftChild(ParseTreeHdl tree)
   {
   assert(tree != NULL);

   return(tree->leftChild);
   }

ParseTreeHdl GetRightSib(ParseTreeHdl tree)
   {
   assert(tree != NULL);

   return(tree->rightSibling);
   }
 
/*----------Manipulation procedures----------*/
void SetNewRightChild(ParseTreeHdl tree, ParseTreeHdl child, int nodeHeight, int lowestY)
   {
   int firstX,
       lastX,
       highestY;
   ParseTreeHdl cur;

   assert(tree != NULL);
   assert(tree->parent == NULL);
   assert(child != NULL);
   assert(child->parent == NULL);
   assert(nodeHeight > 0);

   /* get all the pointers set up*/
   SetParseTreeRightChild(tree, child);

   /* calculate what tree's new x position is*/
   firstX = tree->leftChild->x;
   lastX = tree->rightChild->x;
   tree->x = firstX + ((lastX - firstX)/2);

   /* calculate what tree's new y position is*/
   highestY = lowestY;
   cur = tree->leftChild;
   while (cur != NULL)
      {
      if (highestY > cur->y)
         {
         highestY = cur->y;
         }
      cur = cur->rightSibling;
      }
   tree->y = highestY - nodeHeight;
   }

void SetParseTreeOrgValue(ParseTreeHdl tree, int orgValue, int which)
   {
   assert(tree != NULL);
   assert(which >= 0);
   assert(which < tree->numValues);

   tree->orgValues[which] = orgValue;
   }

/*----------Functions local to this ADT----------*/
/***********************************************************************
 This changes the string associated with the parse tree
 Precondition:   tree has been initialized by CreateParseTree
                 sLength must be the length of s
 Postcondition:  the string associated with tree will be s
***********************************************************************/
void SetParseTreeString(ParseTreeHdl tree, char* s, int sLength)
   {
   assert(tree != NULL);
 
   tree->s = strdup(s);
   tree->sLength = sLength;
   }

/***********************************************************************
 This gives the parse tree a new child
 Precondition:   tree has been initialized by CreateParseTree
                 rightChild has been initialized by CreateParseTree
    unless tree has no children in which case rightChild must either be
    initialized by CreateParseTree or it must be NULL
 Postcondition:  if tree has no children and rightChild is NULL then
    there will be no change.  Otherwise tree will have rightChild as a
    new child positioned on the right.
***********************************************************************/
void SetParseTreeRightChild(ParseTreeHdl tree, ParseTreeHdl rightChild)
   {
   assert(tree != NULL);
   /* if one of the children is NULL*/
   if((tree->leftChild == NULL) || (tree->rightChild == NULL))
      {
      /* then both must be NULL*/
      assert(tree->rightChild == NULL);
      assert(tree->leftChild == NULL);
      }
   else
      {
      /* othewise tree has children and it's right most child can't have a rightSibling*/
      assert(tree->rightChild->rightSibling == NULL);
      /* rightChild == NULL is a special case that is only allowed when tree has no children*/
      assert(rightChild != NULL);
      }
   if(rightChild != NULL)
      {
      /* rightChild can't have a parent because tree is going to become its parent */
      assert(rightChild->parent == NULL);
      /* since rightChild is parentless it can't have any siblings*/
      assert(rightChild->rightSibling == NULL);
      }
 
   /* if this is tree's first child */
   if(tree->leftChild == NULL)
      {
      /* then rightChild is both the left and right child*/
      tree->leftChild = rightChild;
      tree->rightChild = rightChild;
      if(rightChild != NULL)
         {
         tree->leftLeaf = rightChild->leftLeaf;
         tree->rightLeaf = rightChild->rightLeaf;
         rightChild->parent = tree;
         }
      else
         {
         tree->leftLeaf = tree;
         tree->rightLeaf = tree;
         }
      }
    else
      {
      /* otherwise it is just the right child and is the old right child's new sibling*/
      tree->rightChild->rightSibling = rightChild;
      tree->rightChild = rightChild;
      tree->rightLeaf = rightChild->rightLeaf;
      rightChild->parent = tree;
      }
   }