4

の特定のインスタンスによって文字列の最初の文字として一致する可能性のあるすべての文字のセットを計算できるようにしたいと考えています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 ライブラリにアクセスできることに注意してください (それだけの価値があります)。

4

2 に答える 2

4

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

いくつかのことは単純です:

  • シーケンス: first(r1r2) = first(r1) + ( if '' in first(r1) first(r2) else empty set )
  • 代替: 最初(r1|r2) = 最初(r1) + 最初(r2)
  • 反復: first(r*) = first(r) + ''
  • 文字: first(c) = c
  • 文字クラス: first([c1-cn]) = set(c1, c2, ..., cn) ...

これを、正規表現の方言が知っているすべてのプリミティブと特別なフラグに拡張してください。

于 2009-04-24T19:09:02.797 に答える
1

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

  • 囲んでいる括弧を取り除き、再帰的に呼び出します。
  • トップレベルの代替で分割し、各部分を再帰的に呼び出します。
  • 代替手段がない場合は、
    • 左から最初の省略可能なシンボルまでのすべてのシンボルを出力します。
    • 文字グループがある場合は、すべての記号を出力します。

このアイデアにはおそらく多くの誤りがありますが、これは私が試してみたいものです。アサーション、グループ名、その他何千ものものを取り除かなければなりません。また、[^0-9] のような反転文字クラスが見つかった場合は、多くの文字を出力する必要があります。

ですから、これは本当に複雑な問題だと思います。

于 2009-04-24T19:14:22.080 に答える