Commit | Line | Data |
---|---|---|
273a74fa AD |
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) | |
427c0dda | 104 | injections_print ("syntactic direct injections"); |
273a74fa AD |
105 | bitsetv_transitive_closure (injects); |
106 | if (trace_flag & trace_sets) | |
427c0dda | 107 | injections_print ("syntactic injections"); |
273a74fa AD |
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 | } |