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 | * | |
6ecf3d85 | 8 | * %sccs.include.redist.c% |
c8bff85f KB |
9 | */ |
10 | ||
11 | #ifndef lint | |
011facea | 12 | static char sccsid[] = "@(#)mkpar.c 5.3 (Berkeley) %G%"; |
c8bff85f KB |
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 | ||
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 * | |
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 * | |
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 * | |
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 * | |
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 | ||
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 | ||
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 | ||
215 | remove_conflicts() | |
216 | { | |
217 | register int i; | |
218 | register int symbol; | |
011facea | 219 | register action *p, *pref; |
c8bff85f KB |
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; | |
011facea BC |
229 | symbol = -1; |
230 | for (p = parser[i]; p; p = p->next) | |
c8bff85f | 231 | { |
011facea BC |
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 | } | |
c8bff85f KB |
281 | } |
282 | SRtotal += SRcount; | |
283 | RRtotal += RRcount; | |
284 | SRconflicts[i] = SRcount; | |
285 | RRconflicts[i] = RRcount; | |
286 | } | |
287 | } | |
288 | ||
289 | ||
c8bff85f KB |
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 | |
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 | ||
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 | ||
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 | ||
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 | } |