ch19par.c

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

/* Code by Ian D. K. Kelly for Chapter 19, "C Unleashed"    */
/* Parse an arithmetic expression, and plant simple code    */

/* Ch19Par.c
*
*  Parse an arithmetic expression against a given syntax definition.
*
*  Copyright (C) 2000  Ian D. K. Kelly,
*                      idkk Consultancy Ltd.
*                      Macmillan Computer Publishing
*
*  This program is free software; you can redistribute it and/or modify
*  it under the terms of the GNU General Public License as published by
*  the Free Software Foundation; either version 2 of the License, or
*  (at your option) any later version.
*
*  This program 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 General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with this program; if not, write to the Free Software
*  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*
*  Ian Kelly may be contacted at [e-mail]
*
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#include <assert.h>

#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif

#include "Ch19Par.h"
#if 1
#define WAIT {char dummy[6]; printf("pak\n"); fgets(dummy,6,stdin);}
#else
#define WAIT
#endif

/*
*  We need to be able to:
*    1) read in the abstract syntax, and construct from it the
*       syntax tables (tree) which will be used during the parsing
*    2) from the abstract syntax we need to construct the (sparse)
*       "must contain" and "can start with" tables
*    3) read in and parse a possible expression
*    4) generate code for the parsed expression
*/

/*
*  This is the more elaborate version of the parse program n this
*  CD. It contains some of the techniques for speeding up the parse
*  process, and attempts to produce more comprehensible error messages.
*/

/* ====== Read abstract syntax, Free abstract syntax ================ */

/*
*  The abstract syntax will be stated in a file whose filename is
*  in the string variable "sSyntaxFileName". The file pointer for
*  this file is "fSyntaxFile".
*  The format of the syntax is a series of definitions, with each
*  definition commencing on a new line.
*  A definition starts with a syntax name followed by a space followed
*  by its alternates. Each alternate is separated from the next by a
*  dollar sign.
*  Each alternate consists of a series of items. An item is a name
*  (which represents one of the syntax definitions), or a character
*  string enclosed in double-quotes, or a procedure name enclosed in
*  square brackets., or a procedure name enclosed in round brackets.
*  Each procedure name must be a procedure that is available for either
*  syntax verification within this parser (the names enclosed in round
*  brackets), or for generating a part of the output code (the names
*  enclosed in square brackets).
*/

int ReadSyntax ( struct sSyntaxTableElement* SyntaxTable,
                 struct sAlternateTableElement* AlternateTable,
                 struct sRoutineNameTableElement* RoutineNameTable,
                 char* SyntaxLine,
                 struct sSyntaxHead** pRoot, char* sSyntaxFileName )
{
    int iStatus = TRUE;
    struct sSyntaxHead* pRootSyntax = NULL;

assert(SyntaxTable!=NULL);
assert(AlternateTable!=NULL);
assert(RoutineNameTable!=NULL);
assert(SyntaxLine!=NULL);
assert(pRoot!=NULL);
assert(sSyntaxFileName!=NULL);

    pRootSyntax = *pRoot;
    fSyntaxFile = fopen ( sSyntaxFileName, "r" );
    if (fSyntaxFile==NULL)
    {
        /* ERROR - the syntax file could not be opened */
        iStatus = FALSE;
        return iStatus;
    }

    /*
    *  Read in each syntax line, to the end of file, and then
    *  close the file. The first definition is assumed to be
    *  the root that we are aiming for.
    */
    while (!feof(fSyntaxFile))
    {
        iStatus = ProcessSyntaxLine ( SyntaxTable, AlternateTable,
                                      RoutineNameTable, SyntaxLine, pRootSyntax );
        if ( *pRoot == NULL )
        {
            *pRoot = SyntaxTable[0].pSyntaxPointer;

        }
    }

    fclose(fSyntaxFile);

    return iStatus;
}

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

/*
*  Examine the syntax table for an entry containing this name. If it
*  is found, return its subscript. If it is not found, create one,
*  increase the maximum counter, and return its subscript.
*/
int FindSyntaxName ( struct sSyntaxTableElement* SyntaxTable,
                     char* SyntaxName )
{
    int iReturn = 0;
    int i;
    int j;

    j = iNextSyntax;
    /*
    *  If there is an existing entry in the table, then look in the
    *  table for a match:
    */
    if (j>0)
    {
        for (i=0;((iReturn==0)&&(i<iNextSyntax));i++)
        {
            if (strcmp(SyntaxName,SyntaxTable[i].SyntaxName)==0)
            {
                iReturn = i;
            }
        }
    }

    /* If no match has yet been found, create a new table entry: */
    if (iReturn==0)
    {
        iReturn = CreateSyntaxTableEntry ( SyntaxTable, SyntaxName );
        /* Create the new table entry: the name */
#if 0
        strcpy(SyntaxTable[iNextSyntax].SyntaxName,SyntaxName);
        /* Set the pointers to empty: */
        SyntaxTable[iNextSyntax].pSyntaxPointer  = NULL;
        SyntaxTable[iNextSyntax].iMustContain = 0;
        SyntaxTable[iNextSyntax].iStartsWith  = 0;
        iReturn = iNextSyntax;
        /* Set the maximum count up by one: */
        iNextSyntax++;
#endif
    }

    return iReturn;
}

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

int CreateSyntaxTableEntry (struct sSyntaxTableElement* SyntaxTable,
                            char* pSyntaxName)
{
    int iStatus;

    strcpy(SyntaxTable[iNextSyntax].SyntaxName,pSyntaxName);
    /* Set the pointers to empty: */
    SyntaxTable[iNextSyntax].pSyntaxPointer  = NULL;
    SyntaxTable[iNextSyntax].iMustContain = 0;
    SyntaxTable[iNextSyntax].iStartsWith  = 0;
    iStatus = iNextSyntax;
    /* Set the maximum count up by one: */
    iNextSyntax++;

    return iStatus;
}

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

void FreeWholeSyntax ( struct sSyntaxTableElement* SyntaxTable )
{
    int i;

    for (i=0;(i<iNextSyntax);i++)
    {
        if ( SyntaxTable[i].pSyntaxPointer!=NULL )
        {
            FreeSyntaxHead ( SyntaxTable[i].pSyntaxPointer );
            SyntaxTable[i].pSyntaxPointer = NULL;
        }
    }

    return;
}

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

int GetSyntaxName ( struct sSyntaxTableElement* SyntaxTable,
                    char* SyntaxLine, int* j )
{
    struct sSyntaxHead* pNewSyntaxHead;
    char SyntaxName[SYNTAX_NAME_LENGTH+1];
    int i;
    int m;
    int iMySyntaxNumber;

    strcpy(SyntaxName,"");
    m = 0;
    for (i=0; (m==0); i++)
    {
        if (isidchar(SyntaxLine[i + *j]))
        {
            SyntaxName[i] = SyntaxLine[i + *j];
            SyntaxName[i + 1] = '\0';
        }
        else
        {
            m = i;
            *j += i;
        }
    }

    iMySyntaxNumber = FindSyntaxName ( SyntaxTable, SyntaxName );
    if (SyntaxTable[iMySyntaxNumber].pSyntaxPointer==NULL)
    {
        /*
        *  This is the defining entry for this name.
        *  Get and initialise a new SyntaxHead head item
        *  The table entry can then point to this tree item.
        */
        pNewSyntaxHead = malloc ( sizeof (struct sSyntaxHead) );
        if(pNewSyntaxHead == NULL)
        {
          printf("Out of memory on line %d - exiting.\n", __LINE__);
          exit(EXIT_FAILURE);
        }
#ifdef PARDEBUG
        strcpy((pNewSyntaxHead)->SyntaxHeadIdent,"SHD");
#endif
        SyntaxTable[iMySyntaxNumber].pSyntaxPointer  = pNewSyntaxHead;
        /*
        *  Set the name, and all the other fields to empty or null:
        */
        strcpy(pNewSyntaxHead->SyntaxName,SyntaxName);
        pNewSyntaxHead->iSyntaxNumber  = iMySyntaxNumber;
        pNewSyntaxHead->iStartsWith    = 0;
        pNewSyntaxHead->iMustContain   = 0;
        pNewSyntaxHead->FirstAlternate = NULL;
        pNewSyntaxHead->LexRoutine     = NULL;
        pNewSyntaxHead->iIsLexical     = FALSE;
        pNewSyntaxHead->pNextHead      = NULL;
        if (iMySyntaxNumber>0)
        {
            /*
            *  We know that there is a real previous name - so we need to
            *  chain this new element to the one before. This involves
            *  setting this back pointer to the element before, and
            *  the forward pointer of the element before to this one:
            */
            pNewSyntaxHead->pPreviousHead =
                           SyntaxTable[iMySyntaxNumber-1].pSyntaxPointer;
            (SyntaxTable[iMySyntaxNumber-1].pSyntaxPointer)->pNextHead =
                           pNewSyntaxHead;
        }
        else
        {
            pNewSyntaxHead->pPreviousHead  = NULL;
        }
    }
    return iMySyntaxNumber;
}

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

int isidchar ( char testchar )
{
    int iStatus;

    /*
    *  Test the character being presented, and determine whether it
    *  can be part of an identifier or not. The characters allowed
    *  are letters, digits and the underscore. All other characters
    *  are forbidden:
    */

    if ((isalpha(testchar))||(isdigit(testchar)||(testchar=='-')))
        iStatus = TRUE;
    else
        iStatus = FALSE;

    return iStatus;
}

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

int GetIdentifier ( char* InputBuffer, char* Identifier, int* j )
{
    int iStatus = FALSE;
    int i = 0;

    /*
    *  Get the identifier from the input buffer, stopping at the
    *  first character that cannot be in an identifier (under our
    *  definitions):
    */

    while ((isidchar(*(InputBuffer+*j))) && (i<ROUTINE_NAME_LENGTH))
    {
        /*  The character is good: copy it to the caller: */
        Identifier[i++] = *(InputBuffer+*j);
        /*  And indicate the advance of the input pointer: */
        (*j)++;
        /*
        *  Since we have had one good character, indicate success
        *  to the caller. If there are no good characters in the
        *  input, then we will be indicating failure:
        */
        iStatus = TRUE;
    }

    /*  Put in the string termination character: */
    Identifier[i] = '\0';

    return iStatus;
}

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

int GetLexName ( struct sSyntaxTableElement* SyntaxTable,
                 char* SyntaxLine, char* Identifier, int* j, int iMySyntaxNumber )
{
    int    iMyLexNumber = -1;

    while (SyntaxLine[*j]==' ')
        (*j)++;

    /*
    *  We are now either pointing to the first colon of ::= or
    *  :L:= OR we are pointing at the opening left curly of
    *  {name}, where "name" is the name of a routine to be called
    *  at lexical analysis time:
    */
    if ((SyntaxLine[*j]=='{') || (SyntaxLine[*j]=='(')
    ||  (SyntaxLine[*j]=='['))
    {
        /*
        *  Point to the first character of the identifier in
        *  the input line, advancing past the left bracket that
        *  we have just seen:
        */
        (*j)++;
        /*
        *  Fetch the identifier:
        */
        iMyLexNumber = GetIdentifier ( SyntaxLine, Identifier, j );
        /*
        *  Skip the terminating right bracket. There could be an
        *  error check here to verify that it really IS a right
        *  bracket of the same type as the opening bracket (square,
        *  brace or parenthesis).
        *    iStatus = (SyntaxLine[(*j)++]=='}');
        */
        (*j)++;
        /*
        *  and skip past any terminating white space:
        */
        while ((SyntaxLine[*j]==' ') || (SyntaxLine[*j]=='\t'))
        {
            (*j)++;
        }
    }

    if (strncmp(&SyntaxLine[*j],":L:=",4)==0)
    {
        SyntaxTable[iMySyntaxNumber].pSyntaxPointer->iIsLexical = TRUE;
        (*j)+=4;