用於「表達式」的非左遞歸PEG語法

Question

它或者是一個簡單的標識符（如cow），其中括號（(...)）包圍的東西看起來像方法調用（...(...)）或者看起來像成員訪問的東西（ thing.member）：

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

它在斯卡拉解析器組合語法給出的，但它應該是相當簡單的瞭解。這與表達式最終看起來很像許多編程語言（因此名稱爲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 ")"