lalr.c

   1 /* $Id: lalr.c,v 1.13 2020/09/10 17:26:21 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
 187     goto_base = NEW2(nvars + 1, Value_t);
 188     temp_base = NEW2(nvars + 1, Value_t);
 189
 190     goto_map = goto_base - ntokens;
 191     temp_map = temp_base - 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 == MAXYYINT)
 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         Value_t state1 = sp->number;
 230
 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 low = goto_map[symbol];
 254     int high = goto_map[symbol + 1];
 255
 256     for (;;)
 257     {
 258         int middle;
 259         int s;
 260
 261         assert(low <= high);
 262         middle = (low + high) >> 1;
 263         s = from_state[middle];
 264         if (s == state)
 265             return (Value_t)(middle);
 266         else if (s < state)
 267             low = middle + 1;
 268         else
 269             high = middle - 1;
 270     }
 271 }
 272
 273 static void
 274 initialize_F(void)
 275 {
 276     int i;
 277     int j;
 278     int k;
 279     shifts *sp;
 280     Value_t *edge;
 281     unsigned *rowp;
 282     Value_t *rp;
 283     Value_t **reads;
 284     int nedges;
 285     int symbol;
 286     int nwords;
 287
 288     nwords = ngotos * tokensetsize;
 289     F = NEW2(nwords, unsigned);
 290
 291     reads = NEW2(ngotos, Value_t *);
 292     edge = NEW2(ngotos + 1, Value_t);
 293     nedges = 0;
 294
 295     rowp = F;
 296     for (i = 0; i < ngotos; i++)
 297     {
 298         int stateno = to_state[i];
 299
 300         sp = shift_table[stateno];
 301
 302         if (sp)
 303         {
 304             k = sp->nshifts;
 305
 306             for (j = 0; j < k; j++)
 307             {
 308                 symbol = accessing_symbol[sp->shift[j]];
 309                 if (ISVAR(symbol))
 310                     break;
 311                 SETBIT(rowp, symbol);
 312             }
 313
 314             for (; j < k; j++)
 315             {
 316                 symbol = accessing_symbol[sp->shift[j]];
 317                 if (nullable[symbol])
 318                     edge[nedges++] = map_goto(stateno, symbol);
 319             }
 320
 321             if (nedges)
 322             {
 323                 reads[i] = rp = NEW2(nedges + 1, Value_t);
 324
 325                 for (j = 0; j < nedges; j++)
 326                     rp[j] = edge[j];
 327
 328                 rp[nedges] = -1;
 329                 nedges = 0;
 330             }
 331         }
 332
 333         rowp += tokensetsize;
 334     }
 335
 336     SETBIT(F, 0);
 337     digraph(reads);
 338
 339     for (i = 0; i < ngotos; i++)
 340     {
 341         if (reads[i])
 342             FREE(reads[i]);
 343     }
 344
 345     FREE(reads);
 346     FREE(edge);
 347 }
 348
 349 static void
 350 build_relations(void)
 351 {
 352     int i;
 353     int j;
 354     int k;
 355     Value_t *rulep;
 356     Value_t *rp;
 357     shifts *sp;
 358     int length;
 359     int done_flag;
 360     Value_t stateno;
 361     int symbol2;
 362     Value_t *shortp;
 363     Value_t *edge;
 364     Value_t *states;
 365     Value_t **new_includes;
 366
 367     includes = NEW2(ngotos, Value_t *);
 368     edge = NEW2(ngotos + 1, Value_t);
 369     states = NEW2(maxrhs + 1, Value_t);
 370
 371     for (i = 0; i < ngotos; i++)
 372     {
 373         int nedges = 0;
 374         int symbol1 = accessing_symbol[to_state[i]];
 375         Value_t state1 = from_state[i];
 376
 377         for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
 378         {
 379             length = 1;
 380             states[0] = state1;
 381             stateno = state1;
 382
 383             for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
 384             {
 385                 symbol2 = *rp;
 386                 sp = shift_table[stateno];
 387                 k = sp->nshifts;
 388
 389                 for (j = 0; j < k; j++)
 390                 {
 391                     stateno = sp->shift[j];
 392                     if (accessing_symbol[stateno] == symbol2)
 393                         break;
 394                 }
 395
 396                 states[length++] = stateno;
 397             }
 398
 399             add_lookback_edge(stateno, *rulep, i);
 400
 401             length--;
 402             done_flag = 0;
 403             while (!done_flag)
 404             {
 405                 done_flag = 1;
 406                 rp--;
 407                 if (ISVAR(*rp))
 408                 {
 409                     stateno = states[--length];
 410                     edge[nedges++] = map_goto(stateno, *rp);
 411                     if (nullable[*rp] && length > 0)
 412                         done_flag = 0;
 413                 }
 414             }
 415         }
 416
 417         if (nedges)
 418         {
 419             includes[i] = shortp = NEW2(nedges + 1, Value_t);
 420             for (j = 0; j < nedges; j++)
 421                 shortp[j] = edge[j];
 422             shortp[nedges] = -1;
 423         }
 424     }
 425
 426     new_includes = transpose(includes, ngotos);
 427
 428     for (i = 0; i < ngotos; i++)
 429         if (includes[i])
 430             FREE(includes[i]);
 431
 432     FREE(includes);
 433
 434     includes = new_includes;
 435
 436     FREE(edge);
 437     FREE(states);
 438 }
 439
 440 static void
 441 add_lookback_edge(int stateno, int ruleno, int gotono)
 442 {
 443     int i, k;
 444     int found;
 445     shorts *sp;
 446
 447     i = lookaheads[stateno];
 448     k = lookaheads[stateno + 1];
 449     found = 0;
 450     while (!found && i < k)
 451     {
 452         if (LAruleno[i] == ruleno)
 453             found = 1;
 454         else
 455             ++i;
 456     }
 457     assert(found);
 458
 459     sp = NEW(shorts);
 460     sp->next = lookback[i];
 461     sp->value = (Value_t)gotono;
 462     lookback[i] = sp;
 463 }
 464
 465 static Value_t **
 466 transpose(Value_t **R2, int n)
 467 {
 468     Value_t **new_R;
 469     Value_t **temp_R;
 470     Value_t *nedges;
 471     Value_t *sp;
 472     int i;
 473
 474     nedges = NEW2(n, Value_t);
 475
 476     for (i = 0; i < n; i++)
 477     {
 478         sp = R2[i];
 479         if (sp)
 480         {
 481             while (*sp >= 0)
 482                 nedges[*sp++]++;
 483         }
 484     }
 485
 486     new_R = NEW2(n, Value_t *);
 487     temp_R = NEW2(n, Value_t *);
 488
 489     for (i = 0; i < n; i++)
 490     {
 491         int k = nedges[i];
 492
 493         if (k > 0)
 494         {
 495             sp = NEW2(k + 1, Value_t);
 496             new_R[i] = sp;
 497             temp_R[i] = sp;
 498             sp[k] = -1;
 499         }
 500     }
 501
 502     FREE(nedges);
 503
 504     for (i = 0; i < n; i++)
 505     {
 506         sp = R2[i];
 507         if (sp)
 508         {
 509             while (*sp >= 0)
 510                 *temp_R[*sp++]++ = (Value_t)i;
 511         }
 512     }
 513
 514     FREE(temp_R);
 515
 516     return (new_R);
 517 }
 518
 519 static void
 520 compute_FOLLOWS(void)
 521 {
 522     digraph(includes);
 523 }
 524
 525 static void
 526 compute_lookaheads(void)
 527 {
 528     int i, n;
 529     unsigned *fp1, *fp2, *fp3;
 530     shorts *sp, *next;
 531     unsigned *rowp;
 532
 533     rowp = LA;
 534     n = lookaheads[nstates];
 535     for (i = 0; i < n; i++)
 536     {
 537         fp3 = rowp + tokensetsize;
 538         for (sp = lookback[i]; sp; sp = sp->next)
 539         {
 540             fp1 = rowp;
 541             fp2 = F + tokensetsize * sp->value;
 542             while (fp1 < fp3)
 543                 *fp1++ |= *fp2++;
 544         }
 545         rowp = fp3;
 546     }
 547
 548     for (i = 0; i < n; i++)
 549         for (sp = lookback[i]; sp; sp = next)
 550         {
 551             next = sp->next;
 552             FREE(sp);
 553         }
 554
 555     FREE(lookback);
 556     FREE(F);
 557 }
 558
 559 static void
 560 digraph(Value_t **relation)
 561 {
 562     int i;
 563
 564     infinity = (Value_t)(ngotos + 2);
 565     INDEX = NEW2(ngotos + 1, Value_t);
 566     VERTICES = NEW2(ngotos + 1, Value_t);
 567     top = 0;
 568
 569     R = relation;
 570
 571     for (i = 0; i < ngotos; i++)
 572         INDEX[i] = 0;
 573
 574     for (i = 0; i < ngotos; i++)
 575     {
 576         if (INDEX[i] == 0 && R[i])
 577             traverse(i);
 578     }
 579
 580     FREE(INDEX);
 581     FREE(VERTICES);
 582 }
 583
 584 static void
 585 traverse(int i)
 586 {
 587     unsigned *fp1;
 588     unsigned *fp2;
 589     unsigned *fp3;
 590     int j;
 591     Value_t *rp;
 592
 593     Value_t height;
 594     unsigned *base;
 595
 596     VERTICES[++top] = (Value_t)i;
 597     INDEX[i] = height = top;
 598
 599     base = F + i * tokensetsize;
 600     fp3 = base + tokensetsize;
 601
 602     rp = R[i];
 603     if (rp)
 604     {
 605         while ((j = *rp++) >= 0)
 606         {
 607             if (INDEX[j] == 0)
 608                 traverse(j);
 609
 610             if (INDEX[i] > INDEX[j])
 611                 INDEX[i] = INDEX[j];
 612
 613             fp1 = base;
 614             fp2 = F + j * tokensetsize;
 615
 616             while (fp1 < fp3)
 617                 *fp1++ |= *fp2++;
 618         }
 619     }
 620
 621     if (INDEX[i] == height)
 622     {
 623         for (;;)
 624         {
 625             j = VERTICES[top--];
 626             INDEX[j] = infinity;
 627
 628             if (i == j)
 629                 break;
 630
 631             fp1 = base;
 632             fp2 = F + j * tokensetsize;
 633
 634             while (fp1 < fp3)
 635                 *fp2++ = *fp1++;
 636         }
 637     }
 638 }
 639
 640 #ifdef NO_LEAKS
 641 void
 642 lalr_leaks(void)
 643 {
 644     if (includes != 0)
 645     {
 646         int i;
 647
 648         for (i = 0; i < ngotos; i++)
 649         {
 650             free(includes[i]);
 651         }
 652         DO_FREE(includes);
 653     }
 654 }
 655 #endif