contrib/byacc/lalr.c

   1 /* $Id: lalr.c,v 1.11 2014/09/18 00:26:39 tom Exp $ */
   2
   3 #include "defs.h"
   4
   5 typedef struct shorts
   6 {
   7     struct shorts *next;
   8     Value_t value;
   9 }
  10 shorts;
  11
  12 static Value_t map_goto(int state, int symbol);
  13 static Value_t **transpose(Value_t ** R, int n);
  14 static void add_lookback_edge(int stateno, int ruleno, int gotono);
  15 static void build_relations(void);
  16 static void compute_FOLLOWS(void);
  17 static void compute_lookaheads(void);
  18 static void digraph(Value_t ** relation);
  19 static void initialize_F(void);
  20 static void initialize_LA(void);
  21 static void set_accessing_symbol(void);
  22 static void set_goto_map(void);
  23 static void set_maxrhs(void);
  24 static void set_reduction_table(void);
  25 static void set_shift_table(void);
  26 static void set_state_table(void);
  27 static void traverse(int i);
  28
  29 static int tokensetsize;
  30 Value_t *lookaheads;
  31 Value_t *LAruleno;
  32 unsigned *LA;
  33 Value_t *accessing_symbol;
  34 core **state_table;
  35 shifts **shift_table;
  36 reductions **reduction_table;
  37 Value_t *goto_base;
  38 Value_t *goto_map;
  39 Value_t *from_state;
  40 Value_t *to_state;
  41
  42 static Value_t infinity;
  43 static int maxrhs;
  44 static int ngotos;
  45 static unsigned *F;
  46 static Value_t **includes;
  47 static shorts **lookback;
  48 static Value_t **R;
  49 static Value_t *INDEX;
  50 static Value_t *VERTICES;
  51 static Value_t top;
  52
  53 void
  54 lalr(void)
  55 {
  56     tokensetsize = WORDSIZE(ntokens);
  57
  58     set_state_table();
  59     set_accessing_symbol();
  60     set_shift_table();
  61     set_reduction_table();
  62     set_maxrhs();
  63     initialize_LA();
  64     set_goto_map();
  65     initialize_F();
  66     build_relations();
  67     compute_FOLLOWS();
  68     compute_lookaheads();
  69 }
  70
  71 static void
  72 set_state_table(void)
  73 {
  74     core *sp;
  75
  76     state_table = NEW2(nstates, core *);
  77     for (sp = first_state; sp; sp = sp->next)
  78         state_table[sp->number] = sp;
  79 }
  80
  81 static void
  82 set_accessing_symbol(void)
  83 {
  84     core *sp;
  85
  86     accessing_symbol = NEW2(nstates, Value_t);
  87     for (sp = first_state; sp; sp = sp->next)
  88         accessing_symbol[sp->number] = sp->accessing_symbol;
  89 }
  90
  91 static void
  92 set_shift_table(void)
  93 {
  94     shifts *sp;
  95
  96     shift_table = NEW2(nstates, shifts *);
  97     for (sp = first_shift; sp; sp = sp->next)
  98         shift_table[sp->number] = sp;
  99 }
 100
 101 static void
 102 set_reduction_table(void)
 103 {
 104     reductions *rp;
 105
 106     reduction_table = NEW2(nstates, reductions *);
 107     for (rp = first_reduction; rp; rp = rp->next)
 108         reduction_table[rp->number] = rp;
 109 }
 110
 111 static void
 112 set_maxrhs(void)
 113 {
 114     Value_t *itemp;
 115     Value_t *item_end;
 116     int length;
 117     int max;
 118
 119     length = 0;
 120     max = 0;
 121     item_end = ritem + nitems;
 122     for (itemp = ritem; itemp < item_end; itemp++)
 123     {
 124         if (*itemp >= 0)
 125         {
 126             length++;
 127         }
 128         else
 129         {
 130             if (length > max)
 131                 max = length;
 132             length = 0;
 133         }
 134     }
 135
 136     maxrhs = max;
 137 }
 138
 139 static void
 140 initialize_LA(void)
 141 {
 142     int i, j, k;
 143     reductions *rp;
 144
 145     lookaheads = NEW2(nstates + 1, Value_t);
 146
 147     k = 0;
 148     for (i = 0; i < nstates; i++)
 149     {
 150         lookaheads[i] = (Value_t) k;
 151         rp = reduction_table[i];
 152         if (rp)
 153             k += rp->nreds;
 154     }
 155     lookaheads[nstates] = (Value_t) k;
 156
 157     LA = NEW2(k * tokensetsize, unsigned);
 158     LAruleno = NEW2(k, Value_t);
 159     lookback = NEW2(k, shorts *);
 160
 161     k = 0;
 162     for (i = 0; i < nstates; i++)
 163     {
 164         rp = reduction_table[i];
 165         if (rp)
 166         {
 167             for (j = 0; j < rp->nreds; j++)
 168             {
 169                 LAruleno[k] = rp->rules[j];
 170                 k++;
 171             }
 172         }
 173     }
 174 }
 175
 176 static void
 177 set_goto_map(void)
 178 {
 179     shifts *sp;
 180     int i;
 181     int symbol;
 182     int k;
 183     Value_t *temp_base;
 184     Value_t *temp_map;
 185     Value_t state2;
 186     Value_t state1;
 187
 188     goto_base = NEW2(nvars + 1, Value_t);
 189     temp_base = NEW2(nvars + 1, Value_t);
 190
 191     goto_map = goto_base - ntokens;
 192     temp_map = temp_base - ntokens;
 193
 194     ngotos = 0;
 195     for (sp = first_shift; sp; sp = sp->next)
 196     {
 197         for (i = sp->nshifts - 1; i >= 0; i--)
 198         {
 199             symbol = accessing_symbol[sp->shift[i]];
 200
 201             if (ISTOKEN(symbol))
 202                 break;
 203
 204             if (ngotos == MAXYYINT)
 205                 fatal("too many gotos");
 206
 207             ngotos++;
 208             goto_map[symbol]++;
 209         }
 210     }
 211
 212     k = 0;
 213     for (i = ntokens; i < nsyms; i++)
 214     {
 215         temp_map[i] = (Value_t) k;
 216         k += goto_map[i];
 217     }
 218
 219     for (i = ntokens; i < nsyms; i++)
 220         goto_map[i] = temp_map[i];
 221
 222     goto_map[nsyms] = (Value_t) ngotos;
 223     temp_map[nsyms] = (Value_t) ngotos;
 224
 225     from_state = NEW2(ngotos, Value_t);
 226     to_state = NEW2(ngotos, Value_t);
 227
 228     for (sp = first_shift; sp; sp = sp->next)
 229     {
 230         state1 = sp->number;
 231         for (i = sp->nshifts - 1; i >= 0; i--)
 232         {
 233             state2 = sp->shift[i];
 234             symbol = accessing_symbol[state2];
 235
 236             if (ISTOKEN(symbol))
 237                 break;
 238
 239             k = temp_map[symbol]++;
 240             from_state[k] = state1;
 241             to_state[k] = state2;
 242         }
 243     }
 244
 245     FREE(temp_base);
 246 }
 247
 248 /*  Map_goto maps a state/symbol pair into its numeric representation.  */
 249
 250 static Value_t
 251 map_goto(int state, int symbol)
 252 {
 253     int high;
 254     int low;
 255     int middle;
 256     int s;
 257
 258     low = goto_map[symbol];
 259     high = goto_map[symbol + 1];
 260
 261     for (;;)
 262     {
 263         assert(low <= high);
 264         middle = (low + high) >> 1;
 265         s = from_state[middle];
 266         if (s == state)
 267             return (Value_t) (middle);
 268         else if (s < state)
 269             low = middle + 1;
 270         else
 271             high = middle - 1;
 272     }
 273 }
 274
 275 static void
 276 initialize_F(void)
 277 {
 278     int i;
 279     int j;
 280     int k;
 281     shifts *sp;
 282     Value_t *edge;
 283     unsigned *rowp;
 284     Value_t *rp;
 285     Value_t **reads;
 286     int nedges;
 287     int stateno;
 288     int symbol;
 289     int nwords;
 290
 291     nwords = ngotos * tokensetsize;
 292     F = NEW2(nwords, unsigned);
 293
 294     reads = NEW2(ngotos, Value_t *);
 295     edge = NEW2(ngotos + 1, Value_t);
 296     nedges = 0;
 297
 298     rowp = F;
 299     for (i = 0; i < ngotos; i++)
 300     {
 301         stateno = to_state[i];
 302         sp = shift_table[stateno];
 303
 304         if (sp)
 305         {
 306             k = sp->nshifts;
 307
 308             for (j = 0; j < k; j++)
 309             {
 310                 symbol = accessing_symbol[sp->shift[j]];
 311                 if (ISVAR(symbol))
 312                     break;
 313                 SETBIT(rowp, symbol);
 314             }
 315
 316             for (; j < k; j++)
 317             {
 318                 symbol = accessing_symbol[sp->shift[j]];
 319                 if (nullable[symbol])
 320                     edge[nedges++] = map_goto(stateno, symbol);
 321             }
 322
 323             if (nedges)
 324             {
 325                 reads[i] = rp = NEW2(nedges + 1, Value_t);
 326
 327                 for (j = 0; j < nedges; j++)
 328                     rp[j] = edge[j];
 329
 330                 rp[nedges] = -1;
 331                 nedges = 0;
 332             }
 333         }
 334
 335         rowp += tokensetsize;
 336     }
 337
 338     SETBIT(F, 0);
 339     digraph(reads);
 340
 341     for (i = 0; i < ngotos; i++)
 342     {
 343         if (reads[i])
 344             FREE(reads[i]);
 345     }
 346
 347     FREE(reads);
 348     FREE(edge);
 349 }
 350
 351 static void
 352 build_relations(void)
 353 {
 354     int i;
 355     int j;
 356     int k;
 357     Value_t *rulep;
 358     Value_t *rp;
 359     shifts *sp;
 360     int length;
 361     int nedges;
 362     int done_flag;
 363     Value_t state1;
 364     Value_t stateno;
 365     int symbol1;
 366     int symbol2;
 367     Value_t *shortp;
 368     Value_t *edge;
 369     Value_t *states;
 370     Value_t **new_includes;
 371
 372     includes = NEW2(ngotos, Value_t *);
 373     edge = NEW2(ngotos + 1, Value_t);
 374     states = NEW2(maxrhs + 1, Value_t);
 375
 376     for (i = 0; i < ngotos; i++)
 377     {
 378         nedges = 0;
 379         state1 = from_state[i];
 380         symbol1 = accessing_symbol[to_state[i]];
 381
 382         for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
 383         {
 384             length = 1;
 385             states[0] = state1;
 386             stateno = state1;
 387
 388             for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
 389             {
 390                 symbol2 = *rp;
 391                 sp = shift_table[stateno];
 392                 k = sp->nshifts;
 393
 394                 for (j = 0; j < k; j++)
 395                 {
 396                     stateno = sp->shift[j];
 397                     if (accessing_symbol[stateno] == symbol2)
 398                         break;
 399                 }
 400
 401                 states[length++] = stateno;
 402             }
 403
 404             add_lookback_edge(stateno, *rulep, i);
 405
 406             length--;
 407             done_flag = 0;
 408             while (!done_flag)
 409             {
 410                 done_flag = 1;
 411                 rp--;
 412                 if (ISVAR(*rp))
 413                 {
 414                     stateno = states[--length];
 415                     edge[nedges++] = map_goto(stateno, *rp);
 416                     if (nullable[*rp] && length > 0)
 417                         done_flag = 0;
 418                 }
 419             }
 420         }
 421
 422         if (nedges)
 423         {
 424             includes[i] = shortp = NEW2(nedges + 1, Value_t);
 425             for (j = 0; j < nedges; j++)
 426                 shortp[j] = edge[j];
 427             shortp[nedges] = -1;
 428         }
 429     }
 430
 431     new_includes = transpose(includes, ngotos);
 432
 433     for (i = 0; i < ngotos; i++)
 434         if (includes[i])
 435             FREE(includes[i]);
 436
 437     FREE(includes);
 438
 439     includes = new_includes;
 440
 441     FREE(edge);
 442     FREE(states);
 443 }
 444
 445 static void
 446 add_lookback_edge(int stateno, int ruleno, int gotono)
 447 {
 448     int i, k;
 449     int found;
 450     shorts *sp;
 451
 452     i = lookaheads[stateno];
 453     k = lookaheads[stateno + 1];
 454     found = 0;
 455     while (!found && i < k)
 456     {
 457         if (LAruleno[i] == ruleno)
 458             found = 1;
 459         else
 460             ++i;
 461     }
 462     assert(found);
 463
 464     sp = NEW(shorts);
 465     sp->next = lookback[i];
 466     sp->value = (Value_t) gotono;
 467     lookback[i] = sp;
 468 }
 469
 470 static Value_t **
 471 transpose(Value_t ** R2, int n)
 472 {
 473     Value_t **new_R;
 474     Value_t **temp_R;
 475     Value_t *nedges;
 476     Value_t *sp;
 477     int i;
 478     int k;
 479
 480     nedges = NEW2(n, Value_t);
 481
 482     for (i = 0; i < n; i++)
 483     {
 484         sp = R2[i];
 485         if (sp)
 486         {
 487             while (*sp >= 0)
 488                 nedges[*sp++]++;
 489         }
 490     }
 491
 492     new_R = NEW2(n, Value_t *);
 493     temp_R = NEW2(n, Value_t *);
 494
 495     for (i = 0; i < n; i++)
 496     {
 497         k = nedges[i];
 498         if (k > 0)
 499         {
 500             sp = NEW2(k + 1, Value_t);
 501             new_R[i] = sp;
 502             temp_R[i] = sp;
 503             sp[k] = -1;
 504         }
 505     }
 506
 507     FREE(nedges);
 508
 509     for (i = 0; i < n; i++)
 510     {
 511         sp = R2[i];
 512         if (sp)
 513         {
 514             while (*sp >= 0)
 515                 *temp_R[*sp++]++ = (Value_t) i;
 516         }
 517     }
 518
 519     FREE(temp_R);
 520
 521     return (new_R);
 522 }
 523
 524 static void
 525 compute_FOLLOWS(void)
 526 {
 527     digraph(includes);
 528 }
 529
 530 static void
 531 compute_lookaheads(void)
 532 {
 533     int i, n;
 534     unsigned *fp1, *fp2, *fp3;
 535     shorts *sp, *next;
 536     unsigned *rowp;
 537
 538     rowp = LA;
 539     n = lookaheads[nstates];
 540     for (i = 0; i < n; i++)
 541     {
 542         fp3 = rowp + tokensetsize;
 543         for (sp = lookback[i]; sp; sp = sp->next)
 544         {
 545             fp1 = rowp;
 546             fp2 = F + tokensetsize * sp->value;
 547             while (fp1 < fp3)
 548                 *fp1++ |= *fp2++;
 549         }
 550         rowp = fp3;
 551     }
 552
 553     for (i = 0; i < n; i++)
 554         for (sp = lookback[i]; sp; sp = next)
 555         {
 556             next = sp->next;
 557             FREE(sp);
 558         }
 559
 560     FREE(lookback);
 561     FREE(F);
 562 }
 563
 564 static void
 565 digraph(Value_t ** relation)
 566 {
 567     int i;
 568
 569     infinity = (Value_t) (ngotos + 2);
 570     INDEX = NEW2(ngotos + 1, Value_t);
 571     VERTICES = NEW2(ngotos + 1, Value_t);
 572     top = 0;
 573
 574     R = relation;
 575
 576     for (i = 0; i < ngotos; i++)
 577         INDEX[i] = 0;
 578
 579     for (i = 0; i < ngotos; i++)
 580     {
 581         if (INDEX[i] == 0 && R[i])
 582             traverse(i);
 583     }
 584
 585     FREE(INDEX);
 586     FREE(VERTICES);
 587 }
 588
 589 static void
 590 traverse(int i)
 591 {
 592     unsigned *fp1;
 593     unsigned *fp2;
 594     unsigned *fp3;
 595     int j;
 596     Value_t *rp;
 597
 598     Value_t height;
 599     unsigned *base;
 600
 601     VERTICES[++top] = (Value_t) i;
 602     INDEX[i] = height = top;
 603
 604     base = F + i * tokensetsize;
 605     fp3 = base + tokensetsize;
 606
 607     rp = R[i];
 608     if (rp)
 609     {
 610         while ((j = *rp++) >= 0)
 611         {
 612             if (INDEX[j] == 0)
 613                 traverse(j);
 614
 615             if (INDEX[i] > INDEX[j])
 616                 INDEX[i] = INDEX[j];
 617
 618             fp1 = base;
 619             fp2 = F + j * tokensetsize;
 620
 621             while (fp1 < fp3)
 622                 *fp1++ |= *fp2++;
 623         }
 624     }
 625
 626     if (INDEX[i] == height)
 627     {
 628         for (;;)
 629         {
 630             j = VERTICES[top--];
 631             INDEX[j] = infinity;
 632
 633             if (i == j)
 634                 break;
 635
 636             fp1 = base;
 637             fp2 = F + j * tokensetsize;
 638
 639             while (fp1 < fp3)
 640                 *fp2++ = *fp1++;
 641         }
 642     }
 643 }
 644
 645 #ifdef NO_LEAKS
 646 void
 647 lalr_leaks(void)
 648 {
 649     int i;
 650
 651     if (includes != 0)
 652     {
 653         for (i = 0; i < ngotos; i++)
 654         {
 655             free(includes[i]);
 656         }
 657         DO_FREE(includes);
 658     }
 659 }
 660 #endif