home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / jikepg12.zip / jikespg / src / produce.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-11-04  |  55.2 KB  |  1,527 lines
  1. /* $Id: produce.c,v 1.2 1999/11/04 14:02:23 shields Exp $ */
  2. /*
  3.  This software is subject to the terms of the IBM Jikes Compiler
  4.  License Agreement available at the following URL:
  5.  http://www.ibm.com/research/jikes.
  6.  Copyright (C) 1983, 1999, International Business Machines Corporation
  7.  and others.  All Rights Reserved.
  8.  You must accept the terms of that agreement to use this software.
  9. */
  10. static char hostfile[] = __FILE__;
  11.  
  12. #include <string.h>
  13. #include "common.h"
  14. #include "header.h"
  15.  
  16. static short *stack,
  17.              *index_of,
  18.              *nt_list,
  19.              *item_list,
  20.              *item_of,
  21.              *next_item,
  22.              *scope_table;
  23.  
  24. static int scope_top = 0;
  25.  
  26. static struct node **direct_produces;
  27.  
  28. static struct scope_elmt
  29. {
  30.     short link,
  31.           item,
  32.           index;
  33. } *scope_element;
  34.  
  35. static BOOLEAN *symbol_seen;
  36.  
  37. static SET_PTR produces,
  38.                right_produces,
  39.                left_produces;
  40.  
  41. static int top;
  42.  
  43. static void compute_produces(int symbol);
  44. static void print_name_map(int symbol);
  45. static void process_scopes(void);
  46. static BOOLEAN is_scope(int item_no);
  47. static BOOLEAN scope_check(int lhs_symbol, int target, int source);
  48. static insert_prefix(int item_no);
  49. static BOOLEAN is_prefix_equal(int item_no, int item_no2);
  50. static insert_suffix(int item_no);
  51. static BOOLEAN is_suffix_equal(int item_no1, int item_no2);
  52. static void print_scopes(void);
  53. static get_shift_symbol(int lhs_symbol);
  54.  
  55. /****************************************************************************/
  56. /*                              PRODUCE:                                    */
  57. /****************************************************************************/
  58. /* This procedure computes for each state the set of non-terminal symbols   */
  59. /* that are required as candidates for secondary error recovery.  If the    */
  60. /* option NAMES=OPTIMIZED is requested, the NAME map is optimized and SYMNO */
  61. /* is updated accordingly.                                                  */
  62. /****************************************************************************/
  63. void produce(void)
  64. {
  65.     /*****************************************************************/
  66.     /* TOP, STACK, and INDEX are used for the digraph algorithm      */
  67.     /* in the routines COMPUTE_PRODUCES.                             */
  68.     /*                                                               */
  69.     /* The array PRODUCES is used to construct two maps:             */
  70.     /*                                                               */
  71.     /* 1) PRODUCES, a mapping from each non-terminal A to the set of */
  72.     /* non-terminals C such that:                                    */
  73.     /*                                                               */
  74.     /*                   A  =>*  x C w                               */
  75.     /*                                                               */
  76.     /* 2) RIGHT_MOST_PRODUCES, a mapping from each non-terminal A to */
  77.     /* the set of non-terminals C such that:                         */
  78.     /*                                                               */
  79.     /*                   C =>+ A x   and   x =>* %empty.             */
  80.     /*                                                               */
  81.     /* NOTE: This is really a reverse right-most produces mapping,   */
  82.     /*       since given the above rule, we say that                 */
  83.     /*       C right-most produces A.                                */
  84.     /*                                                               */
  85.     /*****************************************************************/
  86.  
  87.     int state_no,
  88.         state,
  89.         nt_root,
  90.         item_no,
  91.         item_root,
  92.         rule_no,
  93.         symbol,
  94.         nt,
  95.         i,
  96.         n;
  97.  
  98.     short *names_map;
  99.  
  100.     struct node **goto_domain,
  101.                 *p,
  102.                 *q;
  103.  
  104.     BOOLEAN *name_used,
  105.              end_node;
  106.  
  107.     SET_PTR set;
  108.  
  109.     stack = Allocate_short_array(num_symbols + 1);
  110.     index_of = Allocate_short_array(num_symbols + 1);
  111.     names_map = Allocate_short_array(num_names + 1);
  112.     name_used = Allocate_boolean_array(num_names + 1);
  113.     item_list = Allocate_short_array(num_items + 1);
  114.     nt_list = Allocate_short_array(num_non_terminals + 1);
  115.     nt_list -= (num_terminals + 1);
  116.     set = (SET_PTR)
  117.           calloc(1, non_term_set_size * sizeof(BOOLEAN_CELL));
  118.     if (set == NULL)
  119.         nospace(__FILE__, __LINE__);
  120.  
  121.     produces = (SET_PTR)
  122.                calloc(num_non_terminals,
  123.                       non_term_set_size * sizeof(BOOLEAN_CELL));
  124.     if (produces == NULL)
  125.         nospace(__FILE__, __LINE__);
  126.     produces -= ((num_terminals + 1) * non_term_set_size);
  127.  
  128.     direct_produces = (struct node **)
  129.                       calloc(num_non_terminals, sizeof(struct node *));
  130.     if (direct_produces == NULL)
  131.         nospace(__FILE__, __LINE__);
  132.     direct_produces -= (num_terminals + 1);
  133.  
  134.     goto_domain = (struct node **)
  135.                   calloc(num_states + 1, sizeof(struct node *));
  136.     if (goto_domain == NULL)
  137.         nospace(__FILE__, __LINE__);
  138.  
  139. /*********************************************************************/
  140. /* Note that the space allocated for PRODUCES and DIRECT_PRODUCES    */
  141. /* is automatically initialized to 0 by calloc. Logically, this sets */
  142. /* all the sets in the PRODUCES map to the empty set and all the     */
  143. /* pointers in DIRECT_PRODUCES are set to NULL.                      */
  144. /*                                                                   */
  145. /* Next, PRODUCES is initialized to compute RIGHT_MOST_PRODUCES.     */
  146. /* Also, we count the number of error rules and verify that they are */
  147. /* in the right format.                                              */
  148. /*********************************************************************/
  149.     item_root = NIL;
  150.     for ALL_NON_TERMINALS(nt)
  151.     {
  152.         for (end_node = ((p = clitems[nt]) == NULL);
  153.              ! end_node; end_node = (p == clitems[nt]))
  154.         {
  155.             p = p -> next;
  156.             item_no = p -> value;
  157.             symbol = item_table[item_no].symbol;
  158.             if (symbol IS_A_NON_TERMINAL)
  159.             {
  160.                 i = item_table[item_no].suffix_index;
  161.                 if (IS_IN_SET(first, i, empty) &&
  162.                     (! IS_IN_NTSET(produces, symbol, nt - num_terminals)))
  163.                 {
  164.                     NTSET_BIT_IN(produces, symbol, nt - num_terminals);
  165.                     q = Allocate_node();
  166.                     q -> value = nt;
  167.                     q -> next = direct_produces[symbol];
  168.                     direct_produces[symbol] = q;
  169.                 }
  170.             }
  171.             rule_no = item_table[item_no].rule_number;
  172.             for (i = 0; i < RHS_SIZE(rule_no); i++)
  173.             {
  174.                 if (item_table[item_no + i].symbol == error_image)
  175.                     break;
  176.             }
  177.             item_no += i;
  178.             symbol = item_table[item_no].symbol;
  179.             if (symbol == error_image)
  180.             {
  181.                 if (item_table[item_no + 1].symbol IS_A_NON_TERMINAL && i > 0)
  182.                 {
  183.                    symbol = item_table[item_no + 2].symbol;
  184.                    if (symbol == empty)
  185.                        num_error_rules++;
  186.                 }
  187.                 if (warnings_bit && symbol != empty)
  188.                 {
  189.                     item_list[item_no] = item_root;
  190.                     item_root = item_no;
  191.                 }
  192.             }
  193.             symbol = eoft_image;
  194.         }
  195.     }
  196.  
  197.     /*********************************************************************/
  198.     /* If WARNINGS_BIT is on and some error rules are in the wrong,      */
  199.     /* format, report them.                                              */
  200.     /*********************************************************************/
  201.     if (warnings_bit && item_root != NIL)
  202.     {
  203.         PR_HEADING;
  204.         if (item_list[item_root] == NIL)
  205.             fprintf(syslis,
  206.                     "*** This error rule is not in manual format:\n\n");
  207.         else
  208.             fprintf(syslis,
  209.                     "*** These error rules are not in manual format:\n\n");
  210.         for (item_no = item_root;
  211.              item_no != NIL; item_no = item_list[item_no])
  212.         {
  213.             print_item(item_no);
  214.         }
  215.     }
  216.  
  217. /********************************************************************/
  218. /* Complete the construction of the RIGHT_MOST_PRODUCES map for     */
  219. /* non-terminals using the digraph algorithm.                       */
  220. /* We make sure that each non-terminal A is not present in its own  */
  221. /* PRODUCES set since we are interested in the non-reflexive        */
  222. /* (positive) transitive closure.                                   */
  223. /********************************************************************/
  224.     for ALL_SYMBOLS(i)
  225.         index_of[i] = OMEGA;
  226.  
  227.     top = 0;
  228.     for ALL_NON_TERMINALS(nt)
  229.     {
  230.         if (index_of[nt] == OMEGA)
  231.             compute_produces(nt);
  232.         NTRESET_BIT_IN(produces, nt, nt - num_terminals);
  233.     }
  234.  
  235. /********************************************************************/
  236. /* Construct the minimum subset of the domain of the GOTO map       */
  237. /* needed for automatic secondary level error recovery.   For each  */
  238. /* state, we start out with the set of all nonterminals on which    */
  239. /* there is a transition in that state, and pare it down to a       */
  240. /* subset S, by removing all nonterminals B in S such that there    */
  241. /* is a goto-reduce action on B by a single production.  If the     */
  242. /* READ-REDUCE option is not turned on, then, we check whether or   */
  243. /* not the goto action on B is to an LR(0) reduce state.Once we have*/
  244. /* our subset S, we further reduce its size as follows.  For each   */
  245. /* nonterminal A in S such that there exists another nonterminal    */
  246. /* B in S, where B ^= A,  A ->+ Bx  and  x =>* %empty, we remove A  */
  247. /* from S.                                                          */
  248. /* At the end of this process, the nonterminal elements whose       */
  249. /* NT_LIST values are still OMEGA are precisely the nonterminal     */
  250. /* symbols that are never used as candidates.                       */
  251. /********************************************************************/
  252.     for ALL_NON_TERMINALS(i)
  253.         nt_list[i] = OMEGA;
  254.     nt_list[accept_image] = NIL;
  255.  
  256.     for ALL_STATES(state_no)
  257.     {
  258.         struct goto_header_type go_to;
  259.  
  260.         go_to = statset[state_no].go_to;
  261.         nt_root = NIL;
  262.         INIT_NTSET(set);
  263.  
  264.         for (i = 1; i <= go_to.size; i++)
  265.         {
  266.             symbol = GOTO_SYMBOL(go_to, i);
  267.             state = GOTO_ACTION(go_to, i);
  268.             if (state < 0)
  269.                 rule_no = -state;
  270.             else
  271.             {
  272.                 q = statset[state].kernel_items;
  273.                 item_no = q -> value;
  274.                 if (q -> next != NULL)
  275.                     rule_no = 0;
  276.                 else
  277.                     rule_no = item_table[item_no].rule_number;
  278.             }
  279.             if (rule_no == 0 || RHS_SIZE(rule_no) != 1)
  280.             {
  281.                 nt_list[symbol] = nt_root;
  282.                 nt_root = symbol;
  283.                 NTSET_UNION(set, 0, produces, symbol);
  284.             }
  285.         }
  286.  
  287.         goto_domain[state_no] = NULL;
  288.         for (symbol = nt_root; symbol != NIL; symbol = nt_list[symbol])
  289.         {
  290.             if (! IS_ELEMENT(set, symbol - num_terminals))
  291.             {
  292.                 q = Allocate_node();
  293.                 q -> value = symbol;
  294.                 q -> next = goto_domain[state_no];
  295.                 goto_domain[state_no] = q;
  296.                 gotodom_size++;
  297.             }
  298.         }
  299.     }
  300.  
  301.     /********************************************************************/
  302.     /* Allocate and construct the permanent goto domain structure:      */
  303.     /*   GD_INDEX and GD_RANGE.                                         */
  304.     /********************************************************************/
  305.     n = 0;
  306.     gd_index = Allocate_short_array(num_states + 2);
  307.     gd_range = Allocate_short_array(gotodom_size + 1);
  308.  
  309.     for ALL_STATES(state_no)
  310.     {
  311.         gd_index[state_no] = n + 1;
  312.         for (p = goto_domain[state_no]; p != NULL; q = p, p = p -> next)
  313.             gd_range[++n] = p -> value;
  314.  
  315.         if (goto_domain[state_no] != NULL)
  316.             free_nodes(goto_domain[state_no], q);
  317.     }
  318.     gd_index[num_states + 1] = n + 1;
  319.  
  320.  
  321. /******************************************************************/
  322. /* Remove names assigned to nonterminals that are never used as   */
  323. /* error candidates.                                              */
  324. /******************************************************************/
  325.     if (names_opt == OPTIMIZE_PHRASES)
  326.     {
  327.         /*****************************************************************/
  328.         /* In addition to nonterminals that are never used as candidates,*/
  329.         /* if a nullable nonterminal was assigned a name by default      */
  330.         /* (nonterminals that were "named" by default are identified     */
  331.         /* with negative indices), that name is also removed.            */
  332.         /*****************************************************************/
  333.         for ALL_NON_TERMINALS(symbol)
  334.         {
  335.             if (nt_list[symbol] == OMEGA)
  336.                 symno[symbol].name_index = symno[accept_image].name_index;
  337.             else if (symno[symbol].name_index < 0)
  338.             {
  339.                 if (null_nt[symbol])
  340.                     symno[symbol].name_index = symno[accept_image].name_index;
  341.                 else
  342.                     symno[symbol].name_index = - symno[symbol].name_index;
  343.             }
  344.         }
  345.  
  346.  
  347.         /*******************************************************************/
  348.         /* Adjust name map to remove unused elements and update SYMNO map. */
  349.         /*******************************************************************/
  350.         for (i = 1; i <= num_names; i++)
  351.             name_used[i] = FALSE;
  352.  
  353.         for ALL_SYMBOLS(symbol)
  354.             name_used[symno[symbol].name_index] = TRUE;
  355.  
  356.         n = 0;
  357.         for (i = 1; i <= num_names; i++)
  358.         {
  359.             if (name_used[i])
  360.             {
  361.                 name[++n] = name[i];
  362.                 names_map[i] = n;
  363.             }
  364.         }
  365.         num_names = n;
  366.  
  367.         for ALL_SYMBOLS(symbol)
  368.             symno[symbol].name_index = names_map[symno[symbol].name_index];
  369.     }
  370.  
  371.     /********************************************************************/
  372.     /* If the option LIST_BIT is ON, print the name map.                */
  373.     /********************************************************************/
  374.     if (list_bit)
  375.     {
  376.         PR_HEADING;
  377.         fprintf(syslis, "\nName map:\n");
  378.         output_line_no += 2;
  379.  
  380.         for ALL_SYMBOLS(symbol)
  381.         {
  382.             if (symno[symbol].name_index != symno[accept_image].name_index)
  383.                 print_name_map(symbol);
  384.         }
  385.         for ALL_SYMBOLS(symbol)
  386.         {
  387.             if (symbol != accept_image &&
  388.                 symno[symbol].name_index == symno[accept_image].name_index)
  389.                 print_name_map(symbol);
  390.         }
  391.     }
  392.  
  393.     if (scopes_bit)
  394.         process_scopes();
  395.  
  396.     ffree(stack);
  397.     ffree(index_of);
  398.     ffree(names_map);
  399.     ffree(name_used);
  400.     nt_list += (num_terminals + 1);
  401.     ffree(nt_list);
  402.     ffree(set);
  403.     produces += ((num_terminals + 1) * non_term_set_size);
  404.     ffree(produces);
  405.     direct_produces += (num_terminals + 1);
  406.     ffree(direct_produces);
  407.     ffree(goto_domain);
  408.  
  409.     return;
  410. }
  411.  
  412.  
  413. /******************************************************************/
  414. /*                     COMPUTE_PRODUCES:                          */
  415. /******************************************************************/
  416. /* This procedure is used to compute the transitive closure of    */
  417. /* the PRODUCES, LEFT_PRODUCES and RIGHT_MOST_PRODUCES maps.      */
  418. /******************************************************************/
  419. static void compute_produces(int symbol)
  420. {
  421.     int indx;
  422.     int new_symbol;
  423.  
  424.     struct node *p,
  425.                 *q;
  426.  
  427.     stack[++top] = symbol;
  428.     indx = top;
  429.     index_of[symbol] = indx;
  430.  
  431.     for (p = direct_produces[symbol]; p != NULL; q = p, p = p -> next)
  432.     {
  433.         new_symbol = p -> value;
  434.         if (index_of[new_symbol] == OMEGA)  /* first time seen? */
  435.             compute_produces(new_symbol);
  436.         index_of[symbol] = MIN(index_of[symbol], index_of[new_symbol]);
  437.         NTSET_UNION(produces, symbol, produces, new_symbol);
  438.     }
  439.     if (direct_produces[symbol] != NULL)
  440.         free_nodes(direct_produces[symbol], q);
  441.  
  442.     if (index_of[symbol] == indx)  /*symbol is SCC root */
  443.     {
  444.         for (new_symbol = stack[top];
  445.              new_symbol != symbol; new_symbol = stack[--top])
  446.         {
  447.             ASSIGN_NTSET(produces, new_symbol, produces, symbol);
  448.             index_of[new_symbol] = INFINITY;
  449.         }
  450.  
  451.         index_of[symbol] = INFINITY;
  452.         top--;
  453.     }
  454.  
  455.     return;
  456. }
  457.  
  458.  
  459.  
  460. /******************************************************************/
  461. /*                       PRINT_NAME_MAP:                          */
  462. /******************************************************************/
  463. /* This procedure prints the name associated with a given symbol. */
  464. /* The same format that was used in the procedure DISPLAY_INPUT   */
  465. /* to print aliases is used to print name mappings.               */
  466. /******************************************************************/
  467. static void print_name_map(int symbol)
  468. {
  469.     int len;
  470.  
  471.     char line[PRINT_LINE_SIZE],
  472.          tok[SYMBOL_SIZE + 1];
  473.  
  474.     restore_symbol(tok, RETRIEVE_STRING(symbol));
  475.  
  476.     len = PRINT_LINE_SIZE - 5;
  477.     print_large_token(line, tok, "", len);
  478.     strcat(line, " ::= ");
  479.     restore_symbol(tok, RETRIEVE_NAME(symno[symbol].name_index));
  480.     if (strlen(line) + strlen(tok) > PRINT_LINE_SIZE - 1)
  481.     {
  482.         fprintf(syslis, "\n%s", line);
  483.         ENDPAGE_CHECK;
  484.         len = PRINT_LINE_SIZE - 4;
  485.         print_large_token(line, tok, "    ", len);
  486.     }
  487.     else
  488.        strcat(line, tok);
  489.  
  490.     fprintf(syslis, "\n%s", line);
  491.     ENDPAGE_CHECK;
  492.  
  493.     return;
  494. }
  495.  
  496.  
  497. /******************************************************************/
  498. /*                         PROCESS_SCOPES:                        */
  499. /******************************************************************/
  500. /* Compute set of "scopes" and use it to construct SCOPE map.     */
  501. /******************************************************************/
  502. static void process_scopes(void)
  503. {
  504.     short *prefix_index,
  505.           *suffix_index,
  506.           *state_index;
  507.  
  508.     struct node **states_of;
  509.  
  510.     int num_state_sets = 0,
  511.         i,
  512.         j,
  513.         k,
  514.         n;
  515.  
  516.     short max_prefix_length = 0,
  517.           dot_symbol,
  518.           nt,
  519.           symbol,
  520.           item_root,
  521.           item_no,
  522.           rule_no,
  523.           state_no,
  524.           nt_root;
  525.  
  526.     BOOLEAN end_node;
  527.  
  528.     struct node *p,
  529.                 *q;
  530.  
  531.     prefix_index = Allocate_short_array(num_items + 1);
  532.     suffix_index = Allocate_short_array(num_items + 1);
  533.     item_of = Allocate_short_array(num_non_terminals);
  534.     item_of -= (num_terminals + 1);
  535.     next_item = Allocate_short_array(num_items + 1);
  536.  
  537.     symbol_seen = Allocate_boolean_array(num_non_terminals);
  538.     symbol_seen -= (num_terminals + 1);
  539.     states_of = (struct node **)
  540.                 calloc(num_non_terminals, sizeof(struct node *));
  541.     states_of -= (num_terminals + 1);
  542.     state_index = Allocate_short_array(num_non_terminals);
  543.     state_index -= (num_terminals + 1);
  544.     scope_element = (struct scope_elmt *)
  545.                     calloc(num_items + 1, sizeof(struct scope_elmt));
  546.  
  547. /********************************************************************/
  548. /* Initially, PRODUCES was used to compute the right-most-produces  */
  549. /* map.  We save that map map and make it reflexive.  Recall that   */
  550. /* RIGHT_PRODUCES is a mapping from each nonterminal B into the set */
  551. /* of nonterminals A such that:                                     */
  552. /*                                                                  */
  553. /*    A =>rm* B                                                     */
  554. /*                                                                  */
  555. /* Next, reallocate PRODUCES and initialize it in order to          */
  556. /* construct the LEFT_PRODUCES map. Initially, CALLOC sets PRODUCES */
  557. /* to the empty map.                                                */
  558. /* LEFT_PRODUCES is a mapping  from each nonterminal A into the set */
  559. /* of nonterminals B such that:                                     */
  560. /*                                                                  */
  561. /*    A =>lm* B x                                                   */
  562. /*                                                                  */
  563. /* for some arbitrary string x.                                     */
  564. /*                                                                  */
  565. /* Since A ->* A for all A,  we insert A in PRODUCES(A)  (but not   */
  566. /* in the linked list).                                             */
  567. /*                                                                  */
  568. /********************************************************************/
  569.     right_produces = produces;
  570.     produces = (SET_PTR)
  571.                calloc(num_non_terminals,
  572.                       non_term_set_size * sizeof(BOOLEAN_CELL));
  573.     if (produces == NULL)
  574.         nospace(__FILE__, __LINE__);
  575.     produces -= ((num_terminals + 1) * non_term_set_size);
  576.  
  577.     for ALL_NON_TERMINALS(nt)
  578.     {
  579.         NTSET_BIT_IN(right_produces, nt, nt - num_terminals);
  580.         NTSET_BIT_IN(produces, nt, nt - num_terminals);
  581.  
  582.         direct_produces[nt] = NULL;
  583.  
  584.         for (end_node = ((p = clitems[nt]) == NULL);
  585.              ! end_node; end_node = (p == clitems[nt]))
  586.         {
  587.             p = p -> next;
  588.             for (item_no = p -> value;
  589.                  item_table[item_no].symbol IS_A_NON_TERMINAL;
  590.                  item_no++)
  591.             {
  592.                 symbol = item_table[item_no].symbol;
  593.                 if (! IS_IN_NTSET(produces, nt, symbol - num_terminals))
  594.                 {
  595.                     NTSET_BIT_IN(produces, nt, symbol - num_terminals);
  596.                     q = Allocate_node();
  597.                     q -> value = symbol;
  598.                     q -> next = direct_produces[nt];
  599.                     direct_produces[nt] = q;
  600.                 }
  601.                 if (! null_nt[symbol])
  602.                     break;
  603.             }
  604.         }
  605.     }
  606.  
  607.     /****************************************************************/
  608.     /* Complete the construction of the LEFT_produces map for       */
  609.     /* non_terminals using the digraph algorithm.                   */
  610.     /****************************************************************/
  611.     for ALL_NON_TERMINALS(nt)
  612.         index_of[nt] = OMEGA;
  613.  
  614.     top = 0;
  615.     for ALL_NON_TERMINALS(nt)
  616.     {
  617.         if (index_of[nt] == OMEGA)
  618.             compute_produces(nt);
  619.     }
  620.     left_produces = produces;
  621.  
  622. /********************************************************************/
  623. /* Allocate and initialize the PRODUCES array to construct the      */
  624. /* PRODUCES map.  After allocation, CALLOC sets all sets to empty.  */
  625. /* Since A ->* A for all A,  we insert A in PRODUCES(A)  (but not   */
  626. /* in the linked list).                                             */
  627. /********************************************************************/
  628.     produces = (SET_PTR)
  629.                calloc(num_non_terminals,
  630.                       non_term_set_size * sizeof(BOOLEAN_CELL));
  631.     if (produces == NULL)
  632.         nospace(__FILE__, __LINE__);
  633.     produces -= ((num_terminals + 1) * non_term_set_size);
  634.  
  635.     for ALL_NON_TERMINALS(nt)
  636.     {
  637.         NTSET_BIT_IN(produces, nt, nt - num_terminals);
  638.  
  639.         direct_produces[nt] = NULL;
  640.  
  641.         for (end_node = ((p = clitems[nt]) == NULL);
  642.              ! end_node; end_node = (p == clitems[nt]))
  643.         {
  644.             p = p -> next;
  645.             for (item_no = p -> value;
  646.                  item_table[item_no].symbol != empty; item_no++)
  647.             {
  648.                 symbol = item_table[item_no].symbol;
  649.                 if (symbol IS_A_NON_TERMINAL)
  650.                 {
  651.                     if (! IS_IN_NTSET(produces, nt, symbol - num_terminals))
  652.                     {
  653.                         NTSET_BIT_IN(produces, nt, symbol - num_terminals);
  654.                         q = Allocate_node();
  655.                         q -> value = symbol;
  656.                         q -> next = direct_produces[nt];
  657.                         direct_produces[nt] = q;
  658.                     }
  659.                 }
  660.             }
  661.         }
  662.     }
  663.  
  664.     /****************************************************************/
  665.     /* Complete the construction of the PRODUCES map for            */
  666.     /* non_terminals using the digraph algorithm.                   */
  667.     /*                                                              */
  668.     /* Since $ACC =>* x A y for all nonterminal A in the grammar, a */
  669.     /* single call to COMPUTE_PRODUCES does the trick.              */
  670.     /****************************************************************/
  671.     for ALL_NON_TERMINALS(nt)
  672.         index_of[nt] = OMEGA;
  673.     top = 0;
  674.     compute_produces(accept_image);
  675.  
  676. /********************************************************************/
  677. /* Construct a mapping from each non_terminal A into the set of     */
  678. /* items of the form [B  ->  x . A y].                              */
  679. /********************************************************************/
  680.     for ALL_NON_TERMINALS(nt)
  681.         item_of[nt] = NIL;
  682.  
  683.     for ALL_ITEMS(item_no)
  684.     {
  685.         dot_symbol = item_table[item_no].symbol;
  686.         if (dot_symbol IS_A_NON_TERMINAL)
  687.         {
  688.             next_item[item_no] = item_of[dot_symbol];
  689.             item_of[dot_symbol] = item_no;
  690.         }
  691.     }
  692.  
  693. /********************************************************************/
  694. /* Construct a list of scoped items in ITEM_LIST.                   */
  695. /* Scoped items are derived from rules of the form  A -> x B y such */
  696. /* that B =>* w A z, %empty not in FIRST(y), and it is not the case */
  697. /* that x = %empty and B ->* A v.                                   */
  698. /* Scoped items may also be identified by the user, using %error    */
  699. /* productions.                                                     */
  700. /* As scoped items are added to the list, we keep track of the      */
  701. /* longest prefix encountered.  This is subsequently used to        */
  702. /* bucket sort the scoped items in descending order of the length    */
  703. /* of their prefixes.                                               */
  704. /********************************************************************/
  705.     for ALL_ITEMS(item_no)
  706.         item_list[item_no] = OMEGA;
  707.  
  708.     item_root = NIL;
  709.     for ALL_ITEMS(item_no)
  710.     {
  711.         dot_symbol = item_table[item_no].symbol;
  712.         if (dot_symbol == error_image)
  713.         {
  714.             if (item_table[item_no].dot != 0 &&
  715.                 (! IS_IN_SET(first,
  716.                              item_table[item_no].suffix_index, empty)))
  717.             {
  718.                 if (item_list[item_no] == OMEGA)
  719.                 {
  720.                     item_list[item_no] = item_root;
  721.                     item_root = item_no;
  722.                     max_prefix_length = MAX(max_prefix_length,
  723.                                             item_table[item_no].dot);
  724.                 }
  725.             }
  726.         }
  727.         else if (dot_symbol IS_A_NON_TERMINAL)
  728.         {
  729.             symbol = rules[item_table[item_no].rule_number].lhs;
  730.             if (! IS_IN_SET(first, item_table[item_no].suffix_index,
  731.                             empty) &&
  732.                 IS_IN_NTSET(produces, dot_symbol, symbol - num_terminals))
  733.             {
  734.                 if (is_scope(item_no))
  735.                 {
  736.                     for (i = item_no + 1; ;i++)
  737.                     {
  738.                         symbol = item_table[i].symbol;
  739.                         if (symbol IS_A_TERMINAL)
  740.                             break;
  741.                         if (! null_nt[symbol])
  742.                             break;
  743.                     }
  744.                     if (symbol IS_A_NON_TERMINAL)
  745.                     {
  746.                         for ALL_NON_TERMINALS(nt)
  747.                             symbol_seen[nt] = FALSE;
  748.                         symbol = get_shift_symbol(symbol);
  749.                     }
  750.  
  751.                     if (symbol != empty && item_list[i] == OMEGA)
  752.                     {
  753.                         item_list[i] = item_root;
  754.                         item_root = i;
  755.                         max_prefix_length = MAX(max_prefix_length,
  756.                                                 item_table[i].dot);
  757.                     }
  758.                 }
  759.             }
  760.         }
  761.     }
  762.  
  763. /*********************************************************************/
  764. /* In this loop, the prefix and suffix string for each scope in      */
  765. /* entered into a table.  We also use the SYMBOL_SEEN array to       */
  766. /* identify the set of left-hand side symbols associated with the    */
  767. /* scopes.                                                           */
  768. /*********************************************************************/
  769.     scope_table = Allocate_short_array(SCOPE_SIZE);
  770.     for (i = 0; i < SCOPE_SIZE; i++)
  771.         scope_table[i] = NIL;
  772.  
  773.     for ALL_NON_TERMINALS(nt)
  774.         symbol_seen[nt] = FALSE;
  775.  
  776.     for (item_no = item_root; item_no != NIL; item_no = item_list[item_no])
  777.     {
  778.         rule_no = item_table[item_no].rule_number;
  779.         symbol = rules[rule_no].lhs;
  780.         num_scopes = num_scopes + 1;
  781.  
  782.         symbol_seen[symbol] = TRUE;
  783.  
  784.         prefix_index[item_no] = insert_prefix(item_no);
  785.         suffix_index[item_no] = insert_suffix(item_no);
  786.     }
  787.     ffree(scope_table);
  788.  
  789. /*********************************************************************/
  790. /* We now construct a mapping from each nonterminal symbol that is   */
  791. /* the left-hand side of a rule containing scopes into the set of    */
  792. /* states that has a transition on the nonterminal in question.      */
  793. /*********************************************************************/
  794.     nt_root = NIL;
  795.     for ALL_NON_TERMINALS(nt)
  796.         states_of[nt] = NULL;
  797.  
  798.     for ALL_STATES(state_no)
  799.     {
  800.         struct goto_header_type go_to;
  801.  
  802.         go_to = statset[state_no].go_to;
  803.         for (i = 1; i <= go_to.size; i++)
  804.         {
  805.             symbol = GOTO_SYMBOL(go_to, i);
  806.             if (symbol_seen[symbol])
  807.             {
  808.                 if (states_of[symbol] == NULL)
  809.                 {
  810.                     nt_list[symbol] = nt_root;
  811.                     nt_root = symbol;
  812.                     num_state_sets = num_state_sets + 1;
  813.                 }
  814.                 q = Allocate_node();
  815.                 q -> value = state_no;
  816.                 q -> next  = states_of[symbol];
  817.                 states_of[symbol] = q;
  818.             }
  819.         }
  820.     }
  821.  
  822.     right_produces += ((num_terminals + 1) * non_term_set_size);
  823.     ffree(right_produces);
  824.     left_produces += ((num_terminals + 1) * non_term_set_size);
  825.     ffree(left_produces);
  826.  
  827. /*********************************************************************/
  828. /* Next, we used the optimal partition procedure to compress the     */
  829. /* space used by the sets of states, allocate the SCOPE structure    */
  830. /* and store the compressed sets of states in it.                    */
  831. /* We also sort the list of items by the length of their prefixes in */
  832. /* descending order.  This is done primarily as an optimization.     */
  833. /* If a longer prefix matches prior to a shorter one, the parsing    */
  834. /* will terminate quicker.                                           */
  835. /*********************************************************************/
  836. process_scope_states:
  837.     {
  838.         SET_PTR collection;
  839.  
  840.         short *element_size,
  841.               *list,
  842.               *start,
  843.               *stack,
  844.               *ordered_symbol,
  845.               *state_list,
  846.               *bucket;
  847.  
  848.         int state_root,
  849.             state_no;
  850.  
  851.         state_set_size = num_states / SIZEOF_BC
  852.                                     + (num_states % SIZEOF_BC ? 1 : 0);
  853.         collection = (SET_PTR)
  854.                      calloc(num_state_sets + 1,
  855.                             state_set_size * sizeof(BOOLEAN_CELL));
  856.         if (collection == NULL)
  857.             nospace(__FILE__, __LINE__);
  858.  
  859.         element_size = Allocate_short_array(num_state_sets + 1);
  860.         start = Allocate_short_array(num_state_sets + 2);
  861.         stack = Allocate_short_array(num_state_sets + 1);
  862.         ordered_symbol = Allocate_short_array(num_state_sets + 1);
  863.         list = Allocate_short_array(num_state_sets + 1);
  864.         state_list = Allocate_short_array(num_states + 1);
  865.         bucket = Allocate_short_array(max_prefix_length + 1);
  866.  
  867.         for (symbol = nt_root, i = 1;
  868.              symbol != NIL; symbol = nt_list[symbol], i++)
  869.         {
  870.             list[i] = i;
  871.             ordered_symbol[i] = symbol;
  872.             EMPTY_COLLECTION_SET(i);
  873.             element_size[i] = 0;
  874.             for (p = states_of[symbol]; p != NULL; p = p -> next)
  875.             {
  876.                 element_size[i]++;
  877.                 SET_COLLECTION_BIT(i, p -> value);
  878.             }
  879.         }
  880.  
  881.         partset(collection, element_size, list, start, stack, num_state_sets);
  882.  
  883.         for (i = 1; i <= num_state_sets; i++)
  884.         {
  885.             symbol = ordered_symbol[i];
  886.             state_index[symbol] = ABS(start[i]);
  887.         }
  888.         scope_state_size = start[num_state_sets + 1] - 1;
  889.  
  890.         scope = (struct scope_type *)
  891.                 calloc(num_scopes + 1, sizeof(struct scope_type));
  892.         if (scope == NULL)
  893.             nospace(__FILE__, __LINE__);
  894.         scope_right_side = Allocate_short_array(scope_rhs_size + 1);
  895.         scope_state = Allocate_short_array(scope_state_size + 1);
  896.  
  897.         k = 0;
  898.         for (i = 0; i <= (int) num_states; i++)
  899.             state_list[i] = OMEGA;
  900.  
  901.         for (i = 1; i <= num_state_sets; i++)
  902.         {
  903.             if (start[i] > 0)
  904.             {
  905.                 state_root = 0;
  906.                 state_list[state_root] = NIL;
  907.  
  908.                 for (end_node = ((j = i) == NIL);
  909.                      ! end_node; end_node = (j == i))
  910.                 {
  911.                     j = stack[j];
  912.                     symbol = ordered_symbol[j];
  913.                     for (p = states_of[symbol]; p != NULL; p = p -> next)
  914.                     {
  915.                         state_no = p -> value;
  916.                         if (state_list[state_no] == OMEGA)
  917.                         {
  918.                             state_list[state_no] = state_root;
  919.                             state_root = state_no;
  920.                         }
  921.                     }
  922.                 }
  923.  
  924.                 for (state_no = state_root;
  925.                      state_no != NIL; state_no = state_root)
  926.                 {
  927.                     state_root = state_list[state_no];
  928.                     state_list[state_no] = OMEGA;
  929.                     k++;
  930.                     scope_state[k] = state_no;
  931.                 }
  932.             }
  933.         }
  934.  
  935.         for (symbol = nt_root; symbol != NIL; symbol = nt_list[symbol])
  936.         {
  937.             for (p = states_of[symbol]; p != NULL; q = p, p = p -> next)
  938.                 ;
  939.             free_nodes(states_of[symbol], q);
  940.         }
  941.  
  942. /***********************************************************************/
  943. /* Use the BUCKET array as a base to partition the scoped items        */
  944. /* based on the length of their prefixes.  The list of items in each   */
  945. /* bucket is kept in the NEXT_ITEM array sorted in descending order    */
  946. /* of the length of the right-hand side of the item.                   */
  947. /* Items are kept sorted in that fashion because when two items have   */
  948. /* the same prefix, we want the one with the shortest suffix to be     */
  949. /* chosen. In other words, if we have two scoped items, say:           */
  950. /*                                                                     */
  951. /*    A ::= x . y       and      B ::= x . z     where |y| < |z|       */
  952. /*                                                                     */
  953. /* and both of them are applicable in a given context with similar     */
  954. /* result, then we always want A ::= x . y to be used.                 */
  955. /***********************************************************************/
  956.         for (i = 1; i <= max_prefix_length; i++)
  957.             bucket[i] = NIL;
  958.  
  959.         for (item_no = item_root;
  960.              item_no != NIL; item_no = item_list[item_no])
  961.         {
  962.             int tail;
  963.  
  964.             k = item_table[item_no].dot;
  965.             for (i = bucket[k]; i != NIL; tail = i, i = next_item[i])
  966.             {
  967.                 if (RHS_SIZE(item_table[item_no].rule_number) >=
  968.                     RHS_SIZE(item_table[i].rule_number))
  969.                    break;
  970.             }
  971.  
  972.             next_item[item_no] = i;
  973.             if (i == bucket[k])
  974.                  bucket[k] = item_no;       /* insert at the beginning */
  975.             else next_item[tail] = item_no; /* insert in middle or end */
  976.         }
  977.  
  978. /*********************************************************************/
  979. /* Reconstruct list of scoped items in sorted order. Since we want   */
  980. /* the items in descending order, we start with the smallest bucket  */
  981. /* proceeding to the largest one and insert the items from each      */
  982. /* bucket in LIFO order in ITEM_LIST.                                */
  983. /*********************************************************************/
  984.         item_root = NIL;
  985.         for (k = 1; k <= max_prefix_length; k++)
  986.         {
  987.             for (item_no = bucket[k];
  988.                  item_no != NIL; item_no = next_item[item_no])
  989.             {
  990.                 item_list[item_no] = item_root;
  991.                 item_root = item_no;
  992.             }
  993.         }
  994.  
  995.         ffree(collection);
  996.         ffree(element_size);
  997.         ffree(start);
  998.         ffree(stack);
  999.         ffree(ordered_symbol);
  1000.         ffree(state_list);
  1001.         ffree(list);
  1002.         ffree(bucket);
  1003.     } /* End PROCESS_SCOPE_STATES */
  1004.  
  1005. /*********************************************************************/
  1006. /* Next, we initialize the remaining fields of the SCOPE structure.  */
  1007. /*********************************************************************/
  1008.     item_no = item_root;
  1009.     for (i = 1; item_no != NIL; i++)
  1010.     {
  1011.         scope[i].prefix = prefix_index[item_no];
  1012.         scope[i].suffix = suffix_index[item_no];
  1013.         rule_no = item_table[item_no].rule_number;
  1014.         scope[i].lhs_symbol = rules[rule_no].lhs;
  1015.         symbol = rhs_sym[rules[rule_no].rhs + item_table[item_no].dot];
  1016.         if (symbol IS_A_TERMINAL)
  1017.             scope[i].look_ahead = symbol;
  1018.         else
  1019.         {
  1020.             for ALL_NON_TERMINALS(j)
  1021.                 symbol_seen[j] = FALSE;
  1022.             scope[i].look_ahead = get_shift_symbol(symbol);
  1023.         }
  1024.         scope[i].state_set = state_index[scope[i].lhs_symbol];
  1025.         item_no = item_list[item_no];
  1026.     }
  1027.  
  1028.     for (j = 1; j <= scope_top; j++)
  1029.     {
  1030.         if (scope_element[j].item < 0)
  1031.         {
  1032.             item_no = -scope_element[j].item;
  1033.             rule_no = item_table[item_no].rule_number;
  1034.             n = scope_element[j].index;
  1035.             for (k = rules[rule_no].rhs+item_table[item_no].dot - 1;
  1036.                  k >= rules[rule_no].rhs; /* symbols before dot*/
  1037.                  k--)
  1038.                 scope_right_side[n++] = rhs_sym[k];
  1039.         }
  1040.         else
  1041.         {
  1042.             item_no = scope_element[j].item;
  1043.             rule_no = item_table[item_no].rule_number;
  1044.             n = scope_element[j].index;
  1045.             for (k = rules[rule_no].rhs + item_table[item_no].dot;
  1046.                  k < rules[rule_no + 1].rhs; /* symbols after dot */
  1047.                  k++)
  1048.             {
  1049.                 symbol = rhs_sym[k];
  1050.                 if (symbol IS_A_NON_TERMINAL)
  1051.                 {
  1052.                     if (! null_nt[symbol])
  1053.                         scope_right_side[n++] = rhs_sym[k];
  1054.                 }
  1055.                 else if (symbol != error_image)
  1056.                     scope_right_side[n++] = rhs_sym[k];
  1057.             }
  1058.         }
  1059.         scope_right_side[n] = 0;
  1060.     }
  1061.  
  1062.     if (list_bit)
  1063.         print_scopes();
  1064.  
  1065.     ffree(prefix_index);
  1066.     ffree(suffix_index);
  1067.     item_of += (num_terminals + 1);
  1068.     ffree(item_of);
  1069.     ffree(next_item);
  1070.     symbol_seen += (num_terminals + 1);
  1071.     ffree(symbol_seen);
  1072.     states_of += (num_terminals + 1);
  1073.     ffree(states_of);
  1074.     state_index += (num_terminals + 1);
  1075.     ffree(state_index);
  1076.     ffree(scope_element);
  1077.  
  1078.     return;
  1079. }
  1080.  
  1081.  
  1082. /*********************************************************************/
  1083. /*                              IS_SCOPE:                            */
  1084. /*********************************************************************/
  1085. /* This procedure checks whether or not an item of the form:         */
  1086. /* [A  ->  w B x  where  B ->* y A z  is a valid scope.              */
  1087. /*                                                                   */
  1088. /* Such an item is a valid scope if the following conditions hold:   */
  1089. /*                                                                   */
  1090. /* 1) it is not the case that x =>* %empty                           */
  1091. /* 2) either it is not the case that w =>* %empty or it is not the   */
  1092. /*    case that B =>lm* A.                                           */
  1093. /* 3) it is not the case that whenever A is introduced through       */
  1094. /*    closure, it is introduced by a nonterminal C where C =>rm* A   */
  1095. /*    and C =>rm+ B.                                                 */
  1096. /*********************************************************************/
  1097. static BOOLEAN is_scope(int item_no)
  1098. {
  1099.     int i,
  1100.         nt,
  1101.         lhs_symbol,
  1102.         target,
  1103.         symbol;
  1104.  
  1105.     for (i = item_no - item_table[item_no].dot; i < item_no; i++)
  1106.     {
  1107.         symbol = item_table[i].symbol;
  1108.         if (symbol IS_A_TERMINAL)
  1109.             return(TRUE);
  1110.         if (! null_nt[symbol])
  1111.             return(TRUE);
  1112.     }
  1113.  
  1114.     lhs_symbol = rules[item_table[item_no].rule_number].lhs;
  1115.     target = item_table[item_no].symbol;
  1116.     if (IS_IN_NTSET(left_produces, target, lhs_symbol - num_terminals))
  1117.         return(FALSE);
  1118.  
  1119.     if (item_table[item_no].dot > 0)
  1120.         return(TRUE);
  1121.  
  1122.     for ALL_NON_TERMINALS(nt)
  1123.         symbol_seen[nt] = FALSE;
  1124.  
  1125.     return(scope_check(lhs_symbol, target, lhs_symbol));
  1126. }
  1127.  
  1128. /*********************************************************************/
  1129. /*                             SCOPE_CHECK:                          */
  1130. /*********************************************************************/
  1131. /* Given a nonterminal LHS_SYMBOL and a nonterminal TARGET where,    */
  1132. /*                                                                   */
  1133. /*                     LHS_SYMBOL ::= TARGET x                       */
  1134. /*                                                                   */
  1135. /* find out if whenever LHS_SYMBOL is introduced through closure, it */
  1136. /* is introduced by a nonterminal SOURCE such that                   */
  1137. /*                                                                   */
  1138. /*                     SOURCE ->rm* LHS_SYMBOL                       */
  1139. /*                                                                   */
  1140. /*                               and                                 */
  1141. /*                                                                   */
  1142. /*                     SOURCE ->rm+ TARGET                           */
  1143. /*                                                                   */
  1144. /*********************************************************************/
  1145. static BOOLEAN scope_check(int lhs_symbol, int target, int source)
  1146. {
  1147.     int item_no,
  1148.         rule_no,
  1149.         symbol;
  1150.  
  1151.     symbol_seen[source] = TRUE;
  1152.  
  1153.     if (IS_IN_NTSET(right_produces, target, source - num_terminals) &&
  1154.         IS_IN_NTSET(right_produces, lhs_symbol, source - num_terminals))
  1155.         return(FALSE);
  1156.  
  1157.     for (item_no = item_of[source];
  1158.          item_no != NIL; item_no = next_item[item_no])
  1159.     {
  1160.         if (item_table[item_no].dot != 0)
  1161.             return(TRUE);
  1162.  
  1163.         rule_no = item_table[item_no].rule_number;
  1164.         symbol = rules[rule_no].lhs;
  1165.         if (! symbol_seen[symbol])        /* not yet processed */
  1166.         {
  1167.             if (scope_check(lhs_symbol, target, symbol))
  1168.                 return(TRUE);
  1169.         }
  1170.     }
  1171.  
  1172.     return(FALSE);
  1173. }
  1174.  
  1175.  
  1176. /*********************************************************************/
  1177. /*                       INSERT_PREFIX:                              */
  1178. /*********************************************************************/
  1179. /* This procedure takes as argument an item and inserts the string   */
  1180. /* prefix of the item preceeding the "dot" into the scope table, if  */
  1181. /* that string is not already there.  In any case, the index  number */
  1182. /* associated with the prefix in question is returned.               */
  1183. /* NOTE that since both prefixes and suffixes are entered in the     */
  1184. /* table, the prefix of a given item, ITEM_NO, is encoded as         */
  1185. /* -ITEM_NO, whereas the suffix of that item is encoded as +ITEM_NO. */
  1186. /*********************************************************************/
  1187. static insert_prefix(int item_no)
  1188. {
  1189.     int i,
  1190.         j,
  1191.         rule_no;
  1192.  
  1193.     unsigned long hash_address = 0;
  1194.  
  1195.     rule_no = item_table[item_no].rule_number;
  1196.     for (i = rules[rule_no].rhs;    /* symbols before dot */
  1197.          i < rules[rule_no].rhs + item_table[item_no].dot; i++)
  1198.         hash_address += rhs_sym[i];
  1199.  
  1200.     i = hash_address % SCOPE_SIZE;
  1201.  
  1202.     for (j = scope_table[i]; j != NIL; j = scope_element[j].link)
  1203.     {
  1204.         if (is_prefix_equal(scope_element[j].item, item_no))
  1205.             return(scope_element[j].index);
  1206.     }
  1207.     scope_top++;
  1208.     scope_element[scope_top].item = -item_no;
  1209.     scope_element[scope_top].index = scope_rhs_size + 1;
  1210.     scope_element[scope_top].link = scope_table[i];
  1211.     scope_table[i] = scope_top;
  1212.  
  1213.     scope_rhs_size += (item_table[item_no].dot + 1);
  1214.  
  1215.     return(scope_element[scope_top].index);
  1216. }
  1217.  
  1218.  
  1219. /******************************************************************/
  1220. /*                      IS_PREFIX_EQUAL:                          */
  1221. /******************************************************************/
  1222. /* This boolean function takes two items as arguments and checks  */
  1223. /* whether or not they have the same prefix.                      */
  1224. /******************************************************************/
  1225. static BOOLEAN is_prefix_equal(int item_no, int item_no2)
  1226. {
  1227.     int item_no1,
  1228.         start,
  1229.         dot,
  1230.         i,
  1231.         j;
  1232.  
  1233.     if (item_no > 0)    /* a suffix */
  1234.         return(FALSE);
  1235.  
  1236.     item_no1 = -item_no;
  1237.     if (item_table[item_no1].dot != item_table[item_no2].dot)
  1238.         return(FALSE);
  1239.  
  1240.     j = rules[item_table[item_no1].rule_number].rhs;
  1241.     start = rules[item_table[item_no2].rule_number].rhs;
  1242.     dot = start + item_table[item_no2].dot - 1;
  1243.     for (i = start; i <= dot; i++)    /* symbols before dot */
  1244.     {
  1245.         if (rhs_sym[i] != rhs_sym[j])
  1246.             return(FALSE);
  1247.         j++;
  1248.     }
  1249.  
  1250.     return(TRUE);
  1251. }
  1252.  
  1253.  
  1254. /*********************************************************************/
  1255. /*                            INSERT_SUFFIX:                         */
  1256. /*********************************************************************/
  1257. /* This procedure is analoguous to INSERT_PREFIX.  It takes as       */
  1258. /* argument an item, and inserts the suffix string following the dot */
  1259. /* in the item into the scope table, if it is not already there.     */
  1260. /* In any case, it returns the index associated with the suffix.     */
  1261. /* When inserting a suffix into the table, all nullable nonterminals */
  1262. /* in the suffix are disregarded.                                    */
  1263. /*********************************************************************/
  1264. static insert_suffix(int item_no)
  1265. {
  1266.     int i,
  1267.         j,
  1268.         rule_no,
  1269.         num_elements = 0;
  1270.  
  1271.     unsigned long hash_address = 0;
  1272.  
  1273.     rule_no = item_table[item_no].rule_number;
  1274.     for (i = rules[rule_no].rhs + item_table[item_no].dot;
  1275.          i < rules[rule_no + 1].rhs; /* symbols after dot */
  1276.          i++)
  1277.     {
  1278.         if (rhs_sym[i] IS_A_NON_TERMINAL)
  1279.         {
  1280.             if (! null_nt[rhs_sym[i]])
  1281.             {
  1282.                 hash_address += rhs_sym[i];
  1283.                 num_elements++;
  1284.             }
  1285.         }
  1286.         else if (rhs_sym[i] != error_image)
  1287.         {
  1288.             hash_address += rhs_sym[i];
  1289.             num_elements++;
  1290.         }
  1291.     }
  1292.  
  1293.     i = hash_address % SCOPE_SIZE;
  1294.  
  1295.     for (j = scope_table[i]; j != NIL; j = scope_element[j].link)
  1296.     {
  1297.         if (is_suffix_equal(scope_element[j].item, item_no))
  1298.             return(scope_element[j].index);
  1299.     }
  1300.     scope_top++;
  1301.     scope_element[scope_top].item = item_no;
  1302.     scope_element[scope_top].index = scope_rhs_size + 1;
  1303.     scope_element[scope_top].link = scope_table[i];
  1304.     scope_table[i] = scope_top;
  1305.  
  1306.     scope_rhs_size += (num_elements + 1);
  1307.  
  1308.     return(scope_element[scope_top].index);
  1309. }
  1310.  
  1311.  
  1312. /******************************************************************/
  1313. /*                        IS_SUFFIX_EQUAL:                        */
  1314. /******************************************************************/
  1315. /* This boolean function takes two items as arguments and checks  */
  1316. /* whether or not they have the same suffix.                      */
  1317. /******************************************************************/
  1318. static BOOLEAN is_suffix_equal(int item_no1, int item_no2)
  1319. {
  1320.     int rule_no,
  1321.         dot1,
  1322.         dot2,
  1323.         i,
  1324.         j;
  1325.  
  1326.     if (item_no1 < 0)      /* a prefix */
  1327.         return(FALSE);
  1328.  
  1329.     rule_no = item_table[item_no1].rule_number;
  1330.     i = rules[rule_no].rhs + item_table[item_no1].dot;
  1331.     dot1 = rules[rule_no + 1].rhs - 1;
  1332.  
  1333.     rule_no = item_table[item_no2].rule_number;
  1334.     j = rules[rule_no].rhs + item_table[item_no2].dot;
  1335.     dot2 = rules[rule_no + 1].rhs - 1;
  1336.  
  1337.     while (i <= dot1 && j <= dot2) /* non-nullable syms before dot */
  1338.     {
  1339.         if (rhs_sym[i] IS_A_NON_TERMINAL)
  1340.         {
  1341.             if (null_nt[rhs_sym[i]])
  1342.             {
  1343.                 i++;
  1344.                 continue;
  1345.             }
  1346.         }
  1347.         else if (rhs_sym[i] == error_image)
  1348.         {
  1349.             i++;
  1350.             continue;
  1351.         }
  1352.  
  1353.         if (rhs_sym[j] IS_A_NON_TERMINAL)
  1354.         {
  1355.             if (null_nt[rhs_sym[j]])
  1356.             {
  1357.                 j++;
  1358.                 continue;
  1359.             }
  1360.         }
  1361.         else if (rhs_sym[j] == error_image)
  1362.         {
  1363.             j++;
  1364.             continue;
  1365.         }
  1366.  
  1367.         if (rhs_sym[i] != rhs_sym[j])
  1368.             return(FALSE);
  1369.  
  1370.         j++;
  1371.         i++;
  1372.     }
  1373.  
  1374.     for (; i <= dot1; i++)
  1375.     {
  1376.         if (rhs_sym[i] IS_A_NON_TERMINAL)
  1377.         {
  1378.             if (! null_nt[rhs_sym[i]])
  1379.                 return(FALSE);
  1380.         }
  1381.         else if (rhs_sym[i] != error_image)
  1382.             return(FALSE);
  1383.     }
  1384.  
  1385.     for (; j <= dot2; j++)
  1386.     {
  1387.         if (rhs_sym[j] IS_A_NON_TERMINAL)
  1388.         {
  1389.             if (! null_nt[rhs_sym[j]])
  1390.                 return(FALSE);
  1391.         }
  1392.         else if (rhs_sym[j] != error_image)
  1393.             return(FALSE);
  1394.     }
  1395.  
  1396.     return(TRUE);
  1397. }
  1398.  
  1399.  
  1400. /******************************************************************/
  1401. /*                         PRINT_SCOPES:                          */
  1402. /******************************************************************/
  1403. /* This procedure is similar to the global procedure PTITEM.      */
  1404. /******************************************************************/
  1405. static void print_scopes(void)
  1406. {
  1407.     int len,
  1408.         offset,
  1409.         i,
  1410.         k,
  1411.         symbol;
  1412.  
  1413.     char line[PRINT_LINE_SIZE + 1],
  1414.          tok[SYMBOL_SIZE + 1],
  1415.          tmp[PRINT_LINE_SIZE];
  1416.  
  1417.     PR_HEADING;
  1418.     fprintf(syslis, "\nScopes:\n");
  1419.     output_line_no += 2;
  1420.  
  1421.     for (k=1; k <= num_scopes; k++)
  1422.     {
  1423.         symbol = scope[k].lhs_symbol;
  1424.         restore_symbol(tok, RETRIEVE_STRING(symbol));
  1425.         len = PRINT_LINE_SIZE - 5;
  1426.         print_large_token(line, tok, "", len);
  1427.         strcat(line, " ::= ");
  1428.         i = (PRINT_LINE_SIZE / 2) - 1;
  1429.         offset = MIN(strlen(line) - 1, i);
  1430.         len = PRINT_LINE_SIZE - (offset + 4);
  1431.  
  1432.         /* locate end of list */
  1433.         for (i = scope[k].prefix; scope_right_side[i] != 0; i++)
  1434.             ;
  1435.  
  1436.         for (i = i - 1; i >= scope[k].prefix; i--) /* symbols before dot */
  1437.         {
  1438.             symbol = scope_right_side[i];
  1439.             restore_symbol(tok, RETRIEVE_STRING(symbol));
  1440.             if (strlen(line) + strlen(tok) > PRINT_LINE_SIZE - 4)
  1441.             {
  1442.                 fprintf(syslis, "\n%s", line);
  1443.                 ENDPAGE_CHECK;
  1444.                 fill_in(tmp, offset, ' ');
  1445.                 print_large_token(line, tok, tmp, len);
  1446.             }
  1447.             else
  1448.                 strcat(line, tok);
  1449.             strcat(line, BLANK);
  1450.         }
  1451.  
  1452. /*********************************************************************/
  1453. /* We now add a dot "." to the output line, and print the remaining  */
  1454. /* symbols in the right hand side.                                   */
  1455. /*********************************************************************/
  1456.         strcat(line, " .");
  1457.         len = PRINT_LINE_SIZE - (offset + 1);
  1458.  
  1459.         for (i = scope[k].suffix;  scope_right_side[i] != 0; i++)
  1460.         {
  1461.             symbol = scope_right_side[i];
  1462.             restore_symbol(tok, RETRIEVE_STRING(symbol));
  1463.             if (strlen(line) + strlen(tok) > PRINT_LINE_SIZE - 1)
  1464.             {
  1465.                 fprintf(syslis, "\n%s", line);
  1466.                 ENDPAGE_CHECK;
  1467.                 fill_in(tmp, offset, ' ');
  1468.                 print_large_token(line, tok, tmp, len);
  1469.             }
  1470.             else
  1471.                 strcat(line, tok);
  1472.             strcat(line, BLANK);
  1473.         }
  1474.         fprintf(syslis, "\n%s", line);
  1475.         ENDPAGE_CHECK;
  1476.     }
  1477.  
  1478.     return;
  1479. }
  1480.  
  1481.  
  1482. /*********************************************************************/
  1483. /*                           GET_SHIFT_SYMBOL:                       */
  1484. /*********************************************************************/
  1485. /* This procedure takes as parameter a nonterminal, LHS_SYMBOL, and  */
  1486. /* determines whether or not there is a terminal symbol t such that  */
  1487. /* LHS_SYMBOL can rightmost produce a string tX.  If so, t is        */
  1488. /* returned, otherwise EMPTY is returned.                            */
  1489. /*********************************************************************/
  1490. static get_shift_symbol(int lhs_symbol)
  1491. {
  1492.     int item_no,
  1493.         rule_no,
  1494.         symbol;
  1495.  
  1496.     BOOLEAN end_node;
  1497.  
  1498.     struct node *p;
  1499.  
  1500.     if (! symbol_seen[lhs_symbol])
  1501.     {
  1502.         symbol_seen[lhs_symbol] = TRUE;
  1503.  
  1504.         for (end_node = ((p = clitems[lhs_symbol]) == NULL);
  1505.              ! end_node; end_node = (p == clitems[lhs_symbol]))
  1506.         {
  1507.             p = p -> next;
  1508.             item_no = p -> value;
  1509.             rule_no = item_table[item_no].rule_number;
  1510.             if (RHS_SIZE(rule_no) > 0)
  1511.             {
  1512.                 symbol = rhs_sym[rules[rule_no].rhs];
  1513.                 if (symbol IS_A_TERMINAL)
  1514.                     return(symbol);
  1515.                 else
  1516.                 {
  1517.                     symbol = get_shift_symbol(symbol);
  1518.                     if (symbol != empty)
  1519.                         return(symbol);
  1520.                 }
  1521.             }
  1522.         }
  1523.     }
  1524.  
  1525.     return(empty);
  1526. }
  1527.