Regular Expression(正規表現) Part17 (368ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
281(1): 2025/11/02(日)20:01 ID:JoUIYtII(1/2) AAS
正規表現の枠を超える後方参照（\1）とかで使ってそう
あれが絡むと事前にDFA作れない
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
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.321s*