home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / jikepg12.zip / jikespg / src / tabutil.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-11-04  |  50.4 KB  |  1,552 lines
  1. /* $Id: tabutil.c,v 1.2 1999/11/04 14:02:23 shields Exp $ */
  2. /*
  3.  This software is subject to the terms of the IBM Jikes Compiler
  4.  License Agreement available at the following URL:
  5.  http://www.ibm.com/research/jikes.
  6.  Copyright (C) 1983, 1999, International Business Machines Corporation
  7.  and others.  All Rights Reserved.
  8.  You must accept the terms of that agreement to use this software.
  9. */
  10. static char hostfile[] = __FILE__;
  11.  
  12. #include <string.h>
  13. #include "common.h"
  14. #include "header.h"
  15.  
  16. static const char digits[] = "0123456789";
  17.  
  18. /**************************************************************************/
  19. /*                           PRNT_SHORTS:                                 */
  20. /**************************************************************************/
  21. void prnt_shorts(char *title, int init, int bound, int perline, short *array)
  22. {
  23.     int i,
  24.         k;
  25.  
  26.     mystrcpy(title);
  27.  
  28.     padline();
  29.     k = 0;
  30.     for (i = init; i <= bound; i++)
  31.     {
  32.         itoc(array[i]);
  33.         *output_ptr++ = COMMA;
  34.         k++;
  35.         if (k == perline && i != bound)
  36.         {
  37.             *output_ptr++ = '\n';
  38.             BUFFER_CHECK(sysdcl);
  39.             padline();
  40.             k = 0;
  41.         }
  42.     }
  43.     if (k != 0)
  44.     {
  45.         *(output_ptr - 1) = '\n';
  46.         BUFFER_CHECK(sysdcl);
  47.     }
  48.  
  49.     if (java_bit)
  50.          mystrcpy("    };\n");
  51.     else mystrcpy("                 };\n");
  52.  
  53.     return;
  54. }
  55.  
  56.  
  57. /**************************************************************************/
  58. /*                              PRNT_INTS:                                */
  59. /**************************************************************************/
  60. void prnt_ints(char *title, int init, int bound, int perline, int *array)
  61. {
  62.     int i,
  63.         k;
  64.  
  65.     mystrcpy(title);
  66.  
  67.     padline();
  68.     k = 0;
  69.     for (i = init; i <= bound; i++)
  70.     {
  71.         itoc(array[i]);
  72.         *output_ptr++ = COMMA;
  73.         k++;
  74.         if (k == perline && i != bound)
  75.         {
  76.             *output_ptr++ = '\n';
  77.             BUFFER_CHECK(sysdcl);
  78.             padline();
  79.             k = 0;
  80.         }
  81.     }
  82.     if (k != 0)
  83.     {
  84.         *(output_ptr - 1) = '\n';
  85.         BUFFER_CHECK(sysdcl);
  86.     }
  87.  
  88.     if (java_bit)
  89.          mystrcpy("    };\n");
  90.     else mystrcpy("                 };\n");
  91.  
  92.     return;
  93. }
  94.  
  95.  
  96. /***************************************************************************/
  97. /*                               MYSTRCPY:                                 */
  98. /***************************************************************************/
  99. void mystrcpy(char *str)
  100. {
  101.     while (*str != '\0')
  102.          *output_ptr++ = *str++;
  103.  
  104.     BUFFER_CHECK(sysdcl);
  105.  
  106.     return;
  107. }
  108.  
  109.  
  110. /***************************************************************************/
  111. /*                               PADLINE:                                  */
  112. /***************************************************************************/
  113. void padline(void)
  114. {
  115.     register int i;
  116.  
  117.     for (i = 0; i < 12; i++)
  118.         *output_ptr++ = ' ';
  119.  
  120.     return;
  121. }
  122.  
  123.  
  124. /***************************************************************************/
  125. /*                                 ITOC:                                   */
  126. /***************************************************************************/
  127. /* ITOC takes as arguments an integer NUM. NUM is an integer containing at */
  128. /* most 11 digits which is converted into a character string and placed in  */
  129. /* the iobuffer.  Leading zeros are eliminated and if the number is        */
  130. /* negative, a leading "-" is added.                                       */
  131. /***************************************************************************/
  132. void itoc(int num)
  133. {
  134.     register int  val;
  135.     register char *p;
  136.     char tmp[12];
  137.  
  138.     val = ABS(num);
  139.     tmp[11] = '\0';
  140.     p = &tmp[11];
  141.     do
  142.     {
  143.         p--;
  144.         *p = digits[val % 10];
  145.         val /= 10;
  146.     } while(val > 0);
  147.  
  148.     if (num < 0)
  149.     {
  150.         p--;
  151.         *p = '-';
  152.     }
  153.  
  154.     while(*p != '\0')
  155.         *(output_ptr++) = *(p++);
  156.  
  157.     return;
  158. }
  159.  
  160.  
  161. /***************************************************************************/
  162. /*                                 FIELD:                                  */
  163. /***************************************************************************/
  164. /* FIELD takes as arguments two integers: NUM and LEN.  NUM is an integer  */
  165. /* containing at most LEN digits which is converted into a character       */
  166. /* string and placed in the iobuffer.                                      */
  167. /* Leading zeros are replaced by blanks and if the number is negative,  a  */
  168. /* leading "-" is added.                                                   */
  169. /***************************************************************************/
  170. void field(int num, int len)
  171. {
  172.     register int val;
  173.     register char *p;
  174.  
  175.     val = ABS(num);
  176.     p = output_ptr + len;
  177.     do
  178.     {
  179.         p--;
  180.         *p = digits[val % 10];
  181.         val /= 10;
  182.     } while(val > 0 && p > output_ptr);
  183.  
  184.     if (num < 0 && p > output_ptr)
  185.     {
  186.         p--;
  187.         *p = '-';
  188.     }
  189.  
  190.     while(p > output_ptr)
  191.     {
  192.         p--;
  193.         *p = ' ';
  194.     }
  195.  
  196.     output_ptr += len;
  197.  
  198.     return;
  199. }
  200.  
  201.  
  202. /***************************************************************************/
  203. /*                            SORTDES:                                     */
  204. /***************************************************************************/
  205. /*  SORTDES sorts the elements of ARRAY and COUNT in the range LOW..HIGH   */
  206. /* based on the values of the elements of COUNT. Knowing that the maximum  */
  207. /* value of the elements of count cannot exceed MAX and cannot be lower    */
  208. /* than zero, we can use a bucket sort technique.                          */
  209. /***************************************************************************/
  210. void sortdes(short array[], short count[], int low, int high, int max)
  211. {
  212.     short *bucket,
  213.           *list;
  214.  
  215.     register int element,
  216.              i,
  217.              k;
  218.  
  219.     /*****************************************************************/
  220.     /* BUCKET is used to hold the roots of lists that contain the    */
  221.     /* elements of each bucket.  LIST is used to hold these lists.   */
  222.     /*****************************************************************/
  223.     bucket = Allocate_short_array(max + 1);
  224.     list = Allocate_short_array(high - low + 1);
  225.  
  226.     for (i = 0; i <= max; i++)
  227.         bucket[i] = NIL;
  228.  
  229. /*********************************************************************/
  230. /* We now partition the elements to be sorted and place them in their*/
  231. /* respective buckets.  We iterate backward over ARRAY and COUNT to  */
  232. /* keep the sorting stable since elements are inserted in the buckets*/
  233. /* in stack-fashion.                                                 */
  234. /*                                                                   */
  235. /*   NOTE that it is known that the values of the elements of ARRAY  */
  236. /* also lie in the range LOW..HIGH.                                  */
  237. /*********************************************************************/
  238.     for (i = high; i >= low; i--)
  239.     {
  240.         k = count[i];
  241.         element = array[i];
  242.         list[element - low] = bucket[k];
  243.         bucket[k] = element;
  244.     }
  245.  
  246. /*********************************************************************/
  247. /* Iterate over each bucket, and place elements in ARRAY and COUNT   */
  248. /* in sorted order.  The iteration is done backward because we want  */
  249. /* the arrays sorted in descending order.                            */
  250. /*********************************************************************/
  251.     k = low;
  252.     for (i = max; i >= 0; i--)
  253.     {
  254.         for (element = bucket[i];
  255.              element != NIL; element = list[element - low], k++)
  256.         {
  257.             array[k] = element;
  258.             count[k] = i;
  259.         }
  260.     }
  261.     ffree(bucket);
  262.     ffree(list);
  263.  
  264.     return;
  265. }
  266.  
  267.  
  268. /***************************************************************************/
  269. /*                              REALLOCATE:                                */
  270. /***************************************************************************/
  271. /*   This procedure is invoked when the TABLE being used is not large      */
  272. /* enough.  A new table is allocated, the information from the old table   */
  273. /* is copied, and the old space is released.                               */
  274. /***************************************************************************/
  275. void reallocate(void)
  276. {
  277.     int *n,
  278.         *p;
  279.  
  280.     register int old_size,
  281.                  i;
  282.  
  283.     if (table_size == MAX_TABLE_SIZE)
  284.     {
  285.         sprintf(msg_line, "Table has exceeded maximum limit of %d",
  286.                           MAX_TABLE_SIZE);
  287.         PRNTERR(msg_line);
  288.         exit(12);
  289.     }
  290.  
  291.     old_size = table_size;
  292.     table_size = MIN(table_size + increment_size, MAX_TABLE_SIZE);
  293.  
  294.     if (verbose_bit)
  295.     {
  296.         if (table_opt == OPTIMIZE_TIME)
  297.         {
  298.             sprintf(msg_line,
  299.                     "Reallocating storage for TIME table, "
  300.                     "adding %d entries", table_size - old_size);
  301.         }
  302.         else
  303.         {
  304.             sprintf(msg_line,
  305.                     "Reallocating storage for SPACE table, "
  306.                     "adding %d entries", table_size - old_size);
  307.         }
  308.         PRNT(msg_line);
  309.     }
  310.  
  311.     n = Allocate_int_array(table_size + 1);
  312.     p = Allocate_int_array(table_size + 1);
  313.  
  314.     for (i = 1; i <= old_size; i++) /* Copy old information */
  315.     {
  316.         n[i] = next[i];
  317.         p[i] = previous[i];
  318.     }
  319.  
  320.     ffree(next);
  321.     ffree(previous);
  322.  
  323.     next = n;
  324.     previous = p;
  325.  
  326.     if (first_index == NIL)
  327.     {
  328.         first_index = old_size + 1;
  329.         previous[first_index] = NIL;
  330.     }
  331.     else
  332.     {
  333.         next[last_index] = old_size + 1;
  334.         previous[old_size + 1] = last_index;
  335.     }
  336.  
  337.     next[old_size + 1] = old_size + 2;
  338.     for (i = old_size + 2; i < (int) table_size; i++)
  339.     {
  340.         next[i] = i + 1;
  341.         previous[i] = i - 1;
  342.     }
  343.     last_index = table_size;
  344.     next[last_index] = NIL;
  345.     previous[last_index] = last_index - 1;
  346.  
  347.     return;
  348. }
  349.  
  350.  
  351. /*****************************************************************************/
  352. /*                            PROCESS_ERROR_MAPS:                            */
  353. /*****************************************************************************/
  354. /* if ERROR_MAPS are requested, we print them out in the following order:    */
  355. /*                                                                           */
  356. /*   1) The FOLLOW map (NEWFOLL)                                             */
  357. /*   2) The SORTED_STATE vector                                              */
  358. /*   3) The ORIGINAL_STATE vector                                            */
  359. /*   4) The map from states into valid symbols on which actions are          */
  360. /*      defined within the state in question: ACTION_SYMBOLS                 */
  361. /*   5) The map from each symbol into the set of staes that can              */
  362. /*      possibly be reached after a transition on the symbol in              */
  363. /*      question: TRANSITION_STATES                                          */
  364. /*                                                                           */
  365. /*****************************************************************************/
  366. void process_error_maps(void)
  367. {
  368.     short *state_start,
  369.           *state_stack,
  370.           *temp,
  371.           *original = NULL,
  372.           *symbol_root,
  373.           *symbol_count,
  374.           *term_list,
  375.           *as_size,
  376.           *action_symbols_range,
  377.           *naction_symbols_range;
  378.  
  379.     int offset,
  380.         item_no,
  381.         lhs_symbol,
  382.         state_no,
  383.         symbol,
  384.         max_len,
  385.         i,
  386.         k,
  387.  
  388.         terminal_ubound,
  389.         non_terminal_ubound;
  390.  
  391.     long num_bytes;
  392.  
  393.     char tok[SYMBOL_SIZE + 1];
  394.  
  395.     terminal_ubound = (table_opt == OPTIMIZE_TIME
  396.                                  ?  num_symbols
  397.                                  :  num_terminals);
  398.  
  399.     non_terminal_ubound = (table_opt == OPTIMIZE_TIME
  400.                                      ?  num_symbols
  401.                                      :  num_non_terminals);
  402.  
  403.     symbol_root = Allocate_short_array(num_symbols + 1);
  404.     symbol_count = Allocate_short_array(num_symbols + 1);
  405.     state_start = Allocate_short_array(num_states + 2);
  406.     state_stack = Allocate_short_array(num_states + 1);
  407.     term_list = Allocate_short_array(num_symbols + 1);
  408.  
  409.     PRNT("\nError maps storage:");
  410.  
  411. /*********************************************************************/
  412. /* The FOLLOW map is written out as two vectors where the first      */
  413. /* vector indexed by a Symbol gives the starting location in the     */
  414. /* second vector where the elements of the follow set of that symbol */
  415. /* starts.  Note that since the terminal and non-terminal symbols    */
  416. /* have been intermixed, the FOLLOW map is written out with the      */
  417. /* complete set of symbols as its domain even though it is only      */
  418. /* defined on non-terminals.                                         */
  419. /*                                                                   */
  420. /* We now compute and write the starting location for each symbol.   */
  421. /* The offset for the first symbol is 1,  and hence does not         */
  422. /* have to be computed.  However,  we compute an extra offset to     */
  423. /* indicate the extent of the last symbol.                           */
  424. /*********************************************************************/
  425.     for (symbol = 1; symbol <= non_terminal_ubound; symbol++)
  426.     {
  427.         symbol_count[symbol] = 0;
  428.         symbol_root[symbol] = OMEGA;
  429.     }
  430.  
  431.     for ALL_NON_TERMINALS(lhs_symbol)
  432.     {
  433.         if (table_opt == OPTIMIZE_TIME)
  434.             symbol = symbol_map[lhs_symbol];
  435.         else
  436.             symbol = symbol_map[lhs_symbol] - num_terminals;
  437.         symbol_root[symbol] = lhs_symbol;
  438.         for ALL_TERMINALS(i)
  439.         {
  440.             if IS_IN_SET(follow, (lhs_symbol + 1), (i + 1))
  441.                symbol_count[symbol]++;
  442.         }
  443.     }
  444.  
  445.     offset = 1;
  446.     k = 1;
  447.     field(offset, 6);     /* Offset of the first state */
  448.     for (symbol = 1; symbol <= non_terminal_ubound; symbol++)
  449.     {
  450.         offset += symbol_count[symbol];
  451.         field(offset, 6);
  452.         k++;
  453.         if (k == 12)
  454.         {
  455.             *output_ptr++ = '\n';
  456.             BUFFER_CHECK(systab);
  457.             k = 0;
  458.         }
  459.     }
  460.     if (k != 0)
  461.     {
  462.         *output_ptr++ = '\n';
  463.         BUFFER_CHECK(systab);
  464.     }
  465.  
  466.     /***************************************************************/
  467.     /*  We now write the elements in the range of the FOLLOW map.  */
  468.     /***************************************************************/
  469.     k = 0;
  470.     for (symbol = 1; symbol <= non_terminal_ubound; symbol++)
  471.     {
  472.         lhs_symbol = symbol_root[symbol];
  473.         if (lhs_symbol != OMEGA)
  474.         {
  475.             for ALL_TERMINALS(i)
  476.             {
  477.                 if IS_IN_SET(follow, (lhs_symbol + 1), (i + 1))
  478.                 {
  479.                     field(symbol_map[i], 4);
  480.                     k++;
  481.                     if (k == 18)
  482.                     {
  483.                         *output_ptr++ = '\n';
  484.                         BUFFER_CHECK(systab);
  485.                         k = 0;
  486.                     }
  487.                 }
  488.             }
  489.         }
  490.     }
  491.     if (k != 0)
  492.     {
  493.         *output_ptr++ = '\n';
  494.         BUFFER_CHECK(systab);
  495.     }
  496.  
  497.     /*****************************************************************/
  498.     /* Compute and list amount of space required for the Follow map. */
  499.     /*****************************************************************/
  500.     if (table_opt == OPTIMIZE_TIME)
  501.     {
  502.         num_bytes = 2 * (num_symbols + offset);
  503.         if (byte_bit)
  504.         {
  505.             if (last_non_terminal <= 255)
  506.                 num_bytes = num_bytes - offset + 1;
  507.         }
  508.     }
  509.     else
  510.     {
  511.         num_bytes = 2 * (num_non_terminals + offset);
  512.         if (byte_bit)
  513.         {
  514.             if (num_terminals <= 255)
  515.                 num_bytes = num_bytes - offset + 1;
  516.         }
  517.     }
  518.     sprintf(msg_line,
  519.             "    Storage required for FOLLOW map: %d Bytes",
  520.             num_bytes);
  521.     PRNT(msg_line);
  522.  
  523.     /**************************************************************/
  524.     /* We now write out the states in sorted order: SORTED_STATE. */
  525.     /**************************************************************/
  526.     k = 0;
  527.     for ALL_STATES(i)
  528.     {
  529.         field(ordered_state[i], 6);
  530.         k++;
  531.         if (k == 12)
  532.         {
  533.             *output_ptr++ = '\n';
  534.             BUFFER_CHECK(systab);
  535.             k = 0;
  536.         }
  537.     }
  538.     if (k != 0)
  539.     {
  540.         *output_ptr++ = '\n';
  541.         BUFFER_CHECK(systab);
  542.     }
  543.  
  544.     /*****************************************************************/
  545.     /* Compute and list space required for SORTED_STATE map.         */
  546.     /*****************************************************************/
  547.     num_bytes = 2 * num_states;
  548.     sprintf(msg_line,
  549.             "    Storage required for SORTED_STATE map: %d Bytes",
  550.             num_bytes);
  551.     PRNT(msg_line);
  552.  
  553.     /********************************************************************/
  554.     /* We now write a vector parallel to SORTED_STATE that gives us the */
  555.     /* original number associated with the state: ORIGINAL_STATE.       */
  556.     /********************************************************************/
  557.     k = 0;
  558.     for (i = 1; i <= (int) num_states; i++)
  559.     {
  560.         field(state_list[i], 6);
  561.         k++;
  562.         if (k == 12)
  563.         {
  564.             *output_ptr++ = '\n';
  565.             BUFFER_CHECK(systab);
  566.             k = 0;
  567.         }
  568.     }
  569.     if (k != 0)
  570.     {
  571.         *output_ptr++ = '\n';
  572.         BUFFER_CHECK(systab);
  573.     }
  574.  
  575.     /*****************************************************************/
  576.     /* Compute and list space required for ORIGINAL_STATE map.       */
  577.     /*****************************************************************/
  578.     num_bytes = 2 * num_states;
  579.     sprintf(msg_line,
  580.             "    Storage required for ORIGINAL_STATE map: %d Bytes",
  581.             num_bytes);
  582.     PRNT(msg_line);
  583.  
  584.     /********************************************************************/
  585.     /* We now construct a bit map for the set of terminal symbols that  */
  586.     /* may appear in each state. Then, we invoke PARTSET to apply the   */
  587.     /* Partition Heuristic and print it.                                */
  588.     /********************************************************************/
  589.     as_size = Allocate_short_array(num_states + 1);
  590.  
  591.     if (table_opt == OPTIMIZE_TIME)
  592.     {
  593.         original = Allocate_short_array(num_symbols + 1);
  594.  
  595.         /*************************************************************/
  596.         /* In a compressed TIME table, the terminal and non-terminal */
  597.         /* symbols are mixed together when they are remapped.        */
  598.         /* We shall now recover the original number associated with  */
  599.         /* each terminal symbol since it lies very nicely in the     */
  600.         /* range 1..NUM_TERMINALS.  This will save a considerable    */
  601.         /* amount of space in the bit_string representation of sets  */
  602.         /* as well as time when operations are performed on those    */
  603.         /* bit-strings.                                              */
  604.         /*************************************************************/
  605.         for ALL_TERMINALS(symbol)
  606.             original[symbol_map[symbol]] = symbol;
  607.     }
  608.  
  609. /***********************************************************************/
  610. /* NOTE that the arrays ACTION_SYMBOLS and NACTION_SYMBOLS are global  */
  611. /* variables that are allocated in the procedure PROCESS_TABLES by     */
  612. /* calloc which automatically initializes them to 0.                   */
  613. /***********************************************************************/
  614.     for ALL_STATES(state_no)
  615.     {
  616.         struct shift_header_type  sh;
  617.         struct reduce_header_type red;
  618.  
  619.         sh = shift[statset[state_no].shift_number];
  620.         as_size[state_no] = sh.size;
  621.         for (i = 1; i <= sh.size; i++)
  622.         {
  623.             if (table_opt == OPTIMIZE_TIME)
  624.                 symbol = original[SHIFT_SYMBOL(sh, i)];
  625.             else
  626.                 symbol = SHIFT_SYMBOL(sh, i);
  627.             SET_BIT_IN(action_symbols, state_no, symbol);
  628.         }
  629.  
  630.         red = reduce[state_no];
  631.         as_size[state_no] += red.size;
  632.         for (i = 1; i <= red.size; i++)
  633.         {
  634.             if (table_opt == OPTIMIZE_TIME)
  635.                 symbol = original[REDUCE_SYMBOL(red, i)];
  636.             else
  637.                 symbol = REDUCE_SYMBOL(red, i);
  638.             SET_BIT_IN(action_symbols, state_no, symbol);
  639.         }
  640.     }
  641.  
  642.     partset(action_symbols, as_size, state_list, state_start,
  643.             state_stack, num_terminals);
  644.  
  645.     ffree(action_symbols);
  646.  
  647.     /*********************************************************************/
  648.     /* We now write the starting location for each state in the domain   */
  649.     /* of the ACTION_SYMBOL map.                                         */
  650.     /* The starting locations are contained in the STATE_START vector.   */
  651.     /*********************************************************************/
  652.     offset = state_start[num_states + 1];
  653.     k = 0;
  654.     for ALL_STATES(i)
  655.     {
  656.         field(ABS(state_start[state_list[i]]), 6);
  657.         k++;
  658.         if (k == 12)
  659.         {
  660.             *output_ptr++ = '\n';
  661.             BUFFER_CHECK(systab);
  662.             k = 0;
  663.         }
  664.     }
  665.     field(offset, 6);
  666.     k++;
  667.     *output_ptr++ = '\n';
  668.     BUFFER_CHECK(systab);
  669.  
  670.     /**************************************************************/
  671.     /* Compute and write out the range of the ACTION_SYMBOLS map. */
  672.     /**************************************************************/
  673.     action_symbols_range = Allocate_short_array(offset);
  674.  
  675.     compute_action_symbols_range(state_start, state_stack,
  676.                                  state_list, action_symbols_range);
  677.  
  678.     k = 0;
  679.     for (i = 0; i < (offset - 1); i++)
  680.     {
  681.         field(action_symbols_range[i], 4);
  682.         k++;
  683.         if (k == 18)
  684.         {
  685.             *output_ptr++ = '\n';
  686.             BUFFER_CHECK(systab);
  687.             k = 0;
  688.         }
  689.     }
  690.     if (k != 0)
  691.     {
  692.         *output_ptr++ = '\n';
  693.         BUFFER_CHECK(systab);
  694.     }
  695.  
  696.     /*************************************************************/
  697.     /* Compute and list space required for ACTION_SYMBOLS map.   */
  698.     /*************************************************************/
  699.     num_bytes = 2 * (num_states + offset);
  700.     if (byte_bit)
  701.     {
  702.         if (offset <= 255)
  703.             num_bytes -= (num_states + 1);
  704.         if (((table_opt == OPTIMIZE_TIME) && (last_terminal <= 255)) ||
  705.             ((table_opt != OPTIMIZE_TIME) && (num_terminals <= 255)))
  706.             num_bytes -= (offset - 1);
  707.     }
  708.     sprintf(msg_line,
  709.             "    Storage required for ACTION_SYMBOLS map: "
  710.             "%ld Bytes", num_bytes);
  711.     PRNT(msg_line);
  712.  
  713.     ffree(action_symbols_range);
  714.  
  715. /***********************************************************************/
  716. /* We now repeat the same process for the domain of the GOTO table.    */
  717. /***********************************************************************/
  718.     for ALL_STATES(state_no)
  719.     {
  720.         as_size[state_no] = gd_index[state_no + 1] - gd_index[state_no];
  721.         for (i = gd_index[state_no]; i < gd_index[state_no + 1]; i++)
  722.         {
  723.             symbol = gd_range[i] - num_terminals;
  724.             NTSET_BIT_IN(naction_symbols, state_no, symbol);
  725.         }
  726.     }
  727.  
  728.     partset(naction_symbols, as_size, state_list, state_start,
  729.             state_stack, num_non_terminals);
  730.  
  731.     ffree(as_size);
  732.     ffree(naction_symbols);
  733.  
  734.     for (i = 1; i <= gotodom_size; i++)  /* Remap non-terminals */
  735.     {
  736.         if (table_opt == OPTIMIZE_TIME)
  737.             gd_range[i] = symbol_map[gd_range[i]];
  738.         else
  739.             gd_range[i] = symbol_map[gd_range[i]] - num_terminals;
  740.     }
  741.  
  742.     /*****************************************************************/
  743.     /* We now write the starting location for each state in the      */
  744.     /* domain of the NACTION_SYMBOLS map. The starting locations are */
  745.     /* contained in the STATE_START vector.                          */
  746.     /*****************************************************************/
  747.     offset = state_start[num_states + 1];
  748.  
  749.     k = 0;
  750.     for ALL_STATES(i)
  751.     {
  752.         field(ABS(state_start[state_list[i]]), 6);
  753.         k++;
  754.         if (k == 12)
  755.         {
  756.             *output_ptr++ = '\n';
  757.             BUFFER_CHECK(systab);
  758.             k = 0;
  759.         }
  760.     }
  761.     field(offset, 6);
  762.     k++;
  763.     *output_ptr++ = '\n';
  764.     BUFFER_CHECK(systab);
  765.  
  766.     /**************************************************************/
  767.     /* Compute and write out the range of the NACTION_SYMBOLS map.*/
  768.     /**************************************************************/
  769.     naction_symbols_range = Allocate_short_array(offset);
  770.  
  771.     compute_naction_symbols_range(state_start, state_stack,
  772.                                   state_list, naction_symbols_range);
  773.  
  774.     k = 0;
  775.     for (i = 0; i < (offset - 1); i++)
  776.     {
  777.         field(naction_symbols_range[i], 4);
  778.         k++;
  779.         if (k == 18)
  780.         {
  781.             *output_ptr++ = '\n';
  782.             BUFFER_CHECK(systab);
  783.             k = 0;
  784.         }
  785.     }
  786.     if (k != 0)
  787.     {
  788.         *output_ptr++ = '\n';
  789.         BUFFER_CHECK(systab);
  790.     }
  791.  
  792.     /*************************************************************/
  793.     /* Compute and list space required for NACTION_SYMBOLS map.  */
  794.     /*************************************************************/
  795.     num_bytes = 2 * (num_states + offset);
  796.     if (byte_bit)
  797.     {
  798.         if (offset <= 255)
  799.             num_bytes -= (num_states + 1);
  800.         if (((table_opt == OPTIMIZE_TIME) && (last_non_terminal <= 255)) ||
  801.             ((table_opt != OPTIMIZE_TIME) && (num_non_terminals <= 255)))
  802.             num_bytes -= (offset - 1);
  803.     }
  804.     sprintf(msg_line,
  805.             "    Storage required for NACTION_SYMBOLS map: "
  806.             "%ld Bytes", num_bytes);
  807.     PRNT(msg_line);
  808.  
  809.     ffree(naction_symbols_range);
  810.  
  811.     /***********************************************************************/
  812.     /* Compute map from each symbol to state into which that symbol can    */
  813.     /* cause a transition: TRANSITION_STATES                               */
  814.     /* TRANSITION_STATES is also written as two vectors like the FOLLOW    */
  815.     /* map and the ACTION_DOMAIN map.                                      */
  816.     /* The first vector contains the starting location in the second       */
  817.     /* vector for each symbol.                                             */
  818.     /*   Construct the TRANSITION_STATES map using an array SYMBOL_ROOT    */
  819.     /* (indexable by each symbol) whose elements are the root of a linked  */
  820.     /* stack built in STATE_STACK. Another array SYMBOL_COUNT is used to   */
  821.     /* keep count of the number of states associated with each symbol.     */
  822.     /* For space tables, the TRANSITION_STATES map is written as two       */
  823.     /* separate tables: SHIFT_STATES and GOTO_STATES.                      */
  824.     /***********************************************************************/
  825.     for ALL_SYMBOLS(symbol)
  826.     {
  827.         symbol_root[symbol] = NIL;
  828.         symbol_count[symbol] = 0;
  829.     }
  830.  
  831.     for (state_no = 2; state_no <= (int) num_states; state_no++)
  832.     {
  833.         struct node *q;
  834.  
  835.         q = statset[state_no].kernel_items;
  836.         if (q == NULL) /* is the state a single production state? */
  837.         {
  838.             q = statset[state_no].complete_items; /* pick arbitrary item */
  839.         }
  840.  
  841.         item_no = q -> value - 1;
  842.         i = item_table[item_no].symbol;
  843.         symbol = symbol_map[i];
  844.         state_stack[state_no] = symbol_root[symbol];
  845.         symbol_root[symbol] = state_no;
  846.         symbol_count[symbol]++;
  847.     }
  848.  
  849.   /***************************************************************************/
  850.   /* We now compute and write the starting location for each terminal symbol */
  851.   /***************************************************************************/
  852.     offset = 1;     /* Offset of the first state */
  853.     field(offset, 6);
  854.     k = 1;
  855.     for (symbol = 1; symbol <= terminal_ubound; symbol++)
  856.     {
  857.         offset += symbol_count[symbol];
  858.         field(offset, 6);
  859.         k++;
  860.         if (k == 12)
  861.         {
  862.             *output_ptr++ = '\n';
  863.             BUFFER_CHECK(systab);
  864.             k = 0;
  865.         }
  866.     }
  867.     if (k != 0)
  868.     {
  869.         *output_ptr++ = '\n';
  870.         BUFFER_CHECK(systab);
  871.     }
  872.  
  873.     /*********************************************************************/
  874.     /* We now write out the range elements of SHIFT_STATES for space     */
  875.     /* tables or TRANSITION_STATES for time tables.                      */
  876.     /*********************************************************************/
  877.     k = 0;
  878.     for (symbol = 1; symbol <= terminal_ubound; symbol++)
  879.     {
  880.         for (state_no = symbol_root[symbol];
  881.              state_no != NIL; state_no = state_stack[state_no])
  882.         {
  883.             field(state_index[state_no] + num_rules, 6);
  884.             k++;
  885.             if (k == 12)
  886.             {
  887.                 *output_ptr++ = '\n';
  888.                 BUFFER_CHECK(systab);
  889.                 k = 0;
  890.             }
  891.         }
  892.     }
  893.     if (k != 0)
  894.     {
  895.         *output_ptr++ = '\n';
  896.         BUFFER_CHECK(systab);
  897.     }
  898.  
  899.     /*********************************************************************/
  900.     /* If space tables are requested we compute and list space required  */
  901.     /* for SHIFT_STATES map. The base vector contains NUM_TERMINALS+ 1   */
  902.     /* elements,  and the vector containing the range elements has size  */
  903.     /* OFFSET - 1. If time tables are requested we compute and list space*/
  904.     /* requirements for TRANSITION_STATES map.  The base vector has      */
  905.     /* NUM_SYMBOLS + 1 elements, and the range elements vector contains  */
  906.     /* OFFSET - 1 elements.                                              */
  907.     /*********************************************************************/
  908.     if (table_opt == OPTIMIZE_TIME)
  909.     {
  910.         num_bytes = 2 * (num_symbols + offset);
  911.         sprintf(msg_line,
  912.                 "    Storage required for TRANSITION_STATES map: %d Bytes",
  913.                 num_bytes);
  914.         PRNT(msg_line);
  915.     }
  916.     else
  917.     {
  918.         num_bytes = 2 * (num_terminals + offset);
  919.         sprintf(msg_line,
  920.                 "    Storage required for SHIFT_STATES map: %d Bytes",
  921.                 num_bytes);
  922.         PRNT(msg_line);
  923.  
  924.         /************************************************************/
  925.         /* We now compute and write the starting location for each  */
  926.         /* non-terminal symbol...                                   */
  927.         /************************************************************/
  928.         offset = 1;
  929.         field(offset, 6);     /* Offset of the first state */
  930.         k = 1;
  931.         for ALL_NON_TERMINALS(symbol)
  932.         {
  933.             offset += symbol_count[symbol];
  934.             field(offset, 6);
  935.             k++;
  936.             if (k == 12)
  937.             {
  938.                 *output_ptr++ = '\n';
  939.                 BUFFER_CHECK(systab);
  940.                 k = 0;
  941.             }
  942.         }
  943.         if (k != 0)
  944.         {
  945.             *output_ptr++ = '\n';
  946.             BUFFER_CHECK(systab);
  947.         }
  948.  
  949.      /*********************************************************************/
  950.      /* We now write out the range elements of GOTO_STATES whose domain   */
  951.      /* is a non-terminal symbol.                                         */
  952.      /*********************************************************************/
  953.         k = 0;
  954.         for ALL_NON_TERMINALS(symbol)
  955.         {
  956.             for (state_no = symbol_root[symbol];
  957.                  state_no != NIL; state_no = state_stack[state_no])
  958.             {
  959.                 field(state_index[state_no] + num_rules, 6);
  960.                 k++;
  961.                 if (k == 12)
  962.                 {
  963.                     *output_ptr++ = '\n';
  964.                     BUFFER_CHECK(systab);
  965.                     k = 0;
  966.                 }
  967.             }
  968.         }
  969.         if (k != 0)
  970.         {
  971.             *output_ptr++ = '\n';
  972.             BUFFER_CHECK(systab);
  973.         }
  974.  
  975.        /*********************************************************************/
  976.        /* We compute and list space required for GOTO_STATES map. The       */
  977.        /* base vector contains NUM_NON_TERMINALS+ 1 elements, and the vector*/
  978.        /* containing the range elements has size OFFSET - 1                 */
  979.        /*********************************************************************/
  980.        num_bytes = 2 * (num_non_terminals + offset);
  981.        sprintf(msg_line,"    Storage required for GOTO_STATES map: %d Bytes",
  982.                num_bytes);
  983.        PRNT(msg_line);
  984.     }
  985.  
  986.     /*********************************************************************/
  987.     /* Write the number associated with the ERROR symbol.                */
  988.     /*********************************************************************/
  989.  
  990.     field(error_image, 4);
  991.     field(eolt_image, 4);
  992.     field(num_names, 4);
  993.     field(num_scopes, 4);
  994.     field(scope_rhs_size, 4);
  995.     field(scope_state_size, 4);
  996.     if (table_opt == OPTIMIZE_SPACE)
  997.         field(num_error_rules, 4);
  998.     *output_ptr++ = '\n';
  999.     BUFFER_CHECK(systab);
  1000.  
  1001.     /*********************************************************************/
  1002.     /* We write out the names map.                                       */
  1003.     /*********************************************************************/
  1004.     num_bytes = 0;
  1005.     max_len = 0;
  1006.     for (i = 1; i <= num_names; i++)
  1007.     {
  1008.         int name_len;
  1009.  
  1010.         strcpy(tok, RETRIEVE_NAME(i));
  1011.         if (tok[0] == '\n')  /* we're dealing with special symbol?  */
  1012.             tok[0] = escape; /* replace initial marker with escape. */
  1013.         name_len = strlen(tok);
  1014.         num_bytes += name_len;
  1015.         if (max_len < name_len)
  1016.             max_len = name_len;
  1017.  
  1018.         field(name_len, 4);
  1019.  
  1020.         if (name_len <= 68)
  1021.             strcpy(output_ptr, tok);
  1022.         else
  1023.         {
  1024.             memcpy(output_ptr, tok, 68);
  1025.             output_ptr+= 68;
  1026.             *output_ptr++ = '\n';
  1027.             BUFFER_CHECK(systab);;
  1028.             strcpy(tok, tok+68);
  1029.  
  1030.             for (name_len = strlen(tok); name_len > 72; name_len = strlen(tok))
  1031.             {
  1032.                 memcpy(output_ptr, tok, 72);
  1033.                 output_ptr+= 72;
  1034.                 *output_ptr++ = '\n';
  1035.                 BUFFER_CHECK(systab);
  1036.                 strcpy(tok, tok+72);
  1037.             }
  1038.             memcpy(output_ptr, tok, name_len);
  1039.         }
  1040.         output_ptr += name_len;
  1041.         *output_ptr++ = '\n';
  1042.         BUFFER_CHECK(systab);
  1043.     }
  1044.  
  1045.     /*********************************************************************/
  1046.     /* We write the name_index of each terminal symbol.  The array TEMP  */
  1047.     /* is used to remap the NAME_INDEX values based on the new symbol    */
  1048.     /* numberings. If time tables are requested, the terminals and non-  */
  1049.     /* terminals are mixed together.                                     */
  1050.     /*********************************************************************/
  1051.     temp = Allocate_short_array(num_symbols + 1);
  1052.  
  1053.     if (table_opt == OPTIMIZE_TIME)
  1054.     {
  1055.         for ALL_SYMBOLS(symbol)
  1056.             temp[symbol_map[symbol]] = symno[symbol].name_index;
  1057.  
  1058.         k = 0;
  1059.         for ALL_SYMBOLS(symbol)
  1060.         {
  1061.             field(temp[symbol], 4);
  1062.             k++;
  1063.             if (k == 18)
  1064.             {
  1065.                 *output_ptr++ = '\n';
  1066.                 BUFFER_CHECK(systab);
  1067.                 k = 0;
  1068.             }
  1069.         }
  1070.  
  1071.         if (k != 0)
  1072.         {
  1073.             *output_ptr++ = '\n';
  1074.             BUFFER_CHECK(systab);
  1075.         }
  1076.     }
  1077.     else
  1078.     {
  1079.         for ALL_TERMINALS(symbol)
  1080.             temp[symbol_map[symbol]] = symno[symbol].name_index;
  1081.  
  1082.         k = 0;
  1083.         for ALL_TERMINALS(symbol)
  1084.         {
  1085.             field(temp[symbol], 4);
  1086.             k++;
  1087.             if (k == 18)
  1088.             {
  1089.                 *output_ptr++ = '\n';
  1090.                 BUFFER_CHECK(systab);
  1091.                 k = 0;
  1092.             }
  1093.         }
  1094.  
  1095.         if (k != 0)
  1096.         {
  1097.             *output_ptr++ = '\n';
  1098.             BUFFER_CHECK(systab);
  1099.         }
  1100.  
  1101.        /****************************************************************/
  1102.        /* We write the name_index of each non_terminal symbol. The     */
  1103.        /* array TEMP is used to remap the NAME_INDEX values based on   */
  1104.        /* the new symbol numberings.                                   */
  1105.        /****************************************************************/
  1106.         for ALL_NON_TERMINALS(symbol)
  1107.             temp[symbol_map[symbol]] = symno[symbol].name_index;
  1108.  
  1109.         k = 0;
  1110.         for ALL_NON_TERMINALS(symbol)
  1111.         {
  1112.             field(temp[symbol], 4);
  1113.             k++;
  1114.             if (k == 18)
  1115.             {
  1116.                 *output_ptr++ = '\n';
  1117.                 BUFFER_CHECK(systab);
  1118.                 k = 0;
  1119.             }
  1120.         }
  1121.  
  1122.         if (k != 0)
  1123.         {
  1124.             *output_ptr++ = '\n';
  1125.             BUFFER_CHECK(systab);
  1126.         }
  1127.     }
  1128.  
  1129.     /*****************************************************/
  1130.     /* Compute and list space requirements for NAME map. */
  1131.     /*****************************************************/
  1132.     if (max_len > 255)
  1133.         offset = 2 * num_symbols;
  1134.     else
  1135.         offset = num_symbols;
  1136.  
  1137.     if (num_bytes > 255)
  1138.         offset += (2 * num_symbols);
  1139.     else
  1140.         offset += num_symbols;
  1141.  
  1142.     sprintf(msg_line,
  1143.             "    Storage required for direct NAME map: %d Bytes",
  1144.             num_bytes + offset);
  1145.     PRNT(msg_line);
  1146.  
  1147.     if (max_len > 255)
  1148.         offset = 2 * num_names;
  1149.     else
  1150.         offset = num_names;
  1151.  
  1152.     if (num_bytes > 255)
  1153.         offset += (2 * num_names);
  1154.     else
  1155.         offset += num_names;
  1156.  
  1157.     if (num_names > 255)
  1158.         offset += (2 * num_symbols);
  1159.     else
  1160.         offset += num_symbols;
  1161.  
  1162.     sprintf(msg_line,
  1163.             "    Storage required for indirect NAME map: %d Bytes",
  1164.             num_bytes + offset);
  1165.     PRNT(msg_line);
  1166.  
  1167.     if (scopes_bit)
  1168.     {
  1169.         for (i = 1; i <= scope_rhs_size; i++)
  1170.         {
  1171.             if (scope_right_side[i] != 0)
  1172.                 scope_right_side[i] = symbol_map[scope_right_side[i]];
  1173.         }
  1174.  
  1175.         for (i = 1; i <= num_scopes; i++)
  1176.         {
  1177.             scope[i].look_ahead = symbol_map[scope[i].look_ahead];
  1178.             if (table_opt == OPTIMIZE_TIME)
  1179.                 scope[i].lhs_symbol = symbol_map[scope[i].lhs_symbol];
  1180.             else
  1181.                 scope[i].lhs_symbol = symbol_map[scope[i].lhs_symbol]
  1182.                                       - num_terminals;
  1183.         }
  1184.  
  1185.         k = 0;
  1186.         for (i = 1; i <= num_scopes; i++)
  1187.         {
  1188.             field(scope[i].prefix, 4);
  1189.             k++;
  1190.             if (k == 18)
  1191.             {
  1192.                 *output_ptr++ = '\n';
  1193.                 BUFFER_CHECK(systab);
  1194.                 k = 0;
  1195.             }
  1196.         }
  1197.  
  1198.         if (k != 0)
  1199.         {
  1200.             *output_ptr++ = '\n';
  1201.             BUFFER_CHECK(systab);
  1202.         }
  1203.  
  1204.         k = 0;
  1205.         for (i = 1; i <= num_scopes; i++)
  1206.         {
  1207.             field(scope[i].suffix, 4);
  1208.             k++;
  1209.             if (k == 18)
  1210.             {
  1211.                 *output_ptr++ = '\n';
  1212.                 BUFFER_CHECK(systab);
  1213.                 k = 0;
  1214.             }
  1215.         }
  1216.  
  1217.         if (k != 0)
  1218.         {
  1219.             *output_ptr++ = '\n';
  1220.             BUFFER_CHECK(systab);
  1221.         }
  1222.  
  1223.         k = 0;
  1224.         for (i = 1; i <= num_scopes; i++)
  1225.         {
  1226.             field(scope[i].lhs_symbol, 4);
  1227.             k++;
  1228.             if (k == 18)
  1229.             {
  1230.                 *output_ptr++ = '\n';
  1231.                 BUFFER_CHECK(systab);
  1232.                 k = 0;
  1233.             }
  1234.         }
  1235.  
  1236.         if (k != 0)
  1237.         {
  1238.             *output_ptr++ = '\n';
  1239.             BUFFER_CHECK(systab);
  1240.         }
  1241.  
  1242.         k = 0;
  1243.         for (i = 1; i <= num_scopes; i++)
  1244.         {
  1245.             field(scope[i].look_ahead, 4);
  1246.             k++;
  1247.             if (k == 18)
  1248.             {
  1249.                 *output_ptr++ = '\n';
  1250.                 BUFFER_CHECK(systab);
  1251.                 k = 0;
  1252.             }
  1253.         }
  1254.  
  1255.         if (k != 0)
  1256.         {
  1257.             *output_ptr++ = '\n';
  1258.             BUFFER_CHECK(systab);
  1259.         }
  1260.  
  1261.         k = 0;
  1262.         for (i = 1; i <= num_scopes; i++)
  1263.         {
  1264.             field(scope[i].state_set, 4);
  1265.             k++;
  1266.             if (k == 18)
  1267.             {
  1268.                 *output_ptr++ = '\n';
  1269.                 BUFFER_CHECK(systab);
  1270.                 k = 0;
  1271.             }
  1272.         }
  1273.  
  1274.         if (k != 0)
  1275.         {
  1276.             *output_ptr++ = '\n';
  1277.             BUFFER_CHECK(systab);
  1278.         }
  1279.  
  1280.         k = 0;
  1281.         for (i = 1; i <= scope_rhs_size; i++)
  1282.         {
  1283.             field(scope_right_side[i], 4);
  1284.             k++;
  1285.             if (k == 18)
  1286.             {
  1287.                 *output_ptr++ = '\n';
  1288.                 BUFFER_CHECK(systab);
  1289.                 k = 0;
  1290.             }
  1291.         }
  1292.  
  1293.         if (k != 0)
  1294.         {
  1295.             *output_ptr++ = '\n';
  1296.             BUFFER_CHECK(systab);
  1297.         }
  1298.  
  1299.         k = 0;
  1300.         for (i = 1; i <= scope_state_size; i++)
  1301.         {
  1302.             if (scope_state[i] == 0)
  1303.                 field(0, 6);
  1304.             else
  1305.                 field(state_index[scope_state[i]] + num_rules, 6);
  1306.             k++;
  1307.             if (k == 12)
  1308.             {
  1309.                 *output_ptr++ = '\n';
  1310.                 BUFFER_CHECK(systab);
  1311.                 k = 0;
  1312.             }
  1313.         }
  1314.  
  1315.         if (k != 0)
  1316.         {
  1317.             *output_ptr++ = '\n';
  1318.             BUFFER_CHECK(systab);
  1319.         }
  1320.  
  1321.         if (table_opt == OPTIMIZE_TIME)
  1322.         {
  1323.             num_bytes = 5 * num_scopes +
  1324.                         scope_rhs_size+ scope_state_size;
  1325.             if (num_symbols > 255)
  1326.                 num_bytes += (2 * num_scopes + scope_rhs_size);
  1327.         }
  1328.         else
  1329.         {
  1330.             num_bytes = 5 * num_scopes +
  1331.                         scope_rhs_size+ 2 * scope_state_size;
  1332.             if (num_non_terminals > 255)
  1333.                 num_bytes += num_scopes;
  1334.             if (num_terminals > 255)
  1335.                 num_bytes += num_scopes;
  1336.             if (num_symbols > 255)
  1337.                 num_bytes += scope_rhs_size;
  1338.         }
  1339.         if (scope_rhs_size > 255)
  1340.             num_bytes += (2 * num_scopes);
  1341.         if (scope_state_size > 255)
  1342.             num_bytes += num_scopes;
  1343.         sprintf(msg_line,
  1344.                 "    Storage required for SCOPE map: %d Bytes",
  1345.                 num_bytes);
  1346.         PRNT(msg_line);
  1347.     }
  1348.  
  1349.     if (original != NULL)
  1350.     {
  1351.         ffree(original);
  1352.     }
  1353.     ffree(symbol_root);
  1354.     ffree(symbol_count);
  1355.     ffree(temp);
  1356.     ffree(state_start);
  1357.     ffree(state_stack);
  1358.     ffree(term_list);
  1359.  
  1360.     return;
  1361. }
  1362.  
  1363.  
  1364. /*********************************************************************/
  1365. /*                   COMPUTE_ACTION_SYMBOLS_RANGE:                   */
  1366. /*********************************************************************/
  1367. /*                                                                   */
  1368. /* This procedure computes the range of the ACTION_SYMBOLS map after */
  1369. /* Optimal Partitioning has been used to compress that map.  Its     */
  1370. /* first argument is an array, STATE_START, that indicates the       */
  1371. /* starting location in the compressed vector for each state.  When  */
  1372. /* a value of STATE_START is negative it indicates that the state in */
  1373. /* question shares its elements with another state.  Its second      */
  1374. /* argument, STATE_STACK, is an array that contains the elements of  */
  1375. /* the partition created by PARTSET.  Each element of the partition  */
  1376. /* is organized as a circular list where the smallest sets appear    */
  1377. /* first in the list.                                                */
  1378. /*                                                                   */
  1379. /*********************************************************************/
  1380. void compute_action_symbols_range(short *state_start,
  1381.                                   short *state_stack,
  1382.                                   short *state_list,
  1383.                                   short *action_symbols_range)
  1384. {
  1385.     int i,
  1386.         j,
  1387.         k,
  1388.         state_no,
  1389.         state,
  1390.         symbol,
  1391.         symbol_root;
  1392.  
  1393.     BOOLEAN end_node;
  1394.  
  1395.     short *symbol_list;
  1396.  
  1397.     symbol_list = Allocate_short_array(num_symbols + 1);
  1398.  
  1399.     /*********************************************************************/
  1400.     /* We now write out the range elements of the ACTION_SYMBOLS map.    */
  1401.     /* Recall that if STATE_START has a negative value, then the set in  */
  1402.     /* question is sharing elements and does not need to be processed.   */
  1403.     /*********************************************************************/
  1404.     k = 0;
  1405.     for ALL_SYMBOLS(j)
  1406.         symbol_list[j] = OMEGA;     /* Initialize all links to OMEGA */
  1407.  
  1408.     for ALL_STATES(i)
  1409.     {
  1410.         state_no = state_list[i];
  1411.         if (state_start[state_no] > 0)
  1412.         {
  1413.             symbol_root = 0;       /* Add "fence" element: 0 to list */
  1414.             symbol_list[symbol_root] = NIL;
  1415.  
  1416.             /*************************************************************/
  1417.             /* Pop a state from the stack,  and add each of its elements */
  1418.             /* that has not yet been processed into the list.            */
  1419.             /* Continue until stack is empty...                          */
  1420.             /* Recall that the stack is represented by a circular queue. */
  1421.             /*************************************************************/
  1422.             for (end_node = ((state = state_no) == NIL);
  1423.                  ! end_node; end_node = (state == state_no))
  1424.             {
  1425.                 struct shift_header_type  sh;
  1426.                 struct reduce_header_type red;
  1427.  
  1428.                 state = state_stack[state];
  1429.                 sh = shift[statset[state].shift_number];
  1430.                 for (j = 1; j <= sh.size; j++)
  1431.                 {
  1432.                     symbol = SHIFT_SYMBOL(sh, j);
  1433.                     if (symbol_list[symbol] == OMEGA)
  1434.                     {
  1435.                         symbol_list[symbol] = symbol_root;
  1436.                         symbol_root = symbol;
  1437.                     }
  1438.                 }
  1439.  
  1440.                 red = reduce[state];
  1441.                 for (j = 1; j <= red.size; j++)
  1442.                 {
  1443.                     symbol = REDUCE_SYMBOL(red, j);
  1444.                     if (symbol_list[symbol] == OMEGA)
  1445.                     {
  1446.                         symbol_list[symbol] = symbol_root;
  1447.                         symbol_root = symbol;
  1448.                     }
  1449.                 }
  1450.             }
  1451.  
  1452.             /*************************************************************/
  1453.             /* Write the list out.                                       */
  1454.             /*************************************************************/
  1455.             for (symbol = symbol_root; symbol != NIL; symbol = symbol_root)
  1456.             {
  1457.                 symbol_root = symbol_list[symbol];
  1458.  
  1459.                 symbol_list[symbol] = OMEGA;
  1460.                 action_symbols_range[k++] = symbol;
  1461.             }
  1462.         }
  1463.     }
  1464.  
  1465.     ffree(symbol_list);
  1466.  
  1467.     return;
  1468. }
  1469.  
  1470.  
  1471. /*********************************************************************/
  1472. /*                   COMPUTE_NACTION_SYMBOLS_RANGE:                  */
  1473. /*********************************************************************/
  1474. /* This procedure computes the range of the NACTION_SYMBOLS map. It  */
  1475. /* organization is analoguous to COMPUTE_ACTION_SYMBOLS_RANGE.       */
  1476. /*********************************************************************/
  1477. void compute_naction_symbols_range(short *state_start,
  1478.                                    short *state_stack,
  1479.                                    short *state_list,
  1480.                                    short *naction_symbols_range)
  1481. {
  1482.     int i,
  1483.         j,
  1484.         k,
  1485.         state_no,
  1486.         state,
  1487.         symbol,
  1488.         symbol_root;
  1489.  
  1490.     BOOLEAN end_node;
  1491.  
  1492.     short *symbol_list;
  1493.  
  1494.     symbol_list = Allocate_short_array(num_symbols + 1);
  1495.  
  1496.     /*********************************************************************/
  1497.     /* We now write out the range elements of the NACTION_SYMBOLS map.   */
  1498.     /* Recall that if STATE_START has a negative value, then the set in  */
  1499.     /* question is sharing elements and does not need to be processed.   */
  1500.     /*********************************************************************/
  1501.     k = 0;
  1502.     for ALL_SYMBOLS(j)
  1503.         symbol_list[j] = OMEGA;     /* Initialize all links to OMEGA */
  1504.  
  1505.     for ALL_STATES(i)
  1506.     {
  1507.         state_no = state_list[i];
  1508.         if (state_start[state_no] > 0)
  1509.         {
  1510.             symbol_root = 0;       /* Add "fence" element: 0 to list */
  1511.             symbol_list[symbol_root] = NIL;
  1512.  
  1513.            /*************************************************************/
  1514.            /* Pop a state from the stack,  and add each of its elements */
  1515.            /* that has not yet been processed into the list.            */
  1516.            /* Continue until stack is empty...                          */
  1517.            /* Recall that the stack is represented by a circular queue. */
  1518.            /*************************************************************/
  1519.             for (end_node =  ((state = state_no) == NIL);
  1520.                  ! end_node; end_node = (state == state_no))
  1521.             {
  1522.                 state = state_stack[state];
  1523.                 for (j = gd_index[state];
  1524.                      j <= gd_index[state + 1] - 1; j++)
  1525.                 {
  1526.                     symbol = gd_range[j];
  1527.                     if (symbol_list[symbol] == OMEGA)
  1528.                     {
  1529.                         symbol_list[symbol] = symbol_root;
  1530.                         symbol_root = symbol;
  1531.                     }
  1532.                 }
  1533.             }
  1534.  
  1535.             /**********************************************************/
  1536.             /* Write the list out.                                    */
  1537.             /**********************************************************/
  1538.             for (symbol = symbol_root; symbol != NIL; symbol = symbol_root)
  1539.             {
  1540.                 symbol_root = symbol_list[symbol];
  1541.  
  1542.                 symbol_list[symbol] = OMEGA;
  1543.                 naction_symbols_range[k++] = symbol;
  1544.             }
  1545.         }
  1546.     }
  1547.  
  1548.     ffree(symbol_list);
  1549.  
  1550.     return;
  1551. }
  1552.