問題タブ [left-recursion]

次の文法は左再帰を持っています:

左再帰を削除するにはどうすればよいですか。ウィキペディアの説明を読みましたが、CFG にはかなり慣れていないので、あまり意味がありませんでした。何か助けていただければ幸いです。平易な英語の説明はさらに高く評価されます。

{a、b、c、d} *の形式の文字列のセットを受け取るdcgを実装しようとしています。問題は、s（[a、c、b]、 []）、正しい答えであるtrueを返しますが、s（[a、c、f]、[]）の形式のクエリがある場合、答えを返さず、ローカルスタックが不足します。

文法を書きましたが、左再帰エラーが発生しました。

次のエラーが表示されます。

[12:41:35] エラー (210): 次のルール セットは相互に左再帰的です [primary_expression、logical_and_expression、logical_or_expression、expression]
[12:41:35] 次のルールは相互に左再帰的であるため、中止します: [ [Lang.primary_expression,index=2,line=19], [Lang.logical_and_expression,index=5,line=36], [Lang.logical_or_expression,index=4,line=31], [Lang.expression,index=3] ,line=24]]

訂正された文法

I ran into an infinite recursion problem while trying to implement a very simple constraint free grammar in prolog.

Here are my rules: (vp -> verb phrase, np -> noun phrase, ap -> adj phrase, pp -> prep phrase)

The problem im running into is that the rule for ap can produce arbitrarily long strings of adjectives, so at some point, i get stuck trying to satisfy the query by trying all these infinite possibilities.

For example, the following query will never produce S = [put, the, red, block, on, the, green, block] because it will first expand the adjective phrase on the left "red" to infinite possibilities before ever trying on the right.

すべての左再帰を削除するために使用できるはずのこのアルゴリズムを見てきました。しかし、私はこの特定の文法で問題に遭遇しています:

何をしようとしても、ループになってしまうか、文法が間接左再帰のままになってしまいます。

この文法でこのアルゴリズムを適切に実装する手順は何ですか?

cpp ソース構文のサブセットを解析しようとしています。次の ANTLR4 パーサー ルールは、C++ 言語仕様から直接コピーされます (ただし、ハイフンはアンダースコアに置き換えられます)。

しかし、org.antlr.v4.Tool が文法を解析しているときに、次のエラーが発生しました。

error(119): cppProcessor.g4::: 次の一連のルールは相互に左再帰的です [direct_abstract_declarator]

direct_abstract_declarator ? 左側の構文でエラーが発生します。どのように修正すればよいですか？ANTLR4 がサポートできないのはなぜですか?

ルールを手動でこの形式にリファクタリングしても、エラーは発生しません。

左再帰ルールを処理するときに、ANTLR4 が最初の構文を直接サポートすることは可能ですか?