# include "dgd.h" # include "str.h" # include "srp.h" typedef struct _item_ { char *ref; /* pointer to rule in grammar */ unsigned short ruleno; /* rule number */ unsigned short offset; /* offset in rule */ struct _item_ *next; /* next in linked list */ } item; # define ITCHUNKSZ 32 typedef struct _itchunk_ { item it[ITCHUNKSZ]; /* chunk of items */ int chunksz; /* size of this chunk */ item *flist; /* list of free items */ struct _itchunk_ *next; /* next in linked list */ } itchunk; /* * NAME: item->new() * DESCRIPTION: create a new item */ static item *it_new(c, ref, ruleno, offset, next) register itchunk **c; char *ref; int ruleno, offset; item *next; { register item *it; if (*c == (itchunk *) NULL || ((*c)->flist == (item *) NULL && (*c)->chunksz == ITCHUNKSZ)) { register itchunk *x; x = ALLOC(itchunk, 1); x->flist = (*c != (itchunk *) NULL) ? (*c)->flist : (item *) NULL; x->next = *c; *c = x; x->chunksz = 0; } if ((*c)->flist != (item *) NULL) { it = (*c)->flist; (*c)->flist = it->next; } else { it = &(*c)->it[(*c)->chunksz++]; } it->ref = ref; it->ruleno = ruleno; it->offset = offset; it->next = next; return it; } /* * NAME: item->del() * DESCRIPTION: delete an item */ static item *it_del(c, it) register itchunk *c; register item *it; { item *next; next = it->next; it->next = c->flist; c->flist = it; return next; } /* * NAME: item->clear() * DESCRIPTION: free all items in memory */ static void it_clear(c) register itchunk *c; { register itchunk *f; while (c != (itchunk *) NULL) { f = c; c = c->next; FREE(f); } } /* * NAME: item->add() * DESCRIPTION: add an item to a set */ static void it_add(c, ri, ref, ruleno, offset, sort) itchunk **c; register item **ri; register char *ref; int ruleno; register int offset; bool sort; { /* * add item to set */ if (offset == UCHAR(ref[0]) << 1) { offset = UCHAR(ref[1]); /* skip possible function at the end */ } if (sort) { while (*ri != (item *) NULL && ((*ri)->ref < ref || ((*ri)->ref == ref && (*ri)->offset <= offset))) { if ((*ri)->ref == ref && (*ri)->offset == offset) { return; /* already in set */ } ri = &(*ri)->next; } } else { while (*ri != (item *) NULL) { if ((*ri)->ref == ref && (*ri)->offset == offset) { return; /* already in set */ } ri = &(*ri)->next; } } *ri = it_new(c, ref, ruleno, offset, *ri); } /* * NAME: item->load() * DESCRIPTION: load an item */ static item *it_load(c, n, buf, grammar) itchunk **c; int n; char **buf, *grammar; { register char *p; register item **ri; item *it; char *ref; int ruleno; ri = ⁢ p = *buf; do { ref = grammar + (UCHAR(p[0]) << 8) + UCHAR(p[1]); p += 2; ruleno = (UCHAR(p[0]) << 8) + UCHAR(p[1]); p += 2; *ri = it_new(c, ref, ruleno, UCHAR(*p++), (item *) NULL); ri = &(*ri)->next; } while (--n != 0); *buf = p; return it; } /* * NAME: item->save() * DESCRIPTION: save an item */ static char *it_save(it, buf, grammar) register item *it; register char *buf; char *grammar; { int offset; while (it != (item *) NULL) { offset = it->ref - grammar; *buf++ = offset >> 8; *buf++ = offset; *buf++ = it->ruleno >> 8; *buf++ = it->ruleno; *buf++ = it->offset; it = it->next; } return buf; } typedef struct { item *items; /* rules and offsets */ union { char e[4]; /* 1 */ char *a; /* > 1 */ } reds; /* reductions */ unsigned short nitem; /* # items */ short nred; /* # reductions, -1 if unexpanded */ short shoffset; /* offset for shifts */ unsigned short shcheck; /* shift offset check */ short gtoffset; /* offset for gotos */ unsigned short next; /* next in linked list */ bool alloc; /* reductions allocated? */ } srpstate; # define REDA(state) (((state)->nred == 1) ? \ (state)->reds.e : (state)->reds.a) /* * NAME: srpstate->hash() * DESCRIPTION: put a new state in the hash table, or return an old one */ static int ss_hash(htab, htabsize, states, idx) unsigned short *htab; int htabsize, idx; srpstate *states; { register unsigned long h; register srpstate *newstate; register item *it, *it2; srpstate *s; unsigned short *sr; /* hash on items */ newstate = &states[idx]; h = 0; for (it = newstate->items; it != (item *) NULL; it = it->next) { h ^= (long) it->ref; h = (h >> 3) ^ (h << 29) ^ it->offset; } /* check state hash table */ sr = &htab[(Uint) h % htabsize]; s = &states[*sr]; while (s != states) { it = newstate->items; it2 = s->items; while (it != (item *) NULL && it2 != (item *) NULL && it->ref == it2->ref && it->offset == it2->offset) { it = it->next; it2 = it2->next; } if (it == it2) { return *sr; /* state already exists */ } sr = &s->next; s = &states[*sr]; } newstate->next = *sr; return *sr = idx; } /* * NAME: srpstate->load() * DESCRIPTION: load a srpstate */ static char *ss_load(buf, rbuf, state) register char *buf, **rbuf; register srpstate *state; { state->items = (item *) NULL; state->nitem = (UCHAR(buf[0]) << 8) + UCHAR(buf[1]); buf += 2; state->nred = (UCHAR(buf[0]) << 8) + UCHAR(buf[1]); buf += 2; state->shoffset = (UCHAR(buf[0]) << 8) + UCHAR(buf[1]); buf += 2; state->shcheck = (UCHAR(buf[0]) << 8) + UCHAR(buf[1]); buf += 2; state->gtoffset = (UCHAR(buf[0]) << 8) + UCHAR(buf[1]); buf += 2; if (state->nred > 0) { if (state->nred == 1) { memcpy(state->reds.e, *rbuf, 4); } else { state->reds.a = *rbuf; } *rbuf += 4 * state->nred; } state->alloc = FALSE; return buf; } /* * NAME: srpstate->save() * DESCRIPTION: save a srpstate */ static char *ss_save(state, buf, rbuf) register srpstate *state; register char *buf, **rbuf; { *buf++ = state->nitem >> 8; *buf++ = state->nitem; *buf++ = state->nred >> 8; *buf++ = state->nred; *buf++ = state->shoffset >> 8; *buf++ = state->shoffset; *buf++ = state->shcheck >> 8; *buf++ = state->shcheck; *buf++ = state->gtoffset >> 8; *buf++ = state->gtoffset; if (state->nred > 0) { memcpy(*rbuf, REDA(state), state->nred * 4); *rbuf += state->nred * 4; } return buf; } typedef struct _shlink_ { Int shifts; /* offset in shift table */ struct _shlink_ *next; /* next in linked list */ } shlink; # define SLCHUNKSZ 64 typedef struct _slchunk_ { shlink sl[SLCHUNKSZ]; /* shlinks */ int chunksz; /* size of chunk */ struct _slchunk_ *next; /* next in linked list */ } slchunk; /* * NAME: shlink->hash() * DESCRIPTION: put a new shlink in the hash table, or return an old one */ static shlink *sl_hash(htab, htabsize, c, shtab, shifts, n) shlink **htab; Uint htabsize; register slchunk **c; char *shtab; register char *shifts; register int n; { register unsigned long h; register int i; register shlink **ssl, *sl; /* search in hash table */ shifts += 4; n -= 4; h = 0; for (i = n; --i >= 0; ) { h = (h >> 3) ^ (h << 29) ^ *shifts++; } shifts -= n; ssl = &htab[h % htabsize]; while (*ssl != (shlink *) NULL) { if (memcmp(shtab + (*ssl)->shifts + 4, shifts, n) == 0) { /* seen this one before */ return *ssl; } ssl = &(*ssl)->next; } if (*c == (slchunk *) NULL || (*c)->chunksz == SLCHUNKSZ) { register slchunk *x; x = ALLOC(slchunk, 1); x->next = *c; *c = x; x->chunksz = 0; } sl = &(*c)->sl[(*c)->chunksz++]; sl->next = *ssl; *ssl = sl; sl->shifts = -1; return sl; } /* * NAME: shlink->clear() * DESCRIPTION: clean up shlinks */ static void sl_clear(c) register slchunk *c; { register slchunk *f; while (c != (slchunk *) NULL) { f = c; c = c->next; FREE(f); } } struct _srp_ { char *grammar; /* grammar */ unsigned short ntoken; /* # of tokens (regexp & string) */ unsigned short nprod; /* # of nonterminals */ unsigned short nred; /* # of reductions */ unsigned short nitem; /* # of items */ Uint srpsize; /* size of shift/reduce parser */ Uint tmpsize; /* size of temporary data */ bool srpchanged; /* srp needs saving */ bool tmpchanged; /* tmp data needs saving */ string *srpstr; /* srp string */ string *tmpstr; /* tmp string */ unsigned short nstates; /* number of states */ unsigned short nexpanded; /* number of expanded states */ Uint sttsize; /* state table size */ Uint sthsize; /* state hash table size */ srpstate *states; /* state array */ unsigned short *sthtab; /* state hash table */ itchunk *itc; /* item chunk */ Uint gap; /* first gap in packed mapping */ Uint spread; /* max spread in packed mapping */ Uint mapsize; /* packed mapping size */ char *data; /* packed shifts */ char *check; /* packed check for shift validity */ bool alloc; /* data and check allocated separately? */ slchunk *slc; /* shlink chunk */ Uint nshift; /* number of shifts (from/to pairs) */ Uint shtsize; /* shift table size */ Uint shhsize; /* shift hash table size */ char *shtab; /* shift (from/to) table */ shlink **shhtab; /* shift hash table */ }; # define NOSHIFT ((short) 0x8000) /* * NAME: srp->new() * DESCRIPTION: create new shift/reduce parser */ srp *srp_new(grammar) char *grammar; { register srp *lr; register char *p; Uint nrule; lr = ALLOC(srp, 1); /* grammar info */ lr->grammar = grammar; lr->ntoken = ((UCHAR(grammar[2]) + UCHAR(grammar[6])) << 8) + UCHAR(grammar[3]) + UCHAR(grammar[7]); lr->nprod = (UCHAR(grammar[8]) << 8) + UCHAR(grammar[9]); nrule = (UCHAR(grammar[10]) << 8) + UCHAR(grammar[11]); /* sizes */ lr->srpstr = (string *) NULL; lr->tmpstr = (string *) NULL; lr->nred = lr->nitem = 0; lr->srpsize = 11 + 10 + 4; /* srp header + 1 state + data/check overhead */ lr->tmpsize = 5 + 5; /* tmp header + 1 item */ lr->srpchanged = lr->tmpchanged = FALSE; /* states */ lr->nstates = 1; lr->nexpanded = 0; lr->sttsize = nrule << 1; lr->sthsize = nrule << 2; lr->states = ALLOC(srpstate, lr->sttsize); lr->sthtab = ALLOC(unsigned short, lr->sthsize); memset(lr->sthtab, '\0', lr->sthsize * sizeof(unsigned short)); lr->itc = (itchunk *) NULL; /* state 0 */ p = grammar + 12 + (lr->ntoken << 1); p = grammar + (UCHAR(p[0]) << 8) + UCHAR(p[1]); lr->states[0].items = it_new(&lr->itc, p + 2, lr->ntoken, 0, (item *) NULL); lr->states[0].nitem = 1; lr->states[0].nred = -1; lr->states[0].shoffset = NOSHIFT; lr->states[0].shcheck = 0; lr->states[0].gtoffset = 0; lr->states[0].alloc = FALSE; /* packed mapping for shift */ lr->gap = lr->spread = 0; lr->mapsize = (Uint) (lr->ntoken + lr->nprod) << 2; lr->data = ALLOC(char, lr->mapsize); memset(lr->data, '\0', lr->mapsize); lr->check = ALLOC(char, lr->mapsize); memset(lr->check, '\xff', lr->mapsize); lr->alloc = TRUE; /* shift hash table */ lr->slc = (slchunk *) NULL; lr->nshift = 0; lr->shtsize = lr->mapsize; lr->shhsize = nrule << 2; lr->shtab = ALLOC(char, lr->shtsize); lr->shhtab = ALLOC(shlink*, lr->shhsize); memset(lr->shhtab, '\0', lr->shhsize * sizeof(shlink*)); return lr; } /* * NAME: srp->del() * DESCRIPTION: delete shift/reduce parser */ void srp_del(lr) register srp *lr; { register int i; register srpstate *state; if (lr->srpstr != (string *) NULL) { str_del(lr->srpstr); } if (lr->tmpstr != (string *) NULL) { str_del(lr->tmpstr); } it_clear(lr->itc); if (lr->sthtab != (unsigned short *) NULL) { FREE(lr->sthtab); } for (i = lr->nstates, state = lr->states; --i >= 0; state++) { if (state->alloc) { FREE(state->reds.a); } } FREE(lr->states); if (lr->alloc) { FREE(lr->data); FREE(lr->check); } sl_clear(lr->slc); if (lr->shtab != (char *) NULL) { FREE(lr->shtab); } if (lr->shhtab != (shlink **) NULL) { FREE(lr->shhtab); } FREE(lr); } /* * NAME: srp->load() * DESCRIPTION: load a shift/reduce parser from strings */ srp *srp_load(grammar, s1, s2) char *grammar; string *s1, *s2; { register srp *lr; register char *buf; register int i; register srpstate *state; char *rbuf; lr = ALLOC(srp, 1); /* grammar info */ lr->grammar = grammar; lr->ntoken = ((UCHAR(grammar[2]) + UCHAR(grammar[6])) << 8) + UCHAR(grammar[3]) + UCHAR(grammar[7]); lr->nprod = (UCHAR(grammar[8]) << 8) + UCHAR(grammar[9]); str_ref(lr->srpstr = s1); lr->tmpstr = s2; if (s2 != (string *) NULL) { str_ref(s2); } buf = s1->text; /* header */ lr->nstates = (UCHAR(buf[1]) << 8) + UCHAR(buf[2]); lr->nexpanded = (UCHAR(buf[3]) << 8) + UCHAR(buf[4]); lr->nred = (UCHAR(buf[5]) << 8) + UCHAR(buf[6]); lr->gap = (UCHAR(buf[7]) << 8) + UCHAR(buf[8]); lr->spread = (UCHAR(buf[9]) << 8) + UCHAR(buf[10]); buf += 11; /* sizes */ lr->nitem = 0; lr->srpsize = s1->len; lr->tmpsize = 0; lr->srpchanged = lr->tmpchanged = FALSE; /* states */ lr->sttsize = lr->nstates + 1; lr->sthsize = 0; lr->states = ALLOC(srpstate, lr->sttsize); lr->sthtab = (unsigned short *) NULL; lr->itc = (itchunk *) NULL; /* load states */ rbuf = buf + lr->nstates * 10; for (i = lr->nstates, state = lr->states; --i >= 0; state++) { buf = ss_load(buf, &rbuf, state); } buf = rbuf; /* load packed mapping */ lr->mapsize = lr->spread + 2; lr->data = buf; buf += lr->spread + 2; lr->check = buf; lr->alloc = FALSE; /* shift hash table */ lr->slc = (slchunk *) NULL; lr->nshift = 0; lr->shtsize = 0; lr->shhsize = 0; lr->shtab = (char *) NULL; lr->shhtab = (shlink **) NULL; return lr; } /* * NAME: srp->loadtmp() * DESCRIPTION: load the temporary data for a shift/reduce parser */ static void srp_loadtmp(lr) register srp *lr; { register int i, n; register srpstate *state; register char *p; Uint nrule; char *buf; nrule = (UCHAR(lr->grammar[10]) << 8) + UCHAR(lr->grammar[11]); buf = lr->tmpstr->text; lr->nitem = (UCHAR(buf[1]) << 8) + UCHAR(buf[2]); lr->nshift = (UCHAR(buf[3]) << 8) + UCHAR(buf[4]); buf += 5; /* states */ lr->sthsize = nrule << 2; lr->sthtab = ALLOC(unsigned short, lr->sthsize); memset(lr->sthtab, '\0', lr->sthsize * sizeof(unsigned short)); for (i = 0, state = lr->states; i < lr->nstates; i++, state++) { if (state->nitem != 0) { state->items = it_load(&lr->itc, state->nitem, &buf, lr->grammar); } ss_hash(lr->sthtab, lr->sthsize, lr->states, i); } /* shifts */ lr->shtsize = lr->nshift * 2; lr->shhsize = nrule << 2; lr->shtab = ALLOC(char, lr->shtsize); memcpy(lr->shtab, buf, lr->nshift); lr->shhtab = ALLOC(shlink*, lr->shhsize); memset(lr->shhtab, '\0', lr->shhsize * sizeof(shlink*)); for (i = 0, p = buf; i != lr->nshift; i += n, p += n) { n = 4 * ((UCHAR(p[4]) << 8) + UCHAR(p[5])) + 6; sl_hash(lr->shhtab, lr->shhsize, &lr->slc, lr->shtab, p, n)->shifts = p - lr->shtab; } lr->tmpsize = lr->tmpstr->len; } /* * NAME: srp->save() * DESCRIPTION: save a shift/reduce parser to strings */ bool srp_save(lr, s1, s2) register srp *lr; string **s1, **s2; { register char *buf; register int i; register srpstate *state; char *rbuf; if (!lr->srpchanged) { *s1 = lr->srpstr; *s2 = lr->tmpstr; return FALSE; } if (lr->srpstr != (string *) NULL) { str_del(lr->srpstr); } str_ref(lr->srpstr = *s1 = str_new((char *) NULL, (long) lr->srpsize)); buf = (*s1)->text; /* header */ *buf++ = 0; *buf++ = lr->nstates >> 8; *buf++ = lr->nstates; *buf++ = lr->nexpanded >> 8; *buf++ = lr->nexpanded; *buf++ = lr->nred >> 8; *buf++ = lr->nred; *buf++ = lr->gap >> 8; *buf++ = lr->gap; *buf++ = lr->spread >> 8; *buf++ = lr->spread; /* save states */ rbuf = buf + lr->nstates * 10; for (i = lr->nstates, state = lr->states; --i >= 0; state++) { buf = ss_save(state, buf, &rbuf); } buf = rbuf; /* save packed mapping */ memcpy(buf, lr->data, lr->spread + 2); buf += lr->spread + 2; memcpy(buf, lr->check, lr->spread + 2); lr->srpchanged = FALSE; if (lr->nstates == lr->nexpanded) { /* no tmp data */ if (lr->tmpstr != (string *) NULL) { str_del(lr->tmpstr); } lr->tmpstr = *s2 = (string *) NULL; return TRUE; } if (!lr->tmpchanged) { /* no changes in tmp data */ *s2 = lr->tmpstr; return TRUE; } if (lr->tmpstr != (string *) NULL) { str_del(lr->tmpstr); } str_ref(lr->tmpstr = *s2 = str_new((char *) NULL, (long) lr->tmpsize)); buf = (*s2)->text; /* tmp header */ *buf++ = 0; *buf++ = lr->nitem >> 8; *buf++ = lr->nitem; *buf++ = lr->nshift >> 8; *buf++ = lr->nshift; /* save items */ for (i = lr->nstates, state = lr->states; --i >= 0; state++) { buf = it_save(state->items, buf, lr->grammar); } /* shift data */ memcpy(buf, lr->shtab, lr->nshift); lr->tmpchanged = FALSE; return TRUE; } /* * NAME: srp->pack() * DESCRIPTION: add a new set of shifts and gotos to the packed mapping */ static int srp_pack(lr, from, to, n, check) register srp *lr; short *from, *to; register int n; unsigned short *check; { register int i, j; register char *p; char *shifts; shlink *sl; Int *offstab; int offset, range; /* * check hash table */ shifts = ALLOCA(char, j = 4 * n + 6); p = shifts + 4; *p++ = n >> 8; *p++ = n; for (i = 0; i < n; i++) { *p++ = from[i] >> 8; *p++ = from[i]; *p++ = to[i] >> 8; *p++ = to[i]; } sl = sl_hash(lr->shhtab, lr->shhsize, &lr->slc, lr->shtab, shifts, j); if (sl->shifts >= 0) { /* same as before */ AFREE(shifts); p = lr->shtab + sl->shifts; *check = (UCHAR(p[0]) << 8) + UCHAR(p[1]); return (short) ((UCHAR(p[2]) << 8) + UCHAR(p[3])); } /* not in hash table */ if (lr->nshift + j > lr->shtsize) { /* grow shift table */ i = (lr->nshift + j) * 2; lr->shtab = REALLOC(lr->shtab, char, lr->shtsize, i); lr->shtsize = i; } sl->shifts = lr->nshift; lr->nshift += j; lr->tmpsize += j; lr->tmpchanged = TRUE; memcpy(lr->shtab + sl->shifts, shifts, j); AFREE(shifts); /* create offset table */ offstab = ALLOCA(Int, n); for (i = n; --i >= 0; ) { offstab[i] = from[i] * 2; } j = offset = offstab[0]; for (i = 1; i < n; i++) { offstab[i] -= j; j += offstab[i]; } range = j - offset + 2; /* * add from/to pairs to packed mapping */ for (i = lr->gap, p = &lr->check[i]; UCHAR(p[0]) != 0xff; i += 2, p += 2) ; lr->gap = i; for (;;) { next: if (i + range >= lr->mapsize) { /* grow tables */ j = (i + range) << 1; if (lr->alloc) { lr->data = REALLOC(lr->data, char, lr->mapsize, j); lr->check = REALLOC(lr->check, char, lr->mapsize, j); } else { char *table; table = ALLOC(char, j); memcpy(table, lr->data, lr->mapsize); lr->data = table; table = ALLOC(char, j); memcpy(table, lr->check, lr->mapsize); lr->check = table; lr->alloc = TRUE; } memset(lr->data + lr->mapsize, '\0', j - lr->mapsize); memset(lr->check + lr->mapsize, '\xff', j - lr->mapsize); lr->mapsize = j; } /* match each symbol with free slot */ for (j = 1; j < n; j++) { p += offstab[j]; if (UCHAR(p[0]) != 0xff) { p = &lr->check[i]; do { i += 2; p += 2; } while (UCHAR(p[0]) != 0xff); goto next; } } AFREE(offstab); /* free slots found: adjust spread */ if (i + range > lr->spread) { lr->srpsize += 2 * (i + range - lr->spread); lr->srpchanged = TRUE; lr->spread = i + range; } /* add to packed mapping */ offset = i - offset; do { j = from[--n] * 2 + offset; p = &lr->data[j]; *p++ = to[n] >> 8; *p = to[n]; p = &lr->check[j]; *p++ = i >> 8; *p = i; } while (n != 0); p = lr->shtab + sl->shifts; *p++ = i >> 8; *p++ = i; *check = i; i = offset / 2; *p++ = i >> 8; *p = i; return i; } } /* * NAME: cmp() * DESCRIPTION: compare two shorts */ static int cmp(sh1, sh2) cvoid *sh1, *sh2; { return (*(short *) sh1 < *(short *) sh2) ? -1 : (*(short *) sh1 == *(short *) sh2) ? 0 : 1; } /* * NAME: srp->expand() * DESCRIPTION: expand a state */ static srpstate *srp_expand(lr, state) register srp *lr; srpstate *state; { register int i, n; register char *p; register item *it; item **itemtab, *next; short *tokens, *symbols, *targets; srpstate *newstate; int nred, nshift, ngoto; if (state - lr->states == 1) { /* final state */ state->nred = 0; lr->srpchanged = TRUE; lr->nexpanded++; return state; } if (lr->sthtab == (unsigned short *) NULL) { srp_loadtmp(lr); /* load tmp info */ } n = lr->ntoken + lr->nprod; itemtab = ALLOCA(item*, n); memset(itemtab, '\0', n * sizeof(item*)); symbols = ALLOCA(short, n); targets = ALLOCA(short, n); tokens = ALLOCA(short, lr->ntoken); nred = nshift = ngoto = 0; /* * compute closure of kernel item set */ for (it = state->items; it != (item *) NULL; it = it->next) { i = it->offset; p = it->ref + 1; if (i == UCHAR(*p++)) { /* end of production */ nred++; } else { p += i; n = (UCHAR(p[0]) << 8) + UCHAR(p[1]); if (n >= lr->ntoken) { p = lr->grammar + 12 + (n << 1); p = lr->grammar + (UCHAR(p[0]) << 8) + UCHAR(p[1]); for (i = (UCHAR(p[0]) << 8) + UCHAR(p[1]), p += 2; --i >= 0; ) { it_add(&lr->itc, &state->items, p, n, 0, FALSE); p += UCHAR(p[1]) + 2; } } } } state->nred = nred; if (nred != 0) { if (nred > 1) { state->reds.a = ALLOC(char, (nred << 2)); state->alloc = TRUE; } lr->nred += nred; lr->srpsize += nred * 4; nred = 0; } /* * compute reductions and shifts */ if (state == lr->states) { symbols[ngoto++] = lr->ntoken; } for (it = state->items; it != (item *) NULL; it = it->next) { p = it->ref; if (it->offset == UCHAR(p[1])) { /* reduction */ n = p - lr->grammar; p = &REDA(state)[nred++ << 2]; *p++ = n >> 8; *p++ = n; *p++ = it->ruleno >> 8; *p = it->ruleno; } else { /* shift/goto */ p += 2 + it->offset; n = (UCHAR(p[0]) << 8) + UCHAR(p[1]); if (itemtab[n] == (item *) NULL) { if (n < lr->ntoken) { tokens[nshift++] = n; } else { symbols[ngoto++] = n; } } it_add(&lr->itc, &itemtab[n], it->ref, it->ruleno, it->offset + 2, TRUE); } } /* * delete non-kernel items */ for (it = state->items, i = state->nitem; --i > 0; it = it->next) ; next = it->next; it->next = (item *) NULL; for (it = next; it != (item *) NULL; it = it_del(lr->itc, it)) ; /* * sort and merge token and goto tables */ qsort(symbols, ngoto, sizeof(short), cmp); memcpy(symbols + ngoto, tokens, nshift * sizeof(short)); AFREE(tokens); tokens = symbols + ngoto; qsort(tokens, nshift, sizeof(short), cmp); /* * create target table */ for (i = 0; i < nshift + ngoto; i++) { newstate = &lr->states[lr->nstates]; newstate->items = itemtab[symbols[i]]; n = ss_hash(lr->sthtab, lr->sthsize, lr->states, lr->nstates); targets[i] = n; if (n == lr->nstates) { /* * new state */ n = 0; for (it = newstate->items; it != (item *) NULL; it = it->next) { n++; } lr->srpsize += 10; lr->nitem += n; lr->tmpsize += 5 * n; lr->tmpchanged = TRUE; newstate->nitem = n; newstate->nred = -1; newstate->shoffset = NOSHIFT; newstate->shcheck = 0; newstate->gtoffset = 0; newstate->alloc = FALSE; if (++lr->nstates == lr->sttsize) { /* grow table */ n = state - lr->states; lr->states = REALLOC(lr->states, srpstate, lr->nstates, lr->sttsize <<= 1); state = lr->states + n; } } } /* * add shifts and gotos to packed mapping */ if (nshift != 0) { state->shoffset = srp_pack(lr, tokens, targets + ngoto, nshift, &state->shcheck); } if (ngoto != 0) { unsigned short dummy; state->gtoffset = srp_pack(lr, symbols, targets, ngoto, &dummy); } AFREE(targets); AFREE(symbols); AFREE(itemtab); lr->srpchanged = TRUE; lr->nexpanded++; return state; } /* * NAME: srp->check() * DESCRIPTION: fetch reductions for a given state, possibly first expanding it */ int srp_check(lr, num, nredp, redp) register srp *lr; int num; int *nredp; char **redp; { register srpstate *state; state = &lr->states[num]; if (state->nred < 0) { state = srp_expand(lr, state); if (lr->tmpsize > USHRT_MAX) { int save; /* * too much temporary data: attempt to expand all states */ save = state - lr->states; for (state = lr->states; lr->nstates != lr->nexpanded; state++) { if (lr->srpsize > USHRT_MAX) { return -1; /* too big */ } if (state->nred < 0) { state = srp_expand(lr, state); } } state = &lr->states[save]; } if (lr->srpsize > USHRT_MAX) { return -1; /* too big */ } } *nredp = state->nred; *redp = REDA(state); return lr->nstates; } /* * NAME: srp->shift() * DESCRIPTION: shift to a new state, if possible */ int srp_shift(lr, num, token) register srp *lr; int num, token; { register int n; register char *p; srpstate *state; state = &lr->states[num]; n = state->shoffset; if (n != NOSHIFT) { n = (n + token) * 2; if (n >= 0 && n < lr->mapsize) { p = &lr->check[n]; if ((UCHAR(p[0]) << 8) + UCHAR(p[1]) == state->shcheck) { /* shift works: return new state */ p = &lr->data[n]; return (UCHAR(p[0]) << 8) + UCHAR(p[1]); } } } /* shift failed */ return -1; } /* * NAME: srp->goto() * DESCRIPTION: goto a new state */ int srp_goto(lr, num, symb) register srp *lr; int num, symb; { register char *p; p = &lr->data[(lr->states[num].gtoffset + symb) * 2]; return (UCHAR(p[0]) << 8) + UCHAR(p[1]); }