![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to mkpar.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / pgrm / yacc|
Return to mkpar.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / pgrm / yacc |
1.1 root 1: /*
2: * Copyright (c) 1989 The Regents of the University of California.
3: * All rights reserved.
4: *
5: * This code is derived from software contributed to Berkeley by
6: * Robert Paul Corbett.
7: *
8: * Redistribution and use in source and binary forms are permitted provided
9: * that: (1) source distributions retain this entire copyright notice and
10: * comment, and (2) distributions including binaries display the following
11: * acknowledgement: ``This product includes software developed by the
12: * University of California, Berkeley and its contributors'' in the
13: * documentation or other materials provided with the distribution and in
14: * all advertising materials mentioning features or use of this software.
15: * Neither the name of the University nor the names of its contributors may
16: * be used to endorse or promote products derived from this software without
17: * specific prior written permission.
18: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
19: * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
20: * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
21: */
22:
23: #ifndef lint
24: static char sccsid[] = "@(#)mkpar.c 5.2 (Berkeley) 6/1/90";
25: #endif /* not lint */
26:
27: #include "defs.h"
28:
29: action **parser;
30: int SRtotal;
31: int RRtotal;
32: short *SRconflicts;
33: short *RRconflicts;
34: short *defred;
35: short *rules_used;
36: short nunused;
37: short final_state;
38:
39: static int SRcount;
40: static int RRcount;
41:
42: extern action *parse_actions();
43: extern action *get_shifts();
44: extern action *add_reductions();
45: extern action *add_reduce();
46:
47:
48: make_parser()
49: {
50: register int i;
51:
52: parser = NEW2(nstates, action *);
53: for (i = 0; i < nstates; i++)
54: parser[i] = parse_actions(i);
55:
56: find_final_state();
57: remove_conflicts();
58: unused_rules();
59: if (SRtotal + RRtotal > 0) total_conflicts();
60: defreds();
61: }
62:
63:
64: action *
65: parse_actions(stateno)
66: register int stateno;
67: {
68: register action *actions;
69:
70: actions = get_shifts(stateno);
71: actions = add_reductions(stateno, actions);
72: return (actions);
73: }
74:
75:
76: action *
77: get_shifts(stateno)
78: int stateno;
79: {
80: register action *actions, *temp;
81: register shifts *sp;
82: register short *to_state;
83: register int i, k;
84: register int symbol;
85:
86: actions = 0;
87: sp = shift_table[stateno];
88: if (sp)
89: {
90: to_state = sp->shift;
91: for (i = sp->nshifts - 1; i >= 0; i--)
92: {
93: k = to_state[i];
94: symbol = accessing_symbol[k];
95: if (ISTOKEN(symbol))
96: {
97: temp = NEW(action);
98: temp->next = actions;
99: temp->symbol = symbol;
100: temp->number = k;
101: temp->prec = symbol_prec[symbol];
102: temp->action_code = SHIFT;
103: temp->assoc = symbol_assoc[symbol];
104: actions = temp;
105: }
106: }
107: }
108: return (actions);
109: }
110:
111: action *
112: add_reductions(stateno, actions)
113: int stateno;
114: register action *actions;
115: {
116: register int i, j, m, n;
117: register int ruleno, tokensetsize;
118: register unsigned *rowp;
119:
120: tokensetsize = WORDSIZE(ntokens);
121: m = lookaheads[stateno];
122: n = lookaheads[stateno + 1];
123: for (i = m; i < n; i++)
124: {
125: ruleno = LAruleno[i];
126: rowp = LA + i * tokensetsize;
127: for (j = ntokens - 1; j >= 0; j--)
128: {
129: if (BIT(rowp, j))
130: actions = add_reduce(actions, ruleno, j);
131: }
132: }
133: return (actions);
134: }
135:
136:
137: action *
138: add_reduce(actions, ruleno, symbol)
139: register action *actions;
140: register int ruleno, symbol;
141: {
142: register action *temp, *prev, *next;
143:
144: prev = 0;
145: for (next = actions; next && next->symbol < symbol; next = next->next)
146: prev = next;
147:
148: while (next && next->symbol == symbol && next->action_code == SHIFT)
149: {
150: prev = next;
151: next = next->next;
152: }
153:
154: while (next && next->symbol == symbol &&
155: next->action_code == REDUCE && next->number < ruleno)
156: {
157: prev = next;
158: next = next->next;
159: }
160:
161: temp = NEW(action);
162: temp->next = next;
163: temp->symbol = symbol;
164: temp->number = ruleno;
165: temp->prec = rprec[ruleno];
166: temp->action_code = REDUCE;
167: temp->assoc = rassoc[ruleno];
168:
169: if (prev)
170: prev->next = temp;
171: else
172: actions = temp;
173:
174: return (actions);
175: }
176:
177:
178: find_final_state()
179: {
180: register int goal, i;
181: register short *to_state;
182: register shifts *p;
183:
184: p = shift_table[0];
185: to_state = p->shift;
186: goal = ritem[1];
187: for (i = p->nshifts - 1; i >= 0; --i)
188: {
189: final_state = to_state[i];
190: if (accessing_symbol[final_state] == goal) break;
191: }
192: }
193:
194:
195: unused_rules()
196: {
197: register int i;
198: register action *p;
199:
200: rules_used = (short *) MALLOC(nrules*sizeof(short));
201: if (rules_used == 0) no_space();
202:
203: for (i = 0; i < nrules; ++i)
204: rules_used[i] = 0;
205:
206: for (i = 0; i < nstates; ++i)
207: {
208: for (p = parser[i]; p; p = p->next)
209: {
210: if (p->action_code == REDUCE && p->suppressed == 0)
211: rules_used[p->number] = 1;
212: }
213: }
214:
215: nunused = 0;
216: for (i = 3; i < nrules; ++i)
217: if (!rules_used[i]) ++nunused;
218:
219: if (nunused)
220: if (nunused == 1)
221: fprintf(stderr, "%s: 1 rule never reduced\n", myname);
222: else
223: fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
224: }
225:
226:
227: remove_conflicts()
228: {
229: register int i;
230: register int symbol;
231: register action *p, *q;
232:
233: SRtotal = 0;
234: RRtotal = 0;
235: SRconflicts = NEW2(nstates, short);
236: RRconflicts = NEW2(nstates, short);
237: for (i = 0; i < nstates; i++)
238: {
239: SRcount = 0;
240: RRcount = 0;
241: for (p = parser[i]; p; p = q->next)
242: {
243: symbol = p->symbol;
244: q = p;
245: while (q->next && q->next->symbol == symbol)
246: q = q->next;
247: if (i == final_state && symbol == 0)
248: end_conflicts(p, q);
249: else if (p != q)
250: resolve_conflicts(p, q);
251: }
252: SRtotal += SRcount;
253: RRtotal += RRcount;
254: SRconflicts[i] = SRcount;
255: RRconflicts[i] = RRcount;
256: }
257: }
258:
259:
260: end_conflicts(p, q)
261: register action *p, *q;
262: {
263: for (;;)
264: {
265: SRcount++;
266: p->suppressed = 1;
267: if (p == q) break;
268: p = p->next;
269: }
270: }
271:
272:
273: resolve_conflicts(first, last)
274: register action *first, *last;
275: {
276: register action *p;
277: register int count;
278:
279: count = 1;
280: for (p = first; p != last; p = p->next)
281: ++count;
282: assert(count > 1);
283:
284: if (first->action_code == SHIFT && count == 2 &&
285: first->prec > 0 && last->prec > 0)
286: {
287: if (first->prec == last->prec)
288: {
289: if (first->assoc == LEFT)
290: first->suppressed = 2;
291: else if (first->assoc == RIGHT)
292: last->suppressed = 2;
293: else
294: {
295: first->suppressed = 2;
296: last->suppressed = 2;
297: first->action_code = ERROR;
298: last->action_code = ERROR;
299: }
300: }
301: else if (first->prec < last->prec)
302: first->suppressed = 2;
303: else
304: last->suppressed = 2;
305: }
306: else
307: {
308: if (first->action_code == SHIFT)
309: SRcount += (count - 1);
310: else
311: RRcount += (count - 1);
312: for (p = first; p != last; p = p->next, p->suppressed = 1)
313: continue;
314: }
315: }
316:
317:
318: total_conflicts()
319: {
320: fprintf(stderr, "%s: ", myname);
321: if (SRtotal == 1)
322: fprintf(stderr, "1 shift/reduce conflict");
323: else if (SRtotal > 1)
324: fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
325:
326: if (SRtotal && RRtotal)
327: fprintf(stderr, ", ");
328:
329: if (RRtotal == 1)
330: fprintf(stderr, "1 reduce/reduce conflict");
331: else if (RRtotal > 1)
332: fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
333:
334: fprintf(stderr, ".\n");
335: }
336:
337:
338: int
339: sole_reduction(stateno)
340: int stateno;
341: {
342: register int count, ruleno;
343: register action *p;
344:
345: count = 0;
346: ruleno = 0;
347: for (p = parser[stateno]; p; p = p->next)
348: {
349: if (p->action_code == SHIFT && p->suppressed == 0)
350: return (0);
351: else if (p->action_code == REDUCE && p->suppressed == 0)
352: {
353: if (ruleno > 0 && p->number != ruleno)
354: return (0);
355: if (p->symbol != 1)
356: ++count;
357: ruleno = p->number;
358: }
359: }
360:
361: if (count == 0)
362: return (0);
363: return (ruleno);
364: }
365:
366:
367: defreds()
368: {
369: register int i;
370:
371: defred = NEW2(nstates, short);
372: for (i = 0; i < nstates; i++)
373: defred[i] = sole_reduction(i);
374: }
375:
376: free_action_row(p)
377: register action *p;
378: {
379: register action *q;
380:
381: while (p)
382: {
383: q = p->next;
384: FREE(p);
385: p = q;
386: }
387: }
388:
389: free_parser()
390: {
391: register int i;
392:
393: for (i = 0; i < nstates; i++)
394: free_action_row(parser[i]);
395:
396: FREE(parser);
397: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.