external/bsd/byacc/dist/lalr.c

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