home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / jikepg12.zip / jikespg / src / timetab.c < prev   
Encoding:
C/C++ Source or Header  |  1999-11-04  |  33.9 KB  |  1,005 lines
  1. /* $Id: timetab.c,v 1.2 1999/11/04 14:02:23 shields Exp $ */
  2. /*
  3.  This software is subject to the terms of the IBM Jikes Compiler
  4.  License Agreement available at the following URL:
  5.  http://www.ibm.com/research/jikes.
  6.  Copyright (C) 1983, 1999, International Business Machines Corporation
  7.  and others.  All Rights Reserved.
  8.  You must accept the terms of that agreement to use this software.
  9. */
  10. static char hostfile[] = __FILE__;
  11.  
  12. #include <string.h>
  13. #include "common.h"
  14. #include "header.h"
  15.  
  16. static int   default_saves = 0;
  17. static short default_rule;
  18.  
  19. static BOOLEAN *is_terminal;
  20.  
  21. /*********************************************************************/
  22. /*                            REMAP_SYMBOLS:                         */
  23. /*********************************************************************/
  24. /* We now remap the symbols in the unified Table based on frequency. */
  25. /* We also remap the states based on frequency.                      */
  26. /*********************************************************************/
  27. static void remap_symbols(void)
  28. {
  29.     struct goto_header_type   go_to;
  30.     struct shift_header_type  sh;
  31.     struct reduce_header_type red;
  32.  
  33.     short *frequency_symbol,
  34.           *frequency_count,
  35.           *row_size;
  36.  
  37.     int symbol,
  38.         state_no,
  39.         i,
  40.         j,
  41.         k;
  42.  
  43.     ordered_state = Allocate_short_array(max_la_state + 1);
  44.     symbol_map = Allocate_short_array(num_symbols + 1);
  45.     is_terminal = Allocate_boolean_array(num_symbols + 1);
  46.     frequency_symbol = Allocate_short_array(num_symbols + 1);
  47.     frequency_count = Allocate_short_array(num_symbols + 1);
  48.     row_size = Allocate_short_array(max_la_state + 1);
  49.  
  50.     fprintf(syslis, "\n");
  51.  
  52. /*********************************************************************/
  53. /*     The variable FREQUENCY_SYMBOL is used to hold the symbols     */
  54. /* in the grammar,  and the variable FREQUENCY_COUNT is used         */
  55. /* correspondingly to hold the number of actions defined on each     */
  56. /* symbol.                                                           */
  57. /* ORDERED_STATE and ROW_SIZE are used in a similar fashion for      */
  58. /* states.                                                           */
  59. /*********************************************************************/
  60.     for (i = 1; i <= num_symbols; i++)
  61.     {
  62.         frequency_symbol[i] = i;
  63.         frequency_count[i] = 0;
  64.     }
  65.     for ALL_STATES(state_no)
  66.     {
  67.         ordered_state[state_no] = state_no;
  68.         row_size[state_no] = 0;
  69.         sh = shift[statset[state_no].shift_number];
  70.         for (i = 1; i <= sh.size; i++)
  71.         {
  72.             row_size[state_no]++;
  73.             symbol = SHIFT_SYMBOL(sh, i);
  74.             frequency_count[symbol]++;
  75.         }
  76.  
  77.         go_to =  statset[state_no].go_to;
  78.         for (i = 1; i <= go_to.size; i++)
  79.         {
  80.             row_size[state_no]++;
  81.             symbol = GOTO_SYMBOL(go_to, i);
  82.             frequency_count[symbol]++;
  83.         }
  84.  
  85.         red =  reduce[state_no];
  86.         default_rule = REDUCE_RULE_NO(red, 0);
  87.         for (i = 1; i <= red.size; i++)
  88.         {
  89.             if (REDUCE_RULE_NO(red, i) != default_rule)
  90.             {
  91.                 row_size[state_no]++;
  92.                 symbol = REDUCE_SYMBOL(red, i);
  93.                 frequency_count[symbol]++;
  94.             }
  95.             else
  96.                 default_saves++;
  97.         }
  98.     }
  99.     sprintf(msg_line,
  100.             "Number of Reductions saved by default: %d", default_saves);
  101.     PRNT(msg_line);
  102.  
  103.     for ALL_LA_STATES(state_no)
  104.     {
  105.         ordered_state[state_no] = state_no;
  106.         row_size[state_no] = 0;
  107.         sh = shift[lastats[state_no].shift_number];
  108.         for (i = 1; i <= sh.size; i++)
  109.         {
  110.             row_size[state_no]++;
  111.             symbol = SHIFT_SYMBOL(sh, i);
  112.             frequency_count[symbol]++;
  113.         }
  114.         red =  lastats[state_no].reduce;
  115.         default_rule = REDUCE_RULE_NO(red, 0);
  116.         for (i = 1; i <= red.size; i++)
  117.         {
  118.             if (REDUCE_RULE_NO(red, i) != default_rule)
  119.             {
  120.                 row_size[state_no]++;
  121.                 symbol = REDUCE_SYMBOL(red, i);
  122.                 frequency_count[symbol]++;
  123.             }
  124.             else
  125.                 default_saves++;
  126.         }
  127.     }
  128.  
  129.  /*********************************************************************/
  130.  /*     The non-terminals are sorted in descending order based on the */
  131.  /* number of actions defined on them.                                */
  132.  /*     The terminals are sorted in descending order based on the     */
  133.  /* number of actions defined on them.                                */
  134.  /*********************************************************************/
  135.     sortdes(frequency_symbol, frequency_count,
  136.             1, num_terminals, max_la_state);
  137.  
  138.     sortdes(frequency_symbol, frequency_count,
  139.             num_terminals + 1, num_symbols, max_la_state);
  140.  
  141.     for (last_symbol = num_symbols;
  142.          last_symbol > num_terminals; last_symbol--)
  143.          if (frequency_count[last_symbol] != 0)
  144.              break;
  145.  
  146. /*********************************************************************/
  147. /* We now merge the two sorted arrays of symbols giving precedence to*/
  148. /* the terminals.  Note that we can guarantee that the terminal array*/
  149. /* will be depleted first since it has precedence, and we know that  */
  150. /* there exists at least one non-terminal: the accept non-terminal,  */
  151. /* on which no action is defined.                                    */
  152. /* As we merge the symbols, we keep track of which ones are terminals*/
  153. /* and which ones are non-terminals.  We also keep track of the new  */
  154. /* mapping for the symbols in SYMBOL_MAP.                            */
  155. /*********************************************************************/
  156.     i = 1;
  157.     j = num_terminals + 1;
  158.     k = 0;
  159.     while (i <= num_terminals)
  160.     {
  161.         k++;
  162.         if (frequency_count[i] >= frequency_count[j])
  163.         {
  164.             symbol = frequency_symbol[i];
  165.             is_terminal[k] = TRUE;
  166.             i++;
  167.         }
  168.         else
  169.         {
  170.             symbol = frequency_symbol[j];
  171.             is_terminal[k] = FALSE;
  172.             j++;
  173.         }
  174.         symbol_map[symbol] = k;
  175.     }
  176.     symbol_map[DEFAULT_SYMBOL] = DEFAULT_SYMBOL;
  177.  
  178. /*********************************************************************/
  179. /* Process the remaining non-terminal and useless terminal symbols.  */
  180. /*********************************************************************/
  181.     for (; j <= num_symbols; j++)
  182.     {
  183.         k++;
  184.         symbol = frequency_symbol[j];
  185.         is_terminal[k] = FALSE;
  186.         symbol_map[symbol] = k;
  187.     }
  188.  
  189.     eoft_image = symbol_map[eoft_image];
  190.     if (error_maps_bit)
  191.     {
  192.         error_image = symbol_map[error_image];
  193.         eolt_image = symbol_map[eolt_image];
  194.     }
  195.  
  196. /*********************************************************************/
  197. /*    All symbol entries in the state automaton are updated based on */
  198. /* the new mapping of the symbols.                                   */
  199. /* The states are sorted in descending order based on the number of  */
  200. /* actions defined on them.                                          */
  201. /*********************************************************************/
  202.     for ALL_STATES(state_no)
  203.     {
  204.         go_to =  statset[state_no].go_to;
  205.         for (i = 1; i <= go_to.size; i++)    /* Remap Goto map */
  206.             GOTO_SYMBOL(go_to, i) = symbol_map[GOTO_SYMBOL(go_to, i)];
  207.         red =  reduce[state_no];
  208.         for (i = 1; i <= red.size; i++)
  209.             REDUCE_SYMBOL(red, i) = symbol_map[REDUCE_SYMBOL(red, i)];
  210.     }
  211.  
  212.     for ALL_LA_STATES(state_no)
  213.     {
  214.         red =  lastats[state_no].reduce;
  215.         for (i = 1; i <= red.size; i++)
  216.             REDUCE_SYMBOL(red, i) = symbol_map[REDUCE_SYMBOL(red, i)];
  217.     }
  218.  
  219.     for (i = 1; i <= num_shift_maps; i++)
  220.     {
  221.         sh = shift[i];
  222.         for (j = 1; j <= sh.size; j++)
  223.             SHIFT_SYMBOL(sh, j) = symbol_map[SHIFT_SYMBOL(sh, j)];
  224.     }
  225.  
  226.     sortdes(ordered_state, row_size, 1, max_la_state, num_symbols);
  227.  
  228.     ffree(frequency_symbol);
  229.     ffree(frequency_count);
  230.     ffree(row_size);
  231.  
  232.     return;
  233. }
  234.  
  235.  
  236. /*********************************************************************/
  237. /*                          OVERLAP_TABLES:                          */
  238. /*********************************************************************/
  239. /* We now overlap the State automaton table, or more precisely,  we  */
  240. /* compute the starting position in a vector where each of its rows  */
  241. /* may be placed without clobbering elements in another row.         */
  242. /* The starting positions are stored in the vector STATE_INDEX.      */
  243. /*********************************************************************/
  244. static void overlap_tables(void)
  245. {
  246.     struct goto_header_type  go_to;
  247.     struct shift_header_type  sh;
  248.     struct reduce_header_type red;
  249.  
  250.     short *symbol_list;
  251.  
  252.     int symbol,
  253.         state_no,
  254.         root_symbol,
  255.         max_indx,
  256.         indx,
  257.         percentage,
  258.         k_bytes,
  259.         k,
  260.         i;
  261.  
  262.     long num_bytes;
  263.  
  264.     state_index = Allocate_int_array(max_la_state + 1);
  265.  
  266.     symbol_list = Allocate_short_array(num_symbols + 1);
  267.  
  268.     num_entries -= default_saves;
  269.     increment_size = MAX((num_entries*increment/100), (num_symbols + 1));
  270.     table_size = MIN((num_entries + increment_size), MAX_TABLE_SIZE);
  271.  
  272. /*********************************************************************/
  273. /* Allocate space for table, and initialize the AVAIL_POOL list.     */
  274. /* The variable FIRST_INDEX keeps track of the first element in the  */
  275. /* doubly-linked list, and LAST_ELEMENT keeps track of the last      */
  276. /* element in the list.                                              */
  277. /* The variable MAX_INDX is used to keep track of the maximum        */
  278. /* starting position for a row that has been used.                   */
  279. /*********************************************************************/
  280.     next = Allocate_int_array(table_size + 1);
  281.     previous = Allocate_int_array(table_size + 1);
  282.  
  283.     first_index = 1;
  284.     next[first_index] = first_index + 1; /* Should be constant-folded */
  285.     previous[first_index] = NIL;
  286.     for (indx = 2; indx < (int) table_size; indx++)
  287.     {
  288.         next[indx] = indx + 1;
  289.         previous[indx] = indx - 1;
  290.     }
  291.     last_index = table_size;
  292.     previous[last_index] = last_index - 1;
  293.     next[last_index] = NIL;
  294.  
  295.     max_indx = first_index;
  296.  
  297. /*********************************************************************/
  298. /* We now iterate over all the states in their new sorted order as   */
  299. /* indicated by the variable STATE_NO, and deternime an "overlap"    */
  300. /* position for them.                                                */
  301. /*********************************************************************/
  302.     for (k = 1; k <= (int) max_la_state; k++)
  303.     {
  304.         state_no = ordered_state[k];
  305.  
  306. /*********************************************************************/
  307. /* First, we iterate over all actions defined in STATE_NO, and       */
  308. /* create a set with all the symbols involved.                       */
  309. /*********************************************************************/
  310.         root_symbol = NIL;
  311.         if (state_no > (int) num_states)
  312.         {
  313.             sh = shift[lastats[state_no].shift_number];
  314.             red = lastats[state_no].reduce;
  315.         }
  316.         else
  317.         {
  318.             go_to = statset[state_no].go_to;
  319.             for (i = 1; i <= go_to.size; i++)
  320.             {
  321.                 symbol = GOTO_SYMBOL(go_to, i);
  322.                 symbol_list[symbol] = root_symbol;
  323.                 root_symbol = symbol;
  324.             }
  325.             sh = shift[statset[state_no].shift_number];
  326.             red = reduce[state_no];
  327.         }
  328.  
  329.         for (i = 1; i <= sh.size; i++)
  330.         {
  331.             symbol = SHIFT_SYMBOL(sh, i);
  332.             symbol_list[symbol] = root_symbol;
  333.             root_symbol = symbol;
  334.         }
  335.         symbol_list[0] = root_symbol;
  336.         root_symbol = 0;
  337.  
  338.         default_rule = REDUCE_RULE_NO(red, 0);
  339.         for (i = 1; i <= red.size; i++)
  340.         {
  341.             if (REDUCE_RULE_NO(red, i) != default_rule)
  342.             {
  343.                 symbol = REDUCE_SYMBOL(red, i);
  344.                 symbol_list[symbol] = root_symbol;
  345.                 root_symbol = symbol;
  346.             }
  347.         }
  348.  
  349. /*********************************************************************/
  350. /* INDX is set to the beginning of the list of available slots and   */
  351. /* we try to determine if it might be a valid starting position. If  */
  352. /* not, INDX is moved to the next element, and we repeat the process */
  353. /* until a valid position is found.                                  */
  354. /*********************************************************************/
  355.         indx = first_index;
  356.  
  357. look_for_match_in_table:
  358.         if (indx == NIL)
  359.             indx = table_size + 1;
  360.         if (indx + num_symbols > (int) table_size)
  361.             reallocate();
  362.  
  363.         for (symbol = root_symbol;
  364.              symbol != NIL; symbol = symbol_list[symbol])
  365.         {
  366.             if (next[indx + symbol] == OMEGA)
  367.             {
  368.                 indx = next[indx];
  369.                 goto look_for_match_in_table;
  370.             }
  371.         }
  372.  
  373. /*********************************************************************/
  374. /* At this stage, a position(INDX), was found to overlay the row in  */
  375. /* question.  Remove elements associated with all positions that     */
  376. /* will be taken by row from the doubly-linked list.                 */
  377. /* NOTE that since SYMBOLs start at 1, the first index can never be  */
  378. /* a candidate (==> I = INDX + SYMBOL) in this loop.                 */
  379. /*********************************************************************/
  380.         if (indx > max_indx)
  381.             max_indx = indx;
  382.  
  383.         state_index[state_no] = indx;
  384.  
  385.         for (symbol = root_symbol;
  386.              symbol != NIL; symbol = symbol_list[symbol])
  387.         {
  388.             i = indx + symbol;
  389.             if (first_index == last_index)
  390.                 first_index = NIL;
  391.             else if (i == first_index)
  392.             {
  393.                 first_index = next[first_index];
  394.                 previous[first_index] = NIL;
  395.             }
  396.             else if (i == last_index)
  397.             {
  398.                 last_index = previous[last_index];
  399.                 next[last_index] = NIL;
  400.             }
  401.             else
  402.             {
  403.                 next[previous[i]] = next[i];
  404.                 previous[next[i]] = previous[i];
  405.             }
  406.             next[i] = OMEGA;
  407.         }
  408.     }
  409.  
  410. /*********************************************************************/
  411. /* Update all global counters, and compute ACCEPT_ACTION and         */
  412. /* ERROR_ACTION.                                                     */
  413. /*********************************************************************/
  414.     table_size = max_indx + num_symbols;
  415.     accept_act = max_indx + num_rules + 1;
  416.     error_act = accept_act + 1;
  417.  
  418.     for (action_size = table_size; action_size >= max_indx; action_size--)
  419.          if (next[action_size] == OMEGA)
  420.              break;
  421.  
  422.     printf("\n");
  423.     sprintf(msg_line,"Length of Check table: %ld", table_size);
  424.     PRNT(msg_line);
  425.  
  426.     sprintf(msg_line,"Length of Action table: %ld", action_size);
  427.     PRNT(msg_line);
  428.  
  429.     sprintf(msg_line,
  430.             "Number of entries in Action Table: %d", num_entries);
  431.     PRNT(msg_line);
  432.  
  433.     percentage = ((action_size - num_entries) * 1000) / num_entries;
  434.     sprintf(msg_line, "Percentage of increase: %d.%d%%",
  435.                       percentage / 10, percentage % 10);
  436.     PRNT(msg_line);
  437.  
  438.     if (byte_bit)
  439.     {
  440.         num_bytes = 2 * action_size + table_size;
  441.         if ((! goto_default_bit) && (! nt_check_bit))
  442.         {
  443.             for (; (last_symbol >= 1) && (! is_terminal[last_symbol]);
  444.                 last_symbol--);
  445.         }
  446.         sprintf(msg_line,
  447.                 "Highest symbol in Check Table: %d", last_symbol);
  448.         PRNT(msg_line);
  449.         if (last_symbol > 255)
  450.             num_bytes += table_size;
  451.     }
  452.     else
  453.         num_bytes = 2 * (action_size + table_size);
  454.  
  455.     if (goto_default_bit)
  456.         num_bytes += ((long) 2 * num_symbols);
  457.  
  458.     k_bytes = (num_bytes / 1024) + 1;
  459.  
  460.     sprintf(msg_line,
  461.             "Storage Required for Tables: %ld Bytes, %dK",
  462.             num_bytes, k_bytes);
  463.     PRNT(msg_line);
  464.  
  465.     num_bytes = (long) 4 * num_rules;
  466.     if (byte_bit)
  467.     {
  468.         num_bytes -= num_rules;
  469.         if (num_symbols < 256)
  470.             num_bytes -= num_rules;
  471.     }
  472.     sprintf(msg_line,
  473.             "Storage Required for Rules: %ld Bytes", num_bytes);
  474.     PRNT(msg_line);
  475.  
  476.     return;
  477. }
  478.  
  479.  
  480. /*********************************************************************/
  481. /*                         PRINT_TABLES:                             */
  482. /*********************************************************************/
  483. /* We now write out the tables to the SYSTAB file.                   */
  484. /*********************************************************************/
  485. static void print_tables(void)
  486. {
  487.     int *action,
  488.         *check;
  489.  
  490.     struct goto_header_type   go_to;
  491.     struct shift_header_type  sh;
  492.     struct reduce_header_type red;
  493.  
  494.     int la_shift_count = 0,
  495.         shift_count = 0,
  496.         goto_count = 0,
  497.         default_count = 0,
  498.         reduce_count = 0,
  499.         shift_reduce_count = 0,
  500.         goto_reduce_count = 0;
  501.  
  502.     int indx,
  503.         la_state_offset,
  504.         act,
  505.         result_act,
  506.         i,
  507.         j,
  508.         k,
  509.         symbol,
  510.         state_no;
  511.  
  512.     char *tok;
  513.  
  514.     long offset;
  515.  
  516.     state_list = Allocate_short_array(max_la_state + 1);
  517.  
  518.     check = next;
  519.     action = previous;
  520.  
  521.     offset = error_act;
  522.     if (read_reduce_bit)
  523.         offset += num_rules;
  524.     la_state_offset = offset;
  525.  
  526.     if (offset > (MAX_TABLE_SIZE + 1))
  527.     {
  528.         sprintf(msg_line, "Table contains entries that are > "
  529.                 "%d; Processing stopped.", MAX_TABLE_SIZE + 1);
  530.         PRNTERR(msg_line);
  531.         exit(12);
  532.     }
  533.  
  534. /*********************************************************************/
  535. /* Initialize all unfilled slots with default values.                */
  536. /*********************************************************************/
  537.     indx = first_index;
  538.     for (i = indx; (i != NIL) && (i <= (int) action_size); i = indx)
  539.     {
  540.         indx = next[i];
  541.  
  542.         check[i] = DEFAULT_SYMBOL;
  543.         action[i] = error_act;
  544.     }
  545.     for (i = (int) action_size + 1; i <= (int) table_size; i++)
  546.         check[i] = DEFAULT_SYMBOL;
  547.  
  548. /*********************************************************************/
  549. /* We set the rest of the table with the proper table entries.       */
  550. /*********************************************************************/
  551.     for (state_no = 1; state_no <= (int) max_la_state; state_no++)
  552.     {
  553.         indx = state_index[state_no];
  554.         if (state_no > (int) num_states)
  555.         {
  556.             sh = shift[lastats[state_no].shift_number];
  557.             red = lastats[state_no].reduce;
  558.         }
  559.         else
  560.         {
  561.             go_to = statset[state_no].go_to;
  562.             for (j = 1; j <= go_to.size; j++)
  563.             {
  564.                 symbol = GOTO_SYMBOL(go_to, j);
  565.                 i = indx + symbol;
  566.                 if (goto_default_bit || nt_check_bit)
  567.                     check[i] = symbol;
  568.                 else
  569.                     check[i] = DEFAULT_SYMBOL;
  570.                 act = GOTO_ACTION(go_to, j);
  571.                 if (act > 0)
  572.                 {
  573.                     action[i] = state_index[act] + num_rules;
  574.                     goto_count++;
  575.                 }
  576.                 else
  577.                 {
  578.                     action[i] = -act;
  579.                     goto_reduce_count++;
  580.                 }
  581.             }
  582.             sh = shift[statset[state_no].shift_number];
  583.             red = reduce[state_no];
  584.         }
  585.  
  586.         for (j = 1; j <= sh.size; j++)
  587.         {
  588.             symbol = SHIFT_SYMBOL(sh, j);
  589.             i = indx + symbol;
  590.             check[i] = symbol;
  591.             act = SHIFT_ACTION(sh, j);
  592.             if (act > (int) num_states)
  593.             {
  594.                 result_act = la_state_offset + state_index[act];
  595.                 la_shift_count++;
  596.             }
  597.             else if (act > 0)
  598.             {
  599.                 result_act = state_index[act] + num_rules;
  600.                 shift_count++;
  601.             }
  602.             else
  603.             {
  604.                 result_act = -act + error_act;
  605.                 shift_reduce_count++;
  606.             }
  607.  
  608.             if (result_act > (MAX_TABLE_SIZE + 1))
  609.             {
  610.                 sprintf(msg_line,
  611.                     "Table contains look-ahead shift entry that is >"
  612.                     " %d; Processing stopped.", MAX_TABLE_SIZE + 1);
  613.                 PRNTERR(msg_line);
  614.                 return;
  615.             }
  616.  
  617.             action[i] = result_act;
  618.         }
  619.  
  620. /*********************************************************************/
  621. /*   We now initialize the elements reserved for reduce actions in   */
  622. /* the current state.                                                */
  623. /*********************************************************************/
  624.         default_rule = REDUCE_RULE_NO(red, 0);
  625.         for (j = 1; j <= red.size; j++)
  626.         {
  627.             if (REDUCE_RULE_NO(red, j) != default_rule)
  628.             {
  629.                 symbol = REDUCE_SYMBOL(red, j);
  630.                 i = indx + symbol;
  631.                 check[i] = symbol;
  632.                 act = REDUCE_RULE_NO(red, j);
  633.                 if (rules[act].lhs == accept_image)
  634.                     action[i] = accept_act;
  635.                 else
  636.                     action[i] = act;
  637.                 reduce_count++;
  638.             }
  639.         }
  640.  
  641. /*********************************************************************/
  642. /*   We now initialize the element reserved for the DEFAULT reduce   */
  643. /* action of the current state.  If error maps are requested,  the   */
  644. /* default slot is initialized to the original state number, and the */
  645. /* corresponding element of the DEFAULT_REDUCE array is initialized. */
  646. /* Otherwise it is initialized to the rule number in question.       */
  647. /*********************************************************************/
  648.         i = indx + DEFAULT_SYMBOL;
  649.         check[i] = DEFAULT_SYMBOL;
  650.         act = REDUCE_RULE_NO(red, 0);
  651.         if (act == OMEGA)
  652.             action[i] = error_act;
  653.         else
  654.         {
  655.             action[i] = act;
  656.             default_count++;
  657.         }
  658.     }
  659.  
  660.     PRNT("\n\nActions in Compressed Tables:");
  661.     sprintf(msg_line,"     Number of Shifts: %d",shift_count);
  662.     PRNT(msg_line);
  663.  
  664.     sprintf(msg_line,"     Number of Shift/Reduces: %d",shift_reduce_count);
  665.     PRNT(msg_line);
  666.  
  667.     if (max_la_state > num_states)
  668.     {
  669.         sprintf(msg_line,
  670.                 "     Number of Look-Ahead Shifts: %d", la_shift_count);
  671.         PRNT(msg_line);
  672.     }
  673.  
  674.     sprintf(msg_line,"     Number of Gotos: %d",goto_count);
  675.     PRNT(msg_line);
  676.  
  677.     sprintf(msg_line,
  678.             "     Number of Goto/Reduces: %d",goto_reduce_count);
  679.     PRNT(msg_line);
  680.  
  681.     sprintf(msg_line,"     Number of Reduces: %d",reduce_count);
  682.     PRNT(msg_line);
  683.  
  684.     sprintf(msg_line,"     Number of Defaults: %d",default_count);
  685.     PRNT(msg_line);
  686.  
  687. /*********************************************************************/
  688. /* Prepare Header with proper information, and write it out.         */
  689. /*********************************************************************/
  690.     output_buffer[0] = 'T';
  691.     output_buffer[1] = (goto_default_bit ? '1' : '0');
  692.     output_buffer[2] = (nt_check_bit ? '1' : '0');
  693.     output_buffer[3] = (read_reduce_bit ? '1' : '0');
  694.     output_buffer[4] = (single_productions_bit ? '1' : '0');
  695.     if (default_opt == 0)
  696.         output_buffer[5] = '0';
  697.     else if (default_opt == 1)
  698.         output_buffer[5] = '1';
  699.     else if (default_opt == 2)
  700.         output_buffer[5] = '2';
  701.     else if (default_opt == 3)
  702.         output_buffer[5] = '3';
  703.     else if (default_opt == 4)
  704.         output_buffer[5] = '4';
  705.     else
  706.         output_buffer[5] = '5';
  707.     output_buffer[6] = (rules[1].lhs == accept_image ? '1' : '0');
  708.     output_buffer[7] = (error_maps_bit ? '1' : '0');
  709.     output_buffer[8] = (byte_bit && last_symbol <= 255 ? '1' : '0');
  710.     output_buffer[9] = escape;
  711.  
  712.     output_ptr = &output_buffer[0] + 10;
  713.     field(num_terminals, 5);
  714.     field(num_symbols, 5);
  715.     field(num_rules, 5);
  716.     field(num_states, 5);
  717.     field(table_size, 5);
  718.     field(action_size, 5);
  719.     field(state_index[1] + num_rules, 5);
  720.     field(eoft_image, 5);
  721.     field(accept_act, 5);
  722.     field(error_act, 5);
  723.     field(la_state_offset, 5);
  724.     field(lalr_level, 5);
  725.     *output_ptr++ = '\n';
  726.  
  727.     /*********************************************************/
  728.     /* We write the terminal symbols map.                    */
  729.     /*********************************************************/
  730.     for (symbol = 1; symbol <= num_symbols; symbol++)
  731.     {
  732.         if (is_terminal[symbol_map[symbol]])
  733.         {
  734.             int len;
  735.  
  736.             if (last_terminal < symbol_map[symbol])
  737.                 last_terminal = symbol_map[symbol];
  738.             tok = RETRIEVE_STRING(symbol);
  739.             if (tok[0] == '\n')  /* We're dealing with special symbol?  */
  740.                 tok[0] = escape; /* replace initial marker with escape. */
  741.             len = strlen(tok);
  742.             field(symbol_map[symbol], 4);
  743.             field(len, 4);
  744.             if (len <= 64)
  745.                 strcpy(output_ptr, tok);
  746.             else
  747.             {
  748.                 memcpy(output_ptr, tok, 64);
  749.                 output_ptr += 64;
  750.                 *output_ptr++ = '\n';
  751.                 *output_ptr = '\0';
  752.                 BUFFER_CHECK(systab);
  753.                 tok += 64;
  754.                 for (len = strlen(tok); len > 72; len = strlen(tok))
  755.                 {
  756.                     memcpy(output_ptr, tok, 72);
  757.                     output_ptr += 72;
  758.                     *output_ptr++ = '\n';
  759.                     BUFFER_CHECK(systab);
  760.                     tok += 72;
  761.                 }
  762.                 memcpy(output_ptr, tok, len);
  763.             }
  764.             output_ptr += len;
  765.             *output_ptr++ = '\n';
  766.             BUFFER_CHECK(systab);
  767.         }
  768.     }
  769.  
  770.     /*********************************************************/
  771.     /* We write the non-terminal symbols map.                */
  772.     /*********************************************************/
  773.     for (symbol = 1; symbol <= num_symbols; symbol++)
  774.     {
  775.         if (! is_terminal[symbol_map[symbol]])
  776.         {
  777.             int len;
  778.  
  779.             if (last_non_terminal < symbol_map[symbol])
  780.                 last_non_terminal = symbol_map[symbol];
  781.             tok = RETRIEVE_STRING(symbol);
  782.             if (tok[0] == '\n')  /* we're dealing with special symbol?  */
  783.                 tok[0] = escape; /* replace initial marker with escape. */
  784.             len = strlen(tok);
  785.             field(symbol_map[symbol], 4);
  786.             field(len, 4);
  787.             if (len <= 64)
  788.                 strcpy(output_ptr, tok);
  789.             else
  790.             {
  791.                 memcpy(output_ptr, tok, 64);
  792.                 output_ptr += 64;
  793.                 *output_ptr++ = '\n';
  794.                 BUFFER_CHECK(systab);
  795.                 tok += 64;
  796.                 for (len = strlen(tok); len > 72; len = strlen(tok))
  797.                 {
  798.                     memcpy(output_ptr, tok, 72);
  799.                     output_ptr += 72;
  800.                     *output_ptr++ = '\n';
  801.                     BUFFER_CHECK(systab);
  802.                     tok += 72;
  803.                 }
  804.                 memcpy(output_ptr, tok, len);
  805.             }
  806.             output_ptr += len;
  807.             *output_ptr++ = '\n';
  808.             BUFFER_CHECK(systab);
  809.         }
  810.     }
  811.  
  812.     /*********************************************************************/
  813.     /* Write size of right hand side of rules followed by CHECK table.   */
  814.     /*********************************************************************/
  815.     k = 0;
  816.     for (i = 1; i <= num_rules; i++)
  817.     {
  818.         field(RHS_SIZE(i), 4);
  819.         k++;
  820.         if (k == 18)
  821.         {
  822.             *output_ptr++ = '\n';
  823.             BUFFER_CHECK(systab);
  824.             k = 0;
  825.         }
  826.     }
  827.  
  828.     for (i = 1; i <= (int) table_size; i++)
  829.     {
  830.         field(check[i], 4);
  831.         k++;
  832.         if (k == 18)
  833.         {
  834.             *output_ptr++ = '\n';
  835.             BUFFER_CHECK(systab);
  836.             k = 0;
  837.         }
  838.     }
  839.  
  840.     if (k != 0)
  841.     {
  842.         *output_ptr++ = '\n';
  843.         BUFFER_CHECK(systab);
  844.     }
  845.  
  846.     /*********************************************************************/
  847.     /* Write left hand side symbol of rules followed by ACTION table.    */
  848.     /*********************************************************************/
  849.     k = 0;
  850.     for (i = 1; i <= num_rules; i++)
  851.     {
  852.         field(symbol_map[rules[i].lhs], 6);
  853.         k++;
  854.         if (k == 12)
  855.         {
  856.             *output_ptr++ = '\n';
  857.             BUFFER_CHECK(systab);
  858.             k = 0;
  859.         }
  860.     }
  861.  
  862.     for (i = 1; i <= (int) action_size; i++)
  863.     {
  864.         field(action[i], 6);
  865.         k++;
  866.         if (k == 12)
  867.         {
  868.             *output_ptr++ = '\n';
  869.             BUFFER_CHECK(systab);
  870.             k = 0;
  871.         }
  872.     }
  873.  
  874.     if (k != 0)
  875.     {
  876.         *output_ptr++ = '\n';
  877.         BUFFER_CHECK(systab);
  878.     }
  879.  
  880.     /******************************************************************/
  881.     /* If GOTO_DEFAULT is requested, we print out the GOTODEF vector  */
  882.     /* after rearranging its elements based on the new ordering of the*/
  883.     /* symbols.  The array TEMP is used to hold the GOTODEF values.   */
  884.     /******************************************************************/
  885.     if (goto_default_bit)
  886.     {
  887.         short *default_map;
  888.  
  889.         default_map = Allocate_short_array(num_symbols + 1);
  890.  
  891.         for (i = 0; i <= num_symbols; i++)
  892.            default_map[i] = error_act;
  893.  
  894.         for ALL_NON_TERMINALS(symbol)
  895.         {
  896.             act = gotodef[symbol];
  897.             if (act < 0)
  898.                 result_act = -act;
  899.             else if (act > 0)
  900.                 result_act = state_index[act] + num_rules;
  901.             else
  902.                 result_act = error_act;
  903.             default_map[symbol_map[symbol]] = result_act;
  904.         }
  905.  
  906.         k = 0;
  907.         for (symbol = 1; symbol <= num_symbols; symbol++)
  908.         {
  909.             k++;
  910.             field(default_map[symbol], 6);
  911.             if (k == 12)
  912.             {
  913.                 *output_ptr++ = '\n';
  914.                 BUFFER_CHECK(systab);
  915.                 k = 0;
  916.             }
  917.         }
  918.  
  919.         if (k != 0)
  920.         {
  921.             *output_ptr++ = '\n';
  922.             BUFFER_CHECK(systab);
  923.         }
  924.     }
  925.  
  926. /*********************************************************************/
  927. /* We first sort the new state numbers.  A bucket sort technique     */
  928. /* is used using the ACTION vector as a base to simulate the         */
  929. /* buckets.  NOTE: the iteration over the buckets is done backward   */
  930. /* because we also construct a list of the original state numbers    */
  931. /* that reflects the permutation of the new state numbers.           */
  932. /* During the backward iteration,  we construct the list as a stack. */
  933. /*********************************************************************/
  934.     if (error_maps_bit || states_bit)
  935.     {
  936.         int max_indx;
  937.  
  938.         max_indx = accept_act - num_rules - 1;
  939.         for (i = 1; i <= max_indx; i++)
  940.             action[i] = OMEGA;
  941.         for ALL_STATES(state_no)
  942.             action[state_index[state_no]] = state_no;
  943.  
  944.         j = num_states + 1;
  945.         for (i = max_indx; i >= 1; i--)
  946.         {
  947.             state_no = action[i];
  948.             if (state_no != OMEGA)
  949.             {
  950.                 j--;
  951.                 ordered_state[j] = i + num_rules;
  952.                 state_list[j] = state_no;
  953.             }
  954.         }
  955.     }
  956.  
  957.     ffree(next);
  958.     ffree(previous);
  959.  
  960. /*********************************************************************/
  961. /* If ERROR_MAPS are requested, we print them out in the following   */
  962. /* order:                                                            */
  963. /*                                                                   */
  964. /*    1) The FOLLOW map (NEWFOLL)                                    */
  965. /*    2) The SORTED_STATE vector                                     */
  966. /*    3) The ORIGINAL_STATE vector                                   */
  967. /*    4) The map from states into valid symbols on which actions are */
  968. /*       defined within the state in question: ACTION_SYMBOLS        */
  969. /*    5) The map from each symbol into the set of states that can    */
  970. /*       possibly be reached after a transition on the symbol in     */
  971. /*       question: TRANSITION_STATES                                 */
  972. /*                                                                   */
  973. /*********************************************************************/
  974.     if (error_maps_bit)
  975.         process_error_maps();
  976.  
  977.     fwrite(output_buffer, sizeof(char),
  978.            output_ptr - &output_buffer[0], systab);
  979.  
  980.     return;
  981. }
  982.  
  983.  
  984. /*********************************************************************/
  985. /*                            CMPRTIM:                               */
  986. /*********************************************************************/
  987. /* In this routine we compress the State tables and write them out   */
  988. /* to a file.  The emphasis here is in generating tables that allow  */
  989. /* fast access. The terminal and non-terminal tables are compressed  */
  990. /* together, so as to achieve maximum speed efficiency.              */
  991. /* Otherwise, the compression technique used in this table is        */
  992. /* analoguous to the technique used in the routine CMPRSPA.          */
  993. /*********************************************************************/
  994. void cmprtim(void)
  995. {
  996.     remap_symbols();
  997.     overlap_tables();
  998.     if (c_bit || cpp_bit || java_bit)
  999.         print_time_parser();
  1000.     else
  1001.         print_tables();
  1002.  
  1003.     return;
  1004. }
  1005.