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