home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / jikepg12.zip / jikespg / src / ptables.c < prev    next >
C/C++ Source or Header  |  1999-11-04  |  18KB  |  495 lines
  1. /* $Id: ptables.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 "common.h"
  13. #include "header.h"
  14.  
  15. struct action_element
  16. {
  17.     struct action_element *next;
  18.     short count,
  19.           action;
  20. };
  21.  
  22. /****************************************************************************/
  23. /*                            PROCESS_SHIFT_ACTIONS:                        */
  24. /****************************************************************************/
  25. /* The array ACTION_COUNT is used to construct a map from each terminal     */
  26. /* into the set (list) of actions defined on that terminal. A count of the  */
  27. /* number of occurences of each action in the automaton is kept.            */
  28. /* This procedure is invoked with a specific shift map which it processes   */
  29. /* and updates the ACTION_COUNT map accordingly.                            */
  30. /****************************************************************************/
  31. static void process_shift_actions(struct action_element **action_count,
  32.                                   int shift_no)
  33. {
  34.     struct shift_header_type sh;
  35.     struct action_element *q;
  36.  
  37.     int symbol,
  38.         act,
  39.         i;
  40.  
  41.     sh = shift[shift_no];
  42.     for (i = 1; i <= sh.size; i++)
  43.     {
  44.         symbol = SHIFT_SYMBOL(sh, i);
  45.         act = SHIFT_ACTION(sh, i);
  46.         for (q = action_count[symbol]; q != NULL; q = q -> next)
  47.         {
  48.             if (q -> action == act)
  49.                 break;
  50.         }
  51.  
  52.         if (q == NULL) /* new action not yet seen */
  53.         {
  54.             q = (struct action_element *)
  55.                 talloc(sizeof(struct action_element));
  56.             if (q == NULL)
  57.                 nospace(__FILE__, __LINE__);
  58.  
  59.             q -> action = act;
  60.             q -> count = 1;
  61.             q -> next = action_count[symbol];
  62.             action_count[symbol] = q;
  63.         }
  64.         else (q -> count)++;
  65.     }
  66.  
  67.     return;
  68. }
  69.  
  70.  
  71. /****************************************************************************/
  72. /*                            COMPUTE_SHIFT_DEFAULT:                        */
  73. /****************************************************************************/
  74. /* This procedure updates the vector SHIFTDF, indexable by the terminals in */
  75. /* the grammar. Its task is to assign to each element of SHIFTDF, the action*/
  76. /* most frequently defined on the symbol in question.                       */
  77. /****************************************************************************/
  78. static void compute_shift_default(void)
  79. {
  80.     struct action_element **action_count,
  81.                            *q;
  82.  
  83.     int state_no,
  84.         symbol,
  85.         default_action,
  86.         max_count,
  87.         shift_count = 0,
  88.         shift_reduce_count = 0;
  89.  
  90.     /******************************************************************/
  91.     /* Set up a a pool of temporary space.                            */
  92.     /******************************************************************/
  93.     reset_temporary_space();
  94.  
  95.     shiftdf = Allocate_short_array(num_terminals + 1);
  96.  
  97.     action_count = (struct action_element **)
  98.                    calloc(num_terminals + 1,
  99.                           sizeof(struct action_element *));
  100.     if (action_count == NULL)
  101.         nospace(__FILE__, __LINE__);
  102.  
  103.     /*******************************************************************/
  104.     /* For each state, invoke PROCESS_SHIFT_ACTIONS to process the     */
  105.     /* shift map associated with that state.                           */
  106.     /*******************************************************************/
  107.     for ALL_STATES(state_no)
  108.     {
  109.         process_shift_actions(action_count,
  110.                               statset[state_no].shift_number);
  111.     }
  112.  
  113.     for ALL_LA_STATES(state_no)
  114.     {
  115.         process_shift_actions(action_count,
  116.                               lastats[state_no].shift_number);
  117.     }
  118.  
  119.     /*********************************************************************/
  120.     /* We now iterate over the ACTION_COUNT mapping, and for each        */
  121.     /* terminal t, initialize SHIFTDF[t] to the action that is most      */
  122.     /* frequently defined on t.                                          */
  123.     /*********************************************************************/
  124.     for ALL_TERMINALS(symbol)
  125.     {
  126.         max_count = 0;
  127.         default_action = 0;
  128.  
  129.         for (q = action_count[symbol]; q != NULL; q = q -> next)
  130.         {
  131.             if (q -> count > max_count)
  132.             {
  133.                 max_count = q -> count;
  134.                 default_action = q -> action;
  135.             }
  136.         }
  137.  
  138.         shiftdf[symbol] = default_action;
  139.         if (default_action > 0)  /* A state number ? */
  140.             shift_count += max_count;
  141.         else
  142.             shift_reduce_count += max_count;
  143.     }
  144.  
  145.     sprintf(msg_line,
  146.             "Number of Shift entries saved by default: %d",
  147.             shift_count);
  148.     PRNT(msg_line);
  149.  
  150.     sprintf(msg_line,
  151.             "Number of Shift/Reduce entries saved by default: %d",
  152.             shift_reduce_count);
  153.     PRNT(msg_line);
  154.  
  155.     num_shifts -= shift_count;
  156.     num_shift_reduces -= shift_reduce_count;
  157.     num_entries = num_entries - shift_count - shift_reduce_count;
  158.  
  159.     ffree(action_count);
  160.  
  161.     return;
  162. }
  163.  
  164.  
  165. /*****************************************************************************/
  166. /*                             COMPUTE_GOTO_DEFAULT:                         */
  167. /*****************************************************************************/
  168. /*   COMPUTE_GOTO_DEFAULT constructs the vector GOTODEF, which is indexed by */
  169. /* the non-terminals in the grammar. Its task is to assign to each element   */
  170. /* of the array the Action which is most frequently defined on the symbol in */
  171. /* question, and remove all such actions from the state automaton.           */
  172. /*****************************************************************************/
  173. static void compute_goto_default(void)
  174. {
  175.     struct goto_header_type go_to;
  176.  
  177.     struct action_element **action_count,
  178.                            *q;
  179.  
  180.     int state_no,
  181.         symbol,
  182.         default_action,
  183.         act,
  184.         i,
  185.         k,
  186.         max_count,
  187.         goto_count = 0,
  188.         goto_reduce_count = 0;
  189.  
  190.     /******************************************************************/
  191.     /* Set up a a pool of temporary space.                            */
  192.     /******************************************************************/
  193.     reset_temporary_space();
  194.  
  195.     gotodef = Allocate_short_array(num_non_terminals);
  196.     gotodef -= (num_terminals + 1);
  197.  
  198.     action_count = (struct action_element **)
  199.                    calloc(num_non_terminals,
  200.                           sizeof(struct action_element *));
  201.     action_count -= (num_terminals + 1);
  202.     if (action_count == NULL)
  203.         nospace(__FILE__, __LINE__);
  204.  
  205.     /*******************************************************************/
  206.     /* The array ACTION_COUNT is used to construct a map from each     */
  207.     /* non-terminal into the set (list) of actions defined on that     */
  208.     /* non-terminal. A count of how many occurences of each action     */
  209.     /* is also kept.                                                   */
  210.     /* This loop is analoguous to the loop in PROCESS_SHIFT_ACTIONS.   */
  211.     /*******************************************************************/
  212.     for ALL_STATES(state_no)
  213.     {
  214.         go_to = statset[state_no].go_to;
  215.         for (i = 1; i <= go_to.size; i++)
  216.         {
  217.             symbol = GOTO_SYMBOL(go_to, i);
  218.             act = GOTO_ACTION(go_to, i);
  219.             for (q = action_count[symbol]; q != NULL; q = q -> next)
  220.             {
  221.                 if (q -> action == act)
  222.                     break;
  223.             }
  224.  
  225.             if (q == NULL) /* new action not yet seen */
  226.             {
  227.                 q = (struct action_element *)
  228.                     talloc(sizeof(struct action_element));
  229.                 if (q == NULL)
  230.                     nospace(__FILE__, __LINE__);
  231.  
  232.                 q -> action = act;
  233.                 q -> count = 1;
  234.                 q -> next = action_count[symbol];
  235.                 action_count[symbol] = q;
  236.             }
  237.             else (q -> count)++;
  238.         }
  239.     }
  240.  
  241.     /*******************************************************************/
  242.     /* We now iterate over the mapping created above and for each      */
  243.     /* non-terminal A, initialize GOTODEF(A) to the action that is     */
  244.     /* most frequently defined on A.                                   */
  245.     /*******************************************************************/
  246.     for ALL_NON_TERMINALS(symbol)
  247.     {
  248.         max_count = 0;
  249.         default_action = 0;
  250.  
  251.         for (q = action_count[symbol]; q != NULL; q = q -> next)
  252.         {
  253.             if (q -> count > max_count)
  254.             {
  255.                 max_count = q -> count;
  256.                 default_action = q -> action;
  257.             }
  258.         }
  259.  
  260.         gotodef[symbol] = default_action;
  261.         if (default_action > 0) /* A state number? */
  262.             goto_count += max_count;
  263.         else
  264.             goto_reduce_count += max_count;
  265.     }
  266.  
  267.     /***********************************************************************/
  268.     /*   We now iterate over the automaton and eliminate all GOTO actions  */
  269.     /* for which there is a DEFAULT.                                       */
  270.     /***********************************************************************/
  271.     for ALL_STATES(state_no)
  272.     {
  273.         k = 0;
  274.         go_to = statset[state_no].go_to;
  275.         for (i = 1; i <= go_to.size; i++)
  276.         {
  277.             if (gotodef[GOTO_SYMBOL(go_to, i)] != GOTO_ACTION(go_to, i))
  278.             {
  279.                 k++;
  280.                 GOTO_SYMBOL(go_to, k) = GOTO_SYMBOL(go_to, i);
  281.                 GOTO_ACTION(go_to, k) = GOTO_ACTION(go_to, i);
  282.             }
  283.         }
  284.         statset[state_no].go_to.size = k;   /* Readjust size */
  285.     }
  286.  
  287.     sprintf(msg_line,
  288.             "Number of Goto entries saved by default: %d",
  289.             goto_count);
  290.     PRNT(msg_line);
  291.     sprintf(msg_line,
  292.             "Number of Goto/Reduce entries saved by default: %d",
  293.             goto_reduce_count);
  294.     PRNT(msg_line);
  295.  
  296.     num_gotos -= goto_count;
  297.     num_goto_reduces -= goto_reduce_count;
  298.     num_entries = num_entries - goto_count - goto_reduce_count;
  299.  
  300.     action_count += (num_terminals + 1);
  301.     ffree(action_count);
  302.  
  303.     return;
  304. }
  305.  
  306.  
  307. /***********************************************************************/
  308. /*                        PROCESS_TABLES:                              */
  309. /***********************************************************************/
  310. /* Remap symbols, apply transition default actions  and call           */
  311. /* appropriate table compression routine.                              */
  312. /***********************************************************************/
  313. void process_tables(void)
  314. {
  315.     int i,
  316.         j,
  317.         state_no,
  318.         rule_no,
  319.         symbol;
  320.  
  321.     struct goto_header_type   go_to;
  322.     struct shift_header_type  sh;
  323.     struct reduce_header_type red;
  324.  
  325.     /*******************************************************************/
  326.     /*        First, we decrease by 1 the constants NUM_SYMBOLS        */
  327.     /* and NUM_TERMINALS, remove the EMPTY symbol(1) and remap the     */
  328.     /* other symbols beginning at 1.  If default reduction is          */
  329.     /* requested, we assume a special DEFAULT_SYMBOL with number zero. */
  330.     /*******************************************************************/
  331.     eoft_image--;
  332.     accept_image--;
  333.     if (error_maps_bit)
  334.     {
  335.         error_image--;
  336.         eolt_image--;
  337.     }
  338.     num_terminals--;
  339.     num_symbols--;
  340.  
  341.     /***************************************************************/
  342.     /* Remap all the symbols used in GOTO and REDUCE actions.      */
  343.     /* Remap all the symbols used in GD_RANGE.                     */
  344.     /* Remap all the symbols used in the range of SCOPE.           */
  345.     /* Release space trapped by the maps IN_STAT and FIRST.        */
  346.     /***************************************************************/
  347.     for ALL_STATES(state_no)
  348.     {
  349.         go_to = statset[state_no].go_to;
  350.         for (i = 1; i <= go_to.size; i++)
  351.             GOTO_SYMBOL(go_to, i)--;
  352.  
  353.         red = reduce[state_no];
  354.         for (i = 1; i <= red.size; i++)
  355.             REDUCE_SYMBOL(red, i)--;
  356.     }
  357.     for ALL_LA_STATES(state_no)
  358.     {
  359.         red = lastats[state_no].reduce;
  360.         for (i = 1; i <= red.size; i++)
  361.             REDUCE_SYMBOL(red, i)--;
  362.     }
  363.  
  364.     for (i = 1; i <= gotodom_size; i++)
  365.         gd_range[i]--;
  366.  
  367.     for (i = 1; i <= num_scopes; i++)
  368.     {
  369.         scope[i].lhs_symbol--;
  370.         scope[i].look_ahead--;
  371.     }
  372.     for (i = 1; i <= scope_rhs_size; i++)
  373.     {
  374.         if (scope_right_side[i] != 0)
  375.             scope_right_side[i]--;
  376.     }
  377.  
  378.     /*******************************************************************/
  379.     /* Remap all symbols in the domain of the Shift maps.              */
  380.     /*******************************************************************/
  381.     for (i = 1; i <= num_shift_maps; i++)
  382.     {
  383.         sh = shift[i];
  384.         for (j = 1; j <= sh.size; j++)
  385.             SHIFT_SYMBOL(sh, j)--;
  386.     }
  387.  
  388.     /*******************************************************************/
  389.     /* Remap the left-hand side of all the rules.                      */
  390.     /*******************************************************************/
  391.     for ALL_RULES(rule_no)
  392.         rules[rule_no].lhs--;
  393.  
  394.     /*******************************************************************/
  395.     /* Remap the dot symbols in ITEM_TABLE.                            */
  396.     /*******************************************************************/
  397.     if (error_maps_bit)
  398.     {
  399.         for ALL_ITEMS(i)
  400.             item_table[i].symbol--;
  401.     }
  402.  
  403.     /*******************************************************************/
  404.     /* We update the SYMNO map.                                        */
  405.     /*******************************************************************/
  406.     for ALL_SYMBOLS(symbol)
  407.         symno[symbol] = symno[symbol + 1];
  408.  
  409.     /*******************************************************************/
  410.     /* If Goto Default and/or Shift Default were requested, process    */
  411.     /* appropriately.                                                  */
  412.     /*******************************************************************/
  413.     if (shift_default_bit)
  414.         compute_shift_default();
  415.  
  416.     if (goto_default_bit)
  417.         compute_goto_default();
  418.  
  419.     /******************************************************************/
  420.     /* Release the pool of temporary space.                           */
  421.     /******************************************************************/
  422.     free_temporary_space();
  423.  
  424.     /*****************************************************************/
  425.     /* We allocate the necessary structures, open the appropriate    */
  426.     /* output file and call the appropriate compression routine.     */
  427.     /*****************************************************************/
  428.     if (error_maps_bit)
  429.     {
  430.         naction_symbols = (SET_PTR)
  431.                           calloc(num_states + 1,
  432.                                  non_term_set_size * sizeof(BOOLEAN_CELL));
  433.         if (naction_symbols == NULL)
  434.             nospace(__FILE__, __LINE__);
  435.         action_symbols = (SET_PTR)
  436.                          calloc(num_states + 1,
  437.                                 term_set_size * sizeof(BOOLEAN_CELL));
  438.         if (action_symbols == NULL)
  439.             nospace(__FILE__, __LINE__);
  440.     }
  441.  
  442.     output_buffer = (char *) calloc(IOBUFFER_SIZE, sizeof(char));
  443.     if (output_buffer == NULL)
  444.         nospace(__FILE__, __LINE__);
  445.  
  446.     if ((! c_bit) && (! cpp_bit) && (! java_bit))
  447.     {
  448. #if defined(C370) && !defined(CW)
  449.         int size;
  450.  
  451.         size = PARSER_LINE_SIZE ;
  452.         if (record_format != 'F')
  453.             size += 4;
  454.         sprintf(msg_line, "w, recfm=%cB, lrecl=%d",
  455.                           record_format, size);
  456.  
  457.         if((systab = fopen(tab_file, msg_line)) == NULL)
  458. #else
  459.         if((systab = fopen(tab_file, "w")) == NULL)
  460. #endif
  461.         {
  462.             fprintf(stderr,
  463.                     "***ERROR: Table file \"%s\" cannot be opened\n",
  464.                     tab_file);
  465.             exit(12);
  466.         }
  467.     }
  468.  
  469.     if (table_opt == OPTIMIZE_SPACE)
  470.         cmprspa();
  471.     else if (table_opt == OPTIMIZE_TIME)
  472.         cmprtim();
  473.  
  474.     if ((! c_bit) && (! cpp_bit) && (! java_bit))
  475.         fclose(systab);
  476.  
  477. /*********************************************************************/
  478. /* If printing of the states was requested,  print the new mapping   */
  479. /* of the states.                                                    */
  480. /*********************************************************************/
  481.     if (states_bit)
  482.     {
  483.         PR_HEADING;
  484.         fprintf(syslis,
  485.                 "\nMapping of new state numbers into "
  486.                 "original numbers:\n");
  487.         for ALL_STATES(i)
  488.              fprintf(syslis,
  489.                      "\n%5d  ==>>  %5d",ordered_state[i], state_list[i]);
  490.         fprintf(syslis,"\n");
  491.     }
  492.  
  493.     return;
  494. }
  495.