From: MenTaLguY <mental@...>
Date: 2007-04-18T03:17:31+09:00
Subject: Re: Slow ruby regexes

On Wed, 18 Apr 2007 01:10:07 +0900, Robert Klemme <shortcutter@googlemail.com> wrote:
> I was under the impression that this precisely is a point of difference
> between NFA and DFA based engines: sed is DFA based and for all I know
> order in an alternative does not matter while it does matter for the
> typical NFA engine.  Did I get this wrong?

Well, for historical reasons, sed implements only "basic" (versus "extended") regular expressions, so it does not have explicit alternation via the | operator.  However, we can still look at it for an example of how a DFA-based engine can handle choosing between alternatives.

Consider:

  echo "aaaaa" | sed -e 's/^\(a*\)\(a*\)$/\1,\2/'

There are six possible ways to match this regular expression:

  aaaaa,  
  aaaa,a
  aaa,aa
  aa,aaa
  a,aaaa
  ,aaaaa

sed always chooses the first alternative.  Choice between alternatives for explicit alternation would be handled the same way.

-mental