単純化された正規表現を構文木に変換する

Question

正規表現をDFAに変換するアルゴリズムの実装を進めています。最初のステップでは、入力正規表現を構文木に変換します。たとえば、b（a | b）abcは、下のツリーに変換されます。

   . 
      /\ 
      . c 
     /\ 
      . b 
     /\ 
     . a 
    /\ 
    / \ 
    / \ 
    .  | 
/\ /\ 
    * * a b 
/ \ 
a  b 

また、私が取り扱っております正規表現は、唯一の特殊文字は「\」（エスケープ文字）であること、非常に単純です「|」 （OR演算子）、 '（' '）'（グループを囲む角括弧）、 '*'（クレーンの星）です。今私が抱えている問題は、（Pythonで）どのように（データ構造として）このツリーを入力から生成するかについて混乱しています。私は手動で行う方法を理解していますが、コードを実行すると、私はサークルに入ります。

質問をさらに展開するには、左から右に、または右から左に式を解析する方が良いでしょうか？再帰は必要ですか？ツリーを作成するためにtreelibを使用していると仮定して、この問題にどのように近づくか。それは私がどこから始めるべきかについての説明や擬似コードスニペットとして私が求めているコードではありません。私はこれを自分で行うべきか、これをより簡単にするライブラリがありますか？どのようにこの操作を実行するかに関する私の理解をさらに助けるためのすべての回答は非常に高く評価されます。

Answer 1

Pythonで利用できるいくつかの字句解析ツールがあります。 ply（基本的には、lexとyaccのPython実装です）。

あなた自身で書くのではなく、それらの1つを使用してください。