Annotation of src/usr.bin/yacc/mkpar.c, Revision 1.14
1.14 ! deraadt 1: /* $OpenBSD: mkpar.c,v 1.13 2005/06/10 16:40:45 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.1 deraadt 35:
36: #include "defs.h"
37:
38: action **parser;
39: int SRtotal;
1.2 etheisen 40: int SRexpect = 0;
1.1 deraadt 41: int RRtotal;
42: short *SRconflicts;
43: short *RRconflicts;
44: short *defred;
45: short *rules_used;
46: short nunused;
47: short final_state;
48:
49: static int SRcount;
50: static int RRcount;
51:
52: extern action *parse_actions();
53: extern action *get_shifts();
54: extern action *add_reductions();
55: extern action *add_reduce();
56:
1.8 millert 57: int sole_reduction(int);
58: void free_action_row(action *);
1.1 deraadt 59:
1.8 millert 60: void find_final_state(void);
61: void unused_rules(void);
62: void remove_conflicts(void);
63: void total_conflicts(void);
64: void defreds(void);
1.6 pvalchev 65:
66:
67: void
1.11 pvalchev 68: make_parser(void)
1.1 deraadt 69: {
1.7 mpech 70: int i;
1.1 deraadt 71:
72: parser = NEW2(nstates, action *);
73: for (i = 0; i < nstates; i++)
74: parser[i] = parse_actions(i);
75:
76: find_final_state();
77: remove_conflicts();
78: unused_rules();
79: if (SRtotal + RRtotal > 0) total_conflicts();
80: defreds();
81: }
82:
83:
84: action *
1.11 pvalchev 85: parse_actions(int stateno)
1.1 deraadt 86: {
1.7 mpech 87: action *actions;
1.1 deraadt 88:
89: actions = get_shifts(stateno);
90: actions = add_reductions(stateno, actions);
91: return (actions);
92: }
93:
94:
95: action *
1.11 pvalchev 96: get_shifts(int stateno)
1.1 deraadt 97: {
1.7 mpech 98: action *actions, *temp;
99: shifts *sp;
100: short *to_state;
101: int i, k;
102: int symbol;
1.1 deraadt 103:
104: actions = 0;
105: sp = shift_table[stateno];
106: if (sp)
107: {
108: to_state = sp->shift;
109: for (i = sp->nshifts - 1; i >= 0; i--)
110: {
111: k = to_state[i];
112: symbol = accessing_symbol[k];
113: if (ISTOKEN(symbol))
114: {
115: temp = NEW(action);
116: temp->next = actions;
117: temp->symbol = symbol;
118: temp->number = k;
119: temp->prec = symbol_prec[symbol];
120: temp->action_code = SHIFT;
121: temp->assoc = symbol_assoc[symbol];
122: actions = temp;
123: }
124: }
125: }
126: return (actions);
127: }
128:
129: action *
1.11 pvalchev 130: add_reductions(int stateno, action *actions)
1.1 deraadt 131: {
1.7 mpech 132: int i, j, m, n;
133: int ruleno, tokensetsize;
134: unsigned *rowp;
1.1 deraadt 135:
136: tokensetsize = WORDSIZE(ntokens);
137: m = lookaheads[stateno];
138: n = lookaheads[stateno + 1];
139: for (i = m; i < n; i++)
140: {
141: ruleno = LAruleno[i];
142: rowp = LA + i * tokensetsize;
143: for (j = ntokens - 1; j >= 0; j--)
144: {
145: if (BIT(rowp, j))
146: actions = add_reduce(actions, ruleno, j);
147: }
148: }
149: return (actions);
150: }
151:
152:
153: action *
1.11 pvalchev 154: add_reduce(action *actions, int ruleno, int symbol)
1.1 deraadt 155: {
1.7 mpech 156: action *temp, *prev, *next;
1.1 deraadt 157:
158: prev = 0;
159: for (next = actions; next && next->symbol < symbol; next = next->next)
160: prev = next;
161:
162: while (next && next->symbol == symbol && next->action_code == SHIFT)
163: {
164: prev = next;
165: next = next->next;
166: }
167:
168: while (next && next->symbol == symbol &&
169: next->action_code == REDUCE && next->number < ruleno)
170: {
171: prev = next;
172: next = next->next;
173: }
174:
175: temp = NEW(action);
176: temp->next = next;
177: temp->symbol = symbol;
178: temp->number = ruleno;
179: temp->prec = rprec[ruleno];
180: temp->action_code = REDUCE;
181: temp->assoc = rassoc[ruleno];
182:
183: if (prev)
184: prev->next = temp;
185: else
186: actions = temp;
187:
188: return (actions);
189: }
190:
191:
1.6 pvalchev 192: void
1.11 pvalchev 193: find_final_state(void)
1.1 deraadt 194: {
1.7 mpech 195: int goal, i;
196: short *to_state;
197: shifts *p;
1.1 deraadt 198:
199: p = shift_table[0];
200: to_state = p->shift;
201: goal = ritem[1];
202: for (i = p->nshifts - 1; i >= 0; --i)
203: {
204: final_state = to_state[i];
205: if (accessing_symbol[final_state] == goal) break;
206: }
207: }
208:
209:
1.6 pvalchev 210: void
1.11 pvalchev 211: unused_rules(void)
1.1 deraadt 212: {
1.7 mpech 213: int i;
214: action *p;
1.1 deraadt 215:
216: rules_used = (short *) MALLOC(nrules*sizeof(short));
217: if (rules_used == 0) no_space();
218:
219: for (i = 0; i < nrules; ++i)
220: rules_used[i] = 0;
221:
222: for (i = 0; i < nstates; ++i)
223: {
224: for (p = parser[i]; p; p = p->next)
225: {
226: if (p->action_code == REDUCE && p->suppressed == 0)
227: rules_used[p->number] = 1;
228: }
229: }
230:
231: nunused = 0;
232: for (i = 3; i < nrules; ++i)
233: if (!rules_used[i]) ++nunused;
234:
1.6 pvalchev 235: if (nunused) {
1.1 deraadt 236: if (nunused == 1)
1.5 millert 237: fprintf(stderr, "%s: 1 rule never reduced\n", __progname);
1.1 deraadt 238: else
1.5 millert 239: fprintf(stderr, "%s: %d rules never reduced\n", __progname,
240: nunused);
1.6 pvalchev 241: }
1.1 deraadt 242: }
243:
244:
1.6 pvalchev 245: void
1.11 pvalchev 246: remove_conflicts(void)
1.1 deraadt 247: {
1.7 mpech 248: int i;
249: int symbol;
1.13 pvalchev 250: action *p, *pref = NULL;
1.1 deraadt 251:
252: SRtotal = 0;
253: RRtotal = 0;
254: SRconflicts = NEW2(nstates, short);
255: RRconflicts = NEW2(nstates, short);
256: for (i = 0; i < nstates; i++)
257: {
258: SRcount = 0;
259: RRcount = 0;
260: symbol = -1;
261: for (p = parser[i]; p; p = p->next)
262: {
263: if (p->symbol != symbol)
264: {
265: pref = p;
266: symbol = p->symbol;
267: }
268: else if (i == final_state && symbol == 0)
269: {
270: SRcount++;
271: p->suppressed = 1;
272: }
273: else if (pref->action_code == SHIFT)
274: {
275: if (pref->prec > 0 && p->prec > 0)
276: {
277: if (pref->prec < p->prec)
278: {
279: pref->suppressed = 2;
280: pref = p;
281: }
282: else if (pref->prec > p->prec)
283: {
284: p->suppressed = 2;
285: }
286: else if (pref->assoc == LEFT)
287: {
288: pref->suppressed = 2;
289: pref = p;
290: }
291: else if (pref->assoc == RIGHT)
292: {
293: p->suppressed = 2;
294: }
295: else
296: {
297: pref->suppressed = 2;
298: p->suppressed = 2;
299: }
300: }
301: else
302: {
303: SRcount++;
304: p->suppressed = 1;
305: }
306: }
307: else
308: {
309: RRcount++;
310: p->suppressed = 1;
311: }
312: }
313: SRtotal += SRcount;
314: RRtotal += RRcount;
315: SRconflicts[i] = SRcount;
316: RRconflicts[i] = RRcount;
317: }
318: }
319:
320:
1.6 pvalchev 321: void
1.11 pvalchev 322: total_conflicts(void)
1.1 deraadt 323: {
1.2 etheisen 324: /* Warn if s/r != expect or if any r/r */
325: if ((SRtotal != SRexpect) || RRtotal)
326: {
327: if (SRtotal == 1)
1.9 deraadt 328: fprintf(stderr, "%s: %s finds 1 shift/reduce conflict\n",
329: input_file_name, __progname);
1.2 etheisen 330: else if (SRtotal > 1)
1.9 deraadt 331: fprintf(stderr, "%s: %s finds %d shift/reduce conflicts\n",
332: input_file_name, __progname, SRtotal);
1.2 etheisen 333: }
1.1 deraadt 334:
335: if (RRtotal == 1)
1.9 deraadt 336: fprintf(stderr, "%s: %s finds 1 reduce/reduce conflict\n",
337: input_file_name, __progname);
1.1 deraadt 338: else if (RRtotal > 1)
1.9 deraadt 339: fprintf(stderr, "%s: %s finds %d reduce/reduce conflicts\n",
340: input_file_name, __progname, RRtotal);
1.1 deraadt 341: }
342:
343:
344: int
1.11 pvalchev 345: sole_reduction(int stateno)
1.1 deraadt 346: {
1.7 mpech 347: int count, ruleno;
348: action *p;
1.1 deraadt 349:
350: count = 0;
1.12 deraadt 351: ruleno = 0;
1.1 deraadt 352: for (p = parser[stateno]; p; p = p->next)
353: {
354: if (p->action_code == SHIFT && p->suppressed == 0)
355: return (0);
356: else if (p->action_code == REDUCE && p->suppressed == 0)
357: {
358: if (ruleno > 0 && p->number != ruleno)
359: return (0);
360: if (p->symbol != 1)
361: ++count;
362: ruleno = p->number;
363: }
364: }
365:
366: if (count == 0)
367: return (0);
368: return (ruleno);
369: }
370:
371:
1.6 pvalchev 372: void
1.11 pvalchev 373: defreds(void)
1.1 deraadt 374: {
1.7 mpech 375: int i;
1.1 deraadt 376:
377: defred = NEW2(nstates, short);
378: for (i = 0; i < nstates; i++)
379: defred[i] = sole_reduction(i);
380: }
1.12 deraadt 381:
1.6 pvalchev 382: void
1.11 pvalchev 383: free_action_row(action *p)
1.1 deraadt 384: {
1.7 mpech 385: action *q;
1.1 deraadt 386:
387: while (p)
388: {
389: q = p->next;
390: FREE(p);
391: p = q;
392: }
393: }
394:
1.6 pvalchev 395: void
1.11 pvalchev 396: free_parser(void)
1.1 deraadt 397: {
1.7 mpech 398: int i;
1.1 deraadt 399:
400: for (i = 0; i < nstates; i++)
401: free_action_row(parser[i]);
402:
403: FREE(parser);
404: }
![[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