From 62cb694d18e211364d664618a705fc6b96a45c51 Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Sun, 15 Sep 2024 13:35:08 -0700 Subject: regex: closure operations don't output epsilon states. * regex.c (nfa_closure, nfa_move_closure): Do not add epsilon states to the output array. We only need to add them to the stack for the spanning traversal. Epsilon states are not real states; they are just a representation of the concept of transitioning to multiple states at the same time. When we add them to the output, they just end up being ignored when nfa_move_closure is called again on that set, since it only cares about states that have real transitions for a character. --- regex.c | 18 ++++++++++++------ 1 file changed, 12 insertions(+), 6 deletions(-) diff --git a/regex.c b/regex.c index 670f9243..7a73d5a6 100644 --- a/regex.c +++ b/regex.c @@ -1292,7 +1292,8 @@ static int nfa_closure(nfa_state_t **stack, nfa_state_t **set, int nin, s->a.visited = visited; stack[stackp++] = s; - set[nout++] = s; + if (!nfa_empty_state_p(s)) + set[nout++] = s; if (nfa_accept_state_p(s)) *accept = 1; if (!moreset && nfa_has_transitions(s)) @@ -1311,7 +1312,8 @@ static int nfa_closure(nfa_state_t **stack, nfa_state_t **set, int nin, if (nfa_test_set_visited(e0, visited)) { stack[stackp++] = e0; - set[nout++] = e0; + if (!nfa_empty_state_p(e0)) + set[nout++] = e0; if (nfa_accept_state_p(e0)) *accept = 1; if (!moreset && nfa_has_transitions(e0)) @@ -1320,7 +1322,8 @@ static int nfa_closure(nfa_state_t **stack, nfa_state_t **set, int nin, if (nfa_test_set_visited(e1, visited)) { stack[stackp++] = e1; - set[nout++] = e1; + if (!nfa_empty_state_p(e1)) + set[nout++] = e1; if (nfa_accept_state_p(e1)) *accept = 1; if (!moreset && nfa_has_transitions(e1)) @@ -1382,7 +1385,8 @@ static int nfa_move_closure(nfa_state_t **stack, nfa_state_t **set, int nin, if (nfa_test_set_visited(mov, visited)) { stack[stackp++] = mov; - set[nout++] = mov; + if (!nfa_empty_state_p(mov)) + set[nout++] = mov; if (nfa_accept_state_p(mov)) *accept = 1; if (!moreset && nfa_has_transitions(mov)) @@ -1403,7 +1407,8 @@ static int nfa_move_closure(nfa_state_t **stack, nfa_state_t **set, int nin, if (nfa_test_set_visited(e0, visited)) { stack[stackp++] = e0; - set[nout++] = e0; + if (!nfa_empty_state_p(e0)) + set[nout++] = e0; if (nfa_accept_state_p(e0)) *accept = 1; if (!moreset && nfa_has_transitions(e0)) @@ -1412,7 +1417,8 @@ static int nfa_move_closure(nfa_state_t **stack, nfa_state_t **set, int nin, if (nfa_test_set_visited(e1, visited)) { stack[stackp++] = e1; - set[nout++] = e1; + if (!nfa_empty_state_p(e1)) + set[nout++] = e1; if (nfa_accept_state_p(e1)) *accept = 1; if (!moreset && nfa_has_transitions(e0)) -- cgit v1.2.3