「式」の非左回帰式PEG文法

Question

単純な識別子（cowなど）のいずれかが、メソッド呼び出し（...(...)）またはメンバーアクセスthing.member）：

def expr = identifier | 
      "(" ~> expr <~ ")" | 
      expr ~ ("(" ~> expr <~ ")") | 
      expr ~ "." ~ identifier 

これは、Scalaのパーサコンビネータ構文で与えられていますが、理解することは非常に簡単でなければなりません。これは、式が多くのプログラミング言語（したがって、名前はexpr）で終わる方法と似ています。しかし、それは左回帰的であり、素晴らしいPEGパーサーが爆発する原因になります。

私は(cow.head).moo(dog.run(fast))のような場合には正しさを維持しながら、左回帰を考慮に入れませんでした。どのようにしてこれをリファクタリングすることができますか、または左回帰文法を許容できるパーサージェネレータに移行する必要がありますか？

Answer 1

トリックは、同じルールへの再帰呼び出しではなく、各ルールの最初の要素が次のルールであり、残りのルールがオプションで繰り返しである複数のルールを持つことです。たとえば、あなたの例では、以下のように動作します（わかりませんので、Scalaジェネレータの表記法は使用しません）。

expr ::= method_call 
method_call ::= member_access ("(" expr ")")* 
member_access ::= atomic_expression ("." identifier)* 
atomic_expression ::= identifier | "(" expr ")"