ANTLR4相互左回帰文法

Question

ここでは、LL（k）パーサの相互左回帰問題に関するStackOverflowに関する多くの質問を読んでいます。私は、左再帰除去するために一般的なアルゴリズムを見つけました：

A : Aa | b ; 

はしかし、私は私の状況に適用する方法を見つけ出すことはできません

A : bR ; 
R : (aA)? ; 

になります。私は、など

left_exp: IDENT | exp DOT IDENT ; 
exp  : handful 
     | of 
     | other rules 
     | left_exp ; 

「他のルールの一握り」すべてが通常の再帰が含まれている、などexp : exp PLUS expを、持っているし、何の問題もありません。問題は、left_expとexpが相互に再帰的であることです。

私はちょうどexpルールにIDENTとexp DOT IDENTを追加することを考えたが、left_expが有効になり、他の有効なexpのルールが適用されないいくつかの状況では、あります。

EDIT

私も割り当てが続く左の発現のための呼び出しを次のルールを持っています。

assign_statement: left_exp (COLON IDENT)? EQUAL exp SEMI ; 

正規表現は、それがDOT IDENTが続いている場合にのみ、左式ですので、その後、割り当てが受け入れるだろうので、私はちょうど、私の表現の定義に

| IDENT 
| exp DOT IDENT 

を追加することができないようですこれらの2つのうちの1つだけではなく、左側の他の有効な式。

Answer 1

私は通常、適用のアプローチは、このように書きます：

A: Aa | b; 

は次のようになります。

A: b (a)*; 

または一般的には：（削除）左再帰を持つとすべてのALTが続く左再帰なしすべてのALT無制限の発生（クレーンオペレータを介して表現される）。例：

A: Aa | Ab | c | d | Ae; 

は次のようになる。

A：（C | D）（| B | E）*。

あなたはに常時交換することにより、容易にこれを確認することができます。

A: Aa | b; 
A: (Aa | b)a | b; 
A: Aaa | ba | b; 
A: (Aa | b)aa | ba | b; 
A: Aaaa | baa | ba | b; 

など

あなたの例では、しかし、あなたは（2つのルールを介した）間接的な左再帰を持っています。 ANTLRではこれを認めません。解決策は、left_expからexpまでaltsを移動し、上記のアルゴリズムIを適用することです。