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