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