diff options
author | Daniel Veillard <veillard@src.gnome.org> | 2006-11-02 10:28:04 +0000 |
---|---|---|
committer | Daniel Veillard <veillard@src.gnome.org> | 2006-11-02 10:28:04 +0000 |
commit | fcd18ff8f753dd7308b619476266f1a2ddcc8859 (patch) | |
tree | 4dec2c99240c84ed3cd911668fa8b78ac9945e28 /xmlregexp.c | |
parent | 0e05f4c2e0bf18930d4019426de31c9ae4d6411a (diff) | |
download | libxml2-fcd18ff8f753dd7308b619476266f1a2ddcc8859.tar.gz |
another small change on the algorithm for the elimination of epsilon
* xmlregexp.c: another small change on the algorithm for the
elimination of epsilon transitions, should help on #362989 too
Daniel
Diffstat (limited to 'xmlregexp.c')
-rw-r--r-- | xmlregexp.c | 28 |
1 files changed, 6 insertions, 22 deletions
diff --git a/xmlregexp.c b/xmlregexp.c index 9719cd54..fbd0e9f3 100644 --- a/xmlregexp.c +++ b/xmlregexp.c @@ -1738,11 +1738,6 @@ xmlFAEliminateSimpleEpsilonTransitions(xmlRegParserCtxtPtr ctxt) { printf("Changed transition %d on %d to go to %d\n", j, tmp->no, newto); #endif -#if 0 - tmp->trans[j].to = newto; - xmlRegStateAddTransTo(ctxt, ctxt->states[newto], - tmp->no); -#endif tmp->trans[j].to = -1; xmlRegStateAddTrans(ctxt, tmp, tmp->trans[j].atom, ctxt->states[newto], @@ -1751,20 +1746,6 @@ xmlFAEliminateSimpleEpsilonTransitions(xmlRegParserCtxtPtr ctxt) { } } } -#if 0 - for (i = 0;i < ctxt->nbStates;i++) { - tmp = ctxt->states[i]; - for (j = 0;j < tmp->nbTrans;j++) { - if (tmp->trans[j].to == statenr) { - tmp->trans[j].to = newto; -#ifdef DEBUG_REGEXP_GRAPH - printf("Changed transition %d on %d to go to %d\n", - j, tmp->no, newto); -#endif - } - } - } -#endif if (state->type == XML_REGEXP_FINAL_STATE) ctxt->states[newto]->type = XML_REGEXP_FINAL_STATE; /* eliminate the transition completely */ @@ -1809,11 +1790,14 @@ xmlFAEliminateEpsilonTransitions(xmlRegParserCtxtPtr ctxt) { has_epsilon = 0; /* - * build the completed transitions bypassing the epsilons + * Build the completed transitions bypassing the epsilons * Use a marking algorithm to avoid loops - * mark sink states too. + * Mark sink states too. + * Process from the latests states backward to the start when + * there is long cascading epsilon chains this minimize the + * recursions and transition compares when adding the new ones */ - for (statenr = 0;statenr < ctxt->nbStates;statenr++) { + for (statenr = ctxt->nbStates - 1;statenr >= 0;statenr--) { state = ctxt->states[statenr]; if (state == NULL) continue; |