Regexパターンに一致する最初の文字のセットを決定できますか？

StackOverflow https://stackoverflow.com/questions/787134

質問

私はすべてのキャラクターのセットを計算できるようにしたいと思います。 最初 の特定のインスタンスによる文字列内の文字 java.util.regex.Pattern. 。より正式には、DFAが特定の正規表現に相当することを考えると、開始状態からのすべての発信遷移のセットが必要です。

例：

Pattern p = Pattern.compile("[abc]def|daniel|chris|\\s+");
Set<Character> first = getFirstSet(p);

セット first 次の要素を含める必要があります。

{ 'a', 'b', 'c', 'd', ' ', '\n', '\r', '\t' }

何か案は？私は自分でDFAを構築し、関連する状態をそのように決定できることをよく知っていますが、そのような面倒を避けたいです（読む：それは私にとってそれほど価値はありません）。私のホスト言語は実際にはScalaであるため、すべてのコアScala Libsにアクセスできることに注意してください。

役に立ちましたか？

解決

正規表現を解析し、左から右のマナーで解析された正規表現で動作する再帰関数を定義し、そのような一連の最初のセットを構築できると思います。

いくつかのことは簡単です：

  • シーケンス：first（r1r2）= first（r1） +（if '' in first（r1）first（r2）else empty set）
  • 代替：first（r1 | r2）= first（r1） + first（r2）
  • 反復：first（r*）= first（r） + ''
  • 文字：最初（c）= c
  • キャラクタークラス：first（[c1-cn]）= set（c1、c2、...、cn）...

これをすべてのプリミティブと特別な旗に拡張しますあなたの正規表現方言は知っています、そしてあなたは行ってもいいです。

他のヒント

あなたはそれを再帰的に解決することができます...

  • 括弧を囲むストリップの括弧で繰り返し電話します。
  • トップレベルの代替品で分割し、各部品の再帰的に電話します。
  • 代替手段がない場合、
    • 左から最初のオプションのシンボルまでのすべてのシンボルを出力します。
    • Charachterグループがある場合、すべてのシンボルを出力します。

このアイデアにはおそらく多くのエラーがありますが、これが私が試してみることです。あなたは、アサーション、グループ名、その他1000を削除する必要があります。また、[^0-9]のような逆キャラクタークラスを見つけた場合、多くの文字を出力する必要があります。

だから私はそれが本当に複雑な問題だと思います。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top