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