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