parsing - 如何解决 PEG 中的左递归

Question

问题是，PEG（解析表达式语法）不允许左递归规则。我已经阅读了有关该主题的可用答案，但问题具体（例如这个）或非常简单（例如x = symbol:(x '.')）。

我创建了以下非常简单的语法来说明问题

EXAMPLE = x+

x = symbol:(x y* / x y z)

y = symbol:('.' x)
z = symbol:('$')

可以使用PEG.js 解析器生成器测试此语法。

能“流利”使用正式语言的人描述如何将这条规则/规则集重写为 PEG？还是有一种通用的方法/算法可以解决左递归？

编辑：我刚刚找到这个 Wikipedia 页面，它描述了一种删除左递归的方法，我将对其进行研究并尝试将其应用于上面显示的语法。

score 2 · Accepted Answer

PEG 解析器本质上是具有无限前瞻和有序选择的 LL(*)。您的语法必须为下一个符号提供一个或多个选择，以允许解析器进行选择。

你的语法看起来很糟糕，但如果我正确地阅读了你的意图，它会在每组的末尾有一组点和一美元。所以它是这样的：

x -> ('.'+ '$')+

有正式的重写算法，但大多数情况下只要弄清楚“接下来会发生什么？”就足够了。“那之后会发生什么？” 和“它是如何重复的？”。

1 回答 1