From 9c5a68b9a3f84f2ec77fddfbbc07c617588d1e8a Mon Sep 17 00:00:00 2001 From: Norihiro Tanaka Date: Mon, 14 Sep 2020 22:21:05 +0900 Subject: [PATCH] dfa: fix failure in removal of epsilon closure If there are a espilon in a branch and the closure is iterated, maybe fails in removal of the node. The bug is introduced in commit da0e8454a8e68035ef4b87dbb9097f85df6ece27. * lib/dfa.c (dfaanalyze): Calculate backward transition for not only concatenation but closure. --- lib/dfa.c | 11 +++++++++++ 1 files changed, 11 insertions(+), 0 deletions(-) diff --git a/lib/dfa.c b/lib/dfa.c index 746c7b5..7851fab 100644 --- a/lib/dfa.c +++ b/lib/dfa.c @@ -2701,6 +2701,17 @@ dfaanalyze (struct dfa *d, bool searchflag) case STAR: case PLUS: + /* Every element in the lastpos of the argument is in the backward + set of every element in the firstpos. */ + if (d->epsilon) + { + tmp.elems = lastpos - stk[-1].nlastpos; + tmp.nelem = stk[-1].nlastpos; + for (position *p = firstpos - stk[-1].nfirstpos; + p < firstpos; p++) + merge2 (&backward[p->index], &tmp, &merged); + } + /* Every element in the firstpos of the argument is in the follow of every element in the lastpos. */ { -- 1.7.1