Annotation of src/usr.bin/yacc/mkpar.c, Revision 1.15
1.15 ! nicm 1: /* $OpenBSD: mkpar.c,v 1.14 2009/10/27 23:59:50 deraadt 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:
1.15 ! nicm 216: rules_used = CALLOC(nrules, sizeof(short));
! 217: if (rules_used == NULL) no_space();
1.1 deraadt 218:
219: for (i = 0; i < nstates; ++i)
220: {
221: for (p = parser[i]; p; p = p->next)
222: {
223: if (p->action_code == REDUCE && p->suppressed == 0)
224: rules_used[p->number] = 1;
225: }
226: }
227:
228: nunused = 0;
229: for (i = 3; i < nrules; ++i)
230: if (!rules_used[i]) ++nunused;
231:
1.6 pvalchev 232: if (nunused) {
1.1 deraadt 233: if (nunused == 1)
1.5 millert 234: fprintf(stderr, "%s: 1 rule never reduced\n", __progname);
1.1 deraadt 235: else
1.5 millert 236: fprintf(stderr, "%s: %d rules never reduced\n", __progname,
237: nunused);
1.6 pvalchev 238: }
1.1 deraadt 239: }
240:
241:
1.6 pvalchev 242: void
1.11 pvalchev 243: remove_conflicts(void)
1.1 deraadt 244: {
1.7 mpech 245: int i;
246: int symbol;
1.13 pvalchev 247: action *p, *pref = NULL;
1.1 deraadt 248:
249: SRtotal = 0;
250: RRtotal = 0;
251: SRconflicts = NEW2(nstates, short);
252: RRconflicts = NEW2(nstates, short);
253: for (i = 0; i < nstates; i++)
254: {
255: SRcount = 0;
256: RRcount = 0;
257: symbol = -1;
258: for (p = parser[i]; p; p = p->next)
259: {
260: if (p->symbol != symbol)
261: {
262: pref = p;
263: symbol = p->symbol;
264: }
265: else if (i == final_state && symbol == 0)
266: {
267: SRcount++;
268: p->suppressed = 1;
269: }
270: else if (pref->action_code == SHIFT)
271: {
272: if (pref->prec > 0 && p->prec > 0)
273: {
274: if (pref->prec < p->prec)
275: {
276: pref->suppressed = 2;
277: pref = p;
278: }
279: else if (pref->prec > p->prec)
280: {
281: p->suppressed = 2;
282: }
283: else if (pref->assoc == LEFT)
284: {
285: pref->suppressed = 2;
286: pref = p;
287: }
288: else if (pref->assoc == RIGHT)
289: {
290: p->suppressed = 2;
291: }
292: else
293: {
294: pref->suppressed = 2;
295: p->suppressed = 2;
296: }
297: }
298: else
299: {
300: SRcount++;
301: p->suppressed = 1;
302: }
303: }
304: else
305: {
306: RRcount++;
307: p->suppressed = 1;
308: }
309: }
310: SRtotal += SRcount;
311: RRtotal += RRcount;
312: SRconflicts[i] = SRcount;
313: RRconflicts[i] = RRcount;
314: }
315: }
316:
317:
1.6 pvalchev 318: void
1.11 pvalchev 319: total_conflicts(void)
1.1 deraadt 320: {
1.2 etheisen 321: /* Warn if s/r != expect or if any r/r */
322: if ((SRtotal != SRexpect) || RRtotal)
323: {
324: if (SRtotal == 1)
1.9 deraadt 325: fprintf(stderr, "%s: %s finds 1 shift/reduce conflict\n",
326: input_file_name, __progname);
1.2 etheisen 327: else if (SRtotal > 1)
1.9 deraadt 328: fprintf(stderr, "%s: %s finds %d shift/reduce conflicts\n",
329: input_file_name, __progname, SRtotal);
1.2 etheisen 330: }
1.1 deraadt 331:
332: if (RRtotal == 1)
1.9 deraadt 333: fprintf(stderr, "%s: %s finds 1 reduce/reduce conflict\n",
334: input_file_name, __progname);
1.1 deraadt 335: else if (RRtotal > 1)
1.9 deraadt 336: fprintf(stderr, "%s: %s finds %d reduce/reduce conflicts\n",
337: input_file_name, __progname, RRtotal);
1.1 deraadt 338: }
339:
340:
341: int
1.11 pvalchev 342: sole_reduction(int stateno)
1.1 deraadt 343: {
1.7 mpech 344: int count, ruleno;
345: action *p;
1.1 deraadt 346:
347: count = 0;
1.12 deraadt 348: ruleno = 0;
1.1 deraadt 349: for (p = parser[stateno]; p; p = p->next)
350: {
351: if (p->action_code == SHIFT && p->suppressed == 0)
352: return (0);
353: else if (p->action_code == REDUCE && p->suppressed == 0)
354: {
355: if (ruleno > 0 && p->number != ruleno)
356: return (0);
357: if (p->symbol != 1)
358: ++count;
359: ruleno = p->number;
360: }
361: }
362:
363: if (count == 0)
364: return (0);
365: return (ruleno);
366: }
367:
368:
1.6 pvalchev 369: void
1.11 pvalchev 370: defreds(void)
1.1 deraadt 371: {
1.7 mpech 372: int i;
1.1 deraadt 373:
374: defred = NEW2(nstates, short);
375: for (i = 0; i < nstates; i++)
376: defred[i] = sole_reduction(i);
377: }
1.12 deraadt 378:
1.6 pvalchev 379: void
1.11 pvalchev 380: free_action_row(action *p)
1.1 deraadt 381: {
1.7 mpech 382: action *q;
1.1 deraadt 383:
384: while (p)
385: {
386: q = p->next;
387: FREE(p);
388: p = q;
389: }
390: }
391:
1.6 pvalchev 392: void
1.11 pvalchev 393: free_parser(void)
1.1 deraadt 394: {
1.7 mpech 395: int i;
1.1 deraadt 396:
397: for (i = 0; i < nstates; i++)
398: free_action_row(parser[i]);
399:
400: FREE(parser);
401: }
![[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