home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / jikepg12.zip / jikespg / src / spacetab.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-11-04  |  80.0 KB  |  2,274 lines
  1. /* $Id: spacetab.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 "space.h"
  15. #include "header.h"
  16.  
  17. static struct node **new_state_element_reduce_nodes;
  18.  
  19. static long total_bytes,
  20.             num_table_entries;
  21.  
  22. static int top,
  23.            empty_root,
  24.            single_root,
  25.            multi_root;
  26.  
  27. static short *row_size,
  28.              *frequency_symbol,
  29.              *frequency_count;
  30.  
  31. static BOOLEAN *shift_on_error_symbol;
  32.  
  33. /****************************************************************************/
  34. /*                            REMAP_NON_TERMINALS:                          */
  35. /****************************************************************************/
  36. /*  REMAP_NON_TERMINALS remaps the non-terminal symbols and states based on */
  37. /* frequency of entries.                                                    */
  38. /****************************************************************************/
  39. static void remap_non_terminals(void)
  40. {
  41.     short *frequency_symbol,
  42.           *frequency_count,
  43.           *row_size;
  44.  
  45.     struct goto_header_type go_to;
  46.  
  47.     int i,
  48.         state_no,
  49.         symbol;
  50.  
  51. /**********************************************************************/
  52. /*   The variable FREQUENCY_SYMBOL is used to hold the non-terminals  */
  53. /* in the grammar, and  FREQUENCY_COUNT is used correspondingly to    */
  54. /* hold the number of actions defined on each non-terminal.           */
  55. /* ORDERED_STATE and ROW_SIZE are used in a similar fashion for states*/
  56. /**********************************************************************/
  57.     frequency_symbol = Allocate_short_array(num_non_terminals);
  58.     frequency_symbol -= (num_terminals + 1);
  59.     frequency_count = Allocate_short_array(num_non_terminals);
  60.     frequency_count -= (num_terminals + 1);
  61.     row_size = Allocate_short_array(num_states + 1);
  62.  
  63.     for ALL_NON_TERMINALS(i)
  64.     {
  65.         frequency_symbol[i] = i;
  66.         frequency_count[i] = 0;
  67.     }
  68.     for ALL_STATES(state_no)
  69.     {
  70.         ordered_state[state_no] = state_no;
  71.         row_size[state_no] = 0;
  72.         go_to = statset[state_no].go_to;
  73.         for (i = 1; i <= go_to.size; i++)
  74.         {
  75.             row_size[state_no]++;
  76.             symbol = GOTO_SYMBOL(go_to, i);
  77.             frequency_count[symbol]++;
  78.         }
  79.     }
  80.  
  81.     /**********************************************************************/
  82.     /* The non-terminals are sorted in descending order based on the      */
  83.     /* number of actions defined on then, and they are remapped based on  */
  84.     /* the new arrangement obtained by the sorting.                       */
  85.     /**********************************************************************/
  86.     sortdes(frequency_symbol, frequency_count,
  87.             num_terminals + 1, num_symbols, num_states);
  88.  
  89.     for ALL_NON_TERMINALS(i)
  90.         symbol_map[frequency_symbol[i]] = i;
  91.  
  92.     /**********************************************************************/
  93.     /*    All non-terminal entries in the state automaton are updated     */
  94.     /* accordingly.  We further subtract NUM_TERMINALS from each          */
  95.     /* non-terminal to make them fall in the range [1..NUM_NON_TERMINLS]  */
  96.     /* instead of [NUM_TERMINALS+1..NUM_SYMBOLS].                         */
  97.     /**********************************************************************/
  98.     for ALL_STATES(state_no)
  99.     {
  100.         go_to = statset[state_no].go_to;
  101.         for (i = 1; i <= go_to.size; i++)
  102.            GOTO_SYMBOL(go_to, i) =
  103.                 symbol_map[GOTO_SYMBOL(go_to, i)] - num_terminals;
  104.     }
  105.  
  106.     /**********************************************************************/
  107.     /* If Goto-Default was requested, we find out how many non-terminals  */
  108.     /* were eliminated as a result, and adjust the GOTO-DEFAULT map,      */
  109.     /* based on the new mapping of the non-terminals.                     */
  110.     /**********************************************************************/
  111.     if (goto_default_bit)
  112.     {
  113.         short *temp_goto_default;
  114.  
  115.         temp_goto_default = Allocate_short_array(num_non_terminals);
  116.         temp_goto_default -= (num_terminals + 1);
  117.  
  118.         for (last_symbol = num_symbols;
  119.              last_symbol > num_terminals; last_symbol--)
  120.              if (frequency_count[last_symbol] != 0)
  121.                  break;
  122.         last_symbol -= num_terminals;
  123.         sprintf(msg_line, "Number of non-terminals eliminated: %d",
  124.                           num_non_terminals - last_symbol);
  125.         PRNT(msg_line);
  126.  
  127.         /**************************************************************/
  128.         /* Remap the GOTO-DEFAULT map.                                */
  129.         /* to hold the original map.                                  */
  130.         /**************************************************************/
  131.         for ALL_NON_TERMINALS(symbol)
  132.             temp_goto_default[symbol_map[symbol]] = gotodef[symbol];
  133.         gotodef += (num_terminals + 1);
  134.         ffree(gotodef);
  135.         gotodef = temp_goto_default;
  136.     }
  137.     else
  138.         last_symbol = num_non_terminals;
  139.  
  140.     /**********************************************************************/
  141.     /* The states are sorted in descending order based on the number of   */
  142.     /* actions defined on them, and they are remapped based on the new    */
  143.     /* arrangement obtained by the sorting.                               */
  144.     /**********************************************************************/
  145.     sortdes(ordered_state, row_size, 1, num_states, last_symbol);
  146.  
  147.     frequency_symbol += (num_terminals + 1);
  148.     ffree(frequency_symbol);
  149.     frequency_count += (num_terminals + 1);
  150.     ffree(frequency_count);
  151.     ffree(row_size);
  152.  
  153.     return;
  154. }
  155.  
  156.  
  157. /****************************************************************************/
  158. /*                           OVERLAP_NT_ROWS:                               */
  159. /****************************************************************************/
  160. /* We now overlap the non-terminal table, or more precisely, we compute the */
  161. /* starting position in a vector where each of its rows may be placed       */
  162. /* without clobbering elements in another row.  The starting positions are  */
  163. /* stored in the vector STATE_INDEX.                                        */
  164. /****************************************************************************/
  165. static void overlap_nt_rows(void)
  166. {
  167.     struct goto_header_type go_to;
  168.  
  169.     int max_indx,
  170.         indx,
  171.         k,
  172.         j,
  173.         i,
  174.         k_bytes,
  175.         percentage,
  176.         state_no,
  177.         symbol;
  178.  
  179.     long num_bytes;
  180.  
  181.     num_table_entries = num_gotos + num_goto_reduces + num_states;
  182.     increment_size = MAX((num_table_entries / 100 * increment),
  183.                          (last_symbol + 1));
  184.     table_size = MIN((num_table_entries + increment_size), MAX_TABLE_SIZE);
  185.  
  186.     /*************************************************************************/
  187.     /* Allocate space for table, and initlaize the AVAIL_POOL list.  The     */
  188.     /* variable FIRST_INDEX keeps track of the first element in the doubly-  */
  189.     /* linked list, and LAST_ELEMENT keeps track of the last element in the  */
  190.     /* list.                                                                 */
  191.     /*   The variable MAX_INDX is used to keep track of the maximum starting */
  192.     /* position for a row that has been used.                                */
  193.     /*************************************************************************/
  194.     next = Allocate_int_array(table_size + 1);
  195.     previous = Allocate_int_array(table_size + 1);
  196.  
  197.     first_index = 1;
  198.     previous[first_index] = NIL;
  199.     next[first_index] = first_index + 1;
  200.     for (indx = 2; indx < (int) table_size; indx++)
  201.     {
  202.         next[indx] = indx + 1;
  203.         previous[indx] = indx - 1;
  204.     }
  205.     last_index = table_size;
  206.     previous[last_index] = last_index - 1;
  207.     next[last_index] = NIL;
  208.  
  209.     max_indx = first_index;
  210.  
  211.     /*******************************************************************/
  212.     /* We now iterate over all the states in their new sorted order as */
  213.     /* indicated by the variable STATE_NO, and determine an "overlap"  */
  214.     /* position for them.                                              */
  215.     /*******************************************************************/
  216.     for ALL_STATES(k)
  217.     {
  218.         state_no = ordered_state[k];
  219.  
  220.         /****************************************************************/
  221.         /* INDX is set to the beginning of the list of available slots  */
  222.         /* and we try to determine if it might be a valid starting      */
  223.         /* position.  If not, INDX is moved to the next element, and we */
  224.         /* repeat the process until a valid position is found.          */
  225.         /****************************************************************/
  226.         go_to = statset[state_no].go_to;
  227.         indx = first_index;
  228.  
  229. look_for_match_in_base_table:
  230.         if (indx == NIL)
  231.             indx = table_size + 1;
  232.         if (indx + last_symbol > table_size)
  233.             reallocate();
  234.         for (i = 1; i <= go_to.size; i++)
  235.         {
  236.             if (next[indx + GOTO_SYMBOL(go_to, i)] == OMEGA)
  237.             {
  238.                 indx = next[indx];
  239.                 goto look_for_match_in_base_table;
  240.             }
  241.         }
  242.  
  243.         /*****************************************************************/
  244.         /* At this stage, a position(INDX), was found to overlay the row */
  245.         /* in question.  Remove elements associated with all positions   */
  246.         /* that will be taken by row from the doubly-linked list.        */
  247.         /* NOTE tha since SYMBOLs start at 1, the first index can never  */
  248.         /* be a candidate (==> I = INDX + SYMBOL) in this loop.          */
  249.         /*****************************************************************/
  250.         for (j = 1; j <= go_to.size; j++)
  251.         {
  252.             symbol = GOTO_SYMBOL(go_to, j);
  253.             i = indx + symbol;
  254.             if (i == last_index)
  255.             {
  256.                 last_index = previous[last_index];
  257.                 next[last_index] = NIL;
  258.             }
  259.             else
  260.             {
  261.                 next[previous[i]] = next[i];
  262.                 previous[next[i]] = previous[i];
  263.             }
  264.             next[i] = OMEGA;
  265.         }
  266.  
  267.         if (first_index == last_index)
  268.             first_index = NIL;
  269.         else if (indx == first_index)
  270.         {
  271.             first_index = next[first_index];
  272.             previous[first_index] = NIL;
  273.         }
  274.         else if (indx == last_index)
  275.         {
  276.             last_index = previous[last_index];
  277.             next[last_index] = NIL;
  278.         }
  279.         else
  280.         {
  281.             next[previous[indx]] = next[indx];
  282.             previous[next[indx]] = previous[indx];
  283.         }
  284.         next[indx] = OMEGA;
  285.         if (indx > max_indx)
  286.             max_indx = indx;
  287.         state_index[state_no] =  indx;
  288.     }
  289.  
  290.     if (goto_default_bit || nt_check_bit)
  291.         check_size = max_indx + num_non_terminals;
  292.     else
  293.         check_size = 0;
  294.  
  295.     for (action_size = max_indx + last_symbol;
  296.          action_size >= max_indx; action_size--)
  297.         if (next[action_size] == OMEGA)
  298.             break;
  299.  
  300.     accept_act = max_indx + num_rules + 1;
  301.     error_act = accept_act + 1;
  302.  
  303.     printf("\n");
  304.     if (goto_default_bit || nt_check_bit)
  305.     {
  306.         sprintf(msg_line,"Length of base Check Table: %d", check_size);
  307.         PRNT(msg_line);
  308.     }
  309.  
  310.     sprintf(msg_line,"Length of base Action Table: %ld", action_size);
  311.     PRNT(msg_line);
  312.  
  313.     sprintf(msg_line,"Number of entries in base Action Table: %d",
  314.             num_table_entries);
  315.     PRNT(msg_line);
  316.  
  317.     percentage = ((action_size - num_table_entries) * 1000)
  318.                    / num_table_entries;
  319.     sprintf(msg_line, "Percentage of increase: %d.%d%%",
  320.                       percentage / 10, percentage % 10);
  321.     PRNT(msg_line);
  322.  
  323.     if (byte_bit)
  324.     {
  325.         num_bytes = 2 * action_size + check_size;
  326.         if (goto_default_bit || nt_check_bit)
  327.         {
  328.             if (last_symbol > 255)
  329.                 num_bytes += check_size;
  330.         }
  331.     }
  332.     else
  333.         num_bytes = 2 * (action_size + check_size);
  334.  
  335.     if (goto_default_bit)
  336.         num_bytes += ((long) 2 * num_non_terminals);
  337.     total_bytes = num_bytes;
  338.  
  339.     k_bytes = (num_bytes / 1024) + 1;
  340.  
  341.     sprintf(msg_line,"Storage required for base Tables: %ld Bytes, %dK",
  342.             num_bytes, k_bytes);
  343.     PRNT(msg_line);
  344.     num_bytes = (long) 4 * num_rules;
  345.     if (byte_bit)
  346.     {
  347.         num_bytes -= num_rules;
  348.         if (num_non_terminals < 256)
  349.             num_bytes -= num_rules;
  350.     }
  351.     sprintf(msg_line, "Storage required for Rules: %ld Bytes", num_bytes);
  352.     PRNT(msg_line);
  353.  
  354.     return;
  355. }
  356.  
  357.  
  358. /*********************************************************************/
  359. /*                        MERGE_SIMILAR_T_ROWS:                      */
  360. /*********************************************************************/
  361. /* We now try to merge states in the terminal table that are similar.*/
  362. /* Two states S1 and S2 are said to be similar if they contain the   */
  363. /* same shift actions and they reduce to the same set of rules.  In  */
  364. /* addition,  there must not exist a terminal symbol "t" such that:  */
  365. /* REDUCE(S1, t) and REDUCE(S2, t) are defined, and                  */
  366. /* REDUCE(S1, t) ^= REDUCE(S2, t)                                    */
  367. /*********************************************************************/
  368. static void merge_similar_t_rows(void)
  369. {
  370.     struct shift_header_type  sh;
  371.     struct reduce_header_type red;
  372.  
  373.     short *table;
  374.  
  375.     int i,
  376.         j,
  377.         rule_no,
  378.         state_no;
  379.  
  380.    unsigned long hash_address;
  381.  
  382.    struct node *q,
  383.                *r,
  384.                *tail,
  385.                *reduce_root;
  386.  
  387.     table = Allocate_short_array(num_shift_maps + 1);
  388.  
  389.     empty_root = NIL;
  390.     single_root = NIL;
  391.     multi_root = NIL;
  392.     top = 0;
  393.  
  394.     for (i = 1; i <= (int) max_la_state; i++)
  395.         shift_on_error_symbol[i] = FALSE;
  396.  
  397.     for (i = 0; i <= num_shift_maps; i++)
  398.         table[i] = NIL;
  399.  
  400. /*********************************************************************/
  401. /* We now hash all the states into TABLE, based on their shift map   */
  402. /* number.                                                           */
  403. /* The rules in the range of the REDUCE MAP are placed in sorted     */
  404. /* order in a linear linked list headed by REDUCE_ROOT.              */
  405. /*********************************************************************/
  406.     for (state_no = 1; state_no <= (int) max_la_state; state_no++)
  407.     {
  408.         reduce_root = NULL;
  409.         if (state_no > (int) num_states)
  410.             red = lastats[state_no].reduce;
  411.         else
  412.             red = reduce[state_no];
  413.  
  414.         for (i = 1; i <= red.size; i++)
  415.         {
  416.             rule_no = REDUCE_RULE_NO(red, i);
  417.  
  418.             for (q = reduce_root; q != NULL; tail = q, q = q -> next)
  419.             { /* Is it or not in REDUCE_ROOT list? */
  420.                 if (q -> value == rule_no)
  421.                     goto continue_traverse_reduce_map;
  422.                 if (q -> value > rule_no)
  423.                     break;
  424.             }
  425.  
  426.             r = Allocate_node(); /* Add element to REDUCE_ROOT list */
  427.             r -> value = rule_no;
  428.             if (q == reduce_root)
  429.             {
  430.                 r -> next = reduce_root;
  431.                 reduce_root = r;
  432.             }
  433.             else
  434.             {
  435.                 r -> next = q;
  436.                 tail -> next = r;
  437.             }
  438. continue_traverse_reduce_map:;
  439.         }
  440.  
  441. /*********************************************************************/
  442. /*   We compute the HASH_ADDRESS,  mark if the state has a shift     */
  443. /* action on the ERROR symbol, and search the hash TABLE to see if a */
  444. /* state matching the description is already in there.               */
  445. /*********************************************************************/
  446.         if (state_no > (int) num_states)
  447.             hash_address = lastats[state_no].shift_number;
  448.         else
  449.         {
  450.             if (default_opt == 5)
  451.             {
  452.                 sh = shift[statset[state_no].shift_number];
  453.                 for (j = 1; (j <= sh.size) &&
  454.                             (! shift_on_error_symbol[state_no]); j++)
  455.                     shift_on_error_symbol[state_no] =
  456.                           (SHIFT_SYMBOL(sh, j) == error_image);
  457.             }
  458.             hash_address = statset[state_no].shift_number;
  459.         }
  460.  
  461.         for (i = table[hash_address]; i != NIL; i = new_state_element[i].link)
  462.         {
  463.             for (r = reduce_root, q = new_state_element_reduce_nodes[i];
  464.                  (r != NULL) && (q != NULL);
  465.                  r = r -> next, q = q -> next)
  466.             {
  467.                 if (r -> value != q -> value)
  468.                     break;
  469.             }
  470.  
  471.             if (r == q)
  472.                 break;
  473.         }
  474.  
  475. /*********************************************************************/
  476. /* If the state is a new state to be inserted in the table, we now   */
  477. /* do so,  and place it in the proper category based on its reduces, */
  478. /* In any case, the IMAGE field is updated, and so is the relevant   */
  479. /* STATE_LIST element.                                               */
  480. /*                                                                   */
  481. /* If the state contains a shift action on the error symbol and also */
  482. /* contains reduce actions,  we allocate a new element for it and    */
  483. /* place it in the list headed by MULTI_ROOT.  Such states are not   */
  484. /* merged, because we do not take default reductions in them.        */
  485. /*********************************************************************/
  486.         if (shift_on_error_symbol[state_no] && (reduce_root != NULL))
  487.         {
  488.             top++;
  489.             if (i == NIL)
  490.             {
  491.                 new_state_element[top].link = table[hash_address];
  492.                 table[hash_address] = top;
  493.             }
  494.  
  495.             new_state_element[top].thread = multi_root;
  496.             multi_root = top;
  497.  
  498.             new_state_element[top].shift_number = hash_address;
  499.             new_state_element_reduce_nodes[top] = reduce_root;
  500.             state_list[state_no] = NIL;
  501.             new_state_element[top].image = state_no;
  502.         }
  503.         else if (i == NIL)
  504.         {
  505.             top++;
  506.             new_state_element[top].link = table[hash_address];
  507.             table[hash_address] = top;
  508.             if (reduce_root == NULL)
  509.             {
  510.                 new_state_element[top].thread = empty_root;
  511.                 empty_root = top;
  512.             }
  513.             else if (reduce_root -> next == NULL)
  514.             {
  515.                 new_state_element[top].thread = single_root;
  516.                 single_root = top;
  517.             }
  518.             else
  519.             {
  520.                 new_state_element[top].thread = multi_root;
  521.                 multi_root = top;
  522.             }
  523.             new_state_element[top].shift_number = hash_address;
  524.             new_state_element_reduce_nodes[top] = reduce_root;
  525.             state_list[state_no] = NIL;
  526.             new_state_element[top].image = state_no;
  527.         }
  528.         else
  529.         {
  530.             state_list[state_no] = new_state_element[i].image;
  531.             new_state_element[i].image = state_no;
  532.  
  533.             for (r = reduce_root; r != NULL; tail = r, r = r -> next)
  534.                 ;
  535.             if (reduce_root != NULL)
  536.                 free_nodes(reduce_root, tail);
  537.         }
  538.     }
  539.  
  540.     ffree(table);
  541.  
  542.     return;
  543. }
  544.  
  545.  
  546. /*********************************************************************/
  547. /*                       MERGE_SHIFT_DOMAINS:                        */
  548. /*********************************************************************/
  549. /*    If shift-default actions are requested, the shift actions      */
  550. /* associated with each state are factored out of the Action matrix  */
  551. /* and all identical rows are merged.  This merged matrix is used to */
  552. /* create a boolean vector that may be used to confirm whether or not*/
  553. /* there is a shift action in a given state S on a given symbol t.   */
  554. /* If we can determine that there is a shift action on a pair (S, t) */
  555. /* we can apply shift default to the Shift actions just like we did  */
  556. /* for the Goto actions.                                             */
  557. /*********************************************************************/
  558. static void merge_shift_domains(void)
  559. {
  560.     short *shift_domain_link,
  561.           *ordered_shift,
  562.           *terminal_list,
  563.           *temp_shift_default;
  564.  
  565.     short shift_domain_table[SHIFT_TABLE_SIZE];
  566.  
  567.     struct shift_header_type  sh;
  568.     struct reduce_header_type red;
  569.  
  570.     BOOLEAN *shift_symbols;
  571.  
  572.     unsigned long hash_address;
  573.  
  574.     int i,
  575.         j,
  576.         indx,
  577.         max_indx,
  578.         k_bytes,
  579.         old_table_size,
  580.         k,
  581.         percentage,
  582.         shift_size,
  583.         shift_no,
  584.         symbol,
  585.         state_no;
  586.  
  587.     long num_bytes;
  588.  
  589. /*********************************************************************/
  590. /* Some of the rows in the shift action map have already been merged */
  591. /* by the merging of compatible states... We simply need to increase */
  592. /* the size of the granularity by merging these new terminal states  */
  593. /* based only on their shift actions.                                */
  594. /*                                                                   */
  595. /* The array SHIFT_DOMAIN_TABLE is used as the base for a hash table.*/
  596. /* Each submap represented by a row of the shift action map is hashed*/
  597. /* into this table by summing the terminal symbols in its domain.    */
  598. /* The submap is then entered in the hash table and assigned a unique*/
  599. /* number if such a map was not already placed in the hash table.    */
  600. /* Otherwise, the number assigned to the previous submap is also     */
  601. /* associated with the new submap.                                   */
  602. /*                                                                   */
  603. /* The vector SHIFT_IMAGE is used to keep track of the unique number */
  604. /* associated with each unique shift submap.                         */
  605. /* The vector REAL_SHIFT_NUMBER is the inverse of SHIFT_IMAGE. It is */
  606. /* used to associate each unique number to its shift submap.         */
  607. /* The integer NUM_TABLE_ENTRIES is used to count the number of      */
  608. /* elements in the new merged shift map.                             */
  609. /*                                                                   */
  610. /* The arrays ORDERED_SHIFT and ROW_SIZE are also initialized here.  */
  611. /* They are used to sort the rows of the shift actions map later...  */
  612. /*********************************************************************/
  613.     shift_domain_link = Allocate_short_array(num_terminal_states + 1);
  614.     ordered_shift = Allocate_short_array(num_shift_maps + 1);
  615.     terminal_list = Allocate_short_array(num_terminals + 1);
  616.     shift_image = Allocate_short_array(max_la_state + 1);
  617.     real_shift_number = Allocate_short_array(num_shift_maps + 1);
  618.     shift_symbols = Allocate_boolean_array(num_terminals + 1);
  619.  
  620.     shift_check_index = Allocate_int_array(num_shift_maps + 1);
  621.  
  622.     for (i = 0; i <= SHIFT_TABLE_UBOUND; i++)
  623.        shift_domain_table[i] = NIL;
  624.  
  625.     num_table_entries = 0;
  626.     shift_domain_count = 0;
  627.  
  628.     for (state_no = 1; state_no <= num_terminal_states; state_no++)
  629.     {
  630.         shift_no = new_state_element[state_no].shift_number;
  631.         for (i = 1; i <=num_terminals; i++)
  632.             shift_symbols[i] = FALSE;
  633.  
  634.         sh = shift[shift_no];
  635.         shift_size = sh.size;
  636.         hash_address = shift_size;
  637.         for (i = 1; i <= shift_size; i++)
  638.         {
  639.             symbol = SHIFT_SYMBOL(sh, i);
  640.             hash_address += symbol;
  641.             shift_symbols[symbol] = TRUE;
  642.         }
  643.  
  644.         hash_address %= SHIFT_TABLE_SIZE;
  645.  
  646.         for (i = shift_domain_table[hash_address];
  647.              i != NIL; i = shift_domain_link[i])
  648.         {
  649.             sh = shift[new_state_element[i].shift_number];
  650.             if (sh.size == shift_size)
  651.             {
  652.                 for (j = 1; j <= shift_size; j++)
  653.                     if (! shift_symbols[SHIFT_SYMBOL(sh, j)])
  654.                         break;
  655.                 if (j > shift_size)
  656.                 {
  657.                     shift_image[state_no] = shift_image[i];
  658.                     goto continu;
  659.                 }
  660.             }
  661.         }
  662.         shift_domain_link[state_no] = shift_domain_table[hash_address];
  663.         shift_domain_table[hash_address] = state_no;
  664.  
  665.         shift_domain_count++;
  666.         shift_image[state_no] = shift_domain_count;
  667.  
  668.         real_shift_number[shift_domain_count] = shift_no;
  669.  
  670.         ordered_shift[shift_domain_count] = shift_domain_count;
  671.         row_size[shift_domain_count] = shift_size;
  672.         num_table_entries += shift_size;
  673. continu:;
  674.     }
  675.  
  676. /*********************************************************************/
  677. /*   Compute the frequencies, and remap the terminal symbols         */
  678. /* accordingly.                                                      */
  679. /*********************************************************************/
  680.     for ALL_TERMINALS(symbol)
  681.     {
  682.         frequency_symbol[symbol] = symbol;
  683.         frequency_count[symbol] = 0;
  684.     }
  685.  
  686.     for (i = 1; i <= shift_domain_count; i++)
  687.     {
  688.         shift_no = real_shift_number[i];
  689.         sh = shift[shift_no];
  690.         for (j = 1; j <= sh.size; j++)
  691.         {
  692.             symbol = SHIFT_SYMBOL(sh, j);
  693.             frequency_count[symbol]++;
  694.         }
  695.     }
  696.  
  697.     sortdes(frequency_symbol, frequency_count, 1, num_terminals,
  698.             shift_domain_count);
  699.  
  700.     for ALL_TERMINALS(symbol)
  701.         symbol_map[frequency_symbol[symbol]] =  symbol;
  702.  
  703.     symbol_map[DEFAULT_SYMBOL] = DEFAULT_SYMBOL;
  704.     eoft_image = symbol_map[eoft_image];
  705.     if (error_maps_bit)
  706.     {
  707.         error_image = symbol_map[error_image];
  708.         eolt_image = symbol_map[eolt_image];
  709.     }
  710.  
  711.     for (i = 1; i <= num_shift_maps; i++)
  712.     {
  713.         sh = shift[i];
  714.         for (j = 1; j <= sh.size; j++)
  715.              SHIFT_SYMBOL(sh, j) = symbol_map[SHIFT_SYMBOL(sh, j)];
  716.     }
  717.  
  718.     for (state_no = 1; state_no <= num_terminal_states; state_no++)
  719.     {
  720.         red = new_state_element[state_no].reduce;
  721.         for (i = 1; i <= red.size; i++)
  722.             REDUCE_SYMBOL(red, i) = symbol_map[REDUCE_SYMBOL(red, i)];
  723.     }
  724.  
  725. /*********************************************************************/
  726. /* If ERROR_MAPS are requested, we also have to remap the original   */
  727. /* REDUCE maps.                                                      */
  728. /*********************************************************************/
  729.     if (error_maps_bit)
  730.     {
  731.         for ALL_STATES(state_no)
  732.         {
  733.             red = reduce[state_no];
  734.             for (i = 1; i <= red.size; i++)
  735.                 REDUCE_SYMBOL(red, i) = symbol_map[REDUCE_SYMBOL(red, i)];
  736.         }
  737.     }
  738.  
  739.     /************************************************************/
  740.     /* Remap the SHIFT_DEFAULT map.                             */
  741.     /************************************************************/
  742.     temp_shift_default = Allocate_short_array(num_terminals + 1);
  743.     for ALL_TERMINALS(symbol)
  744.         temp_shift_default[symbol_map[symbol]] = shiftdf[symbol];
  745.     ffree(shiftdf);
  746.     shiftdf = temp_shift_default;
  747.  
  748. /*********************************************************************/
  749. /* We now compute the starting position for each Shift check row     */
  750. /* as we did for the terminal states.  The starting positions are    */
  751. /* stored in the vector SHIFT_CHECK_INDEX.                           */
  752. /*********************************************************************/
  753.     sortdes(ordered_shift, row_size, 1, shift_domain_count, num_terminals);
  754.  
  755.     increment_size = MAX((num_table_entries / 100 * increment),
  756.                          (num_terminals + 1));
  757.     old_table_size = table_size;
  758.     table_size = MIN((num_table_entries + increment_size), MAX_TABLE_SIZE);
  759.     if ((int) table_size > old_table_size)
  760.     {
  761.         ffree(previous);
  762.         ffree(next);
  763.         previous = Allocate_int_array(table_size + 1);
  764.         next = Allocate_int_array(table_size + 1);
  765.     }
  766.     else
  767.         table_size = old_table_size;
  768.  
  769.     first_index = 1;
  770.     previous[first_index] = NIL;
  771.     next[first_index] = first_index + 1;
  772.     for (indx = 2; indx < (int) table_size; indx++)
  773.     {
  774.         next[indx] = indx + 1;
  775.         previous[indx] = indx - 1;
  776.     }
  777.     last_index = table_size;
  778.     previous[last_index] = last_index - 1;
  779.     next[last_index] = NIL;
  780.     max_indx = first_index;
  781.  
  782. /*********************************************************************/
  783. /* Look for a suitable index where to overlay the shift check row.   */
  784. /*********************************************************************/
  785.     for (k = 1; k <= shift_domain_count; k++)
  786.     {
  787.         shift_no = ordered_shift[k];
  788.         sh = shift[real_shift_number[shift_no]];
  789.         indx = first_index;
  790.  
  791. look_for_match_in_sh_chk_tab:
  792.         if (indx == NIL)
  793.             indx = table_size + 1;
  794.         if (indx + num_terminals > (int) table_size)
  795.             reallocate();
  796.         for (i = 1; i <= sh.size; i++)
  797.         {
  798.             symbol = SHIFT_SYMBOL(sh, i);
  799.             if (next[indx + symbol] == OMEGA)
  800.             {
  801.                indx = next[indx];
  802.                goto look_for_match_in_sh_chk_tab;
  803.             }
  804.         }
  805.  
  806. /*********************************************************************/
  807. /* INDX marks the starting position for the row, remove all the      */
  808. /* positions that are claimed by that shift check row.               */
  809. /* If a position has the value 0,   then it is the starting position */
  810. /* of a Shift row that was previously processed, and that element    */
  811. /* has already been removed from the list of available positions.    */
  812. /*********************************************************************/
  813.         for (j = 1; j <= sh.size; j++)
  814.         {
  815.             symbol = SHIFT_SYMBOL(sh, j);
  816.             i = indx + symbol;
  817.             if (next[i] != 0)
  818.             {
  819.                 if (i == last_index)
  820.                 {
  821.                     last_index = previous[last_index];
  822.                     next[last_index] = NIL;
  823.                 }
  824.                 else
  825.                 {
  826.                     next[previous[i]] = next[i];
  827.                     previous[next[i]] = previous[i];
  828.                 }
  829.             }
  830.             next[i] = OMEGA;
  831.         }
  832.  
  833. /*********************************************************************/
  834. /* We now remove the starting position itself from the list without  */
  835. /* marking it as taken, since it can still be used for a shift check.*/
  836. /* MAX_INDX is updated if required.                                  */
  837. /* SHIFT_CHECK_INDEX(SHIFT_NO) is properly set to INDX as the        */
  838. /* starting position of STATE_NO.                                    */
  839. /*********************************************************************/
  840.         if (first_index == last_index)
  841.             first_index = NIL;
  842.         else if (indx == first_index)
  843.         {
  844.             first_index = next[first_index];
  845.             previous[first_index] = NIL;
  846.         }
  847.         else if (indx == last_index)
  848.         {
  849.             last_index = previous[last_index];
  850.             next[last_index] = NIL;
  851.         }
  852.         else
  853.         {
  854.             next[previous[indx]] = next[indx];
  855.             previous[next[indx]] = previous[indx];
  856.         }
  857.         next[indx] = 0;
  858.  
  859.         if (indx > max_indx)
  860.             max_indx = indx;
  861.         shift_check_index[shift_no] = indx;
  862.     }
  863.  
  864. /*********************************************************************/
  865. /* Update all counts, and report statistics.                         */
  866. /*********************************************************************/
  867.     shift_check_size = max_indx + num_terminals;
  868.  
  869.     printf("\n");
  870.     sprintf(msg_line,"Length of Shift Check Table: %d",shift_check_size);
  871.     PRNT(msg_line);
  872.  
  873.     sprintf(msg_line,"Number of entries in Shift Check Table: %d",
  874.             num_table_entries);
  875.     PRNT(msg_line);
  876.  
  877.     for (k = shift_check_size; k >= max_indx; k--)
  878.         if (next[k] == OMEGA)
  879.             break;
  880.     percentage = (((long) k - num_table_entries) * 1000)
  881.                  / num_table_entries;
  882.  
  883.     sprintf(msg_line,"Percentage of increase: %d.%d%%",
  884.             (percentage/10),(percentage % 10));
  885.     PRNT(msg_line);
  886.  
  887.     if (byte_bit)
  888.     {
  889.         num_bytes = shift_check_size;
  890.         if (num_terminals > 255)
  891.             num_bytes +=shift_check_size;
  892.     }
  893.     else
  894.         num_bytes = 2 * shift_check_size;
  895.     num_bytes += 2 * (num_terminal_states + num_terminals);
  896.  
  897.     k_bytes = (num_bytes / 1024) + 1;
  898.  
  899.     sprintf(msg_line,
  900.             "Storage required for Shift Check Table: %ld Bytes, %dK",
  901.             num_bytes, k_bytes);
  902.     PRNT(msg_line);
  903.     total_bytes += num_bytes;
  904.  
  905.     ffree(ordered_shift);
  906.     ffree(terminal_list);
  907.     ffree(shift_symbols);
  908.     ffree(shift_domain_link);
  909.  
  910.     return;
  911. }
  912.  
  913.  
  914. /*********************************************************************/
  915. /*                         OVERLAY_SIM_T_ROWS:                       */
  916. /*********************************************************************/
  917. /* By now, similar states have been grouped together, and placed in  */
  918. /* one of three linear linked lists headed by the root pointers:     */
  919. /* MULTI_ROOT, SINGLE_ROOT, and EMPTY_ROOT.                          */
  920. /* We iterate over each of these lists and construct new states out  */
  921. /* of these groups of similar states when they are compatible. Then, */
  922. /* we remap the terminal symbols.                                    */
  923. /*********************************************************************/
  924. static void overlay_sim_t_rows(void)
  925. {
  926.     int j,
  927.         k,
  928.         i,
  929.         rule_no,
  930.         state_no,
  931.         symbol,
  932.         default_rule,
  933.         state_subset_root,
  934.         state_set_root,
  935.         state_root,
  936.         reduce_size,
  937.         num_shifts_saved = 0,
  938.         num_reductions_saved = 0,
  939.         default_saves = 0;
  940.  
  941.     short *rule_count,
  942.           *reduce_action;
  943.  
  944.     struct shift_header_type  sh;
  945.     struct reduce_header_type red;
  946.     struct reduce_header_type new_red;
  947.  
  948.     struct node *q,
  949.                 *tail;
  950.  
  951.     rule_count = Allocate_short_array(num_rules + 1);
  952.     reduce_action = Allocate_short_array(num_terminals + 1);
  953.  
  954. /*********************************************************************/
  955. /*     We first iterate over the groups of similar states in the     */
  956. /* MULTI_ROOT list.  These states have been grouped together,        */
  957. /* because they have the same Shift map, and reduce to the same      */
  958. /* rules, but we must check that they are fully compatible by making */
  959. /* sure that no two states contain reduction to a different rule on  */
  960. /* the same symbol.                                                  */
  961. /*     The idea is to take a state out of the group, and merge with  */
  962. /* it as many other compatible states from the group as possible.    */
  963. /* remaining states from the group that caused clashes are thrown    */
  964. /* back into the MULTI_ROOT list as a new group of states.           */
  965. /*********************************************************************/
  966.     for (i = multi_root; i != NIL; i = new_state_element[i].thread)
  967.     {
  968.         for (q = new_state_element_reduce_nodes[i]; q != NULL; q = q -> next)
  969.         {
  970.             rule_count[q -> value] = 0;
  971.         }
  972.  
  973. /*********************************************************************/
  974. /* REDUCE_ACTION is used to keep track of reductions that are to be  */
  975. /* applied on terminal symbols as the states are merged.  We pick    */
  976. /* out the first state (STATE_NO) from the group of states involved, */
  977. /* initialize REDUCE_ACTION with its reduce map, and count the number*/
  978. /* of reductions associated with each rule in that state.            */
  979. /*********************************************************************/
  980.         state_no = new_state_element[i].image;
  981.         if (state_no > (int) num_states)
  982.             red = lastats[state_no].reduce;
  983.         else
  984.             red = reduce[state_no];
  985.  
  986.         for ALL_TERMINALS(j)
  987.             reduce_action[j] = OMEGA;
  988.         for (j = 1; j <= red.size; j++)
  989.         {
  990.             rule_no = REDUCE_RULE_NO(red, j);
  991.             reduce_action[REDUCE_SYMBOL(red, j)] = rule_no;
  992.             rule_count[rule_no]++;
  993.         }
  994.  
  995. /*********************************************************************/
  996. /* STATE_SET_ROOT is used to traverse the rest of the list that form */
  997. /* the group of states being processed.  STATE_SUBSET_ROOT is used   */
  998. /* to construct the new list that will consist of all states in the  */
  999. /* group that are compatible starting with the initial state.        */
  1000. /* STATE_ROOT is used to construct a list of all states in the group */
  1001. /* that are not compatible with the initial state.                   */
  1002. /*********************************************************************/
  1003.         state_set_root = state_list[state_no];
  1004.         state_subset_root = state_no;
  1005.         state_list[state_subset_root] = NIL;
  1006.         state_root = NIL;
  1007.  
  1008.         for (state_no = state_set_root;
  1009.              state_no != NIL; state_no = state_set_root)
  1010.         {
  1011.             state_set_root = state_list[state_set_root];
  1012.  
  1013. /*********************************************************************/
  1014. /* We traverse the reduce map of the state taken out from the group  */
  1015. /* and check to see if it is compatible with the subset being        */
  1016. /* constructed so far.                                               */
  1017. /*********************************************************************/
  1018.             if (state_no > (int) num_states)
  1019.                 red = lastats[state_no].reduce;
  1020.             else
  1021.                 red = reduce[state_no];
  1022.             for (j = 1; j <= red.size; j++)
  1023.             {
  1024.                 symbol = REDUCE_SYMBOL(red, j);
  1025.                 if (reduce_action[symbol] != OMEGA)
  1026.                 {
  1027.                     if (reduce_action[symbol] != REDUCE_RULE_NO(red, j))
  1028.                         break;
  1029.                 }
  1030.             }
  1031.  
  1032. /*********************************************************************/
  1033. /* If J > Q->REDUCE_ELEMENT.N then we traversed the whole reduce map,*/
  1034. /* and all the reductions involved are compatible with the new state */
  1035. /* being constructed.  The state involved is added to the subset, the*/
  1036. /* rule counts are updated, and the REDUCE_ACTIONS map is updated.   */
  1037. /*     Otherwise, we add the state involved to the STATE_ROOT list   */
  1038. /* which will be thrown back in the MULTI_ROOT list.                 */
  1039. /*********************************************************************/
  1040.             if (j > red.size)
  1041.             {
  1042.                 state_list[state_no] = state_subset_root;
  1043.                 state_subset_root = state_no;
  1044.                 for (j = 1; j <= red.size; j++)
  1045.                 {
  1046.                     symbol = REDUCE_SYMBOL(red, j);
  1047.                     if (reduce_action[symbol] == OMEGA)
  1048.                     {
  1049.                         rule_no = REDUCE_RULE_NO(red, j);
  1050.                         if (rules[rule_no].lhs == accept_image)
  1051.                             rule_no = 0;
  1052.                         reduce_action[symbol] = rule_no;
  1053.                         rule_count[rule_no]++;
  1054.                     }
  1055.                     else
  1056.                         num_reductions_saved++;
  1057.                 }
  1058.             }
  1059.             else
  1060.             {
  1061.                 state_list[state_no] = state_root;
  1062.                 state_root = state_no;
  1063.             }
  1064.         }
  1065.  
  1066. /*********************************************************************/
  1067. /* Figure out the best default rule candidate, and update            */
  1068. /* DEFAULT_SAVES.                                                    */
  1069. /* Recall that all accept actions were changed into reduce actions   */
  1070. /* by rule 0.                                                        */
  1071. /*********************************************************************/
  1072.         k = 0;
  1073.         reduce_size = 0;
  1074.         default_rule = error_act;
  1075.         for (q = new_state_element_reduce_nodes[i];
  1076.              q != NULL; tail = q, q = q -> next)
  1077.         {
  1078.             rule_no = q -> value;
  1079.             reduce_size += rule_count[rule_no];
  1080.             if ((rule_count[rule_no] > k) && (rule_no != 0)
  1081.                 && ! shift_on_error_symbol[state_subset_root])
  1082.             {
  1083.                 k = rule_count[rule_no];
  1084.                 default_rule = rule_no;
  1085.             }
  1086.         }
  1087.         default_saves += k;
  1088.         reduce_size -= k;
  1089.  
  1090. /*********************************************************************/
  1091. /* If STATE_ROOT is not NIL then there are states in the group that  */
  1092. /* did not meet the compatibility test.  Throw those states back in  */
  1093. /* front of MULTI_ROOT as a group.                                   */
  1094. /*********************************************************************/
  1095.         if (state_root != NIL)
  1096.         {
  1097.             top++;
  1098.             new_state_element[top].thread = new_state_element[i].thread;
  1099.             new_state_element[i].thread = top;
  1100.             if (state_root > (int) num_states)
  1101.                 new_state_element[top].shift_number =
  1102.                           lastats[state_root].shift_number;
  1103.             else
  1104.                 new_state_element[top].shift_number =
  1105.                                      statset[state_root].shift_number;
  1106.             new_state_element_reduce_nodes[top] =
  1107.                                      new_state_element_reduce_nodes[i];
  1108.             new_state_element[top].image = state_root;
  1109.         }
  1110.         else
  1111.             free_nodes(new_state_element_reduce_nodes[i], tail);
  1112.  
  1113. /*********************************************************************/
  1114. /* Create Reduce map for the newly created terminal state.           */
  1115. /* We may assume that SYMBOL field of defaults is already set to     */
  1116. /* the DEFAULT_SYMBOL value.                                         */
  1117. /*********************************************************************/
  1118.         new_red = Allocate_reduce_map(reduce_size);
  1119.  
  1120.         REDUCE_SYMBOL(new_red, 0) = DEFAULT_SYMBOL;
  1121.         REDUCE_RULE_NO(new_red, 0) = default_rule;
  1122.         for ALL_TERMINALS(symbol)
  1123.         {
  1124.             if (reduce_action[symbol] != OMEGA)
  1125.             {
  1126.                 if (reduce_action[symbol] != default_rule)
  1127.                 {
  1128.                     REDUCE_SYMBOL(new_red, reduce_size) = symbol;
  1129.                     if (reduce_action[symbol] == 0)
  1130.                         REDUCE_RULE_NO(new_red, reduce_size) = accept_act;
  1131.                     else
  1132.                         REDUCE_RULE_NO(new_red, reduce_size) =
  1133.                                        reduce_action[symbol];
  1134.                     reduce_size--;
  1135.                 }
  1136.             }
  1137.         }
  1138.         new_state_element[i].reduce = new_red;
  1139.         new_state_element[i].image = state_subset_root;
  1140.     }
  1141.  
  1142. /*********************************************************************/
  1143. /* We now process groups of states that have reductions to a single  */
  1144. /* rule.  Those states are fully compatible, and the default is the  */
  1145. /* rule in question.                                                 */
  1146. /* Any of the REDUCE_ELEMENT maps that belongs to a state in the     */
  1147. /* group of states being processed may be reused for the new  merged */
  1148. /* state.                                                            */
  1149. /*********************************************************************/
  1150.     for (i = single_root; i != NIL; i = new_state_element[i].thread)
  1151.     {
  1152.         state_no = new_state_element[i].image;
  1153.         q = new_state_element_reduce_nodes[i];
  1154.         rule_no = q -> value;
  1155.         free_nodes(q, q);
  1156.         if (rules[rule_no].lhs == accept_image)
  1157.         {
  1158.             red = reduce[state_no];
  1159.             reduce_size = red.size;
  1160.  
  1161.             new_red = Allocate_reduce_map(reduce_size);
  1162.  
  1163.             REDUCE_SYMBOL(new_red, 0) = DEFAULT_SYMBOL;
  1164.             REDUCE_RULE_NO(new_red, 0) = error_act;
  1165.  
  1166.             for (j = 1; j <= reduce_size; j++)
  1167.             {
  1168.                 REDUCE_SYMBOL(new_red, j) = REDUCE_SYMBOL(red, j);
  1169.                 REDUCE_RULE_NO(new_red, j) = accept_act;
  1170.             }
  1171.         }
  1172.         else
  1173.         {
  1174.             for ALL_TERMINALS(j)
  1175.                 reduce_action[j] = OMEGA;
  1176.  
  1177.             for (; state_no != NIL; state_no = state_list[state_no])
  1178.             {
  1179.                 if (state_no > (int) num_states)
  1180.                     red = lastats[state_no].reduce;
  1181.                 else
  1182.                     red = reduce[state_no];
  1183.                 for (j = 1; j <= red.size; j++)
  1184.                 {
  1185.                     symbol = REDUCE_SYMBOL(red, j);
  1186.                     if (reduce_action[symbol] == OMEGA)
  1187.                     {
  1188.                         reduce_action[symbol] = rule_no;
  1189.                         default_saves++;
  1190.                     }
  1191.                     else
  1192.                        num_reductions_saved++;
  1193.                 }
  1194.             }
  1195.  
  1196.             new_red = Allocate_reduce_map(0);
  1197.  
  1198.             REDUCE_SYMBOL(new_red, 0) = DEFAULT_SYMBOL;
  1199.             REDUCE_RULE_NO(new_red, 0) = rule_no;
  1200.         }
  1201.         new_state_element[i].reduce = new_red;
  1202.     }
  1203.  
  1204. /*********************************************************************/
  1205. /* Groups of states that have no reductions are also compatible.     */
  1206. /* Their default is ERROR_ACTION.                                    */
  1207. /*********************************************************************/
  1208.     for (i = empty_root; i != NIL; i = new_state_element[i].thread)
  1209.     {
  1210.         state_no = new_state_element[i].image;
  1211.         if (state_no > (int) num_states)
  1212.             red = lastats[state_no].reduce;
  1213.         else
  1214.             red = reduce[state_no];
  1215.         REDUCE_SYMBOL(red, 0) = DEFAULT_SYMBOL;
  1216.         REDUCE_RULE_NO(red, 0) = error_act;
  1217.         new_state_element[i].reduce = red;
  1218.     }
  1219.  
  1220.     num_terminal_states = top;
  1221.  
  1222.     frequency_symbol = Allocate_short_array(num_terminals + 1);
  1223.     frequency_count = Allocate_short_array(num_terminals + 1);
  1224.     row_size = Allocate_short_array(max_la_state + 1);
  1225.  
  1226.     if (shift_default_bit)
  1227.         merge_shift_domains();
  1228.  
  1229. /*********************************************************************/
  1230. /* We now reorder the terminal states based on the number of actions */
  1231. /* in them, and remap the terminal symbols if they were not already  */
  1232. /* remapped in the previous block for the SHIFT_CHECK vector.        */
  1233. /*********************************************************************/
  1234.     for ALL_TERMINALS(symbol)
  1235.     {
  1236.         frequency_symbol[symbol] = symbol;
  1237.         frequency_count[symbol] = 0;
  1238.     }
  1239.  
  1240.     for (i = 1; i <= num_terminal_states; i++)
  1241.     {
  1242.         ordered_state[i] = i;
  1243.         row_size[i] = 0;
  1244.         sh = shift[new_state_element[i].shift_number];
  1245.         for (j = 1; j <= sh.size; j++)
  1246.         {
  1247.             symbol = SHIFT_SYMBOL(sh, j);
  1248.             if ((! shift_default_bit) ||
  1249.                 (SHIFT_ACTION(sh, j) != shiftdf[symbol]))
  1250.             {
  1251.                 row_size[i]++;
  1252.                 frequency_count[symbol]++;
  1253.             }
  1254.         }
  1255.  
  1256.         for (state_no = state_list[new_state_element[i].image];
  1257.              state_no != NIL; state_no = state_list[state_no])
  1258.         {
  1259.             num_shifts_saved += row_size[i];
  1260.         }
  1261.  
  1262.         /***********************************************/
  1263.         /* Note that the Default action is skipped !!! */
  1264.         /***********************************************/
  1265.         red = new_state_element[i].reduce;
  1266.         for (j = 1; j <= red.size; j++)
  1267.         {
  1268.             symbol = REDUCE_SYMBOL(red, j);
  1269.             row_size[i]++;
  1270.             frequency_count[symbol]++;
  1271.         }
  1272.     }
  1273.     sprintf(msg_line,
  1274.             "Number of unique terminal states: %d",
  1275.             num_terminal_states);
  1276.     PRNT(msg_line);
  1277.     sprintf(msg_line, "Number of Shift actions saved by merging: %d",
  1278.                       num_shifts_saved);
  1279.     PRNT(msg_line);
  1280.     sprintf(msg_line, "Number of Reduce actions saved by merging: %d",
  1281.                       num_reductions_saved);
  1282.     PRNT(msg_line);
  1283.     sprintf(msg_line, "Number of Reduce saved by default: %d",
  1284.                       default_saves);
  1285.     PRNT(msg_line);
  1286.  
  1287.     sortdes(ordered_state, row_size, 1, num_terminal_states,
  1288.             num_terminals);
  1289.  
  1290.     if (! shift_default_bit)
  1291.     {
  1292.         sortdes(frequency_symbol, frequency_count, 1, num_terminals,
  1293.                 num_terminal_states);
  1294.         for ALL_TERMINALS(symbol)
  1295.             symbol_map[frequency_symbol[symbol]] =  symbol;
  1296.         symbol_map[DEFAULT_SYMBOL] = DEFAULT_SYMBOL;
  1297.         eoft_image = symbol_map[eoft_image];
  1298.         if (error_maps_bit)
  1299.         {
  1300.             error_image = symbol_map[error_image];
  1301.             eolt_image = symbol_map[eolt_image];
  1302.         }
  1303.         for (i = 1; i <= num_shift_maps; i++)
  1304.         {
  1305.             sh = shift[i];
  1306.             for (j = 1; j <= sh.size; j++)
  1307.                 SHIFT_SYMBOL(sh, j) = symbol_map[SHIFT_SYMBOL(sh, j)];
  1308.         }
  1309.  
  1310.         for (state_no = 1; state_no <= num_terminal_states; state_no++)
  1311.         {
  1312.             red = new_state_element[state_no].reduce;
  1313.             for (i = 1; i <= red.size; i++)
  1314.                 REDUCE_SYMBOL(red, i) = symbol_map[REDUCE_SYMBOL(red, i)];
  1315.         }
  1316.  
  1317. /*********************************************************************/
  1318. /* If ERROR_MAPS are requested, we also have to remap the original   */
  1319. /* REDUCE maps.                                                      */
  1320. /*********************************************************************/
  1321.         if (error_maps_bit)
  1322.         {
  1323.             for ALL_STATES(state_no)
  1324.             {
  1325.                 red = reduce[state_no];
  1326.                 for (i = 1; i <= red.size; i++)
  1327.                     REDUCE_SYMBOL(red, i) = symbol_map[REDUCE_SYMBOL(red, i)];
  1328.             }
  1329.         }
  1330.     }
  1331.     num_table_entries = num_shifts + num_shift_reduces + num_reductions
  1332.                         - num_shifts_saved - num_reductions_saved
  1333.                         - default_saves + num_terminal_states;
  1334.  
  1335.     ffree(rule_count);
  1336.     ffree(reduce_action);
  1337.     ffree(row_size);
  1338.     ffree(frequency_count);
  1339.     ffree(frequency_symbol);
  1340.     ffree(shift_on_error_symbol);
  1341.     ffree(new_state_element_reduce_nodes);
  1342.  
  1343.     return;
  1344. }
  1345.  
  1346.  
  1347. /*********************************************************************/
  1348. /*                           OVERLAP_T_ROWS:                         */
  1349. /*********************************************************************/
  1350. /* We now compute the starting position for each terminal state just */
  1351. /* as we did for the non-terminal states.                            */
  1352. /* The starting positions are stored in the vector TERM_STATE_INDEX. */
  1353. /*********************************************************************/
  1354. static void overlap_t_rows(void)
  1355. {
  1356.     struct shift_header_type  sh;
  1357.     struct reduce_header_type red;
  1358.  
  1359.     short *terminal_list;
  1360.  
  1361.     int root_symbol,
  1362.         symbol,
  1363.         i,
  1364.         k,
  1365.         k_bytes,
  1366.         percentage,
  1367.         state_no,
  1368.         old_size,
  1369.         max_indx,
  1370.         indx;
  1371.  
  1372.     long num_bytes;
  1373.  
  1374.     terminal_list = Allocate_short_array(num_terminals + 1);
  1375.     term_state_index = Allocate_int_array(max_la_state + 1);
  1376.  
  1377.     increment_size = MAX((num_table_entries * increment / 100),
  1378.                          (num_terminals + 1));
  1379.     old_size = table_size;
  1380.     table_size = MIN((num_table_entries + increment_size), MAX_TABLE_SIZE);
  1381.     if ((int) table_size > old_size)
  1382.     {
  1383.         ffree(previous);
  1384.         ffree(next);
  1385.         next = Allocate_int_array(table_size + 1);
  1386.         previous = Allocate_int_array(table_size + 1);
  1387.     }
  1388.     else
  1389.         table_size = old_size;
  1390.  
  1391.     first_index = 1;
  1392.     previous[first_index] = NIL;
  1393.     next[first_index] = first_index + 1;
  1394.     for (indx = 2; indx < (int) table_size; indx++)
  1395.     {
  1396.         next[indx] = indx + 1;
  1397.         previous[indx] = indx - 1;
  1398.     }
  1399.     last_index = table_size;
  1400.     previous[last_index] = last_index - 1;
  1401.     next[last_index] = NIL;
  1402.  
  1403.     max_indx = first_index;
  1404.  
  1405.     for (k = 1; k <= num_terminal_states; k++)
  1406.     {
  1407.         state_no = ordered_state[k];
  1408. /*********************************************************************/
  1409. /* For the terminal table, we are dealing with two lists, the SHIFT  */
  1410. /* list, and the REDUCE list. Those lists are merged together first  */
  1411. /* in TERMINAL_LIST.  Since we have to iterate over the list twice,  */
  1412. /* this merging makes things easy.                                   */
  1413. /*********************************************************************/
  1414.         root_symbol = NIL;
  1415.         sh = shift[new_state_element[state_no].shift_number];
  1416.         for (i = 1; i <= sh.size; i++)
  1417.         {
  1418.             symbol = SHIFT_SYMBOL(sh, i);
  1419.             if (! shift_default_bit ||
  1420.                 (SHIFT_ACTION(sh, i) != shiftdf[symbol]))
  1421.             {
  1422.                 terminal_list[symbol] = root_symbol;
  1423.                 root_symbol = symbol;
  1424.             }
  1425.         }
  1426.  
  1427.         red = new_state_element[state_no].reduce;
  1428.         for (i = 1; i <= red.size; i++)
  1429.         {
  1430.             terminal_list[REDUCE_SYMBOL(red, i)] = root_symbol;
  1431.             root_symbol = REDUCE_SYMBOL(red, i);
  1432.         }
  1433.  
  1434. /*********************************************************************/
  1435. /* Look for a suitable index where to overlay the state.             */
  1436. /*********************************************************************/
  1437.         indx = first_index;
  1438.  
  1439. look_for_match_in_term_table:
  1440.         if (indx == NIL)
  1441.             indx = table_size + 1;
  1442.         if (indx + num_terminals > (int) table_size)
  1443.             reallocate();
  1444.         for (symbol = root_symbol;
  1445.              symbol != NIL; symbol = terminal_list[symbol])
  1446.         {
  1447.             if (next[indx + symbol] == OMEGA)
  1448.             {
  1449.                 indx = next[indx];
  1450.                 goto look_for_match_in_term_table;
  1451.             }
  1452.         }
  1453.  
  1454. /*********************************************************************/
  1455. /* INDX marks the starting position for the state, remove all the    */
  1456. /* positions that are claimed by terminal actions in the state.      */
  1457. /*********************************************************************/
  1458.         for (symbol = root_symbol;
  1459.              symbol != NIL; symbol = terminal_list[symbol])
  1460.         {
  1461.             i = indx + symbol;
  1462.             if (i == last_index)
  1463.             {
  1464.                 last_index = previous[last_index];
  1465.                 next[last_index] = NIL;
  1466.             }
  1467.             else
  1468.             {
  1469.                 next[previous[i]] = next[i];
  1470.                 previous[next[i]] = previous[i];
  1471.             }
  1472.             next[i] = OMEGA;
  1473.         }
  1474.  
  1475. /*********************************************************************/
  1476. /* We now remove the starting position itself from the list, and     */
  1477. /* mark it as taken(CHECK(INDX) = OMEGA)                             */
  1478. /* MAX_INDX is updated if required.                                  */
  1479. /* TERM_STATE_INDEX(STATE_NO) is properly set to INDX as the starting*/
  1480. /* position of STATE_NO.                                             */
  1481. /*********************************************************************/
  1482.         if (first_index == last_index)
  1483.             first_index = NIL;
  1484.         else if (indx == first_index)
  1485.         {
  1486.             first_index = next[first_index];
  1487.             previous[first_index] = NIL;
  1488.         }
  1489.         else if (indx == last_index)
  1490.         {
  1491.             last_index = previous[last_index];
  1492.             next[last_index] = NIL;
  1493.         }
  1494.         else
  1495.         {
  1496.             next[previous[indx]] = next[indx];
  1497.             previous[next[indx]] = previous[indx];
  1498.         }
  1499.  
  1500.         next[indx] = OMEGA;
  1501.  
  1502.         if (indx > max_indx)
  1503.             max_indx = indx;
  1504.         term_state_index[state_no] = indx;
  1505.     }
  1506.  
  1507. /*********************************************************************/
  1508. /* Update all counts, and report statistics.                         */
  1509. /*********************************************************************/
  1510.     term_check_size = max_indx + num_terminals;
  1511.     for (term_action_size = max_indx + num_terminals;
  1512.          term_action_size >= max_indx; term_action_size--)
  1513.         if (next[term_action_size] == OMEGA)
  1514.             break;
  1515.  
  1516.     printf("\n");
  1517.     sprintf(msg_line, "Length of Terminal Check Table: %d",
  1518.                       term_check_size);
  1519.     PRNT(msg_line);
  1520.  
  1521.     sprintf(msg_line, "Length of Terminal Action Table: %d",
  1522.                       term_action_size);
  1523.     PRNT(msg_line);
  1524.  
  1525.     sprintf(msg_line, "Number of entries in Terminal Action Table: %d",
  1526.                       num_table_entries);
  1527.     PRNT(msg_line);
  1528.  
  1529.     percentage = (((long)term_action_size - num_table_entries) * 1000)
  1530.                   / num_table_entries;
  1531.  
  1532.     sprintf(msg_line, "Percentage of increase: %d.%d%%",
  1533.                       (percentage / 10), (percentage % 10));
  1534.     PRNT(msg_line);
  1535.  
  1536.     if (byte_bit)
  1537.     {
  1538.         num_bytes = 2 * term_action_size + term_check_size;
  1539.         if (num_terminals > 255)
  1540.             num_bytes += term_check_size;
  1541.     }
  1542.     else
  1543.         num_bytes = 2 * (term_action_size + term_check_size);
  1544.  
  1545.     if (shift_default_bit)
  1546.         num_bytes += (2 * num_terminal_states);
  1547.  
  1548.     k_bytes = (num_bytes / 1024) + 1;
  1549.  
  1550.     sprintf(msg_line,
  1551.             "Storage required for Terminal Tables: %ld Bytes, %dK",
  1552.             num_bytes, k_bytes);
  1553.     PRNT(msg_line);
  1554.  
  1555.     total_bytes += num_bytes;
  1556.  
  1557. /*********************************************************************/
  1558. /* Report total number of storage used.                              */
  1559. /*********************************************************************/
  1560.     k_bytes = (total_bytes / 1024) + 1;
  1561.     sprintf(msg_line,
  1562.             "Total storage required for Tables: %ld Bytes, %dK",
  1563.             total_bytes, k_bytes);
  1564.     PRNT(msg_line);
  1565.  
  1566. /*********************************************************************/
  1567. /* We now write out the tables to the SYSTAB file.                   */
  1568. /*********************************************************************/
  1569.  
  1570.     table_size = MAX(check_size, term_check_size);
  1571.     table_size = MAX(table_size, shift_check_size);
  1572.     table_size = MAX(table_size, action_size);
  1573.     table_size = MAX(table_size, term_action_size);
  1574.  
  1575.     ffree(terminal_list);
  1576.     ffree(next);
  1577.     ffree(previous);
  1578. }
  1579.  
  1580.  
  1581. /*********************************************************************/
  1582. /*                         PRINT_TABLES:                             */
  1583. /*********************************************************************/
  1584. /* We now write out the tables to the SYSTAB file.                   */
  1585. /*********************************************************************/
  1586. static void print_tables(void)
  1587. {
  1588.     int *check,
  1589.         *action;
  1590.  
  1591.     int la_state_offset,
  1592.         i,
  1593.         j,
  1594.         k,
  1595.         indx,
  1596.         act,
  1597.         result_act,
  1598.         default_count = 0,
  1599.         goto_count = 0,
  1600.         goto_reduce_count = 0,
  1601.         reduce_count = 0,
  1602.         la_shift_count = 0,
  1603.         shift_count = 0,
  1604.         shift_reduce_count = 0,
  1605.         rule_no,
  1606.         symbol,
  1607.         state_no;
  1608.  
  1609.     char *tok;
  1610.  
  1611.     long offset;
  1612.  
  1613.     check = Allocate_int_array(table_size + 1);
  1614.     action = Allocate_int_array(table_size + 1);
  1615.  
  1616.     /******************************************************************/
  1617.     /* Prepare header card with proper information, and write it out. */
  1618.     /******************************************************************/
  1619.     offset = error_act;
  1620.     if (read_reduce_bit)
  1621.         offset += num_rules;
  1622.     la_state_offset = offset;
  1623.  
  1624.     if (offset > (MAX_TABLE_SIZE + 1))
  1625.     {
  1626.         sprintf(msg_line, "Table contains entries that are > "
  1627.                 "%d; Processing stopped.", MAX_TABLE_SIZE + 1);
  1628.         PRNTERR(msg_line);
  1629.         exit(12);
  1630.     }
  1631.  
  1632.     output_buffer[0] = 'S';
  1633.     output_buffer[1] = (goto_default_bit ? '1' : '0');
  1634.     output_buffer[2] = (nt_check_bit ? '1' : '0');
  1635.     output_buffer[3] = (read_reduce_bit ? '1' : '0');
  1636.     output_buffer[4] = (single_productions_bit ? '1' : '0');
  1637.     output_buffer[5] = (shift_default_bit ? '1' : '0');
  1638.     output_buffer[6] = (rules[1].lhs == accept_image ? '1' : '0');
  1639.                        /* are there more than 1 start symbols? */
  1640.     output_buffer[7] = (error_maps_bit ? '1' : '0');
  1641.     output_buffer[8] = (byte_bit && last_symbol <= 255 ? '1' : '0');
  1642.     output_buffer[9] = escape;
  1643.  
  1644.     output_ptr = output_buffer + 10;
  1645.     field(num_terminals, 5);
  1646.     field(num_non_terminals, 5);
  1647.     field(num_rules, 5);
  1648.     field(num_states, 5);
  1649.     field(check_size, 5);
  1650.     field(action_size, 5);
  1651.     field(term_check_size, 5);
  1652.     field(term_action_size, 5);
  1653.     field(state_index[1] + num_rules, 5);
  1654.     field(eoft_image, 5);
  1655.     field(accept_act, 5);
  1656.     field(error_act, 5);
  1657.     field(la_state_offset, 5);
  1658.     field(lalr_level, 5);
  1659.     *output_ptr++ = '\n';
  1660.  
  1661.     /*********************************************************/
  1662.     /* We write the terminal symbols map.                    */
  1663.     /*********************************************************/
  1664.     for ALL_TERMINALS(symbol)
  1665.     {
  1666.         int len;
  1667.  
  1668.         tok = RETRIEVE_STRING(symbol);
  1669.         if (tok[0] == '\n')  /* we're dealing with special symbol?  */
  1670.             tok[0] = escape; /* replace initial marker with escape. */
  1671.         len = strlen(tok);
  1672.         field(symbol_map[symbol], 4);
  1673.         field(len, 4);
  1674.         if (len <= 64)
  1675.             strcpy(output_ptr, tok);
  1676.         else
  1677.         {
  1678.             memcpy(output_ptr, tok, 64);
  1679.             output_ptr += 64;
  1680.             *output_ptr++ = '\n';
  1681.             BUFFER_CHECK(systab);
  1682.             tok += 64;
  1683.  
  1684.             for (len = strlen(tok); len > 72; len = strlen(tok))
  1685.             {
  1686.                 memcpy(output_ptr, tok, 72);
  1687.                 output_ptr += 72;
  1688.                 *output_ptr++ = '\n';
  1689.                 BUFFER_CHECK(systab);
  1690.                 tok += 72;
  1691.             }
  1692.             memcpy(output_ptr, tok, len);
  1693.         }
  1694.         output_ptr += len;
  1695.         *output_ptr++ = '\n';
  1696.         BUFFER_CHECK(systab);
  1697.     }
  1698.  
  1699.     /*********************************************************/
  1700.     /* We write the non-terminal symbols map.                */
  1701.     /*********************************************************/
  1702.     for ALL_NON_TERMINALS(symbol)
  1703.     {
  1704.         int len;
  1705.  
  1706.         tok = RETRIEVE_STRING(symbol);
  1707.         if (tok[0] == '\n')  /* we're dealing with special symbol?  */
  1708.             tok[0] = escape; /* replace initial marker with escape. */
  1709.         len = strlen(tok);
  1710.         field(symbol_map[symbol]-num_terminals, 4);
  1711.         field(len, 4);
  1712.         if (len <= 64)
  1713.             strcpy(output_ptr, tok);
  1714.         else
  1715.         {
  1716.             memcpy(output_ptr, tok, 64);
  1717.             output_ptr += 64;
  1718.             *output_ptr++ = '\n';
  1719.             BUFFER_CHECK(systab);
  1720.             tok += 64;
  1721.  
  1722.             for (len = strlen(tok); len > 72; len = strlen(tok))
  1723.             {
  1724.                 memcpy(output_ptr, tok, 72);
  1725.                 output_ptr += 72;
  1726.                 *output_ptr++ = '\n';
  1727.                 BUFFER_CHECK(systab);
  1728.                 tok += 72;
  1729.             }
  1730.             memcpy(output_ptr, tok, len);
  1731.         }
  1732.         output_ptr += len;
  1733.         *output_ptr++ = '\n';
  1734.         BUFFER_CHECK(systab);
  1735.     }
  1736.  
  1737.     /*********************************************************/
  1738.     /* Initialize TABLES with default actions.               */
  1739.     /*********************************************************/
  1740.     for (i = 1; i <= check_size; i++)
  1741.         check[i] = DEFAULT_SYMBOL;
  1742.  
  1743.     for (i = 1; i <= (int) action_size; i++)
  1744.         action[i] = error_act;
  1745.  
  1746.     /********************************************************************/
  1747.     /*    Update the default non-terminal action of each state with the */
  1748.     /* appropriate corresponding terminal state starting index.         */
  1749.     /********************************************************************/
  1750.     for (i = 1; i <= num_terminal_states; i++)
  1751.     {
  1752.         indx = term_state_index[i];
  1753.         state_no = new_state_element[i].image;
  1754.  
  1755.     /*********************************************************************/
  1756.     /*   Update the action link between the non-terminal and terminal    */
  1757.     /* tables.  If error-maps are requested, an indirect linking is made */
  1758.     /* as follows:                                                       */
  1759.     /*  Each non-terminal row identifies its original state number, and  */
  1760.     /* a new vector START_TERMINAL_STATE indexable by state numbers      */
  1761.     /* identifies the starting point of each state in the terminal table.*/
  1762.     /*********************************************************************/
  1763.         if (state_no <= (int) num_states)
  1764.         {
  1765.             for (; state_no != NIL; state_no = state_list[state_no])
  1766.             {
  1767.                 action[state_index[state_no]] = indx;
  1768.             }
  1769.         }
  1770.         else
  1771.         {
  1772.             for (; state_no != NIL; state_no = state_list[state_no])
  1773.             {
  1774.                 act = la_state_offset + indx;
  1775.                 state_index[state_no] = act;
  1776.             }
  1777.         }
  1778.     }
  1779.  
  1780.     /*********************************************************************/
  1781.     /*  Now update the non-terminal tables with the non-terminal actions.*/
  1782.     /*********************************************************************/
  1783.     for ALL_STATES(state_no)
  1784.     {
  1785.         struct goto_header_type go_to;
  1786.  
  1787.         indx = state_index[state_no];
  1788.         go_to = statset[state_no].go_to;
  1789.         for (j = 1; j <= go_to.size; j++)
  1790.         {
  1791.             symbol = GOTO_SYMBOL(go_to, j);
  1792.             i = indx + symbol;
  1793.             if (goto_default_bit || nt_check_bit)
  1794.                 check[i] = symbol;
  1795.             act = GOTO_ACTION(go_to, j);
  1796.             if (act > 0)
  1797.             {
  1798.                 action[i] = state_index[act] + num_rules;
  1799.                 goto_count++;
  1800.             }
  1801.             else
  1802.             {
  1803.                 action[i] = -act;
  1804.                 goto_reduce_count++;
  1805.             }
  1806.         }
  1807.     }
  1808.  
  1809.     /*********************************************************************/
  1810.     /* Write size of right hand side of rules followed by CHECK table.   */
  1811.     /*********************************************************************/
  1812.     k = 0;
  1813.     for (i = 1; i <= num_rules; i++)
  1814.     {
  1815.         field(RHS_SIZE(i), 4);
  1816.         k++;
  1817.         if (k == 18)
  1818.         {
  1819.             *output_ptr++ = '\n';
  1820.             BUFFER_CHECK(systab);
  1821.             k = 0;
  1822.         }
  1823.     }
  1824.  
  1825.     for (i = 1; i <= check_size; i++)
  1826.     {
  1827.         field(check[i], 4);
  1828.         k++;
  1829.         if (k == 18)
  1830.         {
  1831.             *output_ptr++ = '\n';
  1832.             BUFFER_CHECK(systab);
  1833.             k = 0;
  1834.         }
  1835.     }
  1836.  
  1837.     if (k != 0)
  1838.     {
  1839.         *output_ptr++ = '\n';
  1840.         BUFFER_CHECK(systab);
  1841.     }
  1842.  
  1843.     /*********************************************************************/
  1844.     /* Write left hand side symbol of rules followed by ACTION table.    */
  1845.     /*********************************************************************/
  1846.     k = 0;
  1847.     for (i = 1; i <= num_rules; i++)
  1848.     {
  1849.         field(symbol_map[rules[i].lhs] - num_terminals, 6);
  1850.         k++;
  1851.         if (k == 12)
  1852.         {
  1853.             *output_ptr++ = '\n';
  1854.             BUFFER_CHECK(systab);
  1855.             k = 0;
  1856.         }
  1857.     }
  1858.  
  1859.     for (i = 1; i <= (int) action_size; i++)
  1860.     {
  1861.         field(action[i], 6);
  1862.         k++;
  1863.         if (k == 12)
  1864.         {
  1865.             *output_ptr++ = '\n';
  1866.             BUFFER_CHECK(systab);
  1867.             k = 0;
  1868.         }
  1869.     }
  1870.  
  1871.     if (k != 0)
  1872.     {
  1873.         *output_ptr++ = '\n';
  1874.         BUFFER_CHECK(systab);
  1875.     }
  1876.  
  1877.     /********************************************************************/
  1878.     /* Initialize the terminal tables,and update with terminal actions. */
  1879.     /********************************************************************/
  1880.     for (i = 1; i <= term_check_size; i++)
  1881.         check[i] = DEFAULT_SYMBOL;
  1882.  
  1883.     for (i = 1; i <= term_action_size; i++)
  1884.         action[i] = error_act;
  1885.  
  1886.     for (state_no = 1; state_no <= num_terminal_states; state_no++)
  1887.     {
  1888.         struct shift_header_type  sh;
  1889.         struct reduce_header_type red;
  1890.  
  1891.         indx = term_state_index[state_no];
  1892.         sh = shift[new_state_element[state_no].shift_number];
  1893.         for (j = 1; j <= sh.size; j++)
  1894.         {
  1895.             symbol = SHIFT_SYMBOL(sh, j);
  1896.             act = SHIFT_ACTION(sh, j);
  1897.             if ((! shift_default_bit) || (act != shiftdf[symbol]))
  1898.             {
  1899.                 i = indx + symbol;
  1900.                 check[i] = symbol;
  1901.  
  1902.                 if (act > (int) num_states)
  1903.                 {
  1904.                     result_act = state_index[act];
  1905.                     la_shift_count++;
  1906.                 }
  1907.                 else if (act > 0)
  1908.                 {
  1909.                     result_act = state_index[act] + num_rules;
  1910.                     shift_count++;
  1911.                 }
  1912.                 else
  1913.                 {
  1914.                     result_act = -act + error_act;
  1915.                     shift_reduce_count++;
  1916.                 }
  1917.  
  1918.                 if (result_act > (MAX_TABLE_SIZE + 1))
  1919.                 {
  1920.                     sprintf(msg_line,
  1921.                         "Table contains look-ahead shift entry that is >"
  1922.                         " %d; Processing stopped.", MAX_TABLE_SIZE + 1);
  1923.                     PRNTERR(msg_line);
  1924.                     return;
  1925.                 }
  1926.  
  1927.                 action[i] = result_act;
  1928.             }
  1929.         }
  1930.  
  1931.         red = new_state_element[state_no].reduce;
  1932.         for (j = 1; j <= red.size; j++)
  1933.         {
  1934.             symbol = REDUCE_SYMBOL(red, j);
  1935.             rule_no = REDUCE_RULE_NO(red, j);
  1936.             i = indx + symbol;
  1937.             check[i] = symbol;
  1938.             action[i] = rule_no;
  1939.             reduce_count++;
  1940.         }
  1941.  
  1942.         rule_no = REDUCE_RULE_NO(red, 0);
  1943.         if (rule_no != error_act)
  1944.             default_count++;
  1945.  
  1946.         check[indx] = DEFAULT_SYMBOL;
  1947.         if (shift_default_bit)
  1948.             action[indx] = state_no;
  1949.         else
  1950.             action[indx] = rule_no;
  1951.     }
  1952.  
  1953.     PRNT("\n\nActions in Compressed Tables:");
  1954.     sprintf(msg_line,"     Number of Shifts: %d",shift_count);
  1955.     PRNT(msg_line);
  1956.  
  1957.     sprintf(msg_line,"     Number of Shift/Reduces: %d",shift_reduce_count);
  1958.     PRNT(msg_line);
  1959.  
  1960.     if (max_la_state > num_states)
  1961.     {
  1962.         sprintf(msg_line,
  1963.                 "     Number of Look-Ahead Shifts: %d",
  1964.                 la_shift_count);
  1965.         PRNT(msg_line);
  1966.     }
  1967.  
  1968.     sprintf(msg_line,"     Number of Gotos: %d",goto_count);
  1969.     PRNT(msg_line);
  1970.  
  1971.     sprintf(msg_line,"     Number of Goto/Reduces: %d",goto_reduce_count);
  1972.     PRNT(msg_line);
  1973.  
  1974.     sprintf(msg_line,"     Number of Reduces: %d",reduce_count);
  1975.     PRNT(msg_line);
  1976.  
  1977.     sprintf(msg_line,"     Number of Defaults: %d",default_count);
  1978.     PRNT(msg_line);
  1979.  
  1980.     /********************************************************************/
  1981.     /* Write Terminal Check Table.                                      */
  1982.     /********************************************************************/
  1983.     k = 0;
  1984.     for (i = 1; i <= term_check_size; i++)
  1985.     {
  1986.         field(check[i], 4);
  1987.         k++;
  1988.         if (k == 18)
  1989.         {
  1990.             *output_ptr++ = '\n';
  1991.             BUFFER_CHECK(systab);
  1992.             k = 0;
  1993.         }
  1994.     }
  1995.  
  1996.     if (k != 0)
  1997.     {
  1998.         *output_ptr++ = '\n';
  1999.         BUFFER_CHECK(systab);
  2000.     }
  2001.  
  2002.     /********************************************************************/
  2003.     /* Write Terminal Action Table.                                      */
  2004.     /********************************************************************/
  2005.     k = 0;
  2006.     for (i = 1; i <= term_action_size; i++)
  2007.     {
  2008.         field(action[i], 6);
  2009.         k++;
  2010.         if (k == 12)
  2011.         {
  2012.             *output_ptr++ = '\n';
  2013.             BUFFER_CHECK(systab);
  2014.             k = 0;
  2015.         }
  2016.     }
  2017.  
  2018.     if (k != 0)
  2019.     {
  2020.         *output_ptr++ = '\n';
  2021.         BUFFER_CHECK(systab);
  2022.     }
  2023.  
  2024.     /********************************************************************/
  2025.     /* If GOTO_DEFAULT is requested, we print out the GOTODEF vector.   */
  2026.     /********************************************************************/
  2027.     if (goto_default_bit)
  2028.     {
  2029.         k = 0;
  2030.         for ALL_NON_TERMINALS(symbol)
  2031.         {
  2032.             act = gotodef[symbol];
  2033.             if (act < 0)
  2034.                 result_act = -act;
  2035.             else if (act == 0)
  2036.                 result_act = error_act;
  2037.             else
  2038.                 result_act = state_index[act] + num_rules;
  2039.  
  2040.             field(result_act, 6);
  2041.             k++;
  2042.             if (k == 12)
  2043.             {
  2044.                 *output_ptr++ = '\n';
  2045.                 BUFFER_CHECK(systab);
  2046.                 k = 0;
  2047.             }
  2048.         }
  2049.  
  2050.         if (k != 0)
  2051.         {
  2052.             *output_ptr++ = '\n';
  2053.             BUFFER_CHECK(systab);
  2054.         }
  2055.     }
  2056.  
  2057. /*********************************************************************/
  2058. /* If SHIFT_DEFAULT is requested, we print out the Default Reduce    */
  2059. /* map, the Shift State map, the Shift Check vector, and the SHIFTDF */
  2060. /* vector.                                                           */
  2061. /*********************************************************************/
  2062.     if (shift_default_bit)
  2063.     {
  2064.         /* Print out header */
  2065.         field(num_terminal_states, 5);
  2066.         field(shift_check_size, 5);
  2067.         *output_ptr++ = '\n';
  2068.  
  2069.         k = 0;
  2070.         for (state_no = 1; state_no <= num_terminal_states; state_no++)
  2071.         {
  2072.             struct reduce_header_type red;
  2073.  
  2074.             red = new_state_element[state_no].reduce;
  2075.             field(REDUCE_RULE_NO(red, 0), 4);
  2076.             k++;
  2077.             if (k == 18)
  2078.             {
  2079.                 *output_ptr++ = '\n';
  2080.                 BUFFER_CHECK(systab);
  2081.                 k = 0;
  2082.             }
  2083.         }
  2084.         if (k != 0)
  2085.         {
  2086.             *output_ptr++ = '\n';
  2087.             BUFFER_CHECK(systab);
  2088.         }
  2089.  
  2090.         /*************************************************************/
  2091.         /* First, check whether or not maximum value in SHIFT_STATE  */
  2092.         /* table exceeds 9999. If so, stop. Otherwise, write out     */
  2093.         /* SHIFT_STATE table.                                        */
  2094.         /*************************************************************/
  2095.         if ((shift_check_size - num_terminals) > 9999)
  2096.         {
  2097.             PRNTERR("SHIFT_STATE map contains > 9999 elements");
  2098.             return;
  2099.         }
  2100.  
  2101.         k = 0;
  2102.         for (state_no = 1; state_no <= num_terminal_states; state_no++)
  2103.         {
  2104.             field(shift_check_index[shift_image[state_no]], 4);
  2105.             k++;
  2106.             if (k == 18)
  2107.             {
  2108.                 *output_ptr++ = '\n';
  2109.                 BUFFER_CHECK(systab);
  2110.                 k = 0;
  2111.             }
  2112.         }
  2113.         if (k != 0)
  2114.         {
  2115.             *output_ptr++ = '\n';
  2116.             BUFFER_CHECK(systab);
  2117.         }
  2118.  
  2119. /*********************************************************************/
  2120. /* Set the Check vector with the symbols in the domain of the shift  */
  2121. /* maps.                                                             */
  2122. /*********************************************************************/
  2123.         for (i = 1; i <= shift_check_size; i++)
  2124.             check[i] = DEFAULT_SYMBOL;
  2125.  
  2126.         for (i = 1; i <= shift_domain_count; i++)
  2127.         {
  2128.             struct shift_header_type sh;
  2129.  
  2130.             indx = shift_check_index[i];
  2131.             sh = shift[real_shift_number[i]];
  2132.             for (j = 1; j <= sh.size; j++)
  2133.             {
  2134.                 symbol = SHIFT_SYMBOL(sh, j);
  2135.                 check[indx + symbol] = symbol;
  2136.             }
  2137.         }
  2138.  
  2139.         k = 0;
  2140.         for (i = 1; i <= shift_check_size; i++)
  2141.         {
  2142.             field(check[i], 4);
  2143.             k++;
  2144.             if (k == 18)
  2145.             {
  2146.                 *output_ptr++ = '\n';
  2147.                 BUFFER_CHECK(systab);
  2148.                 k = 0;
  2149.             }
  2150.         }
  2151.         if (k != 0)
  2152.         {
  2153.             *output_ptr++ = '\n';
  2154.             BUFFER_CHECK(systab);
  2155.         }
  2156.  
  2157.         k = 0;
  2158.         for ALL_TERMINALS(symbol)
  2159.         {
  2160.             act = shiftdf[symbol];
  2161.             if (act < 0)
  2162.                 result_act = -act + error_act;
  2163.             else if (act == 0)
  2164.                 result_act = error_act;
  2165.             else if (act > (int) num_states)
  2166.                 result_act = state_index[act];
  2167.             else
  2168.                 result_act = state_index[act] + num_rules;
  2169.  
  2170.             if (result_act > (MAX_TABLE_SIZE + 1))
  2171.             {
  2172.                 sprintf(msg_line,
  2173.                     "Table contains look-ahead shift entry that is >"
  2174.                     " %d; Processing stopped.", MAX_TABLE_SIZE + 1);
  2175.                 PRNTERR(msg_line);
  2176.                 return;
  2177.             }
  2178.  
  2179.             field(result_act, 6);
  2180.             k++;
  2181.             if (k == 12)
  2182.             {
  2183.                 *output_ptr++ = '\n';
  2184.                 BUFFER_CHECK(systab);
  2185.                 k = 0;
  2186.             }
  2187.         }
  2188.         if (k != 0)
  2189.         {
  2190.             *output_ptr++ = '\n';
  2191.             BUFFER_CHECK(systab);
  2192.         }
  2193.     }
  2194.  
  2195. /*********************************************************************/
  2196. /* We first sort the new state numbers.  A bucket sort technique     */
  2197. /* is used using the ACTION vector as a base to simulate the         */
  2198. /* buckets.  NOTE: the iteration over the buckets is done backward   */
  2199. /* because we also construct a list of the original state numbers    */
  2200. /* that reflects the permutation of the new state numbers.           */
  2201. /* During the backward iteration,  we construct the list as a stack. */
  2202. /*********************************************************************/
  2203.     if (error_maps_bit || states_bit)
  2204.     {
  2205.         int max_indx;
  2206.  
  2207.         max_indx = accept_act - num_rules - 1;
  2208.         for (i = 1; i <= max_indx; i++)
  2209.             action[i] = OMEGA;
  2210.         for ALL_STATES(state_no)
  2211.             action[state_index[state_no]] = state_no;
  2212.  
  2213.         j = num_states + 1;
  2214.         for (i = max_indx; i >= 1; i--)
  2215.         {
  2216.             state_no = action[i];
  2217.             if (state_no != OMEGA)
  2218.             {
  2219.                 j--;
  2220.                 ordered_state[j] = i + num_rules;
  2221.                 state_list[j] = state_no;
  2222.             }
  2223.         }
  2224.     }
  2225.  
  2226.     ffree(check);
  2227.     ffree(action);
  2228.  
  2229.     if (error_maps_bit)
  2230.         process_error_maps();
  2231.  
  2232.     fwrite(output_buffer, sizeof(char),
  2233.            output_ptr - &output_buffer[0], systab);
  2234.  
  2235.     return;
  2236. }
  2237.  
  2238.  
  2239. /*********************************************************************/
  2240. /*                             CMPRSPA:                              */
  2241. /*********************************************************************/
  2242. void cmprspa(void)
  2243. {
  2244.     state_index = Allocate_int_array(max_la_state + 1);
  2245.  
  2246.     ordered_state = Allocate_short_array(max_la_state + 1);
  2247.     symbol_map = Allocate_short_array(num_symbols + 1);
  2248.     state_list = Allocate_short_array(max_la_state + 1);
  2249.     shift_on_error_symbol = Allocate_boolean_array(max_la_state + 1);
  2250.     new_state_element = (struct new_state_type *)
  2251.                         calloc(max_la_state + 1,
  2252.                                sizeof(struct new_state_type));
  2253.     if (new_state_element == NULL)
  2254.         nospace(__FILE__, __LINE__);
  2255.  
  2256.     new_state_element_reduce_nodes = (struct node **)
  2257.                                      calloc(max_la_state + 1,
  2258.                                             sizeof(struct node *));
  2259.     if (new_state_element_reduce_nodes == NULL)
  2260.         nospace(__FILE__, __LINE__);
  2261.  
  2262.     remap_non_terminals();
  2263.     overlap_nt_rows();
  2264.     merge_similar_t_rows();
  2265.     overlay_sim_t_rows();
  2266.     overlap_t_rows();
  2267.     if (c_bit || cpp_bit || java_bit)
  2268.         print_space_parser();
  2269.     else
  2270.         print_tables();
  2271.  
  2272.     return;
  2273. }
  2274.