左再帰を削除するために文脈自由文法をリファクタリングしたいことがよくあります。このような変換を実装するアルゴリズムは多数あります。たとえば、hereまたはhere。
このようなアルゴリズムは、左再帰の存在に関係なく、文法を再構築します。これには、元の文法から異なる構文木が生成されるなどのマイナスの副作用があり、おそらく異なる結合性があります。絶対に必要な場合にのみ、文法が変換されることが理想的です。
文法内の左再帰の存在を識別するアルゴリズムまたはツールはありますか? 理想的には、これは左再帰を含むプロダクション ルールのサブセットも分類する可能性があります。