From: Robert Klemme <shortcutter@...>
Date: 2007-04-18T16:55:08+09:00
Subject: Re: Slow ruby regexes

On 17.04.2007 20:17, MenTaLguY wrote:
> 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.

Ah!  I reckon this a specialty of GNU sed:

09:45:46 [~]: sed -ne 's#a\|b#A#gp' <<X
 > aaaa
 > bbbb
 > X
AAAA
AAAA
09:46:02 [~]:

On an old Solaris box I get

bash-2.03# sed -ne 's#a|b#A#gp' <<X
 > aaaaa
 > bbbbb
 > X
bash-2.03#

Of course GNU sed is more capable than "standard" sed...

> 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.

Kind regards

	robert