From: Tanaka Akira <akr@...17n.org>
Date: 2002-04-04T18:29:56+09:00
Subject: [ruby-dev:16751] Re: sharing sub-regexp

In article <20020403113824.A7FE78CF@helium.ruby-lang.org>,
  "K.Kosako" <kosako@sofnec.co.jp> writes:

> 1. DFA$B$N5-=RJ}K!(B($B7A<0(B)$B$r!";d$OCN$i$J$$!#(B

> 4. Ruby$B$GMxMQ$9$kA0Ds$NOC$G$"$l$P!"5-=R7A<0$N3HD%$H$J$k$N$G!"(B
>    $B;d$,C1FH$G$O7h$a$i$l$J$$!#(B

$B;d$NCN$k8B$j4{B8$N@55,I=8=%Q%C%1!<%8$K$O$3$N$h$&$J5!G=$OB8:_$7$J$$$N$G!"(B
$BFH<+$K@_7W$9$kI,MW$,$"$j$^$9!#(B

$B$^$!!"35G0$H$7$F$OFq$7$$$b$N$G$O$J$$$N$G!"E,Ev$K@_7W$9$l$P$$$$$s$8$c$J(B
$B$$$+$H;W$$$^$9!#(B

$BNc$($P!"(BGrail $B$H$$$&%=%U%H%&%'%"$G$O(B (abc)* $B$KBP1~$9$k(B DFA $B$r<!$N$h$&(B
$B$KI=8=$7$^$9!#(Bhttp://www.csd.uwo.ca/research/grail/

(START) |- 0
0 a 1
1 b 2
2 c 0
0 -| (FINAL)

0, 1, 2 $B$H$$$&(B state $B$,$"$C$F!"A+0\$,0l9TKh$K=q$$$F$"$C$F!"(B(START) $B$H(B
(FINAL) $B$G=i4|>uBV$H<uM}>uBV$r<($9!"$H$$$&46$8$G$9$M!#(B

> 2. $BIT<uM}$N7k2L$r=hM}$9$k$?$a$K!"B?>/$O2~B$(B($BL?NaDI2C!)(B)$B$,I,MW!#(B

$B$U$`!#(B

> 3. DFA$B@lMQ$G:n$C$?$b$N$h$j!"CY$/$J$k$N$G$O$J$$$+!)(B

$B8B3&@-G=$^$G$O5a$a$F$$$^$;$s!#(B
Ruby $B$G<BAu$7$?$b$N$h$j$b==J,$KB.$1$l$P$$$$$H;W$C$F$$$^$9!#(B

> $B54<V$H$OFHN)$K:n@.$7$?$[$&$,!"M-Mx$G$O$J$$$G$7$g$&$+!)(B
> ($B@55,I=8=$N%"%s%+!<Ey$K$h$k8!:w$N:GE,2=5!G=$O!"0UL#$,$J$$$s$G$9$h$M(B)

$B@55,I=8=$NCf$KKd$a9~$_$?$$$H$$$&$N$,0U?^$J$N$G$9!#(B

$BNc$($P!"(B
%r{/\*(
       # */ $B$,4^$^$l$J$$J8;zNs$K%^%C%A$9$k(B DFA
       (START) |- 0
       0 \* 1
       0 / 0
       0 [^/\*] 0
       1 \* 1
       1 [^/\*] 0
       0 -| (FINAL)
       1 -| (FINAL)
      )\*/}x
$B$H$+!#(B

$B$b$&>/$7FbLLE*$JE@$r=R$Y$k$H!"7k6I!";d$K$H$C$F$O!"@55,I=8=$H(B DFA $B$NEy(B
$B2A@-$rCN$C$F$$$F!"(BDFA $B$K$*$$$F4JC1$KI=8=2DG=$G$"$k$3$H$,$o$+$C$F$$$k$K(B
$B$b$+$+$o$i$:$G$-$J$$$H$$$&$3$H$,%U%i%9%H%l!<%7%g%s$K$J$C$F$$$k$N$G!"@5(B
$B5,I=8=$H$$$C$7$g$K;H$$$?$$$H4uK>$H$7$F$$$^$9!#$?$@$7!"8=<B$K$O$5$^$6$^(B
$B$JLdBjE@$"$k$+$b$7$l$^$;$s$+$i$I$&$7$F$b$H$$$&$o$1$G$O$"$j$^$;$s!#$b$7!"(B
$BHf3SE*4JC1$J$i!"$H$$$&$o$1$G$9!#(B

In article <20020404021742.B61F17AD@helium.ruby-lang.org>,
  "K.Kosako" <kosako@sofnec.co.jp> writes:

> $B%5%$%:$,LdBj$@$+$i6&M-$9$k$H$$$&$3$H$O!"(B
> $B85$N%Q%?!<%s$@$1$G$J$/$F!"@8@.$5$l$?%P%$%H%3!<%I$b6&M-$9$k$H$$$&$3$H$G$9$h$M!#(B

$B$O$$!#(B

> $B6&M-$5$l$?ItJ,$N<B9T$r!"4X?t8F$S=P$7$N$h$&$K<B9T$9$k$?$a$K!"(B
> $B%9%?%C%/$HL?Na%3!<%I$N$r?75,DI2C$9$l$P2DG=$G$O$J$$$+$H;W$$$^$9!#(B
> ($B8F$S=P$7$G$O$J$$D>@\<B9T$N>l9g$b!"8F$S=P$7$N$h$&$K<B9T$7$J$1$l$P$$$1$J$$(B
> $B$N$G!"B.EYE*$K$OITMx$H;W$$$^$9$,!#<BMQ$KE,$5$J$$$[$ICY$/$J$k$+$I$&$+$OITL@!#(B)

$B$J$k$[$I!#(B

> $B:#$O!"(B()$B$K$7$+HV9f$r?6$C$F$$$^$;$s$N$G!"L>A0$G;2>H$9$kJ}K!$@$1$K$7$?$[$&$,(B
> $BNI$$$H;W$$$^$9!#(B
> $BL>A0Dj5A%0%k!<%W$HL>A0;2>H$NFs8DJ,!"%N!<%I$N<oN`$rA}$d$7$F$d$l$P$G$-$k$h$&$J(B
> $B5$$,$7$^$9!#(B

$B3N$+$K(B $BHV9f$,(B 2$B<oN`$"$k$H:.Mp$r>7$/$+$bCN$l$^$;$s$M!#(B
-- 
[$BEDCf(B $BE/(B][$B$?$J$+(B $B$"$-$i(B][Tanaka Akira]
$B!V$U$($m(B! $B$o$+$a$A$c$s:n@o$G$9$(C"=$B!W(B(Little Worker, $B7KM7@84](B)