正規表現パターンにマッチした最初の文字セットを判別できますか？

Question

最初に文字に一致する可能性のあるすべての文字のセットを、文字列の中のある特定のインスタンスjava.util.regex.Patternで計算したいと考えています。より正式には、特定の正規表現に相当するDFAを仮定すると、すべての発信トランジションのセットが開始状態から必要です。

例：

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

任意のアイデア：

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

セットfirstには、次の要素が含まれている必要がありますか？私は自分自身でDFAを構築し、そのような状態を決定することができることをよく承知していますが、そのような面倒を避けたいと思います（読んでください：私にはそれほど価値がありません）。私のホスト言語は実際にはScalaなので、Scalaの中核となるすべてのライブラリにアクセスすることができます（これは価値があります）。

Answer 1

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

いくつかのものは単純です：

• 順序：最初の（R1R2）=最初の（R1）+（）最初（R2）最初の（R1における '' 場合は、他の空のセット）
• 交替：最初の最初|（R1、R2）=最初の（R1）+（R2）
• 反復：最初の（R *）=最初の（R）+ [
• 文字 '：最初の（C）= C
• Characterclasses：最初（[c1-cn]）=セット（c1、c2、...、cn） ...

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

Answer 2

あなたはrecursivly括弧を囲むの...

• ストリップを、それを解決し、recursivlyを呼び出すことができます。
• トップレベルの選択肢で分割し、各部分を繰り返し呼び出します。
• 何の選択肢がない場合
、
• 出力最初なしオプションシンボルに左アップから始まるすべてのシンボル。
• 文字グループがある場合は、すべてのシンボルを出力します。

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

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