home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / jikepg12.zip / jikespg / src / mkred.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-11-04  |  51.7 KB  |  1,215 lines
  1. /* $Id: mkred.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. /* STACK_ROOT is used in la_traverse to construct a stack of symbols.  */
  18. /* The boolean vector SINGLE_COMPLETE_ITEM identifies states whose     */
  19. /* kernel consists of a single final item and other conditions allows  */
  20. /* us to compute default reductions for such states.                   */
  21. /* The vector LA_BASE is used in COMPUTE_READ and TRACE_LALR_PATH to   */
  22. /* identify states whose read sets can be completely computed from     */
  23. /* their kernel items.                                                 */
  24. /***********************************************************************/
  25. static struct node *stack_root = NULL;
  26. static BOOLEAN *single_complete_item;
  27. static int *la_base;
  28.  
  29. /*****************************************************************************/
  30. /*                                 LPGACCESS:                                */
  31. /*****************************************************************************/
  32. /* Given a STATE_NO and an ITEM_NO, ACCESS computes the set of states where  */
  33. /* the rule from which ITEM_NO is derived was introduced through closure.    */
  34. /*****************************************************************************/
  35. struct node *lpgaccess(int state_no, int item_no)
  36. {
  37.     int i;
  38.  
  39.     BOOLEAN end_node;
  40.  
  41.     struct node *access_root,
  42.                 *head,
  43.                 *tail,
  44.                 *q,
  45.                 *p,
  46.                 *s;
  47.  
  48. /****************************************************************/
  49. /* Build a list pointed to by ACCESS_ROOT originally consisting */
  50. /* only of STATE_NO.                                            */
  51. /****************************************************************/
  52.     access_root = Allocate_node();
  53.     access_root -> value = state_no;
  54.     access_root -> next = NULL;
  55.  
  56.     for (i = item_table[item_no].dot; i > 0; i--)/*distance to travel is DOT */
  57.     {
  58.         head = access_root;  /* Save old ACCESS_ROOT */
  59.         access_root = NULL;  /* Initialize ACCESS_ROOT for new list */
  60.         for (p = head; p != NULL; tail = p, p = p -> next)
  61.         {
  62.             /***********************************************************/
  63.             /* Compute set of states with transition into p->value.    */
  64.             /***********************************************************/
  65.             for (end_node = ((s = in_stat[p -> value]) == NULL);
  66.                  ! end_node;
  67.                  end_node = (s == in_stat[p -> value]))
  68.             {
  69.                 s = s -> next;
  70.  
  71.                 q = Allocate_node();
  72.                 q -> value = s -> value;
  73.                 q -> next = access_root;
  74.                 access_root = q;
  75.             }
  76.         }
  77.  
  78.         free_nodes(head, tail);    /* free previous list */
  79.      }
  80.  
  81.      return(access_root);
  82. }
  83.  
  84.  
  85. /*****************************************************************************/
  86. /*                              TRACE_LALR_PATH:                             */
  87. /*****************************************************************************/
  88. /* Given an item of the form: [x .A y], where x and y are arbitrary strings, */
  89. /* and A is a non-terminal, we pretrace the path(s) in the automaton  that   */
  90. /* will be followed in computing the look-ahead set for that item in         */
  91. /* STATE_NO.  A number is assigned to all pairs (S, B), where S is a state,  */
  92. /* and B is a non-terminal, involved in the paths. GOTO_INDX points to the   */
  93. /* GOTO_ELEMENT of (STATE_NO, A).                                            */
  94. /*****************************************************************************/
  95. static void trace_lalr_path(int state_no, int goto_indx)
  96. {
  97.     int i,
  98.         symbol,
  99.         item,
  100.         state;
  101.  
  102.     struct goto_header_type go_to;
  103.  
  104.     BOOLEAN contains_empty;
  105.  
  106.     struct node *p,
  107.                 *r,
  108.                 *t,
  109.                 *w;
  110.  
  111. /*********************************************************************/
  112. /*  If STATE is a state number we first check to see if its base     */
  113. /* look-ahead set is a special one that does not contain EMPTY and   */
  114. /* has already been assigned a slot that can be reused.              */
  115. /* ((LA_BASE[STATE] != OMEGA) signals this condition.)               */
  116. /* NOTE that look-ahead follow sets are shared only when the maximum */
  117. /* look-ahead level allowed is 1 and single productions will not be  */
  118. /* removed. If either (or both) of these conditions is true, we need */
  119. /* to have a unique slot assigned to each pair [S, A] (where S is a  */
  120. /* state, and A is a non-terminal) in the automaton.                 */
  121. /*********************************************************************/
  122.     go_to = statset[state_no].go_to;
  123.     state = GOTO_ACTION(go_to, goto_indx);
  124.     if (state > 0)
  125.     {
  126.         if (la_base[state] != OMEGA &&
  127.             lalr_level == 1 && (! single_productions_bit))
  128.         {
  129.             GOTO_LAPTR(go_to, goto_indx) = la_base[state];
  130.             return;
  131.         }
  132.         r = statset[state].kernel_items;
  133.     }
  134.     else
  135.         r = adequate_item[-state];
  136.  
  137. /***********************************************************************/
  138. /* At this point, R points to a list of items which are the successors */
  139. /* of the items needed to initialize the Look-ahead follow sets.  If   */
  140. /* anyone of these items contains EMPTY, we trace the Digraph for other*/
  141. /* look-ahead follow sets that may be needed, and signal this fact     */
  142. /* using the variable CONTAINS_EMPTY.                                  */
  143. /***********************************************************************/
  144.     la_top++;   /* allocate new slot */
  145.     INT_CHECK(la_top);
  146.     GOTO_LAPTR(go_to, goto_indx) = la_top;
  147.     contains_empty = FALSE;
  148.  
  149.     for (; r != NULL;  r = r -> next)
  150.     {
  151.         item = r -> value - 1;
  152.         if (IS_IN_SET(first, item_table[item].suffix_index, empty))
  153.         {
  154.             contains_empty = TRUE;
  155.             symbol = rules[item_table[item].rule_number].lhs;
  156.             w = lpgaccess(state_no, item);
  157.             for (t = w; t != NULL; p = t, t = t -> next)
  158.             {
  159.                 struct goto_header_type go_to;
  160.  
  161.                 go_to = statset[t -> value].go_to;
  162.  
  163.                 for (i = 1; GOTO_SYMBOL(go_to, i) != symbol; i++)
  164.                     ;
  165.  
  166.                 if (GOTO_LAPTR(go_to, i) == OMEGA)
  167.                     trace_lalr_path(t -> value, i);
  168.             }
  169.  
  170.             free_nodes(w, p);
  171.         }
  172.     }
  173.  
  174. /********************************************************************/
  175. /* If the look-ahead follow set involved does not contain EMPTY, we */
  176. /* mark the state involved (STATE) so that other look-ahead follow  */
  177. /* sets which may need this set may reuse the same one.             */
  178. /* NOTE that if CONTAINS_EMPTY is false, then STATE has to denote a */
  179. /* state number (positive value) and not a rule number (negative).  */
  180. /********************************************************************/
  181.     if (! contains_empty)
  182.         la_base[state] = GOTO_LAPTR(go_to, goto_indx);
  183.  
  184.     return;
  185. }
  186.  
  187.  
  188. /*****************************************************************************/
  189. /*                               COMPUTE_READ:                               */
  190. /*****************************************************************************/
  191. /* COMPUTE_READ computes the number of intermediate look-ahead sets that     */
  192. /* will be needed (in LA_TOP), allocates space for the sets(LA_SET), and    */
  193. /* initializes them.                                                         */
  194. /*  By intermediate look-ahead set, we mean the set of terminals that may    */
  195. /* follow a non-terminal in a given state.                                   */
  196. /*  These sets are initialized to the set of terminals that can immediately  */
  197. /* follow the non-terminal in the state to which it can shift (READ set).    */
  198. /*****************************************************************************/
  199. static void compute_read(void)
  200. {
  201.     int state_no,
  202.         item_no,
  203.         rule_no,
  204.         lhs_symbol,
  205.         state,
  206.         i,
  207.         j,
  208.         la_ptr;
  209.  
  210.     struct node *p,
  211.                 *q,
  212.                 *s,
  213.                 *v;
  214.  
  215.     if (lalr_level > 1 || single_productions_bit)
  216.     {
  217.         read_set = (SET_PTR)
  218.                    calloc(num_states + 1,
  219.                           sizeof(BOOLEAN_CELL) * term_set_size);
  220.         if (read_set == NULL)
  221.             nospace(__FILE__, __LINE__);
  222.     }
  223.  
  224. /************************************************************************/
  225. /*  We traverse all the states and for all complete items that requires */
  226. /* a look-ahead set, we retrace the state digraph (with the help of the */
  227. /* routine TRACE_LALR_PATH) and assign a unique number to all look-ahead*/
  228. /* follow sets that it needs. A look-ahead follow set is a set of       */
  229. /* terminal symbols associated with a pair [S, A], where S is a state,  */
  230. /* and A is a non-terminal:                                             */
  231. /*                                                                      */
  232. /* [S, A] --> Follow-set                                                */
  233. /* Follow-set = {t | t is a terminal that can be shifted on after       */
  234. /*                      execution of a goto action on A in state S}.    */
  235. /*                                                                      */
  236. /* Each follow set is initialized with the set of terminals that can be */
  237. /* shifted on in state S2, where GOTO(S, A) = S2. After initialization  */
  238. /* a follow set F that does not contain the special terminal symbol     */
  239. /* EMPTY is marked with the help of the array LA_BASE, and if the       */
  240. /* highest level of look-ahead allowed is 1, then only one such set is  */
  241. /* allocated, and shared for all pairs (S, B) whose follow set is F.    */
  242. /************************************************************************/
  243.     la_top = 0;
  244.     la_base = (int *) calloc(num_states + 1, sizeof(int));
  245.     if (la_base == NULL)
  246.         nospace(__FILE__, __LINE__);
  247.  
  248.     for ALL_STATES(i)
  249.         la_base[i] = OMEGA;
  250.  
  251.     for ALL_STATES(state_no)
  252.     {
  253.         for (p = ((lalr_level <= 1 && single_complete_item[state_no])
  254.                   ? NULL
  255.                   : statset[state_no].complete_items);
  256.              p != NULL; p = p -> next)
  257.         {
  258.             item_no = p -> value;
  259.             rule_no = item_table[item_no].rule_number;
  260.             lhs_symbol = rules[rule_no].lhs;
  261.             if (lhs_symbol != accept_image)
  262.             {
  263.                 v = lpgaccess(state_no, item_no);
  264.                 for (s = v; s != NULL; q = s, s = s -> next)
  265.                 {
  266.                     struct goto_header_type go_to;
  267.  
  268.                     go_to = statset[s -> value].go_to;
  269.                     for (i = 1; GOTO_SYMBOL(go_to, i) != lhs_symbol; i++)
  270.                         ;
  271.  
  272.                     if (GOTO_LAPTR(go_to, i) == OMEGA)
  273.                         trace_lalr_path(s -> value, i);
  274.                 }
  275.  
  276.                 free_nodes(v, q);
  277.             }
  278.         }
  279.  
  280.     /***********************************************************************/
  281.     /*  If the look-ahead level is greater than 1 or single productions    */
  282.     /* actions are to be removed when possible, then we have to compute    */
  283.     /* a Follow-set for all pairs [S, A] in the state automaton. Therefore,*/
  284.     /* we also have to consider Shift-reduce actions as reductions, and    */
  285.     /* trace back to their roots as well.                                  */
  286.     /* Note that this is not necessary for Goto-reduce actions. Since      */
  287.     /* they terminate with a non-terminal, and that non-terminal is        */
  288.     /* followed by the empty string, and we know that it must produce a    */
  289.     /* rule that either ends up in a reduction, a shift-reduce, or another */
  290.     /* goto-reduce. It will therefore be taken care of automatically by    */
  291.     /* transitive closure.                                                 */
  292.     /***********************************************************************/
  293.         if (lalr_level > 1 || single_productions_bit)
  294.         {
  295.             struct shift_header_type sh;
  296.             struct goto_header_type  go_to;
  297.  
  298.             sh = shift[statset[state_no].shift_number];
  299.             for (j = 1; j <= sh.size; j++)
  300.             {
  301.                 if (SHIFT_ACTION(sh, j) < 0)
  302.                 {
  303.                     rule_no = - SHIFT_ACTION(sh, j);
  304.                     lhs_symbol = rules[rule_no].lhs;
  305.                     item_no = adequate_item[rule_no] -> value - 1;
  306.                     v = lpgaccess(state_no, item_no);
  307.                     for (s = v; s != NULL; q = s, s = s -> next)
  308.                     {
  309.                         go_to = statset[s -> value].go_to;
  310.                         for (i = 1; GOTO_SYMBOL(go_to, i) != lhs_symbol; i++)
  311.                             ;
  312.                         if (GOTO_LAPTR(go_to, i) == OMEGA)
  313.                             trace_lalr_path(s -> value, i);
  314.                     }
  315.  
  316.                     free_nodes(v, q);
  317.                 }
  318.             }
  319.  
  320.         /*******************************************************************/
  321.         /* We also need to compute the set of terminal symbols that can be */
  322.         /* read in a state entered via a terminal transition.              */
  323.         /*******************************************************************/
  324.             if (lalr_level > 1 && state_no != 1)
  325.             {
  326.                 q = statset[state_no].kernel_items;
  327.                 item_no = q -> value - 1;
  328.                 if (item_table[item_no].symbol IS_A_TERMINAL)
  329.                 {
  330.                     ASSIGN_SET(read_set, state_no, first,
  331.                                item_table[item_no].suffix_index);
  332.                     for (q = q -> next; q != NULL; q = q -> next)
  333.                     {
  334.                         item_no = q -> value - 1;
  335.                         SET_UNION(read_set, state_no, first,
  336.                                   item_table[item_no].suffix_index);
  337.                     }
  338.                 }
  339.             }
  340.         }
  341.     }
  342.  
  343.  
  344. /*********************************************************************/
  345. /*   We now allocate space for LA_INDEX and LA_SET, and initialize   */
  346. /* all its elements as indicated in reduce.h. The array LA_BASE is   */
  347. /* used to keep track of Follow sets that have been initialized. If  */
  348. /* another set needs to be initialized with a value that has been    */
  349. /* already computed, LA_BASE is used to retrieve the value.          */
  350. /*********************************************************************/
  351.     for ALL_STATES(i)
  352.         la_base[i] = OMEGA;
  353.  
  354.     la_index = Allocate_short_array(la_top + 1);
  355.  
  356.     la_set = (SET_PTR)
  357.              calloc(la_top + 1, term_set_size * sizeof(BOOLEAN_CELL));
  358.     if (la_set == NULL)
  359.         nospace(__FILE__, __LINE__);
  360.  
  361.     for ALL_STATES(state_no)
  362.     {
  363.         struct goto_header_type go_to;
  364.  
  365.         go_to = statset[state_no].go_to;
  366.         for (i = 1; i <= go_to.size; i++)
  367.         {
  368.             la_ptr = GOTO_LAPTR(go_to, i);
  369.             if (la_ptr != OMEGA)   /* Follow Look-ahead needed */
  370.             {
  371.                 state = GOTO_ACTION(go_to, i);
  372.                 if (state > 0)
  373.                 {
  374.                     if (la_base[state] != OMEGA)  /* already computed */
  375.                     {
  376.                         la_index[la_ptr] = la_index[la_base[state]];
  377.                         ASSIGN_SET(la_set, la_ptr,
  378.                                    la_set, la_base[state]);
  379.                         q = NULL;
  380.                     }
  381.                     else
  382.                     {
  383.                         la_base[state] = la_ptr;
  384.                         q = statset[state].kernel_items;
  385.                     }
  386.                 }
  387.                 else
  388.                     q = adequate_item[-state];
  389.                 if (q != NULL)
  390.                 {
  391.                     item_no = q -> value - 1;
  392.                     /* initialize with first item */
  393.                     ASSIGN_SET(la_set, la_ptr,
  394.                                first, item_table[item_no].suffix_index);
  395.                     for (q = q -> next; q != NULL; q = q -> next)
  396.                     {
  397.                         item_no = q -> value - 1;
  398.                         SET_UNION(la_set, la_ptr, first,
  399.                                   item_table[item_no].suffix_index);
  400.                     }
  401.                     if (IS_IN_SET(la_set, la_ptr, empty))
  402.                         la_index[la_ptr] = OMEGA;
  403.                     else
  404.                         la_index[la_ptr] = INFINITY;
  405.                     if (lalr_level > 1 || single_productions_bit)
  406.                     {
  407.                         if(state > 0)
  408.                         {
  409.                             ASSIGN_SET(read_set, state, la_set, la_ptr);
  410.                         }
  411.                     }
  412.                 }
  413.             }
  414.         }
  415.     }
  416.  
  417.     ffree(la_base);
  418.  
  419.     return;
  420. }
  421.  
  422.  
  423. /*****************************************************************************/
  424. /*                                LA_TRAVERSE:                               */
  425. /*****************************************************************************/
  426. /* LA_TRAVERSE takes two major arguments: STATE_NO, and an index (GOTO_INDX) */
  427. /* that points to the GOTO_ELEMENT array in STATE_NO for the non-terminal    */
  428. /* left hand side of an item for which look-ahead is to be computed. The     */
  429. /* look-ahead of an item of the form [x. A y] in state STATE_NO is the set   */
  430. /* of terminals that can appear immediately after A in the context summarized*/
  431. /* by STATE_NO. When a look-ahead set is computed, the result is placed in   */
  432. /* an allocation of LA_ELEMENT pointed to by the LA_PTR field of the         */
  433. /* GOTO_ELEMENT array.                                                       */
  434. /*                                                                           */
  435. /* The same digraph algorithm used in MKFIRST is used for this computation.  */
  436. /*                                                                           */
  437. /*****************************************************************************/
  438. void la_traverse(int state_no, int goto_indx, int *stack_top)
  439. {
  440.     int indx;
  441.  
  442.     int symbol,
  443.         item,
  444.         state,
  445.         i,
  446.         la_ptr;
  447.  
  448.     struct goto_header_type go_to;
  449.  
  450.     struct node *r,
  451.                 *s,
  452.                 *t,
  453.                 *w;
  454.  
  455.     go_to = statset[state_no].go_to;
  456.     la_ptr =  GOTO_LAPTR(go_to, goto_indx);
  457.  
  458.     s = Allocate_node();    /* Push LA_PTR down the stack */
  459.     s -> value = la_ptr;
  460.     s -> next = stack_root;
  461.     stack_root = s;
  462.  
  463.     indx = ++(*stack_top); /* one element was pushed into the stack */
  464.     la_index[la_ptr] = indx;
  465.  
  466. /**********************************************************************/
  467. /* Compute STATE, action to perform on Goto symbol in question. If    */
  468. /* STATE is positive, it denotes a state to which to shift. If it is  */
  469. /* negative, it is a rule on which to perform a Goto-Reduce.          */
  470. /**********************************************************************/
  471.     state = GOTO_ACTION(go_to, goto_indx);
  472.     if (state > 0)     /* Not a Goto-Reduce action */
  473.         r = statset[state].kernel_items;
  474.     else
  475.         r = adequate_item[-state];
  476.  
  477.     for (; r != NULL; r = r -> next)
  478.     {  /* loop over items [A -> x LHS_SYMBOL . y] */
  479.         item = r -> value - 1;
  480.         if IS_IN_SET(first, item_table[item].suffix_index, empty)
  481.         {
  482.             symbol = rules[item_table[item].rule_number].lhs;
  483.             w = lpgaccess(state_no, item); /* states where RULE was  */
  484.                                      /* introduced through closure   */
  485.             for (t = w; t != NULL; s = t, t = t -> next)
  486.             {
  487.                 struct goto_header_type go_to;
  488.  
  489.                 /**********************************************************/
  490.                 /* Search for GOTO action in access-state after reducing  */
  491.                 /* RULE to its left hand side (SYMBOL). Q points to the   */
  492.                 /* GOTO_ELEMENT in question.                              */
  493.                 /**********************************************************/
  494.                 go_to = statset[t -> value].go_to;
  495.                 for (i = 1; GOTO_SYMBOL(go_to, i) != symbol; i++)
  496.                     ;
  497.                 if (la_index[GOTO_LAPTR(go_to, i)] == OMEGA)
  498.                     la_traverse(t -> value, i, stack_top);
  499.                 SET_UNION(la_set, la_ptr,
  500.                           la_set, GOTO_LAPTR(go_to, i));
  501.                 la_index[la_ptr] = MIN(la_index[la_ptr],
  502.                                        la_index[GOTO_LAPTR(go_to, i)]);
  503.             }
  504.  
  505.             free_nodes(w, s);
  506.         }
  507.     }
  508.  
  509.     if (la_index[la_ptr] == indx) /* Top of a SCC */
  510.     {
  511.         s = stack_root;
  512.  
  513.         for (i = stack_root -> value; i != la_ptr;
  514.              stack_root = stack_root -> next, i = stack_root -> value)
  515.         {
  516.             ASSIGN_SET(la_set, i, la_set, la_ptr);
  517.             la_index[i] = INFINITY;
  518.             (*stack_top)--; /* one element was popped from the stack; */
  519.         }
  520.         la_index[la_ptr] = INFINITY;
  521.         r = stack_root; /* mark last element that is popped and ... */
  522.         stack_root = stack_root -> next; /* ... pop it! */
  523.         (*stack_top)--; /* one element was popped from the stack; */
  524.  
  525.         free_nodes(s, r);
  526.     }
  527.  
  528.     return;
  529. }
  530.  
  531. /*****************************************************************************/
  532. /*                               COMPUTE_LA:                                 */
  533. /*****************************************************************************/
  534. /* COMPUTE_LA takes as argument a state number (STATE_NO), an item number    */
  535. /* (ITEM_NO), and a set (LOOK_AHEAD).  It computes the look-ahead set of     */
  536. /* terminals for the given item in the given state and places the answer in  */
  537. /* the set LOOK_AHEAD.                                                       */
  538. /*****************************************************************************/
  539. void compute_la(int state_no, int item_no, SET_PTR look_ahead)
  540. {
  541.     int lhs_symbol,
  542.         i;
  543.  
  544.     struct node *r,
  545.                 *s,
  546.                 *v;
  547.  
  548.     stack_root = NULL;
  549.     lhs_symbol = rules[item_table[item_no].rule_number].lhs;
  550.     if (lhs_symbol == accept_image)
  551.     {
  552.         ASSIGN_SET(look_ahead, 0,
  553.                    first, item_table[item_no-1].suffix_index);
  554.         return;
  555.     }
  556.  
  557.     INIT_SET(look_ahead);  /* initialize set */
  558.  
  559.     v = lpgaccess(state_no, item_no);
  560.     for (s = v; s != NULL; r = s, s = s -> next)
  561.     {
  562.         struct  goto_header_type go_to;
  563.  
  564.         /*****************************************************************/
  565.         /* Search for GOTO action in Access-State after reducing rule to */
  566.         /* its left hand side(LHS_SYMBOL). Q points to the state.        */
  567.         /*****************************************************************/
  568.         go_to = statset[s -> value].go_to;
  569.         for (i = 1; GOTO_SYMBOL(go_to, i) != lhs_symbol; i++)
  570.             ;
  571.  
  572.         /***********************************************************/
  573.         /* If look-ahead after left hand side is not yet computed, */
  574.         /* LA_TRAVERSE the graph to compute it.                    */
  575.         /***********************************************************/
  576.         if (la_index[GOTO_LAPTR(go_to, i)] == OMEGA)
  577.         {
  578.             int stack_top = 0;
  579.             la_traverse(s -> value, i, &stack_top);
  580.         }
  581.         SET_UNION(look_ahead, 0, la_set, GOTO_LAPTR(go_to, i));
  582.     }
  583.  
  584.     RESET_BIT(look_ahead, empty); /* empty not valid look-ahead */
  585.     free_nodes(v, r);
  586.  
  587.     return;
  588. }
  589.  
  590.  
  591. /**********************************************************************/
  592. /*                            BUILD_IN_STAT:                          */
  593. /**********************************************************************/
  594. /* We construct the IN_STAT map which is the inverse of the transition*/
  595. /* map formed by GOTO and SHIFT maps.                                 */
  596. /* This map is implemented as a table of pointers that can be indexed */
  597. /* by the states to a circular list of integers representing other    */
  598. /* states that contain transitions to the state in question.          */
  599. /**********************************************************************/
  600. static void build_in_stat(void)
  601. {
  602.     struct shift_header_type sh;
  603.     struct goto_header_type  go_to;
  604.     struct node *q;
  605.     int state_no,
  606.         i,
  607.         n;
  608.  
  609.     for ALL_STATES(state_no)
  610.     {
  611.         n = statset[state_no].shift_number;
  612.         sh = shift[n];
  613.         for (i = 1; i <= sh.size; ++i)
  614.         {
  615.             n = SHIFT_ACTION(sh, i);
  616.             if (n > 0 && n <= num_states) /* A shift action? */
  617.             {
  618.                 q = Allocate_node();
  619.                 q -> value = state_no;
  620.                 if (in_stat[n] == NULL)
  621.                     q -> next = q;
  622.                 else
  623.                 {
  624.                     q -> next = in_stat[n] -> next;
  625.                     in_stat[n] -> next = q;
  626.                 }
  627.                 in_stat[n] = q;
  628.             }
  629.         }
  630.  
  631.         go_to = statset[state_no].go_to;
  632.         for (i = 1; i <= go_to.size; i++)
  633.         {
  634.             n = GOTO_ACTION(go_to, i);
  635.             if (n > 0) /* A goto action */
  636.             {
  637.                 q = Allocate_node();
  638.                 q -> value = state_no;
  639.                 if (in_stat[n] == NULL)
  640.                     q -> next = q;
  641.                 else
  642.                 {
  643.                     q -> next = in_stat[n] -> next;
  644.                     in_stat[n] -> next = q;
  645.                 }
  646.                 in_stat[n] = q;
  647.             }
  648.         }
  649.     }
  650.  
  651.     return;
  652. }
  653.  
  654.  
  655. /*****************************************************************************/
  656. /*                                MKRDCTS:                                   */
  657. /*****************************************************************************/
  658. /* MKRDCTS constructs the REDUCE map and detects conflicts in the grammar.   */
  659. /* When constructing an LALR parser, the subroutine COMPUTE_LA is invoked to */
  660. /* compute the lalr look-ahead sets.  For an SLR parser, the FOLLOW map      */
  661. /* computed earlier in the procedure MKFIRST is used.                        */
  662. /*                                                                           */
  663. /* For a complete description of the lookahead algorithm used in this        */
  664. /* program, see Charles, PhD thesis, NYU 1991.                               */
  665. /*****************************************************************************/
  666. void mkrdcts(void)
  667. {
  668.     short *symbol_list,
  669.           *rule_count;
  670.  
  671.     int symbol_root,
  672.         reduce_size,
  673.         state_no,
  674.         item_no,
  675.         rule_no,
  676.         symbol,
  677.         default_rule,
  678.         i,
  679.         n;
  680.  
  681.     struct node **action;
  682.  
  683.     struct node *p,
  684.                 *q,
  685.                 *r,
  686.                 *item_ptr;
  687.  
  688.     BOOLEAN *no_shift_on_error_sym;
  689.     SET_PTR look_ahead;
  690.  
  691. /**********************************************************************/
  692. /* Set up a pool of temporary space. If LALR(k), k > 1 is requested,  */
  693. /* INIT_LALRK_PROCESS sets up the necessary environment for the       */
  694. /* computation of multiple lookahead.                                 */
  695. /**********************************************************************/
  696.     reset_temporary_space();
  697.  
  698.     init_lalrk_process();
  699.  
  700. /**********************************************************************/
  701. /* IN_STAT is used to construct a reverse transition map. See         */
  702. /* BUILD_IN_STAT for more detail.                                     */
  703. /*                                                                    */
  704. /* RULE_COUNT is an array used to count the number of reductions on   */
  705. /* particular rules within a given state.                             */
  706. /*                                                                    */
  707. /* NO_SHIFT_ON_ERROR_SYM is a vector used to identify states that     */
  708. /* contain shift actions on the %ERROR symbol.  Such states are marked*/
  709. /* only when DEFAULT_OPT is 5.                                        */
  710. /*                                                                    */
  711. /* SYMBOL_LIST is used to construct temporary lists of terminals on   */
  712. /* which reductions are defined.                                      */
  713. /*                                                                    */
  714. /* When default actions are requested, the vector SINGLE_COMPLETE_ITEM*/
  715. /* is used to identify states that contain exactly one final item.    */
  716. /* NOTE that when the READ_REDUCE options is turned on, the LR(0)     */
  717. /* automaton constructed contains no such state.                      */
  718. /*                                                                    */
  719. /* ACTION is an array that is used as the base for a mapping from     */
  720. /* each terminal symbol into a list of actions that can be executed   */
  721. /* on that symbol in a given state.                                   */
  722. /*                                                                    */
  723. /* LOOK_AHEAD is used to compute lookahead sets.                      */
  724. /**********************************************************************/
  725.     in_stat = (struct node **)
  726.               calloc(num_states + 1, sizeof(struct node *));
  727.     if (in_stat == NULL)
  728.         nospace(__FILE__, __LINE__);
  729.  
  730.     rule_count = Allocate_short_array(num_rules + 1);
  731.     no_shift_on_error_sym = Allocate_boolean_array(num_states + 1);
  732.     symbol_list = Allocate_short_array(num_terminals + 1);
  733.     single_complete_item = Allocate_boolean_array(num_states + 1);
  734.  
  735.     action = (struct node **)
  736.              calloc(num_terminals + 1, sizeof(struct node *));
  737.     if (action == NULL)
  738.         nospace(__FILE__, __LINE__);
  739.  
  740.     look_ahead = (SET_PTR)
  741.                  calloc(1, term_set_size * sizeof(BOOLEAN_CELL));
  742.     if (look_ahead == NULL)
  743.         nospace(__FILE__, __LINE__);
  744.  
  745.     /****************************************************************/
  746.     /* If we will be removing single productions, we need to keep   */
  747.     /* track of all (state, symbol) pairs on which a conflict is    */
  748.     /* detected. The structure conflict_symbols is used as a base   */
  749.     /* to construct that map. See ADD_CONFLICT_SYMBOL in resolve.c. */
  750.     /* NOTE that this allocation automatically initialized all      */
  751.     /* elements of the conflict_symbols array to NULL.              */
  752.     /****************************************************************/
  753.     if (single_productions_bit)
  754.     {
  755.         conflict_symbols = (struct node **)
  756.                            calloc(num_states + 1, sizeof(struct node *));
  757.         if (conflict_symbols == NULL)
  758.             nospace(__FILE__, __LINE__);
  759.     }
  760.  
  761.     /**********************************************************************/
  762.     /* First, construct the IN_STAT map. Next, iterate over the states to */
  763.     /* construct two boolean vectors.  One indicates whether there is a   */
  764.     /* shift action on the ERROR symbol when the DEFAULT_OPT is 5.  The   */
  765.     /* other indicates whether it is all right to take default action in  */
  766.     /* states containing exactly one final item.                          */
  767.     /*                                                                    */
  768.     /* We also check whether the grammar is LR(0). I.e., whether it needs */
  769.     /* any look-ahead at all.                                             */
  770.     /**********************************************************************/
  771.     build_in_stat();
  772.  
  773.     for ALL_STATES(state_no)
  774.     {
  775.         struct shift_header_type sh;
  776.  
  777.         no_shift_on_error_sym[state_no] = TRUE;
  778.  
  779.         if (default_opt == 5)
  780.         {
  781.             n = statset[state_no].shift_number;
  782.             sh = shift[n];
  783.             for (i = 1; i <= sh.size; ++i)
  784.             {
  785.                 if (SHIFT_SYMBOL(sh, i) == error_image)
  786.                     no_shift_on_error_sym[state_no] = FALSE;
  787.             }
  788.         }
  789.  
  790.     /**********************************************************************/
  791.     /*   Compute whether this state is a final state.  I.e., a state that */
  792.     /* contains only a single complete item. If so, mark it as a default  */
  793.     /* state. Note that if the READ-REDUCE option is used, the automaton  */
  794.     /* will not contain such states. Also, states are marked only when    */
  795.     /* default actions are requested.                                     */
  796.     /**********************************************************************/
  797.         item_ptr = statset[state_no].kernel_items;
  798.         item_no = item_ptr -> value;
  799.         single_complete_item[state_no] =
  800.                ((! read_reduce_bit) &&
  801.                 (! single_productions_bit) &&
  802.                 (table_opt != OPTIMIZE_TIME) &&
  803.                 (table_opt != OPTIMIZE_SPACE) &&
  804.                 (default_opt > 0) &&
  805.                 (item_ptr  -> next == NULL) &&
  806.                 (item_table[item_no].symbol == empty));
  807.  
  808.     /**********************************************************************/
  809.     /* If a state has a complete item, and more than one kernel item      */
  810.     /* which is different from the complete item, then this state         */
  811.     /* requires look-ahead for the complete item.                         */
  812.     /**********************************************************************/
  813.         if (highest_level == 0)
  814.         {
  815.             r = statset[state_no].complete_items;
  816.             if (r != NULL)
  817.             {
  818.                 if (item_ptr -> next != NULL ||
  819.                     item_ptr -> value != r -> value)
  820.                     highest_level = 1;
  821.             }
  822.         }
  823.     }
  824.  
  825.     /****************************************************************/
  826.     /* We call COMPUTE_READ to perform the following tasks:         */
  827.     /* 1) Count how many elements are needed in LA_ELEMENT: LA_TOP  */
  828.     /* 2) Allocate space for and initialize LA_SET and LA_INDEX     */
  829.     /****************************************************************/
  830.     if (! slr_bit)
  831.         compute_read();
  832.  
  833.     /****************************************************************/
  834.     /* Allocate space for REDUCE which will be used to map each     */
  835.     /* into its reduce map. We also initialize RULE_COUNT which     */
  836.     /* will be used to count the number of reduce actions on each   */
  837.     /* rule with in a given state.                                  */
  838.     /****************************************************************/
  839.     reduce = (struct reduce_header_type *)
  840.              calloc(num_states + 1, sizeof(struct reduce_header_type));
  841.     if (reduce == NULL)
  842.         nospace(__FILE__, __LINE__);
  843.  
  844.     for ALL_RULES(i)
  845.         rule_count[i] = 0;
  846.  
  847.     /****************************************************************/
  848.     /* We are now ready to construct the reduce map. First, we      */
  849.     /* initialize MAX_LA_STATE to NUM_STATES. If no lookahead       */
  850.     /* state is added (the grammar is LALR(1)) this value will not  */
  851.     /* change. Otherwise, MAX_LA_STATE is incremented by 1 for each */
  852.     /* lookahead state added.                                       */
  853.     /****************************************************************/
  854.     max_la_state = num_states;
  855.  
  856.     /****************************************************************/
  857.     /* We iterate over the states, compute the lookahead sets,      */
  858.     /* resolve conflicts (if multiple lookahead is requested) and/or*/
  859.     /* report the conflicts if requested...                         */
  860.     /****************************************************************/
  861.     for ALL_STATES(state_no)
  862.     {
  863.         struct reduce_header_type red;
  864.  
  865.         default_rule = OMEGA;
  866.         symbol_root = NIL;
  867.  
  868.         item_ptr = statset[state_no].complete_items;
  869.         if (item_ptr != NULL)
  870.         {
  871.     /**********************************************************************/
  872.     /* Check if it is possible to take default reduction. The DEFAULT_OPT */
  873.     /* parameter indicates what kind of default options are requested.    */
  874.     /* The various values it can have are:                                */
  875.     /*                                                                    */
  876.     /*    a)   0 => no default reduction.                                 */
  877.     /*    b)   1 => default reduction only on adequate states. I.e.,      */
  878.     /*              states with only one complete item in their kernel.   */
  879.     /*    c)   2 => Default on all states that contain exactly one        */
  880.     /*              complete item not derived from an empty rule.         */
  881.     /*    d)   3 => Default on all states that contain exactly one        */
  882.     /*              complete item including items from empty rules.       */
  883.     /*    e)   4 => Default reduction on all states that contain exactly  */
  884.     /*              one item. If a state contains more than one item we   */
  885.     /*              take Default on the item that generated the most      */
  886.     /*              reductions. If there is a tie, one is selected at     */
  887.     /*              random.                                               */
  888.     /*    f)   5 => Same as 4 except that no default actions are computed */
  889.     /*              for states that contain a shift action on the ERROR   */
  890.     /*              symbol.                                               */
  891.     /*                                                                    */
  892.     /*  In the code below, we first check for category 3.  If it is not   */
  893.     /* satisfied, then we check for the others. Note that in any case,    */
  894.     /* default reductions are never taken on the ACCEPT rule.             */
  895.     /*                                                                    */
  896.     /**********************************************************************/
  897.             item_no = item_ptr -> value;
  898.             rule_no = item_table[item_no].rule_number;
  899.             symbol = rules[rule_no].lhs;
  900.             if (single_complete_item[state_no] && symbol != accept_image)
  901.             {
  902.                 default_rule = rule_no;
  903.                 item_ptr = NULL; /* No need to check for conflicts */
  904.             }
  905.  
  906.         /******************************************************************/
  907.         /* Iterate over all complete items in the state, build action     */
  908.         /* map, and check for conflicts.                                  */
  909.         /******************************************************************/
  910.             for (; item_ptr != NULL; item_ptr = item_ptr -> next)
  911.             { /* for all complete items */
  912.                 item_no = item_ptr -> value;
  913.                 rule_no = item_table[item_no].rule_number;
  914.  
  915.                 if (slr_bit)  /* SLR table? use Follow */
  916.                 {
  917.                     ASSIGN_SET(look_ahead, 0, follow, rules[rule_no].lhs);
  918.                 }
  919.                 else
  920.                     compute_la(state_no, item_no, look_ahead);
  921.  
  922.                 for ALL_TERMINALS(symbol) /* for all symbols in la set */
  923.                 {
  924.                     if (IS_ELEMENT(look_ahead, symbol))
  925.                     {
  926.                         p = Allocate_node();
  927.                         p -> value = item_no;
  928.  
  929.                         if (action[symbol] == NULL)
  930.                         {
  931.                             symbol_list[symbol] = symbol_root;
  932.                             symbol_root = symbol;
  933.                         }
  934.                         else
  935.                         {
  936.                             /**********************************************/
  937.                             /* Always place the rule with the largest     */
  938.                             /* right-hand side first in the list.         */
  939.                             /**********************************************/
  940.                             n = item_table[action[symbol]
  941.                                                 -> value].rule_number;
  942.                             if (RHS_SIZE(n) >= RHS_SIZE(rule_no))
  943.                             {
  944.                                 p -> value = action[symbol] -> value;
  945.                                 action[symbol] -> value = item_no;
  946.                             }
  947.                         }
  948.  
  949.                         p -> next = action[symbol];
  950.                         action[symbol] = p;
  951.                     }
  952.                 }
  953.             }
  954.  
  955.         /******************************************************************/
  956.         /* At this stage, we have constructed the ACTION map for STATE_NO.*/
  957.         /* ACTION is a map from each symbol into a set of final items.    */
  958.         /* The rules associated with these items are the rules by which   */
  959.         /* to reduce when the lookahead is the symbol in question.        */
  960.         /* SYMBOL_LIST/SYMBOL_ROOT is a list of the non-empty elements of */
  961.         /* ACTION. If the number of elements in a set ACTION(t), for some */
  962.         /* terminal t, is greater than one or it is not empty and STATE_NO*/
  963.         /* contains a shift action on t then STATE_NO has one or more     */
  964.         /* conflict(s). The procedure RESOLVE_CONFLICTS takes care of     */
  965.         /* resolving the conflicts appropriately and returns an ACTION    */
  966.         /* map where each element has either 0 (if the conflicts were     */
  967.         /* shift-reduce conflicts, the shift is given precedence) or 1    */
  968.         /* element (if the conflicts were reduce-reduce conflicts, only   */
  969.         /* the first element in the ACTION(t) list is returned).          */
  970.         /******************************************************************/
  971.             if (symbol_root != NIL)
  972.             {
  973.                 resolve_conflicts(state_no, action,
  974.                                   symbol_list, symbol_root);
  975.  
  976.                 for (symbol = symbol_root;
  977.                      symbol != NIL; symbol = symbol_list[symbol])
  978.                 {
  979.                     if (action[symbol] != NULL)
  980.                     {
  981.                         item_no = action[symbol] -> value;
  982.                         rule_count[item_table[item_no].rule_number]++;
  983.                     }
  984.                 }
  985.             }
  986.         }
  987.  
  988.     /*********************************************************************/
  989.     /* We are now ready to compute the size of the reduce map for        */
  990.     /* STATE_NO (reduce_size) and the default rule.                      */
  991.     /* If the state being processed contains only a single complete item */
  992.     /* then the DEFAULT_RULE was previously computed and the list of     */
  993.     /* symbols is empty.                                                 */
  994.     /* NOTE: a REDUCE_ELEMENT will be allocated for all states, even     */
  995.     /* those that have no reductions at all. This will facilitate the    */
  996.     /* Table Compression routines, for they can assume that such an      */
  997.     /* object exists, and can be used for Default values.                */
  998.     /*********************************************************************/
  999.         reduce_size = 0;
  1000.         if (symbol_root != NIL)
  1001.         {
  1002.         /******************************************************************/
  1003.         /* Compute REDUCE_SIZE, the number of reductions in the state and */
  1004.         /* DEFAULT_RULE: the rule with the highest number of reductions   */
  1005.         /* to it.                                                         */
  1006.         /******************************************************************/
  1007.             n = 0;
  1008.             for (q = statset[state_no].complete_items;
  1009.                  q != NULL; q = q -> next)
  1010.             {
  1011.                 item_no = q -> value;
  1012.                 rule_no = item_table[item_no].rule_number;
  1013.                 symbol = rules[rule_no].lhs;
  1014.                 reduce_size += rule_count[rule_no];
  1015.                 if ((rule_count[rule_no] > n) &&
  1016.                     (no_shift_on_error_sym[state_no]) &&
  1017.                     (symbol != accept_image))
  1018.                 {
  1019.                     n = rule_count[rule_no];
  1020.                     default_rule = rule_no;
  1021.                 }
  1022.             }
  1023.  
  1024.             /*********************************************************/
  1025.             /*   If the removal of single productions is requested   */
  1026.             /* and/or parsing tables will not be output, figure out  */
  1027.             /* if the level of the default option requested permits  */
  1028.             /* default actions, and compute how many reduce actions  */
  1029.             /* can be eliminated as a result.                        */
  1030.             /*********************************************************/
  1031.             if (default_opt == 0)
  1032.                 default_rule = OMEGA;
  1033.             else if (table_opt != OPTIMIZE_TIME &&
  1034.                      table_opt != OPTIMIZE_SPACE &&
  1035.                      ! single_productions_bit)
  1036.             {
  1037.                 q = statset[state_no].complete_items;
  1038.                 if (q -> next == NULL)
  1039.                 {
  1040.                     item_no = q -> value;
  1041.                     rule_no = item_table[item_no].rule_number;
  1042.                     if (default_opt > 2 ||  /* No empty rule defined */
  1043.                         (default_opt == 2 && RHS_SIZE(rule_no) != 0))
  1044.                         reduce_size -= n;
  1045.                     else
  1046.                         default_rule = OMEGA;
  1047.                 }
  1048.                 else if (default_opt > 3)
  1049.                     reduce_size -= n;
  1050.             }
  1051.             num_reductions += reduce_size;
  1052.         }
  1053.  
  1054.         /**************************************************************/
  1055.         /*   NOTE that the default fields are set for all states,     */
  1056.         /* whether or not DEFAULT actions are requested. This is      */
  1057.         /* all right since one can always check whether (DEFAULT > 0) */
  1058.         /* before using these fields.                                 */
  1059.         /**************************************************************/
  1060.         red = Allocate_reduce_map(reduce_size);
  1061.         reduce[state_no] = red;
  1062.  
  1063.         REDUCE_SYMBOL(red, 0)  = DEFAULT_SYMBOL;
  1064.         REDUCE_RULE_NO(red, 0) = default_rule;
  1065.         for (symbol = symbol_root;
  1066.              symbol != NIL; symbol = symbol_list[symbol])
  1067.         {
  1068.             if (action[symbol] != NULL)
  1069.             {
  1070.                 rule_no = item_table[action[symbol] -> value].rule_number;
  1071.                 if (rule_no != default_rule ||
  1072.                     table_opt == OPTIMIZE_SPACE ||
  1073.                     table_opt == OPTIMIZE_TIME  ||
  1074.                     single_productions_bit)
  1075.                 {
  1076.                     REDUCE_SYMBOL(red, reduce_size)  = symbol;
  1077.                     REDUCE_RULE_NO(red, reduce_size) = rule_no;
  1078.                     reduce_size--;
  1079.                 }
  1080.  
  1081.                 free_nodes(action[symbol], action[symbol]);
  1082.                 action[symbol] = NULL;
  1083.             }
  1084.         }
  1085.  
  1086.         /************************************************************/
  1087.         /* Reset RULE_COUNT elements used in this state.            */
  1088.         /************************************************************/
  1089.         for (q = statset[state_no].complete_items;
  1090.              q != NULL; q = q -> next)
  1091.         {
  1092.             rule_no = item_table[q -> value].rule_number;
  1093.             rule_count[rule_no] = 0;
  1094.         }
  1095.     } /* end for ALL_STATES*/
  1096.  
  1097.     printf("\n");
  1098.     fprintf(syslis,"\n\n");
  1099.  
  1100. /****************************************************************/
  1101. /* If the automaton required multiple lookahead, construct the  */
  1102. /* permanent lookahead states.                                  */
  1103. /****************************************************************/
  1104.     if (max_la_state > num_states)
  1105.         create_lastats();
  1106.  
  1107. /****************************************************************/
  1108. /* We are now finished with the LALR(k) construction of the     */
  1109. /* automaton. Clear all temporary space that was used in that   */
  1110. /* process and calculate the maximum lookahead level that was   */
  1111. /* needed.                                                      */
  1112. /****************************************************************/
  1113.     exit_lalrk_process();
  1114.     free_conflict_space();
  1115.  
  1116.     lalr_level = highest_level;
  1117.  
  1118. /****************************************************************/
  1119. /* If the removal of single productions is requested, do that.  */
  1120. /****************************************************************/
  1121.     if (single_productions_bit)
  1122.         remove_single_productions();
  1123.  
  1124. /****************************************************************/
  1125. /* If either more than one lookahead was needed or the removal  */
  1126. /* of single productions was requested, the automaton was       */
  1127. /* transformed with the addition of new states and new          */
  1128. /* transitions. In such a case, we reconstruct the IN_STAT map. */
  1129. /****************************************************************/
  1130.     if (lalr_level > 1 || single_productions_bit)
  1131.     {
  1132.         for ALL_STATES(state_no)
  1133.         { /* First, clear out the previous map */
  1134.             if (in_stat[state_no] != NULL)
  1135.             {
  1136.                 q = in_stat[state_no] -> next; /* point to root */
  1137.                 free_nodes(q, in_stat[state_no]);
  1138.                 in_stat[state_no] = NULL;
  1139.             }
  1140.         }
  1141.  
  1142.         build_in_stat(); /* rebuild in_stat map */
  1143.     }
  1144.  
  1145. /******************************************************************/
  1146. /* Print informational messages and free all temporary space that */
  1147. /* was used to compute lookahead information.                     */
  1148. /******************************************************************/
  1149.     if (not_lrk)
  1150.     {
  1151.         printf("This grammar is not LR(K).\n");
  1152.         fprintf(syslis,"This grammar is not LR(K).\n");
  1153.     }
  1154.     else if (num_rr_conflicts > 0 || num_sr_conflicts > 0)
  1155.     {
  1156.         if (! slr_bit)
  1157.         {
  1158.             if (highest_level != INFINITY)
  1159.             {
  1160.                 printf("This grammar is not LALR(%d).\n",
  1161.                        highest_level);
  1162.                 fprintf(syslis,
  1163.                         "This grammar is not LALR(%d).\n",
  1164.                         highest_level);
  1165.             }
  1166.             else
  1167.             {
  1168.                 printf("This grammar is not LALR(K).\n");
  1169.                 fprintf(syslis,"This grammar is not LALR(K).\n");
  1170.             }
  1171.         }
  1172.         else
  1173.         {
  1174.             printf("This grammar is not SLR(1).\n");
  1175.             fprintf(syslis,"This grammar is not SLR(1).\n");
  1176.         }
  1177.     }
  1178.     else
  1179.     {
  1180.         if (highest_level == 0)
  1181.         {
  1182.             printf("This grammar is LR(0).\n");
  1183.             fprintf(syslis,"This grammar is LR(0).\n");
  1184.         }
  1185.         else if (slr_bit)
  1186.         {
  1187.             printf("This grammar is SLR(1).\n");
  1188.             fprintf(syslis,"This grammar is SLR(1).\n");
  1189.         }
  1190.         else
  1191.         {
  1192.             printf("This grammar is LALR(%d).\n", highest_level);
  1193.             fprintf(syslis,
  1194.                     "This grammar is LALR(%d).\n", highest_level);
  1195.         }
  1196.     }
  1197.  
  1198.     ffree(rule_count);
  1199.     ffree(no_shift_on_error_sym);
  1200.     ffree(symbol_list);
  1201.     ffree(single_complete_item);
  1202.     ffree(action);
  1203.     ffree(look_ahead);
  1204.     if (conflict_symbols != NULL)
  1205.         ffree(conflict_symbols);
  1206.     if (read_set != NULL)
  1207.         ffree(read_set);
  1208.     if (la_index != NULL)
  1209.         ffree(la_index);
  1210.     if (la_set != NULL)
  1211.         ffree(la_set);
  1212.  
  1213.     return;
  1214. } /* end mkrdcts */
  1215.