parsing - 使用从右到左的解析器绕过左递归

Question

我正在为我的 OOP 类(class)做一个项目。部分任务是为非常简单的语法开发解析器。据我所知，到目前为止，最简单的手动实现解析器是递归下降解析器。

然而，我正在解析的语言的所有运算符本质上都是左结合的。据我所知，处理由左结合性强制执行的左递归的最佳方法是改用 LR 解析器。

我的想法是改为从右到左解析标记，我相信这应该使我能够将左关联规则重写为右关联规则。

这行得通吗？如果不行，为什么不行？

Answer 1

如果您愿意，可以这样做，尽管这不一定能解决您所有的问题。如果您熟悉 LL 或 LR 解析器，则有相应的版本从右到左工作，称为 RR 和 RL 解析器，它们的工作方式与 LL 或 LR 解析器在相反方向扫描的方式非常相似。因此，它们与原始 LL 或 LR 解析算法具有相似的弱点，因此虽然这可能对您有所帮助，但实际上可能无法解决任何问题。

作为替代方案，您可以尝试重写语法以查看是否可以直接对优先级和结合性进行编码。根据语法，您还可以考虑使用像 Dijkstra 调车场算法这样的优先级解析算法。您还可以考虑使用带回溯的递归下降解析器。最后，您可以使用 Earley 解析器之类的东西，它可以处理任何语法并且编写代码并不难。