Commit | Line | Data |
---|---|---|
c8bff85f KB |
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 | * Redistribution and use in source and binary forms are permitted | |
9 | * provided that the above copyright notice and this paragraph are | |
10 | * duplicated in all such forms and that any documentation, | |
11 | * advertising materials, and other materials related to such | |
12 | * distribution and use acknowledge that the software was developed | |
13 | * by the University of California, Berkeley. The name of the | |
14 | * University may not be used to endorse or promote products derived | |
15 | * from this software without specific prior written permission. | |
16 | * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR | |
17 | * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED | |
18 | * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. | |
19 | */ | |
20 | ||
21 | #ifndef lint | |
22 | static char sccsid[] = "@(#)mkpar.c 5.1 (Berkeley) %G%"; | |
23 | #endif /* not lint */ | |
24 | ||
25 | #include "defs.h" | |
26 | ||
27 | action **parser; | |
28 | int SRtotal; | |
29 | int RRtotal; | |
30 | short *SRconflicts; | |
31 | short *RRconflicts; | |
32 | short *defred; | |
33 | short *rules_used; | |
34 | short nunused; | |
35 | short final_state; | |
36 | ||
37 | static int SRcount; | |
38 | static int RRcount; | |
39 | ||
40 | extern action *parse_actions(); | |
41 | extern action *get_shifts(); | |
42 | extern action *add_reductions(); | |
43 | extern action *add_reduce(); | |
44 | ||
45 | ||
46 | make_parser() | |
47 | { | |
48 | register int i; | |
49 | ||
50 | parser = NEW2(nstates, action *); | |
51 | for (i = 0; i < nstates; i++) | |
52 | parser[i] = parse_actions(i); | |
53 | ||
54 | find_final_state(); | |
55 | remove_conflicts(); | |
56 | unused_rules(); | |
57 | if (SRtotal + RRtotal > 0) total_conflicts(); | |
58 | defreds(); | |
59 | } | |
60 | ||
61 | ||
62 | action * | |
63 | parse_actions(stateno) | |
64 | register int stateno; | |
65 | { | |
66 | register action *actions; | |
67 | ||
68 | actions = get_shifts(stateno); | |
69 | actions = add_reductions(stateno, actions); | |
70 | return (actions); | |
71 | } | |
72 | ||
73 | ||
74 | action * | |
75 | get_shifts(stateno) | |
76 | int stateno; | |
77 | { | |
78 | register action *actions, *temp; | |
79 | register shifts *sp; | |
80 | register short *to_state; | |
81 | register int i, k; | |
82 | register int symbol; | |
83 | ||
84 | actions = 0; | |
85 | sp = shift_table[stateno]; | |
86 | if (sp) | |
87 | { | |
88 | to_state = sp->shift; | |
89 | for (i = sp->nshifts - 1; i >= 0; i--) | |
90 | { | |
91 | k = to_state[i]; | |
92 | symbol = accessing_symbol[k]; | |
93 | if (ISTOKEN(symbol)) | |
94 | { | |
95 | temp = NEW(action); | |
96 | temp->next = actions; | |
97 | temp->symbol = symbol; | |
98 | temp->number = k; | |
99 | temp->prec = symbol_prec[symbol]; | |
100 | temp->action_code = SHIFT; | |
101 | temp->assoc = symbol_assoc[symbol]; | |
102 | actions = temp; | |
103 | } | |
104 | } | |
105 | } | |
106 | return (actions); | |
107 | } | |
108 | ||
109 | action * | |
110 | add_reductions(stateno, actions) | |
111 | int stateno; | |
112 | register action *actions; | |
113 | { | |
114 | register int i, j, m, n; | |
115 | register int ruleno, tokensetsize; | |
116 | register unsigned *rowp; | |
117 | ||
118 | tokensetsize = WORDSIZE(ntokens); | |
119 | m = lookaheads[stateno]; | |
120 | n = lookaheads[stateno + 1]; | |
121 | for (i = m; i < n; i++) | |
122 | { | |
123 | ruleno = LAruleno[i]; | |
124 | rowp = LA + i * tokensetsize; | |
125 | for (j = ntokens - 1; j >= 0; j--) | |
126 | { | |
127 | if (BIT(rowp, j)) | |
128 | actions = add_reduce(actions, ruleno, j); | |
129 | } | |
130 | } | |
131 | return (actions); | |
132 | } | |
133 | ||
134 | ||
135 | action * | |
136 | add_reduce(actions, ruleno, symbol) | |
137 | register action *actions; | |
138 | register int ruleno, symbol; | |
139 | { | |
140 | register action *temp, *prev, *next; | |
141 | ||
142 | prev = 0; | |
143 | for (next = actions; next && next->symbol < symbol; next = next->next) | |
144 | prev = next; | |
145 | ||
146 | while (next && next->symbol == symbol && next->action_code == SHIFT) | |
147 | { | |
148 | prev = next; | |
149 | next = next->next; | |
150 | } | |
151 | ||
152 | while (next && next->symbol == symbol && | |
153 | next->action_code == REDUCE && next->number < ruleno) | |
154 | { | |
155 | prev = next; | |
156 | next = next->next; | |
157 | } | |
158 | ||
159 | temp = NEW(action); | |
160 | temp->next = next; | |
161 | temp->symbol = symbol; | |
162 | temp->number = ruleno; | |
163 | temp->prec = rprec[ruleno]; | |
164 | temp->action_code = REDUCE; | |
165 | temp->assoc = rassoc[ruleno]; | |
166 | ||
167 | if (prev) | |
168 | prev->next = temp; | |
169 | else | |
170 | actions = temp; | |
171 | ||
172 | return (actions); | |
173 | } | |
174 | ||
175 | ||
176 | find_final_state() | |
177 | { | |
178 | register int goal, i; | |
179 | register short *to_state; | |
180 | register shifts *p; | |
181 | ||
182 | p = shift_table[0]; | |
183 | to_state = p->shift; | |
184 | goal = ritem[1]; | |
185 | for (i = p->nshifts - 1; i >= 0; --i) | |
186 | { | |
187 | final_state = to_state[i]; | |
188 | if (accessing_symbol[final_state] == goal) break; | |
189 | } | |
190 | } | |
191 | ||
192 | ||
193 | unused_rules() | |
194 | { | |
195 | register int i; | |
196 | register action *p; | |
197 | ||
198 | rules_used = (short *) MALLOC(nrules*sizeof(short)); | |
199 | if (rules_used == 0) no_space(); | |
200 | ||
201 | for (i = 0; i < nrules; ++i) | |
202 | rules_used[i] = 0; | |
203 | ||
204 | for (i = 0; i < nstates; ++i) | |
205 | { | |
206 | for (p = parser[i]; p; p = p->next) | |
207 | { | |
208 | if (p->action_code == REDUCE && p->suppressed == 0) | |
209 | rules_used[p->number] = 1; | |
210 | } | |
211 | } | |
212 | ||
213 | nunused = 0; | |
214 | for (i = 3; i < nrules; ++i) | |
215 | if (!rules_used[i]) ++nunused; | |
216 | ||
217 | if (nunused) | |
218 | if (nunused == 1) | |
219 | fprintf(stderr, "%s: 1 rule never reduced\n", myname); | |
220 | else | |
221 | fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused); | |
222 | } | |
223 | ||
224 | ||
225 | remove_conflicts() | |
226 | { | |
227 | register int i; | |
228 | register int symbol; | |
229 | register action *p, *q; | |
230 | ||
231 | SRtotal = 0; | |
232 | RRtotal = 0; | |
233 | SRconflicts = NEW2(nstates, short); | |
234 | RRconflicts = NEW2(nstates, short); | |
235 | for (i = 0; i < nstates; i++) | |
236 | { | |
237 | SRcount = 0; | |
238 | RRcount = 0; | |
239 | for (p = parser[i]; p; p = q->next) | |
240 | { | |
241 | symbol = p->symbol; | |
242 | q = p; | |
243 | while (q->next && q->next->symbol == symbol) | |
244 | q = q->next; | |
245 | if (i == final_state && symbol == 0) | |
246 | end_conflicts(p, q); | |
247 | else if (p != q) | |
248 | resolve_conflicts(p, q); | |
249 | } | |
250 | SRtotal += SRcount; | |
251 | RRtotal += RRcount; | |
252 | SRconflicts[i] = SRcount; | |
253 | RRconflicts[i] = RRcount; | |
254 | } | |
255 | } | |
256 | ||
257 | ||
258 | end_conflicts(p, q) | |
259 | register action *p, *q; | |
260 | { | |
261 | for (;;) | |
262 | { | |
263 | SRcount++; | |
264 | p->suppressed = 1; | |
265 | if (p == q) break; | |
266 | p = p->next; | |
267 | } | |
268 | } | |
269 | ||
270 | ||
271 | resolve_conflicts(first, last) | |
272 | register action *first, *last; | |
273 | { | |
274 | register action *p; | |
275 | register int count; | |
276 | ||
277 | count = 1; | |
278 | for (p = first; p != last; p = p->next) | |
279 | ++count; | |
280 | assert(count > 1); | |
281 | ||
282 | if (first->action_code == SHIFT && count == 2 && | |
283 | first->prec > 0 && last->prec > 0) | |
284 | { | |
285 | if (first->prec == last->prec) | |
286 | { | |
287 | if (first->assoc == LEFT) | |
288 | first->suppressed = 2; | |
289 | else if (first->assoc == RIGHT) | |
290 | last->suppressed = 2; | |
291 | else | |
292 | { | |
293 | first->suppressed = 2; | |
294 | last->suppressed = 2; | |
295 | first->action_code = ERROR; | |
296 | last->action_code = ERROR; | |
297 | } | |
298 | } | |
299 | else if (first->prec < last->prec) | |
300 | first->suppressed = 2; | |
301 | else | |
302 | last->suppressed = 2; | |
303 | } | |
304 | else | |
305 | { | |
306 | if (first->action_code == SHIFT) | |
307 | SRcount += (count - 1); | |
308 | else | |
309 | RRcount += (count - 1); | |
310 | for (p = first; p != last; p = p->next, p->suppressed = 1) | |
311 | continue; | |
312 | } | |
313 | } | |
314 | ||
315 | ||
316 | total_conflicts() | |
317 | { | |
318 | fprintf(stderr, "%s: ", myname); | |
319 | if (SRtotal == 1) | |
320 | fprintf(stderr, "1 shift/reduce conflict"); | |
321 | else if (SRtotal > 1) | |
322 | fprintf(stderr, "%d shift/reduce conflicts", SRtotal); | |
323 | ||
324 | if (SRtotal && RRtotal) | |
325 | fprintf(stderr, ", "); | |
326 | ||
327 | if (RRtotal == 1) | |
328 | fprintf(stderr, "1 reduce/reduce conflict"); | |
329 | else if (RRtotal > 1) | |
330 | fprintf(stderr, "%d reduce/reduce conflicts", RRtotal); | |
331 | ||
332 | fprintf(stderr, ".\n"); | |
333 | } | |
334 | ||
335 | ||
336 | int | |
337 | sole_reduction(stateno) | |
338 | int stateno; | |
339 | { | |
340 | register int count, ruleno; | |
341 | register action *p; | |
342 | ||
343 | count = 0; | |
344 | ruleno = 0; | |
345 | for (p = parser[stateno]; p; p = p->next) | |
346 | { | |
347 | if (p->action_code == SHIFT && p->suppressed == 0) | |
348 | return (0); | |
349 | else if (p->action_code == REDUCE && p->suppressed == 0) | |
350 | { | |
351 | if (ruleno > 0 && p->number != ruleno) | |
352 | return (0); | |
353 | if (p->symbol != 1) | |
354 | ++count; | |
355 | ruleno = p->number; | |
356 | } | |
357 | } | |
358 | ||
359 | if (count == 0) | |
360 | return (0); | |
361 | return (ruleno); | |
362 | } | |
363 | ||
364 | ||
365 | defreds() | |
366 | { | |
367 | register int i; | |
368 | ||
369 | defred = NEW2(nstates, short); | |
370 | for (i = 0; i < nstates; i++) | |
371 | defred[i] = sole_reduction(i); | |
372 | } | |
373 | ||
374 | free_action_row(p) | |
375 | register action *p; | |
376 | { | |
377 | register action *q; | |
378 | ||
379 | while (p) | |
380 | { | |
381 | q = p->next; | |
382 | FREE(p); | |
383 | p = q; | |
384 | } | |
385 | } | |
386 | ||
387 | free_parser() | |
388 | { | |
389 | register int i; | |
390 | ||
391 | for (i = 0; i < nstates; i++) | |
392 | free_action_row(parser[i]); | |
393 | ||
394 | FREE(parser); | |
395 | } |