ch19par.c

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

    }
    else
    {
        SyntaxTable[iMySyntaxNumber].pSyntaxPointer->iIsLexical = FALSE;
        (*j)+=3;
    }

    /*
    *  Note that if we did not get a good identifier, then this
    *  routine passes that error back to its caller:
    */
    return iMyLexNumber;
}

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

int GetRoutinePointer ( struct sRoutineNameTableElement* RoutineNameTable,
                        char* pszRoutineName, int (**FoundRoutine) (void*) )
{
    int iStatus = FALSE;
    int i;

    /*
    *  Scan the routine name table for the matching name, if any, and
    *  return a pointer to the real routine. If there is no match, then
    *  there is an error, and this routine indicates FALSE to its caller
    */

    /*
    *  Initial answer pointer is NULL:
    */
    *FoundRoutine = NULL;

    for (i=0;(i<=GLOBMAXNAME);i++)
    {
        if (strcmp(pszRoutineName, RoutineNameTable[i].sNameBody ) == 0)
        {
            /*
            *  The match has been found, so return the pointer to
            *  the real routine, indicate success, and return to caller
            */
            *FoundRoutine = RoutineNameTable[i].BodyRoutine;
            iStatus = TRUE;
            return iStatus;
        }
        /*
        *  This was not the match - go try the next table element
        */
    }

    /*
    *  No entry in the table matched - return to caller indicating
    *  that we have failure:
    */

    return iStatus;
}

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

int GetNewSyntaxHead ( struct sSyntaxTableElement* SyntaxTable,
                       struct sRoutineNameTableElement* RoutineNameTable,
                       struct sSyntaxHead** ppNewSyntaxHead ,
                       char*  Identifier )
{
    int iStatus = TRUE;

    *ppNewSyntaxHead = malloc(sizeof(struct sSyntaxHead));
    if(*ppNewSyntaxHead == NULL)
    {
      printf("Out of memory on line %d - exiting.\n", __LINE__);
      exit(EXIT_FAILURE);
    }
#ifdef PARDEBUG
    strcpy((*ppNewSyntaxHead)->SyntaxHeadIdent,"SHD");
#endif

    (*ppNewSyntaxHead)->SyntaxName[0]  ='\0';
    (*ppNewSyntaxHead)->FirstAlternate = NULL;
    (*ppNewSyntaxHead)->iStartsWith    = 0;
    (*ppNewSyntaxHead)->iMustContain   = 0;
    (*ppNewSyntaxHead)->LexRoutine     = NULL;
    (*ppNewSyntaxHead)->iIsLexical     = FALSE;
    (*ppNewSyntaxHead)->pNextHead      = NULL;
    (*ppNewSyntaxHead)->iSyntaxNumber  = iNextSyntax/*++*/;
    if (iNextSyntax>0)
    {
        /*
        *  This new syntax head is not the very first, so there is
        *  a predecessor. We need to chain the back pointer of this
        *  new Syntax Head item to the previous one, and the forward
        *  pointer of the previous one to this:
        */
        (*ppNewSyntaxHead)->pPreviousHead =
                  SyntaxTable[iNextSyntax-1].pSyntaxPointer;
        if ((SyntaxTable[iNextSyntax-1].pSyntaxPointer)!=NULL)
        {
            (SyntaxTable[iNextSyntax-1].pSyntaxPointer)->pNextHead =
                  *ppNewSyntaxHead;
        }
    }
    else
    {
        /*
        *  There is no predecessor:
        */
        (*ppNewSyntaxHead)->pPreviousHead = NULL;
    }
    /*
    *  The array "Identifier" now contains a null-terminated
    *  string with the lexical routine name. Get a pointer
    *  to that real routine, by checking against our internal
    *  table of names:
    */
    if (strcmp(Identifier,"")==0)
    {
        (*ppNewSyntaxHead)->LexRoutine = NULL;
        (*ppNewSyntaxHead)->iIsLexical = FALSE;
    }
    else
    {
        GetRoutinePointer ( RoutineNameTable,
                            Identifier,
                            &((*ppNewSyntaxHead)->LexRoutine) );
        (*ppNewSyntaxHead)->iIsLexical = TRUE;
    }

    return iStatus;
}

/*
*  Process just one syntax line. That is, just one definition
*/
int ProcessSyntaxLine ( struct sSyntaxTableElement* SyntaxTable,
                        struct sAlternateTableElement* AlternateTable,
                        struct sRoutineNameTableElement* RoutineNameTable,
                        char* SyntaxLine,
                        struct sSyntaxHead* pRootSyntax )
{
    int    iStatus = TRUE;
    char*  pC;
    char   LexIdentifier[ROUTINE_NAME_LENGTH+1];
    int    j=0;
    int    iMySyntaxNumber;
    struct sSyntaxHead *pNewSyntaxHead = pRootSyntax;

    /*
    *  Get the next input line, and if there is anything there
    *  then process it. If there is nothing there, then we
    *  have finished.
    */
    pC = fgets(SyntaxLine, SYNTAX_LINE_LIMIT, fSyntaxFile );
    if (pC!=NULL)
    {
        /*
        *  Get the name, and look in the Syntax Names Table:
        */
#ifdef SYNDEBUGPRINT
        printf("ProcessSyntaxLine: We have a syntax line: j=%d\n",j);
        printf("ProcessSyntaxLine: =-=-=-=-=-=-=-=-:%s:=-=-=-=-=-=-=-=-\n",
                 SyntaxLine);
#endif
        iMySyntaxNumber = GetSyntaxName ( SyntaxTable, SyntaxLine, &j );
        pNewSyntaxHead = SyntaxTable[iMySyntaxNumber].pSyntaxPointer;

        /*
        *  Variable "j" now contains the subscript of the space
        *  that terminates the initial name element. Read in the
        *  terminator (which is either ::= or :L:=, and then read all
        *  the alternates for this item until we reach the end
        *  of line and/or the terminating hash sign:
        */
        LexIdentifier[0] = '\0';
        GetLexName ( SyntaxTable, SyntaxLine, LexIdentifier, &j,
                    iMySyntaxNumber );
        iStatus = GetAlternates ( SyntaxTable, AlternateTable,
                                  RoutineNameTable, SyntaxLine, &j, pNewSyntaxHead );

    }   /* end of "if/then" there was something on the input line */
    return iStatus;
}

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

void FreeSyntaxHead ( struct sSyntaxHead* pFreeHead )
{
    struct sSyntaxAlt* pFreeAlt;

    while ( pFreeHead!=NULL )
    {
        /* Point to the first alternate, and free the list of them: */
        pFreeAlt = pFreeHead->FirstAlternate;
        FreeAlternates ( &pFreeAlt );
        /* Free the head item itself: */
        free ( pFreeHead );
        /* And return NULL pointer to caller: */
        pFreeHead = NULL;
    }
    /*
    *  Note that the above "while" loop will execute only once. This
    *  code is generalized for future expansion should the head items
    *  be collected into a list.
    */

    return;
}

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

/*
*  Get the alternates, starting at the character whose subscript
*  is passed in the argument. This parameter is passed on down to
*  the code that gets each individual alternate, and back up to
*  the caller, who then knows how much of the input has been taken
*  by the function. When this variable is set to zero, then all the
*  alternates have been read.
*/
int GetAlternates ( struct sSyntaxTableElement* SyntaxTable,
                    struct sAlternateTableElement* AlternateTable,
                    struct sRoutineNameTableElement* RoutineNameTable,
                    char* SyntaxLine,
                    int* j, struct sSyntaxHead* pNewSyntaxHead )
{
    int iStatus = TRUE;
    struct sSyntaxAlt* pNewAlternate = NULL;
    struct sSyntaxAlt* pPreviousAlternate;

    /*
    *  Until we have either failure or we reach the end of the
    *  definition, get the next alternate:
    */
    while (( iStatus == TRUE ) && ( *j != 0 ))
    {
        /*
        *  Within this loop, remember the address of the previous
        *  alternate, and get a new alternate header:
        */
        pPreviousAlternate = pNewAlternate;
        pNewAlternate = malloc ( sizeof ( struct sSyntaxAlt ) );
        if(pNewAlternate == NULL)
        {
          printf("Out of memory on line %d - exiting.\n", __LINE__);
          exit(EXIT_FAILURE);
        }
#ifdef PARDEBUG
        strcpy((pNewAlternate)->SyntaxAltIdent,"SAL");
#endif
        pNewAlternate->iAlternateNumber = 0;
        pNewAlternate->iMustContain = 0;
        pNewAlternate->iStartsWith = 0;
        pNewAlternate->iSyntaxNumber = 0;
        pNewAlternate->NextAlt = NULL;
        pNewAlternate->ParentHead = NULL;
        pNewAlternate->PreviousAlt = NULL;
        pNewAlternate->ThisBody = NULL;

        /*
        *  If this is not the first alternate, then chain this to
        *  the previous one:
        */
        if (pPreviousAlternate!=NULL)
        {
assert(pPreviousAlternate!=pNewAlternate);
            pPreviousAlternate->NextAlt = pNewAlternate;
            pNewAlternate->PreviousAlt = pPreviousAlternate;
        }
        else
        {
            /*
            *  This is the first ever alternate: set the back pointer
            *  to NULL - there is no previous:
            */
            pNewAlternate->PreviousAlt = NULL;
        }
        /*
        *  Point this new alternate forward to nothing:
        */
        pNewAlternate->NextAlt = NULL;
        /*  the alternate counter for this new alternate: */
        iNextAlternate++;
        /* Set the Alternate Table: */
        AlternateTable[iNextAlternate].pAlternatePointer = pNewAlternate;
        AlternateTable[iNextAlternate].iSyntaxNumber = iNextSyntax;
        AlternateTable[iNextAlternate].iStartsWith = 0;
        AlternateTable[iNextAlternate].iMustContain = 0;
        /* Save this alternate number in the tree item: */
        pNewAlternate->iAlternateNumber = iNextAlternate;
        /* Point back to the parent syntax item: */
        pNewAlternate->iSyntaxNumber = iNextSyntax;
        /*
        *  Now chain this new alternate item onto the end of the
        *  chain. If it is the first item, point the parent to it,
        *  otherwise point the previous item to it:
        */
        if (pPreviousAlternate==NULL)
        {
            pNewSyntaxHead->FirstAlternate = pNewAlternate;
        }
        else
        {
assert(pPreviousAlternate!=pNewAlternate);        
            pPreviousAlternate->NextAlt = pNewAlternate;
        }
        /* Get the body of the alternate, i.e. its individual items: */
        iStatus = GetOneAlternate ( SyntaxTable, RoutineNameTable, SyntaxLine,
                                    j , pNewAlternate );
    }   /* end "while" getting successive Alternates */

    return iStatus;
}

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

/*
*  Get just one alternate. This will terminate at:
*    1)  end of line, or
*    2)  a vertical bar, or
*    3)  the hash sign which terminates a definition
*/
int GetOneAlternate ( struct sSyntaxTableElement* SyntaxTable,
                      struct sRoutineNameTableElement* RoutineNameTable,
                      char* SyntaxLine,
                      int* j, struct sSyntaxAlt* pNewAlternate )
{
    int iStatus = TRUE;
    int i;
    struct sSyntaxBody* pPreviousBody = NULL;
    struct sSyntaxBody* pNewBody = NULL;

    i = 0;
    while (( i == 0 ) && ( iStatus == TRUE ))
    {
        SkipSpaces ( SyntaxLine, j );
        if ((SyntaxLine[*j]=='|')  || (SyntaxLine[*j]=='#')
        ||  (SyntaxLine[*j]=='\n') || (SyntaxLine[*j]=='\0'))
        {
            /* End of alternate: */
            /* Set the marker to terminate the enclosing "while": */
            i = 1;
            if ((SyntaxLine[*j]=='#') || (SyntaxLine[*j]=='\0'))
            {
                iStatus = FALSE;
            }
            else
            {
                /*
                *  Skip past the Alternate terminator character:
                */
                (*j)++;
                iStatus = TRUE;
            }
        }   /* end of "if/then" termination of alternate */
        else
        {
            /*
            *  Get a new body item, and chain it on to the tree
            *  structure:
            */
            pPreviousBody = pNewBody;
            pNewBody = malloc ( sizeof ( struct sSyntaxBody ) );
            if(pNewBody == NULL)
            {
              printf("Out of memory on line %d - exiting.\n", __LINE__);
              exit(EXIT_FAILURE);
            }

#ifdef PARDEBUG
            strcpy((pNewBody)->SyntaxBodyIdent,"SBD");
#endif

            /*
            *  If this is the first body item within an alternate, then
            *  the parent alternate structure must point to it, the back
            *  pointer is NULL (because there is no previous):
            */
            if (pPreviousBody==NULL)
            {
                pNewAlternate->ThisBody = pNewBody;
                pNewBody->PreviousBody  = NULL;
            }
            else
            {
                /*
                *  This is not the first body item within an alternate,
                *  so chain this item back to the previous one - and the
                *  previous one forward to this:
                */
                pNewBody->PreviousBody = pPreviousBody;
                pPreviousBody->NextBody = pNewBody;
            }
            pNewBody->NextBody      = NULL;
            pNewBody->BodyContents  = NULL;
            pNewBody->BodyCheck     = NULL;
            pNewBody->BodyHead      = NULL;
            pNewBody->LexCheck      = NULL;
            pNewBody->CodeGenerate  = NULL;
            pNewBody->iSyntaxNumber = iNextSyntax;
            pNewBody->iAlternateNumber = iNextAlternate;
            pNewBody->ParentAlt     = pNewAlternate;
            pNewBody->iStartsWith   = 0;
            pNewBody->iMustContain  = 0;