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