Regular Expression(正規表現) Part17 (284ﾚｽ)

Regular Expression(正規表現) Part17 http://mevius.5ch.net/test/read.cgi/tech/1702684760/

上下前次1-新
通常表示 512ﾊﾞｲﾄ分割 ﾚｽ栞
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん

---

283: デフォルトの名無しさん [sage] 2025/11/03(月) 19:15:39.49 ID:6hs01YZr >>280 自己レス。AI に聞いたら | GNU grepでは、DFA の生成に On-the-Fly（実行時逐次的）な手法を採用していますが、 | それは基本的に部分集合構成法を逐次的に行うことを意味します。 | ε遷移の除去も、このプロセスの中で実質的に On-the-Fly で行われます。 とのことでした。やっぱε-除去も On-the-Fly なのか、ムズいなー >>281 GNU grep の On-the-Fly 法は、到達しない状態ノードを作らないようにすることで 省メモリ化と高速化が目的なので、DFA の構造自体が動的に変わるものではないと思ってました。 で、言われるように後方参照は正規言語のクラスを超えてるので、DFA 型エンジンでは 普通は実現出来ないのだけど、「正規表現技術入門」では | GNU grep は基本的に DFA 型ですが、部分的（後方参照への対応のためなど）に一部 | VM 型のアプローチもとっています。 とかさらっと書いてあるだけで、具体的な記述はないんすよね (やっぱ入門書だな)。 でも言われてみれば、On-the-Fly 的に動的に DFA を構成して行けば、それで後方参照も 実現出来そうな気がしてきた。バックトラックとか面倒そうだけど一考の価値はあるかも GNU grep もそうやって実装してる ? かどうかは分からないけど http://mevius.5ch.net/test/read.cgi/tech/1702684760/283

---

ﾒﾓ帳

(0/65535文字)

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.831s*