消除明确的 PEG 语法中的左递归

Question

我已经通读了 Whosebug 上的一堆现有问题，但我无法弄清楚语法。

statement "Statement" =
    assignment / primitive / reference / operation
operation "Operation" =
    statement operator:operator statement
operator "Operator" =
    "+"

^{* 请注意，稍后我可能会在运算符规则中添加更多运算符模式（即“==”、“**”、“/”）。因此，它可能会变得更加复杂。}

我实际上在这里使用 PEG.js 而不是普通的 PEG，因此使用了非常规的语法。

编译器向我抱怨 statement 访问了 operation ，后者又访问了 statement 等等，这可能导致无限循环。这通常称为左递归。

对于这个特殊情况，我无法理解如何解决这个问题。对于这种情况，我不太了解头尾模式。

^{注意：我想尽可能方便地在其他规则中重复使用 statement 规则。因此，将其拆分为一些单独的规则作为一些解决方法可能是一个解决方案，但不会真正帮助我作为答案。}

Answer 1

在某位朋友的大力帮助下^{顺便在10分钟内理解了整个PEG解析架构}，我能够解决这个场景的问题。

让我们问这个：

In an operation in the form of left+right , will we ever have an assignment (of the form a=b) or another operation (of the form a+b) on the left side?

答案很可能是否定的。

因此，这个语法有效：

statement "Statement" =
    assignment / operation / primitive / reference
operation "Operation" =
    (primitive / reference) operator statement
operator "Operator" =
    "+"

如您所见，我只是以某种方式内联了 statement 规则，将其替换为 statement 规则中的 primitive / reference 部分，省略了 assignment和 operation 部分，因为我们在左侧不需要它们。

这只是解决方案。一切正常。

但是，如果您想知道为什么像 1+2+3+4+5 这样的解析输入有效，尽管我们显然不允许在 + 的左侧递归 operation，请注意我们仍然允许他们站在右边。右递归在 PEG 中是完全有效的。

消除明确的 PEG 语法中的左递归

Eliminate left-recursion in unambiguous PEG grammar

javascript

parsing

abstract-syntax-tree

peg

pegjs