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