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