2 * Copyright (c) 1989 The Regents of the University of California.
5 * This code is derived from software contributed to Berkeley by
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. All advertising materials mentioning features or use of this software
17 * must display the following acknowledgement:
18 * This product includes software developed by the University of
19 * California, Berkeley and its contributors.
20 * 4. Neither the name of the University nor the names of its contributors
21 * may be used to endorse or promote products derived from this software
22 * without specific prior written permission.
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
38 static char sccsid[] = "@(#)mkpar.c 5.3 (Berkeley) 1/20/91";
56 extern action *parse_actions();
57 extern action *get_shifts();
58 extern action *add_reductions();
59 extern action *add_reduce();
66 parser = NEW2(nstates, action *);
67 for (i = 0; i < nstates; i++)
68 parser[i] = parse_actions(i);
73 if (SRtotal + RRtotal > 0) total_conflicts();
79 parse_actions(stateno)
82 register action *actions;
84 actions = get_shifts(stateno);
85 actions = add_reductions(stateno, actions);
94 register action *actions, *temp;
96 register short *to_state;
101 sp = shift_table[stateno];
104 to_state = sp->shift;
105 for (i = sp->nshifts - 1; i >= 0; i--)
108 symbol = accessing_symbol[k];
112 temp->next = actions;
113 temp->symbol = symbol;
115 temp->prec = symbol_prec[symbol];
116 temp->action_code = SHIFT;
117 temp->assoc = symbol_assoc[symbol];
126 add_reductions(stateno, actions)
128 register action *actions;
130 register int i, j, m, n;
131 register int ruleno, tokensetsize;
132 register unsigned *rowp;
134 tokensetsize = WORDSIZE(ntokens);
135 m = lookaheads[stateno];
136 n = lookaheads[stateno + 1];
137 for (i = m; i < n; i++)
139 ruleno = LAruleno[i];
140 rowp = LA + i * tokensetsize;
141 for (j = ntokens - 1; j >= 0; j--)
144 actions = add_reduce(actions, ruleno, j);
152 add_reduce(actions, ruleno, symbol)
153 register action *actions;
154 register int ruleno, symbol;
156 register action *temp, *prev, *next;
159 for (next = actions; next && next->symbol < symbol; next = next->next)
162 while (next && next->symbol == symbol && next->action_code == SHIFT)
168 while (next && next->symbol == symbol &&
169 next->action_code == REDUCE && next->number < ruleno)
177 temp->symbol = symbol;
178 temp->number = ruleno;
179 temp->prec = rprec[ruleno];
180 temp->action_code = REDUCE;
181 temp->assoc = rassoc[ruleno];
194 register int goal, i;
195 register short *to_state;
201 for (i = p->nshifts - 1; i >= 0; --i)
203 final_state = to_state[i];
204 if (accessing_symbol[final_state] == goal) break;
214 rules_used = (short *) MALLOC(nrules*sizeof(short));
215 if (rules_used == 0) no_space();
217 for (i = 0; i < nrules; ++i)
220 for (i = 0; i < nstates; ++i)
222 for (p = parser[i]; p; p = p->next)
224 if (p->action_code == REDUCE && p->suppressed == 0)
225 rules_used[p->number] = 1;
230 for (i = 3; i < nrules; ++i)
231 if (!rules_used[i]) ++nunused;
235 fprintf(stderr, "%s: 1 rule never reduced\n", myname);
237 fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
245 register action *p, *pref;
249 SRconflicts = NEW2(nstates, short);
250 RRconflicts = NEW2(nstates, short);
251 for (i = 0; i < nstates; i++)
256 for (p = parser[i]; p; p = p->next)
258 if (p->symbol != symbol)
263 else if (i == final_state && symbol == 0)
268 else if (pref->action_code == SHIFT)
270 if (pref->prec > 0 && p->prec > 0)
272 if (pref->prec < p->prec)
274 pref->suppressed = 2;
277 else if (pref->prec > p->prec)
281 else if (pref->assoc == LEFT)
283 pref->suppressed = 2;
286 else if (pref->assoc == RIGHT)
292 pref->suppressed = 2;
310 SRconflicts[i] = SRcount;
311 RRconflicts[i] = RRcount;
318 fprintf(stderr, "%s: ", myname);
320 fprintf(stderr, "1 shift/reduce conflict");
321 else if (SRtotal > 1)
322 fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
324 if (SRtotal && RRtotal)
325 fprintf(stderr, ", ");
328 fprintf(stderr, "1 reduce/reduce conflict");
329 else if (RRtotal > 1)
330 fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
332 fprintf(stderr, ".\n");
337 sole_reduction(stateno)
340 register int count, ruleno;
345 for (p = parser[stateno]; p; p = p->next)
347 if (p->action_code == SHIFT && p->suppressed == 0)
349 else if (p->action_code == REDUCE && p->suppressed == 0)
351 if (ruleno > 0 && p->number != ruleno)
369 defred = NEW2(nstates, short);
370 for (i = 0; i < nstates; i++)
371 defred[i] = sole_reduction(i);
391 for (i = 0; i < nstates; i++)
392 free_action_row(parser[i]);