From dec64ca4eac5bb06d892756018f842293ad20006 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 cafb61533f5bfb989698e3924f97471498b2422b. * lib/dfa.c (dfaanalyze): Calculate backward transition for not only concatenation but closure. --- lib/dfa.c | 12 ++++++++++++ 1 files changed, 12 insertions(+), 0 deletions(-) diff --git a/lib/dfa.c b/lib/dfa.c index 746c7b5..a7305ec 100644 --- a/lib/dfa.c +++ b/lib/dfa.c @@ -2701,6 +2701,18 @@ 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; + position *p = firstpos - stk[-1].nfirstpos; + 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