home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / misc / toolboxsas.lha / Toolbox / lib / lalr / Parser.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-02-15  |  13.8 KB  |  446 lines
  1. /* $Id: Parser.c,v 2.9 1992/08/07 15:28:42 grosch rel $ */
  2.  
  3. #define bool  char
  4. #define true  1
  5. #define false 0
  6.  
  7. $@ #include "@.h"
  8. #include "Errors.h"
  9. #include "Memory.h"
  10. #include "DynArray.h"
  11. #include "Sets.h"
  12. #include <string.h>
  13. #ifndef BCOPY
  14.   #include <memory.h>
  15. #endif
  16.  
  17.  
  18. #ifdef lex_interface
  19. $@  #define $_GetToken yylex
  20.   extern int yylex(void);
  21.   #ifndef AttributeDef
  22.     #include "Positions.h"
  23. $@    typedef struct {tPosition Position;} $_tScanAttribute;
  24. $@    static $_tScanAttribute $_Attribute = {{0,0}};
  25.   #endif
  26.   #ifndef ErrorAttributeDef
  27. $@    #define $_ErrorAttribute(Token,RepairAttribute)
  28.   #endif
  29.   #ifndef yyGetAttribute
  30.     #define yyGetAttribute(yyAttrStackPtr,Attribute) *yyAttrStackPtr = yylval
  31.   #endif
  32. #else
  33. $@  #include "$.h"
  34.   #ifndef yyGetAttribute
  35.     #define yyGetAttribute(yyAttrStackPtr,Attribute) (yyAttrStackPtr)->Scan = Attribute
  36.   #endif
  37. #endif
  38.  
  39.  
  40. $G /* GLOBAL section is inserted here */
  41.  
  42.  
  43. #if defined lex_interface & ! defined yylvalDef
  44.   tParsAttribute yylval;
  45. #endif
  46. #ifndef yyInitStackSize
  47.   #define yyInitStackSize 100
  48. #endif
  49. #define yyNoState 0
  50.  
  51.  
  52. $T /* table constants are inserted here */
  53.  
  54.  
  55. #define yyFirstFinalState yyFirstReadTermState
  56.  
  57.  
  58. typedef unsigned short yyStateRange;
  59. typedef unsigned short yySymbolRange;
  60. typedef struct {yyStateRange Check, Next;} yyTCombType;
  61.  
  62.  
  63. $@ char *@_TokenName[yyLastTerminal+1] = {
  64. $W /* token names are inserted here */
  65. };
  66. static yyTCombType yyTComb[yyTableMax+1] = {
  67. $M
  68. };
  69. static unsigned short yyNComb[yyNTableMax - yyLastTerminal] = {
  70. $N
  71. };
  72. static yyTCombType *yyTBasePtr[yyLastReadState+1] = {
  73. $P
  74. };
  75. static unsigned short* yyNBasePtr[yyLastReadState+1] = {
  76. $Q
  77. };
  78. static unsigned short yyDefault[yyLastReadState+1] = {
  79. $D
  80. };
  81. static unsigned char yyLength[yyLastReduceState - yyFirstReduceState+1] = {
  82. $K
  83. };
  84. static yySymbolRange yyLeftHandSide[yyLastReduceState - yyFirstReduceState+1] = {
  85. $H
  86. };
  87. static yySymbolRange yyContinuation[yyLastReadState+1] = {
  88. $O
  89. };
  90. static unsigned short yyFinalToProd[yyLastReadNontermState - yyFirstReadTermState+1] = {
  91. $F
  92. };
  93.  
  94.  
  95. static void yyErrorRecovery(yySymbolRange * yyTerminal, yyStateRange * yyStateStack, unsigned long yyStackSize, short yyStackPtr);
  96. static void yyComputeContinuation(yyStateRange * yyStack, unsigned long yyStackSize, short yyStackPtr, tSet * yyContinueSet);
  97. static bool yyIsContinuation(yySymbolRange yyTerminal, yyStateRange * yyStateStack, unsigned long yyStackSize, short yyStackPtr);
  98. static void yyComputeRestartPoints(yyStateRange * yyStateStack, unsigned long yyStackSize, short yyStackPtr, tSet * yyRestartSet);
  99. static yyStateRange yyNext(yyStateRange yyState, yySymbolRange yySymbol);
  100. $@ static void Begin@(void);
  101.  
  102.  
  103. $@ int @(void)
  104.  {
  105.   register yyStateRange yyState;
  106.   register long yyTerminal;
  107.   register yyStateRange *yyStateStackPtr;
  108.   register tParsAttribute *yyAttrStackPtr;
  109.   register bool yyIsRepairing;
  110.   unsigned long yyStateStackSize= yyInitStackSize;
  111.   unsigned long yyAttrStackSize = yyInitStackSize;
  112.   yyStateRange *yyStateStack;
  113.   tParsAttribute* yyAttributeStack;
  114.   tParsAttribute yySynAttribute; /* synthesized attribute */ /* ??? */
  115.   register yyStateRange *yyEndOfStack;
  116.   int yyErrorCount = 0;
  117.  
  118. $L /* LOCAL section is inserted here */
  119.  
  120. $@  Begin@();
  121.   yyState = yyStartState;
  122. $@  yyTerminal = $_GetToken();
  123.   MakeArray((char **)&yyStateStack,&yyStateStackSize,sizeof(yyStateRange));
  124.   MakeArray((char **)&yyAttributeStack,&yyAttrStackSize,sizeof(tParsAttribute));
  125.   yyEndOfStack      = &yyStateStack[yyStateStackSize];
  126.   yyStateStackPtr   = yyStateStack;
  127.   yyAttrStackPtr    = yyAttributeStack;
  128.   yyIsRepairing     = false;
  129. ParseLoop:
  130.   for (;;)
  131.    {
  132.     if (yyStateStackPtr >= yyEndOfStack)
  133.      {
  134.       int yyyStateStackPtr = yyStateStackPtr - yyStateStack;
  135.       int yyyAttrStackPtr = yyAttrStackPtr - yyAttributeStack;
  136.       ExtendArray ((char **)&yyStateStack,&yyStateStackSize,sizeof (yyStateRange));
  137.       ExtendArray ((char **)&yyAttributeStack,&yyAttrStackSize,sizeof (tParsAttribute));
  138.       yyStateStackPtr = yyStateStack + yyyStateStackPtr;
  139.       yyAttrStackPtr = yyAttributeStack + yyyAttrStackPtr;
  140.       yyEndOfStack = &yyStateStack[yyStateStackSize];
  141.      }
  142.     *yyStateStackPtr = yyState;
  143. TermTrans:
  144.     for (;;)
  145.      {/* SPEC State = Next (State, Terminal); terminal transition */
  146.       register short *yyTCombPtr;
  147.  
  148.       yyTCombPtr = (short *)(yyTBasePtr[yyState] + yyTerminal);
  149.       if (*yyTCombPtr++ == yyState)
  150.        {
  151.         yyState = *yyTCombPtr;
  152.         break;
  153.        }
  154.       if ((yyState = yyDefault[yyState]) != yyNoState)
  155.         goto TermTrans;
  156.       /* syntax error */
  157.       if (!yyIsRepairing)
  158.        {/* report and recover */
  159.         yySymbolRange yyyTerminal = yyTerminal;
  160.         yyErrorCount++;
  161.         yyErrorRecovery(&yyyTerminal,yyStateStack,yyStateStackSize,(short)(yyStateStackPtr-yyStateStack));
  162.         yyTerminal = yyyTerminal;
  163.         yyIsRepairing = true;
  164.        }
  165.       yyState = *yyStateStackPtr;
  166.       for (;;)
  167.        {
  168.         if (yyNext(yyState,(yySymbolRange)yyTerminal) == yyNoState)
  169.          {/* repair */
  170.           yySymbolRange yyRepairToken;
  171. $@          $_tScanAttribute yyRepairAttribute;
  172.             yyRepairToken = yyContinuation[yyState];
  173.             yyState = yyNext(yyState, yyRepairToken);
  174.             if (yyState <= yyLastReadTermState)
  175.              {/* read or read terminal reduce ? */
  176. $@              $_ErrorAttribute((int)yyRepairToken,&yyRepairAttribute);
  177. $@              ErrorMessageI(xxTokenInserted,xxRepair,$_Attribute.Position,xxString,@_TokenName[yyRepairToken]);
  178.               if (yyState >= yyFirstFinalState)
  179.                {/* avoid second push */
  180.                 yyState = yyFinalToProd[yyState - yyFirstReadTermState];
  181.                }
  182.               yyGetAttribute(yyAttrStackPtr++,yyRepairAttribute);
  183.               * ++yyStateStackPtr = yyState;
  184.              }
  185.             if (yyState >= yyFirstFinalState)
  186.               goto Final; /* final state ? */
  187.            }
  188.           else
  189.            {
  190.             yyState = yyNext(yyState,(yySymbolRange)yyTerminal);
  191.             goto Final;
  192.            }
  193.          }
  194.        }
  195. Final:
  196.       if (yyState >= yyFirstFinalState)
  197.        {/* final state ? */
  198.         if (yyState <= yyLastReadTermState)
  199.          {/* read terminal reduce ? */
  200.           yyStateStackPtr++;
  201. $@          yyGetAttribute(yyAttrStackPtr++,$_Attribute);
  202. $@          yyTerminal = $_GetToken();
  203.             yyIsRepairing = false;
  204. $X          yyState = yyFinalToProd[yyState - yyFirstReadTermState];
  205.          }
  206.         for (;;)
  207.          {/* left-hand side */
  208.           #define yyNonterminal yyState
  209.  
  210. $R          /* Code for Reductions is inserted here */
  211.           /* SPEC State = Next(Top(),Nonterminal); nonterminal transition */
  212.           yyState = *(yyNBasePtr[*yyStateStackPtr++] + yyNonterminal);
  213.           *yyAttrStackPtr++ = yySynAttribute; /* ??? */
  214.           if (yyState < yyFirstFinalState)
  215.             goto ParseLoop; /* read nonterminal reduce ? */
  216. $X          yyState = yyFinalToProd[yyState - yyFirstReadTermState];
  217.          }
  218.        }
  219.       else
  220.        {/* read */
  221.         yyStateStackPtr++;
  222. $@        yyGetAttribute(yyAttrStackPtr++,$_Attribute);
  223. $@        yyTerminal = $_GetToken();
  224.         yyIsRepairing = false;
  225.        }
  226.      }
  227.  }
  228.  
  229.  
  230. static void yyErrorRecovery(yySymbolRange *yyTerminal, yyStateRange *yyStateStack, unsigned long yyStackSize, short yyStackPtr)
  231.  {
  232.   bool yyTokensSkipped;
  233.   tSet yyContinueSet;
  234.   tSet yyRestartSet;
  235.   int yyLength = 0;
  236.   char yyContinueString[256];
  237.  
  238.   /* 1. report an error */
  239. $@  ErrorMessage(xxSyntaxError,xxError,$_Attribute.Position);
  240.   /* 2. report the set of expected terminal symbols */
  241.   MakeSet(&yyContinueSet,(short)yyLastTerminal);
  242.   yyComputeContinuation(yyStateStack,yyStackSize,yyStackPtr,&yyContinueSet);
  243.   yyContinueString[0] = '\0';
  244.   while (!IsEmpty(&yyContinueSet))
  245.    {
  246. $@    char *yyTokenString = @_TokenName[Extract(&yyContinueSet)];
  247.     if ((yyLength += strlen(yyTokenString)+1) >= 256)
  248.       break;
  249.     strcat(yyContinueString,yyTokenString);
  250.     strcat(yyContinueString," ");
  251.    }
  252. $@  ErrorMessageI(xxExpectedTokens,xxInformation,$_Attribute.Position,xxString,yyContinueString);
  253.   ReleaseSet(&yyContinueSet);
  254.   /* 3. compute the set of terminal symbols for restart of the parse */
  255.   MakeSet(&yyRestartSet,(short)yyLastTerminal);
  256.   yyComputeRestartPoints(yyStateStack,yyStackSize,yyStackPtr,&yyRestartSet);
  257.   /* 4. skip terminal symbols until a restart point is reached */
  258.   yyTokensSkipped = false;
  259.   while (!IsElement(*yyTerminal,&yyRestartSet))
  260.    {
  261. $@    *yyTerminal = $_GetToken();
  262.     yyTokensSkipped = true;
  263.    }
  264.   ReleaseSet(&yyRestartSet);
  265.   /* 5. report the restart point */
  266.   if (yyTokensSkipped)
  267.    {
  268. $@    ErrorMessage(xxRestartPoint,xxInformation,$_Attribute.Position);
  269.    }
  270.  }
  271.  
  272.  
  273. /* compute the set of terminal symbols that can be accepted (read)
  274.    in a given stack configuration (eventually after reduce actions) */
  275.  
  276. static void yyComputeContinuation(yyStateRange *yyStack, unsigned long yyStackSize, short yyStackPtr, tSet *yyContinueSet)
  277.  {
  278.   register yySymbolRange yyTerminal;
  279.   register yyStateRange yyState = yyStack[yyStackPtr];
  280.  
  281.   AssignEmpty(yyContinueSet);
  282.   for (yyTerminal = yyFirstTerminal;yyTerminal <= yyLastTerminal;yyTerminal++)
  283.    {
  284.     if (yyNext(yyState,yyTerminal) != yyNoState && yyIsContinuation(yyTerminal,yyStack,yyStackSize,yyStackPtr))
  285.       Include(yyContinueSet,(short)yyTerminal);
  286.    }
  287.  }
  288.  
  289.  
  290. /* check whether a given terminal symbol can be accepted (read)
  291.    in a certain stack configuration (eventually after reduce actions) */
  292.  
  293. static bool yyIsContinuation(yySymbolRange yyTerminal, yyStateRange *yyStateStack, unsigned long yyStackSize, short yyStackPtr)
  294.  {
  295.   register yyStateRange yState;
  296.   register yySymbolRange yyNonterminal;
  297.   yyStateRange *yyStack;
  298.  
  299.   MakeArray ((char **)&yyStack,&yyStackSize,sizeof(yyStateRange)); /* pass Stack by value */
  300.   #ifdef BCOPY
  301.     bcopy((char *)yyStateStack,(char *)yyStack,(int)sizeof(yyStateRange) * (yyStackPtr+1));
  302.   #else
  303.     memcpy((char *)yyStack,(char *)yyStateStack,(int)sizeof(yyStateRange) * (yyStackPtr+1));
  304.   #endif
  305.   yState = yyStack[yyStackPtr];
  306.   for (;;)
  307.    {
  308.     yyStack[yyStackPtr] = yState;
  309.     yState = yyNext(yState, yyTerminal);
  310.     if (yState == yyNoState)
  311.      {
  312.       ReleaseArray((char **)&yyStack,&yyStackSize,sizeof(yyStateRange));
  313.       return false;
  314.      }
  315.     if (yState <= yyLastReadTermState)
  316.      {/* read or read terminal reduce ? */
  317.       ReleaseArray((char **)&yyStack,&yyStackSize,sizeof(yyStateRange));
  318.       return true;
  319.      }
  320.     for (;;)
  321.      {/* reduce */
  322.       if (yState == yyStopState)
  323.        {
  324.         ReleaseArray((char **)&yyStack,&yyStackSize,sizeof(yyStateRange));
  325.         return true;
  326.        }
  327.       else
  328.        {
  329.         yyStackPtr -= yyLength[yState - yyFirstReduceState];
  330.         yyNonterminal = yyLeftHandSide[yState - yyFirstReduceState];
  331.        }
  332.       yState = yyNext(yyStack[yyStackPtr],yyNonterminal);
  333.       if (yyStackPtr >= yyStackSize)
  334.        {
  335.         ExtendArray((char **)&yyStack,&yyStackSize,sizeof(yyStateRange));
  336.        }
  337.       yyStackPtr++;
  338.       if (yState < yyFirstFinalState)
  339.         break; /* read nonterminal ? */
  340.       yState = yyFinalToProd[yState - yyFirstReadTermState]; /* read nonterminal reduce */
  341.      }
  342.    }
  343.  }
  344.  
  345.  
  346. /* compute a set of terminal symbols that can be used to restart
  347.    parsing in a given stack configuration. we simulate parsing until
  348.    end of file using a suffix program synthesized by the function
  349.    Continuation. All symbols acceptable in the states reached during
  350.    the simulation can be used to restart parsing. */
  351.  
  352. static void yyComputeRestartPoints(yyStateRange *yyStateStack, unsigned long yyStackSize, short yyStackPtr, tSet *yyRestartSet)
  353.  {
  354.   register yyStateRange yState;
  355.   register yySymbolRange yyNonterminal;
  356.   yyStateRange *yyStack;
  357.   tSet yyContinueSet;
  358.  
  359.   MakeArray ((char **)&yyStack,&yyStackSize,sizeof(yyStateRange)); /* pass Stack by value */
  360.   #ifdef BCOPY
  361.     bcopy((char *)yyStateStack,(char *)yyStack,(int)sizeof(yyStateRange) * (yyStackPtr+1));
  362.   #else
  363.     memcpy((char *)yyStack,(char *)yyStateStack,(int)sizeof(yyStateRange) * (yyStackPtr+1));
  364.   #endif
  365.   MakeSet(&yyContinueSet,(short)yyLastTerminal);
  366.   AssignEmpty(yyRestartSet);
  367.   yState = yyStack[yyStackPtr];
  368.   for (;;)
  369.    {
  370.     if (yyStackPtr >= yyStackSize)
  371.       ExtendArray((char **)&yyStack,&yyStackSize,sizeof(yyStateRange));
  372.     yyStack[yyStackPtr] = yState;
  373.     yyComputeContinuation(yyStack,yyStackSize,yyStackPtr,&yyContinueSet);
  374.     Union(yyRestartSet,&yyContinueSet);
  375.     yState = yyNext(yState,yyContinuation[yState]);
  376.     if (yState >= yyFirstFinalState)
  377.      {/* final state ? */
  378.       if (yState <= yyLastReadTermState)
  379.        {/* read terminal reduce ? */
  380.         yyStackPtr++;
  381.         yState = yyFinalToProd[yState - yyFirstReadTermState];
  382.        }
  383.       for (;;)
  384.        {/* reduce */
  385.         if (yState == yyStopState)
  386.          {
  387.           ReleaseSet(&yyContinueSet);
  388.           ReleaseArray((char **)&yyStack,&yyStackSize,sizeof(yyStateRange));
  389.           return;
  390.          }
  391.         else
  392.          {
  393.           yyStackPtr -= yyLength[yState - yyFirstReduceState];
  394.           yyNonterminal = yyLeftHandSide[yState - yyFirstReduceState];
  395.          }
  396.         yState = yyNext(yyStack[yyStackPtr],yyNonterminal);
  397.         yyStackPtr++;
  398.         if (yState < yyFirstFinalState)
  399.           break; /* read nonterminal ? */
  400.         yState = yyFinalToProd[yState - yyFirstReadTermState]; /* read nonterminal reduce */
  401.        }
  402.      }
  403.     else
  404.      {/* read */
  405.       yyStackPtr++;
  406.      }
  407.    }
  408.  }
  409.  
  410.  
  411. /* access the parse table:   Next : State x Symbol -> Action */
  412.  
  413. static yyStateRange yyNext(yyStateRange yyState,yySymbolRange yySymbol)
  414.  {
  415.   register yyTCombType *yyTCombPtr;
  416.  
  417.   if (yySymbol <= yyLastTerminal)
  418.    {
  419.     for (;;)
  420.      {
  421.       yyTCombPtr = yyTBasePtr[yyState] + yySymbol;
  422.       if (yyTCombPtr->Check != yyState)
  423.        {
  424.         if ((yyState = yyDefault[yyState]) == yyNoState)
  425.           return yyNoState;
  426.        }
  427.       else
  428.         return yyTCombPtr->Next;
  429.      }
  430.    }
  431.   else
  432.     return *(yyNBasePtr[yyState] + yySymbol);
  433.  }
  434.  
  435.  
  436. $@ static void Begin@(void)
  437.  {
  438. $B /* BEGIN section is inserted here */
  439.  }
  440.  
  441.  
  442. $@ void Close@(void)
  443.  {
  444. $C /* CLOSE section is inserted here */
  445.  }
  446.