1 /* Match rules with nonterminals for bison,
2
3 Copyright (C) 1984, 1989, 2000, 2001, 2002, 2003, 2005 Free
4 Software Foundation, Inc.
5
6 This file is part of Bison, the GNU Compiler Compiler.
7
8 Bison 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 2, or (at your option)
11 any later version.
12
13 Bison 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 Bison; see the file COPYING. If not, write to
20 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21 Boston, MA 02110-1301, USA. */
22
23 #include <config.h>
24 #include "system.h"
25
26 #include "getargs.h"
27
28 #include "derives.h"
29 #include "gram.h"
30 #include "reader.h"
31 #include "symtab.h"
32
33 /* Linked list of rule numbers. */
34 typedef struct rule_list
35 {
36 struct rule_list *next;
37 rule *value;
38 } rule_list;
39
40 rule ***derives;
41
42 static void
print_derives(void)43 print_derives (void)
44 {
45 int i;
46
47 fputs ("DERIVES\n", stderr);
48
49 for (i = ntokens; i < nsyms; i++)
50 {
51 rule **rp;
52 fprintf (stderr, "\t%s derives\n", symbols[i]->tag);
53 for (rp = derives[i - ntokens]; *rp; ++rp)
54 {
55 fprintf (stderr, "\t\t%3d ", (*rp)->user_number);
56 rule_rhs_print (*rp, stderr);
57 }
58 }
59
60 fputs ("\n\n", stderr);
61 }
62
63
64 void
derives_compute(void)65 derives_compute (void)
66 {
67 symbol_number i;
68 rule_number r;
69 rule **q;
70
71 /* DSET[NTERM - NTOKENS] -- A linked list of the numbers of the rules
72 whose LHS is NTERM. */
73 rule_list **dset = xcalloc (nvars, sizeof *dset);
74
75 /* DELTS[RULE] -- There are NRULES rule number to attach to nterms.
76 Instead of performing NRULES allocations for each, have an array
77 indexed by rule numbers. */
78 rule_list *delts = xnmalloc (nrules, sizeof *delts);
79
80 for (r = nrules - 1; r >= 0; --r)
81 {
82 symbol_number lhs = rules[r].lhs->number;
83 rule_list *p = &delts[r];
84 /* A new LHS is found. */
85 p->next = dset[lhs - ntokens];
86 p->value = &rules[r];
87 dset[lhs - ntokens] = p;
88 }
89
90 /* DSET contains what we need under the form of a linked list. Make
91 it a single array. */
92
93 derives = xnmalloc (nvars, sizeof *derives);
94 q = xnmalloc (nvars + nrules, sizeof *q);
95
96 for (i = ntokens; i < nsyms; i++)
97 {
98 rule_list *p = dset[i - ntokens];
99 derives[i - ntokens] = q;
100 while (p)
101 {
102 *q++ = p->value;
103 p = p->next;
104 }
105 *q++ = NULL;
106 }
107
108 if (trace_flag & trace_sets)
109 print_derives ();
110
111 free (dset);
112 free (delts);
113 }
114
115
116 void
derives_free(void)117 derives_free (void)
118 {
119 free (derives[0]);
120 free (derives);
121 }
122