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