ch19par.c

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

    if ((*ppSyntaxP)!=NULL)
        iReturn = TRUE;
    return iReturn;
}

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

int GenerateOutputCode ( struct sParseNode* pRootP )
{
    int  iStatus = TRUE;
    struct sParseNode* pParseHead;
    struct sParseNode* pParseBody;

    /*
    *  The parse has been successful. We must now scan the whole
    *  parse tree, processing the nodes in Reverse Polish order,
    *  generatng the output code, by calling the routines (if any)
    *  that are associated with the particular syntax items:
    */

    pParseHead = pRootP;
    if (pParseHead!=NULL)
    {
    pParseBody = pParseHead->ThisParse;
    while ((pParseHead!=NULL) && (iStatus==TRUE))
    {
        /*
        *  process this node:
        */
        iStatus = ProcessOutputNode( &pParseHead, &pParseBody );
    }
    }

    return iStatus;
}

int ProcessOutputNode ( struct sParseNode** ppParseHead,
                        struct sParseNode** ppParseBody )
{
    int iStatus = TRUE;

    /*
    *  Get the address of the next node:
    */
assert(ppParseBody!=NULL);
assert(ppParseHead!=NULL);
fprintf(fOutputFile,"ABOUT TO CONSIDER GENERATION, ppParseBody=%p->%p\n",
(void *)ppParseBody,(void *)*ppParseBody);
    if ((*ppParseBody)==NULL)
    {
        /*
        *  This is the last element in a branch. Anything to do?
        */
assert(*ppParseHead!=NULL);
        if (/*((*ppParseHead)->ThisBody!=NULL) && */
            (((*ppParseHead)->CodeGenerate)!=NULL))
        {
fprintf(fOutputFile,"ABOUT TO GENERATE\n");
             (*ppParseHead)->CodeGenerate ( NULL );
        }
    }
    else
    {
fprintf(fOutputFile,"NO OUTPUT TO GENERATE\n");
        *ppParseBody = (*ppParseBody)->NextParse;
    }
    if((*ppParseBody)!=NULL)
    {
        *ppParseHead = (*ppParseBody)->ParentParse;
    }
    else
    {
        *ppParseHead = NULL;
    }
    return iStatus;
}

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

int gencomparison ( char* pszComparator )
{
    int iStatus = TRUE;
    static int globLabel = 0;

    fprintf(fOutputFile,"A1 = stack[index--];\n");
    fprintf(fOutputFile,"A2 = stack[index--];\n");
    fprintf(fOutputFile,"if (A1 %s A2) goto M%4.4d;\n",
                        pszComparator,++globLabel);
    fprintf(fOutputFile,"A1 = 0;\n");
    fprintf(fOutputFile,"goto L%4.4d;\n",globLabel);
    fprintf(fOutputFile,"M%4.4d:\n",globLabel);
    fprintf(fOutputFile,"A1 = 1;\n");
    fprintf(fOutputFile,"L%4.4d:\n",globLabel);
    return iStatus;
}

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

int genlt ( void* one )
{
    int iStatus;
    iStatus = gencomparison("<");
    return iStatus;
}

int gengt ( void* one )
{
    int iStatus;
    iStatus = gencomparison(">");
    return iStatus;
}

int genle ( void* one )
{
    int iStatus;
    iStatus = gencomparison("<=");
    return iStatus;
}

int genge ( void* one )
{
    int iStatus;
    iStatus = gencomparison(">=");
    return iStatus;
}

int geneq ( void* one )
{
    int iStatus;
    iStatus = gencomparison("==");
    return iStatus;
}

int genne ( void* one )
{
    int iStatus;
    iStatus = gencomparison("!=");
    return iStatus;
}

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

int genoperate ( char* pszOperator )
{
    int iStatus = TRUE;

    fprintf(fOutputFile,"A1 = stack[index--];\n");
    fprintf(fOutputFile,"A2 = stack[index--];\n");
    fprintf(fOutputFile,"A1 = A1 %s A2;\n",pszOperator);
    fprintf(fOutputFile,"stack[index++] = A1;\n");

    return iStatus;
}

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

int genadd ( void* one )
{
    int iStatus;

    /*
    *  Plant the code to add together the top two items on
    *  the stack:
    *       A1 = stack[index--];
    *       A2 = stack[index--];
    *       A1 = A1 + A2;
    *       stack[index++] = A1;
    *
    *  This uses a general routine, which takes just the "plus"
    *  sign as argument, and is also used by gensubtract, gendivide,
    *  genmultiply and genmodulus.
    *  What is not so obvious at first glance is that the same
    *  pattern of code is planted for genAND, genOR, genXOR,
    *  genLAND and genLOR.
    */

    iStatus = genoperate("+");

    return iStatus;
}

int gensubtract ( void* one )
{
    int iStatus;
    iStatus = genoperate("-");
    return iStatus;
}

int genmultiply ( void* one )
{
    int iStatus;
    iStatus = genoperate("*");
    return iStatus;
}

int gendivide ( void* one )
{
    int iStatus;
    iStatus = genoperate("/");
    return iStatus;
}

int genmodulus ( void* one )
{
    int iStatus;
    iStatus = genoperate("%");
    return iStatus;
}

int genAND ( void* one )
{
    int iStatus;
    iStatus = genoperate("&&");
    return iStatus;
}

int genOR ( void* one )
{
    int iStatus;
    iStatus = genoperate("||");
    return iStatus;
}

int genXOR ( void* one )
{
    int iStatus;
    iStatus = genoperate("^");
    return iStatus;
}

int genLAND ( void* one )
{
    int iStatus;
    iStatus = genoperate("&");
    return iStatus;
}

int genLOR ( void* one )
{
    int iStatus;
    iStatus = genoperate("|");
    return iStatus;
}

/* ---------------------------------------------------------------- */
void sp(int depth)
{
    int i;
    for (i=0;i<depth;i++)
        printf(" ");
    return;
}

void PrintParseTree ( struct sParseNode* pInput, int depth )
{
    struct sParseNode* pParseNode;
    int    newDepth;

    newDepth = depth+1;
    pParseNode = pInput;
    while (pParseNode!=NULL)
    {
       sp(depth); printf("At :%p: points :%p:%p:",(void *)pParseNode,
       (void *)pParseNode->ThisHead,(void *)pParseNode->ThisBody);
assert(pParseNode->ThisHead!=NULL);       
       printf("%p\n",pParseNode->ThisHead->SyntaxName);
       sp(depth); printf("   :%p:%p:%p:  :%p:%p:%p:\n",
       (void *)pParseNode->ParentParse,(void *)pParseNode->NextParse,
       (void *)pParseNode->PreviousParse,
       (void *)pParseNode->ThisParse,(void *)pParseNode->ThisHead,
       (void *)pParseNode->ThisBody);

       /*
       *  Is there anything at the level below?
       */
       if (pParseNode->ThisParse!=NULL)
       {
           PrintParseTree ( pParseNode->ThisParse, newDepth);
       }

       /*
       *  Go to next at this level
       */
       pParseNode = pParseNode->NextParse;
    }

    return;
}

void PrintSyntaxTree ( struct sSyntaxTableElement* SyntaxTable,
                       struct sAlternateTableElement* AlternateTable,
                       struct sSyntaxHead* pRootSyntax )
{
    struct sSyntaxHead* pSyntaxHead;
    struct sSyntaxAlt*  pSyntaxAlt;
    struct sSyntaxBody* pSyntaxBody;
    int iHead = 0;
    int iAlt  = 0;
    int iBody = 0;
    int i = 0;
    /* Start from the root syntax head  */
    pSyntaxHead = pRootSyntax;
    printf("------------------START----------------------\n");
    /* Loop round the syntax heads      */
    while ((pSyntaxHead!=NULL) && (iHead<20))
    {
        iHead++;
        printf("Head name :%s: address  :%p:",pSyntaxHead->SyntaxName,
               (void *)pSyntaxHead);
#ifdef PARDEBUG
        printf("   %s",(pSyntaxHead)->SyntaxHeadIdent);
#endif
        printf("\n");
        printf("Syntax counter in head  :%d:\n",pSyntaxHead->iSyntaxNumber);
        printf("First Alternate in Head :%p:\n",(void *)pSyntaxHead->FirstAlternate);
        pSyntaxAlt = pSyntaxHead->FirstAlternate;
        iAlt = 0;
        while ((pSyntaxAlt!=NULL) && (iAlt<10))
        {
            iAlt++;
            printf("    Start of alternate :%p:",(void *)pSyntaxAlt);
#ifdef PARDEBUG
            printf("   %s",(pSyntaxAlt)->SyntaxAltIdent);
#endif
            printf("\n");
            printf("    Alternate counter  :%d:\n",
                   pSyntaxAlt->iAlternateNumber);
            printf("    Syntax Counter in Alternate :%d:\n",
                   pSyntaxAlt->iSyntaxNumber);
            printf("    Body pointer in Alternate   :%p:\n",
                   (void *)pSyntaxAlt->ThisBody);
            /* For this syntax head, loop round the alternates */
            /* For this alternate, loop round the body items   */
            pSyntaxBody = pSyntaxAlt->ThisBody;
            iBody = 0;
            while ((pSyntaxBody!=NULL) && (iBody<20))
            {
                printf("        Start of body  :%p:",(void *)pSyntaxBody);
#ifdef PARDEBUG
                printf("   %s",(pSyntaxBody)->SyntaxBodyIdent);
#endif
                printf("\n");
                printf("        parent alt     :%p:\n",(void *)pSyntaxBody->ParentAlt);
                printf("        Body Contents  :%p:\n",(void *)pSyntaxBody->BodyContents);
                if (pSyntaxBody->BodyContents!=NULL)
                    printf("        == :%p: :%s:\n",(void *)pSyntaxBody->BodyContents,
                    (pSyntaxBody->BodyContents));
                printf("        Syntax Head    :%p:\n",(void *)pSyntaxBody->BodyHead);
                printf("        Syntax Number  :%d: alternate :%d:\n",
                    pSyntaxBody->iSyntaxNumber,pSyntaxBody->iAlternateNumber);
                printf("        End of body    :%p:\n",(void *)pSyntaxBody);
                pSyntaxBody = pSyntaxBody->NextBody;
                iBody++;
            }    /* End of body loop */
            printf("    End of alternate   :%p:\n",(void *)pSyntaxAlt);
            pSyntaxAlt = pSyntaxAlt->NextAlt;
        }   /* End of alternate loop */
        printf("End of Head %s\n",pSyntaxHead->SyntaxName);
        pSyntaxHead = pSyntaxHead-> pNextHead;
    }  /* End of syntax head loop */
    printf("---------------TABLES---------------------\n");
    printf("iNextSyntax=:%5.5d: iNextAlternate=:%5.5d:\n",iNextSyntax,
            iNextAlternate);
    for (i=0;(i<iNextSyntax);i++)
    {
        printf("%5.5d :%p: :%s:\n",i,(void *)SyntaxTable[i].pSyntaxPointer,
               SyntaxTable[i].SyntaxName);
    }
    printf("   ...................................\n");
    for (i=0;(i<iNextAlternate);i++)
    {
        printf("%5.5d :%p: :%5.5d:\n",i,(void *)AlternateTable[i].pAlternatePointer,
               AlternateTable[i].iSyntaxNumber);
    }
    printf("------------------END----------------------\n");
    return;
}

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

void SetupRoutineNames ( struct sRoutineNameTableElement* RoutineNameTable )
{
    /*
    *  Set up the elements in the RoutineNames table. Each element
    *  contains:
    *    1)  the name of the routine, as a character string, and
    *    2) a pointer to that routine
    *  These routines are the Code Generation routines, and the
    *  Parse (speed-up) routines, and the Lexical phase routines
    */
    strcpy(RoutineNameTable[0].sNameBody,"genadd");
    RoutineNameTable[0].BodyRoutine = genadd;
    strcpy(RoutineNameTable[1].sNameBody,"gensubtract");
    RoutineNameTable[1].BodyRoutine = gensubtract;
    strcpy(RoutineNameTable[2].sNameBody,"genmultiply");
    RoutineNameTable[2].BodyRoutine = genmultiply;
    strcpy(RoutineNameTable[3].sNameBody,"gendivide");
    RoutineNameTable[3].BodyRoutine = gendivide;
    strcpy(RoutineNameTable[4].sNameBody,"genmodulus");
    RoutineNameTable[4].BodyRoutine = genmodulus;
    strcpy(RoutineNameTable[5].sNameBody,"gen