用于"表达式"的非左递归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  <~ ")"