Regular Expression(正規表現) Part17 (368ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
280(2): 2025/11/02(日)19:07 ID:vGsY1NrW(1) AAS
「正規表現技術入門」を読むと、GNU grep ではマッチング途中で必要になった部分だけ
オンデマンドで DFA を構成していく On-the-Fly 構成法を使っている、と書かれてるけど
どのレベルから On-the-Fly してるんでしょ ?
部分集合構成法で NFA を DFA に変換する所からなのか、もっと前のε-遷移除去からなのか
あるいはさらに前の正規表現をパースして NFA を作る所も On-the-Fly なんですかね ?
GNU grep のソース見ろと言われそうだけど
283(1): 2025/11/03(月)19:15 ID:6hs01YZr(1) AAS
>>280
自己レス。AI に聞いたら
| GNU grepでは、DFA の生成に On-the-Fly（実行時逐次的）な手法を採用していますが、
| それは基本的に部分集合構成法を逐次的に行うことを意味します。
| ε遷移の除去も、このプロセスの中で実質的に On-the-Fly で行われます。
とのことでした。やっぱε-除去も On-the-Fly なのか、ムズいなー
>>281
GNU grep の On-the-Fly 法は、到達しない状態ノードを作らないようにすることで
省メモリ化と高速化が目的なので、DFA の構造自体が動的に変わるものではないと思ってました。
で、言われるように後方参照は正規言語のクラスを超えてるので、DFA 型エンジンでは
省7
292(1): 2025/11/20(木)00:34 ID:mbRrNt6G(1/2) AAS
DragonBook (第2版) の第3章まで読んだら、>>280 に書いた ε-遷移についての最初の疑問も氷解してしまったので、
一応伏線回収しておきます
「正規表現技術入門」では、ε-遷移を除去した後で部分集合構成法を行う、という流れで記述されていたので、
部分集合構成法を行うには前もって ε-遷移を除去しなければならない、と思い込んでいたのだけど、
その必要は全くなかったのでした
部分集合構成法の処理の中で一つ部分集合が得られたら、その集合の ε-閉包を取って
(その集合に そこから ε-遷移する状態を全て加えて)、それを DFA の 1 状態とすればよいだけなのでした
>>283 に書いた AI の回答が何となく歯切れが悪かった理由もこれで納得出来たわけで、
何でこんな簡単なことを思い付かなかったのか、我ながらアホでしたね
「正規表現技術入門」は章ごとに執筆者が違っていて、VM 型エンジンの章は鬼雲の作者が直々に書いていて説得力があるのですが、
省10
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.571s*