| /* |
| Copyright 2002-2003 John Plevyak, All Rights Reserved |
| */ |
| |
| #include "d.h" |
| |
| #define INITIAL_ALLITEMS 3359 |
| |
| #define item_hash(_i) \ |
| (((uint)(_i)->rule->index << 8) + \ |
| ((uint)((_i)->kind != ELEM_END ? (_i)->index : (_i)->rule->elems.n))) |
| |
| static int |
| insert_item(State *s, Elem *e) { |
| Item *i = e; |
| if (set_add(&s->items_hash, i)) { |
| vec_add(&s->items, i); |
| return 1; |
| } |
| return 0; |
| } |
| |
| static int |
| itemcmp(const void *ai, const void *aj) { |
| uint i = item_hash(*(Item**)ai); |
| uint j = item_hash(*(Item**)aj); |
| return (i > j) ? 1 : ((i < j) ? -1 : 0); |
| } |
| |
| static State * |
| new_state() { |
| State *s = MALLOC(sizeof(State)); |
| memset(s, 0, sizeof(State)); |
| return s; |
| } |
| |
| static void |
| free_state(State *s) { |
| vec_free(&s->items); |
| vec_free(&s->items_hash); |
| FREE(s); |
| } |
| |
| static State * |
| maybe_add_state(Grammar *g, State *s) { |
| int i, j; |
| |
| for (i = 0; i < g->states.n; i++) { |
| if (s->hash == g->states.v[i]->hash && |
| s->items.n == g->states.v[i]->items.n) { |
| for (j = 0; j < s->items.n; j++) |
| if (s->items.v[j] != g->states.v[i]->items.v[j]) |
| goto Lcont; |
| free_state(s); |
| return g->states.v[i]; |
| Lcont:; |
| } |
| } |
| s->index = g->states.n; |
| vec_add(&g->states, s); |
| return s; |
| } |
| |
| static Elem * |
| next_elem(Item *i) { |
| if (i->index + 1 >= i->rule->elems.n) |
| return i->rule->end; |
| else |
| return i->rule->elems.v[i->index + 1]; |
| } |
| |
| static State * |
| build_closure(Grammar *g, State *s) { |
| int j, k; |
| |
| for (j = 0; j < s->items.n; j++) { |
| Item *i = s->items.v[j]; |
| Elem *e = i; |
| if (e->kind == ELEM_NTERM) { |
| Production *pp = e->e.nterm; |
| for (k = 0; k < e->e.nterm->rules.n; k++) |
| insert_item(s, pp->rules.v[k]->elems.v ? |
| pp->rules.v[k]->elems.v[0] : pp->rules.v[k]->end); |
| } |
| } |
| qsort(s->items.v, s->items.n, sizeof(Item*), itemcmp); |
| s->hash = 0; |
| for (j = 0; j < s->items.n; j++) |
| s->hash += item_hash(s->items.v[j]); |
| return maybe_add_state(g, s); |
| } |
| |
| static Elem * |
| clone_elem(Elem *e) { |
| Elem *ee = MALLOC(sizeof(*ee)); |
| memcpy(ee, e, sizeof(*ee)); |
| return ee; |
| } |
| |
| static void |
| add_goto(State *s, State *ss, Elem *e) { |
| Goto *g = MALLOC(sizeof(Goto)); |
| g->state = ss; |
| g->elem = clone_elem(e); |
| vec_add(&s->gotos, g); |
| } |
| |
| static void |
| build_state_for(Grammar *g, State *s, Elem *e) { |
| int j; |
| Item *i; |
| State *ss = NULL; |
| |
| for (j = 0; j < s->items.n; j++) { |
| i = s->items.v[j]; |
| if (i->kind != ELEM_END && i->kind == e->kind && |
| i->e.term_or_nterm == e->e.term_or_nterm) |
| { |
| if (!ss) ss = new_state(); |
| insert_item(ss, next_elem(i)); |
| } |
| } |
| if (ss) |
| add_goto(s, build_closure(g, ss), e); |
| } |
| |
| static void |
| build_new_states(Grammar *g) { |
| int i, j; |
| State *s; |
| Elem e; |
| |
| for (i = 0; i < g->states.n; i++) { |
| s = g->states.v[i]; |
| for (j = 0; j < g->terminals.n; j++) { |
| e.kind = ELEM_TERM; |
| e.e.term = g->terminals.v[j]; |
| build_state_for(g, s, &e); |
| } |
| for (j = 0; j < g->productions.n; j++) { |
| e.kind = ELEM_NTERM; |
| e.e.nterm = g->productions.v[j]; |
| build_state_for(g, s, &e); |
| } |
| } |
| } |
| |
| static void |
| build_states_for_each_production(Grammar *g) { |
| int i; |
| for (i = 0; i < g->productions.n; i++) |
| if (!g->productions.v[i]->internal && g->productions.v[i]->elem) { |
| State *s = new_state(); |
| insert_item(s, g->productions.v[i]->elem); |
| g->productions.v[i]->state = build_closure(g, s); |
| } |
| } |
| |
| uint |
| elem_symbol(Grammar *g, Elem *e) { |
| if (e->kind == ELEM_NTERM) |
| return e->e.nterm->index; |
| else |
| return g->productions.n + e->e.term->index; |
| } |
| |
| static int |
| gotocmp(const void *aa, const void *bb) { |
| Goto *a = *(Goto **)aa, *b = *(Goto **)bb; |
| int i = a->state->index, j = b->state->index; |
| return ((i > j) ? 1 : ((i < j) ? -1 : 0)); |
| } |
| |
| static void |
| sort_Gotos(Grammar *g) { |
| int i; |
| |
| for (i = 0; i < g->states.n; i++) { |
| VecGoto *vg = &g->states.v[i]->gotos; |
| qsort(vg->v, vg->n, sizeof(Goto*), gotocmp); |
| } |
| } |
| |
| static void |
| build_LR_sets(Grammar *g) { |
| State *s = new_state(); |
| insert_item(s, g->productions.v[0]->rules.v[0]->elems.v[0]); |
| build_closure(g, s); |
| build_states_for_each_production(g); |
| build_new_states(g); |
| sort_Gotos(g); |
| } |
| |
| static Action * |
| new_Action(Grammar *g, int akind, Term *aterm, Rule *arule, State *astate) { |
| Action *a = MALLOC(sizeof(Action)); |
| a->kind = akind; |
| a->term = aterm; |
| a->rule = arule; |
| a->state = astate; |
| a->index = g->action_count++; |
| return a; |
| } |
| |
| static void |
| add_action(Grammar *g, State *s, int akind, Term *aterm, |
| Rule *arule, State *astate) |
| { |
| int i; |
| Action *a; |
| |
| if (akind == ACTION_REDUCE) { |
| /* eliminate duplicates */ |
| for (i = 0; i < s->reduce_actions.n; i++) |
| if (s->reduce_actions.v[i]->rule == arule) |
| return; |
| a = new_Action(g, akind, aterm, arule, astate); |
| vec_add(&s->reduce_actions, a); |
| } else { |
| /* eliminate duplicates */ |
| for (i = 0; i < s->shift_actions.n; i++) |
| if (s->shift_actions.v[i]->term == aterm && |
| s->shift_actions.v[i]->state == astate && |
| s->shift_actions.v[i]->kind == akind) |
| return; |
| a = new_Action(g, akind, aterm, arule, astate); |
| vec_add(&s->shift_actions, a); |
| } |
| } |
| |
| static void |
| init_LR(Grammar *g) { |
| g->action_count = 0; |
| } |
| |
| static int |
| actioncmp(const void *aa, const void *bb) { |
| Action *a = *(Action **)aa, *b = *(Action **)bb; |
| int i, j; |
| if (a->kind == ACTION_SHIFT) |
| i = a->term->index + 1000000; |
| else |
| i = a->rule->index; |
| if (b->kind == ACTION_SHIFT) |
| j = b->term->index + 1000000; |
| else |
| j = b->rule->index; |
| return ((i > j) ? 1 : ((i < j) ? -1 : 0)); |
| } |
| |
| void |
| sort_VecAction(VecAction *v) { |
| qsort(v->v, v->n, sizeof(Action*), actioncmp); |
| } |
| |
| static void |
| build_actions(Grammar *g) { |
| int x, y, z; |
| State *s; |
| Elem *e; |
| |
| for (x = 0; x < g->states.n; x++) { |
| s = g->states.v[x]; |
| for (y = 0; y < s->items.n; y++) { |
| e = s->items.v[y]; |
| if (e->kind != ELEM_END) { |
| if (e->kind == ELEM_TERM) { |
| for (z = 0; z < s->gotos.n; z++) { |
| if (s->gotos.v[z]->elem->e.term == e->e.term) |
| add_action(g, s, ACTION_SHIFT, |
| e->e.term, 0, s->gotos.v[z]->state); |
| } |
| } |
| } else if (e->rule->prod->index) |
| add_action(g, s, ACTION_REDUCE, NULL, e->rule, 0); |
| else |
| s->accept = 1; |
| } |
| sort_VecAction(&s->shift_actions); |
| sort_VecAction(&s->reduce_actions); |
| } |
| } |
| |
| State * |
| goto_State(State *s, Elem *e) { |
| int i; |
| for (i = 0; i < s->gotos.n; i++) |
| if (s->gotos.v[i]->elem->e.term_or_nterm == e->e.term_or_nterm) |
| return s->gotos.v[i]->state; |
| return NULL; |
| } |
| |
| static Hint * |
| new_Hint(uint d, State *s, Rule *r) { |
| Hint *h = MALLOC(sizeof(*h)); |
| h->depth = d; |
| h->state = s; |
| h->rule = r; |
| return h; |
| } |
| |
| static int |
| hintcmp(const void *ai, const void *aj) { |
| Hint *i = *(Hint**)ai; |
| Hint *j = *(Hint**)aj; |
| return |
| (i->depth > j->depth) ? 1 : ( |
| (i->depth < j->depth) ? -1 : ( |
| (i->rule->index > j->rule->index) ? 1 : ( |
| (i->rule->index < j->rule->index) ? -1 : 0))); |
| } |
| |
| static void |
| build_right_epsilon_hints(Grammar *g) { |
| int x, y, z; |
| State *s, *ss; |
| Elem *e; |
| Rule *r; |
| |
| for (x = 0; x < g->states.n; x++) { |
| s = g->states.v[x]; |
| for (y = 0; y < s->items.n; y++) { |
| e = s->items.v[y]; |
| r = e->rule; |
| if (e->kind != ELEM_END) { |
| for (z = e->index; z < r->elems.n; z++) { |
| if ((r->elems.v[z]->kind != ELEM_NTERM || |
| !r->elems.v[z]->e.nterm->nullable)) |
| goto Lnext; |
| } |
| ss = s; |
| for (z = e->index; z < r->elems.n; z++) |
| ss = goto_State(ss, r->elems.v[z]); |
| if (ss && r->elems.n) |
| vec_add(&s->right_epsilon_hints, |
| new_Hint(r->elems.n - e->index - 1, ss, r)); |
| else /* ignore for states_for_each_productions */; |
| } |
| Lnext:; |
| } |
| if (s->right_epsilon_hints.n > 1) |
| qsort(s->right_epsilon_hints.v, s->right_epsilon_hints.n, |
| sizeof(Hint*), hintcmp); |
| } |
| } |
| |
| static void |
| build_error_recovery(Grammar *g) { |
| int i, j, k, depth; |
| State *s; |
| Rule *r, *rr; |
| Elem *e, *ee; |
| |
| for (i = 0; i < g->states.n; i++) { |
| s = g->states.v[i]; |
| for (j = 0; j < s->items.n; j++) { |
| r = s->items.v[j]->rule; |
| if (r->elems.n > 1 && |
| r->elems.v[r->elems.n - 1]->kind == ELEM_TERM && |
| r->elems.v[r->elems.n - 1]->e.term->kind == TERM_STRING) |
| { |
| depth = s->items.v[j]->index; |
| e = r->elems.v[r->elems.n - 1]; |
| for (k = 0; k < s->error_recovery_hints.n; k++) { |
| rr = s->error_recovery_hints.v[k]->rule; |
| ee = rr->elems.v[rr->elems.n - 1]; |
| if (e->e.term->string_len == ee->e.term->string_len && |
| !strcmp(e->e.term->string, ee->e.term->string)) |
| { |
| if (s->error_recovery_hints.v[k]->depth > depth) |
| s->error_recovery_hints.v[k]->depth = depth; |
| goto Ldone; |
| } |
| } |
| vec_add(&s->error_recovery_hints, new_Hint(depth, NULL, r)); |
| Ldone:; |
| } |
| } |
| qsort(s->error_recovery_hints.v, s->error_recovery_hints.n, |
| sizeof(Hint*), hintcmp); |
| } |
| } |
| |
| void |
| build_LR_tables(Grammar *g) { |
| init_LR(g); |
| build_LR_sets(g); |
| build_actions(g); |
| build_right_epsilon_hints(g); |
| build_error_recovery(g); |
| } |