home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / jikepg12.zip / jikespg / src / resolve.c < prev    next >
C/C++ Source or Header  |  1999-11-04  |  105KB  |  2,562 lines
  1. /* $Id: resolve.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. /***********************************************************************/
  17. /* VISITED is a structure used to mark state-symbol pairs that have    */
  18. /* been visited in the process of computing follow-sources for a       */
  19. /* given action in conflict.                                           */
  20. /* The field MAP is an array indexable by the states 1..NUM_STATES;    */
  21. /* each element of which points to a set (list) of symbols. Thus, for  */
  22. /* a given state S, and for all symbol X in the list MAP[S], [S,X]     */
  23. /* has been visited. For efficiency, the fields LIST and ROOT are used */
  24. /* to store the set (list) of indexed elements of MAP that are not     */
  25. /* NULL.                                                               */
  26. /* See routines MARK_VISITED, WAS_VISITED, CLEAR_VISITED,              */
  27. /*              INIT_LALRK_PROCESS, EXIT_PROCESS                       */
  28. /***********************************************************************/
  29. static struct visited_element
  30. {
  31.     struct node **map;
  32.     short        *list,
  33.                   root;
  34. } visited;
  35.  
  36. /***********************************************************************/
  37. /* Given a set of actions that are in conflict on a given symbol, the  */
  38. /* structure SOURCES_ELEMENT is used to store a mapping from each      */
  39. /* such action into a set of configurations that can be reached        */
  40. /* following execution of the action in question up to the point where */
  41. /* the automaton is about to shift the conflict symbol.                */
  42. /* The field CONFIGS is an array indexable by actions which are        */
  43. /* encoded as follows:                                                 */
  44. /*    1. shift-reduce  [-NUM_RULES..-1]                                */
  45. /*    2. reduce        [0..NUM_RULES]                                  */
  46. /*    3. shift         [NUM_RULES+1..NUM_STATES+1].                    */
  47. /* Each element of CONFIGS points to a set (sorted list) of            */
  48. /* configurations.  For efficiency, the fields LIST and ROOT are used  */
  49. /* to store the set (list) of indexed elements of CONFIGS that are not */
  50. /* NULL.                                                               */
  51. /* See routines ALLOCATE_SOURCES, FREE_SOURCES, CLEAR_SOURCES,         */
  52. /*              ADD_CONFIGS, UNION_CONFIG_SETS.                        */
  53. /* See STATE_TO_RESOLVE_CONFLICTS for an explanation of STACK_SEEN.    */
  54. /*                                                                     */
  55. /* A configuration is a stack of states that represents a certain path */
  56. /* in the automaton. The stack is implemented as a list of             */
  57. /* STACK_ELEMENT nodes linked through the field PREVIOUS.              */
  58. /* A set/list of configurations is linked through the field NEXT.      */
  59. /* When attempting to resolve conflicts we try to make sure that the   */
  60. /* set of configurations associated with each action is unique. This   */
  61. /* is achieved by throwing these configurations into a set and making  */
  62. /* sure that there are no duplicates. The field LINK is used for that  */
  63. /* purpose (see routine STACK_WAS_SEEN). The field STATE_NUMBER is     */
  64. /* obviously used to store the number of a state in the automaton. The */
  65. /* field SIZE holds index of the node within the stack. Thus, for the  */
  66. /* first element of the stack this field represents the number of      */
  67. /* elements in the stack; for the last element, this field holds the   */
  68. /* value 1.                                                            */
  69. /* See routines ALLOCATE_STACK_ELEMENT, FREE_STACK_ELEMENT,            */
  70. /*              ADD_DANGLING_STACK, FREE_DANGLING_STACK.               */
  71. /***********************************************************************/
  72. static struct sources_element
  73. {
  74.     struct stack_element **configs,
  75.                          **stack_seen;
  76.     short                 *list,
  77.                            root;
  78. } sources;
  79.  
  80. struct stack_element
  81. {
  82.     struct stack_element *previous,
  83.                          *next,
  84.                          *link;
  85.     short                 state_number,
  86.                           size;
  87. };
  88. static struct stack_element *stack_pool = NULL,
  89.                             *dangling_stacks = NULL;
  90.  
  91. /***********************************************************************/
  92. /* The structure STATE_ELEMENT is used to construct lookahead states.  */
  93. /* LA_STATE_ROOT point to a list of lookahead states using the LINK    */
  94. /* field. The field NEXT_SHIFT is used to hash the new shift maps      */
  95. /* associated with lookahead states. The field IN_STATE identifies the */
  96. /* state that shifted into the lookahead state in question. The field  */
  97. /* SYMBOL identifies the symbol on shift the transition was made into  */
  98. /* the lookahead state in question.  The remaining fields are          */
  99. /* self-explanatory.                                                   */
  100. /***********************************************************************/
  101. struct state_element
  102. {
  103.     struct state_element      *link,
  104.                               *next_shift;
  105.     struct reduce_header_type  reduce;
  106.     struct shift_header_type   shift;
  107.     short                      in_state,
  108.                                symbol,
  109.                                state_number,
  110.                                shift_number;
  111. };
  112. static struct state_element *la_state_root = NULL;
  113.  
  114. /***********************************************************************/
  115. /* The structures SR_CONFLICT_ELEMENT and RR_CONFLICT_ELEMENT are used */
  116. /* th store conflict information. CONFLICT_ELEMENT_POOL is used to     */
  117. /* keep track of a pool conflict element structures (SR or RR) that    */
  118. /* are available for allocation.                                       */
  119. /* See routines ALLOCATE_CONFLICT_ELEMENT and FREE_CONFLICT_ELEMENTS.  */
  120. /***********************************************************************/
  121. struct sr_conflict_element
  122. {
  123.     struct sr_conflict_element *next;
  124.     short                       state_number,
  125.                                 item,
  126.                                 symbol;
  127. };
  128. static struct sr_conflict_element *sr_conflict_root;
  129.  
  130. struct rr_conflict_element
  131. {
  132.     struct rr_conflict_element *next;
  133.     short                       symbol,
  134.                                 item1,
  135.                                 item2;
  136. };
  137. static struct rr_conflict_element *rr_conflict_root;
  138. static void *conflict_element_pool = NULL;
  139.  
  140. /***********************************************************************/
  141. /* NT_ITEMS and ITEM_LIST are used to construct a mapping from each    */
  142. /* nonterminal into the set of items of which the nonterminal in       */
  143. /* question is the dot symbol. See CONFLICTS_INITIALIZATION.           */
  144. /***********************************************************************/
  145. static short *nt_items  = NULL,
  146.              *item_list = NULL;
  147.  
  148. /***********************************************************************/
  149. /* LALR_VISITED is used to keep track of (state, nonterminal) pairs    */
  150. /* that are visited in tracing the path of a lalr conflict.SLR_VISITED */
  151. /* is similarly used to keep track of nonterminal symbols that are     */
  152. /* visited in tracing the path of an slr conflict. SYMBOL_SEEN is used */
  153. /* to keep track of nonterminal symbols that are visited in tracing a  */
  154. /* path to the start state (root).                                     */
  155. /*                                                                     */
  156. /* CYCLIC is a boolean vector used to identify states that can enter   */
  157. /* a cycle of transitions on nullable nonterminals.                    */
  158. /* As the computation of CYCLIC requires a modified version of the     */
  159. /* digraph algorithm, the variables STACK, INDEX_OF and TOP are used   */
  160. /* for that algorithm.                                                 */
  161. /*                                                                     */
  162. /* RMPSELF is a boolean vector that indicates whether or not a given   */
  163. /* non-terminal can right-most produce itself. It is only constructed  */
  164. /* when LALR_LEVEL > 1.                                                */
  165. /***********************************************************************/
  166. static BOOLEAN *lalr_visited,
  167.                *slr_visited,
  168.                *symbol_seen,
  169.                *cyclic,
  170.                *rmpself;
  171.  
  172. static short *stack,
  173.              *index_of,
  174.               top;
  175.  
  176. static struct state_element **shift_table;
  177.  
  178. /*******************************************************************/
  179. /*                     ALLOCATE_CONFLICT_ELEMENT:                  */
  180. /*******************************************************************/
  181. /* This function allocates a conflict_element (sr or rr) structure */
  182. /* & returns a pointer to it. If there are nodes in the free pool, */
  183. /* one of them is returned. Otherwise, a new node is allocated     */
  184. /* from the temporary storage pool.                                */
  185. /*******************************************************************/
  186. static void *allocate_conflict_element(void)
  187. {
  188.     void *p;
  189.  
  190.     p = conflict_element_pool;
  191.     if (p != NULL)
  192.         conflict_element_pool = ((struct sr_conflict_element *) p) -> next;
  193.     else
  194.     {
  195.         p = (void *) talloc(MAX(sizeof(struct sr_conflict_element),
  196.                             sizeof(struct rr_conflict_element)));
  197.         if (p == NULL)
  198.             nospace(__FILE__, __LINE__);
  199.     }
  200.  
  201.     return p;
  202. }
  203.  
  204.  
  205. /**********************************************************************/
  206. /*                         FREE_CONFLICT_ELEMENTS:                    */
  207. /**********************************************************************/
  208. /* This routine returns a list of conflict_element (sr/rr)structures  */
  209. /* to the free pool.                                                  */
  210. /**********************************************************************/
  211. static void free_conflict_elements(void *head, void *tail)
  212. {
  213.     ((struct sr_conflict_element *) tail) -> next =
  214.              (struct sr_conflict_element *) conflict_element_pool;
  215.     conflict_element_pool = head;
  216.  
  217.     return;
  218. }
  219.  
  220.  
  221. /*******************************************************************/
  222. /*                      ALLOCATE_STACK_ELEMENT:                    */
  223. /*******************************************************************/
  224. /* This function allocates a stack_element structure and returns a */
  225. /* pointer to it. If there are nodes in the free pool, one of them */
  226. /* is returned. Otherwise, a new node is allocated from the        */
  227. /* temporary storage pool.                                         */
  228. /*******************************************************************/
  229. static struct stack_element *allocate_stack_element(void)
  230. {
  231.     struct stack_element *p;
  232.  
  233.     p = stack_pool;
  234.     if (p != NULL)
  235.         stack_pool = p -> next;
  236.     else
  237.     {
  238.         p = (struct stack_element *)
  239.             talloc(sizeof(struct stack_element));
  240.         if (p == NULL)
  241.             nospace(__FILE__, __LINE__);
  242.     }
  243.  
  244.     return p;
  245. }
  246.  
  247.  
  248. /**********************************************************************/
  249. /*                           FREE_STACK_ELEMENTS:                     */
  250. /**********************************************************************/
  251. /* This routine returns a list of stack_element structures to the     */
  252. /* free pool.                                                         */
  253. /**********************************************************************/
  254. static void free_stack_elements(struct stack_element *head,
  255.                                 struct stack_element *tail)
  256. {
  257.     tail -> next = stack_pool;
  258.     stack_pool = head;
  259.  
  260.     return;
  261. }
  262.  
  263.  
  264. /***************************************************************************/
  265. /*                        ADD_DANGLING_STACK_ELEMENT:                      */
  266. /***************************************************************************/
  267. /* When an allocated stack_element structure is not directly associated    */
  268. /* with an action, it is added to a circular list of dangling stack_element*/
  269. /* nodes so that its space can be reclaimed.                               */
  270. /***************************************************************************/
  271. static void add_dangling_stack_element(struct stack_element *s)
  272. {
  273.     if (dangling_stacks == NULL)
  274.         s -> next = s;
  275.     else
  276.     {
  277.         s -> next = dangling_stacks -> next;
  278.         dangling_stacks -> next = s;
  279.     }
  280.     dangling_stacks = s;
  281.  
  282.     return;
  283. }
  284.  
  285.  
  286. /***************************************************************************/
  287. /*                       FREE_DANGLING_STACK_ELEMENTS:                     */
  288. /***************************************************************************/
  289. /* This function is invoked to free up all dangling stack_element nodes    */
  290. /* and reset the dangling stack list.                                      */
  291. /* Recall that the dangling stack list is circular.                        */
  292. /***************************************************************************/
  293. static void free_dangling_stack_elements(void)
  294. {
  295.     struct stack_element *tail;
  296.  
  297.     if (dangling_stacks != NULL)
  298.     {
  299.         tail = dangling_stacks;
  300.         free_stack_elements(dangling_stacks -> next, tail);
  301.  
  302.         dangling_stacks = NULL;
  303.     }
  304.  
  305.     return;
  306. }
  307.  
  308.  
  309. /***************************************************************************/
  310. /*                              ALLOCATE_SOURCES:                          */
  311. /***************************************************************************/
  312. /* This function allocates and initializes a SOURCE_ELEMENT map.           */
  313. /* See definition of SOURCE_ELEMENT above.                                 */
  314. /***************************************************************************/
  315. static struct sources_element allocate_sources(void)
  316. {
  317.     struct sources_element sources;
  318.  
  319.     sources.configs = (struct stack_element **)
  320.                       calloc(num_rules + num_rules + num_states + 1,
  321.                              sizeof(struct stack_element *));
  322.     if (sources.configs == NULL)
  323.         nospace(__FILE__, __LINE__);
  324.     sources.configs += num_rules;
  325.  
  326.     sources.stack_seen = (struct stack_element **)
  327.                          calloc(STATE_TABLE_SIZE,
  328.                                 sizeof(struct stack_element *));
  329.     if (sources.stack_seen == NULL)
  330.         nospace(__FILE__, __LINE__);
  331.  
  332.     sources.list =
  333.         Allocate_short_array(num_rules + num_rules + num_states + 1);
  334.     sources.list += num_rules;
  335.  
  336.     sources.root = NIL;
  337.  
  338.     return sources;
  339. }
  340.  
  341.  
  342. /***************************************************************************/
  343. /*                               CLEAR_SOURCES:                            */
  344. /***************************************************************************/
  345. /* This function takes as argument a SOURCES_ELEMENT structure which it    */
  346. /* resets to the empty map.                                                */
  347. /* See definition of SOURCE_ELEMENT above.                                 */
  348. /***************************************************************************/
  349. static struct sources_element clear_sources(struct sources_element sources)
  350. {
  351.     struct stack_element *p,
  352.                          *tail;
  353.     int act,
  354.         i;
  355.  
  356.     for (act = sources.root; act != NIL; act = sources.list[act])
  357.     {
  358.         for (p = sources.configs[act]; p != NULL; tail = p, p = p -> next)
  359.             ;
  360.         free_stack_elements(sources.configs[act], tail);
  361.         sources.configs[act] = NULL;
  362.     }
  363.  
  364.     sources.root = NIL;
  365.  
  366.     return sources;
  367. }
  368.  
  369.  
  370. /***************************************************************************/
  371. /*                               FREE_SOURCES:                             */
  372. /***************************************************************************/
  373. /* This function takes as argument a SOURCES_ELEMENT structure. First, it  */
  374. /* clears it to reclaim all space that was used by STACK_ELEMENTs and then */
  375. /* it frees the array space used as a base to construct the map.           */
  376. /***************************************************************************/
  377. static void free_sources(struct sources_element sources)
  378. {
  379.     sources = clear_sources(sources);
  380.  
  381.     sources.configs -= num_rules;
  382.     ffree(sources.configs);
  383.  
  384.     ffree(sources.stack_seen);
  385.  
  386.     sources.list -= num_rules;
  387.     ffree(sources.list);
  388.  
  389.     return;
  390. }
  391.  
  392.  
  393. /***************************************************************************/
  394. /*                             UNION_CONFIG_SETS:                          */
  395. /***************************************************************************/
  396. /* This function takes as argument two pointers to sorted lists of stacks. */
  397. /* It merges the lists in the proper order and returns the resulting list. */
  398. /***************************************************************************/
  399. static struct stack_element *union_config_sets(struct stack_element *root1,
  400.                                                struct stack_element *root2)
  401. {
  402.     struct stack_element *p1,
  403.                          *p2,
  404.                          *root,
  405.                          *tail;
  406.  
  407.     root = NULL;
  408.  
  409.     /*******************************************************************/
  410.     /* This loop iterates over both lists until one (or both) has been */
  411.     /* completely processed. Each time around the loop, a stack is     */
  412.     /* removed from one of the lists and possibly added to the new     */
  413.     /* list. The new list is initially kept as a circular list to      */
  414.     /* preserve the sorted ordering in which elements are added to it. */
  415.     /*******************************************************************/
  416.     while (root1 != NULL && root2 != NULL)
  417.     {
  418.         /***************************************************************/
  419.         /* Compare the two stacks in front of the lists for equality.  */
  420.         /* We exit this loop when we encounter the end of one (or both)*/
  421.         /* of the stacks or two elements in them that are not the same.*/
  422.         /***************************************************************/
  423.         for (p1 = root1, p2 = root2;
  424.              p1 != NULL && p2 != NULL;
  425.              p1 = p1 -> previous, p2 = p2 -> previous)
  426.         {
  427.             if (p1 -> state_number != p2 -> state_number)
  428.                 break;
  429.         }
  430.  
  431.         /***************************************************************/
  432.         /* We now have 3 cases to consider:                            */
  433.         /*    1. The two stacks are equal? Discard one!                */
  434.         /*    2. List 1 stack is prefix of list 2 stack (p1 == NULL)?  */
  435.         /*       or list 1 stack is less than list 2 stack?            */
  436.         /*       Remove list 1 stack and add it to new list.           */
  437.         /*    3. List 2 stack is either a prefix of list 1 stack, or   */
  438.         /*       it is smaller!                                        */
  439.         /*       Remove list 2 stack and add it to new list.           */
  440.         /***************************************************************/
  441.         if (p1 == p2) /* are both p1 and p2 NULL? */
  442.         {
  443.             p2 = root2;
  444.             root2 = root2 -> next;
  445.             add_dangling_stack_element(p2);
  446.         }
  447.         else if ((p1 == NULL) ||
  448.                 ((p2 != NULL) && (p1 -> state_number < p2 -> state_number)))
  449.         {
  450.             p1 = root1;
  451.             root1 = root1 -> next;
  452.  
  453.             if (root == NULL)
  454.                 p1 -> next = p1;
  455.             else
  456.             {
  457.                 p1 -> next = root -> next;
  458.                 root -> next = p1;
  459.             }
  460.             root = p1;
  461.         }
  462.         else
  463.         {
  464.             p2 = root2;
  465.             root2 = root2 -> next;
  466.  
  467.             if (root == NULL)
  468.                 p2 -> next = p2;
  469.             else
  470.             {
  471.                 p2 -> next = root -> next;
  472.                 root -> next = p2;
  473.             }
  474.             root = p2;
  475.         }
  476.     }
  477.  
  478.     /*******************************************************************/
  479.     /* At this stage, at least one (or both) list has been expended    */
  480.     /* (or was empty to start with).                                   */
  481.     /* If the new list is not empty, turn it into a linear list and    */
  482.     /* append the unexpended list to it, if any.                       */
  483.     /* Otherwise, set the new list to the nonempty list if any!        */
  484.     /*******************************************************************/
  485.     if (root != NULL)
  486.     {
  487.         tail = root;
  488.         root = root -> next;
  489.         tail -> next = (root1 == NULL ? root2 : root1);
  490.     }
  491.     else root = (root1 == NULL ? root2 : root1);
  492.  
  493.     return root;
  494. }
  495.  
  496.  
  497. /***************************************************************************/
  498. /*                                ADD_CONFIGS:                             */
  499. /***************************************************************************/
  500. /* This function takes as argument a SOURCES_ELEMENT map, an ACTION and a  */
  501. /* set (sorted list) of configurations. It adds the set of configurations  */
  502. /* to the previous set of configurations associated with the ACTION in the */
  503. /* SOURCES_ELEMENT map.                                                    */
  504. /***************************************************************************/
  505. static struct sources_element add_configs(struct sources_element sources,
  506.                                           int action,
  507.                                           struct stack_element *config_root)
  508. {
  509.     if (config_root == NULL) /* The new set is empty? Do nothing */
  510.         return sources;
  511.  
  512.     if (sources.configs[action] == NULL) /* The previous was empty? */
  513.     {
  514.         sources.list[action] = sources.root;
  515.         sources.root = action;
  516.     }
  517.  
  518.     sources.configs[action] = union_config_sets(sources.configs[action],
  519.                                                 config_root);
  520.  
  521.     return sources;
  522. }
  523.  
  524.  
  525.  
  526. /***************************************************************************/
  527. /*                               CLEAR_VISITED:                            */
  528. /***************************************************************************/
  529. /* This function clears out all external space used by the VISITED set and */
  530. /* resets VISITED to the empty set.                                        */
  531. /***************************************************************************/
  532. static void clear_visited(void)
  533. {
  534.     struct node *p,
  535.                 *tail;
  536.     int state_no;
  537.  
  538.     for (state_no = visited.root;
  539.          state_no != NIL; state_no = visited.list[state_no])
  540.     {
  541.         for (p = visited.map[state_no]; p != NULL; tail = p, p = p -> next)
  542.             ;
  543.         free_nodes(visited.map[state_no], tail);
  544.         visited.map[state_no] = NULL;
  545.     }
  546.  
  547.     visited.root = NIL;
  548.  
  549.     return;
  550. }
  551.  
  552. /***************************************************************************/
  553. /*                                WAS_VISITED:                             */
  554. /***************************************************************************/
  555. /* This boolean function checks whether or not a given pair [state, symbol]*/
  556. /* was already inserted in the VISITED set.                                */
  557. /***************************************************************************/
  558. static BOOLEAN was_visited(int state_no, int symbol)
  559. {
  560.     struct node *p;
  561.  
  562.     for (p = visited.map[state_no]; p != NULL; p = p -> next)
  563.     {
  564.         if (p -> value == symbol)
  565.             break;
  566.     }
  567.  
  568.     return (p != NULL);
  569. }
  570.  
  571.  
  572. /***************************************************************************/
  573. /*                               MARK_VISITED:                             */
  574. /***************************************************************************/
  575. /* This function inserts a given pair [state, symbol] into the VISITED set.*/
  576. /***************************************************************************/
  577. static void mark_visited(int state_no, int symbol)
  578. {
  579.     struct node *p;
  580.  
  581.     if (visited.map[state_no] == NULL) /* 1st time we see state_no? */
  582.     {
  583.         visited.list[state_no] = visited.root;
  584.         visited.root = state_no;
  585.     }
  586.  
  587.     p = Allocate_node();
  588.     p -> value = symbol;
  589.     p -> next = visited.map[state_no];
  590.     visited.map[state_no] = p;
  591.  
  592.     return;
  593. }
  594.  
  595.  
  596. /***********************************************************************/
  597. /*                             COMPUTE_CYCLIC:                         */
  598. /***********************************************************************/
  599. /* This procedure is a modified instantiation of the digraph algorithm */
  600. /* to compute the CYCLIC set of states.                                */
  601. /***********************************************************************/
  602. static void compute_cyclic(short state_no)
  603. {
  604.     int indx;
  605.     struct goto_header_type go_to;
  606.     int symbol,
  607.         act,
  608.         i;
  609.  
  610.     stack[++top] = state_no;
  611.     indx = top;
  612.     cyclic[state_no] = FALSE;
  613.     index_of[state_no] = indx;
  614.  
  615.     go_to = statset[state_no].go_to;
  616.     for (i = 1; i <= go_to.size; i++)
  617.     {
  618.         symbol = GOTO_SYMBOL(go_to, i);
  619.         act = GOTO_ACTION(go_to, i);
  620.         if (act > 0 && null_nt[symbol])
  621.         {   /* We have a transition on a nullable nonterminal? */
  622.             if (index_of[act] == OMEGA)
  623.                 compute_cyclic(act);
  624.             else if (index_of[act] != INFINITY)
  625.                 cyclic[state_no] = TRUE;
  626.             cyclic[state_no] = cyclic[state_no] || cyclic[act];
  627.  
  628.             index_of[state_no] = MIN(index_of[state_no], index_of[act]);
  629.         }
  630.     }
  631.  
  632.     if (index_of[state_no] == indx)
  633.     {
  634.         do
  635.         {
  636.             act = stack[top--];
  637.             index_of[act] = INFINITY;
  638.         } while(act != state_no);
  639.     }
  640.  
  641.     return;
  642. }
  643.  
  644.  
  645. /***********************************************************************/
  646. /*                           TRACE_ROOT:                               */
  647. /***********************************************************************/
  648. /*    In tracing an error, we will be moving backward in the state     */
  649. /* automaton looking for items with the conflict symbol as look-ahead. */
  650. /* In the case of SLR, we may have to analoguously look at an          */
  651. /* arbitrary set of items involved.  In moving around these graphs, it */
  652. /* is possible to encounter a cycle, in which case, we simply want to  */
  653. /* back out of the cycle and try another path. We therefore need to    */
  654. /* keep track of which nodes have already been visited.  For LALR      */
  655. /* conflicts, we use the LA_PTR field of the GOTO_ELEMENTs as an index */
  656. /* to a BOOLEAN array LALR_VISITED.  For SLR conflicts, a boolean      */
  657. /* array, SLR_VISITED, indexable by non-terminals, is used.  For       */
  658. /* trace-backs to the root item, the boolean array SYMBOL_SEEN, also   */
  659. /* also indexable by non-terminals, is used.                           */
  660. /***********************************************************************/
  661. static BOOLEAN trace_root(int lhs_symbol)
  662. {
  663.     int item;
  664.  
  665.     if (lhs_symbol == accept_image)
  666.         return(TRUE);
  667.  
  668.     if (symbol_seen[lhs_symbol])
  669.         return(FALSE);
  670.  
  671.     symbol_seen[lhs_symbol] = TRUE;
  672.     for (item = nt_items[lhs_symbol]; item != NIL; item = item_list[item])
  673.     {
  674.         if (trace_root(rules[item_table[item].rule_number].lhs))
  675.         {
  676.             print_item(item);
  677.             return(TRUE);
  678.         }
  679.     }
  680.  
  681.     return(FALSE);
  682. }
  683.  
  684.  
  685. /***********************************************************************/
  686. /*                             PRINT_ROOT_PATH:                        */
  687. /***********************************************************************/
  688. /* The procedure below is invoked to retrace a path from the initial   */
  689. /* item to a given item (ITEM_NO) passed to it as argument.            */
  690. /***********************************************************************/
  691. static void print_root_path(int item_no)
  692. {
  693.     symbol_seen = Allocate_boolean_array(num_non_terminals);
  694.     symbol_seen -= (num_terminals + 1);
  695.  
  696.     if (trace_root(rules[item_table[item_no].rule_number].lhs))
  697.     {
  698.         fprintf(syslis, "\n"); /* Leave one blank line after root trace. */
  699.         ENDPAGE_CHECK;
  700.     }
  701.  
  702.     symbol_seen += (num_terminals + 1);
  703.     ffree(symbol_seen);
  704.  
  705.     return;
  706. }
  707.  
  708.  
  709. /***********************************************************************/
  710. /*                          LALR_PATH_RETRACED:                        */
  711. /***********************************************************************/
  712. /* This procedure takes as argument, a state number, STATE_NO, an      */
  713. /* index into the goto map of state_no, GOTO_INDX, which identifies a  */
  714. /* starting point for a search for the CONFLICT_SYMBOL. It attempts to */
  715. /* find a path in the automaton (from the starting point) that leads   */
  716. /* to a state where the conflict symbol can be read. If a path is      */
  717. /* found, all items along the path are printed and SUCCESS is returned.*/
  718. /*  Otherwise, FAILURE is returned.                                    */
  719. /***********************************************************************/
  720. static BOOLEAN lalr_path_retraced(int state_no,
  721.                                   int goto_indx,
  722.                                   int conflict_symbol)
  723. {
  724.     int symbol,
  725.         item,
  726.         state,
  727.         i;
  728.  
  729.     struct goto_header_type go_to;
  730.  
  731.     struct node *p,
  732.                 *q,
  733.                 *tail,
  734.                 *w;
  735.  
  736.     BOOLEAN found;
  737.  
  738.     go_to = statset[state_no].go_to;
  739.     lalr_visited[GOTO_LAPTR(go_to, goto_indx)] = TRUE;
  740.  
  741.     found = FALSE;
  742.  
  743.     state = GOTO_ACTION(go_to, goto_indx);
  744.     for (p = (state > 0 ? statset[state].kernel_items
  745.                         : adequate_item[-state]);
  746.          (p != NULL) && (! found); p = p -> next)
  747.     {
  748.         item = p -> value - 1;
  749.         if IS_IN_SET(first, item_table[item].suffix_index, conflict_symbol)
  750.         {   /* Conflict_symbol can be read in state? */
  751.             if (trace_opt == TRACE_FULL)
  752.                 print_root_path(item);
  753.             found = TRUE;
  754.         }
  755.         else if IS_IN_SET(first, item_table[item].suffix_index, empty)
  756.         {
  757.             symbol = rules[item_table[item].rule_number].lhs;
  758.             w = lpgaccess(state_no, item);
  759.             for (q = w; q != NULL; tail = q, q = q -> next)
  760.             {
  761.                 go_to = statset[q -> value].go_to;
  762.                 for (i = 1; GOTO_SYMBOL(go_to, i) != symbol; i++)
  763.                     ;
  764.  
  765.                 if (! lalr_visited[GOTO_LAPTR(go_to, i)])
  766.                 {
  767.                     if (lalr_path_retraced(q -> value, i, conflict_symbol))
  768.                     {
  769.                         found = TRUE;
  770.                         break;
  771.                     }
  772.                 }
  773.             }
  774.  
  775.             for (; q != NULL; tail = q, q = q -> next)
  776.                 ;
  777.             free_nodes(w, tail);
  778.         }
  779.     }
  780.  
  781.     if (found)
  782.         print_item(item);
  783.  
  784.     return(found);
  785. }
  786.  
  787.  
  788. /***********************************************************************/
  789. /*                      PRINT_RELEVANT_LALR_ITEMS:                     */
  790. /***********************************************************************/
  791. /*   In this procedure, we attempt to retrace an LALR conflict path    */
  792. /* (there may be more than one) of CONFLICT_SYMBOL in the state        */
  793. /* automaton that led to ITEM_NO in state STATE_NO.                    */
  794. /***********************************************************************/
  795. static void print_relevant_lalr_items(int state_no,
  796.                                       int item_no,
  797.                                       int conflict_symbol)
  798. {
  799.     int lhs_symbol,
  800.         i;
  801.  
  802.     struct node *p,
  803.                 *tail,
  804.                 *v;
  805.  
  806.     lhs_symbol = rules[item_table[item_no].rule_number].lhs;
  807.     if (lhs_symbol == accept_image)
  808.         return;
  809.  
  810.     lalr_visited = Allocate_boolean_array(la_top + 1);
  811.  
  812.     v = lpgaccess(state_no, item_no);
  813.     for (p = v; p != NULL; tail = p, p = p -> next)
  814.     {
  815.         struct goto_header_type go_to;
  816.  
  817.         go_to = statset[p -> value].go_to;
  818.         for (i = 1; GOTO_SYMBOL(go_to, i) != lhs_symbol; i++)
  819.             ;
  820.  
  821.         if (lalr_path_retraced(p -> value, i, conflict_symbol))
  822.             break;
  823.     }
  824.  
  825.     for (; p != NULL; tail = p, p = p -> next)
  826.         ;
  827.  
  828.     free_nodes(v, tail);
  829.  
  830.     ffree(lalr_visited);
  831.  
  832.     return;
  833. }
  834.  
  835.  
  836. /***********************************************************************/
  837. /*                              SLR_TRACE:                             */
  838. /***********************************************************************/
  839. /* The procedure below is invoked to retrace a path that may have      */
  840. /* introduced the CONFLICT_SYMBOL in the FOLLOW set of the nonterminal */
  841. /* that produces ITEM_NO.  Note that such a path must exist.           */
  842. /***********************************************************************/
  843. static BOOLEAN slr_trace(int lhs_symbol, int conflict_symbol)
  844. {
  845.     int item;
  846.  
  847.     if (slr_visited[lhs_symbol])
  848.         return(FALSE);
  849.  
  850.     slr_visited[lhs_symbol] = TRUE;
  851.  
  852.     for (item = nt_items[lhs_symbol]; item != NIL; item = item_list[item])
  853.     {
  854.         if IS_IN_SET(first, item_table[item].suffix_index, conflict_symbol)
  855.         {
  856.             if (trace_opt == TRACE_FULL)
  857.                 print_root_path(item);
  858.             break;
  859.         }
  860.         if IS_IN_SET(first, item_table[item].suffix_index, empty)
  861.         {
  862.             if (slr_trace(rules[item_table[item].rule_number].lhs,
  863.                           conflict_symbol))
  864.                 break;
  865.         }
  866.     }
  867.  
  868.     if (item != NIL)
  869.     {
  870.         print_item(item);
  871.         return(TRUE);
  872.     }
  873.     else
  874.         return(FALSE);
  875. }
  876.  
  877.  
  878. /***********************************************************************/
  879. /*                           PRINT_RELEVANT_SLR_ITEMS:                 */
  880. /***********************************************************************/
  881. /* This procedure is invoked to print an SLR path of items that leads  */
  882. /* to the conflict symbol.                                             */
  883. /***********************************************************************/
  884. static void print_relevant_slr_items(int item_no, int conflict_symbol)
  885. {
  886.     slr_visited = Allocate_boolean_array(num_non_terminals);
  887.     slr_visited -= (num_terminals + 1);
  888.  
  889.     if (slr_trace(rules[item_table[item_no].rule_number].lhs,
  890.                    conflict_symbol))
  891.         ;
  892.     slr_visited += (num_terminals + 1);
  893.     ffree(slr_visited);
  894.  
  895.     return;
  896. }
  897.  
  898.  
  899. /***********************************************************************/
  900. /*                       CONFLICTS_INITIALIZATION:                     */
  901. /***********************************************************************/
  902. /* This routine is invoked when a grammar contains conflicts, and the  */
  903. /* first conflict is detected.                                         */
  904. /***********************************************************************/
  905. static void conflicts_initialization(void)
  906. {
  907.     int i;
  908.  
  909.     /*******************************************************************/
  910.     /* NT_ITEMS and ITEM_LIST are used in reporting SLR conflicts, and */
  911.     /* in recreating paths from the Start item. See the routines       */
  912.     /* PRINT_RELEVANT_SLR_ITEMS and PRINT_ROOT_PATH.                   */
  913.     /*******************************************************************/
  914.     nt_items = Allocate_short_array(num_non_terminals);
  915.     nt_items -= (num_terminals + 1);
  916.     item_list = Allocate_short_array(num_items + 1);
  917.  
  918.     i = (PRINT_LINE_SIZE - 11) / 2 - 1;
  919.     PR_HEADING;
  920.     fill_in(msg_line, i, '-');
  921.     fprintf(syslis, "\n%s CONFLICTS %s\n", msg_line, msg_line);
  922.     output_line_no += 2;
  923.  
  924. /***********************************************************************/
  925. /*   SLR conflicts may be caused by a symbol in the FOLLOW set of a    */
  926. /* left hand side, which is not actually in the LALR look-ahead set in */
  927. /* that context.  Therefore, there may not exist a path in the state   */
  928. /* automaton from the state where the conflict was detected to another */
  929. /* state where it was introduced.  In such a case, we try to retrace a */
  930. /* path that contributed the conflict-symbol to the FOLLOW set via a   */
  931. /* sequence of productions.                                            */
  932. /*                                                                     */
  933. /* To assist in this task, we build below a map from each non-terminal */
  934. /* A to the set of items of which A is the dot SYMBOL. I.e., all items */
  935. /* of the form [x .A y] where x and y are arbitrary strings, and A is  */
  936. /* a non-terminal. This map is also used in retracing a path from the  */
  937. /* Start item to any other item.                                       */
  938. /***********************************************************************/
  939.     for ALL_NON_TERMINALS(i)
  940.         nt_items[i] = NIL;
  941.  
  942.     for ALL_ITEMS(i)
  943.     {
  944.         if (item_table[i].symbol IS_A_NON_TERMINAL)
  945.         {
  946.             item_list[i] = nt_items[item_table[i].symbol];
  947.             nt_items[item_table[i].symbol] =  i;
  948.         }
  949.     }
  950.  
  951.     return;
  952. }
  953.  
  954.  
  955. /***********************************************************************/
  956. /*                            PROCESS_CONFLICTS:                       */
  957. /***********************************************************************/
  958. /*   If conflicts are detected, tehy are placed in two lists headed by */
  959. /* SR_CONFLICT_ROOT and RR_CONFLICT_ROOT.  We scan these lists, and    */
  960. /* report the conflicts.                                               */
  961. /***********************************************************************/
  962. static void process_conflicts(int state_no)
  963. {
  964.     int symbol,
  965.         rule_no,
  966.         n;
  967.  
  968.     char temp[SYMBOL_SIZE + 1];
  969.  
  970.     if (nt_items == NULL)
  971.         conflicts_initialization();
  972.  
  973.     print_state(state_no); /* Print state containing conflicts */
  974.  
  975.     /*******************************************************************/
  976.     /* Process shift-reduce conflicts.                                 */
  977.     /*******************************************************************/
  978.     if (sr_conflict_root != NULL)
  979.     {
  980.         struct sr_conflict_element *p,
  981.                                    *tail;
  982.  
  983.         for (p = sr_conflict_root; p != NULL; tail = p, p = p -> next)
  984.         {
  985.             symbol = p -> symbol;
  986.             rule_no = item_table[p -> item].rule_number;
  987.  
  988.             restore_symbol(temp, RETRIEVE_STRING(symbol));
  989.             printf("*** Shift/reduce conflict on \"%s\" with rule %d\n",
  990.                    temp, rule_no);
  991.             fprintf(syslis,
  992.                     "\n*** Shift/reduce conflict on \"%s\" with rule %d\n",
  993.                     temp, rule_no);
  994.  
  995.             if (trace_opt != NOTRACE)
  996.             {
  997.                 if (! slr_bit)
  998.                     print_relevant_lalr_items(state_no, p -> item, symbol);
  999.                 else
  1000.                     print_relevant_slr_items(p -> item, symbol);
  1001.                 print_item(p -> item);
  1002.             }
  1003.         }
  1004.  
  1005.         free_conflict_elements(sr_conflict_root, tail);
  1006.     }
  1007.  
  1008.     /*******************************************************************/
  1009.     /* Process reduce-reduce conflicts.                                */
  1010.     /*******************************************************************/
  1011.     if (rr_conflict_root != NULL)
  1012.     {
  1013.         struct rr_conflict_element *p,
  1014.                                    *tail;
  1015.  
  1016.         for (p = rr_conflict_root; p != NULL; tail = p, p = p -> next)
  1017.         {
  1018.             symbol = p -> symbol;
  1019.             n = item_table[p -> item1].rule_number;
  1020.             rule_no = item_table[p -> item2].rule_number;
  1021.  
  1022.             restore_symbol(temp, RETRIEVE_STRING(symbol));
  1023.             printf("*** Reduce/reduce conflict "
  1024.                    "on \"%s\" between rule %d and %d\n",
  1025.                    temp, n, rule_no);
  1026.             fprintf(syslis,
  1027.                     "\n*** Reduce/reduce conflict "
  1028.                     "on \"%s\" between rule %d and %d\n",
  1029.                     temp, n, rule_no);
  1030.             output_line_no +=2;
  1031.             if (trace_opt != NOTRACE)
  1032.             {
  1033.                 if (! slr_bit)
  1034.                     print_relevant_lalr_items(state_no, p -> item1, symbol);
  1035.                 else
  1036.                     print_relevant_slr_items(p -> item1, symbol);
  1037.                 print_item(p -> item1);
  1038.                 fill_in(msg_line, PRINT_LINE_SIZE - 3, '-');
  1039.                 fprintf(syslis,"\n%s",msg_line);
  1040.                 ENDPAGE_CHECK;
  1041.                 if (! slr_bit)
  1042.                     print_relevant_lalr_items(state_no, p -> item2, symbol);
  1043.                 else
  1044.                     print_relevant_slr_items(p -> item2, symbol);
  1045.                 print_item(p -> item2);
  1046.             }
  1047.         }
  1048.  
  1049.         free_conflict_elements(rr_conflict_root, tail);
  1050.     }
  1051.  
  1052.     return;
  1053. }
  1054.  
  1055.  
  1056. /***********************************************************************/
  1057. /*                           ADD_CONFLICT_SYMBOL:                      */
  1058. /***********************************************************************/
  1059. /* Add SYMBOL to the set of symbols CONFLICT_SYMBOLS[STATE_NO].        */
  1060. /***********************************************************************/
  1061. static void add_conflict_symbol(int state_no, int symbol)
  1062. {
  1063.     struct node *p;
  1064.  
  1065.     p = Allocate_node();
  1066.     p -> value = symbol;
  1067.     if (conflict_symbols[state_no] == NULL)
  1068.         p -> next = p;
  1069.     else
  1070.     {
  1071.         p -> next = conflict_symbols[state_no] -> next;
  1072.         conflict_symbols[state_no] -> next = p;
  1073.     }
  1074.     conflict_symbols[state_no] = p;
  1075.  
  1076.     return;
  1077. }
  1078.  
  1079.  
  1080. /***********************************************************************/
  1081. /*                             FOLLOW_SOURCES:                         */
  1082. /***********************************************************************/
  1083. /* This function takes as argument a configuration STACK, a SYMBOL on  */
  1084. /* which a transition can be made in the configuration and a terminal  */
  1085. /* lookahead symbol, LA_SYMBOL. It executes the transition on SYMBOL   */
  1086. /* and simulates all paths taken in the automaton after that transition*/
  1087. /* until new state(s) are reached where a transition is possible on    */
  1088. /* the lookahead symbol. It then returns the new set of configurations */
  1089. /* found on which a transition on LA_SYMBOL is possible.               */
  1090. /***********************************************************************/
  1091. static struct stack_element *follow_sources(struct stack_element *stack,
  1092.                                             int symbol, int la_symbol)
  1093. {
  1094.     struct shift_header_type sh;
  1095.     struct goto_header_type  go_to;
  1096.  
  1097.     struct stack_element *configs,
  1098.                          *q;
  1099.     struct node *item_ptr;
  1100.  
  1101.     int item_no,
  1102.         state_no,
  1103.         rule_no,
  1104.         lhs_symbol,
  1105.         act,
  1106.         i;
  1107.  
  1108.     configs = NULL; /* Initialize the output set of configurations */
  1109.  
  1110.     /*******************************************************************/
  1111.     /* If the starting configuration consists of a single state and    */
  1112.     /* the initial [state, symbol] pair has already been visited,      */
  1113.     /* return the null set. Otherwise, mark the pair visited and ...   */
  1114.     /*******************************************************************/
  1115.     state_no = stack -> state_number;
  1116.     if (stack -> size == 1)
  1117.     {
  1118.         if (was_visited(state_no, symbol) ||
  1119.             (state_no == 1 && symbol == accept_image))
  1120.             return configs;
  1121.  
  1122.         mark_visited(state_no, symbol);
  1123.     }
  1124.  
  1125.     /*******************************************************************/
  1126.     /* Find the transition defined on the symbol...                    */
  1127.     /* If the SYMBOL is a nonterminal and we can determine that the    */
  1128.     /* lookahead symbol (LA_SYMBOL) cannot possibly follow the         */
  1129.     /* nonterminal in question in this context, we simply abandon the  */
  1130.     /* search and return the NULL set.                                 */
  1131.     /*******************************************************************/
  1132.     if (symbol IS_A_NON_TERMINAL)
  1133.     {
  1134.         go_to = statset[state_no].go_to;
  1135.         for (i = 1; GOTO_SYMBOL(go_to, i) != symbol; i++)
  1136.             ;
  1137.         if (la_index[GOTO_LAPTR(go_to, i)] == OMEGA)
  1138.         {
  1139.             int stack_top = 0;
  1140.             la_traverse(state_no, i, &stack_top);
  1141.         }
  1142.  
  1143.         if (! IS_IN_SET(la_set, GOTO_LAPTR(go_to, i), la_symbol))
  1144.             return configs;
  1145.  
  1146.         act = GOTO_ACTION(go_to, i);
  1147.     }
  1148.     else
  1149.     {
  1150.         sh = shift[statset[state_no].shift_number];
  1151.         for (i = 1; SHIFT_SYMBOL(sh, i) != symbol; i++)
  1152.             ;
  1153.         act = SHIFT_ACTION(sh, i);
  1154.     }
  1155.  
  1156.     /*******************************************************************/
  1157.     /* If the ACTion on the symbol is a shift or a goto, ...           */
  1158.     /*******************************************************************/
  1159.     if (act > 0)
  1160.     {
  1161.         /***************************************************************/
  1162.         /* We check to see if the new state contains an action on the  */
  1163.         /* lookahead symbol. If that's the case then we create a new   */
  1164.         /* configuration by appending ACT to the starting configuration*/
  1165.         /* and add this newly formed configuration to the set(list) of */
  1166.         /* configurations...                                           */
  1167.         /***************************************************************/
  1168.         sh = shift[statset[act].shift_number];
  1169.         for (i = 1; i <= sh.size; i++)
  1170.         {
  1171.             if (SHIFT_SYMBOL(sh, i) == la_symbol)
  1172.                 break;
  1173.         }
  1174.         if (i <= sh.size) /* there is a transition on la_symbol in act */
  1175.         {
  1176.             q = allocate_stack_element();
  1177.             q -> state_number = act;
  1178.             q -> size = stack -> size + 1;
  1179.             q -> previous = stack;
  1180.             q -> next = NULL;
  1181.  
  1182.             configs = q;
  1183.         }
  1184.  
  1185.         /***************************************************************/
  1186.         /* If the new state cannot get into a cycle of null            */
  1187.         /* transitions, we check to see if it contains any transition  */
  1188.         /* on a nullable nonterminal. For each such transition, we     */
  1189.         /* append the new state to the stack and recursively invoke    */
  1190.         /* FOLLOW_SOURCES to check if a transition on LA_SYMBOL cannot */
  1191.         /* follow such a null transition.                              */
  1192.         /***************************************************************/
  1193.         if (! cyclic[act])
  1194.         {
  1195.             go_to = statset[act].go_to;
  1196.             for (i = 1; i <= go_to.size; i++)
  1197.             {
  1198.                 symbol = GOTO_SYMBOL(go_to, i);
  1199.                 if (null_nt[symbol])
  1200.                 {
  1201.                     struct stack_element *new_configs;
  1202.  
  1203.                     q = allocate_stack_element();
  1204.                     q -> state_number = act;
  1205.                     q -> size = stack -> size + 1;
  1206.                     q -> previous = stack;
  1207.                     q -> next = NULL;
  1208.  
  1209.                     new_configs = follow_sources(q, symbol, la_symbol);
  1210.                     if (new_configs == NULL)
  1211.                         free_stack_elements(q, q);
  1212.                     else
  1213.                     {
  1214.                         add_dangling_stack_element(q);
  1215.                         configs = union_config_sets(configs, new_configs);
  1216.                     }
  1217.                 }
  1218.             }
  1219.         }
  1220.     }
  1221.  
  1222.     /*******************************************************************/
  1223.     /* We now iterate over the kernel set of items associated with the */
  1224.     /* ACTion defined on SYMBOL...                                     */
  1225.     /*******************************************************************/
  1226.     for (item_ptr = (act > 0 ? statset[act].kernel_items
  1227.                              : adequate_item[-act]);
  1228.          item_ptr != NULL; item_ptr = item_ptr -> next)
  1229.     {
  1230.         item_no = item_ptr -> value;
  1231.  
  1232.         /***************************************************************/
  1233.         /* For each item that is a final item whose left-hand side     */
  1234.         /* is neither the starting symbol nor a symbol that can        */
  1235.         /* right-most produce itself...                                */
  1236.         /***************************************************************/
  1237.         if (item_table[item_no].symbol == empty)
  1238.         {
  1239.             rule_no = item_table[item_no].rule_number;
  1240.             lhs_symbol = rules[rule_no].lhs;
  1241.             if (lhs_symbol != accept_image && ! rmpself[lhs_symbol])
  1242.             {
  1243.                 /*******************************************************/
  1244.                 /* If the length of the prefix of the item preceeding  */
  1245.                 /* the dot is shorter that the length of the stack, we */
  1246.                 /* retrace the item's path within the stack and        */
  1247.                 /* invoke FOLLOW_SOURCES with the prefix of the stack  */
  1248.                 /* where the item was introduced through closure, the  */
  1249.                 /* left-hand side of the item and the lookahead symbol.*/
  1250.                 /*******************************************************/
  1251.                 if (item_table[item_no].dot < stack -> size)
  1252.                 {
  1253.                     q = stack;
  1254.                     for (i = 1; i < item_table[item_no].dot; i++)
  1255.                         q = q -> previous;
  1256.  
  1257.                     q = follow_sources(q, lhs_symbol, la_symbol);
  1258.                     configs = union_config_sets(configs, q);
  1259.                 }
  1260.                 else
  1261.                 {
  1262.                     struct node *v,
  1263.                                 *p,
  1264.                                 *tail;
  1265.  
  1266.                     /***************************************************/
  1267.                     /* Compute the item in the root state of the stack,*/
  1268.                     /* and find the root state...                      */
  1269.                     /***************************************************/
  1270.                     item_no -= stack -> size;
  1271.                     for (q = stack; q -> size != 1; q = q -> previous)
  1272.                         ;
  1273.  
  1274.                     /***************************************************/
  1275.                     /* We are now back in the main automaton, find all */
  1276.                     /* sources where the item was introduced through   */
  1277.                     /* closure start a new configuration and invoke    */
  1278.                     /* FOLLOW_SOURCES with the appropriate arguments to*/
  1279.                     /* calculate the set of configurations associated  */
  1280.                     /* with these sources.                             */
  1281.                     /***************************************************/
  1282.                     v = lpgaccess(q -> state_number, item_no);
  1283.                     for (p = v; p != NULL; tail = p, p = p -> next)
  1284.                     {
  1285.                         struct stack_element *new_configs;
  1286.  
  1287.                         q = allocate_stack_element();
  1288.                         q -> state_number = p -> value;
  1289.                         q -> size = 1;
  1290.                         q -> previous = NULL;
  1291.                         q -> next = NULL;
  1292.  
  1293.                         new_configs = follow_sources(q, lhs_symbol, la_symbol);
  1294.                         if (new_configs == NULL)
  1295.                             free_stack_elements(q, q);
  1296.                         else
  1297.                         {
  1298.                             add_dangling_stack_element(q);
  1299.                             configs = union_config_sets(configs, new_configs);
  1300.                         }
  1301.                     }
  1302.  
  1303.                     free_nodes(v, tail);
  1304.                 }
  1305.             }
  1306.         }
  1307.     }
  1308.  
  1309.     return configs;
  1310. }
  1311.  
  1312.  
  1313. /***********************************************************************/
  1314. /*                                NEXT_LA:                             */
  1315. /***********************************************************************/
  1316. /* This function has a similar structure as FOLLOW_SOURCES.  But,      */
  1317. /* instead of computing configurations that can be reached, it         */
  1318. /* computes lookahead symbols that can be reached.  It takes as        */
  1319. /* argument a configuration STACK, a SYMBOL on which a transition can  */
  1320. /* be made in the configuration and a set variable, LOOK_AHEAD, where  */
  1321. /* the result is to be stored.  When NEXT_LA is invoked from the       */
  1322. /* outside, LOOK_AHEAD is assumed to be initialized to the empty set.  */
  1323. /* NEXT_LA first executes the transition on SYMBOL and thereafter, all */
  1324. /* terminal symbols that can be read are added to LOOKAHEAD.           */
  1325. /***********************************************************************/
  1326. static void next_la(struct stack_element *stack,
  1327.                     int symbol, SET_PTR look_ahead)
  1328. {
  1329.     struct shift_header_type sh;
  1330.     struct goto_header_type  go_to;
  1331.  
  1332.     struct stack_element *q;
  1333.     struct node *item_ptr;
  1334.  
  1335.     int item_no,
  1336.         state_no,
  1337.         rule_no,
  1338.         lhs_symbol,
  1339.         act,
  1340.         i;
  1341.  
  1342.     /*******************************************************************/
  1343.     /* The only symbol that can follow the end-of-file symbol is the   */
  1344.     /* end-of-file symbol.                                             */
  1345.     /*******************************************************************/
  1346.     if (symbol == eoft_image)
  1347.     {
  1348.         SET_BIT_IN(look_ahead, 0, eoft_image);
  1349.         return;
  1350.     }
  1351.  
  1352.     state_no = stack -> state_number;
  1353.  
  1354.     /*******************************************************************/
  1355.     /* Find the transition defined on the symbol...                    */
  1356.     /*******************************************************************/
  1357.     if (symbol IS_A_NON_TERMINAL)
  1358.     {
  1359.         go_to = statset[state_no].go_to;
  1360.         for (i = 1; GOTO_SYMBOL(go_to, i) != symbol; i++)
  1361.             ;
  1362.         act = GOTO_ACTION(go_to, i);
  1363.     }
  1364.     else
  1365.     {
  1366.         sh = shift[statset[state_no].shift_number];
  1367.         for (i = 1; SHIFT_SYMBOL(sh, i) != symbol; i++)
  1368.             ;
  1369.         act = SHIFT_ACTION(sh, i);
  1370.     }
  1371.  
  1372.     /*******************************************************************/
  1373.     /* If the ACTion on the symbol is a shift or a goto, then all      */
  1374.     /* terminal symbols that can be read in ACT are added to           */
  1375.     /* LOOK_AHEAD.                                                     */
  1376.     /*******************************************************************/
  1377.     if (act > 0)
  1378.     {
  1379.         SET_UNION(look_ahead, 0, read_set, act);
  1380.     }
  1381.  
  1382.     /*******************************************************************/
  1383.     /* We now iterate over the kernel set of items associated with the */
  1384.     /* ACTion defined on SYMBOL...                                     */
  1385.     /* Recall that the READ_SET of ACT is but the union of the FIRST   */
  1386.     /* map defined on the suffixes of the items in the kernel of ACT.  */
  1387.     /*******************************************************************/
  1388.     for (item_ptr = (act > 0 ? statset[act].kernel_items
  1389.                              : adequate_item[-act]);
  1390.          item_ptr != NULL; item_ptr = item_ptr -> next)
  1391.     {
  1392.         item_no = item_ptr -> value;
  1393.  
  1394.         /***************************************************************/
  1395.         /* For each item that is a final item whose left-hand side     */
  1396.         /* is neither the starting symbol nor a symbol that can        */
  1397.         /* right-most produce itself...                                */
  1398.         /***************************************************************/
  1399.         if (IS_IN_SET(first, item_table[item_no - 1].suffix_index, empty))
  1400.         {
  1401.             rule_no = item_table[item_no].rule_number;
  1402.             lhs_symbol = rules[rule_no].lhs;
  1403.             if (lhs_symbol != accept_image && ! rmpself[lhs_symbol])
  1404.             {
  1405.                 /*******************************************************/
  1406.                 /* If the length of the prefix of the item preceeding  */
  1407.                 /* the dot is shorter that the length of the stack, we */
  1408.                 /* retrace the item's path within the stack and        */
  1409.                 /* invoke NEXT_LA with the prefix of the stack         */
  1410.                 /* where the item was introduced through closure, the  */
  1411.                 /* left-hand side of the item and LOOK_AHEAD.          */
  1412.                 /*******************************************************/
  1413.                 if (item_table[item_no].dot < stack -> size)
  1414.                 {
  1415.                     q = stack;
  1416.                     for (i = 1; i < item_table[item_no].dot; i++)
  1417.                         q = q -> previous;
  1418.                     next_la(q, lhs_symbol, look_ahead);
  1419.                 }
  1420.                 else
  1421.                 {
  1422.                     struct node *v,
  1423.                                 *p,
  1424.                                 *tail;
  1425.  
  1426.                     /***************************************************/
  1427.                     /* Compute the item in the root state of the stack,*/
  1428.                     /* and find the root state...                      */
  1429.                     /***************************************************/
  1430.                     item_no -= stack -> size;
  1431.                     for (q = stack; q -> size != 1; q = q -> previous)
  1432.                         ;
  1433.  
  1434.                     /***************************************************/
  1435.                     /* We are now back in the main automaton, find all */
  1436.                     /* sources where the item was introduced through   */
  1437.                     /* closure and add all terminal symbols in the     */
  1438.                     /* follow set of the left-hand side symbol in each */
  1439.                     /* source to LOOK_AHEAD.                           */
  1440.                     /***************************************************/
  1441.                     v = lpgaccess(q -> state_number, item_no);
  1442.                     for (p = v; p != NULL; tail = p, p = p -> next)
  1443.                     {
  1444.                         go_to = statset[p -> value].go_to;
  1445.                         for (i = 1; GOTO_SYMBOL(go_to, i) != lhs_symbol; i++)
  1446.                             ;
  1447.  
  1448.                         /***********************************************/
  1449.                         /* If look-ahead after left hand side is not   */
  1450.                         /* yet computed,call LA_TRAVERSE to compute it.*/
  1451.                         /***********************************************/
  1452.                         if (la_index[GOTO_LAPTR(go_to, i)] == OMEGA)
  1453.                         {
  1454.                             int stack_top = 0;
  1455.                             la_traverse(p -> value, i, &stack_top);
  1456.                         }
  1457.  
  1458.                         SET_UNION(look_ahead, 0,
  1459.                                   la_set, GOTO_LAPTR(go_to, i));
  1460.                     }
  1461.  
  1462.                     free_nodes(v, tail);
  1463.                 }
  1464.             }
  1465.         }
  1466.     }
  1467.  
  1468.     return;
  1469. }
  1470.  
  1471.  
  1472. /***********************************************************************/
  1473. /*                              STACK_WAS_SEEN:                        */
  1474. /***********************************************************************/
  1475. /* This function takes as argument an array, STACK_SEEN, with          */
  1476. /* STATE_TABLE_SIZE elements (indexable in the range                   */
  1477. /* 0..STATE_TABLE_SIZE-1) which is the base of a hash table and a      */
  1478. /* STACK. It searches the hash table to see if it already contained    */
  1479. /* the stack in question. If yes, it returns TRUE. Otherwise, it       */
  1480. /* inserts the stack into the table and returns FALSE.                 */
  1481. /***********************************************************************/
  1482. static BOOLEAN stack_was_seen(struct stack_element **stack_seen,
  1483.                               struct stack_element *stack)
  1484. {
  1485.     unsigned long hash_address;
  1486.     struct stack_element *p,
  1487.                          *q,
  1488.                          *r;
  1489.  
  1490.     hash_address = stack -> size;   /* Initialize hash address */
  1491.     for (p = stack; p != NULL; p = p -> previous)
  1492.         hash_address += p -> state_number;
  1493.     hash_address %= STATE_TABLE_SIZE;
  1494.  
  1495.     for (p = stack_seen[hash_address]; p != NULL; p = p -> link)
  1496.     {
  1497.         if (stack -> size == p -> size)
  1498.         {
  1499.             for (q = stack, r = p;
  1500.                  q != NULL;
  1501.                  q = q -> previous, r = r -> previous)
  1502.             {
  1503.                 if (q -> state_number != r -> state_number)
  1504.                     break;
  1505.             }
  1506.             if (q == NULL)
  1507.                 return TRUE;
  1508.         }
  1509.     }
  1510.  
  1511.     stack -> link = stack_seen[hash_address];
  1512.     stack_seen[hash_address] = stack;
  1513.  
  1514.     return FALSE;
  1515. }
  1516.  
  1517.  
  1518. /***********************************************************************/
  1519. /*                      STATE_TO_RESOLVE_CONFLICTS:                    */
  1520. /***********************************************************************/
  1521. /* STATE_TO_RESOLVE_CONFLICTS is a function that attempts to resolve   */
  1522. /* conflicts by doing more look-ahead.  If the conflict resolution     */
  1523. /* is successful, then a new state is created and returned; otherwise, */
  1524. /* the NULL pointer is returned.                                       */
  1525. /***********************************************************************/
  1526. static struct state_element *state_to_resolve_conflicts
  1527.        (struct sources_element sources, int la_symbol, int level)
  1528. {
  1529.     struct sources_element new_sources;
  1530.  
  1531.     struct node **action,
  1532.                  *p,
  1533.                  *tail;
  1534.  
  1535.     short *symbol_list,
  1536.           *action_list,
  1537.           *rule_count,
  1538.            symbol_root,
  1539.            shift_root,
  1540.            reduce_root;
  1541.  
  1542.     SET_PTR look_ahead;
  1543.  
  1544.     struct stack_element *stack;
  1545.  
  1546.     struct state_element **la_shift_state,
  1547.                           *state;
  1548.  
  1549.     int num_shift_actions,
  1550.         num_reduce_actions,
  1551.         default_rule,
  1552.         count,
  1553.         i,
  1554.         symbol,
  1555.         act;
  1556.  
  1557.     new_sources = allocate_sources();
  1558.  
  1559.     action = (struct node **)
  1560.              calloc(num_terminals + 1, sizeof(struct node *));
  1561.     if (action == NULL)
  1562.         nospace(__FILE__, __LINE__);
  1563.  
  1564.     symbol_list = Allocate_short_array(num_terminals + 1);
  1565.     action_list = Allocate_short_array(num_terminals + 1);
  1566.     rule_count = Allocate_short_array(num_rules + 1);
  1567.  
  1568.     look_ahead = (SET_PTR)
  1569.                  calloc(1, term_set_size * sizeof(BOOLEAN_CELL));
  1570.     if (look_ahead == NULL)
  1571.         nospace(__FILE__, __LINE__);
  1572.  
  1573.     la_shift_state = (struct state_element **)
  1574.                      calloc(num_terminals + 1,
  1575.                             sizeof(struct state_element *));
  1576.     if (la_shift_state == NULL)
  1577.         nospace(__FILE__, __LINE__);
  1578.  
  1579.     /*******************************************************************/
  1580.     /* Initialize new lookahead state. Initialize counters. Check and  */
  1581.     /* adjust HIGHEST_LEVEL reached so far, if necessary.              */
  1582.     /*******************************************************************/
  1583.     state = NULL;
  1584.  
  1585.     num_shift_actions = 0;
  1586.     num_reduce_actions = 0;
  1587.     shift_root = NIL;
  1588.     reduce_root = NIL;
  1589.  
  1590.     if (level > highest_level)
  1591.         highest_level = level;
  1592.  
  1593.     /*******************************************************************/
  1594.     /* One of the parameters received is a SOURCES map whose domain is */
  1595.     /* a set of actions and each of these actions is mapped into a set */
  1596.     /* of configurations that can be reached after that action is      */
  1597.     /* executed (in the state where the conflicts were detected).      */
  1598.     /* In this loop, we compute an ACTION map which maps each each     */
  1599.     /* terminal symbol into 0 or more actions in the domain of SOURCES.*/
  1600.     /*                                                                 */
  1601.     /* NOTE in a sources map, if a configuration is associated with    */
  1602.     /* more than one action then the grammar is not LALR(k) for any k. */
  1603.     /* We check for that condition below. However, this check is there */
  1604.     /* for purely cosmetic reason. It is not necessary for the         */
  1605.     /* algorithm to work correctly and its removal will speed up this  */
  1606.     /* loop somewhat (for conflict-less input).                        */
  1607.     /* The first loop below initializes the hash table used for        */
  1608.     /* lookups ...                                                     */
  1609.     /*******************************************************************/
  1610.     for (i = 0; i < STATE_TABLE_SIZE; i++)
  1611.          sources.stack_seen[i] = NULL;
  1612.  
  1613.     symbol_root = NIL;
  1614.     for (act = sources.root; act != NIL; act = sources.list[act])
  1615.     {
  1616.         /***************************************************************/
  1617.         /* For each action we iterate over its associated set of       */
  1618.         /* configurations and invoke NEXT_LA to compute the lookahead  */
  1619.         /* set for that configuration. These lookahead sets are in     */
  1620.         /* turn unioned together to form a lookahead set for the       */
  1621.         /* action in question.                                         */
  1622.         /***************************************************************/
  1623.         INIT_SET(look_ahead);
  1624.         for (stack = sources.configs[act];
  1625.              stack != NULL; stack = stack -> next)
  1626.         {
  1627.             if (stack_was_seen(sources.stack_seen, stack))
  1628.             {/* This is the superfluous code mentioned above! */
  1629.                 highest_level = INFINITY;
  1630.                 goto clean_up_and_return;
  1631.             }
  1632.  
  1633.             next_la(stack, la_symbol, look_ahead);
  1634.         }
  1635.         RESET_BIT(look_ahead, empty);         /* EMPTY never in LA set */
  1636.  
  1637.         /***************************************************************/
  1638.         /* For each lookahead symbol computed for this action, add an  */
  1639.         /* action to the ACTION map and keep track of the symbols on   */
  1640.         /* which any action is defined.                                */
  1641.         /* If new conflicts are detected and we are already at the     */
  1642.         /* lookahead level requested, we terminate the computation...  */
  1643.         /***************************************************************/
  1644.         count = 0;
  1645.         for ALL_TERMINALS(symbol)
  1646.         {
  1647.             if (IS_ELEMENT(look_ahead, symbol))
  1648.             {
  1649.                 count++;
  1650.  
  1651.                 if (action[symbol] == NULL)
  1652.                 {
  1653.                     symbol_list[symbol] = symbol_root;
  1654.                     symbol_root = symbol;
  1655.                 }
  1656.                 else if (level == lalr_level)
  1657.                     goto clean_up_and_return;
  1658.  
  1659.                 p = Allocate_node();
  1660.                 p -> value = act;
  1661.                 p -> next = action[symbol];
  1662.                 action[symbol] = p;
  1663.             }
  1664.         }
  1665.  
  1666.         /***************************************************************/
  1667.         /* If the action in question is a reduction then we keep track */
  1668.         /* of how many times it was used.                              */
  1669.         /***************************************************************/
  1670.         if (act >= 0 && act <= num_rules)
  1671.             rule_count[act] = count;
  1672.     }
  1673.  
  1674.     /*******************************************************************/
  1675.     /* We now iterate over the symbols on which actions are defined.   */
  1676.     /* If we detect conflicts on any symbol, we compute new sources    */
  1677.     /* and try to recover by computing more lookahead. Otherwise, we   */
  1678.     /* update the counts and create two lists: a list of symbols on    */
  1679.     /* which shift actions are defined and a list of symbols on which  */
  1680.     /* reduce actions are defined.                                     */
  1681.     /*******************************************************************/
  1682.     for (symbol = symbol_root;
  1683.          symbol != NIL; symbol = symbol_list[symbol])
  1684.     {
  1685.         /***************************************************************/
  1686.         /* We have four cases to consider:                             */
  1687.         /*    1. There are conflicts on SYMBOL                         */
  1688.         /*    2. The action on SYMBOL is a shift-reduce                */
  1689.         /*    3. The action on SYMBOL is a shift                       */
  1690.         /*    4. The action on SYMBOL is a reduce                      */
  1691.         /***************************************************************/
  1692.         if (action[symbol] -> next != NULL)
  1693.         {
  1694.             new_sources = clear_sources(new_sources);
  1695.             for (p = action[symbol]; p != NULL; tail = p, p = p -> next)
  1696.             {
  1697.                 act = p -> value;
  1698.                 if (act >= 0 && act <= num_rules)
  1699.                     rule_count[act]--;
  1700.  
  1701.                 clear_visited();
  1702.  
  1703.                 for (stack = sources.configs[act];
  1704.                      stack != NULL; stack = stack -> next)
  1705.                 {
  1706.                     struct stack_element *new_configs;
  1707.  
  1708.                     new_configs = follow_sources(stack, la_symbol, symbol);
  1709.                     new_sources = add_configs(new_sources, act, new_configs);
  1710.                 }
  1711.             }
  1712.             free_nodes(action[symbol], tail);
  1713.             action[symbol] = NULL;
  1714.  
  1715.             state = state_to_resolve_conflicts(new_sources, symbol, level + 1);
  1716.  
  1717.             if (state == NULL)
  1718.                 goto clean_up_and_return;
  1719.  
  1720.             la_shift_state[symbol] = state;
  1721.  
  1722.             p = Allocate_node();
  1723.             p -> value = state -> state_number;
  1724.             p -> next = NULL;
  1725.             action[symbol] = p;
  1726.  
  1727.             num_shift_actions++;
  1728.             action_list[symbol] = shift_root;
  1729.             shift_root = symbol;
  1730.         }
  1731.         else if (action[symbol] -> value < 0)
  1732.         {
  1733.             num_shift_actions++;
  1734.             action_list[symbol] = shift_root;
  1735.             shift_root = symbol;
  1736.         }
  1737.         else if (action[symbol] -> value > num_rules)
  1738.         {
  1739.             num_shift_actions++;
  1740.             (action[symbol] -> value) -= num_rules;
  1741.             action_list[symbol] = shift_root;
  1742.             shift_root = symbol;
  1743.         }
  1744.         else
  1745.         {
  1746.             num_reduce_actions++;
  1747.             action_list[symbol] = reduce_root;
  1748.             reduce_root = symbol;
  1749.         }
  1750.     }
  1751.  
  1752.     /*******************************************************************/
  1753.     /* We now iterate over the reduce actions in the domain of sources */
  1754.     /* and compute a default action.                                   */
  1755.     /*******************************************************************/
  1756.     default_rule = OMEGA;
  1757.     count = 0;
  1758.     for (act = sources.root; act != NIL; act = sources.list[act])
  1759.     {
  1760.         if (act >= 0 && act <= num_rules)
  1761.         {
  1762.             if (rule_count[act] > count)
  1763.             {
  1764.                 count = rule_count[act];
  1765.                 default_rule = act;
  1766.             }
  1767.         }
  1768.     }
  1769.  
  1770.     /*******************************************************************/
  1771.     /* By now, we are ready to create a new look-ahead state. The      */
  1772.     /* actions for the state are in the ACTION vector, and the         */
  1773.     /* constants: NUM_SHIFT_ACTIONS and NUM_REDUCE_ACTIONS indicate    */
  1774.     /* the number of shift and reduce actions in the ACTION vector.    */
  1775.     /* Note that the IN_STATE field of each look-ahead state created   */
  1776.     /* is initially set to the number associated with that state. If   */
  1777.     /* all the conflicts detected in the state, S, that requested the  */
  1778.     /* creation of a look-ahead state are resolved, then this field    */
  1779.     /* is updated with S.                                              */
  1780.     /* Otherwise, this field indicates that this look-ahead state is   */
  1781.     /* dangling - no other state point to it.                          */
  1782.     /*******************************************************************/
  1783.     state = (struct state_element *)
  1784.             talloc(sizeof(struct state_element));
  1785.     if (state == (struct state_element *) NULL)
  1786.         nospace(__FILE__, __LINE__);
  1787.  
  1788.     state -> link = la_state_root;
  1789.     la_state_root = state;
  1790.  
  1791.     max_la_state++;
  1792.     SHORT_CHECK(max_la_state);
  1793.     state -> symbol = la_symbol;
  1794.     state -> state_number = max_la_state;
  1795.     state -> in_state = max_la_state;   /* Initialize it to something! */
  1796.  
  1797.     /*******************************************************************/
  1798.     /* If there are any shift-actions in this state, we create a shift */
  1799.     /* map for them if one does not yet exist, otherwise, we reuse the */
  1800.     /* old existing one.                                               */
  1801.     /*******************************************************************/
  1802.     if (num_shift_actions > 0)
  1803.     {
  1804.         unsigned long hash_address;
  1805.  
  1806.         struct shift_header_type sh;
  1807.  
  1808.         struct state_element *p;
  1809.  
  1810.         /***************************************************************/
  1811.         /* In this loop, we compute the hash address as the number of  */
  1812.         /* shift actions, plus the sum of all the symbols on which a   */
  1813.         /* shift action is defined.  As a side effect, we also take    */
  1814.         /* care of some other issues. Shift actions which were encoded */
  1815.         /* to distinguish them from reduces action are decoded.        */
  1816.         /* The counters for shift and shift-reduce actions are updated.*/
  1817.         /* For all Shift actions to look-ahead states, the IN_STATE    */
  1818.         /* field of these look-ahead target states are updated.        */
  1819.         /***************************************************************/
  1820.         hash_address = num_shift_actions;   /* Initialize hash address */
  1821.         for (symbol = shift_root;
  1822.              symbol != NIL; symbol = action_list[symbol])
  1823.         {
  1824.             hash_address += symbol;
  1825.  
  1826.             if (action[symbol] -> value < 0)
  1827.                 num_shift_reduces++;
  1828.             else if (action[symbol] -> value <= num_states)
  1829.                 num_shifts++;
  1830.             else /* lookahead-shift */
  1831.                 la_shift_state[symbol] -> in_state = max_la_state;
  1832.         }
  1833.         hash_address %= SHIFT_TABLE_SIZE;
  1834.  
  1835.         /***************************************************************/
  1836.         /* Search list associated with HASH_ADDRESS, and if the shift  */
  1837.         /* map in question is found, update the SHIFT, and SHIFT_NUMBER*/
  1838.         /* fields of the new Look-Ahead State.                         */
  1839.         /***************************************************************/
  1840.         for (p = shift_table[hash_address]; p != NULL; p = p -> next_shift)
  1841.         {  /* Search hash table for shift map */
  1842.             sh = p -> shift;
  1843.             if (sh.size == num_shift_actions)
  1844.             {
  1845.                 for (i = 1; i <= num_shift_actions; i++)
  1846.                 { /* compare shift maps */
  1847.                     if (SHIFT_ACTION(sh, i) !=
  1848.                         action[SHIFT_SYMBOL(sh, i)] -> value)
  1849.                        break;
  1850.                 }
  1851.  
  1852.                 if (i > num_shift_actions) /* are they equal ? */
  1853.                 {
  1854.                     state -> shift = sh;
  1855.                     state -> shift_number = p -> shift_number;
  1856.                     break;
  1857.                 }
  1858.             }
  1859.         }
  1860.  
  1861.         /***************************************************************/
  1862.         /* Shift map was not found.  We have to create a new one and   */
  1863.         /* insert it into the table.                                   */
  1864.         /***************************************************************/
  1865.         if (p == NULL)
  1866.         {
  1867.             num_shift_maps++;
  1868.  
  1869.             sh = Allocate_shift_map(num_shift_actions);
  1870.  
  1871.             state -> shift = sh;
  1872.             state -> shift_number = num_shift_maps;
  1873.             state -> next_shift = shift_table[hash_address];
  1874.             shift_table[hash_address] = state;
  1875.  
  1876.             for (symbol = shift_root, i = 1;
  1877.                  symbol != NIL; symbol = action_list[symbol], i++)
  1878.             {
  1879.                 SHIFT_SYMBOL(sh, i) = symbol;
  1880.                 SHIFT_ACTION(sh, i) = action[symbol] -> value;
  1881.             }
  1882.         }
  1883.     }
  1884.     else
  1885.     {
  1886.         state -> shift.size = 0;
  1887.         state -> shift_number = 0;
  1888.     }
  1889.  
  1890.     /*******************************************************************/
  1891.     /* Construct Reduce map.                                           */
  1892.     /* When SPACE or TIME tables are requested, no default actions are */
  1893.     /* taken.                                                          */
  1894.     /*******************************************************************/
  1895.     Build_reduce_map:
  1896.     {
  1897.         struct reduce_header_type red;
  1898.         int i;
  1899.  
  1900.         if (default_rule != OMEGA &&
  1901.             table_opt != OPTIMIZE_TIME &&
  1902.             table_opt != OPTIMIZE_SPACE &&
  1903.             default_opt != 0)
  1904.             num_reduce_actions -= rule_count[default_rule];
  1905.  
  1906.         num_reductions += num_reduce_actions;
  1907.  
  1908.         red = Allocate_reduce_map(num_reduce_actions);
  1909.         state -> reduce = red;
  1910.         for (symbol = reduce_root, i = 1;
  1911.              symbol != NIL; symbol = action_list[symbol])
  1912.         {
  1913.             if (default_opt == 0 ||
  1914.                 action[symbol] -> value != default_rule ||
  1915.                 table_opt == OPTIMIZE_TIME ||
  1916.                 table_opt == OPTIMIZE_SPACE)
  1917.             {
  1918.                 REDUCE_SYMBOL (red, i) = symbol;
  1919.                 REDUCE_RULE_NO(red, i) = action[symbol] -> value;
  1920.  
  1921.                 i++;
  1922.             }
  1923.         }
  1924.  
  1925.         REDUCE_SYMBOL(red, 0) = DEFAULT_SYMBOL;
  1926.         if (default_opt > 0)
  1927.             REDUCE_RULE_NO(red, 0) = default_rule;
  1928.         else
  1929.             REDUCE_RULE_NO(red, 0) = OMEGA;
  1930.     }
  1931.  
  1932.  
  1933.     /*******************************************************************/
  1934.     /* Release all space allocated to process this lookahead state and */
  1935.     /* return.                                                         */
  1936.     /*******************************************************************/
  1937. clean_up_and_return:
  1938.     free_sources(new_sources);
  1939.     for (symbol = symbol_root; symbol != NIL; symbol = symbol_list[symbol])
  1940.     {
  1941.         for (p = action[symbol]; p != NULL; tail = p, p = p -> next)
  1942.              ;
  1943.         if (action[symbol] != NULL)
  1944.             free_nodes(action[symbol], tail);
  1945.     }
  1946.     ffree(action);
  1947.     ffree(symbol_list);
  1948.     ffree(action_list);
  1949.     ffree(rule_count);
  1950.     ffree(look_ahead);
  1951.     ffree(la_shift_state);
  1952.  
  1953.     return state;
  1954. }
  1955.  
  1956.  
  1957. /***********************************************************************/
  1958. /*                              INIT_RMPSELF:                          */
  1959. /***********************************************************************/
  1960. /* This procedure is invoked when LALR_LEVEL > 1 to construct the      */
  1961. /* RMPSELF set which identifies the nonterminals that can right-most   */
  1962. /* produce themselves. It takes as argumen the map PRODUCES which      */
  1963. /* identifies for each nonterminal the set of nonterminals that it can */
  1964. /* right-most produce.                                                 */
  1965. /***********************************************************************/
  1966. void init_rmpself(SET_PTR produces)
  1967. {
  1968.     int nt;
  1969.  
  1970.     rmpself = Allocate_boolean_array(num_non_terminals);
  1971.     rmpself -= (num_terminals + 1);
  1972.  
  1973.     /*******************************************************************/
  1974.     /* Note that each element of the map produces is a boolean vector  */
  1975.     /* that is indexable in the range 1..num_non_terminals. Since each */
  1976.     /* nonterminal is offset by the value num_terminals (to distinguish*/
  1977.     /* it from the terminals),it must therefore be adjusted accordingly*/
  1978.     /* when dereferencing an element in the range of the produces map. */
  1979.     /*******************************************************************/
  1980.     for ALL_NON_TERMINALS(nt)
  1981.         rmpself[nt] = IS_IN_NTSET(produces, nt, nt - num_terminals);
  1982.  
  1983.     return;
  1984. }
  1985.  
  1986.  
  1987. /***********************************************************************/
  1988. /*                          INIT_LALRK_PROCESS:                        */
  1989. /***********************************************************************/
  1990. /* If LALR(k), k > 1, is requested, we may have to create more shift   */
  1991. /* maps. Initialize SHIFT_TABLE. Note that each element of SHIFT_TABLE */
  1992. /* is automatically initialized to NULL by CALLOC.                     */
  1993. /* (See STATE_TO_RESOLVE_CONFLICTS)                                    */
  1994. /* Second, we check whether or not the grammar is not LR(k) for any k  */
  1995. /* because there exist a nonterminal A such that                       */
  1996. /*                                                                     */
  1997. /*                     A =>+rm A                                       */
  1998. /*                                                                     */
  1999. /* Finally, allocate and compute the CYCLIC vector which identifies    */
  2000. /* states that can enter a cycle via transitions on nullable           */
  2001. /* nonterminals. If such a cyle exists, the grammar can also be        */
  2002. /* claimed to be not LR(k) for any k.                                  */
  2003. /***********************************************************************/
  2004. void init_lalrk_process(void)
  2005. {
  2006.     int state_no,
  2007.         symbol;
  2008.  
  2009.     not_lrk = FALSE;
  2010.  
  2011.     if (lalr_level > 1)
  2012.     {
  2013.         shift_table = (struct state_element **)
  2014.                       calloc(SHIFT_TABLE_SIZE,
  2015.                              sizeof(struct state_element *));
  2016.         if (shift_table == NULL)
  2017.             nospace(__FILE__, __LINE__);
  2018.  
  2019.         for ALL_NON_TERMINALS(symbol)
  2020.             not_lrk = not_lrk || rmpself[symbol];
  2021.  
  2022.         cyclic = Allocate_boolean_array(num_states + 1);
  2023.         index_of = Allocate_short_array(num_states + 1);
  2024.         stack = Allocate_short_array(num_states + 1);
  2025.         for ALL_STATES(state_no)
  2026.             index_of[state_no] = OMEGA;
  2027.         top = 0;
  2028.         for ALL_STATES(state_no)
  2029.         {
  2030.             if (index_of[state_no] == OMEGA)
  2031.                 compute_cyclic(state_no);
  2032.             not_lrk = not_lrk || cyclic[state_no];
  2033.         }
  2034.  
  2035.         ffree(stack);
  2036.         ffree(index_of);
  2037.  
  2038.         sources = allocate_sources();
  2039.  
  2040.         visited.map = (struct node **)
  2041.                       calloc(num_states + 1, sizeof(struct node *));
  2042.         if (visited.map == NULL)
  2043.             nospace(__FILE__, __LINE__);
  2044.  
  2045.         visited.list = Allocate_short_array(num_states + 1);
  2046.         visited.root = NIL;
  2047.     }
  2048.  
  2049.     return;
  2050. }
  2051.  
  2052. /***********************************************************************/
  2053. /*                        EXIT_LALRK_PROCESS:                          */
  2054. /***********************************************************************/
  2055. /* Free all support structures that were allocated to help compute     */
  2056. /* additional lookahead.                                               */
  2057. /***********************************************************************/
  2058. void exit_lalrk_process(void)
  2059. {
  2060.     if (lalr_level > 1)
  2061.     {
  2062.         rmpself += (num_terminals + 1);
  2063.         ffree(rmpself);
  2064.         ffree(shift_table);
  2065.         ffree(cyclic);
  2066.  
  2067.         free_sources(sources);
  2068.         clear_visited();
  2069.         ffree(visited.map);
  2070.         ffree(visited.list);
  2071.     }
  2072.  
  2073.     return;
  2074. }
  2075.  
  2076.  
  2077. /***********************************************************************/
  2078. /*                            FREE_CONFLICT_SPACE                      */
  2079. /***********************************************************************/
  2080. /* If we had to report conflicts, free the SLR support structures.     */
  2081. /***********************************************************************/
  2082. void free_conflict_space(void)
  2083. {
  2084.     if (nt_items != NULL)
  2085.     {
  2086.         nt_items += (num_terminals + 1);
  2087.         ffree(nt_items);
  2088.         ffree(item_list);
  2089.     }
  2090.  
  2091.     return;
  2092. }
  2093.  
  2094.  
  2095. /***********************************************************************/
  2096. /*                           RESOLVE_CONFLICTS:                        */
  2097. /***********************************************************************/
  2098. /* If conflicts were detected and LALR(k) processing was requested,    */
  2099. /* where k > 1, then we attempt to resolve the conflicts by computing  */
  2100. /* more lookaheads.  Shift-Reduce conflicts are processed first,       */
  2101. /* followed by Reduce-Reduce conflicts.                                */
  2102. /***********************************************************************/
  2103. void resolve_conflicts(int state_no, struct node **action,
  2104.                        short *symbol_list, int symbol_root)
  2105. {
  2106.     struct shift_header_type sh;
  2107.  
  2108.     struct node *p,
  2109.                 *tail;
  2110.  
  2111.     struct stack_element *q;
  2112.  
  2113.     struct state_element *state;
  2114.  
  2115.     int i,
  2116.         act,
  2117.         item_no,
  2118.         lhs_symbol,
  2119.         symbol;
  2120.  
  2121.     /*******************************************************************/
  2122.     /* Note that a shift action to a state "S" is encoded with the     */
  2123.     /* value (S+NUM_RULES) to help distinguish it from reduce actions. */
  2124.     /* Reduce actions lie in the range [0..NUM_RULES].   Shift-reduce  */
  2125.     /* actions lie in the range [-NUM_RULES..-1].                      */
  2126.     /*******************************************************************/
  2127.     sr_conflict_root = NULL;
  2128.  
  2129.     sh = shift[statset[state_no].shift_number];
  2130.     for (i = 1; i <= sh.size; i++)
  2131.     {
  2132.         symbol = SHIFT_SYMBOL(sh, i);
  2133.  
  2134.         if (single_productions_bit && action[symbol] != NULL)
  2135.             add_conflict_symbol(state_no, symbol);
  2136.  
  2137.         if (lalr_level > 1 && action[symbol] != NULL)
  2138.         {
  2139.             sources = clear_sources(sources);
  2140.  
  2141.             q = allocate_stack_element();
  2142.             q -> state_number = state_no;
  2143.             q -> size = 1;
  2144.             q -> previous = NULL;
  2145.             q -> next = NULL;
  2146.  
  2147.             act = SHIFT_ACTION(sh, i);
  2148.             if (act > 0)
  2149.                  sources = add_configs(sources, act + num_rules, q);
  2150.             else
  2151.                  sources = add_configs(sources, act, q);
  2152.  
  2153.             for (p = action[symbol]; p != NULL; tail = p, p = p -> next)
  2154.             {
  2155.                 struct stack_element *new_configs;
  2156.                 struct node *v,
  2157.                             *s;
  2158.  
  2159.                 item_no = p -> value;
  2160.                 act = item_table[item_no].rule_number;
  2161.                 lhs_symbol = rules[act].lhs;
  2162.  
  2163.                 clear_visited();
  2164.  
  2165.                 v = lpgaccess(state_no, item_no);
  2166.                 for (s = v; s != NULL; tail = s, s = s -> next)
  2167.                 {
  2168.                     q = allocate_stack_element();
  2169.                     q -> state_number = s -> value;
  2170.                     q -> size = 1;
  2171.                     q -> previous = NULL;
  2172.                     q -> next = NULL;
  2173.  
  2174.                     new_configs = follow_sources(q, lhs_symbol, symbol);
  2175.                     if (new_configs == NULL)
  2176.                         free_stack_elements(q, q);
  2177.                     else
  2178.                     {
  2179.                         add_dangling_stack_element(q);
  2180.                         sources = add_configs(sources, act, new_configs);
  2181.                     }
  2182.                 }
  2183.  
  2184.                 free_nodes(v, tail);
  2185.             }
  2186.  
  2187.         /***************************************************************/
  2188.         /* The function STATE_TO_RESOLVE_CONFLICTS returns a pointer   */
  2189.         /* value to a STATE_ELEMENT which has been constructed to      */
  2190.         /* resolve the conflicts in question. If the value returned by */
  2191.         /* that function is NULL, then it was not possible to resolve  */
  2192.         /* the conflicts.  In any case, STATE_TO_RESOLVE_CONFLICTS     */
  2193.         /* frees the space that is used by the action map headed by    */
  2194.         /* ACTION_ROOT.                                                */
  2195.         /***************************************************************/
  2196.             state = state_to_resolve_conflicts(sources, symbol, 2);
  2197.  
  2198.             if (state != NULL)
  2199.             {
  2200.                 state -> in_state = state_no;
  2201.  
  2202.                 free_nodes(action[symbol], tail);
  2203.                 action[symbol] = NULL;
  2204.             }
  2205.         }
  2206.  
  2207.         /***************************************************************/
  2208.         /* If unresolved shift-reduce conflicts are detected on symbol,*/
  2209.         /*  add them to the list of conflicts so they can be reported  */
  2210.         /* (if the CONFLICT option is on) and count them.              */
  2211.         /***************************************************************/
  2212.         if (action[symbol] != NULL)
  2213.         {
  2214.             act = SHIFT_ACTION(sh, i);
  2215.  
  2216.             for (p = action[symbol]; p != NULL; tail = p, p = p -> next)
  2217.             {
  2218.                 if (conflicts_bit)
  2219.                 {
  2220.                     struct sr_conflict_element *q;
  2221.  
  2222.                     q = (struct sr_conflict_element *)
  2223.                         allocate_conflict_element();
  2224.                     q -> state_number = act;
  2225.                     q -> item = p -> value;
  2226.                     q -> symbol = symbol;
  2227.  
  2228.                     q -> next = sr_conflict_root;
  2229.                     sr_conflict_root = q;
  2230.                 }
  2231.  
  2232.                 num_sr_conflicts++;
  2233.             }
  2234.  
  2235.             /***********************************************************/
  2236.             /* Remove reduce actions defined on symbol so as to give   */
  2237.             /* precedence to the shift.                                */
  2238.             /***********************************************************/
  2239.             free_nodes(action[symbol], tail);
  2240.             action[symbol] = NULL;
  2241.         }
  2242.     }
  2243.  
  2244.     /*******************************************************************/
  2245.     /* We construct a map from each action to a list of states as we   */
  2246.     /* did for the Shift-reduce conflicts. A boolean vector ITEM_SEEN  */
  2247.     /* is used to prevent duplication of actions. This problem does    */
  2248.     /* not occur with Shift-Reduce conflicts.                          */
  2249.     /*******************************************************************/
  2250.     rr_conflict_root = NULL;
  2251.  
  2252.     for (symbol = symbol_root;
  2253.          symbol != NIL; symbol = symbol_list[symbol])
  2254.     {
  2255.         if (action[symbol] != NULL)
  2256.         {
  2257.             if (single_productions_bit && action[symbol] -> next != NULL)
  2258.                 add_conflict_symbol(state_no, symbol);
  2259.  
  2260.             if (lalr_level > 1 && action[symbol] -> next != NULL)
  2261.             {
  2262.                 sources = clear_sources(sources);
  2263.  
  2264.                 for (p = action[symbol]; p != NULL; tail = p, p = p -> next)
  2265.                 {
  2266.                     struct stack_element *new_configs;
  2267.                     struct node *v,
  2268.                                 *s;
  2269.  
  2270.                     item_no = p -> value;
  2271.                     act = item_table[item_no].rule_number;
  2272.                     lhs_symbol = rules[act].lhs;
  2273.  
  2274.                     clear_visited();
  2275.  
  2276.                     v = lpgaccess(state_no, item_no);
  2277.                     for (s = v; s != NULL; tail = s, s = s -> next)
  2278.                     {
  2279.                         q = allocate_stack_element();
  2280.                         q -> state_number = s -> value;
  2281.                         q -> size = 1;
  2282.                         q -> previous = NULL;
  2283.                         q -> next = NULL;
  2284.  
  2285.                         new_configs = follow_sources(q, lhs_symbol, symbol);
  2286.                         if (new_configs == NULL)
  2287.                             free_stack_elements(q, q);
  2288.                         else
  2289.                         {
  2290.                             add_dangling_stack_element(q);
  2291.                             sources = add_configs(sources, act, new_configs);
  2292.                         }
  2293.                     }
  2294.  
  2295.                     free_nodes(v, tail);
  2296.                 }
  2297.  
  2298.         /***************************************************************/
  2299.         /*     STATE_TO_RESOLVE_CONFLICTS will return a pointer to a   */
  2300.         /* STATE_ELEMENT if the conflicts were resolvable with more    */
  2301.         /* lookaheads, otherwise, it returns NULL.                     */
  2302.         /***************************************************************/
  2303.                 state = state_to_resolve_conflicts(sources, symbol, 2);
  2304.  
  2305.                 if (state != NULL)
  2306.                 {
  2307.                     state -> in_state = state_no;
  2308.  
  2309.                     free_nodes(action[symbol], tail);
  2310.                     action[symbol] = NULL;
  2311.                 }
  2312.             }
  2313.  
  2314.             /***********************************************************/
  2315.             /* If unresolved reduce-reduce conflicts are detected on   */
  2316.             /* symbol, add them to the list of conflicts so they can be*/
  2317.             /* reported (if the CONFLICT option is on) and count them. */
  2318.             /***********************************************************/
  2319.             if (action[symbol] != NULL)
  2320.             {
  2321.                 act = action[symbol] -> value;
  2322.  
  2323.                 for (p = action[symbol] -> next;
  2324.                      p != NULL; tail = p, p = p -> next)
  2325.                 {
  2326.                     if (conflicts_bit)
  2327.                     {
  2328.                         struct rr_conflict_element *q;
  2329.  
  2330.                         q = (struct rr_conflict_element *)
  2331.                             allocate_conflict_element();
  2332.                         q -> symbol = symbol;
  2333.                         q -> item1  = act;
  2334.                         q -> item2  = p -> value;
  2335.  
  2336.                         q -> next = rr_conflict_root;
  2337.                         rr_conflict_root = q;
  2338.                     }
  2339.  
  2340.                     num_rr_conflicts++;
  2341.                 }
  2342.  
  2343.                 /***********************************************************/
  2344.                 /* Remove all reduce actions that are defined on symbol    */
  2345.                 /* except the first one. That rule is the one with the     */
  2346.                 /* longest right-hand side that was associated with symbol.*/
  2347.                 /* See code in MKRED.C.                                    */
  2348.                 /***********************************************************/
  2349.                 if (action[symbol] -> next != NULL)
  2350.                 {
  2351.                     free_nodes(action[symbol] -> next, tail);
  2352.                     action[symbol] -> next = NULL;
  2353.                 }
  2354.             }
  2355.         }
  2356.     }
  2357.  
  2358.     /*******************************************************************/
  2359.     /* If any unresolved conflicts were detected, process them.        */
  2360.     /*******************************************************************/
  2361.     if (sr_conflict_root != NULL || rr_conflict_root != NULL)
  2362.         process_conflicts(state_no);
  2363.  
  2364.     free_dangling_stack_elements();
  2365.  
  2366.     return;
  2367. }
  2368.  
  2369.  
  2370. /***********************************************************************/
  2371. /*                           CREATE_LASTATS:                           */
  2372. /***********************************************************************/
  2373. /* Transfer the look-ahead states to their permanent destination, the  */
  2374. /* array LASTATS and update the original automaton with the relevant   */
  2375. /* transitions into the lookahead states.                              */
  2376. /***********************************************************************/
  2377. void create_lastats(void)
  2378. {
  2379.     struct state_element **new_shift_actions,
  2380.                           *p;
  2381.  
  2382.     struct shift_header_type sh;
  2383.  
  2384.     short *shift_action,
  2385.           *shift_list,
  2386.           *shift_count,
  2387.           *state_list;
  2388.  
  2389.     int shift_root,
  2390.         state_root,
  2391.         shift_size,
  2392.         i,
  2393.         symbol,
  2394.         state_no,
  2395.         shift_no;
  2396.  
  2397.     /*******************************************************************/
  2398.     /* Allocate LASTATS structure to permanently construct lookahead   */
  2399.     /* states and reallocate SHIFT map as we may have to construct     */
  2400.     /* new shift maps.                                                 */
  2401.     /*******************************************************************/
  2402.     lastats = (struct lastats_type *)
  2403.               calloc(max_la_state - num_states,
  2404.                      sizeof(struct lastats_type));
  2405.     if (lastats == NULL)
  2406.         nospace(__FILE__, __LINE__);
  2407.     lastats -= (num_states + 1);
  2408.  
  2409.     shift = (struct shift_header_type *)
  2410.             realloc(shift,
  2411.                     (max_la_state + 1) * sizeof(struct shift_header_type));
  2412.     if (shift == NULL)
  2413.         nospace(__FILE__, __LINE__);
  2414.  
  2415.     /*******************************************************************/
  2416.     /* Allocate temporary space used to construct final lookahead      */
  2417.     /* states.                                                         */
  2418.     /*******************************************************************/
  2419.     new_shift_actions = (struct state_element **)
  2420.                         calloc(num_states + 1, sizeof(struct state_element *));
  2421.     if (new_shift_actions == NULL)
  2422.         nospace(__FILE__, __LINE__);
  2423.  
  2424.     shift_action = Allocate_short_array(num_terminals + 1);
  2425.     shift_list   = Allocate_short_array(num_terminals + 1);
  2426.     shift_count  = Allocate_short_array(max_la_state + 1);
  2427.     state_list   = Allocate_short_array(max_la_state + 1);
  2428.  
  2429.     /*******************************************************************/
  2430.     /* The array shift_action will be used to construct a shift map    */
  2431.     /* for a given state. It is initialized here to the empty map.     */
  2432.     /* The array shift_count is used to count how many references      */
  2433.     /* there are to each shift map.                                    */
  2434.     /*******************************************************************/
  2435.     for ALL_TERMINALS(symbol)
  2436.         shift_action[symbol] = OMEGA;
  2437.  
  2438.     for (i = 0; i <= (int) max_la_state; i++)
  2439.         shift_count[i] = 0;
  2440.  
  2441.     for ALL_STATES(state_no)
  2442.         shift_count[statset[state_no].shift_number]++;
  2443.  
  2444.     /*******************************************************************/
  2445.     /* Traverse the list of lookahead states and initialize the        */
  2446.     /* final lastat element appropriately. Also, construct a mapping   */
  2447.     /* from each relevant initial state into the list of lookahead     */
  2448.     /* states into which it can shift. We also keep track of these     */
  2449.     /* initial states in a list headed by state_root.                  */
  2450.     /*******************************************************************/
  2451.     state_root = NIL;
  2452.     for (p = la_state_root; p != NULL; p = p -> link)
  2453.     {
  2454.         lastats[p -> state_number].in_state = p -> in_state;
  2455.         lastats[p -> state_number].shift_number = p -> shift_number;
  2456.         lastats[p -> state_number].reduce = p -> reduce;
  2457.         if (p -> shift.size != 0)
  2458.             shift[p -> shift_number] = p -> shift;
  2459.  
  2460.         state_no = p -> in_state;
  2461.         if (state_no <= (int) num_states)
  2462.         {
  2463.             if (new_shift_actions[state_no] == NULL)
  2464.             {
  2465.                 state_list[state_no] = state_root;
  2466.                 state_root = state_no;
  2467.             }
  2468.             p -> next_shift = new_shift_actions[state_no];
  2469.             new_shift_actions[state_no] = p;
  2470.         }
  2471.     }
  2472.  
  2473.     /*******************************************************************/
  2474.     /* We now traverse the list of initial states that can shift into  */
  2475.     /* lookahead states and update their shift map appropriately.      */
  2476.     /*******************************************************************/
  2477.     for (state_no = state_root;
  2478.          state_no != NIL; state_no = state_list[state_no])
  2479.     {
  2480.         /***************************************************************/
  2481.         /* Copy the shift map associated with STATE_NO into the direct */
  2482.         /* access map SHIFT_ACTION.                                    */
  2483.         /***************************************************************/
  2484.         shift_no = statset[state_no].shift_number;
  2485.         sh = shift[shift_no];
  2486.         shift_root = NIL;
  2487.         for (i = 1; i <= sh.size; i++)
  2488.         {
  2489.             symbol = SHIFT_SYMBOL(sh, i);
  2490.             shift_action[symbol] = SHIFT_ACTION(sh, i);
  2491.  
  2492.             shift_list[symbol] = shift_root;
  2493.             shift_root = symbol;
  2494.         }
  2495.  
  2496.         /***************************************************************/
  2497.         /* Add the lookahead shift transitions to the initial shift    */
  2498.         /* map.                                                        */
  2499.         /***************************************************************/
  2500.         shift_size = sh.size;
  2501.         for (p = new_shift_actions[state_no]; p != NULL; p = p -> next_shift)
  2502.         {
  2503.             if (shift_action[p -> symbol] == OMEGA)
  2504.             {
  2505.                 shift_size++;
  2506.  
  2507.                 shift_list[p -> symbol] = shift_root;
  2508.                 shift_root = p -> symbol;
  2509.             }
  2510.             else if (shift_action[p -> symbol] < 0)
  2511.                 num_shift_reduces--;
  2512.             else
  2513.                 num_shifts--;
  2514.  
  2515.             shift_action[p -> symbol] = p -> state_number;
  2516.         }
  2517.  
  2518.         /***************************************************************/
  2519.         /* There are two conditions under which we have to construct   */
  2520.         /* a brand new shift map:                                      */
  2521.         /*     1. The initial shift map was shared with other states.  */
  2522.         /*     2. The updated shift map contains more elements than    */
  2523.         /*        the initial one.                                     */
  2524.         /***************************************************************/
  2525.         if (shift_count[shift_no] > 1)
  2526.         {
  2527.             shift_count[shift_no]--;
  2528.             num_shift_maps++;
  2529.             sh = Allocate_shift_map(shift_size);
  2530.             shift[num_shift_maps] = sh;
  2531.             statset[state_no].shift_number = num_shift_maps;
  2532.         }
  2533.         else if (shift_size > sh.size)
  2534.         {
  2535.             sh = Allocate_shift_map(shift_size);
  2536.             shift[shift_no] = sh;
  2537.         }
  2538.  
  2539.         /***************************************************************/
  2540.         /* Reconstruct the relevant shift map.                         */
  2541.         /***************************************************************/
  2542.         for (symbol = shift_root, i = 1;
  2543.              symbol != NIL;
  2544.              shift_action[symbol] = OMEGA, symbol = shift_list[symbol], i++)
  2545.         {
  2546.             SHIFT_SYMBOL(sh, i) = symbol;
  2547.             SHIFT_ACTION(sh, i) = shift_action[symbol];
  2548.         }
  2549.     }
  2550.  
  2551.     /*******************************************************************/
  2552.     /* Free all local temporary structures and return.                 */
  2553.     /*******************************************************************/
  2554.     ffree(new_shift_actions);
  2555.     ffree(shift_action);
  2556.     ffree(shift_list);
  2557.     ffree(shift_count);
  2558.     ffree(state_list);
  2559.  
  2560.     return;
  2561. }
  2562.