![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to conflicts.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / GNUtools / bison|
Return to conflicts.c CVS log | Up to [Apple XNU] / GNUtools / bison |
1.1 root 1: /* Find and resolve or report look-ahead conflicts for bison,
2: Copyright (C) 1984, 1989 Free Software Foundation, Inc.
3:
4: This file is part of Bison, the GNU Compiler Compiler.
5:
6: Bison is free software; you can redistribute it and/or modify
7: it under the terms of the GNU General Public License as published by
8: the Free Software Foundation; either version 2, or (at your option)
9: any later version.
10:
11: Bison is distributed in the hope that it will be useful,
12: but WITHOUT ANY WARRANTY; without even the implied warranty of
13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14: GNU General Public License for more details.
15:
16: You should have received a copy of the GNU General Public License
17: along with Bison; see the file COPYING. If not, write to
18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
19:
20: #ifdef _AIX
21: #pragma alloca
22: #endif
23: #include <stdio.h>
24: #include "system.h"
25: #include "machine.h"
26: #include "new.h"
27: #include "files.h"
28: #include "gram.h"
29: #include "state.h"
30:
31:
32: #ifdef __GNUC__
33: #ifdef alloca
34: #undef alloca
35: #endif
36: #define alloca __builtin_alloca
37: #else
38: #ifdef HAVE_ALLOCA_H
39: #include <alloca.h>
40: #else
41: #ifndef _AIX
42: extern char *alloca ();
43: #endif
44: #endif
45: #endif
46:
47: extern char **tags;
48: extern int tokensetsize;
49: extern char *consistent;
50: extern short *accessing_symbol;
51: extern shifts **shift_table;
52: extern unsigned *LA;
53: extern short *LAruleno;
54: extern short *lookaheads;
55: extern int verboseflag;
56:
57: void set_conflicts();
58: void resolve_sr_conflict();
59: void flush_shift();
60: void log_resolution();
61: void total_conflicts();
62: void count_sr_conflicts();
63: void count_rr_conflicts();
64:
65: char any_conflicts;
66: char *conflicts;
67: errs **err_table;
68: int expected_conflicts;
69:
70:
71: static unsigned *shiftset;
72: static unsigned *lookaheadset;
73: static int src_total;
74: static int rrc_total;
75: static int src_count;
76: static int rrc_count;
77:
78:
79: void
80: initialize_conflicts()
81: {
82: register int i;
83: /* register errs *sp; JF unused */
84:
85: conflicts = NEW2(nstates, char);
86: shiftset = NEW2(tokensetsize, unsigned);
87: lookaheadset = NEW2(tokensetsize, unsigned);
88:
89: err_table = NEW2(nstates, errs *);
90:
91: any_conflicts = 0;
92:
93: for (i = 0; i < nstates; i++)
94: set_conflicts(i);
95: }
96:
97:
98: void
99: set_conflicts(state)
100: int state;
101: {
102: register int i;
103: register int k;
104: register shifts *shiftp;
105: register unsigned *fp2;
106: register unsigned *fp3;
107: register unsigned *fp4;
108: register unsigned *fp1;
109: register int symbol;
110:
111: if (consistent[state]) return;
112:
113: for (i = 0; i < tokensetsize; i++)
114: lookaheadset[i] = 0;
115:
116: shiftp = shift_table[state];
117: if (shiftp)
118: {
119: k = shiftp->nshifts;
120: for (i = 0; i < k; i++)
121: {
122: symbol = accessing_symbol[shiftp->shifts[i]];
123: if (ISVAR(symbol)) break;
124: SETBIT(lookaheadset, symbol);
125: }
126: }
127:
128: k = lookaheads[state + 1];
129: fp4 = lookaheadset + tokensetsize;
130:
131: /* loop over all rules which require lookahead in this state */
132: /* first check for shift-reduce conflict, and try to resolve using precedence */
133:
134: for (i = lookaheads[state]; i < k; i++)
135: if (rprec[LAruleno[i]])
136: {
137: fp1 = LA + i * tokensetsize;
138: fp2 = fp1;
139: fp3 = lookaheadset;
140:
141: while (fp3 < fp4)
142: {
143: if (*fp2++ & *fp3++)
144: {
145: resolve_sr_conflict(state, i);
146: break;
147: }
148: }
149: }
150:
151: /* loop over all rules which require lookahead in this state */
152: /* Check for conflicts not resolved above. */
153:
154: for (i = lookaheads[state]; i < k; i++)
155: {
156: fp1 = LA + i * tokensetsize;
157: fp2 = fp1;
158: fp3 = lookaheadset;
159:
160: while (fp3 < fp4)
161: {
162: if (*fp2++ & *fp3++)
163: {
164: conflicts[state] = 1;
165: any_conflicts = 1;
166: }
167: }
168:
169: fp2 = fp1;
170: fp3 = lookaheadset;
171:
172: while (fp3 < fp4)
173: *fp3++ |= *fp2++;
174: }
175: }
176:
177:
178:
179: /* Attempt to resolve shift-reduce conflict for one rule
180: by means of precedence declarations.
181: It has already been checked that the rule has a precedence.
182: A conflict is resolved by modifying the shift or reduce tables
183: so that there is no longer a conflict. */
184:
185: void
186: resolve_sr_conflict(state, lookaheadnum)
187: int state;
188: int lookaheadnum;
189: {
190: register int i;
191: register int mask;
192: register unsigned *fp1;
193: register unsigned *fp2;
194: register int redprec;
195: /* Extra parens avoid errors on Ultrix 4.3. */
196: errs *errp = (errs *) alloca ((sizeof(errs) + ntokens * sizeof(short)));
197: short *errtokens = errp->errs;
198:
199: /* find the rule to reduce by to get precedence of reduction */
200: redprec = rprec[LAruleno[lookaheadnum]];
201:
202: mask = 1;
203: fp1 = LA + lookaheadnum * tokensetsize;
204: fp2 = lookaheadset;
205: for (i = 0; i < ntokens; i++)
206: {
207: if ((mask & *fp2 & *fp1) && sprec[i])
208: /* Shift-reduce conflict occurs for token number i
209: and it has a precedence.
210: The precedence of shifting is that of token i. */
211: {
212: if (sprec[i] < redprec)
213: {
214: if (verboseflag) log_resolution(state, lookaheadnum, i, "reduce");
215: *fp2 &= ~mask; /* flush the shift for this token */
216: flush_shift(state, i);
217: }
218: else if (sprec[i] > redprec)
219: {
220: if (verboseflag) log_resolution(state, lookaheadnum, i, "shift");
221: *fp1 &= ~mask; /* flush the reduce for this token */
222: }
223: else
224: {
225: /* Matching precedence levels.
226: For left association, keep only the reduction.
227: For right association, keep only the shift.
228: For nonassociation, keep neither. */
229:
230: switch (sassoc[i])
231: {
232:
233: case RIGHT_ASSOC:
234: if (verboseflag) log_resolution(state, lookaheadnum, i, "shift");
235: break;
236:
237: case LEFT_ASSOC:
238: if (verboseflag) log_resolution(state, lookaheadnum, i, "reduce");
239: break;
240:
241: case NON_ASSOC:
242: if (verboseflag) log_resolution(state, lookaheadnum, i, "an error");
243: break;
244: }
245:
246: if (sassoc[i] != RIGHT_ASSOC)
247: {
248: *fp2 &= ~mask; /* flush the shift for this token */
249: flush_shift(state, i);
250: }
251: if (sassoc[i] != LEFT_ASSOC)
252: {
253: *fp1 &= ~mask; /* flush the reduce for this token */
254: }
255: if (sassoc[i] == NON_ASSOC)
256: {
257: /* Record an explicit error for this token. */
258: *errtokens++ = i;
259: }
260: }
261: }
262:
263: mask <<= 1;
264: if (mask == 0)
265: {
266: mask = 1;
267: fp2++; fp1++;
268: }
269: }
270: errp->nerrs = errtokens - errp->errs;
271: if (errp->nerrs)
272: {
273: /* Some tokens have been explicitly made errors. Allocate
274: a permanent errs structure for this state, to record them. */
275: i = (char *) errtokens - (char *) errp;
276: err_table[state] = (errs *) xmalloc ((unsigned int)i);
277: bcopy (errp, err_table[state], i);
278: }
279: else
280: err_table[state] = 0;
281: }
282:
283:
284:
285: /* turn off the shift recorded for the specified token in the specified state.
286: Used when we resolve a shift-reduce conflict in favor of the reduction. */
287:
288: void
289: flush_shift(state, token)
290: int state;
291: int token;
292: {
293: register shifts *shiftp;
294: register int k, i;
295: /* register unsigned symbol; JF unused */
296:
297: shiftp = shift_table[state];
298:
299: if (shiftp)
300: {
301: k = shiftp->nshifts;
302: for (i = 0; i < k; i++)
303: {
304: if (shiftp->shifts[i] && token == accessing_symbol[shiftp->shifts[i]])
305: (shiftp->shifts[i]) = 0;
306: }
307: }
308: }
309:
310:
311: void
312: log_resolution(state, LAno, token, resolution)
313: int state, LAno, token;
314: char *resolution;
315: {
316: fprintf(foutput,
317: "Conflict in state %d between rule %d and token %s resolved as %s.\n",
318: state, LAruleno[LAno], tags[token], resolution);
319: }
320:
321:
322: void
323: conflict_log()
324: {
325: register int i;
326:
327: src_total = 0;
328: rrc_total = 0;
329:
330: for (i = 0; i < nstates; i++)
331: {
332: if (conflicts[i])
333: {
334: count_sr_conflicts(i);
335: count_rr_conflicts(i);
336: src_total += src_count;
337: rrc_total += rrc_count;
338: }
339: }
340:
341: total_conflicts();
342: }
343:
344:
345: void
346: verbose_conflict_log()
347: {
348: register int i;
349:
350: src_total = 0;
351: rrc_total = 0;
352:
353: for (i = 0; i < nstates; i++)
354: {
355: if (conflicts[i])
356: {
357: count_sr_conflicts(i);
358: count_rr_conflicts(i);
359: src_total += src_count;
360: rrc_total += rrc_count;
361:
362: fprintf(foutput, "State %d contains", i);
363:
364: if (src_count == 1)
365: fprintf(foutput, " 1 shift/reduce conflict");
366: else if (src_count > 1)
367: fprintf(foutput, " %d shift/reduce conflicts", src_count);
368:
369: if (src_count > 0 && rrc_count > 0)
370: fprintf(foutput, " and");
371:
372: if (rrc_count == 1)
373: fprintf(foutput, " 1 reduce/reduce conflict");
374: else if (rrc_count > 1)
375: fprintf(foutput, " %d reduce/reduce conflicts", rrc_count);
376:
377: putc('.', foutput);
378: putc('\n', foutput);
379: }
380: }
381:
382: total_conflicts();
383: }
384:
385:
386: void
387: total_conflicts()
388: {
389: extern int fixed_outfiles;
390:
391: if (src_total == expected_conflicts && rrc_total == 0)
392: return;
393:
394: if (fixed_outfiles)
395: {
396: /* If invoked under the name `yacc', use the output format
397: specified by POSIX. */
398: fprintf(stderr, "conflicts: ");
399: if (src_total > 0)
400: fprintf(stderr, " %d shift/reduce", src_total);
401: if (src_total > 0 && rrc_total > 0)
402: fprintf(stderr, ",");
403: if (rrc_total > 0)
404: fprintf(stderr, " %d reduce/reduce", rrc_total);
405: putc('\n', stderr);
406: }
407: else
408: {
409: fprintf(stderr, "%s contains", infile);
410:
411: if (src_total == 1)
412: fprintf(stderr, " 1 shift/reduce conflict");
413: else if (src_total > 1)
414: fprintf(stderr, " %d shift/reduce conflicts", src_total);
415:
416: if (src_total > 0 && rrc_total > 0)
417: fprintf(stderr, " and");
418:
419: if (rrc_total == 1)
420: fprintf(stderr, " 1 reduce/reduce conflict");
421: else if (rrc_total > 1)
422: fprintf(stderr, " %d reduce/reduce conflicts", rrc_total);
423:
424: putc('.', stderr);
425: putc('\n', stderr);
426: }
427: }
428:
429:
430: void
431: count_sr_conflicts(state)
432: int state;
433: {
434: register int i;
435: register int k;
436: register int mask;
437: register shifts *shiftp;
438: register unsigned *fp1;
439: register unsigned *fp2;
440: register unsigned *fp3;
441: register int symbol;
442:
443: src_count = 0;
444:
445: shiftp = shift_table[state];
446: if (!shiftp) return;
447:
448: for (i = 0; i < tokensetsize; i++)
449: {
450: shiftset[i] = 0;
451: lookaheadset[i] = 0;
452: }
453:
454: k = shiftp->nshifts;
455: for (i = 0; i < k; i++)
456: {
457: if (! shiftp->shifts[i]) continue;
458: symbol = accessing_symbol[shiftp->shifts[i]];
459: if (ISVAR(symbol)) break;
460: SETBIT(shiftset, symbol);
461: }
462:
463: k = lookaheads[state + 1];
464: fp3 = lookaheadset + tokensetsize;
465:
466: for (i = lookaheads[state]; i < k; i++)
467: {
468: fp1 = LA + i * tokensetsize;
469: fp2 = lookaheadset;
470:
471: while (fp2 < fp3)
472: *fp2++ |= *fp1++;
473: }
474:
475: fp1 = shiftset;
476: fp2 = lookaheadset;
477:
478: while (fp2 < fp3)
479: *fp2++ &= *fp1++;
480:
481: mask = 1;
482: fp2 = lookaheadset;
483: for (i = 0; i < ntokens; i++)
484: {
485: if (mask & *fp2)
486: src_count++;
487:
488: mask <<= 1;
489: if (mask == 0)
490: {
491: mask = 1;
492: fp2++;
493: }
494: }
495: }
496:
497:
498: void
499: count_rr_conflicts(state)
500: int state;
501: {
502: register int i;
503: register int j;
504: register int count;
505: register unsigned mask;
506: register unsigned *baseword;
507: register unsigned *wordp;
508: register int m;
509: register int n;
510:
511: rrc_count = 0;
512:
513: m = lookaheads[state];
514: n = lookaheads[state + 1];
515:
516: if (n - m < 2) return;
517:
518: mask = 1;
519: baseword = LA + m * tokensetsize;
520: for (i = 0; i < ntokens; i++)
521: {
522: wordp = baseword;
523:
524: count = 0;
525: for (j = m; j < n; j++)
526: {
527: if (mask & *wordp)
528: count++;
529:
530: wordp += tokensetsize;
531: }
532:
533: if (count >= 2) rrc_count++;
534:
535: mask <<= 1;
536: if (mask == 0)
537: {
538: mask = 1;
539: baseword++;
540: }
541: }
542: }
543:
544:
545: void
546: print_reductions(state)
547: int state;
548: {
549: register int i;
550: register int j;
551: register int k;
552: register unsigned *fp1;
553: register unsigned *fp2;
554: register unsigned *fp3;
555: register unsigned *fp4;
556: register int rule;
557: register int symbol;
558: register unsigned mask;
559: register int m;
560: register int n;
561: register int default_LA;
562: register int default_rule;
563: register int cmax;
564: register int count;
565: register shifts *shiftp;
566: register errs *errp;
567: int nodefault = 0;
568:
569: for (i = 0; i < tokensetsize; i++)
570: shiftset[i] = 0;
571:
572: shiftp = shift_table[state];
573: if (shiftp)
574: {
575: k = shiftp->nshifts;
576: for (i = 0; i < k; i++)
577: {
578: if (! shiftp->shifts[i]) continue;
579: symbol = accessing_symbol[shiftp->shifts[i]];
580: if (ISVAR(symbol)) break;
581: /* if this state has a shift for the error token,
582: don't use a default rule. */
583: if (symbol == error_token_number) nodefault = 1;
584: SETBIT(shiftset, symbol);
585: }
586: }
587:
588: errp = err_table[state];
589: if (errp)
590: {
591: k = errp->nerrs;
592: for (i = 0; i < k; i++)
593: {
594: if (! errp->errs[i]) continue;
595: symbol = errp->errs[i];
596: SETBIT(shiftset, symbol);
597: }
598: }
599:
600: m = lookaheads[state];
601: n = lookaheads[state + 1];
602:
603: if (n - m == 1 && ! nodefault)
604: {
605: default_rule = LAruleno[m];
606:
607: fp1 = LA + m * tokensetsize;
608: fp2 = shiftset;
609: fp3 = lookaheadset;
610: fp4 = lookaheadset + tokensetsize;
611:
612: while (fp3 < fp4)
613: *fp3++ = *fp1++ & *fp2++;
614:
615: mask = 1;
616: fp3 = lookaheadset;
617:
618: for (i = 0; i < ntokens; i++)
619: {
620: if (mask & *fp3)
621: fprintf(foutput, " %-4s\t[reduce using rule %d (%s)]\n",
622: tags[i], default_rule, tags[rlhs[default_rule]]);
623:
624: mask <<= 1;
625: if (mask == 0)
626: {
627: mask = 1;
628: fp3++;
629: }
630: }
631:
632: fprintf(foutput, " $default\treduce using rule %d (%s)\n\n",
633: default_rule, tags[rlhs[default_rule]]);
634: }
635: else if (n - m >= 1)
636: {
637: cmax = 0;
638: default_LA = -1;
639: fp4 = lookaheadset + tokensetsize;
640:
641: if (! nodefault)
642: for (i = m; i < n; i++)
643: {
644: fp1 = LA + i * tokensetsize;
645: fp2 = shiftset;
646: fp3 = lookaheadset;
647:
648: while (fp3 < fp4)
649: *fp3++ = *fp1++ & ( ~ (*fp2++));
650:
651: count = 0;
652: mask = 1;
653: fp3 = lookaheadset;
654: for (j = 0; j < ntokens; j++)
655: {
656: if (mask & *fp3)
657: count++;
658:
659: mask <<= 1;
660: if (mask == 0)
661: {
662: mask = 1;
663: fp3++;
664: }
665: }
666:
667: if (count > cmax)
668: {
669: cmax = count;
670: default_LA = i;
671: default_rule = LAruleno[i];
672: }
673:
674: fp2 = shiftset;
675: fp3 = lookaheadset;
676:
677: while (fp3 < fp4)
678: *fp2++ |= *fp3++;
679: }
680:
681: for (i = 0; i < tokensetsize; i++)
682: shiftset[i] = 0;
683:
684: if (shiftp)
685: {
686: k = shiftp->nshifts;
687: for (i = 0; i < k; i++)
688: {
689: if (! shiftp->shifts[i]) continue;
690: symbol = accessing_symbol[shiftp->shifts[i]];
691: if (ISVAR(symbol)) break;
692: SETBIT(shiftset, symbol);
693: }
694: }
695:
696: mask = 1;
697: fp1 = LA + m * tokensetsize;
698: fp2 = shiftset;
699: for (i = 0; i < ntokens; i++)
700: {
701: int defaulted = 0;
702:
703: if (mask & *fp2)
704: count = 1;
705: else
706: count = 0;
707:
708: fp3 = fp1;
709: for (j = m; j < n; j++)
710: {
711: if (mask & *fp3)
712: {
713: if (count == 0)
714: {
715: if (j != default_LA)
716: {
717: rule = LAruleno[j];
718: fprintf(foutput, " %-4s\treduce using rule %d (%s)\n",
719: tags[i], rule, tags[rlhs[rule]]);
720: }
721: else defaulted = 1;
722:
723: count++;
724: }
725: else
726: {
727: if (defaulted)
728: {
729: rule = LAruleno[default_LA];
730: fprintf(foutput, " %-4s\treduce using rule %d (%s)\n",
731: tags[i], rule, tags[rlhs[rule]]);
732: defaulted = 0;
733: }
734: rule = LAruleno[j];
735: fprintf(foutput, " %-4s\t[reduce using rule %d (%s)]\n",
736: tags[i], rule, tags[rlhs[rule]]);
737: }
738: }
739:
740: fp3 += tokensetsize;
741: }
742:
743: mask <<= 1;
744: if (mask == 0)
745: {
746: mask = 1;
747: /* This used to be fp1, but I think fp2 is right
748: because fp2 is where the words are fetched to test with mask
749: in this loop. */
750: fp2++;
751: }
752: }
753:
754: if (default_LA >= 0)
755: {
756: fprintf(foutput, " $default\treduce using rule %d (%s)\n",
757: default_rule, tags[rlhs[default_rule]]);
758: }
759:
760: putc('\n', foutput);
761: }
762: }
763:
764:
765: void
766: finalize_conflicts()
767: {
768: FREE(conflicts);
769: FREE(shiftset);
770: FREE(lookaheadset);
771: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.