ch19par.c

稀疏矩阵、链表、图、队列、二叉树、多叉树、排序、遗传算法等的实现

int TryMatchParse ( char** ppInputBuffer,
                    int* k,
                    struct sSyntaxBody* pSyntaxP,
                    struct sParseNode** ppParseBody )
{
    int iStatus = TRUE;
    int iBodyStringLength;
    int kLocal;
    struct sParseNode* pNewParse = NULL;
    char *pInputBuffer = NULL;

assert(ppInputBuffer!=NULL);
assert(*ppInputBuffer!=NULL);
    pInputBuffer = *ppInputBuffer;
assert(ppParseBody!=NULL);
assert(*ppParseBody!=NULL);
assert(k!=NULL);
    (*ppParseBody)->iFirstChar = *k;

    /*
     *  The question this routine tries to answer is "does the input
     *  buffer, starting at position 'k', match the abstract syntax
     *  to which pSyntaxP refers? If so, return TRUE and complete the
     *  parse node referred to from ppParseBody. If not, then return
     *  FALSE, without having completed the ppParseBody node.
     *  In order to answer this question, this routine has to:
     *  EITHER check the buffer character-string against an abstract
     *  syntax string
     *  OR set up the environment for a deeper Parse
     *  OR (in the case of the existence and support of the short-
     *  circuit routines) call some specific interior routines which
     *  performs a rapid check.
     *  In this implementation we have just the first two possibilities,
     *  as this version of the code does not act upon short-circuit
     *  routines.
     */

    /*
     *  At what kind of syntax node are we pointing?
     *  We answer this question by looking at the syntax node and seeing
     *  whether it points to a character string (BodyContents is non-NULL)
     *  or to another Syntax node (sSyntaxHead is non-NULL)
     */
printf("TryMatchParse pSyntaxp=:%p:\n", (void *)pSyntaxP);
if(pSyntaxP!=NULL)printf("pSyntaxP->BodyContents=:%p:\n",
(void *)pSyntaxP->BodyContents);
    if (pSyntaxP->BodyCheck!=NULL)
    {
printf("About to call BodyCheck routine %p\n",(void*)pSyntaxP->BodyCheck);
       iStatus = (*pSyntaxP->BodyCheck)( pInputBuffer+*k );
    }
    else if (pSyntaxP->BodyContents!=NULL)
    {
printf("TryMatchParse string comparison\n");
        /*
         *  This is a character-string comparison node:
         *  Make the string compare, from the abstract string (pointed
         *  at by the syntax tree) and the actual string (starting at
         *  position 'k' in the input buffer). The length of the
         *  comparison has to be the length of the abstract string, as
         *  all of this must match exactly. We have to check that this
         *  length does not overshoot the end of the input buffer:
         */
        iBodyStringLength = strlen(pSyntaxP->BodyContents);
        if (((iBodyStringLength + *k)>PARSE_BUFFER_LENGTH)
           ||((iBodyStringLength + *k)>strlen(pInputBuffer+*k))
           ||(iBodyStringLength<1))
        {
            /*
            *  This overshoots or undershoots - so it cannot compare exactly -
            *  indicate failure:
            */
            iStatus = FALSE;
            return iStatus;
        }
        /*
        *  At this point we know that the input buffer is at least
        *  as long, from the character being pointed at, as the abstract
        *  string. Hence we can safely compare the full length of the
        *  strings:
        */
assert(pInputBuffer+*k!=NULL);
assert(pSyntaxP->BodyContents!=NULL);
printf("contents k=%d\n",*k);
printf("comparing [%s] against [%s] for %d\n",
pInputBuffer+*k,pSyntaxP->BodyContents,iBodyStringLength);
if (iBodyStringLength==1) printf("%02X|%02X\n",*(pInputBuffer+*k),
*pSyntaxP->BodyContents);
        if (strncmp(pInputBuffer+*k,pSyntaxP->BodyContents,
                    iBodyStringLength)!=0)
        {
printf("Compare not equal\n");
WAIT
            /*
            *  The strings are not equal - indicate failure:
            */
            iStatus = FALSE;
            return iStatus;
        }
printf("Compare was equal\n");
WAIT
        *ppInputBuffer += iBodyStringLength;
        (*ppParseBody)->iLastChar = *k + iBodyStringLength;
        /*
        *  If control reaches this part of the "if/then" we have
        *  a successful string comparison
        */
    } else {
        /*
        *  This is a node which has to be parsed more deeply:
        *  We have to go down a level, so we need to call Parse recursively.
        *  To do this we have to allocate a new parse node, and chain it
        *  to this current node as the first daughter. If the recursive
        *  call to Parse returns success, then we can carry on. If it
        *  returns failure, then we too have to return failure - and
        *  the Parse level above will find the next potential syntax
        *  element for us to test against.
        */

        /*
        *  So, firstly, get and chain in a new daughter node:
        */
printf("TrymatchParse deeper comparison\n");
        pNewParse = NULL;
        kLocal = *k;
        if (!BuildNewParseBody ( *ppParseBody, NULL, &pNewParse, kLocal, -1))
        {
            /*
            *  Oh dear. We were unable to build a new parse node to place
            *  on the tree. Now is a good time to burst into tears. Failing
            *  that, we can just issue an error message and terminate the
            *  whole program. For the time being, however, we shall just
            *  weakly indicate failure:
            */
            iStatus = FALSE;
            return iStatus;
        }
        pNewParse->CodeGenerate = pSyntaxP->CodeGenerate;
printf("Setting ThisHead [%p] line %d\n",pSyntaxP->BodyHead,__LINE__);
        pNewParse->ThisHead = pSyntaxP->BodyHead;
        pNewParse->ThisBody = pSyntaxP->ParentAlt->ThisBody;
printf("TryMatchParse about to Parse\n");
        if((pSyntaxP->BodyHead)!=NULL)
/*           iStatus = Parse ( &pInputBuffer, &kLocal, pSyntaxP->BodyHead, */
           iStatus = Parse ( ppInputBuffer, &kLocal, pSyntaxP->BodyHead,
                          &pNewParse );
        else
           iStatus = TRUE;
        *k = kLocal;
printf("TryMatchParse Parse=%d\n",iStatus);
    }

    return iStatus;
}


/* ------------------------------------------------------------------ */

/*
 *  The generalised Parse routines take as initial input three
 *  parameters:
 *    the address of the input buffer,
 *    the address of the abstract sytax tree ("what can be recognised")
 *    the address of the output parse tree ("what was recognised").
 *  Initially the syntax tree is givem but the parse tree is NULL.
 *  The input buffer is assumed to have already been stripped of extra
 *  spaces, so that every <whitespace> has been changed to be exactly
 *  one space character.
*/

int Parse ( char** ppInputBuffer,
            int*   k,
            struct sSyntaxHead* pRootS,
            struct sParseNode** ppRootP )
{
    int    iStatus                   = FALSE;
    int    iWorkStatus               = TRUE;
    int    bNextExists               = FALSE;
    int    bSkipCalled               = FALSE;
    struct sSyntaxBody*  pSyntaxP    = NULL;
    struct sSyntaxBody** ppSyntaxP   = &pSyntaxP;
    struct sParseNode*   pParseBody  = NULL;
    struct sParseNode**  ppParseBody = &pParseBody;
    struct sParseNode*   pRootP      = NULL;

    /*
    *  If the parse pointer is NULL, then we have not performed any
    *  parse yet at all. In this case we have to allocate the first,
    *  root element. In all other cases the parse pointer is pointing
    *  to the lowest element we are trying to complete.
    */
assert(pRootS!=NULL);
assert(ppRootP!=NULL);
printf("TOP of Parse, ppRootP=:%p:\n", (void *)ppRootP);
if(ppRootP!=NULL)printf("->:%p:\n", (void *)*ppRootP);
    if ((*ppRootP)==NULL)
    {
printf("Root Pointer is NULL in Parse\n");
        *ppRootP = malloc(sizeof (struct sParseNode));

        if ((*ppRootP)==NULL)
        {
            /*
            *  We have not been able to allocate the root element.
            *  At this point we could issue an error message. In any
            *  case we need to signal an error and return:
            */
            printf("Out of memory on line %d of file %s - exiting.\n",
                   __LINE__,__FILE__);
            iStatus = FALSE;
            return iStatus;
        }

#ifdef PARDEBUG
        strcpy((*ppRootP)->ParseNodeIdent,"PBD");
#endif

        /*
        *  We have the new root element. Set its initial values:
        */
        (*ppRootP)->ParentParse   = NULL;
        (*ppRootP)->NextParse     = NULL;
        (*ppRootP)->PreviousParse = NULL;
        (*ppRootP)->ThisHead      = pRootS;
        (*ppRootP)->ThisBody      = NULL;
        (*ppRootP)->ThisParse     = NULL;
        (*ppRootP)->CodeGenerate  = NULL;
        (*ppRootP)->iFirstChar    = 0;
        (*ppRootP)->iLastChar     = -1;
    }
    else
    {
printf("ppRootP was not NULL in Parse\n");
        (*ppRootP)->ThisHead      = pRootS;
    }
    pParseBody = *ppRootP;
printf("pRootS=:%p:\n",(void *)pRootS);
assert(pRootS->FirstAlternate!=NULL);
printf("FirstAlternate=:%p:\n",(void *)pRootS->FirstAlternate);
printf("ThisBody=:%p:\n",(void *)pRootS->FirstAlternate->ThisBody);

    pSyntaxP = pRootS->FirstAlternate->ThisBody;
    ppSyntaxP = &pSyntaxP;
    bNextExists = (pSyntaxP!=NULL);

    /*
    *  If this a non-NULL pointer, then we have to inspect the
    *  buffer, and match it against the syntax. If it is a NULL
    *  pointer, however, then we have finished this parse node:
    */
printf("bNextExists=%d iWorkStatus=%d\n",bNextExists,iWorkStatus);
        while (bNextExists && iWorkStatus)
        {
printf("pSyntaxP=:%p: ppSyntaxP=:%p:\n",(void *)pSyntaxP,(void *)ppSyntaxP);
    if (pSyntaxP==NULL)
    {
        iStatus = TRUE;
        return iStatus;
    }   /* this was a finished parse */
        bNextExists = TRUE;
            /*
            *  Now try to match the input buffer against this possible
            *  syntax item:
            */
            iWorkStatus = TryMatchParse ( ppInputBuffer, k, pSyntaxP,
                                          ppParseBody );
printf("After TryMatchParse iWorkStatus=%d\n",iWorkStatus);
WAIT
            /*
            *  If this matched, then we go on to the next item in the chain
            *  of items in this syntax branch. If it does not match, then we
            *  have to go back up a level to the next choice:
            */
            bSkipCalled = FALSE;
            if (iWorkStatus)
            {
                *ppInputBuffer += *k;
                bNextExists = GetNextSyntax ( ppSyntaxP );
    if (pSyntaxP==NULL)
    {
        iStatus = TRUE;
        return iStatus;
    }   /* this was a finished parse */
            }
            else
            {
printf("Before SkipNexSyntax ppSyntaxP=%p\n",(void *)*ppSyntaxP);
                iWorkStatus = SkipNextSyntax ( ppSyntaxP );
printf("After  SkipNexSyntax ppSyntaxP=%p\n",(void *)*ppSyntaxP);
                bSkipCalled = TRUE;
/*WAIT*/
                *k = pParseBody->iFirstChar;
    if (pSyntaxP==NULL)
    {
        iStatus = FALSE;
        return iStatus;
    }   /* this was a finished parse */
            }
printf("After Get/Skip bNextExists=%d iWorkStatus=%d\n",bNextExists,iWorkStatus);
printf("pSyntaxP=:%p: ppSyntaxP=:%p:\n",(void *)pSyntaxP,(void *)ppSyntaxP);
    if (((*ppSyntaxP)!=NULL) && bNextExists && iWorkStatus)
    {
        pSyntaxP = *ppSyntaxP;
printf("After resetting pSyntaxP=%p\n",(void *)pSyntaxP);
    if (pSyntaxP==NULL)
    {
        iStatus = TRUE;
        return iStatus;
    }   /* this was a finished parse */
#if 0
        (*ppRootP)->ThisBody = NextParseItem ( &pRootP ); /* ??? */
        pSyntaxP = NextParseItem ( &pRootP );
        *ppRootP = pRootP;
#endif
    }
    else
    {
       if(*ppRootP==NULL)
       {
          iStatus = FALSE;
          *ppRootP = NULL;
          return iStatus;
       }
       else if ((bSkipCalled) && (!iWorkStatus))
       {
printf("Skip was called, parse node=%.*s\n",
SYNTAX_NAME_LENGTH,(*ppRootP)->ThisHead->SyntaxName);
WAIT
          pRootP = (*ppRootP)->ParentParse;
          free(*ppRootP);
if (pRootP==NULL) {printf("About to set ppRootP to NULL\n");WAIT}
          *ppRootP = pRootP;
       }
    }

        }   /* end of "while" there is another node to check */
        /*
        *  if "iWorkStatus" is TRUE then we have finished a parse
        *  node successfully. Otherwise we have to tell the caller
        *  to backtrack.
        */
        iStatus = iWorkStatus;
printf("Parse is returning %d\n",iStatus);
    return iStatus;
}

/* ---------------------------------------------------------------- */
int GetNextSyntax ( struct sSyntaxBody** ppSyntaxP )
{
    int iReturn = FALSE;

    /*
    *  We have just parsed a node successfully, and ppSyntaxP is
    *  pointing at that syntax node. We need to find the next item in
    *  the abstract syntax tree that needs to be inspected next.
    *  That item has to be on this syntax branch, following the
    *  one we have just finished. If it exists, then we construct
    *  a new parse node, chain it on to the previous one, point
    *  to it, and return indicating success.
    *  If it does not exist, howver, then we leave all the input
    *  pointers in their current status, and return indicating
    *  failure.
    */
assert(ppSyntaxP!=NULL);
assert(*ppSyntaxP!=NULL);
    *ppSyntaxP = (*ppSyntaxP)->NextBody;
    if ((*ppSyntaxP)!=NULL)
        iReturn = TRUE;
    return iReturn;
}

/* ---------------------------------------------------------------- */

int SkipNextSyntax (struct sSyntaxBody** ppSyntaxP )
{
    int iReturn = FALSE;

    /*
    *  We have just parsed a node unsuccessfully, and ppSyntaxP
    *  is pointing at that node. We need to find the next item in
    *  the abstract syntax tree which has to be considered. This
    *  item must be the first item on a subsequent branch of the
    *  same main syntax head as we have just tried. If this
    *  exists, then we point this parse node to it, and return
    *  indicating success. If, however, it does not exist then
    *  we leave all the pointers as they are, and return indicating
    *  failure. It will then be up to the caller to get rid of
    *  this parse node, and try again higher up.
    */
assert(ppSyntaxP!=NULL);
assert(*ppSyntaxP!=NULL);
assert((*ppSyntaxP)->ParentAlt!=NULL);
    if (((*ppSyntaxP)->ParentAlt->NextAlt)!=NULL)
    {
        *ppSyntaxP = (*ppSyntaxP)->ParentAlt->NextAlt->ThisBody;
    }
    else
    {
        *ppSyntaxP = NULL;
    }