home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / jikepg12.zip / jikespg / src / mkfirst.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-11-04  |  65.8 KB  |  1,829 lines
  1. /* $Id: mkfirst.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. #define LEN (PRINT_LINE_SIZE - 4)
  17. #define NEXT_RULE_SIZE (num_rules + 1)
  18. #define LAST_RHS_INDEX(rule_no) rules[rule_no + 1].rhs - 1
  19.  
  20. #define INIT_FIRST(nt) \
  21.         { \
  22.             register int k; \
  23.             for (k = 0; k < term_set_size; k++)\
  24.                  first[nt * term_set_size + k] = 0;\
  25.         }
  26.  
  27. static BOOLEAN is_terminal_rhs(short *rhs_start,
  28.                                BOOLEAN *produces_terminals, int rule_no);
  29. static BOOLEAN is_nullable_rhs(short *rhs_start, int rule_no);
  30. static void compute_first(int nt);
  31. static void print_unreachables(void);
  32. static void print_xref(void);
  33. static void print_nt_first(void);
  34. static void print_follow_map(void);
  35. static short first_map(int root, int tail);
  36. static void s_first(int root, int tail, int set);
  37. static void compute_follow(int nt);
  38. static void quick_sym(short array[], int l, int h);
  39. static void check_non_terminals(void);
  40. static void no_rules_produced(void);
  41. static void nullables_computation(void);
  42. static void compute_closure(int lhs_symbol);
  43. static void compute_produces(int symbol);
  44.  
  45. static struct f_element_type
  46. {
  47.     short suffix_root,
  48.           suffix_tail,
  49.           link;
  50. } *first_element;
  51.  
  52. static struct node **direct_produces;
  53. static SET_PTR produces;
  54.  
  55. /****************************************************************************/
  56. /* TOP, STACK, and INDEX_OF are used for the linear graph algorithm in      */
  57. /* constructing the FIRST, FOLLOW and CLOSURE maps.                         */
  58. /*                                                                          */
  59. /* LHS_RULE and NEXT_RULE are used in constructing a map from non-terminals */
  60. /* to the set of rules produced by the non-terminals.                       */
  61. /*                                                                          */
  62. /* FIRSTis an array used as a hash table to construct                       */
  63. /* the mapping from sequence of symbols to their FIRST terminal             */
  64. /* set.  A sequence is hashed into a location depending on the              */
  65. /* first symbol in that sequence.                                           */
  66. /*                                                                          */
  67. /* FIRST_ITEM_OF is a map from each rule into the first item                */
  68. /* that it generates.                                                       */
  69. /*                                                                          */
  70. /* The following pointers are used to construct a mapping from each symbol  */
  71. /* in the grammar into the set of items denoted by that symbol. I.e.,       */
  72. /*                                                                          */
  73. /*     f(t) := { [A -> x .t y] | A -> x t y is a rule in the grammar }      */
  74. /*                                                                          */
  75. /* Since these sets are simply partitions of the set of items, they are kept*/
  76. /* all in a sequential list in the array NEXT_ITEM.  The roots of the lists */
  77. /* are placed in the arrats T_ITEMS and NT_ITEMS.                           */
  78. /****************************************************************************/
  79. static short *stack,
  80.              *index_of,
  81.  
  82.              *lhs_rule,
  83.              *next_rule,
  84.  
  85.              *first_table,
  86.              *first_item_of,
  87.  
  88.              *next_item,
  89.              *nt_items,
  90.              *nt_list;
  91.  
  92. static int top;
  93.  
  94. /*****************************************************************************/
  95. /*                               MKFIRST:                                    */
  96. /*****************************************************************************/
  97. /*    MKFIRST constructs the FIRST and FOLLOW maps, the CLOSURE map,         */
  98. /* ADEQUATE_ITEM and ITEM_TABLE maps and all other basic maps.               */
  99. /*****************************************************************************/
  100. void mkfirst(void)
  101. {
  102.     int symbol,
  103.         nt,
  104.         item_no,
  105.         first_of_empty,
  106.         rule_no,
  107.         i;
  108.  
  109.     BOOLEAN end_node;
  110.  
  111.     term_set_size = num_terminals / SIZEOF_BC
  112.                   + (num_terminals % SIZEOF_BC ? 1 : 0);
  113.     non_term_set_size = num_non_terminals / SIZEOF_BC
  114.                       + (num_non_terminals % SIZEOF_BC ? 1 : 0);
  115.  
  116.     /* allocate various arrays */
  117.  
  118.     lhs_rule = Allocate_short_array(num_non_terminals);
  119.     lhs_rule -= (num_terminals + 1);
  120.  
  121.     next_rule = Allocate_short_array(NEXT_RULE_SIZE);
  122.     first_item_of = Allocate_short_array(NEXT_RULE_SIZE);
  123.     stack = Allocate_short_array(num_non_terminals + 1);
  124.  
  125.     index_of = Allocate_short_array(num_non_terminals);
  126.     index_of -= (num_terminals + 1);
  127.  
  128.     /*********************************************************************/
  129.     /* NT_FIRST is used to construct a mapping from non-terminals to the */
  130.     /* set of terminals taht may appear first in a string derived from   */
  131.     /* the non-terminal.                                                 */
  132.     /*********************************************************************/
  133.     nt_first = (SET_PTR)
  134.                calloc(num_non_terminals,
  135.                       term_set_size * sizeof(BOOLEAN_CELL));
  136.     if (nt_first == NULL)
  137.         nospace(__FILE__, __LINE__);
  138.  
  139.     nt_first -= ((num_terminals + 1) * term_set_size);
  140.  
  141.     next_item = Allocate_short_array(num_items + 1);
  142.  
  143.     nt_items = Allocate_short_array(num_non_terminals);
  144.     nt_items -= (num_terminals + 1);
  145.  
  146.     nt_list = Allocate_short_array(num_non_terminals);
  147.     nt_list -= (num_terminals + 1);
  148.  
  149.     first_element = (struct f_element_type *)
  150.                     calloc(num_items + 1, sizeof(struct f_element_type));
  151.     if (first_element == NULL)
  152.         nospace(__FILE__, __LINE__);
  153.  
  154.     item_table = (struct itemtab *)
  155.                  calloc(num_items + 1, sizeof(struct itemtab));
  156.     if (item_table == NULL)
  157.         nospace(__FILE__, __LINE__);
  158.  
  159.     for ALL_NON_TERMINALS(i) /* Initialize LHS_RULE to NIL */
  160.         lhs_rule[i] = NIL;
  161.  
  162.     /**************************************************************/
  163.     /* In this loop, we construct the LHS_RULE map which maps     */
  164.     /* each non-terminal symbol into the set of rules it produces */
  165.     /**************************************************************/
  166.     for ALL_RULES(rule_no)
  167.     {
  168.         symbol = rules[rule_no].lhs;
  169.         if (lhs_rule[symbol] == NIL)
  170.             next_rule[rule_no] = rule_no;
  171.         else
  172.         {
  173.             next_rule[rule_no] = next_rule[lhs_rule[symbol]];
  174.             next_rule[lhs_rule[symbol]]  = rule_no;
  175.         }
  176.         lhs_rule[symbol] = rule_no;
  177.     }
  178.  
  179.     /*************************************************************/
  180.     /* Check if there are any non-terminals that do not produce  */
  181.     /* any rules.                                                */
  182.     /*************************************************************/
  183.  
  184.     no_rules_produced();
  185.  
  186.     /*************************************************************/
  187.     /* Construct the CLOSURE map of non-terminals.               */
  188.     /*************************************************************/
  189.     closure = (struct node **)
  190.               calloc(num_non_terminals, sizeof(struct node *));
  191.     if (closure == NULL)
  192.         nospace(__FILE__, __LINE__);
  193.     closure -= (num_terminals + 1);
  194.  
  195.     for ALL_NON_TERMINALS(i)
  196.         index_of[i] = OMEGA;
  197.  
  198.     top = 0;
  199.     for ALL_NON_TERMINALS(nt)
  200.     {
  201.         if (index_of[nt] == OMEGA)
  202.             compute_closure(nt);
  203.     }
  204.  
  205.     /*************************************************************/
  206.     /* Construct the NULL_NT map for non-terminals.              */
  207.     /* A non-terminal B is said to be nullable if either:        */
  208.     /*    B -> %empty  or  B -> B1 B2 B3 ... Bk  where Bi is     */
  209.     /*                         nullable for 1 <= i <= k          */
  210.     /*************************************************************/
  211.     null_nt = Allocate_boolean_array(num_non_terminals);
  212.     null_nt -= (num_terminals + 1);
  213.  
  214.     nullables_computation();
  215.  
  216.     /*************************************************************/
  217.     /* Construct the FIRST map for non-terminals and also a list */
  218.     /* of non-terminals whose first set is empty.                */
  219.     /*************************************************************/
  220.     for ALL_NON_TERMINALS(i) /* Initialize INDEX_OF to OMEGA */
  221.         index_of[i] = OMEGA;
  222.     top = 0;
  223.     for ALL_NON_TERMINALS(nt)
  224.     {
  225.         if (index_of[nt] == OMEGA)
  226.             compute_first(nt);
  227.     }
  228.  
  229.     /*************************************************************/
  230.     /*  Since every input source will be followed by the EOFT    */
  231.     /*  symbol, FIRST[accept_image] cannot contain empty but     */
  232.     /*  instead must contain the EOFT symbol.                    */
  233.     /*************************************************************/
  234.     if (null_nt[accept_image])
  235.     {
  236.         null_nt[accept_image] = FALSE;
  237.         RESET_BIT_IN(nt_first, accept_image, empty);
  238.         SET_BIT_IN(nt_first, accept_image, eoft_image);
  239.     }
  240.  
  241.     /***************************************************************/
  242.     /* Check whether there are any non-terminals that do not       */
  243.     /* generate any terminal strings. If so, signal error and stop.*/
  244.     /***************************************************************/
  245.  
  246.     check_non_terminals();
  247.  
  248.     /***************************************************************/
  249.     /* Construct the ITEM_TABLE, FIRST_ITEM_OF, and NT_ITEMS maps. */
  250.     /***************************************************************/
  251.  
  252.     first_table = Allocate_short_array(num_symbols + 1);
  253.  
  254.     for ALL_SYMBOLS(i) /* Initialize FIRST_TABLE to NIL */
  255.         first_table[i] = NIL;
  256.  
  257.     top = 1;
  258.     first_of_empty = top;
  259.     first_element[first_of_empty].suffix_root = 1;
  260.     first_element[first_of_empty].suffix_tail = 0;
  261.  
  262.     for ALL_NON_TERMINALS(i) /* Initialize NT_ITEMS to NIL */
  263.         nt_items[i] = NIL;
  264.  
  265.     item_no = 0;
  266.     item_table[item_no].rule_number = 0;
  267.     item_table[item_no].symbol = empty;
  268.     item_table[item_no].dot = 0;
  269.     item_table[item_no].suffix_index = NIL;
  270.  
  271.     for ALL_RULES(rule_no)
  272.     {
  273.         int j,
  274.             k;
  275.  
  276.         first_item_of[rule_no] = item_no + 1;
  277.         j = 0;
  278.         k = LAST_RHS_INDEX(rule_no);
  279.         for ENTIRE_RHS(i, rule_no)
  280.         {
  281.             item_no++;
  282.             symbol = rhs_sym[i];
  283.             item_table[item_no].rule_number = rule_no;
  284.             item_table[item_no].symbol = symbol;
  285.             item_table[item_no].dot = j;
  286.  
  287.             if (lalr_level > 1 ||
  288.                 symbol IS_A_NON_TERMINAL ||
  289.                 symbol == error_image)
  290.             {
  291.                 if (i == k)
  292.                     item_table[item_no].suffix_index = first_of_empty;
  293.                 else
  294.                     item_table[item_no].suffix_index = first_map(i + 1, k);
  295.             }
  296.             else
  297.                 item_table[item_no].suffix_index = NIL;
  298.  
  299.             if (symbol IS_A_NON_TERMINAL)
  300.             {
  301.                 next_item[item_no] = nt_items[symbol];
  302.                 nt_items[symbol] = item_no;
  303.             }
  304.             j++;
  305.         }
  306.  
  307.         item_table[++item_no].rule_number = rule_no;
  308.         item_table[item_no].symbol = empty;
  309.         item_table[item_no].dot = j;
  310.         item_table[item_no].suffix_index = NIL;
  311.     }
  312.  
  313.  
  314.     /***************************************************************/
  315.     /* We now compute the first set for all suffixes that were     */
  316.     /* inserted in the FIRST_TABLE map. There are TOP such suffixes*/
  317.     /* Extra space is also allocated to compute the first set for  */
  318.     /* suffixes whose left-hand side is the ACCEPT non-terminal.   */
  319.     /* The first set for these suffixes are the sets needed to     */
  320.     /* construct the FOLLOW map and compute look-ahead sets.  They */
  321.     /* are placed in the FIRST table in the range 1..NUM_FIRST_SETS*/
  322.     /* The first element in the FIRST table contains the first sets*/
  323.     /* for the empty sequence.                                     */
  324.     /***************************************************************/
  325.     num_first_sets = top;
  326.  
  327.     for (end_node = ((rule_no = lhs_rule[accept_image]) == NIL);
  328.          ! end_node;
  329.          end_node = (rule_no == lhs_rule[accept_image]))
  330.     {
  331.         rule_no = next_rule[rule_no];
  332.         num_first_sets++;
  333.     }
  334.  
  335.     first = (SET_PTR)
  336.             calloc(num_first_sets + 1, term_set_size * sizeof(BOOLEAN_CELL));
  337.     if (first == NULL)
  338.         nospace(__FILE__, __LINE__);
  339.     for (i = 1; i <= top; i++)
  340.     {
  341.         s_first(first_element[i].suffix_root,
  342.                 first_element[i].suffix_tail, i);
  343.     }
  344.  
  345.     rule_no = lhs_rule[accept_image];
  346.     for (i = top + 1; i <= num_first_sets; i++)
  347.     {
  348.         rule_no = next_rule[rule_no];
  349.         item_no = first_item_of[rule_no];
  350.         item_table[item_no].suffix_index = i;
  351.         INIT_FIRST(i);
  352.         SET_BIT_IN(first, i, eoft_image);
  353.     }
  354.  
  355.     /***************************************************************/
  356.     /* If the READ/REDUCE option is on, we precalculate the kernel */
  357.     /* of the final states which simply consists of the last item  */
  358.     /* in  the corresponding rule.  Rules with the ACCEPT          */
  359.     /* non-terminal as their left-hand side are not considered so  */
  360.     /* as to let the Accpet action remain as a Reduce action       */
  361.     /* instead of a Goto/Reduce action.                            */
  362.     /***************************************************************/
  363.     adequate_item = (struct node **)
  364.                     calloc(num_rules + 1, sizeof(struct node *));
  365.     if (adequate_item == NULL)
  366.         nospace(__FILE__, __LINE__);
  367.  
  368.     if (read_reduce_bit)
  369.     {
  370.         for ALL_RULES(rule_no)
  371.         {
  372.             int j;
  373.  
  374.             j = RHS_SIZE(rule_no);
  375.             if (rules[rule_no].lhs != accept_image && j > 0)
  376.             {
  377.                 struct node *p;
  378.  
  379.                 item_no = first_item_of[rule_no] + j;
  380.                 p = Allocate_node();
  381.                 p -> value = item_no;
  382.                 p -> next = NULL;
  383.                 adequate_item[rule_no] = p;
  384.             }
  385.             else
  386.                 adequate_item[rule_no] = NULL;
  387.         }
  388.     }
  389.  
  390.  
  391.     /***************************************************************/
  392.     /* Construct the CLITEMS map. Each element of CLITEMS points   */
  393.     /* to a circular linked list of items.                         */
  394.     /***************************************************************/
  395.     clitems = (struct node **)
  396.               calloc(num_non_terminals, sizeof(struct node *));
  397.     if (clitems == NULL)
  398.         nospace(__FILE__, __LINE__);
  399.     clitems -= (num_terminals + 1);
  400.  
  401.     for ALL_NON_TERMINALS(nt)
  402.     {
  403.         clitems[nt] = NULL;
  404.  
  405.         for (end_node = ((rule_no = lhs_rule[nt]) == NIL);
  406.              ! end_node;
  407.              end_node = (rule_no == lhs_rule[nt]))
  408.         {
  409.             struct node *p;
  410.  
  411.             rule_no = next_rule[rule_no];
  412.             p = Allocate_node();
  413.             p -> value = first_item_of[rule_no];
  414.             if (clitems[nt] == NULL)
  415.                 p -> next = p;
  416.             else
  417.             {
  418.                 p -> next = clitems[nt] -> next;
  419.                 clitems[nt] -> next = p;
  420.             }
  421.             clitems[nt] = p;
  422.         }
  423.     }
  424.  
  425.     /***************************************************************/
  426.     /* If LALR_LEVEL > 1, we need to calculate RMPSELF, a set that */
  427.     /* identifies the nonterminals that can right-most produce     */
  428.     /* themselves. In order to compute RMPSELF, the map PRODUCES   */
  429.     /* must be constructed which identifies for each nonterminal   */
  430.     /* the set of nonterminals that it can right-most produce.     */
  431.     /***************************************************************/
  432.     if (lalr_level > 1)
  433.     {
  434.         produces = (SET_PTR)
  435.                    calloc(num_non_terminals,
  436.                           non_term_set_size * sizeof(BOOLEAN_CELL));
  437.         if (produces == NULL)
  438.             nospace(__FILE__, __LINE__);
  439.         produces -= ((num_terminals + 1) * non_term_set_size);
  440.  
  441.         direct_produces = (struct node **)
  442.                           calloc(num_non_terminals, sizeof(struct node *));
  443.         if (direct_produces == NULL)
  444.             nospace(__FILE__, __LINE__);
  445.         direct_produces -= (num_terminals + 1);
  446.  
  447.         for ALL_NON_TERMINALS(nt)
  448.         {
  449.             struct node *p,
  450.                         *q;
  451.  
  452.             for (end_node = ((p = clitems[nt]) == NULL);
  453.                  ! end_node; end_node = (p == clitems[nt]))
  454.             {
  455.                 p = p -> next;
  456.                 item_no = p -> value;
  457.                 symbol = item_table[item_no].symbol;
  458.                 if (symbol IS_A_NON_TERMINAL)
  459.                 {
  460.                     i = item_table[item_no].suffix_index;
  461.                     if (IS_IN_SET(first, i, empty) &&
  462.                         (! IS_IN_NTSET(produces, nt,
  463.                                        symbol - num_terminals)))
  464.                     {
  465.                         NTSET_BIT_IN(produces, nt,
  466.                                      symbol - num_terminals);
  467.                         q = Allocate_node();
  468.                         q -> value = symbol;
  469.                         q -> next = direct_produces[nt];
  470.                         direct_produces[nt] = q;
  471.                     }
  472.                 }
  473.             }
  474.         }
  475.  
  476.         /************************************************************/
  477.         /* Complete the construction of the RIGHT_MOST_PRODUCES map */
  478.         /* for non-terminals using the digraph algorithm.           */
  479.         /************************************************************/
  480.         for ALL_NON_TERMINALS(nt)
  481.             index_of[nt] = OMEGA;
  482.  
  483.         top = 0;
  484.         for ALL_NON_TERMINALS(nt)
  485.         {
  486.             if (index_of[nt] == OMEGA)
  487.                 compute_produces(nt);
  488.         }
  489.  
  490.         init_rmpself(produces);
  491.  
  492.         produces += ((num_terminals + 1) * non_term_set_size);
  493.         ffree(produces);
  494.         direct_produces += (num_terminals + 1);
  495.         ffree(direct_produces);
  496.     }
  497.  
  498.     /***************************************************************/
  499.     /* Construct the FOLLOW map if                                 */
  500.     /*   1) an SLR table is requested                              */
  501.     /*   2) if we have to print the FOLLOW map                     */
  502.     /*   3) Error-maps are requested                               */
  503.     /*   4) There are more than one starting symbol.               */
  504.     /***************************************************************/
  505.     if (slr_bit || follow_bit || error_maps_bit ||
  506.         next_rule[lhs_rule[accept_image]] != lhs_rule[accept_image])
  507.     {
  508.         follow = (SET_PTR)
  509.                  calloc(num_non_terminals,
  510.                         term_set_size * sizeof(BOOLEAN_CELL));
  511.         if (follow == NULL)
  512.             nospace(__FILE__, __LINE__);
  513.         follow -= ((num_terminals + 1) * term_set_size);
  514.  
  515.         SET_BIT_IN(follow, accept_image, eoft_image);
  516.  
  517.         for ALL_NON_TERMINALS(i) /* Initialize INDEX_OF to OMEGA */
  518.             index_of[i] = OMEGA;
  519.  
  520.         index_of[accept_image] = INFINITY;  /* mark computed */
  521.         top = 0;
  522.  
  523.         for ALL_NON_TERMINALS(nt)
  524.         {
  525.             if (index_of[nt] == OMEGA) /* not yet computed ? */
  526.                 compute_follow(nt);
  527.         }
  528.  
  529.     /***************************************************************/
  530.     /*  Initialize FIRST for suffixes that can follow each starting*/
  531.     /* non-terminal ( except the main symbol) with the FOLLOW set */
  532.     /* of the non-terminal in question.                            */
  533.     /***************************************************************/
  534.         rule_no = lhs_rule[accept_image];
  535.         if (next_rule[rule_no] != rule_no)
  536.         {
  537.             rule_no = next_rule[rule_no];   /* first rule */
  538.             top = item_table[first_item_of[rule_no]].suffix_index;
  539.             for (i = top + 1; i <= num_first_sets; i++)
  540.             {
  541.                 rule_no = next_rule[rule_no];
  542.                 item_no = first_item_of[rule_no];
  543.                 symbol = item_table[item_no].symbol;
  544.                 if (symbol IS_A_NON_TERMINAL)
  545.                 {
  546.                    ASSIGN_SET(first, i, follow, symbol);
  547.                 }
  548.             }
  549.         }
  550.     }
  551.  
  552.     /***************************************************************/
  553.     /* If WARNINGS option is turned on, the unreachable symbols in */
  554.     /* the grammar are printed.                                    */
  555.     /***************************************************************/
  556.     if (warnings_bit)
  557.         print_unreachables();
  558.  
  559.     /***************************************************************/
  560.     /* If a Cross_Reference listing is requested, it is generated  */
  561.     /* here.                                                       */
  562.     /***************************************************************/
  563.     if (xref_bit)
  564.         print_xref();
  565.  
  566.     /***************************************************************/
  567.     /* If a listing of the FIRST map is requested, it is generated */
  568.     /* here.                                                       */
  569.     /***************************************************************/
  570.     if (first_bit)
  571.         print_nt_first();
  572.  
  573.     /****************************************************************/
  574.     /* If a listing of the FOLLOW map is requested, it is generated */
  575.     /* here.                                                        */
  576.     /***************************************************************/
  577.     if (follow_bit)
  578.         print_follow_map();
  579.  
  580.     /***************************************************************/
  581.     /* Free allocated arrays.                                      */
  582.     /***************************************************************/
  583.     nt_first += ((num_terminals + 1) * term_set_size);
  584.     ffree(nt_first);
  585.     nt_list += (num_terminals + 1);
  586.     ffree(nt_list);
  587.     ffree(first_table);
  588.     ffree(first_element);
  589.     nt_items += (num_terminals + 1);
  590.     ffree(nt_items);
  591.     ffree(next_item);
  592.     ffree(stack);
  593.     index_of += (num_terminals + 1);
  594.     ffree(index_of);
  595.     lhs_rule += (num_terminals + 1);
  596.     ffree(lhs_rule);
  597.     ffree(next_rule);
  598.     ffree(first_item_of);
  599.  
  600.     return;
  601. }
  602.  
  603.  
  604. /*****************************************************************************/
  605. /*                           NO_RULES_PRODUCED:                              */
  606. /*****************************************************************************/
  607. static void no_rules_produced(void)
  608. {
  609.     char line[PRINT_LINE_SIZE + 1],
  610.          tok[SYMBOL_SIZE + 1];
  611.  
  612.     int nt_root,
  613.         nt_last,
  614.         symbol;
  615.  
  616.     /*************************************************************/
  617.     /* Build a list of all non-terminals that do not produce any */
  618.     /* rules.                                                    */
  619.     /*************************************************************/
  620.     nt_root = NIL;
  621.     for ALL_NON_TERMINALS(symbol)
  622.     {
  623.         if (lhs_rule[symbol] == NIL)
  624.         {
  625.             if (nt_root == NIL)
  626.                 nt_root = symbol;
  627.             else
  628.                 nt_list[nt_last] = symbol;
  629.             nt_last = symbol;
  630.         }
  631.     }
  632.  
  633.     /*************************************************************/
  634.     /* If the list of non-terminals that do not produce any rules*/
  635.     /* is not empty, signal error and stop.                      */
  636.     /*************************************************************/
  637.  
  638.     if (nt_root != NIL)
  639.     {
  640.         PR_HEADING;
  641.         nt_list[nt_last] = NIL;
  642.         if (nt_list[nt_root] == NIL)
  643.         {
  644.             PRNTERR("The following Non-terminal does not produce any rules: ");
  645.         }
  646.         else
  647.         {
  648.             PRNTERR("The following Non-terminals do not produce any rules: ");
  649.         }
  650.         strcpy(line, "        ");
  651.  
  652.         for (symbol = nt_root; symbol != NIL; symbol = nt_list[symbol])
  653.         {
  654.             restore_symbol(tok, RETRIEVE_STRING(symbol));
  655.             if (strlen(line) + strlen(tok) > PRINT_LINE_SIZE)
  656.             {
  657.                 PRNT(line);
  658.                 print_large_token(line, tok, "    ", LEN);
  659.             }
  660.             else
  661.                 strcat(line, tok);
  662.             strcat(line,BLANK);
  663.         }
  664.         PRNT(line);
  665.         exit(12);
  666.     }
  667. }
  668.  
  669.  
  670. /*****************************************************************************/
  671. /*                            COMPUTE_CLOSURE:                               */
  672. /*****************************************************************************/
  673. /*  This function computes the closure of a non-terminal LHS_SYMBOL passed   */
  674. /* to it as an argument using the digraph algorithm.                         */
  675. /*  The closure of a non-terminal A is the set of all non-terminals Bi that  */
  676. /* can directly or indirectly start a string generated by A.                 */
  677. /* I.e., A *::= Bi X where X is an arbitrary string.                         */
  678. /*****************************************************************************/
  679. static void compute_closure(int lhs_symbol)
  680. {
  681.     int indx;
  682.     short *nont_list;
  683.  
  684.     int symbol,
  685.         rule_no,
  686.         nt_root,
  687.         i;
  688.  
  689.     struct node *p,
  690.                 *q;
  691.  
  692.     BOOLEAN end_node;
  693.  
  694.     nont_list = Allocate_short_array(num_non_terminals);
  695.     nont_list -= (num_terminals + 1); /* Temporary direct        */
  696.                                       /* access set for closure. */
  697.     stack[++top] = lhs_symbol;
  698.     indx = top;
  699.     index_of[lhs_symbol] = indx;
  700.  
  701.     for ALL_NON_TERMINALS(i)
  702.         nont_list[i] = OMEGA;
  703.  
  704.     nont_list[lhs_symbol] = NIL;
  705.     nt_root = lhs_symbol;
  706.  
  707.     closure[lhs_symbol] = NULL; /* Permanent closure set. Linked list */
  708.  
  709.     for (end_node = ((rule_no = lhs_rule[lhs_symbol]) == NIL);
  710.          ! end_node;          /* Iterate over all rules of LHS_SYMBOL */
  711.          end_node = (rule_no == lhs_rule[lhs_symbol]))
  712.     {
  713.         rule_no = next_rule[rule_no];
  714.         symbol = (RHS_SIZE(rule_no) == 0 ? empty
  715.                                          : rhs_sym[rules[rule_no].rhs]);
  716.  
  717.         if (symbol IS_A_NON_TERMINAL)
  718.         {
  719.             if (nont_list[symbol] == OMEGA)
  720.             {
  721.                 if (index_of[symbol] == OMEGA) /* if first time seen */
  722.                     compute_closure(symbol);
  723.  
  724.                 index_of[lhs_symbol] = MIN(index_of[lhs_symbol],
  725.                                            index_of[symbol]);
  726.                 nont_list[symbol] = nt_root;
  727.                 nt_root = symbol;
  728.  
  729.                 /* add closure[symbol] to closure of LHS_SYMBOL.  */
  730.  
  731.                 for (end_node = ((q = closure[symbol]) == NULL);
  732.                      ! end_node;
  733.                      end_node = (q == closure[symbol]))
  734.                 {
  735.                     q = q -> next;
  736.                     if (nont_list[q -> value] == OMEGA)
  737.                     {
  738.                         nont_list[q -> value] = nt_root;
  739.                         nt_root = q -> value;
  740.                     }
  741.                 }
  742.             }
  743.         }
  744.     }
  745.  
  746.     for (; nt_root != lhs_symbol; nt_root = nont_list[nt_root])
  747.     {
  748.         p = Allocate_node();
  749.         p -> value = nt_root;
  750.         if (closure[lhs_symbol] == NULL)
  751.             p -> next = p;
  752.         else
  753.         {
  754.             p -> next = closure[lhs_symbol] -> next;
  755.             closure[lhs_symbol] -> next = p;
  756.         }
  757.         closure[lhs_symbol] = p;
  758.     }
  759.  
  760.     if (index_of[lhs_symbol] == indx)
  761.     {
  762.         for (symbol = stack[top]; symbol != lhs_symbol; symbol = stack[--top])
  763.         {
  764.             q = closure[symbol];
  765.             if (q != NULL)
  766.             {
  767.                 p = q -> next;
  768.                 free_nodes(p, q); /* free nodes used by CLOSURE[SYMBOL] */
  769.                 closure[symbol] = NULL;
  770.             }
  771.  
  772.             p = Allocate_node();
  773.             p -> value = lhs_symbol;
  774.             p -> next = p;
  775.             closure[symbol] = p;
  776.  
  777.             for (end_node = ((q = closure[lhs_symbol]) == NULL);
  778.                  ! end_node;
  779.                  end_node = (q == closure[lhs_symbol]))
  780.             {
  781.                 q = q -> next;
  782.                 if (q -> value != symbol)
  783.                 {
  784.                     p = Allocate_node();
  785.                     p -> value = q -> value;
  786.                     p -> next = closure[symbol] -> next;
  787.                     closure[symbol] -> next = p;
  788.                     closure[symbol] = p;
  789.                 }
  790.             }
  791.  
  792.             index_of[symbol] = INFINITY;
  793.         }
  794.  
  795.         index_of[lhs_symbol] = INFINITY;
  796.         top--;
  797.     }
  798.  
  799.     nont_list += (num_terminals + 1);
  800.     ffree(nont_list);
  801.  
  802.     return;
  803. }
  804.  
  805.  
  806. /*****************************************************************************/
  807. /*                           NULLABLES_COMPUTATION:                          */
  808. /*****************************************************************************/
  809. /*   This procedure computes the set of non-terminal symbols that can        */
  810. /* generate the empty string.  Such non-terminals are said to be nullable.   */
  811. /*                                                                           */
  812. /* A non-terminal "A" can generate empty if the grammar in question contains */
  813. /* a rule:                                                                   */
  814. /*          A ::= B1 B2 ... Bn     n >= 0,  1 <= i <= n                      */
  815. /* and Bi, for all i, is a nullable non-terminal.                            */
  816. /*****************************************************************************/
  817. static void nullables_computation(void)
  818. {
  819.     short *rhs_start;
  820.  
  821.     int rule_no,
  822.         nt;
  823.  
  824.     BOOLEAN changed = TRUE,
  825.             end_node;
  826.  
  827.     rhs_start = Allocate_short_array(NEXT_RULE_SIZE);
  828.  
  829.     /******************************************************************/
  830.     /* First, mark all non-terminals as non-nullable.  Then initialize*/
  831.     /* RHS_START. RHS_START is a mapping from each rule in the grammar*/
  832.     /* into the next symbol in its right-hand side that has not yet   */
  833.     /* proven to be nullable.                                         */
  834.     /******************************************************************/
  835.     for ALL_NON_TERMINALS(nt)
  836.         null_nt[nt] = FALSE;
  837.  
  838.     for ALL_RULES(rule_no)
  839.         rhs_start[rule_no] = rules[rule_no].rhs;
  840.  
  841.     /******************************************************************/
  842.     /* We now iterate over the rules and try to advance the RHS_START */
  843.     /* pointer thru each right-hand side as far as we can.  If one or */
  844.     /* more non-terminals are found to be nullable, they are marked   */
  845.     /* as such and the process is repeated.                           */
  846.     /*                                                                */
  847.     /* If we go through all the rules and no new non-terminal is found*/
  848.     /* to be nullable then we stop and return.                        */
  849.     /*                                                                */
  850.     /* Note that for each iteration, only rules associated with       */
  851.     /* non-terminals that are non-nullable are considered.  Further,  */
  852.     /* as soon as a non-terminal is found to be nullable, the         */
  853.     /* remaining rules associated with it are not considered.  I.e.,  */
  854.     /* we quit the inner loop.                                        */
  855.     /******************************************************************/
  856.     while(changed)
  857.     {
  858.         changed = FALSE;
  859.  
  860.         for ALL_NON_TERMINALS(nt)
  861.         {
  862.             for (end_node = ((rule_no = lhs_rule[nt]) == NIL);
  863.                  ! null_nt[nt] && ! end_node;
  864.                  end_node = (rule_no == lhs_rule[nt]))
  865.             {
  866.                 rule_no = next_rule[rule_no];
  867.                 if (is_nullable_rhs(rhs_start,rule_no))
  868.                 {
  869.                     changed = TRUE;
  870.                     null_nt[nt] = TRUE;
  871.                 }
  872.             }
  873.         }
  874.     }
  875.  
  876.     ffree(rhs_start);
  877.  
  878.     return;
  879. }
  880.  
  881.  
  882. /*****************************************************************************/
  883. /*                            IS_NULLABLE_RHS:                               */
  884. /*****************************************************************************/
  885. /*   This procedure tries to advance the RHS_START pointer.  If the current  */
  886. /* symbol identified by the RHS_START element is a terminal it returns FALSE */
  887. /* to indicate that it cannot go any further.  If it encounters a  non-null- */
  888. /* lable non-terminal, it also returns FALSE. Otherwise, the whole right-hand*/
  889. /* side is consumed, and it returns the value TRUE.                          */
  890. /*****************************************************************************/
  891. static BOOLEAN is_nullable_rhs(short *rhs_start, int rule_no)
  892. {
  893.     int symbol;
  894.  
  895.     for(rhs_start[rule_no] = rhs_start[rule_no];
  896.         rhs_start[rule_no] <= rules[rule_no + 1].rhs - 1;
  897.         rhs_start[rule_no]++)
  898.     {
  899.         symbol = rhs_sym[rhs_start[rule_no]];
  900.         if (symbol IS_A_TERMINAL)
  901.             return(FALSE);
  902.         else if (! null_nt[symbol]) /* symbol is a non-terminal */
  903.             return(FALSE);
  904.     }
  905.  
  906.     return(TRUE);
  907. }
  908.  
  909.  
  910. /*****************************************************************************/
  911. /*                             COMPUTE_FIRST:                                */
  912. /*****************************************************************************/
  913. /* This subroutine computes FIRST(NT) for some non-terminal NT using the     */
  914. /* digraph algorithm.                                                        */
  915. /* FIRST(NT) is the set of all terminals Ti that may start a string generated*/
  916. /* by NT. That is, NT *::= Ti X where X is an arbitrary string.              */
  917. /*****************************************************************************/
  918. static void compute_first(int nt)
  919. {
  920.     int indx;
  921.  
  922.     BOOLEAN end_node,
  923.             blocked;
  924.  
  925.     int i,
  926.         symbol,
  927.         rule_no;
  928.  
  929.     SET_PTR temp_set;
  930.  
  931.     temp_set = (SET_PTR)
  932.                calloc(1, term_set_size * sizeof(BOOLEAN_CELL));
  933.     if (temp_set == NULL)
  934.         nospace(__FILE__, __LINE__);
  935.  
  936.     stack[++top] = nt;
  937.     indx = top;
  938.     index_of[nt] = indx;
  939.  
  940.     /**************************************************************/
  941.     /* Iterate over all rules generated by non-terminal NT...     */
  942.     /* In this application of the transitive closure algorithm,   */
  943.     /*                                                            */
  944.     /*  G(A) := { t | A ::= t X for a terminal t and a string X } */
  945.     /*                                                            */
  946.     /* The relation R is defined as follows:                      */
  947.     /*                                                            */
  948.     /*    R(A, B) iff A ::= B1 B2 ... Bk B X                      */
  949.     /*                                                            */
  950.     /* where Bi is nullable for 1 <= i <= k                       */
  951.     /**************************************************************/
  952.  
  953.     for (end_node = ((rule_no = lhs_rule[nt]) == NIL);
  954.          ! end_node;    /* Iterate over all rules produced by NT */
  955.          end_node = (rule_no == lhs_rule[nt]))
  956.     {
  957.         rule_no = next_rule[rule_no];
  958.         blocked = FALSE;
  959.  
  960.         for ENTIRE_RHS(i, rule_no)
  961.         {
  962.             symbol = rhs_sym[i];
  963.             if (symbol IS_A_NON_TERMINAL)
  964.             {
  965.                 if (index_of[symbol] == OMEGA)
  966.                     compute_first(symbol);
  967.                 index_of[nt] = MIN( index_of[nt], index_of[symbol]);
  968.  
  969.                 ASSIGN_SET(temp_set, 0, nt_first, symbol);
  970.                 RESET_BIT(temp_set, empty);
  971.                 SET_UNION(nt_first, nt, temp_set, 0);
  972.                 blocked = NOT(null_nt[symbol]);
  973.             }
  974.             else
  975.             {
  976.                 SET_BIT_IN(nt_first, nt, symbol);
  977.                 blocked = TRUE;
  978.             }
  979.  
  980.             if (blocked)
  981.                 break;
  982.         }
  983.  
  984.         if (! blocked)
  985.         {
  986.             SET_BIT_IN(nt_first, nt, empty);
  987.         }
  988.     }
  989.  
  990.     if (index_of[nt] == indx)
  991.     {
  992.         for (symbol = stack[top]; symbol != nt; symbol = stack[--top])
  993.         {
  994.             ASSIGN_SET(nt_first, symbol, nt_first, nt);
  995.             index_of[symbol] = INFINITY;
  996.         }
  997.         index_of[nt] = INFINITY;
  998.         top--;
  999.     }
  1000.     ffree(temp_set);
  1001.     return;
  1002. }
  1003.  
  1004.  
  1005. /*****************************************************************************/
  1006. /*                            CHECK_NON_TERMINALS:                           */
  1007. /*****************************************************************************/
  1008. /* This procedure checks whether or not any non-terminal symbols can fail to */
  1009. /* generate a string of terminals.                                           */
  1010. /*                                                                           */
  1011. /* A non-terminal "A" can generate a terminal string if the grammar in       */
  1012. /* question contains a rule of the form:                                     */
  1013. /*                                                                           */
  1014. /*         A ::= X1 X2 ... Xn           n >= 0,  1 <= i <= n                 */
  1015. /*                                                                           */
  1016. /* and Xi, for all i, is a terminal or a non-terminal that can generate a    */
  1017. /* string of terminals.                                                      */
  1018. /* This routine is structurally identical to COMPUTE_NULLABLES.              */
  1019. /*****************************************************************************/
  1020. static void check_non_terminals(void)
  1021. {
  1022.     char line[PRINT_LINE_SIZE + 1],
  1023.          tok[SYMBOL_SIZE + 1];
  1024.  
  1025.     short *rhs_start;
  1026.  
  1027.     int rule_no,
  1028.         nt_root,
  1029.         nt_last,
  1030.         symbol,
  1031.         nt;
  1032.  
  1033.     BOOLEAN changed = TRUE,
  1034.             end_node,
  1035.             *produces_terminals;
  1036.  
  1037.     rhs_start = Allocate_short_array(NEXT_RULE_SIZE);
  1038.     produces_terminals = Allocate_boolean_array(num_non_terminals);
  1039.     produces_terminals -= (num_terminals + 1);
  1040.  
  1041.     /******************************************************************/
  1042.     /* First, mark all non-terminals as not producing terminals. Then */
  1043.     /* initialize RHS_START. RHS_START is a mapping from each rule in */
  1044.     /* the grammar into the next symbol in its right-hand side that   */
  1045.     /* has not yet proven to be a symbol that generates terminals.    */
  1046.     /******************************************************************/
  1047.     for ALL_NON_TERMINALS(nt)
  1048.         produces_terminals[nt] = FALSE;
  1049.  
  1050.     produces_terminals[accept_image] = TRUE;
  1051.  
  1052.     for ALL_RULES(rule_no)
  1053.         rhs_start[rule_no] = rules[rule_no].rhs;
  1054.  
  1055.     /******************************************************************/
  1056.     /* We now iterate over the rules and try to advance the RHS_START */
  1057.     /* pointer to each right-hand side as far as we can.  If one or   */
  1058.     /* more non-terminals are found to be "all right", they are       */
  1059.     /* marked as such and the process is repeated.                    */
  1060.     /*                                                                */
  1061.     /* If we go through all the rules and no new non-terminal is      */
  1062.     /* found to be "all right" then we stop and return.               */
  1063.     /*                                                                */
  1064.     /* Note that on each iteration, only rules associated with        */
  1065.     /* non-terminals that are not "all right" are considered. Further,*/
  1066.     /* as soon as a non-terminal is found to be "all right", the      */
  1067.     /* remaining rules associated with it are not considered. I.e.,   */
  1068.     /* we quit the inner loop.                                        */
  1069.     /******************************************************************/
  1070.     while(changed)
  1071.     {
  1072.         changed = FALSE;
  1073.  
  1074.         for ALL_NON_TERMINALS(nt)
  1075.         {
  1076.             for (end_node = ((rule_no = lhs_rule[nt]) == NIL);
  1077.                  (! produces_terminals[nt]) && (! end_node);
  1078.                  end_node = (rule_no == lhs_rule[nt]))
  1079.             {
  1080.                 rule_no = next_rule[rule_no];
  1081.                 if (is_terminal_rhs(rhs_start, produces_terminals, rule_no))
  1082.                 {
  1083.                     changed = TRUE;
  1084.                     produces_terminals[nt] = TRUE;
  1085.                 }
  1086.             }
  1087.         }
  1088.     }
  1089.  
  1090.     /*************************************************************/
  1091.     /* Construct a list of all non-terminals that do not generate*/
  1092.     /* terminal strings.                                         */
  1093.     /*************************************************************/
  1094.     nt_root = NIL;
  1095.     for ALL_NON_TERMINALS(nt)
  1096.     {
  1097.         if (! produces_terminals[nt])
  1098.         {
  1099.             if (nt_root == NIL)
  1100.                 nt_root = nt;
  1101.             else
  1102.                 nt_list[nt_last] = nt;
  1103.             nt_last = nt;
  1104.         }
  1105.     }
  1106.  
  1107.     /*************************************************************/
  1108.     /* If there are non-terminal symbols that do not generate    */
  1109.     /* terminal strings, print them out and stop the program.    */
  1110.     /*************************************************************/
  1111.     if (nt_root != NIL)
  1112.     {
  1113.         nt_list[nt_last] = NIL;  /* mark end of list */
  1114.         PR_HEADING;
  1115.         strcpy(line, "*** ERROR: The following Non-terminal");
  1116.         if (nt_list[nt_root] == NIL)
  1117.             strcat(line, " does not generate any terminal strings: ");
  1118.         else
  1119.         {
  1120.             strcat(line, "s do not generate any terminal strings: ");
  1121.             PRNT(line);
  1122.             strcpy(line, "        "); /* 8 spaces */
  1123.         }
  1124.  
  1125.         for (symbol = nt_root; symbol != NIL; symbol = nt_list[symbol])
  1126.         {
  1127.             restore_symbol(tok, RETRIEVE_STRING(symbol));
  1128.             if (strlen(line) + strlen(tok) > PRINT_LINE_SIZE-1)
  1129.             {
  1130.                 PRNT(line);
  1131.                 print_large_token(line, tok, "    ", LEN);
  1132.             }
  1133.             else
  1134.                 strcat(line, tok);
  1135.             strcat(line, BLANK);
  1136.         }
  1137.         PRNT(line);
  1138.         exit(12);
  1139.     }
  1140.     produces_terminals += (num_terminals + 1);
  1141.     ffree(produces_terminals);
  1142.     ffree(rhs_start);
  1143. }
  1144.  
  1145.  
  1146. /*****************************************************************************/
  1147. /*                          IS_TERMINAL_RHS:                                 */
  1148. /*****************************************************************************/
  1149. /*   This procedure tries to advance the RHS_START pointer.  If the current  */
  1150. /* symbol identified by the RHS_START element is a bad non-terminal it       */
  1151. /* returns FALSE.  Otherwise, the whole right-hand side is traversed, and it */
  1152. /* returns the value TRUE.                                                   */
  1153. /*****************************************************************************/
  1154. static BOOLEAN is_terminal_rhs(short *rhs_start,
  1155.                                BOOLEAN *produces_terminals, int rule_no)
  1156. {
  1157.     int symbol;
  1158.  
  1159.     for(rhs_start[rule_no] = rhs_start[rule_no];
  1160.         rhs_start[rule_no] <= rules[rule_no + 1].rhs - 1;
  1161.         rhs_start[rule_no]++)
  1162.     {
  1163.         symbol = rhs_sym[rhs_start[rule_no]];
  1164.         if (symbol IS_A_NON_TERMINAL)
  1165.         {
  1166.             if (! produces_terminals[symbol])
  1167.                 return(FALSE);
  1168.         }
  1169.     }
  1170.  
  1171.     return(TRUE);
  1172. }
  1173.  
  1174.  
  1175. /*****************************************************************************/
  1176. /*                             FIRST_MAP:                                    */
  1177. /*****************************************************************************/
  1178. /*  FIRST_MAP takes as arguments two pointers, ROOT and TAIL, to a sequence  */
  1179. /* of symbols in RHS which it inserts in FIRST_TABLE.  The vector FIRST_TABLE*/
  1180. /* is used as the base for a hashed table where collisions are resolved by   */
  1181. /* links.  Elements added to this hash table are allocated from the vector   */
  1182. /* FIRST_ELEMENT, with the variable TOP always indicating the position of the*/
  1183. /* last element in FIRST_ELEMENT that was allocated.                         */
  1184. /* NOTE: The suffix indentified by ROOT and TAIL is presumed not to be empty.*/
  1185. /*       That is, ROOT <= TAIL !!!                                           */
  1186. /*****************************************************************************/
  1187. static short first_map(int root, int tail)
  1188. {
  1189.     int i,
  1190.         j,
  1191.         k;
  1192.  
  1193.     for (i = first_table[rhs_sym[root]]; i != NIL; i = first_element[i].link)
  1194.     {
  1195.         for (j = root + 1,
  1196.              k = first_element[i].suffix_root + 1;
  1197.              (j <= tail && k <= first_element[i].suffix_tail);
  1198.              j++, k++)
  1199.         {
  1200.             if (rhs_sym[j] != rhs_sym[k])
  1201.                 break;
  1202.         }
  1203.         if (j > tail && k > first_element[i].suffix_tail)
  1204.             return((short) i);
  1205.     }
  1206.     top++;
  1207.     first_element[top].suffix_root = root;
  1208.     first_element[top].suffix_tail = tail;
  1209.     first_element[top].link = first_table[rhs_sym[root]];
  1210.     first_table[rhs_sym[root]] = top;
  1211.  
  1212.     return(top);
  1213. }
  1214.  
  1215.  
  1216. /*****************************************************************************/
  1217. /*                              S_FIRST:                                     */
  1218. /*****************************************************************************/
  1219. /* S_FIRST takes as argument, two pointers: ROOT and TAIL to a sequence of   */
  1220. /* symbols in the vector RHS, and INDEX which is the index of a first set.   */
  1221. /* It computes the set of all terminals that can appear as the first symbol  */
  1222. /* in the sequence and places the result in the FIRST set indexable by INDEX.*/
  1223. /*****************************************************************************/
  1224. static void s_first(int root, int tail, int index)
  1225. {
  1226.     int i,
  1227.         symbol;
  1228.  
  1229.     symbol = (root > tail ? empty : rhs_sym[root]);
  1230.  
  1231.     if (symbol IS_A_TERMINAL)
  1232.     {
  1233.         INIT_FIRST(index);
  1234.         SET_BIT_IN(first, index, symbol); /* add it to set */
  1235.     }
  1236.     else
  1237.     {
  1238.         ASSIGN_SET(first, index, nt_first, symbol);
  1239.     }
  1240.  
  1241.     for (i = root + 1; i <= tail && IS_IN_SET(first, index, empty); i++)
  1242.     {
  1243.         symbol = rhs_sym[i];
  1244.         RESET_BIT_IN(first, index, empty);    /* remove EMPTY */
  1245.         if (symbol IS_A_TERMINAL)
  1246.         {
  1247.             SET_BIT_IN(first, index, symbol);  /* add it to set */
  1248.         }
  1249.         else
  1250.         {
  1251.             SET_UNION(first, index, nt_first, symbol);
  1252.         }
  1253.     }
  1254.  
  1255.     return;
  1256. }
  1257.  
  1258.  
  1259. /******************************************************************/
  1260. /*                     COMPUTE_PRODUCES:                          */
  1261. /******************************************************************/
  1262. /* For a given symbol, complete the computation of                */
  1263. /* PRODUCES[symbol].                                              */
  1264. /******************************************************************/
  1265. static void compute_produces(int symbol)
  1266. {
  1267.     int indx;
  1268.  
  1269.     int new_symbol;
  1270.  
  1271.     struct node *p,
  1272.                 *q;
  1273.  
  1274.     stack[++top] = symbol;
  1275.     indx = top;
  1276.     index_of[symbol] = indx;
  1277.  
  1278.     for (p = direct_produces[symbol]; p != NULL; q = p, p = p -> next)
  1279.     {
  1280.         new_symbol = p -> value;
  1281.         if (index_of[new_symbol] == OMEGA)  /* first time seen? */
  1282.             compute_produces(new_symbol);
  1283.         index_of[symbol] = MIN(index_of[symbol], index_of[new_symbol]);
  1284.         NTSET_UNION(produces, symbol, produces, new_symbol);
  1285.     }
  1286.     if (direct_produces[symbol] != NULL)
  1287.         free_nodes(direct_produces[symbol], q);
  1288.  
  1289.     if (index_of[symbol] == indx)  /*symbol is SCC root */
  1290.     {
  1291.         for (new_symbol = stack[top];
  1292.              new_symbol != symbol; new_symbol = stack[--top])
  1293.         {
  1294.             ASSIGN_NTSET(produces, new_symbol, produces, symbol);
  1295.             index_of[new_symbol] = INFINITY;
  1296.         }
  1297.  
  1298.         index_of[symbol] = INFINITY;
  1299.         top--;
  1300.     }
  1301.  
  1302.     return;
  1303. }
  1304.  
  1305.  
  1306. /*****************************************************************************/
  1307. /*                          COMPUTE_FOLLOW:                                  */
  1308. /*****************************************************************************/
  1309. /* COMPUTE_FOLLOW computes FOLLOW[nt] for some non-terminal NT using the     */
  1310. /* digraph algorithm.  FOLLOW[NT] is the set of all terminals Ti that        */
  1311. /* may immediately follow a string X generated by NT. I.e., if NT *::= X     */
  1312. /* then X Ti is a valid substring of a class of strings that may be          */
  1313. /* recognized by the language.                                               */
  1314. /*****************************************************************************/
  1315. static void compute_follow(int nt)
  1316. {
  1317.     int indx;
  1318.  
  1319.     int rule_no,
  1320.         lhs_symbol,
  1321.         item_no;
  1322.  
  1323.     SET_PTR temp_set;
  1324.  
  1325.     temp_set = (SET_PTR)
  1326.                calloc(1, term_set_size * sizeof(BOOLEAN_CELL));
  1327.     if (temp_set == NULL)
  1328.         nospace(__FILE__, __LINE__);
  1329.  
  1330.     /**************************************************************/
  1331.     /* FOLLOW[NT] was initialized to 0 for all non-terminals.     */
  1332.     /**************************************************************/
  1333.  
  1334.     stack[++top] = nt;
  1335.     indx = top;
  1336.     index_of[nt] = indx;
  1337.  
  1338.     for (item_no = nt_items[nt]; item_no != NIL; item_no = next_item[item_no])
  1339.     { /* iterate over all items of NT */
  1340.         ASSIGN_SET(temp_set, 0, first, item_table[item_no].suffix_index);
  1341.         if (IS_ELEMENT(temp_set, empty))
  1342.         {
  1343.             RESET_BIT(temp_set, empty);
  1344.             rule_no = item_table[item_no].rule_number;
  1345.             lhs_symbol = rules[rule_no].lhs;
  1346.             if (index_of[lhs_symbol] == OMEGA)
  1347.                 compute_follow(lhs_symbol);
  1348.             SET_UNION( follow, nt, follow, lhs_symbol);
  1349.             index_of[nt] = MIN( index_of[nt], index_of[lhs_symbol]);
  1350.         }
  1351.         SET_UNION(follow, nt, temp_set, 0);
  1352.     }
  1353.  
  1354.     if (index_of[nt] == indx)
  1355.     {
  1356.         for (lhs_symbol = stack[top];
  1357.              lhs_symbol != nt; lhs_symbol = stack[--top])
  1358.         {
  1359.             ASSIGN_SET(follow, lhs_symbol, follow, nt);
  1360.             index_of[lhs_symbol] = INFINITY;
  1361.         }
  1362.         index_of[nt] = INFINITY;
  1363.         top--;
  1364.     }
  1365.     ffree(temp_set);
  1366.     return;
  1367. }
  1368.  
  1369.  
  1370. /*****************************************************************************/
  1371. /*                           PRINT_UNREACHABLES:                             */
  1372. /*****************************************************************************/
  1373. static void print_unreachables(void)
  1374. {
  1375.     short *symbol_list;
  1376.  
  1377.     int nt,
  1378.         t_root,
  1379.         nt_root,
  1380.         rule_no,
  1381.         symbol,
  1382.         i;
  1383.  
  1384.     BOOLEAN end_node;
  1385.  
  1386.     char line[PRINT_LINE_SIZE + 1],
  1387.          tok[SYMBOL_SIZE + 1];
  1388.  
  1389.     /***************************************************************/
  1390.     /* SYMBOL_LIST is used for two purposes:                       */
  1391.     /*  1) to mark symbols that are reachable from the Accepting   */
  1392.     /*        non-terminal.                                        */
  1393.     /*  2) to construct lists of symbols that are not reachable.   */
  1394.     /***************************************************************/
  1395.  
  1396.     symbol_list = Allocate_short_array(num_symbols + 1);
  1397.     for ALL_SYMBOLS(i)
  1398.         symbol_list[i] = OMEGA;
  1399.     symbol_list[eoft_image] = NIL;
  1400.     symbol_list[empty] = NIL;
  1401.     if (error_maps_bit)
  1402.         symbol_list[error_image] = NIL;
  1403.  
  1404.     /*********************************************************************/
  1405.     /* Initialize a list consisting only of the Accept non-terminal.     */
  1406.     /* This list is a work pile of non-terminals to process as follows:  */
  1407.     /* Each non-terminal in the front of the list is removed in turn and */
  1408.     /* 1) All terminal symbols in one of its right-hand sides are        */
  1409.     /*     marked reachable.                                             */
  1410.     /* 2) All non-terminals in one of its right-hand sides are placed    */
  1411.     /*     in the the work pile of it had not been processed previously  */
  1412.     /*********************************************************************/
  1413.     nt_root = accept_image;
  1414.     symbol_list[nt_root] = NIL;
  1415.  
  1416.     for (nt = nt_root; nt != NIL; nt = nt_root)
  1417.     {
  1418.         nt_root = symbol_list[nt];
  1419.  
  1420.         for (end_node = ((rule_no = lhs_rule[nt]) == NIL);
  1421.              ! end_node;
  1422.              end_node = (rule_no == lhs_rule[nt]))
  1423.         {
  1424.             rule_no = next_rule[rule_no];
  1425.             for ENTIRE_RHS(i, rule_no)
  1426.             {
  1427.                 symbol = rhs_sym[i];
  1428.                 if (symbol IS_A_TERMINAL)
  1429.                     symbol_list[symbol] = NIL;
  1430.                 else if (symbol_list[symbol] == OMEGA)
  1431.                 {
  1432.                     symbol_list[symbol] = nt_root;
  1433.                     nt_root = symbol;
  1434.                 }
  1435.             }
  1436.         }
  1437.     }
  1438.  
  1439.     /***************************************************************/
  1440.     /* We now iterate (backwards to keep things in order) over the */
  1441.     /* terminal symbols, and place each unreachable terminal in a  */
  1442.     /* list. If the list is not empty, we signal that these symbols*/
  1443.     /* are unused.                                                 */
  1444.     /***************************************************************/
  1445.     t_root = NIL;
  1446.     for ALL_TERMINALS_BACKWARDS(symbol)
  1447.     {
  1448.         if (symbol_list[symbol] == OMEGA)
  1449.         {
  1450.             symbol_list[symbol] = t_root;
  1451.             t_root = symbol;
  1452.         }
  1453.     }
  1454.  
  1455.     if (t_root != NIL)
  1456.     {
  1457.         PR_HEADING;
  1458.         if (symbol_list[t_root] != NIL)
  1459.         {
  1460.             PRNT("*** The following Terminals are useless: ");
  1461.             fprintf(syslis, "\n\n");
  1462.             strcpy(line, "        "); /* 8 spaces */
  1463.         }
  1464.         else
  1465.             strcpy(line, "*** The following Terminal is useless: ");
  1466.  
  1467.         for (symbol = t_root; symbol != NIL; symbol = symbol_list[symbol])
  1468.         {
  1469.             restore_symbol(tok, RETRIEVE_STRING(symbol));
  1470.             if (strlen(line) + strlen(tok) > PRINT_LINE_SIZE)
  1471.             {
  1472.                 PRNT(line);
  1473.                 print_large_token(line, tok, "    ", LEN);
  1474.             }
  1475.             else
  1476.             {
  1477.                 strcat(line, tok);
  1478.                 strcat(line, BLANK);
  1479.              }
  1480.              strcat(line, BLANK);
  1481.         }
  1482.         PRNT(line);
  1483.     }
  1484.  
  1485.  
  1486.     /***************************************************************/
  1487.     /* We now iterate (backward to keep things in order) over the  */
  1488.     /* non-terminals, and place each unreachable non-terminal in a */
  1489.     /* list.  If the list is not empty, we signal that these       */
  1490.     /* symbols are unused.                                         */
  1491.     /***************************************************************/
  1492.     nt_root = NIL;
  1493.     for ALL_NON_TERMINALS_BACKWARDS(symbol)
  1494.     {
  1495.         if (symbol_list[symbol] == OMEGA)
  1496.         {
  1497.             symbol_list[symbol] = nt_root;
  1498.             nt_root = symbol;
  1499.         }
  1500.     }
  1501.  
  1502.     if (nt_root != NIL)
  1503.     {
  1504.         PR_HEADING;
  1505.         if (symbol_list[nt_root] != NIL)
  1506.         {
  1507.             PRNT("*** The following Non-Terminals are useless: ");
  1508.             fprintf(syslis, "\n\n");
  1509.             strcpy(line, "        "); /* 8 spaces */
  1510.         }
  1511.         else
  1512.             strcpy(line, "*** The following Non-Terminal is useless: ");
  1513.  
  1514.         for (symbol = nt_root; symbol != NIL; symbol = symbol_list[symbol])
  1515.         {
  1516.             restore_symbol(tok, RETRIEVE_STRING(symbol));
  1517.             if (strlen(line) + strlen(tok) > PRINT_LINE_SIZE)
  1518.             {
  1519.                 PRNT(line);
  1520.                 print_large_token(line, tok, "    ", LEN);
  1521.             }
  1522.             else
  1523.                 strcat(line, tok);
  1524.             strcat(line, BLANK);
  1525.         }
  1526.         PRNT(line);
  1527.     }
  1528.  
  1529.     ffree(symbol_list);
  1530.  
  1531.     return;
  1532. }
  1533.  
  1534.  
  1535. /*****************************************************************************/
  1536. /*                               PRINT_XREF:                                 */
  1537. /*****************************************************************************/
  1538. /* PRINT_XREF prints out the Cross-reference map. We build a map from each   */
  1539. /* terminal into the set of items whose Dot-symbol (symbol immediately       */
  1540. /* following the dot ) is the terminal in question.  Note that we iterate    */
  1541. /* backwards over the rules to keep the rules associated with the items      */
  1542. /* sorted, since they are inserted in STACK fashion in the lists:  Last-in,  */
  1543. /* First out.                                                                */
  1544. /*****************************************************************************/
  1545. static void print_xref(void)
  1546. {
  1547.     short *sort_sym,
  1548.           *t_items;
  1549.  
  1550.     int i,
  1551.         offset,
  1552.         rule_no,
  1553.         item_no,
  1554.         symbol;
  1555.  
  1556.     char line[PRINT_LINE_SIZE + 1],
  1557.          tok[SYMBOL_SIZE + 1];
  1558.  
  1559.     /*********************************************************************/
  1560.     /* SORT_SYM is used to sort the symbols for cross_reference listing. */
  1561.     /*********************************************************************/
  1562.     sort_sym = Allocate_short_array(num_symbols + 1);
  1563.     t_items = Allocate_short_array(num_terminals + 1);
  1564.  
  1565.     for ALL_TERMINALS(i)
  1566.         t_items[i] = NIL;
  1567.  
  1568.     for ALL_RULES_BACKWARDS(rule_no)
  1569.     {
  1570.         item_no = first_item_of[rule_no];
  1571.         for ENTIRE_RHS(i, rule_no)
  1572.         {
  1573.             symbol = rhs_sym[i];
  1574.             if (symbol IS_A_TERMINAL)
  1575.             {
  1576.                 next_item[item_no] = t_items[symbol];
  1577.                 t_items[symbol] = item_no;
  1578.             }
  1579.             item_no++;
  1580.         }
  1581.     }
  1582.     for ALL_SYMBOLS(i)
  1583.         sort_sym[i] = i;
  1584.     quick_sym(sort_sym, 1, num_symbols);
  1585.  
  1586.     PR_HEADING;
  1587.     fprintf(syslis, "\n\nCross-reference table:\n");
  1588.     output_line_no += 3;
  1589.     for ALL_SYMBOLS(i)
  1590.     {
  1591.         symbol = sort_sym[i];
  1592.         if (symbol != accept_image && symbol != eoft_image
  1593.                                    && symbol != empty)
  1594.         {
  1595.             fprintf(syslis, "\n");
  1596.             ENDPAGE_CHECK;
  1597.             restore_symbol(tok, RETRIEVE_STRING(symbol));
  1598.             print_large_token(line, tok, "", PRINT_LINE_SIZE-7);
  1599.             strcat(line, "  ==>> ");
  1600.             offset = strlen(line) - 1;
  1601.             if (symbol IS_A_NON_TERMINAL)
  1602.             {
  1603.                 BOOLEAN end_node;
  1604.  
  1605.                 for (end_node = ((rule_no = lhs_rule[symbol]) == NIL);
  1606.                      ! end_node;
  1607.                      end_node = (rule_no == lhs_rule[symbol]))
  1608.                 {
  1609.                     rule_no = next_rule[rule_no];
  1610.                     sprintf(tok, "%d", rule_no);
  1611.                     if (strlen(tok) + strlen(line) > PRINT_LINE_SIZE)
  1612.                     {
  1613.                         int j;
  1614.  
  1615.                         fprintf(syslis, "\n%s", line);
  1616.                         ENDPAGE_CHECK;
  1617.                         strcpy(line, BLANK);
  1618.                         for (j = 1; j <= offset; j++)
  1619.                              strcat(line, BLANK);
  1620.                     }
  1621.                     strcat(line, tok);
  1622.                     strcat(line, BLANK);
  1623.                 }
  1624.                 fprintf(syslis, "\n%s", line);
  1625.                 ENDPAGE_CHECK;
  1626.                 item_no = nt_items[symbol];
  1627.             }
  1628.             else
  1629.             {
  1630.                 for (item_no = t_items[symbol];
  1631.                      item_no != NIL; item_no = next_item[item_no])
  1632.                 {
  1633.                     rule_no = item_table[item_no].rule_number;
  1634.                     sprintf(tok, "%d", rule_no);
  1635.                     if (strlen(tok) + strlen(line) > PRINT_LINE_SIZE)
  1636.                     {
  1637.                         int j;
  1638.  
  1639.                         fprintf(syslis, "\n%s", line);
  1640.                         ENDPAGE_CHECK;
  1641.                         strcpy(line, BLANK);
  1642.                         for (j = 1; j <= offset; j++)
  1643.                              strcat(line, BLANK);
  1644.                     }
  1645.                     strcat(line, tok);
  1646.                     strcat(line, BLANK);
  1647.                 }
  1648.                 fprintf(syslis, "\n%s",line);
  1649.                 ENDPAGE_CHECK;
  1650.             }
  1651.         }
  1652.     }
  1653.     fprintf(syslis, "\n\n");
  1654.     output_line_no +=2;
  1655.     ffree(t_items);
  1656.     ffree(sort_sym);
  1657.  
  1658.     return;
  1659. }
  1660.  
  1661.  
  1662. /*****************************************************************************/
  1663. /*                              QUICK_SYM:                                   */
  1664. /*****************************************************************************/
  1665. /* QUICK_SYM takes as arguments an array of pointers whose elements point to */
  1666. /* nodes and two integer arguments: L, H. L and H indicate respectively the  */
  1667. /* lower and upper bound of a section in the array.                          */
  1668. /*****************************************************************************/
  1669. static void quick_sym(short array[], int l, int h)
  1670. {
  1671.     /**************************************************************/
  1672.     /* Since no more than 2**15-1 symbols are allowed, the stack  */
  1673.     /* not grow past 14.                                          */
  1674.     /**************************************************************/
  1675.  
  1676.     int   lostack[14],
  1677.           histack[14],
  1678.           lower,
  1679.           upper,
  1680.           top,
  1681.           i,
  1682.           j;
  1683.  
  1684.     short temp,
  1685.           pivot;
  1686.  
  1687.     top = 1;
  1688.     lostack[top] = l;
  1689.     histack[top] = h;
  1690.  
  1691.     while(top != 0)
  1692.     {
  1693.         lower = lostack[top];
  1694.         upper = histack[top--];
  1695.  
  1696.         while(upper > lower)
  1697.         {
  1698.             /********************************************************/
  1699.             /* Split the array section indicated by LOWER and UPPER */
  1700.             /* using ARRAY[LOWER] as the pivot.                     */
  1701.             /********************************************************/
  1702.             i = lower;
  1703.             pivot = array[lower];
  1704.             for (j = lower + 1; j <= upper; j++)
  1705.             {
  1706.                 if (strcmp(RETRIEVE_STRING(array[j]),
  1707.                            RETRIEVE_STRING(pivot)) < 0)
  1708.                 {
  1709.                     temp = array[++i];
  1710.                     array[i] = array[j];
  1711.                     array[j] = temp;
  1712.                 }
  1713.             }
  1714.  
  1715.             array[lower] = array[i];
  1716.             array[i] = pivot;
  1717.  
  1718.             top++;
  1719.             if ((i - lower) < (upper - i))
  1720.             {
  1721.                 lostack[top] = i + 1;
  1722.                 histack[top] = upper;
  1723.                 upper = i - 1;
  1724.             }
  1725.             else
  1726.             {
  1727.                 histack[top] = i - 1;
  1728.                 lostack[top] = lower;
  1729.                 lower = i + 1;
  1730.             }
  1731.         }
  1732.     }
  1733.  
  1734.     return;
  1735. }
  1736.  
  1737.  
  1738. /*****************************************************************************/
  1739. /*                             PRINT_NT_FIRST:                               */
  1740. /*****************************************************************************/
  1741. /* PRINT_NT_FIRST prints the first set for each non-terminal.                */
  1742. /*****************************************************************************/
  1743. static void print_nt_first(void)
  1744. {
  1745.     int nt,
  1746.         t;
  1747.  
  1748.     char line[PRINT_LINE_SIZE + 1],
  1749.          tok[SYMBOL_SIZE + 1];
  1750.  
  1751.     PR_HEADING;
  1752.     fprintf(syslis, "\nFirst map for non-terminals:\n\n");
  1753.     output_line_no += 3;
  1754.  
  1755.     for ALL_NON_TERMINALS(nt)
  1756.     {
  1757.         restore_symbol(tok, RETRIEVE_STRING(nt));
  1758.         print_large_token(line, tok, "", PRINT_LINE_SIZE - 7);
  1759.         strcat(line, "  ==>> ");
  1760.         for ALL_TERMINALS(t)
  1761.         {
  1762.             if (IS_IN_SET(nt_first, nt, t))
  1763.             {
  1764.                 restore_symbol(tok, RETRIEVE_STRING(t));
  1765.                 if (strlen(line) + strlen(tok) > PRINT_LINE_SIZE - 1)
  1766.                 {
  1767.                     fprintf(syslis, "\n%s", line);
  1768.                     ENDPAGE_CHECK;
  1769.                     print_large_token(line, tok, "    ", LEN);
  1770.                 }
  1771.                 else
  1772.                     strcat(line, tok);
  1773.                 strcat(line, BLANK);
  1774.             }
  1775.         }
  1776.         fprintf(syslis, "\n%s\n", line);
  1777.         output_line_no++;
  1778.         ENDPAGE_CHECK;
  1779.     }
  1780.  
  1781.     return;
  1782. }
  1783.  
  1784.  
  1785. /*****************************************************************************/
  1786. /*                           PRINT_FOLLOW_MAP:                               */
  1787. /*****************************************************************************/
  1788. /* PRINT_FOLLOW_MAP prints the follow map.                                   */
  1789. /*****************************************************************************/
  1790. static void print_follow_map(void)
  1791. {
  1792.     int nt,
  1793.         t;
  1794.  
  1795.     char line[PRINT_LINE_SIZE + 1],
  1796.          tok[SYMBOL_SIZE + 1];
  1797.  
  1798.     PR_HEADING;
  1799.     fprintf(syslis, "\nFollow Map:\n\n");
  1800.     output_line_no += 3;
  1801.  
  1802.     for ALL_NON_TERMINALS(nt)
  1803.     {
  1804.         restore_symbol(tok, RETRIEVE_STRING(nt));
  1805.         print_large_token(line, tok, "", PRINT_LINE_SIZE-7);
  1806.         strcat(line, "  ==>> ");
  1807.         for ALL_TERMINALS(t)
  1808.         {
  1809.             if (IS_IN_SET(follow, nt, t))
  1810.             {
  1811.                 restore_symbol(tok, RETRIEVE_STRING(t));
  1812.                 if (strlen(line) + strlen(tok) > PRINT_LINE_SIZE-2)
  1813.                 {
  1814.                     fprintf(syslis, "\n%s", line);
  1815.                     ENDPAGE_CHECK;
  1816.                     print_large_token(line, tok, "    ", LEN);
  1817.                 }
  1818.                 else
  1819.                     strcat(line, tok);
  1820.                 strcat(line, BLANK);
  1821.             }
  1822.         }
  1823.         fprintf(syslis, "\n%s\n", line);
  1824.         output_line_no++;
  1825.         ENDPAGE_CHECK;
  1826.     }
  1827.     return;
  1828. }
  1829.