From: MenTaLguY <mental@...>
Date: 2007-04-14T13:33:48+09:00
Subject: Re: Slow ruby regexes

--=-eLdkntk2YfmG8l9RGh49
Content-Type: text/plain
Content-Transfer-Encoding: quoted-printable

On Sat, 2007-04-14 at 06:50 +0900, Robert Klemme wrote:
> > Nope, you can effectively prioritize alternatives with DFAs, the same
> > way you can specify greedy/non-greedy matches.  NFAs and DFAs _really
> > are_ equivalent in expressiveness.
>=20
> How do you do that?

Let's use a real simple example:  /^(?:(ab)|(..))$/

Here, we want capturing subexpression 1 to have priority over capturing
subexpression 2.  This time, I'll use a [] notation to annotate
transitions with capture boundaries and priorities.

First, the NFA:

 start: ('' [start $1]->group_1 | '' [start $2]->group_2),
 group_1: ('a' ->group_1b),
 group_1b: ('b' [end $1,priority 1]->final),
 group_2: (any ->group_2b),
 group_2b: (any [end $2,priority 0]->final)

Now, the equivalent DFA:

 {start}: ('' [start $1,start $2]->{group_1,group_2}),
 {group_1,group_2}: (
   'a' ->{group_1b,group_2b} |
   (any-'a') ->{group_2b}
 ),
 {group_1b,group_2b}: (
   'b' [end $1]->{final} |
   (any-'b') [end $2]->{final}
 )
 {group_2b}: (any [end $2]->{final})

See how that works?

More complex examples can be attacked using the same principles, though
it gets painful to work by hand pretty fast.

-mental

--=-eLdkntk2YfmG8l9RGh49
Content-Type: application/pgp-signature; name=signature.asc
Content-Description: This is a digitally signed message part

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (GNU/Linux)

iD8DBQBGIFmpSuZBmZzm14ERAomIAKDT4xgwzMN9kLSaXGFiIy7Jwte3RgCglEYC
XEpQtL86jjUDI8Dk80pxZ9E=
=sPqJ
-----END PGP SIGNATURE-----

--=-eLdkntk2YfmG8l9RGh49--