home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / compcomp / yacc / y4.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-17  |  14.3 KB  |  498 lines
  1. /************************************************************************/
  2. /*                y4.c                    */
  3. /*  YACC source file #4 (of 4).                     */
  4. /************************************************************************/    
  5.      
  6. /************************************************************************/    
  7. /*                contents                */
  8. /*                                    */
  9. /*                                    */
  10. /*  * y4PutParser    Write out the parser: yyact, yypact, yypgo.    */
  11. /*  * y4PutArray    y4PutParser helper.                */
  12. /*    y4Optimize                            */
  13. /*  * y4EnterGoto    Enter goto on nonterminal i into array a.    */
  14. /*  * y4GetNumber    Read and convert an integer from stdin.     */
  15. /*  * y4NextI        Find the next i.                */
  16. /*  * y4OptSummary    Summarize optimizer performance.        */
  17. /*  * y4StoreState    Enter state i into the a array.         */
  18. /*                                    */
  19. /* * Local to this file.                        */
  20. /*                                    */
  21. /************************************************************************/
  22.     
  23.     
  24. /************************************************************************/   
  25. /*                              history                                 */    
  26. /*                                                                      */    
  27. /* 85Nov15 CrT  Global variable names decrypted.                        */
  28. /* 85Nov13 CrT    Give plaintiff routine in error messages.        */
  29. /* 85Nov12 CrT    Function names decrypted. Still unique in first 6 chars.*/
  30. /* 85Nov11 CrT    y4.c reconstructed from  8 subfiles.  Cosmetics.    */
  31. /* 80Dec18 RBD    ZAPFILE not used for decus compiler, fmkdl() used.    */
  32. /* 80Dec06 RBD    Broken out of y4.c, impure data in y4imp.c.        */
  33. /* 7?????? SCJ    Created.                        */
  34. /*                                                                      */ 
  35. /*                              credits                                 */ 
  36. /*      CrT=CrT                                                         */ 
  37. /*      RBD=Bob Denny                                                   */  
  38. /*      SCJ=Steven C Johnson.                                           */  
  39. /*      SG =Scott Guthery                                               */  
  40. /************************************************************************/ 
  41.  
  42.    
  43. #include <stdio.h>
  44. #include "system.h"
  45. #include "dtxtrn.h"
  46.                   
  47. #define yypact y1Temp
  48. #define y4Greed  y1StateType
  49.                   
  50. #define NOMORE -1000
  51.                   
  52. static int * y4GGreed = y1LookaheadSet[0].lset;
  53. static int * y4pgo    = y1WorkingSet[0].ws.lset;
  54. static int * yypgo  = &y2NonterminalState[0].tvalue;
  55.                   
  56. static int y4MaxSpread = 0;        /* Maximum spread of any entry.            */
  57. static int y4MaxOffset = 0;        /* Maximum offset into y1Action array.           */
  58. static int *y4FreePool    = y2Pool;
  59. static int *y4LastAction;
  60.  
  61. /* Debug switch for nextI. Set to TRUE for debugging printouts. */
  62. static int y4DebugNext     = 0;
  63.  
  64. /* Debugging switch for action optimization. Set to: */
  65. /*     0 for no debugging printouts.                 */
  66. /*     1 for no debugging printouts.             */
  67. /*     2 for general narration.                      */
  68. /*     3 for narration plus complete table dump.     */
  69.  
  70. static int y4DebugActions    = 0;
  71.  
  72. /************************************************************************/ 
  73. /*    y4PutParser    Write out the parser: yyact, yypact, yypgo.    */
  74. /************************************************************************/
  75. static y4PutParser() {        /* Called only by y4Optimize    */
  76.  
  77.     fprintf( y2ytabcFD, "# define YYLAST %d\n", y4LastAction-y1Action+1 );
  78.           
  79.     y4PutArray( "yyact" ,   y1Action, (y4LastAction-y1Action)+1 );
  80.     y4PutArray( "yypact",  y1GotoIndex, y1NextState    );
  81.     y4PutArray( "yypgo" , y4pgo, y2LastNonterminal+1  );
  82. }
  83.  
  84. /************************************************************************/
  85. /*    y4PutArray    y4PutParser helper.                */
  86. /************************************************************************/
  87. y4PutArray( s, v, n )        /* Called only by y4PutParser. */
  88. char *s;
  89. int  *v, n;
  90. {
  91.     register i;
  92.           
  93.     fprintf( y2ytabcFD, "short %s[]={\n", s );
  94.  
  95.     for (i = 0;   i < n;   ) {
  96.  
  97.     if (i % 10   ==   0)   fprintf( y2ytabcFD, "\n"    );
  98.  
  99.     fprintf( y2ytabcFD, "%4d", v[i] );
  100.  
  101.     if (++i == n)           fprintf( y2ytabcFD, " };\n" );
  102.     else               fprintf( y2ytabcFD, ","       );
  103.     }
  104. }
  105.  
  106. /************************************************************************/
  107. /*    y4Optimize    Read the arrays from tempfile, set parameters.    */
  108. /************************************************************************/
  109. y4Optimize() {        /* Called only from main. */
  110.            
  111.     register i, *p, j, k, *q; 
  112.            
  113.     /* Read the arrays from tempfile and set parameters: */ 
  114.   
  115.     if ((y2InputFD = fopen(TEMPNAME,"r"))   ==     NULL) {
  116.     y1Error( "y4Optimize: Cannot open tempfile" );
  117.     } 
  118.   
  119.     y4pgo[0]      = 0;
  120.     yypact[0]   = 0; 
  121.     y1NextState      = 0;
  122.     y2LastNonterminal      = 0;
  123.   
  124.     loop {
  125.   
  126.         switch (y4GetNumber()) { 
  127.   
  128.     case '\n':    yypact[++y1NextState] = (--y4FreePool) - y2Pool;     continue;
  129.         case ',':                                               continue; 
  130.         case '$':                                               break; 
  131.         default: 
  132.         y1Error( "y4Optimize: Bad tempfile(1)" );
  133.         } 
  134.         break; 
  135.     } 
  136.            
  137.     yypact[ y1NextState ]    = yypgo[0]  = (--y4FreePool) - y2Pool;
  138.            
  139.     loop {
  140.   
  141.         switch (y4GetNumber()) { 
  142.   
  143.     case '\n':    yypgo[++y2LastNonterminal]= y4FreePool-y2Pool;          continue;
  144.         case '\r':                                              continue; 
  145.         case ',' :                                              continue; 
  146.         case -1  :      /* EOF */                               break; 
  147.         default: 
  148.         y1Error( "y4Optimize: Bad tempfile(2)" );
  149.         } 
  150.         break; 
  151.     } 
  152.            
  153.     yypgo[ y2LastNonterminal-- ]  = (--y4FreePool) - y2Pool;
  154.   
  155.     for (i = 0;   i < y1NextState;   ++i) {
  156.         k = 32000; 
  157.         j = 0; 
  158.     q = y2Pool + yypact[i+1];
  159.     for (p = y2Pool + yypact[i];   p < q;    p += 2) {
  160.   
  161.             if (*p > j)   j = *p; 
  162.             if (*p < k)   k = *p; 
  163.         } 
  164.   
  165.         if (k <= j) { 
  166.   
  167.             /***********************************************/ 
  168.             /* Nontrivial situation.                       */ 
  169.             /* Temporarily, kill this for compatibility    */ 
  170.             /* j -= k;  j is now the range                 */ 
  171.             /***********************************************/ 
  172.   
  173.         if (k > y4MaxOffset)   y4MaxOffset = k;
  174.         } 
  175.     y4Greed[i]    = (yypact[ i+1 ] - yypact[ i ])    +   2 * j;
  176.   
  177.     if (j > y4MaxSpread)   y4MaxSpread = j;
  178.     } 
  179.            
  180.     /* Initialize y4GGreed table: */
  181.            
  182.     for (i = 1;   i <= y2LastNonterminal;   ++i) {
  183.   
  184.     y4GGreed[i] = 1;
  185.         j = 0; 
  186.   
  187.         /* Minimum entry index is always 0: */ 
  188.     q = y2Pool + yypgo[i+1] -1;
  189.   
  190.     for (p = y2Pool + yypgo[ i ];    p < q;     p += 2) {
  191.   
  192.         y4GGreed[i] += 2;
  193.   
  194.             if (*p > j)   j = *p; 
  195.         } 
  196.     y4GGreed[ i ] = y4GGreed[ i ]    +   2 * j;
  197.   
  198.     if (j > y4MaxOffset)   y4MaxOffset = j;
  199.     } 
  200.            
  201.     /* Prepare to put the shift actions into the y1Action array: */
  202.            
  203.     for (i = 0;   i < MAXaCTIONS;   ++i)   y1Action[i] = 0;
  204.     y4LastAction = y1Action;
  205.            
  206.     for (i = 0;   i < y1NextState;   ++i) {
  207.   
  208.     if (y4Greed[ i ] == 0    &&   y4DebugActions > 1) {
  209.   
  210.         fprintf( y2ytabcFD, "State %d: null\n", i );
  211.         } 
  212.     y1GotoIndex[i] = YYFLAG1;
  213.     } 
  214.            
  215.     while ((i = y4NextI())   !=   NOMORE) { 
  216.   
  217.         if (i >= 0)   y4StoreState(  i ); 
  218.         else          y4EnterGoto(  -i ); 
  219.            
  220.     } 
  221.            
  222.     if (y4DebugActions > 2) {
  223.   
  224.     /* Print y1Action array: */
  225.     for (p = y1Action;   p <= y4LastAction;   p += 10) {
  226.   
  227.         fprintf( y2ytabcFD, "%4d  ", p-y1Action );
  228.   
  229.         for (i = 0;   i < 10;   ++i)   fprintf( y2ytabcFD, "%4d  ", p[i] );
  230.   
  231.         fprintf( y2ytabcFD, "\n" );
  232.         } 
  233.     } 
  234.   
  235.     /* Write out the output appropriate to the language: */ 
  236.     y4PutParser(); 
  237.            
  238.     y4OptSummary(); 
  239.            
  240.     fclose( y2InputFD );
  241.   
  242.     ZAPFILE(TEMPNAME); 
  243. } 
  244.  
  245. /************************************************************************/
  246. /*    y4EnterGoto    Enter goto on nonterminal i into array y1Action.       */
  247. /************************************************************************/
  248. y4EnterGoto( i )    /* Called only from y4Optimize. */
  249. int i;
  250. {
  251.     register *p, *r, *s, *q1, *q2;
  252.           
  253.     y4GGreed[ i ] = 0;
  254.           
  255.     q2    = y2Pool + yypgo[i+1] - 1;
  256.     q1    = y2Pool + yypgo[i  ]     ;
  257.           
  258.     /* Find a place for it: */
  259.           
  260.     for (p = y1Action;     p < &y1Action[MAXaCTIONS];   ++p) {
  261.  
  262.     if (*p)   continue;
  263.  
  264.     for (r = q1;   r < q2;     r += 2) {
  265.  
  266.         s = p + *r +1;
  267.  
  268.         if (*s)   goto nextgp;
  269.  
  270.         if (s > y4LastAction) {
  271.         if ((y4LastAction = s) > &y1Action[ MAXaCTIONS ])   {
  272.             y1Error( "y4EnterGoto: Array y1Action[] overflowed(1)" );
  273.         }
  274.             } 
  275.     }
  276.  
  277.         /* We have found a spot: */
  278.           
  279.     *p  = *q2;
  280.  
  281.     if (p > y4LastAction) {
  282.  
  283.         if ((y4LastAction = p)   >     &y1Action[ MAXaCTIONS ]) {
  284.         y1Error( "y4EnterGoto: Array y1Action[] overflowed(2)" );
  285.         }
  286.     }
  287.  
  288.     for (r = q1;   r < q2;     r += 2) {
  289.  
  290.         s  = p + *r + 1;
  291.         *s = r[ 1 ]    ;
  292.     }
  293.           
  294.     y4pgo[ i ]    = p - y1Action;
  295.  
  296.     if (y4DebugActions > 1) {
  297.         fprintf(
  298.         y2ytabcFD,
  299.         "Nonterminal %d, entry at %d\n",
  300.         i,
  301.         y4pgo[i]
  302.         );
  303.     }
  304.     goto nextgi;
  305. nextgp: ;
  306.  
  307.     }
  308.     y1Error( "y4EnterGoto: Cannot place goto %d\n", i );
  309.           
  310. nextgi:   
  311.     ;
  312. }
  313.  
  314. /************************************************************************/
  315. /*    y4GetNumber    Read and convert an integer from stdin.     */
  316. /************************************************************************/
  317. static y4GetNumber() {        /* Called only from y4Optimize. */
  318.     register s, val, c;
  319.           
  320.    /*********************************************************/
  321.    /* Read and convert an integer from the standard input.  */
  322.    /* Return the terminating character.             */
  323.    /* Blanks, tabs, and newlines are ignored.            */
  324.    /*********************************************************/
  325.  
  326.    s    = 1;
  327.    val    = 0;
  328.           
  329.    while  ((c = y1GetChar( y2InputFD ))   !=   EOF) {
  330.  
  331.     if    (isdigit( c ))      val = val * 10   +   (c - '0');
  332.     else if ( c == '-'   )      s   = -1            ;
  333.     else if ( c == '\r'  )      continue            ;
  334.     else              break             ;
  335.  
  336.     }
  337.  
  338.     *y4FreePool++ = s * val;
  339.  
  340.     if (y4FreePool > &y2Pool[ MAXy2POOL ])   y1Error( "y4GetNumber: Out of space" );
  341.  
  342.     return   c;
  343. }
  344.  
  345. /************************************************************************/
  346. /*    y4NextI     Find the next i.                */
  347. /************************************************************************/
  348. static y4NextI() {    /* Called only from y4Optimize. */
  349.     register i, max, maxi;
  350.           
  351.     max = 0;
  352.           
  353.     for (i = 1;   i <= y2LastNonterminal;   ++i){
  354.  
  355.     if( y4GGreed[i] >= max ) {
  356.  
  357.         max     = y4GGreed[i];
  358.         maxi    = -i;
  359.     }
  360.     }
  361.           
  362.     for (i = 0;   i < y1NextState;   ++i) {
  363.  
  364.     if (y4Greed[ i ]   >=    max) {
  365.  
  366.         max     = y4Greed[i];
  367.         maxi    = i;
  368.     }
  369.     }
  370.           
  371.     if (y4DebugNext    )   fprintf( y2ytabcFD, "nxti = %d, max = %d\n", maxi, max );
  372.     if (max == 0)   return NOMORE;
  373.     else        return maxi  ;
  374. }
  375.  
  376. /************************************************************************/
  377. /*    y4OptSummary      Summary optimizer performance.                  */
  378. /************************************************************************/
  379. static y4OptSummary() {     /* Called only from y4Optimize. */
  380.  
  381.     register int i, *p;
  382.           
  383.     if (y2OutputFD == NULL)   return;
  384.           
  385.     i    = 0;
  386.  
  387.     for (p = y4LastAction;   p >= y1Action;   --p) {
  388.  
  389.     if (*p == 0)   ++i;
  390.     }
  391.  
  392.     fprintf(
  393.     y2OutputFD,
  394.     "Optimizer space used: input %d/%d, output %d/%d\n",
  395.     y4FreePool-y2Pool+1,
  396.     MAXy2POOL,
  397.     y4LastAction - y1Action +1,
  398.     MAXaCTIONS
  399.     );
  400.     fprintf(   y2OutputFD,   "%d table entries, %d zero\n",   (y4LastAction-y1Action)+1,   i);
  401.  
  402.     fprintf(
  403.     y2OutputFD,
  404.     "maximum spread: %d, maximum offset: %d\n",
  405.     y4MaxSpread,
  406.     y4MaxOffset
  407.     );
  408.     fclose( y2OutputFD );
  409. }
  410.  
  411. /************************************************************************/
  412. /*    y4StoreState    Enter state i into the y1Action array.               */
  413. /************************************************************************/
  414. static y4StoreState( i )    /* Called only from y4Optimize. */
  415. int i;
  416. {
  417.     register *r, *s, n, flag, j, *q1, *q2;
  418.           
  419.     y4Greed[ i ]  = 0;
  420.           
  421.     q2    = y2Pool + yypact[ i+1 ];
  422.     q1    = y2Pool + yypact[ i   ];
  423.  
  424.     /* Find an acceptable place: */
  425.           
  426.     for (n = -y4MaxOffset;   n < MAXaCTIONS;   ++n) {
  427.  
  428.     flag = 0;
  429.  
  430.     for (r = q1;   r < q2;     r += 2) {
  431.  
  432.         if ((s = *r + n + y1Action)   <   y1Action)   goto nextn;
  433.  
  434.         if (*s == 0)       ++flag;
  435.         else if (*s != r[1])   goto nextn;
  436.     }
  437.           
  438.         /********************************************/
  439.     /* Check that the position equals another   */
  440.     /* only if the states are identical:        */
  441.         /********************************************/
  442.  
  443.     for (j = 0;   j < y1NextState;     ++j) {
  444.  
  445.         if (y1GotoIndex[ j ] == n) {
  446.  
  447.         if (flag)   goto nextn;  /* We have some disagreement. */
  448.  
  449.         if (yypact[ j+1 ] + yypact[i]    ==   yypact[j] + yypact[i+1]) {
  450.  
  451.             /* States are equal: */
  452.             y1GotoIndex[ i ] = n;
  453.  
  454.             if (y4DebugActions > 1) {
  455.             fprintf(
  456.                 y2ytabcFD,
  457.                 "State %d: entry at %d equals state %d\n",
  458.                 i,
  459.                 n,
  460.                 j
  461.             );
  462.             }
  463.             return;
  464.         }
  465.  
  466.         /* We have some disagreement: */
  467.         goto nextn;
  468.         }
  469.     }
  470.           
  471.     for (r = q1;   r < q2;     r += 2) {
  472.  
  473.         if ((s = *r + n + y1Action)   >=   &y1Action[ MAXaCTIONS ]) {
  474.         y1Error( "y4StoreState: Out of space in optimizer y1Action[] array" );
  475.         }
  476.  
  477.         if (s > y4LastAction)   y4LastAction = s;
  478.  
  479.             if (*s != 0   &&   *s != r[1]) {
  480.         y1Error(
  481.             "y4StoreState: y1Action[] array clobbered, pos'n %d, by %d",
  482.             s-y1Action,
  483.             r[1]
  484.         );
  485.         }
  486.         *s = r[1];
  487.     }
  488.     y1GotoIndex[ i ] = n;
  489.  
  490.     if (y4DebugActions > 1)   fprintf( y2ytabcFD, "State %d: entry at %d\n", i, y1GotoIndex[i] );
  491.  
  492.         return; 
  493.           
  494. nextn:    ;
  495.     }
  496.     y1Error( "y4StoreState: Failed to place state %d\n",   i   );
  497. }
  498.