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