home *** CD-ROM | disk | FTP | other *** search
/ ftp.mactech.com 2010 / ftp.mactech.com.tar / ftp.mactech.com / online / source / c / compilers / Bison.sit.hqx / Bison / Source / reduce.c < prev    next >
Text File  |  1992-08-21  |  15KB  |  645 lines
  1. /***********************************************************
  2.  *
  3.  * Macintosh/MPW version of GNU Bison 1.18
  4.  * Please read the README_MPW file for more information
  5.  *
  6.  ***********************************************************/
  7.  
  8. /* Grammar reduction for Bison.
  9.    Copyright (C) 1988, 1989 Free Software Foundation, Inc.
  10.  
  11. This file is part of Bison, the GNU Compiler Compiler.
  12.  
  13. Bison is free software; you can redistribute it and/or modify
  14. it under the terms of the GNU General Public License as published by
  15. the Free Software Foundation; either version 2, or (at your option)
  16. any later version.
  17.  
  18. Bison is distributed in the hope that it will be useful,
  19. but WITHOUT ANY WARRANTY; without even the implied warranty of
  20. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21. GNU General Public License for more details.
  22.  
  23. You should have received a copy of the GNU General Public License
  24. along with Bison; see the file COPYING.  If not, write to
  25. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  26.  
  27.  
  28. /*
  29.  * Reduce the grammar:  Find and eliminate unreachable terminals,
  30.  * nonterminals, and productions.  David S. Bakin.
  31.  */
  32.  
  33. /*
  34.  * Don't eliminate unreachable terminals:  They may be used by the user's
  35.  * parser.
  36.  */
  37.  
  38. #include <stdio.h>
  39. #include "system.h"
  40. #include "files.h"
  41. #include "gram.h"
  42. #include "machine.h"
  43. #include "new.h"
  44.  
  45. #ifdef macintosh
  46. #include "CursorCtl.h"
  47. #pragma segment bison
  48. #endif
  49.  
  50. extern char   **tags;        /* reader.c */
  51. extern int      verboseflag;    /* getargs.c */
  52. static int      statisticsflag;    /* XXXXXXX */
  53.  
  54. #ifndef TRUE
  55. #define TRUE    (1)
  56. #define FALSE    (0)
  57. #endif
  58. typedef int bool;
  59. typedef unsigned *BSet;
  60. typedef short  *rule;
  61.  
  62.  
  63. /*
  64.  * N is set of all nonterminals which are not useless.  P is set of all rules
  65.  * which have no useless nonterminals in their RHS.  V is the set of all
  66.  * accessible symbols.
  67.  */
  68.  
  69. static BSet     N, P, V, V1;
  70.  
  71. static int      nuseful_productions, nuseless_productions,
  72.                 nuseful_nonterminals, nuseless_nonterminals;
  73.  
  74.  
  75. static void useless_nonterminals();
  76. static void inaccessable_symbols();
  77. static void reduce_grammar_tables();
  78. static void print_results();
  79. static void print_notices();
  80. void dump_grammar();
  81.  
  82. extern void fatals ();
  83.  
  84.  
  85. bool
  86. bits_equal (L, R, n)
  87. BSet L;
  88. BSet R;
  89. int n;
  90. {
  91.   int i;
  92.  
  93.   for (i = n - 1; i >= 0; i--)
  94.     if (L[i] != R[i])
  95.       return FALSE;
  96.   return TRUE;
  97. }
  98.  
  99.  
  100. int
  101. nbits (i)
  102. unsigned i;
  103. {
  104.   int count = 0;
  105.  
  106.   while (i != 0) {
  107.     i ^= (i & -i);
  108.     ++count;
  109.   }
  110.   return count;
  111. }
  112.  
  113.  
  114. int
  115. bits_size (S, n)
  116. BSet S;
  117. int n;
  118. {
  119.   int i, count = 0;
  120.  
  121.   for (i = n - 1; i >= 0; i--)
  122.     count += nbits(S[i]);
  123.   return count;
  124. }
  125.  
  126. void
  127. reduce_grammar ()
  128. {
  129.   bool reduced;
  130.  
  131.   /* Allocate the global sets used to compute the reduced grammar */
  132.  
  133.   N = NEW2(WORDSIZE(nvars), unsigned);
  134.   P = NEW2(WORDSIZE(nrules + 1), unsigned);
  135.   V = NEW2(WORDSIZE(nsyms), unsigned);
  136.   V1 = NEW2(WORDSIZE(nsyms), unsigned);
  137.  
  138.   useless_nonterminals();
  139.   inaccessable_symbols();
  140.  
  141.   reduced = (bool) (nuseless_nonterminals + nuseless_productions > 0);
  142.  
  143.   if (verboseflag)
  144.     print_results();
  145.  
  146.   if (reduced == FALSE)
  147.     goto done_reducing;
  148.  
  149.   print_notices();
  150.  
  151.   if (!BITISSET(N, start_symbol - ntokens))
  152.     fatals("Start symbol %s does not derive any sentence.",
  153.        tags[start_symbol]);
  154.  
  155.   reduce_grammar_tables();
  156.   /* if (verboseflag) {
  157.      fprintf(foutput, "REDUCED GRAMMAR\n\n");
  158.      dump_grammar();
  159.      }
  160.      */
  161.  
  162.   /**/ statisticsflag = FALSE; /* someday getopts should handle this */
  163.   if (statisticsflag == TRUE)
  164.     fprintf(stderr,
  165.         "reduced %s defines %d terminal%s, %d nonterminal%s\
  166. , and %d production%s.\n", infile,
  167.         ntokens, (ntokens == 1 ? "" : "s"),
  168.         nvars,   (nvars   == 1 ? "" : "s"),
  169.         nrules,  (nrules  == 1 ? "" : "s"));
  170.  
  171.  done_reducing:
  172.  
  173.   /* Free the global sets used to compute the reduced grammar */
  174.  
  175.   FREE(N);
  176.   FREE(V);
  177.   FREE(P);
  178.  
  179. }
  180.  
  181. /*
  182.  * Another way to do this would be with a set for each production and then do
  183.  * subset tests against N, but even for the C grammar the whole reducing
  184.  * process takes only 2 seconds on my 8Mhz AT.
  185.  */
  186.  
  187. static bool 
  188. useful_production (i, N)
  189. int  i;
  190. BSet N;
  191. {
  192.   rule  r;
  193.   short n;
  194.  
  195.   /*
  196.    * A production is useful if all of the nonterminals in its RHS
  197.    * appear in the set of useful nonterminals.
  198.    */
  199.  
  200.   for (r = &ritem[rrhs[i]]; *r > 0; r++)
  201.     if (ISVAR(n = *r))
  202.       if (!BITISSET(N, n - ntokens))
  203.     return FALSE;
  204.   return TRUE;
  205. }
  206.  
  207.  
  208. /* Remember that rules are 1-origin, symbols are 0-origin. */
  209.  
  210. static void 
  211. useless_nonterminals ()
  212. {
  213.   BSet Np, Ns;
  214.   int  i, n;
  215.  
  216.   /*
  217.    * N is set as built.  Np is set being built this iteration. P is set
  218.    * of all productions which have a RHS all in N.
  219.    */
  220.  
  221.   Np = NEW2(WORDSIZE(nvars), unsigned);
  222.  
  223.   /*
  224.    * The set being computed is a set of nonterminals which can derive
  225.    * the empty string or strings consisting of all terminals. At each
  226.    * iteration a nonterminal is added to the set if there is a
  227.    * production with that nonterminal as its LHS for which all the
  228.    * nonterminals in its RHS are already in the set.  Iterate until the
  229.    * set being computed remains unchanged.  Any nonterminals not in the
  230.    * set at that point are useless in that they will never be used in
  231.    * deriving a sentence of the language.
  232.    * 
  233.    * This iteration doesn't use any special traversal over the
  234.    * productions.  A set is kept of all productions for which all the
  235.    * nonterminals in the RHS are in useful.  Only productions not in
  236.    * this set are scanned on each iteration.  At the end, this set is
  237.    * saved to be used when finding useful productions: only productions
  238.    * in this set will appear in the final grammar.
  239.    */
  240.  
  241.   n = 0;
  242.   while (1)
  243.     {
  244.  
  245. #ifdef macintosh
  246.       SpinCursor( 1 );
  247. #endif
  248.  
  249.       for (i = WORDSIZE(nvars) - 1; i >= 0; i--)
  250.     Np[i] = N[i];
  251.       for (i = 1; i <= nrules; i++)
  252.     {
  253.       if (!BITISSET(P, i))
  254.         {
  255.           if (useful_production(i, N))
  256.         {
  257.           SETBIT(Np, rlhs[i] - ntokens);
  258.           SETBIT(P, i);
  259.         }
  260.         }
  261.     }
  262.       if (bits_equal(N, Np, WORDSIZE(nvars)))
  263.     break;
  264.       Ns = Np;
  265.       Np = N;
  266.       N = Ns;
  267.     }
  268.   FREE(N);
  269.   N = Np;
  270. }
  271.  
  272. static void 
  273. inaccessable_symbols ()
  274. {
  275.   BSet  Vp, Vs, Pp;
  276.   int   i, n;
  277.   short t;
  278.   rule  r;
  279.  
  280.   /*
  281.    * Find out which productions are reachable and which symbols are
  282.    * used.  Starting with an empty set of productions and a set of
  283.    * symbols which only has the start symbol in it, iterate over all
  284.    * productions until the set of productions remains unchanged for an
  285.    * iteration.  For each production which has a LHS in the set of
  286.    * reachable symbols, add the production to the set of reachable
  287.    * productions, and add all of the nonterminals in the RHS of the
  288.    * production to the set of reachable symbols.
  289.    * 
  290.    * Consider only the (partially) reduced grammar which has only
  291.    * nonterminals in N and productions in P.
  292.    * 
  293.    * The result is the set P of productions in the reduced grammar, and
  294.    * the set V of symbols in the reduced grammar.
  295.    * 
  296.    * Although this algorithm also computes the set of terminals which are
  297.    * reachable, no terminal will be deleted from the grammar. Some
  298.    * terminals might not be in the grammar but might be generated by
  299.    * semantic routines, and so the user might want them available with
  300.    * specified numbers.  (Is this true?)  However, the nonreachable
  301.    * terminals are printed (if running in verbose mode) so that the user
  302.    * can know.
  303.    */
  304.  
  305.   Vp = NEW2(WORDSIZE(nsyms), unsigned);
  306.   Pp = NEW2(WORDSIZE(nrules + 1), unsigned);
  307.  
  308.   /* If the start symbol isn't useful, then nothing will be useful. */
  309.   if (!BITISSET(N, start_symbol - ntokens))
  310.     goto end_iteration;
  311.  
  312.   SETBIT(V, start_symbol);
  313.  
  314.   n = 0;
  315.   while (1)
  316.     {
  317.  
  318. #ifdef macintosh
  319.       SpinCursor( 1 );
  320. #endif
  321.  
  322.       for (i = WORDSIZE(nsyms) - 1; i >= 0; i--)
  323.     Vp[i] = V[i];
  324.       for (i = 1; i <= nrules; i++)
  325.     {
  326.       if (!BITISSET(Pp, i) && BITISSET(P, i) && 
  327.           BITISSET(V, rlhs[i]))
  328.         {
  329.           for (r = &ritem[rrhs[i]]; *r >= 0; r++)
  330.         {
  331.           if (ISTOKEN(t = *r)
  332.               || BITISSET(N, t - ntokens))
  333.             {
  334.               SETBIT(Vp, t);
  335.             }
  336.         }
  337.           SETBIT(Pp, i);
  338.         }
  339.     }
  340.       if (bits_equal(V, Vp, WORDSIZE(nsyms)))
  341.     {
  342.       break;
  343.     }
  344.       Vs = Vp;
  345.       Vp = V;
  346.       V = Vs;
  347.     }
  348.  end_iteration:
  349.  
  350.   FREE(V);
  351.   V = Vp;
  352.  
  353.   /* Tokens 0, 1, and 2 are internal to Bison.  Consider them useful. */
  354.   SETBIT(V, 0);            /* end-of-input token */
  355.   SETBIT(V, 1);            /* error token */
  356.   SETBIT(V, 2);            /* illegal token */
  357.  
  358.   FREE(P);
  359.   P = Pp;
  360.  
  361.   nuseful_productions = bits_size(P, WORDSIZE(nrules + 1));
  362.   nuseless_productions = nrules - nuseful_productions;
  363.  
  364.   nuseful_nonterminals = 0;
  365.   for (i = ntokens; i < nsyms; i++)
  366.     if (BITISSET(V, i))
  367.       nuseful_nonterminals++;
  368.   nuseless_nonterminals = nvars - nuseful_nonterminals;
  369.  
  370.   /* A token that was used in %prec should not be warned about.  */
  371.   for (i = 1; i < nrules; i++)
  372.     if (rprecsym[i] != 0)
  373.       SETBIT(V1, rprecsym[i]);
  374. }
  375.  
  376. static void 
  377. reduce_grammar_tables ()
  378. {
  379. /* This is turned off because we would need to change the numbers
  380.    in the case statements in the actions file.  */
  381. #if 0
  382.   /* remove useless productions */
  383.   if (nuseless_productions > 0)
  384.     {
  385.       short np, pn, ni, pi;
  386.  
  387.       np = 0;
  388.       ni = 0;
  389.       for (pn = 1; pn <= nrules; pn++)
  390.     {
  391.  
  392. #ifdef macintosh
  393.       SpinCursor( 1 );
  394. #endif
  395.  
  396.       if (BITISSET(P, pn))
  397.         {
  398.           np++;
  399.           if (pn != np)
  400.         {
  401.           rlhs[np] = rlhs[pn];
  402.           rline[np] = rline[pn];
  403.           rprec[np] = rprec[pn];
  404.           rassoc[np] = rassoc[pn];
  405.           rrhs[np] = rrhs[pn];
  406.           if (rrhs[np] != ni)
  407.             {
  408.               pi = rrhs[np];
  409.               rrhs[np] = ni;
  410.               while (ritem[pi] >= 0)
  411.             ritem[ni++] = ritem[pi++];
  412.               ritem[ni++] = -np;
  413.             }
  414.         } else {
  415.           while (ritem[ni++] >= 0);
  416.         }
  417.         }
  418.     }
  419.       ritem[ni] = 0;
  420.       nrules -= nuseless_productions;
  421.       nitems = ni;
  422.  
  423.       /*
  424.        * Is it worth it to reduce the amount of memory for the
  425.        * grammar? Probably not.
  426.        */
  427.  
  428.     }
  429. #endif /* 0 */
  430.   /* Disable useless productions,
  431.      since they may contain useless nonterms
  432.      that would get mapped below to -1 and confuse everyone.  */
  433.   if (nuseless_productions > 0)
  434.     {
  435.       int pn;
  436.  
  437.       for (pn = 1; pn <= nrules; pn++)
  438.     {
  439.       if (!BITISSET(P, pn))
  440.         {
  441.           rlhs[pn] = -1;
  442.         }
  443.     }
  444.     }
  445.  
  446.   /* remove useless symbols */
  447.   if (nuseless_nonterminals > 0)
  448.     {
  449.  
  450.       int    i, n;
  451. /*      short  j; JF unused */
  452.       short *nontermmap;
  453.       rule   r;
  454.  
  455.       /*
  456.        * create a map of nonterminal number to new nonterminal
  457.        * number. -1 in the map means it was useless and is being
  458.        * eliminated.
  459.        */
  460.  
  461.       nontermmap = NEW2(nvars, short) - ntokens;
  462.       for (i = ntokens; i < nsyms; i++)
  463.     nontermmap[i] = -1;
  464.  
  465.       n = ntokens;
  466.       for (i = ntokens; i < nsyms; i++)
  467.     if (BITISSET(V, i))
  468.       nontermmap[i] = n++;
  469.  
  470.       /* Shuffle elements of tables indexed by symbol number.  */
  471.  
  472.       for (i = ntokens; i < nsyms; i++)
  473.     {
  474.  
  475. #ifdef macintosh
  476.       SpinCursor( 1 );
  477. #endif
  478.  
  479.       n = nontermmap[i];
  480.       if (n >= 0)
  481.         {
  482.           sassoc[n] = sassoc[i];
  483.           sprec[n] = sprec[i];
  484.           tags[n] = tags[i];
  485.         } else {
  486.           free(tags[i]);
  487.         }
  488.     }
  489.  
  490.       /* Replace all symbol numbers in valid data structures.  */
  491.  
  492.       for (i = 1; i <= nrules; i++)
  493.     {
  494.  
  495. #ifdef macintosh
  496.       SpinCursor( 1 );
  497. #endif
  498.  
  499.       /* Ignore the rules disabled above.  */
  500.       if (rlhs[i] >= 0)
  501.         rlhs[i] = nontermmap[rlhs[i]];
  502.       if (ISVAR (rprecsym[i]))
  503.         /* Can this happen?  */
  504.         rprecsym[i] = nontermmap[rprecsym[i]];
  505.     }
  506.  
  507.       for (r = ritem; *r; r++)
  508.     if (ISVAR(*r))
  509.       *r = nontermmap[*r];
  510.  
  511.       start_symbol = nontermmap[start_symbol];
  512.  
  513.       nsyms -= nuseless_nonterminals;
  514.       nvars -= nuseless_nonterminals;
  515.  
  516.       free(&nontermmap[ntokens]);
  517.     }
  518. }
  519.  
  520. static void 
  521. print_results ()
  522. {
  523.   int   i;
  524. /*  short j; JF unused */
  525.   rule  r;
  526.   bool  b;
  527.  
  528.   if (nuseless_nonterminals > 0)
  529.     {
  530.       fprintf(foutput, "Useless nonterminals:\n\n");
  531.       for (i = ntokens; i < nsyms; i++)
  532.     if (!BITISSET(V, i))
  533.       fprintf(foutput, "   %s\n", tags[i]);
  534.     }
  535.   b = FALSE;
  536.   for (i = 0; i < ntokens; i++)
  537.     {
  538.  
  539. #ifdef macintosh
  540.       SpinCursor( 1 );
  541. #endif
  542.  
  543.       if (!BITISSET(V, i) && !BITISSET(V1, i))
  544.     {
  545.       if (!b)
  546.         {
  547.           fprintf(foutput, "\n\nTerminals which are not used:\n\n");
  548.           b = TRUE;
  549.         }
  550.       fprintf(foutput, "   %s\n", tags[i]);
  551.     }
  552.     }
  553.  
  554.   if (nuseless_productions > 0)
  555.     {
  556.       fprintf(foutput, "\n\nUseless rules:\n\n");
  557.       for (i = 1; i <= nrules; i++)
  558.     {
  559.       if (!BITISSET(P, i))
  560.         {
  561.           fprintf(foutput, "#%-4d  ", i);
  562.           fprintf(foutput, "%s :\t", tags[rlhs[i]]);
  563.           for (r = &ritem[rrhs[i]]; *r >= 0; r++)
  564.         {
  565.           fprintf(foutput, " %s", tags[*r]);
  566.         }
  567.           fprintf(foutput, ";\n");
  568.         }
  569.     }
  570.     }
  571.   if (nuseless_nonterminals > 0 || nuseless_productions > 0 || b)
  572.     fprintf(foutput, "\n\n");
  573. }
  574.  
  575. void 
  576. dump_grammar ()
  577. {
  578.   int i;
  579.   rule r;
  580.  
  581.   fprintf(foutput,
  582.       "ntokens = %d, nvars = %d, nsyms = %d, nrules = %d, nitems = %d\n\n",
  583.       ntokens, nvars, nsyms, nrules, nitems);
  584.   fprintf(foutput, "Variables\n---------\n\n");
  585.   fprintf(foutput, "Value  Sprec    Sassoc    Tag\n");
  586.   for (i = ntokens; i < nsyms; i++)
  587.     fprintf(foutput, "%5d  %5d  %5d  %s\n",
  588.         i, sprec[i], sassoc[i], tags[i]);
  589.   fprintf(foutput, "\n\n");
  590.   fprintf(foutput, "Rules\n-----\n\n");
  591.   for (i = 1; i <= nrules; i++)
  592.     {
  593.  
  594. #ifdef macintosh
  595.       SpinCursor( 1 );
  596. #endif
  597.  
  598.       fprintf(foutput, "%-5d(%5d%5d)%5d : (@%-5d)", 
  599.           i, rprec[i], rassoc[i], rlhs[i], rrhs[i]);
  600.       for (r = &ritem[rrhs[i]]; *r > 0; r++)
  601.     fprintf(foutput, "%5d", *r);
  602.       fprintf(foutput, " [%d]\n", -(*r));
  603.     }
  604.   fprintf(foutput, "\n\n");
  605.   fprintf(foutput, "Rules interpreted\n-----------------\n\n");
  606.   for (i = 1; i <= nrules; i++)
  607.     {
  608.       fprintf(foutput, "%-5d  %s :", i, tags[rlhs[i]]);
  609.       for (r = &ritem[rrhs[i]]; *r > 0; r++)
  610.     fprintf(foutput, " %s", tags[*r]);
  611.       fprintf(foutput, "\n");
  612.     }
  613.   fprintf(foutput, "\n\n");
  614. }
  615.  
  616.  
  617. static void 
  618. print_notices ()
  619. {
  620.   extern int fixed_outfiles;
  621.  
  622.   if (fixed_outfiles && nuseless_productions)
  623.     fprintf(stderr, "%d rules never reduced\n", nuseless_productions);
  624.  
  625.   fprintf(stderr, "%s contains ", infile);
  626.  
  627.   if (nuseless_nonterminals > 0)
  628.     {
  629.       fprintf(stderr, "%d useless nonterminal%s",
  630.           nuseless_nonterminals,
  631.           (nuseless_nonterminals == 1 ? "" : "s"));
  632.     }
  633.   if (nuseless_nonterminals > 0 && nuseless_productions > 0)
  634.     fprintf(stderr, " and ");
  635.  
  636.   if (nuseless_productions > 0)
  637.     {
  638.       fprintf(stderr, "%d useless rule%s",
  639.           nuseless_productions,
  640.           (nuseless_productions == 1 ? "" : "s"));
  641.     }
  642.   fprintf(stderr, ".\n");
  643.   fflush(stderr);
  644. }
  645.