parsing - “表达式”的非左递归 PEG 文法

Question

它要么是一个简单的标识符（比如cow），要么是被方括号（）包围的(...)东西，要么是看起来像方法调用（...(...)）的东西，要么是看起来像成员访问（thing.member）的东西：

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

它以 Scala Parser Combinator 语法给出，但应该很容易理解。它类似于表达式最终在许多编程语言中的样子（因此得名expr）。但是，就目前而言，它是左递归的，并导致我漂亮的 PEG 解析器爆炸。

我没有成功地分解左递归，同时仍然保持对(cow.head).moo(dog.run(fast)). 我该如何重构这个，或者我需要转向一些可以容忍左递归语法的解析器生成器？

Answer 1

诀窍是有多个规则，其中每个规则的第一个元素是下一个规则，而不是对同一规则的递归调用，并且规则的其余部分是可选的和重复的。例如，以下内容适用于您的示例：

def expr              = method_call
def method_call       = member_access ~ ( "(" ~> expr <~ ")" ).*
def member_access     = atomic_expression ~ ( "." ~> identifier).*
def atomic_expression = identifier |
                        "(" ~> expr  <~ ")"