ruby-dev

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

> 1. DFAの記述方法(形式)を、私は知らない。

> 4. Rubyで利用する前提の話であれば、記述形式の拡張となるので、
>    私が単独では決められない。

私の知る限り既存の正規表現パッケージにはこのような機能は存在しないので、
独自に設計する必要があります。

まぁ、概念としては難しいものではないので、適当に設計すればいいんじゃな
いかと思います。

例えば、Grail というソフトウェアでは (abc)* に対応する DFA を次のよう
に表現します。http://www.csd.uwo.ca/research/grail/

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

0, 1, 2 という state があって、遷移が一行毎に書いてあって、(START) と
(FINAL) で初期状態と受理状態を示す、という感じですね。

> 2. 不受理の結果を処理するために、多少は改造(命令追加？)が必要。

ふむ。

> 3. DFA専用で作ったものより、遅くなるのではないか？

限界性能までは求めていません。
Ruby で実装したものよりも十分に速ければいいと思っています。

> 鬼車とは独立に作成したほうが、有利ではないでしょうか？
> (正規表現のアンカー等による検索の最適化機能は、意味がないんですよね)

正規表現の中に埋め込みたいというのが意図なのです。

例えば、
%r{/\*(
       # */ が含まれない文字列にマッチする DFA
       (START) |- 0
       0 \* 1
       0 / 0
       0 [^/\*] 0
       1 \* 1
       1 [^/\*] 0
       0 -| (FINAL)
       1 -| (FINAL)
      )\*/}x
とか。

もう少し内面的な点を述べると、結局、私にとっては、正規表現と DFA の等
価性を知っていて、DFA において簡単に表現可能であることがわかっているに
もかかわらずできないということがフラストレーションになっているので、正
規表現といっしょに使いたいと希望としています。ただし、現実にはさまざま
な問題点あるかもしれませんからどうしてもというわけではありません。もし、
比較的簡単なら、というわけです。

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

> サイズが問題だから共有するということは、
> 元のパターンだけでなくて、生成されたバイトコードも共有するということですよね。

はい。

> 共有された部分の実行を、関数呼び出しのように実行するために、
> スタックと命令コードのを新規追加すれば可能ではないかと思います。
> (呼び出しではない直接実行の場合も、呼び出しのように実行しなければいけない
> ので、速度的には不利と思いますが。実用に適さないほど遅くなるかどうかは不明。)

なるほど。

> 今は、()にしか番号を振っていませんので、名前で参照する方法だけにしたほうが
> 良いと思います。
> 名前定義グループと名前参照の二個分、ノードの種類を増やしてやればできるような
> 気がします。

確かに 番号が 2種類あると混乱を招くかも知れませんね。
-- 
[田中 哲][たなか あきら][Tanaka Akira]
「ふえろ! わかめちゃん作戦です$(C⊇」(Little Worker, 桂遊生丸)

Thread

Prev Next

In This Thread

Prev Next