home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / jikepg12.zip / jikespg / src / remsp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-11-04  |  65.1 KB  |  1,576 lines
  1. /* $Id: remsp.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 "reduce.h"
  14. #include "header.h"
  15.  
  16. #define IS_SP_RHS(symbol)   (sp_rules[symbol] != NIL)
  17. #define IS_SP_RULE(rule_no) (rule_list[rule_no] != OMEGA)
  18.  
  19. static int max_sp_state;
  20.  
  21. static struct action_element
  22. {
  23.     struct action_element *next;
  24.     short symbol,
  25.           action;
  26. } **new_action;
  27. static struct action_element *action_element_pool = NULL;
  28.  
  29. static struct update_action_element
  30. {
  31.     struct update_action_element *next;
  32.     short symbol,
  33.           action,
  34.           state;
  35. } **update_action;
  36.  
  37. static struct sp_state_element
  38. {
  39.     struct sp_state_element *next,
  40.                             *link;
  41.     struct action_element   *action_root;
  42.     struct node             *rule_root,
  43.                             *complete_items;
  44.     short                    state_number,
  45.                              rule_count,
  46.                              action_count;
  47. } **sp_table;
  48. static struct sp_state_element *sp_state_root;
  49.  
  50. static short *sp_rules,
  51.              *stack,
  52.              *index_of,
  53.              *next_rule,
  54.              *rule_list,
  55.  
  56.              **sp_action;
  57.  
  58. static BOOLEAN *is_conflict_symbol;
  59.  
  60. static SET_PTR look_ahead;
  61.  
  62. static int top,
  63.            symbol_root,
  64.            rule_root;
  65.  
  66. /**********************************************************************/
  67. /*                        ALLOCATE_ACTION_ELEMENT:                    */
  68. /**********************************************************************/
  69. /* This function first tries to recycle an action_element node from a */
  70. /* free list. If the list is empty a new node is allocated from       */
  71. /* temporary storage.                                                 */
  72. /**********************************************************************/
  73. static struct action_element* allocate_action_element(void)
  74. {
  75.     struct action_element *p;
  76.  
  77.     p = action_element_pool;
  78.     if (p != NULL)
  79.         action_element_pool = p -> next;
  80.     else
  81.     {
  82.         p = (struct action_element *)
  83.             talloc(sizeof(struct action_element));
  84.         if (p == (struct action_element *) NULL)
  85.             nospace(__FILE__, __LINE__);
  86.     }
  87.  
  88.     return p;
  89. }
  90.  
  91.  
  92. /**********************************************************************/
  93. /*                          FREE_ACTION_ELEMENTS:                     */
  94. /**********************************************************************/
  95. /* This routine returns a list of action_element structures to the    */
  96. /* free list.                                                         */
  97. /**********************************************************************/
  98. static void free_action_elements(struct action_element *head,
  99.                                  struct action_element *tail)
  100. {
  101.     tail -> next = action_element_pool;
  102.     action_element_pool = head;
  103.  
  104.     return;
  105. }
  106.  
  107.  
  108. /**********************************************************************/
  109. /*                             COMPUTE_SP_MAP:                        */
  110. /**********************************************************************/
  111. /* Compute_sp_map is an instantiation of the digraph algorithm. It    */
  112. /* is invoked repeatedly by remove_single_productions to:             */
  113. /*                                                                    */
  114. /*   1) Partially order the right-hand side of all the single         */
  115. /*      productions (SP) into a list [A1, A2, A3, ..., An]            */
  116. /*      such that if Ai -> Aj then i < j.                             */
  117. /*                                                                    */
  118. /*   2) As a side effect, it uses the ordering above to order all     */
  119. /*      the SP rules.                                                 */
  120. /*                                                                    */
  121. /**********************************************************************/
  122. static void compute_sp_map(int symbol)
  123. {
  124.     int indx;
  125.     int i,
  126.         lhs_symbol,
  127.         rule_no;
  128.  
  129.     stack[++top] = symbol;
  130.     indx = top;
  131.     index_of[symbol] = indx;
  132.  
  133. /**********************************************************************/
  134. /* In this instantiation of the digraph algorithm, two symbols (A, B) */
  135. /* are related if  A -> B  is a SP and A is the right-hand side of    */
  136. /* some other SP rule.                                                */
  137. /**********************************************************************/
  138.     for (rule_no = sp_rules[symbol];
  139.          rule_no != NIL; rule_no = next_rule[rule_no])
  140.     {
  141.         lhs_symbol = rules[rule_no].lhs;
  142.         if (IS_SP_RHS(lhs_symbol))
  143.         {
  144.             if (index_of[lhs_symbol] == OMEGA)
  145.                 compute_sp_map(lhs_symbol);
  146.  
  147.             index_of[symbol] = MIN(index_of[symbol],
  148.                                    index_of[lhs_symbol]);
  149.         }
  150.     }
  151.  
  152. /**********************************************************************/
  153. /* If the index of symbol is the same index it started with then      */
  154. /* symbol if the root of a SCC...                                     */
  155. /**********************************************************************/
  156.     if (index_of[symbol] == indx)
  157.     {
  158.         /**************************************************************/
  159.         /* If symbol is on top of the stack then it is the only       */
  160.         /* symbol in its SCC (thus it is not part of a cycle).        */
  161.         /* Note that since remove_single_productions is only invoked  */
  162.         /* when the input grammar is conflict-free, the graph of      */
  163.         /* the single productions will never contain any cycle.       */
  164.         /* Thus, this test will always succeed and all single         */
  165.         /* productions associated with the symbol being processed     */
  166.         /* are added to the list of SP rules here...                  */
  167.         /**************************************************************/
  168.         if (stack[top] == symbol)
  169.         {
  170.             for (rule_no = sp_rules[symbol];
  171.                  rule_no != NIL; rule_no = next_rule[rule_no])
  172.             {
  173.                 if (rule_root == NIL)
  174.                     rule_list[rule_no] = rule_no;
  175.                 else
  176.                 {
  177.                     rule_list[rule_no] = rule_list[rule_root];
  178.                     rule_list[rule_root] = rule_no;
  179.                 }
  180.                 rule_root = rule_no;
  181.             }
  182.         }
  183.  
  184.         /**************************************************************/
  185.         /* As all SCC contains exactly one symbol (as explained above)*/
  186.         /* this loop will always execute exactly once.                */
  187.         /**************************************************************/
  188.         do
  189.         {
  190.             i = stack[top--];
  191.             index_of[i] = INFINITY;
  192.         } while(i != symbol);
  193.     }
  194.  
  195.     return;
  196. }
  197.  
  198.  
  199. /**********************************************************************/
  200. /*                         COMPUTE_SP_ACTION:                         */
  201. /**********************************************************************/
  202. /* When the parser enters STATE_NO and it is processing SYMBOL, its   */
  203. /* next move is ACTION. Given these 3 parameters, compute_sp_action   */
  204. /* computes the set of reduce actions that may be executed after      */
  205. /* SYMBOL is shifted in STATE_NO.                                     */
  206. /*                                                                    */
  207. /* NOTE that this algorithm works only for the LALR(1) case. When the */
  208. /* transition on SYMBOL is a lookahead-shift, indicating that the     */
  209. /* parser requires extra lookahead on a particular symbol, the set of */
  210. /* reduce actions for that symbol is calculated as the empty set.     */
  211. /**********************************************************************/
  212. static void compute_sp_action(short state_no, short symbol, short action)
  213. {
  214.     struct goto_header_type go_to;
  215.  
  216.     struct node *item_ptr;
  217.     int item_no,
  218.         rule_no,
  219.         lhs_symbol,
  220.         i,
  221.         k;
  222.  
  223.     BOOLEAN end_node;
  224.  
  225.     struct node *p;
  226.  
  227.     go_to = statset[state_no].go_to;
  228.  
  229.     if (sp_action[symbol] == NULL)
  230.         sp_action[symbol] = Allocate_short_array(num_terminals + 1);
  231.  
  232.     for ALL_TERMINALS(i) /* initialize sp_action to the empty map */
  233.         sp_action[symbol][i] = OMEGA;
  234.  
  235. /**********************************************************************/
  236. /* Note that before this routine is invoked, the global vector        */
  237. /* index_of identifies the index of each symbol in the goto map of    */
  238. /* state_no.                                                          */
  239. /**********************************************************************/
  240.     if (is_conflict_symbol[symbol])             /* do nothing */
  241.         ;
  242.     else if (action > 0) /* transition action (shift or goto) */
  243.     {
  244.         for (item_ptr = statset[action].complete_items;
  245.              item_ptr != NULL; item_ptr = item_ptr -> next)
  246.         {
  247.             item_no = item_ptr -> value;
  248.             rule_no = item_table[item_no].rule_number;
  249.             lhs_symbol = rules[rule_no].lhs;
  250.             if (RHS_SIZE(rule_no) == 1 && lhs_symbol != accept_image)
  251.             {
  252.                 if (slr_bit)
  253.                 {
  254.                     ASSIGN_SET(look_ahead, 0, follow, lhs_symbol);
  255.                 }
  256.                 else
  257.                 {
  258.                     i = index_of[lhs_symbol];
  259.                     k = GOTO_LAPTR(go_to, i);
  260.                     if (la_index[k] == OMEGA)
  261.                     {
  262.                         int stack_top = 0;
  263.                         la_traverse(state_no, i, &stack_top);
  264.                     }
  265.                     ASSIGN_SET(look_ahead, 0, la_set, k);
  266.                 }
  267.                 RESET_BIT(look_ahead, empty); /* empty not valid look-ahead */
  268.  
  269.                 for ALL_TERMINALS(i)
  270.                 {
  271.                     if (IS_ELEMENT(look_ahead, i))
  272.                         sp_action[symbol][i] = rule_no;
  273.                 }
  274.             }
  275.         }
  276.  
  277.         /**************************************************************/
  278.         /* Remove all lookahead symbols on which conflicts were       */
  279.         /* detected from consideration.                               */
  280.         /**************************************************************/
  281.         for (end_node = ((p = conflict_symbols[action]) == NULL);
  282.              ! end_node; end_node = (p == conflict_symbols[action]))
  283.         {
  284.             p = p -> next;
  285.             sp_action[symbol][p -> value] = OMEGA;
  286.         }
  287.     }
  288.     else /* read-reduce action */
  289.     {
  290.         rule_no = -action;
  291.         if (RHS_SIZE(rule_no) == 1)
  292.         {
  293.             lhs_symbol = rules[rule_no].lhs;
  294.  
  295.             if (slr_bit)
  296.             {
  297.                 ASSIGN_SET(look_ahead, 0, follow, lhs_symbol);
  298.             }
  299.             else
  300.             {
  301.                 i = index_of[lhs_symbol];
  302.                 k = GOTO_LAPTR(go_to, i);
  303.                 if (la_index[k] == OMEGA)
  304.                 {
  305.                     int stack_top = 0;
  306.                     la_traverse(state_no, i, &stack_top);
  307.                 }
  308.                 ASSIGN_SET(look_ahead, 0, la_set, k);
  309.             }
  310.             RESET_BIT(look_ahead, empty); /* empty not valid look-ahead */
  311.  
  312.             for ALL_TERMINALS(i)
  313.             {
  314.                 if (IS_ELEMENT(look_ahead, i))
  315.                     sp_action[symbol][i] = rule_no;
  316.             }
  317.         }
  318.     }
  319.  
  320.     return;
  321. }
  322.  
  323.  
  324. /**********************************************************************/
  325. /*                           SP_DEFAULT_ACTION:                       */
  326. /**********************************************************************/
  327. /* Sp_default_action takes as parameter a state, state_no and a rule, */
  328. /* rule_no that may be reduce when the parser enters state_no.        */
  329. /* Sp_default_action tries to determine the highest rule that may be  */
  330. /* reached via a sequence of SP reductions.                           */
  331. /**********************************************************************/
  332. static short sp_default_action(short state_no, short rule_no)
  333. {
  334.     struct reduce_header_type red;
  335.     struct goto_header_type go_to;
  336.  
  337.     int lhs_symbol,
  338.         action,
  339.         i;
  340.  
  341.     go_to = statset[state_no].go_to;
  342.  
  343. /**********************************************************************/
  344. /* While the rule we have at hand is a single production, ...         */
  345. /**********************************************************************/
  346.     while (IS_SP_RULE(rule_no))
  347.     {
  348.         lhs_symbol = rules[rule_no].lhs;
  349.         for (i = 1; GOTO_SYMBOL(go_to, i) != lhs_symbol; i++)
  350.             ;
  351.  
  352.         action = GOTO_ACTION(go_to, i);
  353.         if (action < 0) /* goto-reduce action? */
  354.         {
  355.             action = -action;
  356.             if (RHS_SIZE(action) != 1)
  357.                 break;
  358.  
  359.             rule_no = action;
  360.         }
  361.         else
  362.         {
  363.             int best_rule = OMEGA;
  364.  
  365.         /**************************************************************/
  366.         /* Enter the state action and look for preferably a SP rule   */
  367.         /* or some rule with right-hand size 1.                       */
  368.         /**************************************************************/
  369.             red = reduce[action];
  370.             for (i = 1; i <= red.size; i++)
  371.             {
  372.                 action = REDUCE_RULE_NO(red, i);
  373.                 if (IS_SP_RULE(action))
  374.                 {
  375.                     best_rule = action;
  376.                     break;
  377.                 }
  378.                 if (RHS_SIZE(action) == 1)
  379.                     best_rule = action;
  380.             }
  381.             if (best_rule == OMEGA)
  382.                 break;
  383.  
  384.             rule_no = best_rule;
  385.         }
  386.     }
  387.  
  388.     return rule_no;
  389. }
  390.  
  391. /**********************************************************************/
  392. /*                              SP_NT_ACTION:                         */
  393. /**********************************************************************/
  394. /* This routine takes as parameter a state, state_no, a nonterminal,  */
  395. /* lhs_symbol (that is the right-hand side of a SP or a rule with     */
  396. /* right-hand size 1, but not identified as a SP) on which there is   */
  397. /* a transition in state_no and a lookahead symbol la_symbol that may */
  398. /* be processed after taking the transition. It returns the reduce    */
  399. /* action that follows the transition if an action on la_symbol is    */
  400. /* found, otherwise it returns the most suitable default action.      */
  401. /**********************************************************************/
  402. static short sp_nt_action(short state_no, short lhs_symbol, short la_symbol)
  403. {
  404.     struct reduce_header_type red;
  405.     struct goto_header_type go_to;
  406.  
  407.     int action,
  408.         rule_no,
  409.         i;
  410.  
  411.     go_to = statset[state_no].go_to;
  412.     for (i = 1; GOTO_SYMBOL(go_to, i) != lhs_symbol; i++)
  413.         ;
  414.  
  415.     action = GOTO_ACTION(go_to, i);
  416.     if (action < 0)
  417.         action = -action;
  418.     else
  419.     {
  420.         red = reduce[action];
  421.         action = OMEGA;
  422.         for (i = 1; i <= red.size; i++)
  423.         {
  424.             rule_no = REDUCE_RULE_NO(red, i);
  425.             if (REDUCE_SYMBOL(red, i) == la_symbol)
  426.             {
  427.                 action = rule_no;
  428.                 break;
  429.             }
  430.             else if (action == OMEGA && IS_SP_RULE(rule_no))
  431.                 action = rule_no;
  432.         }
  433.     }
  434.  
  435.     return action;
  436. }
  437.  
  438.  
  439. /**********************************************************************/
  440. /*                       GREATEST_COMMON_ANCESTOR:                    */
  441. /**********************************************************************/
  442. /* Let BASE_RULE be a rule  A -> X.  The item [A -> .X] is in STATE1  */
  443. /* and STATE2.  After shifting on X (in STATE1 and STATE2), if the    */
  444. /* lookahead is LA_SYMBOL then BASE_RULE is reduced. In STATE1, a     */
  445. /* sequence of single-production reductions is executed ending with   */
  446. /* a reduction of RULE1. In STATE2, a sequence of single-productions  */
  447. /* is also executed ending with RULE2.                                */
  448. /* The goal of this function is to find the greatest ancestor of      */
  449. /* BASE_RULE that is also a descendant of both RULE1 and RULE2.       */
  450. /**********************************************************************/
  451. static short greatest_common_ancestor(short base_rule, short la_symbol,
  452.                                       short state1, short rule1,
  453.                                       short state2, short rule2)
  454. {
  455.     int lhs_symbol,
  456.         act1,
  457.         act2,
  458.         rule_no;
  459.  
  460.     act1 = base_rule;
  461.     act2 = base_rule;
  462.     while (act1 == act2)
  463.     {
  464.         rule_no = act1;
  465.         if (act1 == rule1 || act2 == rule2)
  466.             break;
  467.  
  468.         lhs_symbol = rules[rule_no].lhs;
  469.  
  470.         act1 = sp_nt_action(state1, lhs_symbol, la_symbol);
  471.         act2 = sp_nt_action(state2, lhs_symbol, la_symbol);
  472.     }
  473.  
  474.     return rule_no;
  475. }
  476.  
  477.  
  478. /**********************************************************************/
  479. /*                       COMPUTE_UPDATE_ACTION:                       */
  480. /**********************************************************************/
  481. /* In SOURCE_STATE there is a transition on SYMBOL into STATE_NO.     */
  482. /* SYMBOL is the right-hand side of a SP rule and the global map      */
  483. /* sp_action[SYMBOL] yields a set of update reduce actions that may   */
  484. /* follow the transition on SYMBOL into STATE_NO.                     */
  485. /**********************************************************************/
  486. static void compute_update_actions(short source_state,
  487.                                    short state_no, short symbol)
  488. {
  489.     int i,
  490.         rule_no;
  491.  
  492.     struct reduce_header_type red;
  493.     struct update_action_element *p;
  494.  
  495.     red = reduce[state_no];
  496.  
  497.     for (i = 1; i <= red.size; i++)
  498.     {
  499.         if (IS_SP_RULE(REDUCE_RULE_NO(red, i)))
  500.         {
  501.             rule_no = sp_action[symbol][REDUCE_SYMBOL(red, i)];
  502.             if (rule_no == OMEGA)
  503.                 rule_no = sp_default_action(source_state,
  504.                                             REDUCE_RULE_NO(red, i));
  505.  
  506.         /**************************************************************/
  507.         /* Lookup the update map to see if a previous update was made */
  508.         /* in STATE_NO on SYMBOL...                                   */
  509.         /**************************************************************/
  510.             for (p = update_action[state_no]; p != NULL; p = p -> next)
  511.             {
  512.                 if (p -> symbol == REDUCE_SYMBOL(red, i))
  513.                     break;
  514.             }
  515.  
  516.         /**************************************************************/
  517.         /* If no previous update action was defined on STATE_NO and   */
  518.         /* SYMBOL, simply add it. Otherwise, chose as the greatest    */
  519.         /* common ancestor of the initial reduce action and the two   */
  520.         /* contending updates as the update action.                   */
  521.         /**************************************************************/
  522.             if (p == NULL)
  523.             {
  524.                 p = (struct update_action_element *)
  525.                     talloc(sizeof(struct update_action_element));
  526.                 if (p == (struct update_action_element *) NULL)
  527.                     nospace(__FILE__, __LINE__);
  528.                 p -> next = update_action[state_no];
  529.                 update_action[state_no] = p;
  530.  
  531.                 p -> symbol = REDUCE_SYMBOL(red, i);
  532.                 p -> action = rule_no;
  533.                 p -> state  = source_state;
  534.             }
  535.             else if ((rule_no != p -> action) &&
  536.                      (p -> action != REDUCE_RULE_NO(red, i)))
  537.             {
  538.                 p -> action = greatest_common_ancestor(REDUCE_RULE_NO(red, i),
  539.                                                        REDUCE_SYMBOL(red, i),
  540.                                                        source_state, rule_no,
  541.                                                        p -> state,
  542.                                                        p -> action);
  543.             }
  544.         }
  545.     }
  546.  
  547.     return;
  548. }
  549.  
  550.  
  551. /**********************************************************************/
  552. /*                             SP_STATE_MAP:                          */
  553. /**********************************************************************/
  554. /* Sp_state_map is invoked to create a new state using the reduce map */
  555. /* sp_symbol[SYMBOL]. The new state will be entered via a transition  */
  556. /* on SYMBOL which is the right-hand side of the SP rule of which     */
  557. /* ITEM_NO is the final item.                                         */
  558. /*                                                                    */
  559. /* RULE_HEAD is the root of a list of rules in the global vector      */
  560. /* next_rule.  This list of rules identifies the range of the reduce  */
  561. /* map sp_symbol[SYMBOL]. The value SP_RULE_COUNT is the number of    */
  562. /* rules in the list. The value SP_ACTION_COUNT is the number of      */
  563. /* actions in the map sp_symbol[SYMBOL].                              */
  564. /**********************************************************************/
  565. static short sp_state_map(int rule_head, short item_no,
  566.                           short sp_rule_count,
  567.                           short sp_action_count, short symbol)
  568. {
  569.     struct sp_state_element *state;
  570.     struct node             *p;
  571.  
  572.     int rule_no,
  573.         i;
  574.  
  575.     BOOLEAN no_overwrite;
  576.  
  577.     unsigned long hash_address;
  578.  
  579.     /******************************************************************/
  580.     /* These new SP states are defined by their reduce maps. Hash the */
  581.     /* reduce map based on the set of rules in its range - simply add */
  582.     /* them up and reduce modulo STATE_TABLE_SIZE.                    */
  583.     /******************************************************************/
  584.     hash_address = 0;
  585.     for (rule_no = rule_head;
  586.          rule_no != NIL; rule_no = next_rule[rule_no])
  587.         hash_address += rule_no;
  588.  
  589.     hash_address %= STATE_TABLE_SIZE;
  590.  
  591.     /******************************************************************/
  592.     /* Search the hash table for a compatible state. Two states S1    */
  593.     /* and S2 are compatible if                                       */
  594.     /*     1) the set of rules in their reduce map is identical.      */
  595.     /*     2) for each terminal symbol t, either                      */
  596.     /*            reduce[S1][t] == reduce[S2][t] or                   */
  597.     /*            reduce[S1][t] == OMEGA         or                   */
  598.     /*            reduce[S2][t] == OMEGA                              */
  599.     /*                                                                */
  600.     /******************************************************************/
  601.     for (state = sp_table[hash_address];
  602.          state != NULL; state = state -> link)
  603.     {
  604.         if (state -> rule_count == sp_rule_count) /* same # of rules? */
  605.         {
  606.             for (p = state -> rule_root; p != NULL; p = p -> next)
  607.             {
  608.                 if (next_rule[p -> value] == OMEGA)   /* not in list? */
  609.                     break;
  610.             }
  611.  
  612.     /******************************************************************/
  613.     /* If the set of rules are identical, we proceed to compare the   */
  614.     /* actions for compatibility. The idea is to make sure that all   */
  615.     /* actions in the hash table do not clash in the actions in the   */
  616.     /* map sp_action[SYMBOL].                                         */
  617.     /******************************************************************/
  618.             if (p == NULL) /* all the rules match? */
  619.             {
  620.                 struct action_element *actionp,
  621.                                       *action_tail;
  622.  
  623.                 for (actionp = state -> action_root;
  624.                      actionp != NULL; actionp = actionp -> next)
  625.                 {
  626.                     if (sp_action[symbol][actionp -> symbol] != OMEGA &&
  627.                         sp_action[symbol][actionp -> symbol] !=
  628.                                                      actionp -> action)
  629.                          break;
  630.                 }
  631.  
  632.         /**************************************************************/
  633.         /* If the two states are compatible merge them into the map   */
  634.         /* sp_action[SYMBOL]. (Note that this effectively destroys    */
  635.         /* the original map.) Also, keep track of whether or not an   */
  636.         /* actual merging action was necessary with the boolean       */
  637.         /* variable no_overwrite.                                     */
  638.         /**************************************************************/
  639.                 if (actionp == NULL) /* compatible states */
  640.                 {
  641.                     no_overwrite = TRUE;
  642.                     for (actionp = state -> action_root;
  643.                          actionp != NULL;
  644.                          action_tail = actionp, actionp = actionp -> next)
  645.                     {
  646.                         if (sp_action[symbol][actionp -> symbol] == OMEGA)
  647.                         {
  648.                             sp_action[symbol][actionp -> symbol] =
  649.                                                          actionp -> action;
  650.                             no_overwrite = FALSE;
  651.                         }
  652.                     }
  653.  
  654.             /**********************************************************/
  655.             /* If the item was not previously associated with this    */
  656.             /* state, add it.                                         */
  657.             /**********************************************************/
  658.                     for (p = state -> complete_items;
  659.                          p != NULL; p = p -> next)
  660.                     {
  661.                         if (p -> value == item_no)
  662.                             break;
  663.                     }
  664.                     if (p == NULL)
  665.                     {
  666.                         p = Allocate_node();
  667.                         p -> value = item_no;
  668.                         p -> next = state -> complete_items;
  669.                         state -> complete_items = p;
  670.                     }
  671.  
  672.             /**********************************************************/
  673.             /* If the two maps are identical (there was no merging),  */
  674.             /* return the state number otherwise, free the old map    */
  675.             /* and break out of the search loop.                      */
  676.             /**********************************************************/
  677.                     if (no_overwrite &&
  678.                         state -> action_count == sp_action_count)
  679.                         return state -> state_number;
  680.  
  681.                     free_action_elements(state -> action_root, action_tail);
  682.  
  683.                     break; /* for (state = sp_table[hash_address]; ... */
  684.                 }
  685.             }
  686.         }
  687.     }
  688.  
  689.     /******************************************************************/
  690.     /* If we did not find a compatible state, construct a new one.    */
  691.     /* Add it to the list of state and add it to the hash table.      */
  692.     /******************************************************************/
  693.     if (state == NULL)
  694.     {
  695.         state = (struct sp_state_element *)
  696.                 talloc(sizeof(struct sp_state_element));
  697.         if (state == NULL)
  698.             nospace(__FILE__, __LINE__);
  699.  
  700.         state -> next = sp_state_root;
  701.         sp_state_root = state;
  702.  
  703.         state -> link = sp_table[hash_address];
  704.         sp_table[hash_address] = state;
  705.  
  706.         max_sp_state++;
  707.         state -> state_number = max_sp_state;
  708.         state -> rule_count = sp_rule_count;
  709.  
  710.         p = Allocate_node();
  711.         p -> value = item_no;
  712.         p -> next = NULL;
  713.         state -> complete_items = p;
  714.  
  715.         state -> rule_root = NULL;
  716.         for (rule_no = rule_head;
  717.              rule_no != NIL; rule_no = next_rule[rule_no])
  718.         {
  719.             p = Allocate_node();
  720.             p -> value = rule_no;
  721.             p -> next = state -> rule_root;
  722.             state -> rule_root = p;
  723.         }
  724.     }
  725.  
  726.     /******************************************************************/
  727.     /* If the state is new or had its reduce map merged with another  */
  728.     /* map, we update the reduce map here.                            */
  729.     /******************************************************************/
  730.     state -> action_count = sp_action_count;
  731.     state -> action_root = NULL;
  732.     for ALL_TERMINALS(i)
  733.     {
  734.         struct action_element *actionp;
  735.  
  736.         if (sp_action[symbol][i] != OMEGA)
  737.         {
  738.             actionp = allocate_action_element();
  739.             actionp -> symbol = i;
  740.             actionp -> action = sp_action[symbol][i];
  741.  
  742.             actionp -> next = state -> action_root;
  743.             state -> action_root = actionp;
  744.         }
  745.     }
  746.  
  747.     return state -> state_number;
  748. }
  749.  
  750.  
  751. /*****************************************************************************/
  752. /*                       REMOVE_SINGLE_PRODUCTIONS:                          */
  753. /*****************************************************************************/
  754. /* This program is invoked to remove as many single production actions as    */
  755. /* possible for a conflict-free automaton.                                   */
  756. /*****************************************************************************/
  757. void remove_single_productions(void)
  758. {
  759.     struct goto_header_type go_to;
  760.     struct shift_header_type sh;
  761.     struct reduce_header_type red;
  762.  
  763.     struct sp_state_element *state;
  764.     struct node             *p,
  765.                             *rule_tail;
  766.  
  767.     int rule_head,
  768.         sp_rule_count,
  769.         sp_action_count,
  770.         rule_no,
  771.         state_no,
  772.         symbol,
  773.         lhs_symbol,
  774.         action,
  775.         item_no,
  776.         i,
  777.         j;
  778.  
  779.     BOOLEAN end_node;
  780.  
  781.     short *symbol_list,
  782.           *shift_transition,
  783.           *rule_count;
  784.  
  785.     short shift_table[SHIFT_TABLE_SIZE];
  786.  
  787.     struct new_shift_element
  788.     {
  789.         short link,
  790.               shift_number;
  791.     } *new_shift;
  792.  
  793.     /******************************************************************/
  794.     /* Set up a a pool of temporary space.                            */
  795.     /******************************************************************/
  796.     reset_temporary_space();
  797.  
  798.     /******************************************************************/
  799.     /* Allocate all other necessary temporary objects.                */
  800.     /******************************************************************/
  801.     sp_rules = Allocate_short_array(num_symbols + 1);
  802.     stack = Allocate_short_array(num_symbols + 1);
  803.     index_of = Allocate_short_array(num_symbols + 1);
  804.     next_rule = Allocate_short_array(num_rules + 1);
  805.     rule_list = Allocate_short_array(num_rules + 1);
  806.     symbol_list = Allocate_short_array(num_symbols + 1);
  807.     shift_transition = Allocate_short_array(num_symbols + 1);
  808.     rule_count = Allocate_short_array(num_rules + 1);
  809.  
  810.     new_shift = (struct new_shift_element *)
  811.                 calloc(max_la_state + 1,
  812.                        sizeof(struct new_shift_element));
  813.     if (new_shift == NULL)
  814.         nospace(__FILE__, __LINE__);
  815.  
  816.     look_ahead = (SET_PTR)
  817.                  calloc(1, term_set_size * sizeof(BOOLEAN_CELL));
  818.     if (look_ahead == NULL)
  819.         nospace(__FILE__, __LINE__);
  820.  
  821.     sp_action = (short **)
  822.                 calloc(num_symbols + 1, sizeof(short *));
  823.     if (sp_action == NULL)
  824.         nospace(__FILE__, __LINE__);
  825.  
  826.     is_conflict_symbol = (BOOLEAN *)
  827.                          calloc(num_symbols + 1, sizeof(BOOLEAN));
  828.     if (is_conflict_symbol == NULL)
  829.         nospace(__FILE__, __LINE__);
  830.  
  831.     sp_table = (struct sp_state_element **)
  832.                calloc(STATE_TABLE_SIZE,
  833.                       sizeof(struct sp_state_element *));
  834.     if (sp_table == NULL)
  835.         nospace(__FILE__, __LINE__);
  836.  
  837.     new_action = (struct action_element **)
  838.                  calloc(num_states + 1, sizeof(struct action_element *));
  839.     if (new_action == NULL)
  840.         nospace(__FILE__, __LINE__);
  841.  
  842.     update_action = (struct update_action_element **)
  843.                     calloc(num_states + 1,
  844.                            sizeof(struct update_action_element *));
  845.     if (update_action == NULL)
  846.         nospace(__FILE__, __LINE__);
  847.  
  848.     /******************************************************************/
  849.     /* Initialize all relevant sets and maps to the empty set.        */
  850.     /******************************************************************/
  851.     rule_root = NIL;
  852.     symbol_root = NIL;
  853.  
  854.     for ALL_RULES(i)
  855.         rule_list[i] = OMEGA;
  856.  
  857.     for ALL_SYMBOLS(i)
  858.     {
  859.         symbol_list[i] = OMEGA;
  860.         sp_rules[i]    = NIL;
  861.         sp_action[i]   = NULL;
  862.     }
  863.  
  864.     /******************************************************************/
  865.     /* Construct a set of all symbols used in the right-hand side of  */
  866.     /* single production in symbol_list. The variable symbol_root     */
  867.     /* points to the root of the list. Also, construct a mapping from */
  868.     /* each symbol into the set of single productions of which it is  */
  869.     /* the right-hand side. sp_rules is the base of that map and the  */
  870.     /* relevant sets are stored in the vector next_rule.              */
  871.     /******************************************************************/
  872.     for ALL_RULES(rule_no)
  873.     {
  874.         if (rules[rule_no].sp)
  875.         {
  876.             i = rhs_sym[rules[rule_no].rhs];
  877.             next_rule[rule_no] = sp_rules[i];
  878.             sp_rules[i] = rule_no;
  879.             if (symbol_list[i] == OMEGA)
  880.             {
  881.                 symbol_list[i] = symbol_root;
  882.                 symbol_root = i;
  883.             }
  884.         }
  885.     }
  886.  
  887.     /******************************************************************/
  888.     /* Initialize the index_of vector and clear the stack (top).      */
  889.     /* Next, iterate over the list of right-hand side symbols used in */
  890.     /* single productions and invoke compute_sp_map to partially      */
  891.     /* order these symbols (based on the ::= (or ->) relationship) as */
  892.     /* well as their associated rules. (See compute_sp_map for detail)*/
  893.     /* As the list of rules is constructed as a circular list to keep */
  894.     /* it in proper order, it is turned into a linear list here.      */
  895.     /******************************************************************/
  896.     for (i = symbol_root; i != NIL; i = symbol_list[i])
  897.         index_of[i] = OMEGA;
  898.     top = 0;
  899.     for (i = symbol_root; i != NIL; i = symbol_list[i])
  900.     {
  901.         if (index_of[i] == OMEGA)
  902.             compute_sp_map(i);
  903.     }
  904.  
  905.     if (rule_root != NIL) /* make rule_list non-circular */
  906.     {
  907.         rule_no = rule_root;
  908.         rule_root = rule_list[rule_no];
  909.         rule_list[rule_no] = NIL;
  910.     }
  911.  
  912.     /******************************************************************/
  913.     /* Clear out all the sets in sp_rules and using the new revised   */
  914.     /* list of SP rules mark the new set of right-hand side symbols.  */
  915.     /* Note this code is important for consistency in case we are     */
  916.     /* removing single productions in an automaton containing         */
  917.     /* conflicts. If an automaton does not contain any conflict, the  */
  918.     /* new set of SP rules is always the same as the initial set.     */
  919.     /******************************************************************/
  920.     for (i = symbol_root; i != NIL; i = symbol_list[i])
  921.         sp_rules[i] = NIL;
  922.  
  923.     top = 0;
  924.     for (rule_no = rule_root;
  925.          rule_no != NIL; rule_no = rule_list[rule_no])
  926.     {
  927.         top++;
  928.  
  929.         i = rhs_sym[rules[rule_no].rhs];
  930.         sp_rules[i] = OMEGA;
  931.     }
  932.  
  933.     /******************************************************************/
  934.     /* Initialize the base of the hash table for the new SP states.   */
  935.     /* Initialize the root pointer for the list of new states.        */
  936.     /* Initialize max_sp_state to num_states. It will be incremented  */
  937.     /* each time a new state is constructed.                          */
  938.     /* Initialize the update_action table.                            */
  939.     /* Initialize the is_conflict_symbol array for non_terminals.     */
  940.     /* Since nonterminals are not used as lookahead symbols, they are */
  941.     /* never involved in conflicts.                                   */
  942.     /* Initialize the set/list (symbol_root, symbol_list) to the      */
  943.     /* empty set/list.                                                */
  944.     /******************************************************************/
  945.     for (i = 0; i < STATE_TABLE_SIZE; i++)
  946.         sp_table[i] = NULL;
  947.  
  948.     sp_state_root = NULL;
  949.     max_sp_state = num_states;
  950.  
  951.     for ALL_STATES(state_no)
  952.         update_action[state_no] = NULL;
  953.  
  954.     for ALL_NON_TERMINALS(i)
  955.         is_conflict_symbol[i] = FALSE;
  956.  
  957.     symbol_root = NIL;
  958.     for ALL_SYMBOLS(i)
  959.         symbol_list[i] = OMEGA;
  960.  
  961.     /******************************************************************/
  962.     /* Traverse all regular states and process the relevant ones.     */
  963.     /******************************************************************/
  964.     for ALL_STATES(state_no)
  965.     {
  966.         struct node *item_ptr;
  967.  
  968.         new_action[state_no] = NULL;
  969.  
  970.         go_to = statset[state_no].go_to;
  971.         sh = shift[statset[state_no].shift_number];
  972.  
  973.         /**************************************************************/
  974.         /* If the state has no goto actions, it is not considered, as */
  975.         /* no single productions could have been introduced in it.    */
  976.         /* Otherwise, we initialize index_of to the empty map and     */
  977.         /* presume that symbol_list is initialized to the empty set.  */
  978.         /**************************************************************/
  979.         if (go_to.size > 0)
  980.         {
  981.             for ALL_SYMBOLS(i)
  982.                 index_of[i] = OMEGA;
  983.  
  984.             for ALL_TERMINALS(i)
  985.                 is_conflict_symbol[i] = FALSE;
  986.             for (end_node = ((p = conflict_symbols[state_no]) == NULL);
  987.                  ! end_node; end_node = (p == conflict_symbols[state_no]))
  988.             {
  989.                 p = p -> next;
  990.                 is_conflict_symbol[p -> value] = TRUE;
  991.             }
  992.  
  993.             /**********************************************************/
  994.             /* First, use index_of to map each nonterminal symbol on  */
  995.             /* which there is a transition in state_no into its index */
  996.             /* in the goto map of state_no.                           */
  997.             /* Note that this initialization must be executed first   */
  998.             /* before we process the next loop, because index_of is   */
  999.             /* a global variable that is used in the routine          */
  1000.             /* compute_sp_action.                                     */
  1001.             /**********************************************************/
  1002.             for (i = 1; i <= go_to.size; i++)
  1003.                 index_of[GOTO_SYMBOL(go_to, i)] = i;
  1004.  
  1005.             /**********************************************************/
  1006.             /* Traverse first the goto map, then the shift map and    */
  1007.             /* for each symbol that is the right-hand side of a single*/
  1008.             /* production on which there is a transition, compute the */
  1009.             /* lookahead set that can follow this transition and add  */
  1010.             /* the symbol to the set of candidates (in symbol_list).  */
  1011.             /**********************************************************/
  1012.             for (i = 1; i <= go_to.size; i++)
  1013.             {
  1014.                 symbol = GOTO_SYMBOL(go_to, i);
  1015.                 if (IS_SP_RHS(symbol))
  1016.                 {
  1017.                     compute_sp_action(state_no, symbol,
  1018.                                       GOTO_ACTION(go_to, i));
  1019.                     symbol_list[symbol] = symbol_root;
  1020.                     symbol_root = symbol;
  1021.                 }
  1022.             }
  1023.  
  1024.             for (i = 1; i <= sh.size; i++)
  1025.             {
  1026.                 symbol = SHIFT_SYMBOL(sh, i);
  1027.                 index_of[symbol] = i;
  1028.                 if (IS_SP_RHS(symbol))
  1029.                 {
  1030.                     compute_sp_action(state_no, symbol,
  1031.                                       SHIFT_ACTION(sh, i));
  1032.                     symbol_list[symbol] = symbol_root;
  1033.                     symbol_root = symbol;
  1034.                 }
  1035.             }
  1036.  
  1037.             /**********************************************************/
  1038.             /* We now traverse the set of single productions in order */
  1039.             /* and for each rule that was introduced through closure  */
  1040.             /* in the state (there is an action on both the left- and */
  1041.             /* right-hand side)...                                    */
  1042.             /**********************************************************/
  1043.             for (rule_no = rule_root;
  1044.                  rule_no != NIL; rule_no = rule_list[rule_no])
  1045.             {
  1046.                 symbol = rhs_sym[rules[rule_no].rhs];
  1047.                 if (symbol_list[symbol] != OMEGA)
  1048.                 {
  1049.                     lhs_symbol = rules[rule_no].lhs;
  1050.                     if (index_of[lhs_symbol] != OMEGA)
  1051.                     {
  1052.                         if (symbol_list[lhs_symbol] == OMEGA)
  1053.                         {
  1054.                             compute_sp_action(state_no, lhs_symbol,
  1055.                                 GOTO_ACTION(go_to, index_of[lhs_symbol]));
  1056.                             symbol_list[lhs_symbol] = symbol_root;
  1057.                             symbol_root = lhs_symbol;
  1058.                         }
  1059.                 /******************************************************/
  1060.                 /* Copy all reduce actions defined after the          */
  1061.                 /* transition on the left-hand side into the          */
  1062.                 /* corresponding action defined after the transition  */
  1063.                 /* on the right-hand side. If an action is defined    */
  1064.                 /* for the left-hand side -                           */
  1065.                 /*                                                    */
  1066.                 /*     sp_action[lhs_symbol][i] != OMEGA              */
  1067.                 /*                                                    */
  1068.                 /* - but not for the right-hand side -                */
  1069.                 /*                                                    */
  1070.                 /*     sp_action[symbol][i] == OMEGA                  */
  1071.                 /*                                                    */
  1072.                 /* it is an indication that after the transition on   */
  1073.                 /* symbol, the action on i is a lookahead shift. In   */
  1074.                 /* that case, no action is copied.                    */
  1075.                 /******************************************************/
  1076.                         for ALL_TERMINALS(i)
  1077.                         {
  1078.                             if (sp_action[lhs_symbol][i] != OMEGA &&
  1079.                                 sp_action[symbol][i] != OMEGA)
  1080.                                     sp_action[symbol][i] =
  1081.                                         sp_action[lhs_symbol][i];
  1082.                         }
  1083.                     }
  1084.                 }
  1085.             }
  1086.  
  1087.             /**********************************************************/
  1088.             /* For each symbol that is the right-hand side of some SP */
  1089.             /* for which a reduce map is defined, we either construct */
  1090.             /* a new state if the transition is into a final state,   */
  1091.             /* or we update the relevant reduce action of the state   */
  1092.             /* into which the transition is made, otherwise.          */
  1093.             /*                                                        */
  1094.             /* When execution of this loop is terminated the set      */
  1095.             /* symbol_root/symbol_list is reinitialize to the empty   */
  1096.             /* set.                                                   */
  1097.             /**********************************************************/
  1098.             for (symbol = symbol_root;
  1099.                  symbol != NIL;
  1100.                  symbol_list[symbol] = OMEGA, symbol = symbol_root)
  1101.             {
  1102.                 symbol_root = symbol_list[symbol];
  1103.  
  1104.                 if (IS_SP_RHS(symbol))
  1105.                 {
  1106.                     if (symbol IS_A_TERMINAL)
  1107.                          action = SHIFT_ACTION(sh, index_of[symbol]);
  1108.                     else action = GOTO_ACTION(go_to, index_of[symbol]);
  1109.  
  1110.                 /******************************************************/
  1111.                 /* If the transition is a lookahead shift, do nothing.*/
  1112.                 /* If the action is a goto- or shift-reduce, compute  */
  1113.                 /* the relevant rule and item involved.               */
  1114.                 /* Otherwise, the action is a shift or a goto. If the */
  1115.                 /* transition is into a final state then it is        */
  1116.                 /* processed as the case of read-reduce above. If     */
  1117.                 /* not, we invoke compute_update_actions to update    */
  1118.                 /* the relevant actions.                              */
  1119.                 /******************************************************/
  1120.                     if (action > num_states) /* lookahead shift */
  1121.                         rule_no = OMEGA;
  1122.                     else if (action < 0) /* read-reduce action */
  1123.                     {
  1124.                         rule_no = -action;
  1125.                         item_no = adequate_item[rule_no] -> value;
  1126.                     }
  1127.                     else                /* transition action  */
  1128.                     {
  1129.                         item_ptr = statset[action].kernel_items;
  1130.                         item_no = item_ptr -> value;
  1131.                         if ((item_ptr -> next == NULL) &&
  1132.                             (item_table[item_no].symbol == empty))
  1133.                              rule_no = item_table[item_no].rule_number;
  1134.                         else
  1135.                         {
  1136.                             compute_update_actions(state_no, action, symbol);
  1137.                             rule_no = OMEGA;
  1138.                         }
  1139.                     }
  1140.  
  1141.                 /******************************************************/
  1142.                 /* If we have a valid SP rule we first construct the  */
  1143.                 /* set of rules in the range of the reduce map of the */
  1144.                 /* right-hand side of the rule. If that set contains  */
  1145.                 /* a single rule then the action on the right-hand    */
  1146.                 /* side is redefined as the same action on the left-  */
  1147.                 /* hand side of the rule in question. Otherwise, we   */
  1148.                 /* create a new state for the final item of the SP    */
  1149.                 /* rule consisting of the reduce map associated with  */
  1150.                 /* the right-hand side of the SP rule and the new     */
  1151.                 /* action on the right-hand side is a transition into */
  1152.                 /* this new state.                                    */
  1153.                 /******************************************************/
  1154.                     if (rule_no != OMEGA)
  1155.                     {
  1156.                         if (IS_SP_RULE(rule_no))
  1157.                         {
  1158.                             struct action_element *p;
  1159.  
  1160.                             sp_rule_count = 0;
  1161.                             sp_action_count = 0;
  1162.                             rule_head = NIL;
  1163.  
  1164.                             for ALL_RULES(i)
  1165.                                 next_rule[i] = OMEGA;
  1166.  
  1167.                             for ALL_TERMINALS(i)
  1168.                             {
  1169.                                 rule_no = sp_action[symbol][i];
  1170.                                 if (rule_no != OMEGA)
  1171.                                 {
  1172.                                     sp_action_count++;
  1173.                                     if (next_rule[rule_no] == OMEGA)
  1174.                                     {
  1175.                                         sp_rule_count++;
  1176.                                         next_rule[rule_no] = rule_head;
  1177.                                         rule_head = rule_no;
  1178.                                     }
  1179.                                 }
  1180.                             }
  1181.  
  1182.                             if (sp_rule_count == 1 && IS_SP_RULE(rule_head))
  1183.                             {
  1184.                                 lhs_symbol = rules[rule_head].lhs;
  1185.                                 action = GOTO_ACTION(go_to,
  1186.                                                 index_of[lhs_symbol]);
  1187.                             }
  1188.                             else
  1189.                             {
  1190.                                 action = sp_state_map(rule_head,
  1191.                                                       item_no,
  1192.                                                       sp_rule_count,
  1193.                                                       sp_action_count,
  1194.                                                       symbol);
  1195.                             }
  1196.  
  1197.                             p = allocate_action_element();
  1198.                             p -> symbol = symbol;
  1199.                             p -> action = action;
  1200.  
  1201.                             p -> next = new_action[state_no];
  1202.                             new_action[state_no] = p;
  1203.                         }
  1204.                     }
  1205.                 }
  1206.             }
  1207.         }
  1208.     } /* for ALL_STATES(state_no) */
  1209.  
  1210.     /******************************************************************/
  1211.     /* We are now ready to extend all global maps based on states and */
  1212.     /* permanently install the new states.                            */
  1213.     /******************************************************************/
  1214.     statset = (struct statset_type *)
  1215.               realloc(statset,
  1216.                       (max_sp_state + 1) * sizeof(struct statset_type));
  1217.     if (statset == NULL)
  1218.         nospace(__FILE__, __LINE__);
  1219.  
  1220.     reduce = (struct reduce_header_type *)
  1221.              realloc(reduce,
  1222.                      (max_sp_state + 1) * sizeof(struct reduce_header_type));
  1223.     if (reduce == NULL)
  1224.         nospace(__FILE__, __LINE__);
  1225.  
  1226.     if (gd_index != NULL) /* see routine PRODUCE */
  1227.     {
  1228.         gd_index = (short *)
  1229.                    realloc(gd_index, (max_sp_state + 2) * sizeof(short));
  1230.         if (gd_index == NULL)
  1231.             nospace(__FILE__, __LINE__);
  1232.  
  1233.         /**************************************************************/
  1234.         /* Each element gd_index[i] points to the starting location   */
  1235.         /* of a slice in another array. The last element of the slice */
  1236.         /* can be computed as (gd_index[i+1] - 1). After extending    */
  1237.         /* gd_index, we set each new element to point to the same     */
  1238.         /* index as its previous element, making it point to a null   */
  1239.         /* slice.                                                     */
  1240.         /**************************************************************/
  1241.         for (state_no = num_states + 2;
  1242.              state_no <= max_sp_state + 1; state_no++)
  1243.              gd_index[state_no] = gd_index[state_no - 1];
  1244.     }
  1245.  
  1246.     in_stat = (struct node **)
  1247.               realloc(in_stat,
  1248.                       (max_sp_state + 1) * sizeof(struct node *));
  1249.     if (in_stat == NULL)
  1250.         nospace(__FILE__, __LINE__);
  1251.  
  1252.     for (state_no = num_states + 1; state_no <= max_sp_state; state_no++)
  1253.          in_stat[state_no] = NULL;
  1254.  
  1255.     /******************************************************************/
  1256.     /* We now adjust all references to a lookahead state. The idea is */
  1257.     /* offset the number associated with each lookahead state by the  */
  1258.     /* number of new SP states that were added.                       */
  1259.     /******************************************************************/
  1260.     for (j = 1; j <= num_shift_maps; j++)
  1261.     {
  1262.         sh = shift[j];
  1263.         for (i = 1; i <= sh.size; i++)
  1264.         {
  1265.             if (SHIFT_ACTION(sh, i) > num_states)
  1266.                 SHIFT_ACTION(sh, i) += (max_sp_state - num_states);
  1267.         }
  1268.     }
  1269.  
  1270.     for (state_no = num_states + 1; state_no <= max_la_state; state_no++)
  1271.     {
  1272.         if (lastats[state_no].in_state > num_states)
  1273.             lastats[state_no].in_state += (max_sp_state - num_states);
  1274.     }
  1275.  
  1276.     lastats -= (max_sp_state - num_states);
  1277.     max_la_state += (max_sp_state - num_states);
  1278.     SHORT_CHECK(max_la_state);
  1279.  
  1280.     /******************************************************************/
  1281.     /* We now permanently construct all the new SP states.            */
  1282.     /******************************************************************/
  1283.     for (state = sp_state_root; state != NULL; state = state -> next)
  1284.     {
  1285.         struct action_element *actionp;
  1286.  
  1287.         int default_rule,
  1288.             reduce_size;
  1289.  
  1290.         state_no = state -> state_number;
  1291.  
  1292.         /**************************************************************/
  1293.         /* These states are identified as special SP states since     */
  1294.         /* they have no kernel items. They also have no goto and      */
  1295.         /* shift actions.                                             */
  1296.         /**************************************************************/
  1297.         statset[state_no].kernel_items = NULL;
  1298.         statset[state_no].complete_items = state -> complete_items;
  1299.         statset[state_no].go_to.size = 0;
  1300.         statset[state_no].go_to.map = NULL;
  1301.         statset[state_no].shift_number = 0;
  1302.  
  1303.         /**************************************************************/
  1304.         /* Count the number of actions defined on each rule in the    */
  1305.         /* range of the reduce map.                                   */
  1306.         /**************************************************************/
  1307.         for (p = state -> rule_root; p != NULL; p = p -> next)
  1308.             rule_count[p -> value] = 0;
  1309.  
  1310.         for (actionp = state -> action_root;
  1311.              actionp != NULL; actionp = actionp -> next)
  1312.             rule_count[actionp -> action]++;
  1313.  
  1314.         /**************************************************************/
  1315.         /* Count the total number of reduce actions in the reduce map */
  1316.         /* and calculate the default.                                 */
  1317.         /**************************************************************/
  1318.         reduce_size = 0;
  1319.         sp_rule_count = 0;
  1320.         for (p = state -> rule_root; p != NULL; rule_tail = p, p = p -> next)
  1321.         {
  1322.             reduce_size += rule_count[p -> value];
  1323.             if (rule_count[p -> value] > sp_rule_count)
  1324.             {
  1325.                 sp_rule_count = rule_count[p -> value];
  1326.                 default_rule = p -> value;
  1327.             }
  1328.         }
  1329.  
  1330.         free_nodes(state -> rule_root, rule_tail);
  1331.  
  1332.         /**************************************************************/
  1333.         /* Construct a permanent reduce map for this SP state.        */
  1334.         /**************************************************************/
  1335.         num_reductions += reduce_size;
  1336.  
  1337.         red = Allocate_reduce_map(reduce_size);
  1338.         reduce[state_no] = red;
  1339.         REDUCE_SYMBOL(red, 0)  = DEFAULT_SYMBOL;
  1340.         REDUCE_RULE_NO(red, 0) = default_rule;
  1341.  
  1342.         for (actionp = state -> action_root;
  1343.              actionp != NULL; actionp = actionp -> next)
  1344.         {
  1345.             REDUCE_SYMBOL(red, reduce_size)  = actionp -> symbol;
  1346.             REDUCE_RULE_NO(red, reduce_size) = actionp -> action;
  1347.             reduce_size--;
  1348.         }
  1349.     }
  1350.  
  1351.     /******************************************************************/
  1352.     /* We are now ready to update some old actions and add new ones.  */
  1353.     /* This may require that we create new shift maps.  We            */
  1354.     /* initialize top to 0 so we can use it as an index to allocate   */
  1355.     /* elements from new_shift. We also initialize all the elements   */
  1356.     /* of shift_table to NIL. Shift_table will be used as the base of */
  1357.     /* a hash table for the new shift maps.                           */
  1358.     /******************************************************************/
  1359.     top = 0;
  1360.     for (i = 0; i <= SHIFT_TABLE_UBOUND; i++)
  1361.         shift_table[i] = NIL;
  1362.  
  1363.     /******************************************************************/
  1364.     /* At most, the shift array contains 1..num_states elements. As,  */
  1365.     /* each of these elements might be (theoretically) replaced by a  */
  1366.     /* new one, we need to double its size.                           */
  1367.     /******************************************************************/
  1368.     shift = (struct shift_header_type *)
  1369.             realloc(shift,
  1370.                2 * (num_states + 1) * sizeof(struct shift_header_type));
  1371.     if (shift == NULL)
  1372.         nospace(__FILE__, __LINE__);
  1373.  
  1374.     /******************************************************************/
  1375.     /* For each state with updates or new actions, take appropriate   */
  1376.     /* actions.                                                       */
  1377.     /******************************************************************/
  1378.     for ALL_STATES(state_no)
  1379.     {
  1380.         BOOLEAN any_shift_action;
  1381.  
  1382.         /**************************************************************/
  1383.         /* Update reduce actions for final items of single productions*/
  1384.         /* that are in non-final states.                              */
  1385.         /**************************************************************/
  1386.         if (update_action[state_no] != NULL)
  1387.         {
  1388.             struct update_action_element *p;
  1389.  
  1390.             red = reduce[state_no];
  1391.             for (i = 1; i <= red.size; i++)
  1392.                 index_of[REDUCE_SYMBOL(red, i)] = i;
  1393.  
  1394.             for (p = update_action[state_no]; p != NULL; p = p -> next)
  1395.                 REDUCE_RULE_NO(red, index_of[p -> symbol]) = p -> action;
  1396.         }
  1397.  
  1398.         /**************************************************************/
  1399.         /* Update initial automaton with transitions into new SP      */
  1400.         /* states.                                                    */
  1401.         /**************************************************************/
  1402.         if (new_action[state_no] != NULL)
  1403.         {
  1404.             struct action_element *p;
  1405.  
  1406.             /**********************************************************/
  1407.             /* Mark the index of each symbol on which there is a      */
  1408.             /* transition and copy the shift map into the vector      */
  1409.             /* shift_transition.                                      */
  1410.             /**********************************************************/
  1411.             go_to = statset[state_no].go_to;
  1412.             for (i = 1; i <= go_to.size; i++)
  1413.                 index_of[GOTO_SYMBOL(go_to, i)] = i;
  1414.  
  1415.             sh = shift[statset[state_no].shift_number];
  1416.             for (i = 1; i <= sh.size; i++)
  1417.             {
  1418.                 index_of[SHIFT_SYMBOL(sh, i)] = i;
  1419.                 shift_transition[SHIFT_SYMBOL(sh, i)] = SHIFT_ACTION(sh, i);
  1420.             }
  1421.  
  1422.             /**********************************************************/
  1423.             /* Iterate over the new action and update the goto map    */
  1424.             /* directly for goto actions but update shift_transition  */
  1425.             /* for shift actions. Also, keep track as to whether or   */
  1426.             /* not there were any shift transitions at all...         */
  1427.             /**********************************************************/
  1428.             any_shift_action = FALSE;
  1429.  
  1430.             for (p = new_action[state_no]; p != NULL; p = p -> next)
  1431.             {
  1432.                 if (p -> symbol IS_A_NON_TERMINAL)
  1433.                 {
  1434.                     if (GOTO_ACTION(go_to, index_of[p -> symbol]) < 0 &&
  1435.                         p -> action > 0)
  1436.                     {
  1437.                         num_goto_reduces--;
  1438.                         num_gotos++;
  1439.                     }
  1440.                     GOTO_ACTION(go_to, index_of[p -> symbol]) = p -> action;
  1441.                 }
  1442.                 else
  1443.                 {
  1444.                     if (SHIFT_ACTION(sh, index_of[p -> symbol]) < 0 &&
  1445.                         p -> action > 0)
  1446.                     {
  1447.                         num_shift_reduces--;
  1448.                         num_shifts++;
  1449.                     }
  1450.                     shift_transition[p -> symbol] = p -> action;
  1451.  
  1452.                     any_shift_action = TRUE;
  1453.                 }
  1454.             }
  1455.  
  1456.             /**********************************************************/
  1457.             /* If there were any shift actions, a new shift map may   */
  1458.             /* have been created. Hash shift_transition into the      */
  1459.             /* shift hash table.                                      */
  1460.             /**********************************************************/
  1461.             if (any_shift_action)
  1462.             {
  1463.                 struct shift_header_type sh2;
  1464.                 unsigned long hash_address;
  1465.  
  1466.                 hash_address = sh.size;
  1467.                 for (i = 1; i <= sh.size; i++) /* Compute Hash location */
  1468.                     hash_address += SHIFT_SYMBOL(sh, i);
  1469.                 hash_address %= SHIFT_TABLE_SIZE;
  1470.  
  1471.             /**************************************************************/
  1472.             /* Search HASH_ADDRESS location for shift map that matches    */
  1473.             /* the shift map in shift_transition.  If a match is found    */
  1474.             /* we leave the loop prematurely, the search index j is not   */
  1475.             /* NIL, and it identifies the shift map in the hash table     */
  1476.             /* that matched the shift_transition.                         */
  1477.             /**************************************************************/
  1478.                 for (j = shift_table[hash_address];
  1479.                      j != NIL; j = new_shift[j].link)
  1480.                 {
  1481.                     sh2 = shift[new_shift[j].shift_number];
  1482.                     if (sh.size == sh2.size)
  1483.                     {
  1484.                         for (i = 1; i <= sh.size; i++)
  1485.                             if (SHIFT_ACTION(sh2, i) !=
  1486.                                 shift_transition[SHIFT_SYMBOL(sh2, i)])
  1487.                                     break;
  1488.                         if (i > sh.size)
  1489.                             break; /* for (j = shift_table[ ... */
  1490.                     }
  1491.                 }
  1492.  
  1493.             /**************************************************************/
  1494.             /* If j == NIL, the map at hand had not yet being inserted in */
  1495.             /* the table, it is inserted.  Otherwise, we have a match,    */
  1496.             /* and STATE_NO is reset to share the shift map previously    */
  1497.             /* inserted that matches its shift map.                       */
  1498.             /**************************************************************/
  1499.                 if (j == NIL)
  1500.                 {
  1501.                     sh2 = Allocate_shift_map(sh.size);
  1502.                     for (i = 1; i <= sh.size; i++)
  1503.                     {
  1504.                         symbol = SHIFT_SYMBOL(sh, i);
  1505.                         SHIFT_SYMBOL(sh2, i) = symbol;
  1506.                         SHIFT_ACTION(sh2, i) = shift_transition[symbol];
  1507.                     }
  1508.                     num_shift_maps++;
  1509.                     shift[num_shift_maps] = sh2;
  1510.  
  1511.                     statset[state_no].shift_number = num_shift_maps;
  1512.  
  1513.                     top++;
  1514.                     new_shift[top].shift_number = num_shift_maps;
  1515.  
  1516.                     new_shift[top].link = shift_table[hash_address];
  1517.                     shift_table[hash_address] = top;
  1518.                 }
  1519.                 else
  1520.                 {
  1521.                     statset[state_no].shift_number =
  1522.                            new_shift[j].shift_number;
  1523.                 }
  1524.             }
  1525.         }
  1526.     }
  1527.  
  1528.     /******************************************************************/
  1529.     /* Free all nodes used in the construction of the conflict_symbols*/
  1530.     /* map as this map is no longer useful and its size is based on   */
  1531.     /* the base value of num_states.                                  */
  1532.     /******************************************************************/
  1533.     for ALL_STATES(state_no)
  1534.     {
  1535.         if (conflict_symbols[state_no] != NULL)
  1536.         {
  1537.             p = conflict_symbols[state_no] -> next;
  1538.             free_nodes(p, conflict_symbols[state_no]);
  1539.         }
  1540.     }
  1541.  
  1542.     /******************************************************************/
  1543.     /* All updates have now been made, adjust the number of regular   */
  1544.     /* states to include the new SP states.                           */
  1545.     /******************************************************************/
  1546.     num_states = max_sp_state;
  1547.  
  1548.     /******************************************************************/
  1549.     /* Free all temporary space allocated earlier.                    */
  1550.     /******************************************************************/
  1551.     ffree(sp_rules);
  1552.     ffree(stack);
  1553.     ffree(index_of);
  1554.     ffree(next_rule);
  1555.     ffree(rule_list);
  1556.     ffree(symbol_list);
  1557.     ffree(shift_transition);
  1558.     ffree(rule_count);
  1559.     ffree(new_shift);
  1560.     ffree(look_ahead);
  1561.     for ALL_SYMBOLS(i)
  1562.     {
  1563.         if (sp_action[i] != NULL)
  1564.         {
  1565.             ffree(sp_action[i]);
  1566.         }
  1567.     }
  1568.     ffree(sp_action);
  1569.     ffree(is_conflict_symbol);
  1570.     ffree(sp_table);
  1571.     ffree(new_action);
  1572.     ffree(update_action);
  1573.  
  1574.     return;
  1575. }
  1576.