From 77b787ce5d6c418f33adac83ca1ba48028d96bed Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Thu, 3 Jan 2019 09:53:57 +0000 Subject: [PATCH] Small simplifications in GOR1 initialization phase. Instead of using two stacks to weed out low-precedence initial configurations with duplicate target state, let them remain on the bottom of topsort stack, which effectively makes them ignored. --- re2c/src/dfa/closure_posix.cc | 17 ++++++++--------- 1 file changed, 8 insertions(+), 9 deletions(-) diff --git a/re2c/src/dfa/closure_posix.cc b/re2c/src/dfa/closure_posix.cc index 96843f54..1d5b2cfe 100644 --- a/re2c/src/dfa/closure_posix.cc +++ b/re2c/src/dfa/closure_posix.cc @@ -64,21 +64,20 @@ void closure_posix_gor1(determ_context_t &ctx) done.clear(); - // Initialization: topsort stack must contain configurations with - // unique target state, ordered from the highest POSIX precedence - // (on top) to the lowest precedence (at the bottom). + // initialization: topsort stack must contain configurations + // ordered by POSIX precedence (with highest precedence on top) std::sort(init.begin(), init.end(), cmp_gor1_t(ctx)); - for (cclositer_t c = init.begin(); c != init.end(); ++c) { + for (rcclositer_t c = init.rbegin(); c != init.rend(); ++c) { q = c->state; if (q->clos == NOCLOS) { q->clos = static_cast(done.size()); done.push_back(*c); - linear.push(q); } - } - for (; !linear.empty(); ) { - topsort.push(linear.top()); - linear.pop(); + else { + // duplicate state, but higher precedence => overwrite + done[q->clos] = *c; + } + topsort.push(q); } for (; !topsort.empty(); ) { -- 2.50.1