为什么右递归解析器不无限循环？

Question

左递归会使解析器进入无限循环。那么为什么右递归不会发生同样的情况呢？

Answer 1

在递归下降解析器中，像A -> B C | D这样的语法规则是通过尝试在当前位置解析B，然后，如果成功，则尝试在B结束的位置解析C来实现的。如果其中任何一个都失败了，我们就尝试解析当前位置的D。

如果C等于A(右递归)，这是可以接受的。这意味着如果B成功了，我们尝试在B之后的位置解析A，这意味着我们首先尝试在那里解析B，然后在新位置再次尝试A或尝试D。这将继续下去，直到最终B失败，我们尝试D。

然而，如果B等于A(左递归)，那就是一个很大的问题。因为现在要解析A，我们首先尝试解析当前位置的A，这将尝试解析当前位置的A…无限的广告。我们从不推进我们的位置，也从来不尝试任何事情，除了A(它只是不断地尝试自己)，所以我们永远不会达到可能终止的地步。

？假设完全反向跟踪。否则，如果B和/或C使用了任何令牌(或比我们预先获得的更多的令牌)，则A可能在不尝试D的情况下失败，但对于本讨论来说，这些都不重要。