Home | History | Annotate | Line # | Download | only in dist
lalr.c revision 1.1.1.6 
      1 /* $Id: lalr.c,v 1.1.1.6 2016/01/09 21:55:11 christos 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
    661