1

Antlr で文法を書いている最中に、左再帰に何度か遭遇したことがあります。いくつかの調査を行った後、この問題に対処する 2 つの方法を見つけました。ポールのアルゴリズムと、Robert C. Moore の作品で説明されている左隅の変換Removing Left Recursion from Context-Free Grammars, 2000です。ポールのアルゴリズムは非常に非現実的なものですが、一方で左隅の変換は文法規則の数を からO(n)まで増やすだけO(n^2)ですが、ほとんどの場合、これよりもはるかに少ないため、そのアルゴリズムは非常に効率的です。だから私の質問は次のとおりです:左再帰の削除は意図的に実装されておらず、文法の実装者に責任を負っていますか、それともオプションとは見なされていませんか?

4

1 に答える 1

2

この答えには2つの部分があります。

  1. ANTLR 4は直接左再帰を削除します。
  2. 一般に、左再帰の削除は、実際の文法ではより複雑です。ANTLR は、生成元の文法に非常によく似た再帰降下パーサーを生成します。左再帰の削除では、述語、埋め込みアクション、引数、ローカル変数、および (ANTLR 3 の場合) AST 操作を考慮する必要があります。ツールが作成されなかったのは、不完全 (サポートされている構造の制限)、不正確 (適切に動作するパーサーを生成しない)、非現実的な複雑さの間のどこかにあるはずだったからです。
于 2013-08-23T18:49:08.937 に答える