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