diff options
Diffstat (limited to 'src/state-item.c')
| -rw-r--r-- | src/state-item.c | 59 |
1 files changed, 22 insertions, 37 deletions
diff --git a/src/state-item.c b/src/state-item.c index 2fa519ed..fea56a59 100644 --- a/src/state-item.c +++ b/src/state-item.c @@ -384,11 +384,10 @@ disable_state_item (state_item *si) bitset_free (si->prods); } -/* disable all transitions and productions that can only be - * reached through this state_item. - */ +/* Disable all state_item paths that lead to/from SI and nowhere + else. */ static void -prune_forward (const state_item *si) +prune_state_item (const state_item *si) { state_item_list queue = gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true, 1, @@ -398,8 +397,16 @@ prune_forward (const state_item *si) { state_item *dsi = (state_item *) gl_list_get_at (queue, 0); gl_list_remove_at (queue, 0); - if (dsi->trans >= 0) - gl_list_add_last (queue, &state_items[dsi->trans]); + if (SI_DISABLED (dsi - state_items)) + continue; + + if (dsi->trans >= 0 && !SI_DISABLED (dsi->trans)) + { + const state_item *trans = &state_items[dsi->trans]; + bitset_reset (trans->revs, dsi - state_items); + if (bitset_empty_p (trans->revs)) + gl_list_add_last (queue, trans); + } if (dsi->prods) { @@ -407,32 +414,15 @@ prune_forward (const state_item *si) state_item_number sin; BITSET_FOR_EACH (biter, dsi->prods, sin, 0) { + if (SI_DISABLED (sin)) + continue; const state_item *prod = &state_items[sin]; bitset_reset (prod->revs, dsi - state_items); if (bitset_empty_p (prod->revs)) gl_list_add_last (queue, prod); } } - if (dsi != si) - disable_state_item (dsi); - } - gl_list_free (queue); -} -/* disable all state_item paths that lead to - * si and nowhere else. - */ -static void -prune_backward (const state_item *si) -{ - state_item_list queue = - gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true, 1, - (const void **) &si); - - while (gl_list_size (queue) > 0) - { - state_item *dsi = (state_item *) gl_list_get_at (queue, 0); - gl_list_remove_at (queue, 0); bitset_iterator biter; state_item_number sin; BITSET_FOR_EACH (biter, dsi->revs, sin, 0) @@ -440,7 +430,9 @@ prune_backward (const state_item *si) if (SI_DISABLED (sin)) continue; state_item *rev = &state_items[sin]; - if (rev->prods) + if (&state_items[rev->trans] == dsi) + gl_list_add_last (queue, rev); + else if (rev->prods) { bitset_reset (rev->prods, dsi - state_items); if (bitset_empty_p (rev->prods)) @@ -449,16 +441,13 @@ prune_backward (const state_item *si) else gl_list_add_last (queue, rev); } - if (dsi != si) - disable_state_item (dsi); + disable_state_item (dsi); } gl_list_free (queue); } -/* - To make searches more efficient, we can prune away paths that are - caused by disabled transitions. - */ +/* To make searches more efficient, prune away paths that are caused + by disabled transitions. */ static void prune_disabled_paths (void) { @@ -466,11 +455,7 @@ prune_disabled_paths (void) { state_item *si = &state_items[i]; if (si->trans == -1 && item_number_is_symbol_number (*si->item)) - { - prune_forward (si); - prune_backward (si); - disable_state_item (si); - } + prune_state_item (si); } } |