抽象構文ツリーをゼロから作成することで、正規表現用のパーサーを構築しようとしています（Javaなどのカップパーサーなどのプロジェクト依存性やツールなし）。正規表現に含まれるすべての情報を保存するのではなく、可能な限り単純化したいと思います。正規表現の最適なASTを構築するにはどうすればよいですか？
例として、x::=y|zは、文字クラスx::=[yz]と同じASTになるはずです。しかし、正規表現は非常に複雑になる可能性があるため、実装する同等のものを決定することはできません。たとえば、負の選択肢x::=[^b]を保存する方法はわかりません。x::=a|c|d|e|...
どのような抽象化を行いますか？これらの抽象概念の中には後で間違ったASTにつながることがありますか？
ASTは、特定のプログラム（OPの場合は「正規表現」）の構文を表します。通常、ASTは入力プログラムの特定の分解を記録する実際の解析ツリーから派生します。
OPは、文字クラスと同じように文字の上に交替を表すASTが必要であることを示唆しています。彼は特定のパースと "同等の"または "標準的な"フォームを混同しているようです。
一般に、明らかに異なるパーズツリーを持つ異なる入力文字列と、分解が正規化されている場合は同じASTが存在する可能性があります。それは必ずしも容易ではありません。簡単なケース（OPの例はその一部である）を見つけることができ、そこでは言語の一部のための正規形を定義し、その正規形に等価な構成を強制することができる。一般に、任意の同等のものから標準を生成できるという保証はありません。
または、OPが1つを選択しようとしているので、[^ x]を明示的に127個のASCII代替語で表すのがよいでしょうか？ [^ < 63 characters>]のために選択する必要があるのは何ですか？ [^ < 64文字>]ですか？ [^ < 65文字]間違いなく2^24文字を持つUnicodeの[^ x]表現はどうでしょうか？
実用的な問題として、彼は、パースツリーおよび/またはそのパーズツリーに対応するASTを生成することをOPに提案します。その後、ASTを正規形に正規化しようとすると意味があればそれを試みることができますが、これは別の手順として保存することをお勧めします。
文字クラスは別にしてください。これを考えてみましょう：Unicodeは120k文字以上の文字を定義しているので、 '[^ b]'はおよそ120kのメンバーと交互になります。それはASTのために良いことではない。 –