src/injections.c

   1 /* Grammar reduction for Bison.
   2    Copyright (C) 2002  Free Software Foundation, Inc.
   3
   4    This file is part of Bison, the GNU Compiler Compiler.
   5
   6    Bison is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    Bison is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with Bison; see the file COPYING.  If not, write to
  18    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19    Boston, MA 02111-1307, USA.  */
  20
  21 /* Reduce the grammar: Look for injections.  Akim Demaille.  */
  22
  23 #include "system.h"
  24 #include "quotearg.h"
  25 #include "bitsetv.h"
  26 #include "bitsetv-print.h"
  27 #include "complain.h"
  28 #include "gram.h"
  29 #include "getargs.h"
  30 #include "derives.h"
  31 #include "injections.h"
  32
  33 /* Set of all nonterminals which are not useless.  */
  34 static bitsetv injects;
  35
  36 #define   INJECTS(Var)   injects[(Var) - ntokens]
  37
  38 /*-----------------------------------------------------------.
  39 | Free the global sets used to compute the reduced grammar.  |
  40 `-----------------------------------------------------------*/
  41
  42 void
  43 injections_new (void)
  44 {
  45   if (!injects)
  46     injects = bitsetv_create (nvars, nvars, BITSET_FIXED);
  47   else
  48     bitsetv_zero (injects);
  49 }
  50
  51 void
  52 injections_free (void)
  53 {
  54   bitsetv_free (injects);
  55   injects = NULL;
  56 }
  57
  58
  59 /*------------------------------.
  60 | Dump the list of injections.  |
  61 `------------------------------*/
  62
  63 static void
  64 injections_print (const char *title)
  65 {
  66   int i, j;
  67
  68   fprintf (stderr, "%s\n", title);
  69   for (i = ntokens; i < nsyms; i++)
  70     if (bitset_count (INJECTS (i)))
  71     {
  72       fprintf (stderr, "\t%s injects\n",
  73                quotearg_style (escape_quoting_style, symbols[i]->tag));
  74       for (j = 0; j < nvars; j++)
  75         if (bitset_test (INJECTS (i), j))
  76           fprintf (stderr, "\t\t%s\n",
  77                    quotearg_style (escape_quoting_style,
  78                                    symbols[j + ntokens]->tag));
  79     }
  80   fprintf (stderr, "\n\n");
  81 }
  82
  83
  84 /*-----------------------------------------------------------------.
  85 | Set INJECTS[i, j] if the nonterminal j derives the nonterminal j |
  86 | (typically, `i -> j' is a rule, plus transitive closure).        |
  87 `-----------------------------------------------------------------*/
  88
  89 static void
  90 injections_compute (void)
  91 {
  92   int i, j;
  93
  94   injections_new ();
  95   for (i = ntokens; i < nsyms; i++)
  96     for (j = 0; derives[i][j] >= 0; ++j)
  97       {
  98         int symbol = rules[derives[i][j]].rhs[0];
  99         if (ISVAR (symbol) && rules[derives[i][j]].rhs[1] < 0)
 100           bitset_set (INJECTS (i), symbol - ntokens);
 101       }
 102
 103   if (trace_flag & trace_sets)
 104     injections_print ("syntactic direct injections");
 105   bitsetv_transitive_closure (injects);
 106   if (trace_flag & trace_sets)
 107     injections_print ("syntactic injections");
 108 }
 109
 110
 111
 112 /*--------------------------------------------------------------.
 113 | Look for infinitely ambiguous grammars: they contain cycles.  |
 114 `--------------------------------------------------------------*/
 115
 116 void
 117 injections_check_cycles (void)
 118 {
 119   int i;
 120
 121   injections_compute ();
 122   for (i = ntokens; i < nsyms; i++)
 123     if (bitset_test (INJECTS (i), i - ntokens))
 124       complain (_("infinitely ambiguous grammar: %s derives itself"),
 125                 symbols[i]->tag);
 126 }