ASTに正規表現を解析するPythonライブラリですか？

Question

強調するために、私は "正規表現を使って解析する"とは思っていません - "正規表現を象徴的な木に解析する" （検索は前者のみを持ち出しています...）

私の使用例：データベース上で正規表現検索を高速化するには、(foo|bar)baz+(bat)*のような正規表現を解析したいと思います。一致。 （この場合は、foo/barが交互になり、batが0回出現するので、ちょうどbazです。）

これを行うには、正規表現の演算子/セマンティクスを理解する必要があります。

In [7]: re.compile('(foo|bar)baz+(bat)', re.DEBUG) 
subpattern 1 
    branch 
    literal 102 
    literal 111 
    literal 111 
    or 
    literal 98 
    literal 97 
    literal 114 
literal 98 
literal 97 
max_repeat 1 4294967295 
    literal 122 
subpattern 2 
    literal 98 
    literal 97 
    literal 116 

しかし、それだけでプリントアウトだし、C-実装は、その後私の知る限り構造を保存しない：re.DEBUGが最も接近します。私のオーナーパーザーを書かずにこれをどのように解析できるかについてのアイデアはありますか？

Answer 1

あなただけの文脈自由文法を使用して（クラシック）正規表現を指定することができます。

regex = { alternatives }; 
alternatives = primitive { '|' alternatives } ; 
primitive = '(' regex ')' | '[' character_set ']' | ... 

これはあなたが正規表現を使用して正規表現を解析（Perlは例外で、 しかし、その「正規表現できないことを意味します"古典的"を超えて拡張されています）。

正規表現を解析するには、独自のパーサーを構築して、何らかの種類のツリー（re.Debugがきれいに近い状態）や望むマジックライブラリを構築する必要があります。

これは簡単な部分だと思います。これは自分自身をすることは大変難しいことではありません。そのようなパーサーを構築するための簡単なスキームについては、 Is there an alternative for flex/bison that is usable on 8-bit embedded systems?を参照してください。

（「必要な部分文字列を」把握するために、例えば）セマンティクス正規表現のを理解するために、あなたはパースツリーの上に散歩アナライザ を構築するとともに、各サブツリーのために逃げることができるかもしれません（下up）、共通文字列を計算します。従来のNDFA構築を実装し、その上を歩かなければならない場合や、NDFAからDFA構築を実装してDFAを操作しなければならない場合があります。実際の正規表現には、組み込みの文字セット、キャプチャグループなどの複雑な複雑さが含まれがちです。

「共通の文字列」は、文字列を狭く定義することはできますが、これは、文字の固定長または可変長のギャップによって分離さいくつかの定数ストリングが含まれる場合があります、例えば、あなたの必要なサブストリングが常に自体は、フォームの「簡単な正規表現」として表現かもしれません：

(<character>+ ?+) <character>+