Annotation of src/usr.bin/yacc/mkpar.c, Revision 1.10
1.10 ! millert 1: /* $OpenBSD: mkpar.c,v 1.9 2002/06/19 03:24:56 deraadt Exp $ */
1.4 deraadt 2:
3: /* $NetBSD: mkpar.c,v 1.4 1996/03/19 03:21:39 jtc Exp $ */
4:
5: /*
6: * Copyright (c) 1989 The Regents of the University of California.
7: * All rights reserved.
8: *
9: * This code is derived from software contributed to Berkeley by
10: * Robert Paul Corbett.
11: *
12: * Redistribution and use in source and binary forms, with or without
13: * modification, are permitted provided that the following conditions
14: * are met:
15: * 1. Redistributions of source code must retain the above copyright
16: * notice, this list of conditions and the following disclaimer.
17: * 2. Redistributions in binary form must reproduce the above copyright
18: * notice, this list of conditions and the following disclaimer in the
19: * documentation and/or other materials provided with the distribution.
1.10 ! millert 20: * 3. Neither the name of the University nor the names of its contributors
1.4 deraadt 21: * may be used to endorse or promote products derived from this software
22: * without specific prior written permission.
23: *
24: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34: * SUCH DAMAGE.
35: */
1.3 etheisen 36:
1.1 deraadt 37: #ifndef lint
1.4 deraadt 38: #if 0
39: static char sccsid[] = "@(#)mkpar.c 5.3 (Berkeley) 1/20/91";
40: #else
41: static char rcsid[] = "$NetBSD: mkpar.c,v 1.4 1996/03/19 03:21:39 jtc Exp $";
42: #endif
1.1 deraadt 43: #endif /* not lint */
44:
45: #include "defs.h"
46:
47: action **parser;
48: int SRtotal;
1.2 etheisen 49: int SRexpect = 0;
1.1 deraadt 50: int RRtotal;
51: short *SRconflicts;
52: short *RRconflicts;
53: short *defred;
54: short *rules_used;
55: short nunused;
56: short final_state;
57:
58: static int SRcount;
59: static int RRcount;
60:
61: extern action *parse_actions();
62: extern action *get_shifts();
63: extern action *add_reductions();
64: extern action *add_reduce();
65:
1.8 millert 66: int sole_reduction(int);
67: void free_action_row(action *);
1.1 deraadt 68:
1.8 millert 69: void find_final_state(void);
70: void unused_rules(void);
71: void remove_conflicts(void);
72: void total_conflicts(void);
73: void defreds(void);
1.6 pvalchev 74:
75:
76: void
1.1 deraadt 77: make_parser()
78: {
1.7 mpech 79: int i;
1.1 deraadt 80:
81: parser = NEW2(nstates, action *);
82: for (i = 0; i < nstates; i++)
83: parser[i] = parse_actions(i);
84:
85: find_final_state();
86: remove_conflicts();
87: unused_rules();
88: if (SRtotal + RRtotal > 0) total_conflicts();
89: defreds();
90: }
91:
92:
93: action *
94: parse_actions(stateno)
1.7 mpech 95: int stateno;
1.1 deraadt 96: {
1.7 mpech 97: action *actions;
1.1 deraadt 98:
99: actions = get_shifts(stateno);
100: actions = add_reductions(stateno, actions);
101: return (actions);
102: }
103:
104:
105: action *
106: get_shifts(stateno)
107: int stateno;
108: {
1.7 mpech 109: action *actions, *temp;
110: shifts *sp;
111: short *to_state;
112: int i, k;
113: int symbol;
1.1 deraadt 114:
115: actions = 0;
116: sp = shift_table[stateno];
117: if (sp)
118: {
119: to_state = sp->shift;
120: for (i = sp->nshifts - 1; i >= 0; i--)
121: {
122: k = to_state[i];
123: symbol = accessing_symbol[k];
124: if (ISTOKEN(symbol))
125: {
126: temp = NEW(action);
127: temp->next = actions;
128: temp->symbol = symbol;
129: temp->number = k;
130: temp->prec = symbol_prec[symbol];
131: temp->action_code = SHIFT;
132: temp->assoc = symbol_assoc[symbol];
133: actions = temp;
134: }
135: }
136: }
137: return (actions);
138: }
139:
140: action *
141: add_reductions(stateno, actions)
142: int stateno;
1.7 mpech 143: action *actions;
1.1 deraadt 144: {
1.7 mpech 145: int i, j, m, n;
146: int ruleno, tokensetsize;
147: unsigned *rowp;
1.1 deraadt 148:
149: tokensetsize = WORDSIZE(ntokens);
150: m = lookaheads[stateno];
151: n = lookaheads[stateno + 1];
152: for (i = m; i < n; i++)
153: {
154: ruleno = LAruleno[i];
155: rowp = LA + i * tokensetsize;
156: for (j = ntokens - 1; j >= 0; j--)
157: {
158: if (BIT(rowp, j))
159: actions = add_reduce(actions, ruleno, j);
160: }
161: }
162: return (actions);
163: }
164:
165:
166: action *
167: add_reduce(actions, ruleno, symbol)
1.7 mpech 168: action *actions;
169: int ruleno, symbol;
1.1 deraadt 170: {
1.7 mpech 171: action *temp, *prev, *next;
1.1 deraadt 172:
173: prev = 0;
174: for (next = actions; next && next->symbol < symbol; next = next->next)
175: prev = next;
176:
177: while (next && next->symbol == symbol && next->action_code == SHIFT)
178: {
179: prev = next;
180: next = next->next;
181: }
182:
183: while (next && next->symbol == symbol &&
184: next->action_code == REDUCE && next->number < ruleno)
185: {
186: prev = next;
187: next = next->next;
188: }
189:
190: temp = NEW(action);
191: temp->next = next;
192: temp->symbol = symbol;
193: temp->number = ruleno;
194: temp->prec = rprec[ruleno];
195: temp->action_code = REDUCE;
196: temp->assoc = rassoc[ruleno];
197:
198: if (prev)
199: prev->next = temp;
200: else
201: actions = temp;
202:
203: return (actions);
204: }
205:
206:
1.6 pvalchev 207: void
1.1 deraadt 208: find_final_state()
209: {
1.7 mpech 210: int goal, i;
211: short *to_state;
212: shifts *p;
1.1 deraadt 213:
214: p = shift_table[0];
215: to_state = p->shift;
216: goal = ritem[1];
217: for (i = p->nshifts - 1; i >= 0; --i)
218: {
219: final_state = to_state[i];
220: if (accessing_symbol[final_state] == goal) break;
221: }
222: }
223:
224:
1.6 pvalchev 225: void
1.1 deraadt 226: unused_rules()
227: {
1.7 mpech 228: int i;
229: action *p;
1.1 deraadt 230:
231: rules_used = (short *) MALLOC(nrules*sizeof(short));
232: if (rules_used == 0) no_space();
233:
234: for (i = 0; i < nrules; ++i)
235: rules_used[i] = 0;
236:
237: for (i = 0; i < nstates; ++i)
238: {
239: for (p = parser[i]; p; p = p->next)
240: {
241: if (p->action_code == REDUCE && p->suppressed == 0)
242: rules_used[p->number] = 1;
243: }
244: }
245:
246: nunused = 0;
247: for (i = 3; i < nrules; ++i)
248: if (!rules_used[i]) ++nunused;
249:
1.6 pvalchev 250: if (nunused) {
1.1 deraadt 251: if (nunused == 1)
1.5 millert 252: fprintf(stderr, "%s: 1 rule never reduced\n", __progname);
1.1 deraadt 253: else
1.5 millert 254: fprintf(stderr, "%s: %d rules never reduced\n", __progname,
255: nunused);
1.6 pvalchev 256: }
1.1 deraadt 257: }
258:
259:
1.6 pvalchev 260: void
1.1 deraadt 261: remove_conflicts()
262: {
1.7 mpech 263: int i;
264: int symbol;
265: action *p, *pref;
1.1 deraadt 266:
267: SRtotal = 0;
268: RRtotal = 0;
269: SRconflicts = NEW2(nstates, short);
270: RRconflicts = NEW2(nstates, short);
271: for (i = 0; i < nstates; i++)
272: {
273: SRcount = 0;
274: RRcount = 0;
275: symbol = -1;
276: for (p = parser[i]; p; p = p->next)
277: {
278: if (p->symbol != symbol)
279: {
280: pref = p;
281: symbol = p->symbol;
282: }
283: else if (i == final_state && symbol == 0)
284: {
285: SRcount++;
286: p->suppressed = 1;
287: }
288: else if (pref->action_code == SHIFT)
289: {
290: if (pref->prec > 0 && p->prec > 0)
291: {
292: if (pref->prec < p->prec)
293: {
294: pref->suppressed = 2;
295: pref = p;
296: }
297: else if (pref->prec > p->prec)
298: {
299: p->suppressed = 2;
300: }
301: else if (pref->assoc == LEFT)
302: {
303: pref->suppressed = 2;
304: pref = p;
305: }
306: else if (pref->assoc == RIGHT)
307: {
308: p->suppressed = 2;
309: }
310: else
311: {
312: pref->suppressed = 2;
313: p->suppressed = 2;
314: }
315: }
316: else
317: {
318: SRcount++;
319: p->suppressed = 1;
320: }
321: }
322: else
323: {
324: RRcount++;
325: p->suppressed = 1;
326: }
327: }
328: SRtotal += SRcount;
329: RRtotal += RRcount;
330: SRconflicts[i] = SRcount;
331: RRconflicts[i] = RRcount;
332: }
333: }
334:
335:
1.6 pvalchev 336: void
1.1 deraadt 337: total_conflicts()
338: {
1.2 etheisen 339: /* Warn if s/r != expect or if any r/r */
340: if ((SRtotal != SRexpect) || RRtotal)
341: {
342: if (SRtotal == 1)
1.9 deraadt 343: fprintf(stderr, "%s: %s finds 1 shift/reduce conflict\n",
344: input_file_name, __progname);
1.2 etheisen 345: else if (SRtotal > 1)
1.9 deraadt 346: fprintf(stderr, "%s: %s finds %d shift/reduce conflicts\n",
347: input_file_name, __progname, SRtotal);
1.2 etheisen 348: }
1.1 deraadt 349:
350: if (RRtotal == 1)
1.9 deraadt 351: fprintf(stderr, "%s: %s finds 1 reduce/reduce conflict\n",
352: input_file_name, __progname);
1.1 deraadt 353: else if (RRtotal > 1)
1.9 deraadt 354: fprintf(stderr, "%s: %s finds %d reduce/reduce conflicts\n",
355: input_file_name, __progname, RRtotal);
1.1 deraadt 356: }
357:
358:
359: int
360: sole_reduction(stateno)
361: int stateno;
362: {
1.7 mpech 363: int count, ruleno;
364: action *p;
1.1 deraadt 365:
366: count = 0;
367: ruleno = 0;
368: for (p = parser[stateno]; p; p = p->next)
369: {
370: if (p->action_code == SHIFT && p->suppressed == 0)
371: return (0);
372: else if (p->action_code == REDUCE && p->suppressed == 0)
373: {
374: if (ruleno > 0 && p->number != ruleno)
375: return (0);
376: if (p->symbol != 1)
377: ++count;
378: ruleno = p->number;
379: }
380: }
381:
382: if (count == 0)
383: return (0);
384: return (ruleno);
385: }
386:
387:
1.6 pvalchev 388: void
1.1 deraadt 389: defreds()
390: {
1.7 mpech 391: int i;
1.1 deraadt 392:
393: defred = NEW2(nstates, short);
394: for (i = 0; i < nstates; i++)
395: defred[i] = sole_reduction(i);
396: }
397:
1.6 pvalchev 398: void
1.1 deraadt 399: free_action_row(p)
1.7 mpech 400: action *p;
1.1 deraadt 401: {
1.7 mpech 402: action *q;
1.1 deraadt 403:
404: while (p)
405: {
406: q = p->next;
407: FREE(p);
408: p = q;
409: }
410: }
411:
1.6 pvalchev 412: void
1.1 deraadt 413: free_parser()
414: {
1.7 mpech 415: int i;
1.1 deraadt 416:
417: for (i = 0; i < nstates; i++)
418: free_action_row(parser[i]);
419:
420: FREE(parser);
421: }
![[BACK]](/icons/back.gif){kind=icon}
Return to mkpar.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / yacc