1a94046c4Sbostic /*
2a94046c4Sbostic * Copyright (c) 1989 The Regents of the University of California.
3a94046c4Sbostic * All rights reserved.
4a94046c4Sbostic *
5a94046c4Sbostic * This code is derived from software contributed to Berkeley by
6a94046c4Sbostic * Robert Paul Corbett.
7a94046c4Sbostic *
8ea70a0c4Sbostic * %sccs.include.redist.c%
9a94046c4Sbostic */
10a94046c4Sbostic
11a94046c4Sbostic #ifndef lint
12*c3162ce4Scorbett static char sccsid[] = "@(#)mkpar.c 5.3 (Berkeley) 01/20/91";
13a94046c4Sbostic #endif /* not lint */
14a94046c4Sbostic
15a94046c4Sbostic #include "defs.h"
16a94046c4Sbostic
17a94046c4Sbostic action **parser;
18a94046c4Sbostic int SRtotal;
19a94046c4Sbostic int RRtotal;
20a94046c4Sbostic short *SRconflicts;
21a94046c4Sbostic short *RRconflicts;
22a94046c4Sbostic short *defred;
23a94046c4Sbostic short *rules_used;
24a94046c4Sbostic short nunused;
25a94046c4Sbostic short final_state;
26a94046c4Sbostic
27a94046c4Sbostic static int SRcount;
28a94046c4Sbostic static int RRcount;
29a94046c4Sbostic
30a94046c4Sbostic extern action *parse_actions();
31a94046c4Sbostic extern action *get_shifts();
32a94046c4Sbostic extern action *add_reductions();
33a94046c4Sbostic extern action *add_reduce();
34a94046c4Sbostic
35a94046c4Sbostic
make_parser()36a94046c4Sbostic make_parser()
37a94046c4Sbostic {
38a94046c4Sbostic register int i;
39a94046c4Sbostic
40a94046c4Sbostic parser = NEW2(nstates, action *);
41a94046c4Sbostic for (i = 0; i < nstates; i++)
42a94046c4Sbostic parser[i] = parse_actions(i);
43a94046c4Sbostic
44a94046c4Sbostic find_final_state();
45a94046c4Sbostic remove_conflicts();
46a94046c4Sbostic unused_rules();
47a94046c4Sbostic if (SRtotal + RRtotal > 0) total_conflicts();
48a94046c4Sbostic defreds();
49a94046c4Sbostic }
50a94046c4Sbostic
51a94046c4Sbostic
52a94046c4Sbostic action *
parse_actions(stateno)53a94046c4Sbostic parse_actions(stateno)
54a94046c4Sbostic register int stateno;
55a94046c4Sbostic {
56a94046c4Sbostic register action *actions;
57a94046c4Sbostic
58a94046c4Sbostic actions = get_shifts(stateno);
59a94046c4Sbostic actions = add_reductions(stateno, actions);
60a94046c4Sbostic return (actions);
61a94046c4Sbostic }
62a94046c4Sbostic
63a94046c4Sbostic
64a94046c4Sbostic action *
get_shifts(stateno)65a94046c4Sbostic get_shifts(stateno)
66a94046c4Sbostic int stateno;
67a94046c4Sbostic {
68a94046c4Sbostic register action *actions, *temp;
69a94046c4Sbostic register shifts *sp;
70a94046c4Sbostic register short *to_state;
71a94046c4Sbostic register int i, k;
72a94046c4Sbostic register int symbol;
73a94046c4Sbostic
74a94046c4Sbostic actions = 0;
75a94046c4Sbostic sp = shift_table[stateno];
76a94046c4Sbostic if (sp)
77a94046c4Sbostic {
78a94046c4Sbostic to_state = sp->shift;
79a94046c4Sbostic for (i = sp->nshifts - 1; i >= 0; i--)
80a94046c4Sbostic {
81a94046c4Sbostic k = to_state[i];
82a94046c4Sbostic symbol = accessing_symbol[k];
83a94046c4Sbostic if (ISTOKEN(symbol))
84a94046c4Sbostic {
85a94046c4Sbostic temp = NEW(action);
86a94046c4Sbostic temp->next = actions;
87a94046c4Sbostic temp->symbol = symbol;
88a94046c4Sbostic temp->number = k;
89a94046c4Sbostic temp->prec = symbol_prec[symbol];
90a94046c4Sbostic temp->action_code = SHIFT;
91a94046c4Sbostic temp->assoc = symbol_assoc[symbol];
92a94046c4Sbostic actions = temp;
93a94046c4Sbostic }
94a94046c4Sbostic }
95a94046c4Sbostic }
96a94046c4Sbostic return (actions);
97a94046c4Sbostic }
98a94046c4Sbostic
99a94046c4Sbostic action *
add_reductions(stateno,actions)100a94046c4Sbostic add_reductions(stateno, actions)
101a94046c4Sbostic int stateno;
102a94046c4Sbostic register action *actions;
103a94046c4Sbostic {
104a94046c4Sbostic register int i, j, m, n;
105a94046c4Sbostic register int ruleno, tokensetsize;
106a94046c4Sbostic register unsigned *rowp;
107a94046c4Sbostic
108a94046c4Sbostic tokensetsize = WORDSIZE(ntokens);
109a94046c4Sbostic m = lookaheads[stateno];
110a94046c4Sbostic n = lookaheads[stateno + 1];
111a94046c4Sbostic for (i = m; i < n; i++)
112a94046c4Sbostic {
113a94046c4Sbostic ruleno = LAruleno[i];
114a94046c4Sbostic rowp = LA + i * tokensetsize;
115a94046c4Sbostic for (j = ntokens - 1; j >= 0; j--)
116a94046c4Sbostic {
117a94046c4Sbostic if (BIT(rowp, j))
118a94046c4Sbostic actions = add_reduce(actions, ruleno, j);
119a94046c4Sbostic }
120a94046c4Sbostic }
121a94046c4Sbostic return (actions);
122a94046c4Sbostic }
123a94046c4Sbostic
124a94046c4Sbostic
125a94046c4Sbostic action *
add_reduce(actions,ruleno,symbol)126a94046c4Sbostic add_reduce(actions, ruleno, symbol)
127a94046c4Sbostic register action *actions;
128a94046c4Sbostic register int ruleno, symbol;
129a94046c4Sbostic {
130a94046c4Sbostic register action *temp, *prev, *next;
131a94046c4Sbostic
132a94046c4Sbostic prev = 0;
133a94046c4Sbostic for (next = actions; next && next->symbol < symbol; next = next->next)
134a94046c4Sbostic prev = next;
135a94046c4Sbostic
136a94046c4Sbostic while (next && next->symbol == symbol && next->action_code == SHIFT)
137a94046c4Sbostic {
138a94046c4Sbostic prev = next;
139a94046c4Sbostic next = next->next;
140a94046c4Sbostic }
141a94046c4Sbostic
142a94046c4Sbostic while (next && next->symbol == symbol &&
143a94046c4Sbostic next->action_code == REDUCE && next->number < ruleno)
144a94046c4Sbostic {
145a94046c4Sbostic prev = next;
146a94046c4Sbostic next = next->next;
147a94046c4Sbostic }
148a94046c4Sbostic
149a94046c4Sbostic temp = NEW(action);
150a94046c4Sbostic temp->next = next;
151a94046c4Sbostic temp->symbol = symbol;
152a94046c4Sbostic temp->number = ruleno;
153a94046c4Sbostic temp->prec = rprec[ruleno];
154a94046c4Sbostic temp->action_code = REDUCE;
155a94046c4Sbostic temp->assoc = rassoc[ruleno];
156a94046c4Sbostic
157a94046c4Sbostic if (prev)
158a94046c4Sbostic prev->next = temp;
159a94046c4Sbostic else
160a94046c4Sbostic actions = temp;
161a94046c4Sbostic
162a94046c4Sbostic return (actions);
163a94046c4Sbostic }
164a94046c4Sbostic
165a94046c4Sbostic
find_final_state()166a94046c4Sbostic find_final_state()
167a94046c4Sbostic {
168a94046c4Sbostic register int goal, i;
169a94046c4Sbostic register short *to_state;
170a94046c4Sbostic register shifts *p;
171a94046c4Sbostic
172a94046c4Sbostic p = shift_table[0];
173a94046c4Sbostic to_state = p->shift;
174a94046c4Sbostic goal = ritem[1];
175a94046c4Sbostic for (i = p->nshifts - 1; i >= 0; --i)
176a94046c4Sbostic {
177a94046c4Sbostic final_state = to_state[i];
178a94046c4Sbostic if (accessing_symbol[final_state] == goal) break;
179a94046c4Sbostic }
180a94046c4Sbostic }
181a94046c4Sbostic
182a94046c4Sbostic
unused_rules()183a94046c4Sbostic unused_rules()
184a94046c4Sbostic {
185a94046c4Sbostic register int i;
186a94046c4Sbostic register action *p;
187a94046c4Sbostic
188a94046c4Sbostic rules_used = (short *) MALLOC(nrules*sizeof(short));
189a94046c4Sbostic if (rules_used == 0) no_space();
190a94046c4Sbostic
191a94046c4Sbostic for (i = 0; i < nrules; ++i)
192a94046c4Sbostic rules_used[i] = 0;
193a94046c4Sbostic
194a94046c4Sbostic for (i = 0; i < nstates; ++i)
195a94046c4Sbostic {
196a94046c4Sbostic for (p = parser[i]; p; p = p->next)
197a94046c4Sbostic {
198a94046c4Sbostic if (p->action_code == REDUCE && p->suppressed == 0)
199a94046c4Sbostic rules_used[p->number] = 1;
200a94046c4Sbostic }
201a94046c4Sbostic }
202a94046c4Sbostic
203a94046c4Sbostic nunused = 0;
204a94046c4Sbostic for (i = 3; i < nrules; ++i)
205a94046c4Sbostic if (!rules_used[i]) ++nunused;
206a94046c4Sbostic
207a94046c4Sbostic if (nunused)
208a94046c4Sbostic if (nunused == 1)
209a94046c4Sbostic fprintf(stderr, "%s: 1 rule never reduced\n", myname);
210a94046c4Sbostic else
211a94046c4Sbostic fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
212a94046c4Sbostic }
213a94046c4Sbostic
214a94046c4Sbostic
remove_conflicts()215a94046c4Sbostic remove_conflicts()
216a94046c4Sbostic {
217a94046c4Sbostic register int i;
218a94046c4Sbostic register int symbol;
219*c3162ce4Scorbett register action *p, *pref;
220a94046c4Sbostic
221a94046c4Sbostic SRtotal = 0;
222a94046c4Sbostic RRtotal = 0;
223a94046c4Sbostic SRconflicts = NEW2(nstates, short);
224a94046c4Sbostic RRconflicts = NEW2(nstates, short);
225a94046c4Sbostic for (i = 0; i < nstates; i++)
226a94046c4Sbostic {
227a94046c4Sbostic SRcount = 0;
228a94046c4Sbostic RRcount = 0;
229*c3162ce4Scorbett symbol = -1;
230*c3162ce4Scorbett for (p = parser[i]; p; p = p->next)
231a94046c4Sbostic {
232*c3162ce4Scorbett if (p->symbol != symbol)
233*c3162ce4Scorbett {
234*c3162ce4Scorbett pref = p;
235a94046c4Sbostic symbol = p->symbol;
236*c3162ce4Scorbett }
237*c3162ce4Scorbett else if (i == final_state && symbol == 0)
238*c3162ce4Scorbett {
239*c3162ce4Scorbett SRcount++;
240*c3162ce4Scorbett p->suppressed = 1;
241*c3162ce4Scorbett }
242*c3162ce4Scorbett else if (pref->action_code == SHIFT)
243*c3162ce4Scorbett {
244*c3162ce4Scorbett if (pref->prec > 0 && p->prec > 0)
245*c3162ce4Scorbett {
246*c3162ce4Scorbett if (pref->prec < p->prec)
247*c3162ce4Scorbett {
248*c3162ce4Scorbett pref->suppressed = 2;
249*c3162ce4Scorbett pref = p;
250*c3162ce4Scorbett }
251*c3162ce4Scorbett else if (pref->prec > p->prec)
252*c3162ce4Scorbett {
253*c3162ce4Scorbett p->suppressed = 2;
254*c3162ce4Scorbett }
255*c3162ce4Scorbett else if (pref->assoc == LEFT)
256*c3162ce4Scorbett {
257*c3162ce4Scorbett pref->suppressed = 2;
258*c3162ce4Scorbett pref = p;
259*c3162ce4Scorbett }
260*c3162ce4Scorbett else if (pref->assoc == RIGHT)
261*c3162ce4Scorbett {
262*c3162ce4Scorbett p->suppressed = 2;
263*c3162ce4Scorbett }
264*c3162ce4Scorbett else
265*c3162ce4Scorbett {
266*c3162ce4Scorbett pref->suppressed = 2;
267*c3162ce4Scorbett p->suppressed = 2;
268*c3162ce4Scorbett }
269*c3162ce4Scorbett }
270*c3162ce4Scorbett else
271*c3162ce4Scorbett {
272*c3162ce4Scorbett SRcount++;
273*c3162ce4Scorbett p->suppressed = 1;
274*c3162ce4Scorbett }
275*c3162ce4Scorbett }
276*c3162ce4Scorbett else
277*c3162ce4Scorbett {
278*c3162ce4Scorbett RRcount++;
279*c3162ce4Scorbett p->suppressed = 1;
280*c3162ce4Scorbett }
281a94046c4Sbostic }
282a94046c4Sbostic SRtotal += SRcount;
283a94046c4Sbostic RRtotal += RRcount;
284a94046c4Sbostic SRconflicts[i] = SRcount;
285a94046c4Sbostic RRconflicts[i] = RRcount;
286a94046c4Sbostic }
287a94046c4Sbostic }
288a94046c4Sbostic
289a94046c4Sbostic
total_conflicts()290a94046c4Sbostic total_conflicts()
291a94046c4Sbostic {
292a94046c4Sbostic fprintf(stderr, "%s: ", myname);
293a94046c4Sbostic if (SRtotal == 1)
294a94046c4Sbostic fprintf(stderr, "1 shift/reduce conflict");
295a94046c4Sbostic else if (SRtotal > 1)
296a94046c4Sbostic fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
297a94046c4Sbostic
298a94046c4Sbostic if (SRtotal && RRtotal)
299a94046c4Sbostic fprintf(stderr, ", ");
300a94046c4Sbostic
301a94046c4Sbostic if (RRtotal == 1)
302a94046c4Sbostic fprintf(stderr, "1 reduce/reduce conflict");
303a94046c4Sbostic else if (RRtotal > 1)
304a94046c4Sbostic fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
305a94046c4Sbostic
306a94046c4Sbostic fprintf(stderr, ".\n");
307a94046c4Sbostic }
308a94046c4Sbostic
309a94046c4Sbostic
310a94046c4Sbostic int
sole_reduction(stateno)311a94046c4Sbostic sole_reduction(stateno)
312a94046c4Sbostic int stateno;
313a94046c4Sbostic {
314a94046c4Sbostic register int count, ruleno;
315a94046c4Sbostic register action *p;
316a94046c4Sbostic
317a94046c4Sbostic count = 0;
318a94046c4Sbostic ruleno = 0;
319a94046c4Sbostic for (p = parser[stateno]; p; p = p->next)
320a94046c4Sbostic {
321a94046c4Sbostic if (p->action_code == SHIFT && p->suppressed == 0)
322a94046c4Sbostic return (0);
323a94046c4Sbostic else if (p->action_code == REDUCE && p->suppressed == 0)
324a94046c4Sbostic {
325a94046c4Sbostic if (ruleno > 0 && p->number != ruleno)
326a94046c4Sbostic return (0);
327a94046c4Sbostic if (p->symbol != 1)
328a94046c4Sbostic ++count;
329a94046c4Sbostic ruleno = p->number;
330a94046c4Sbostic }
331a94046c4Sbostic }
332a94046c4Sbostic
333a94046c4Sbostic if (count == 0)
334a94046c4Sbostic return (0);
335a94046c4Sbostic return (ruleno);
336a94046c4Sbostic }
337a94046c4Sbostic
338a94046c4Sbostic
defreds()339a94046c4Sbostic defreds()
340a94046c4Sbostic {
341a94046c4Sbostic register int i;
342a94046c4Sbostic
343a94046c4Sbostic defred = NEW2(nstates, short);
344a94046c4Sbostic for (i = 0; i < nstates; i++)
345a94046c4Sbostic defred[i] = sole_reduction(i);
346a94046c4Sbostic }
347a94046c4Sbostic
free_action_row(p)348a94046c4Sbostic free_action_row(p)
349a94046c4Sbostic register action *p;
350a94046c4Sbostic {
351a94046c4Sbostic register action *q;
352a94046c4Sbostic
353a94046c4Sbostic while (p)
354a94046c4Sbostic {
355a94046c4Sbostic q = p->next;
356a94046c4Sbostic FREE(p);
357a94046c4Sbostic p = q;
358a94046c4Sbostic }
359a94046c4Sbostic }
360a94046c4Sbostic
free_parser()361a94046c4Sbostic free_parser()
362a94046c4Sbostic {
363a94046c4Sbostic register int i;
364a94046c4Sbostic
365a94046c4Sbostic for (i = 0; i < nstates; i++)
366a94046c4Sbostic free_action_row(parser[i]);
367a94046c4Sbostic
368a94046c4Sbostic FREE(parser);
369a94046c4Sbostic }
370