1268899Sbapt/* $Id: mkpar.c,v 1.14 2014/04/01 23:05:37 tom Exp $ */ 2234949Sbapt 3234949Sbapt#include "defs.h" 4234949Sbapt 5268899Sbapt#define NotSuppressed(p) ((p)->suppressed == 0) 6268899Sbapt 7268899Sbapt#if defined(YYBTYACC) 8268899Sbapt#define MaySuppress(p) ((backtrack ? ((p)->suppressed <= 1) : (p)->suppressed == 0)) 9268899Sbapt /* suppress the preferred action => enable backtracking */ 10268899Sbapt#define StartBacktrack(p) if (backtrack && (p) != NULL && NotSuppressed(p)) (p)->suppressed = 1 11268899Sbapt#else 12268899Sbapt#define MaySuppress(p) ((p)->suppressed == 0) 13268899Sbapt#define StartBacktrack(p) /*nothing */ 14268899Sbapt#endif 15268899Sbapt 16234949Sbaptstatic action *add_reduce(action *actions, int ruleno, int symbol); 17234949Sbaptstatic action *add_reductions(int stateno, action *actions); 18234949Sbaptstatic action *get_shifts(int stateno); 19234949Sbaptstatic action *parse_actions(int stateno); 20234949Sbaptstatic int sole_reduction(int stateno); 21234949Sbaptstatic void defreds(void); 22234949Sbaptstatic void find_final_state(void); 23234949Sbaptstatic void free_action_row(action *p); 24234949Sbaptstatic void remove_conflicts(void); 25234949Sbaptstatic void total_conflicts(void); 26234949Sbaptstatic void unused_rules(void); 27234949Sbapt 28234949Sbaptaction **parser; 29234949Sbapt 30234949Sbaptint SRexpect; 31234949Sbaptint RRexpect; 32234949Sbapt 33234949Sbaptint SRtotal; 34234949Sbaptint RRtotal; 35234949Sbapt 36234949SbaptValue_t *SRconflicts; 37234949SbaptValue_t *RRconflicts; 38234949SbaptValue_t *defred; 39234949SbaptValue_t *rules_used; 40234949SbaptValue_t nunused; 41234949SbaptValue_t final_state; 42234949Sbapt 43234949Sbaptstatic Value_t SRcount; 44234949Sbaptstatic Value_t RRcount; 45234949Sbapt 46234949Sbaptvoid 47234949Sbaptmake_parser(void) 48234949Sbapt{ 49234949Sbapt int i; 50234949Sbapt 51234949Sbapt parser = NEW2(nstates, action *); 52234949Sbapt for (i = 0; i < nstates; i++) 53234949Sbapt parser[i] = parse_actions(i); 54234949Sbapt 55234949Sbapt find_final_state(); 56234949Sbapt remove_conflicts(); 57234949Sbapt unused_rules(); 58234949Sbapt if (SRtotal + RRtotal > 0) 59234949Sbapt total_conflicts(); 60234949Sbapt defreds(); 61234949Sbapt} 62234949Sbapt 63234949Sbaptstatic action * 64234949Sbaptparse_actions(int stateno) 65234949Sbapt{ 66234949Sbapt action *actions; 67234949Sbapt 68234949Sbapt actions = get_shifts(stateno); 69234949Sbapt actions = add_reductions(stateno, actions); 70234949Sbapt return (actions); 71234949Sbapt} 72234949Sbapt 73234949Sbaptstatic action * 74234949Sbaptget_shifts(int stateno) 75234949Sbapt{ 76234949Sbapt action *actions, *temp; 77234949Sbapt shifts *sp; 78234949Sbapt Value_t *to_state2; 79234949Sbapt Value_t i, k; 80234949Sbapt Value_t symbol; 81234949Sbapt 82234949Sbapt actions = 0; 83234949Sbapt sp = shift_table[stateno]; 84234949Sbapt if (sp) 85234949Sbapt { 86234949Sbapt to_state2 = sp->shift; 87234949Sbapt for (i = (Value_t) (sp->nshifts - 1); i >= 0; i--) 88234949Sbapt { 89234949Sbapt k = to_state2[i]; 90234949Sbapt symbol = accessing_symbol[k]; 91234949Sbapt if (ISTOKEN(symbol)) 92234949Sbapt { 93234949Sbapt temp = NEW(action); 94234949Sbapt temp->next = actions; 95234949Sbapt temp->symbol = symbol; 96234949Sbapt temp->number = k; 97234949Sbapt temp->prec = symbol_prec[symbol]; 98234949Sbapt temp->action_code = SHIFT; 99234949Sbapt temp->assoc = symbol_assoc[symbol]; 100234949Sbapt actions = temp; 101234949Sbapt } 102234949Sbapt } 103234949Sbapt } 104234949Sbapt return (actions); 105234949Sbapt} 106234949Sbapt 107234949Sbaptstatic action * 108234949Sbaptadd_reductions(int stateno, action *actions) 109234949Sbapt{ 110234949Sbapt int i, j, m, n; 111234949Sbapt int ruleno, tokensetsize; 112234949Sbapt unsigned *rowp; 113234949Sbapt 114234949Sbapt tokensetsize = WORDSIZE(ntokens); 115234949Sbapt m = lookaheads[stateno]; 116234949Sbapt n = lookaheads[stateno + 1]; 117234949Sbapt for (i = m; i < n; i++) 118234949Sbapt { 119234949Sbapt ruleno = LAruleno[i]; 120234949Sbapt rowp = LA + i * tokensetsize; 121234949Sbapt for (j = ntokens - 1; j >= 0; j--) 122234949Sbapt { 123234949Sbapt if (BIT(rowp, j)) 124234949Sbapt actions = add_reduce(actions, ruleno, j); 125234949Sbapt } 126234949Sbapt } 127234949Sbapt return (actions); 128234949Sbapt} 129234949Sbapt 130234949Sbaptstatic action * 131234949Sbaptadd_reduce(action *actions, 132234949Sbapt int ruleno, 133234949Sbapt int symbol) 134234949Sbapt{ 135234949Sbapt action *temp, *prev, *next; 136234949Sbapt 137234949Sbapt prev = 0; 138234949Sbapt for (next = actions; next && next->symbol < symbol; next = next->next) 139234949Sbapt prev = next; 140234949Sbapt 141234949Sbapt while (next && next->symbol == symbol && next->action_code == SHIFT) 142234949Sbapt { 143234949Sbapt prev = next; 144234949Sbapt next = next->next; 145234949Sbapt } 146234949Sbapt 147234949Sbapt while (next && next->symbol == symbol && 148234949Sbapt next->action_code == REDUCE && next->number < ruleno) 149234949Sbapt { 150234949Sbapt prev = next; 151234949Sbapt next = next->next; 152234949Sbapt } 153234949Sbapt 154234949Sbapt temp = NEW(action); 155234949Sbapt temp->next = next; 156234949Sbapt temp->symbol = (Value_t) symbol; 157234949Sbapt temp->number = (Value_t) ruleno; 158234949Sbapt temp->prec = rprec[ruleno]; 159234949Sbapt temp->action_code = REDUCE; 160234949Sbapt temp->assoc = rassoc[ruleno]; 161234949Sbapt 162234949Sbapt if (prev) 163234949Sbapt prev->next = temp; 164234949Sbapt else 165234949Sbapt actions = temp; 166234949Sbapt 167234949Sbapt return (actions); 168234949Sbapt} 169234949Sbapt 170234949Sbaptstatic void 171234949Sbaptfind_final_state(void) 172234949Sbapt{ 173234949Sbapt int goal, i; 174234949Sbapt Value_t *to_state2; 175234949Sbapt shifts *p; 176234949Sbapt 177234949Sbapt p = shift_table[0]; 178234949Sbapt to_state2 = p->shift; 179234949Sbapt goal = ritem[1]; 180234949Sbapt for (i = p->nshifts - 1; i >= 0; --i) 181234949Sbapt { 182234949Sbapt final_state = to_state2[i]; 183234949Sbapt if (accessing_symbol[final_state] == goal) 184234949Sbapt break; 185234949Sbapt } 186234949Sbapt} 187234949Sbapt 188234949Sbaptstatic void 189234949Sbaptunused_rules(void) 190234949Sbapt{ 191234949Sbapt int i; 192234949Sbapt action *p; 193234949Sbapt 194240517Sbapt rules_used = TMALLOC(Value_t, nrules); 195234949Sbapt NO_SPACE(rules_used); 196234949Sbapt 197234949Sbapt for (i = 0; i < nrules; ++i) 198234949Sbapt rules_used[i] = 0; 199234949Sbapt 200234949Sbapt for (i = 0; i < nstates; ++i) 201234949Sbapt { 202234949Sbapt for (p = parser[i]; p; p = p->next) 203234949Sbapt { 204268899Sbapt if ((p->action_code == REDUCE) && MaySuppress(p)) 205234949Sbapt rules_used[p->number] = 1; 206234949Sbapt } 207234949Sbapt } 208234949Sbapt 209234949Sbapt nunused = 0; 210234949Sbapt for (i = 3; i < nrules; ++i) 211234949Sbapt if (!rules_used[i]) 212234949Sbapt ++nunused; 213234949Sbapt 214234949Sbapt if (nunused) 215234949Sbapt { 216234949Sbapt if (nunused == 1) 217234949Sbapt fprintf(stderr, "%s: 1 rule never reduced\n", myname); 218234949Sbapt else 219234949Sbapt fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused); 220234949Sbapt } 221234949Sbapt} 222234949Sbapt 223234949Sbaptstatic void 224234949Sbaptremove_conflicts(void) 225234949Sbapt{ 226234949Sbapt int i; 227234949Sbapt int symbol; 228234949Sbapt action *p, *pref = 0; 229234949Sbapt 230234949Sbapt SRtotal = 0; 231234949Sbapt RRtotal = 0; 232234949Sbapt SRconflicts = NEW2(nstates, Value_t); 233234949Sbapt RRconflicts = NEW2(nstates, Value_t); 234234949Sbapt for (i = 0; i < nstates; i++) 235234949Sbapt { 236234949Sbapt SRcount = 0; 237234949Sbapt RRcount = 0; 238234949Sbapt symbol = -1; 239268899Sbapt#if defined(YYBTYACC) 240268899Sbapt pref = NULL; 241268899Sbapt#endif 242234949Sbapt for (p = parser[i]; p; p = p->next) 243234949Sbapt { 244234949Sbapt if (p->symbol != symbol) 245234949Sbapt { 246268899Sbapt /* the first parse action for each symbol is the preferred action */ 247234949Sbapt pref = p; 248234949Sbapt symbol = p->symbol; 249234949Sbapt } 250268899Sbapt /* following conditions handle multiple, i.e., conflicting, parse actions */ 251234949Sbapt else if (i == final_state && symbol == 0) 252234949Sbapt { 253234949Sbapt SRcount++; 254234949Sbapt p->suppressed = 1; 255268899Sbapt StartBacktrack(pref); 256234949Sbapt } 257234949Sbapt else if (pref != 0 && pref->action_code == SHIFT) 258234949Sbapt { 259234949Sbapt if (pref->prec > 0 && p->prec > 0) 260234949Sbapt { 261234949Sbapt if (pref->prec < p->prec) 262234949Sbapt { 263234949Sbapt pref->suppressed = 2; 264234949Sbapt pref = p; 265234949Sbapt } 266234949Sbapt else if (pref->prec > p->prec) 267234949Sbapt { 268234949Sbapt p->suppressed = 2; 269234949Sbapt } 270234949Sbapt else if (pref->assoc == LEFT) 271234949Sbapt { 272234949Sbapt pref->suppressed = 2; 273234949Sbapt pref = p; 274234949Sbapt } 275234949Sbapt else if (pref->assoc == RIGHT) 276234949Sbapt { 277234949Sbapt p->suppressed = 2; 278234949Sbapt } 279234949Sbapt else 280234949Sbapt { 281234949Sbapt pref->suppressed = 2; 282234949Sbapt p->suppressed = 2; 283234949Sbapt } 284234949Sbapt } 285234949Sbapt else 286234949Sbapt { 287234949Sbapt SRcount++; 288234949Sbapt p->suppressed = 1; 289268899Sbapt StartBacktrack(pref); 290234949Sbapt } 291234949Sbapt } 292234949Sbapt else 293234949Sbapt { 294234949Sbapt RRcount++; 295234949Sbapt p->suppressed = 1; 296268899Sbapt StartBacktrack(pref); 297234949Sbapt } 298234949Sbapt } 299234949Sbapt SRtotal += SRcount; 300234949Sbapt RRtotal += RRcount; 301234949Sbapt SRconflicts[i] = SRcount; 302234949Sbapt RRconflicts[i] = RRcount; 303234949Sbapt } 304234949Sbapt} 305234949Sbapt 306234949Sbaptstatic void 307234949Sbapttotal_conflicts(void) 308234949Sbapt{ 309234949Sbapt fprintf(stderr, "%s: ", myname); 310234949Sbapt if (SRtotal == 1) 311234949Sbapt fprintf(stderr, "1 shift/reduce conflict"); 312234949Sbapt else if (SRtotal > 1) 313234949Sbapt fprintf(stderr, "%d shift/reduce conflicts", SRtotal); 314234949Sbapt 315234949Sbapt if (SRtotal && RRtotal) 316234949Sbapt fprintf(stderr, ", "); 317234949Sbapt 318234949Sbapt if (RRtotal == 1) 319234949Sbapt fprintf(stderr, "1 reduce/reduce conflict"); 320234949Sbapt else if (RRtotal > 1) 321234949Sbapt fprintf(stderr, "%d reduce/reduce conflicts", RRtotal); 322234949Sbapt 323234949Sbapt fprintf(stderr, ".\n"); 324234949Sbapt 325234949Sbapt if (SRexpect >= 0 && SRtotal != SRexpect) 326234949Sbapt { 327234949Sbapt fprintf(stderr, "%s: ", myname); 328234949Sbapt fprintf(stderr, "expected %d shift/reduce conflict%s.\n", 329234949Sbapt SRexpect, PLURAL(SRexpect)); 330234949Sbapt exit_code = EXIT_FAILURE; 331234949Sbapt } 332234949Sbapt if (RRexpect >= 0 && RRtotal != RRexpect) 333234949Sbapt { 334234949Sbapt fprintf(stderr, "%s: ", myname); 335234949Sbapt fprintf(stderr, "expected %d reduce/reduce conflict%s.\n", 336234949Sbapt RRexpect, PLURAL(RRexpect)); 337234949Sbapt exit_code = EXIT_FAILURE; 338234949Sbapt } 339234949Sbapt} 340234949Sbapt 341234949Sbaptstatic int 342234949Sbaptsole_reduction(int stateno) 343234949Sbapt{ 344234949Sbapt int count, ruleno; 345234949Sbapt action *p; 346234949Sbapt 347234949Sbapt count = 0; 348234949Sbapt ruleno = 0; 349234949Sbapt for (p = parser[stateno]; p; p = p->next) 350234949Sbapt { 351268899Sbapt if (p->action_code == SHIFT && MaySuppress(p)) 352234949Sbapt return (0); 353268899Sbapt else if ((p->action_code == REDUCE) && MaySuppress(p)) 354234949Sbapt { 355234949Sbapt if (ruleno > 0 && p->number != ruleno) 356234949Sbapt return (0); 357234949Sbapt if (p->symbol != 1) 358234949Sbapt ++count; 359234949Sbapt ruleno = p->number; 360234949Sbapt } 361234949Sbapt } 362234949Sbapt 363234949Sbapt if (count == 0) 364234949Sbapt return (0); 365234949Sbapt return (ruleno); 366234949Sbapt} 367234949Sbapt 368234949Sbaptstatic void 369234949Sbaptdefreds(void) 370234949Sbapt{ 371234949Sbapt int i; 372234949Sbapt 373234949Sbapt defred = NEW2(nstates, Value_t); 374234949Sbapt for (i = 0; i < nstates; i++) 375234949Sbapt defred[i] = (Value_t) sole_reduction(i); 376234949Sbapt} 377234949Sbapt 378234949Sbaptstatic void 379234949Sbaptfree_action_row(action *p) 380234949Sbapt{ 381234949Sbapt action *q; 382234949Sbapt 383234949Sbapt while (p) 384234949Sbapt { 385234949Sbapt q = p->next; 386234949Sbapt FREE(p); 387234949Sbapt p = q; 388234949Sbapt } 389234949Sbapt} 390234949Sbapt 391234949Sbaptvoid 392234949Sbaptfree_parser(void) 393234949Sbapt{ 394234949Sbapt int i; 395234949Sbapt 396234949Sbapt for (i = 0; i < nstates; i++) 397234949Sbapt free_action_row(parser[i]); 398234949Sbapt 399234949Sbapt FREE(parser); 400234949Sbapt} 401234949Sbapt 402234949Sbapt#ifdef NO_LEAKS 403234949Sbaptvoid 404234949Sbaptmkpar_leaks(void) 405234949Sbapt{ 406234949Sbapt DO_FREE(defred); 407234949Sbapt DO_FREE(rules_used); 408234949Sbapt DO_FREE(SRconflicts); 409234949Sbapt DO_FREE(RRconflicts); 410234949Sbapt} 411234949Sbapt#endif 412