用于“表达”的非左递归PEG语法 [英] Non-left-recursive PEG grammar for an "expression"

问题描述

这是一个简单的标识符（如 cow ）用方括号（（...））看起来像一个方法调用（ ...（...））或看起来像成员访问（ thing.member ）：

It's either a simple identifier (like cow) something surrounded by brackets ((...)) something that looks like a method call (...(...)) or something that looks like a member access (thing.member):

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

这是Scala Parser Combinator语法中给出的，但应该非常直观。它类似于表达式最终在许多编程语言中查找（因此名称 expr ）但是，因为它是，它是左递归的，并导致我好的PEG解析器爆炸。

It's given in Scala Parser Combinator syntax, but it should be pretty straightforward to understand. It's similar to how expressions end up looking in many programming languages (hence the name expr) However, as it stands, it is left-recursive and causes my nice PEG parser to explode.

我没有成功解决左递归，而仍然保持正确的（cow.head）.moo（dog.run （快速））。我如何重构这个，或者我需要转移到一个解析器生成器可以容忍左递归的语法？

I have not succeeded in factoring out the left-recursion while still maintaining correctness for cases like (cow.head).moo(dog.run(fast)). How can I refactor this, or would I need to shift to some parser-generator that can tolerate left recursive grammars?

推荐答案

诀窍是有多个规则，其中每个规则的第一个元素是下一个规则，而不是递归调用相同的规则，其余的规则是可选的和重复。例如下面的例子将适用于你的例子（不使用Scala生成器符号，因为我不知道它）：

The trick is to have multiple rules where the first element of each rule is the next rule instead of being a recursive call to the same rule, and the rest of the rule is optional and repeating. For example the following would work for your example (not using Scala generator notation because I don't know it):

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

这篇关于用于“表达”的非左递归PEG语法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！