1 | /* Match rules with nonterminals for bison, |
2 | |
3 | Copyright (C) 1984, 1989, 2000-2003, 2005, 2009-2015, 2018-2019 Free |
4 | Software Foundation, Inc. |
5 | |
6 | This file is part of Bison, the GNU Compiler Compiler. |
7 | |
8 | This program is free software: you can redistribute it and/or modify |
9 | it under the terms of the GNU General Public License as published by |
10 | the Free Software Foundation, either version 3 of the License, or |
11 | (at your option) any later version. |
12 | |
13 | This program is distributed in the hope that it will be useful, |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
16 | GNU General Public License for more details. |
17 | |
18 | You should have received a copy of the GNU General Public License |
19 | along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
20 | |
21 | #include <config.h> |
22 | #include "system.h" |
23 | |
24 | #include "getargs.h" |
25 | |
26 | #include "derives.h" |
27 | #include "gram.h" |
28 | #include "reader.h" |
29 | #include "symtab.h" |
30 | |
31 | /* Linked list of rule numbers. */ |
32 | typedef struct rule_list |
33 | { |
34 | struct rule_list *next; |
35 | rule *value; |
36 | } rule_list; |
37 | |
38 | rule ***derives; |
39 | |
40 | static void |
41 | print_derives (void) |
42 | { |
43 | int i; |
44 | |
45 | fputs ("DERIVES\n" , stderr); |
46 | |
47 | for (i = ntokens; i < nsyms; i++) |
48 | { |
49 | fprintf (stderr, " %s derives\n" , symbols[i]->tag); |
50 | for (rule **rp = derives[i - ntokens]; *rp; ++rp) |
51 | { |
52 | fprintf (stderr, " %3d " , (*rp)->user_number); |
53 | rule_rhs_print (*rp, stderr); |
54 | fprintf (stderr, "\n" ); |
55 | } |
56 | } |
57 | |
58 | fputs ("\n\n" , stderr); |
59 | } |
60 | |
61 | |
62 | void |
63 | derives_compute (void) |
64 | { |
65 | /* DSET[NTERM - NTOKENS] -- A linked list of the numbers of the rules |
66 | whose LHS is NTERM. */ |
67 | rule_list **dset = xcalloc (nvars, sizeof *dset); |
68 | |
69 | /* DELTS[RULE] -- There are NRULES rule number to attach to nterms. |
70 | Instead of performing NRULES allocations for each, have an array |
71 | indexed by rule numbers. */ |
72 | rule_list *delts = xnmalloc (nrules, sizeof *delts); |
73 | |
74 | for (rule_number r = nrules - 1; r >= 0; --r) |
75 | { |
76 | symbol_number lhs = rules[r].lhs->number; |
77 | rule_list *p = &delts[r]; |
78 | /* A new LHS is found. */ |
79 | p->next = dset[lhs - ntokens]; |
80 | p->value = &rules[r]; |
81 | dset[lhs - ntokens] = p; |
82 | } |
83 | |
84 | /* DSET contains what we need under the form of a linked list. Make |
85 | it a single array. */ |
86 | |
87 | derives = xnmalloc (nvars, sizeof *derives); |
88 | /* Q is the storage for DERIVES[...] (DERIVES[0] = q). */ |
89 | rule **q = xnmalloc (nvars + nrules, sizeof *q); |
90 | |
91 | for (symbol_number i = ntokens; i < nsyms; i++) |
92 | { |
93 | rule_list *p = dset[i - ntokens]; |
94 | derives[i - ntokens] = q; |
95 | while (p) |
96 | { |
97 | *q++ = p->value; |
98 | p = p->next; |
99 | } |
100 | *q++ = NULL; |
101 | } |
102 | |
103 | if (trace_flag & trace_sets) |
104 | print_derives (); |
105 | |
106 | free (dset); |
107 | free (delts); |
108 | } |
109 | |
110 | |
111 | void |
112 | derives_free (void) |
113 | { |
114 | free (derives[0]); |
115 | free (derives); |
116 | } |
117 | |