如何解决PEG中的左递归

Question

问题是，PEGs（解析表达式语法）do not allow left-recursive rules。 我已阅读有关此主题的可用答案，但具体问题（如this one）或非常简单（例如x = symbol:(x '.')）。

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

EXAMPLE = x+ 

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

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

此语法可以使用PEG.js parser generator进行测试。

在正式语言中“流利”的人是否可以描述如何将此规则/规则重写为PEG？还是有一个通用的方法/算法，可以解决左递归？

编辑：我刚刚发现this Wikipedia page，它描述了一个方法，以消除左递归，我会研究，并尝试将其应用到上面显示的语法。

Answer 1

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

你的语法看起来很糟糕，但是如果我正确地阅读你的意图，它会在每个组的最后有一组点和一个美元。如此这般类似：

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

有正式重写算法，但大多是不够的，只是弄清楚“可能来下什么呢？”和'之后会发生什么？'和“它是如何重复的？”。