为什么右递归文法不适用于自下而上的 LR(k) 解析？
Why right-recursive grammar is not appropriate for Bottom-Up LR(k) parsing?
- 为什么右递归文法不适用于自下而上的 LR(k) 解析？
我知道自下而上的解析从叶子开始并构建到根节点，而自上而下的解析从根开始并一直向下，对这些问题进行了一些研究并了解了如何修改它们但是无法直接回答为什么这不起作用。感谢您的帮助。
[OP 将问题标题从 "why can't ... be used" 更改为 "why isn't appropriate ..." 这反过来又将我的评论更改为回答，所以我把它作为一个发布。]
您可以对任何 LR(k) 解析算法使用左递归或右递归规则。
如果要构建树，右递归规则会导致解析过程变得有趣 属性：您必须保持与右递归一样深的堆栈以跟踪收集的节点。
人们会给你源文件，列表中包含一百万个项目，所以你的堆栈一定有那么深。使用正确的递归规则，这可能足够深，如果你有一个固定大小的堆栈，你 运行 超出 space。
通常使用处理器的自然下推堆栈来实现解析器堆栈。我们常见的操作系统（Windows、Linux）及其常见的编译器恰好为您提供 exactly such fixed size pushdown stacks，因此在某种意义上它们加剧了这个问题。
使用左递归规则，您可以在每个列表项之后进行归约，因此堆栈基本上可以是单位深度。这更友好：不会崩溃，并且可以很好地使用缓存。
- 为什么右递归文法不适用于自下而上的 LR(k) 解析？
我知道自下而上的解析从叶子开始并构建到根节点，而自上而下的解析从根开始并一直向下，对这些问题进行了一些研究并了解了如何修改它们但是无法直接回答为什么这不起作用。感谢您的帮助。
[OP 将问题标题从 "why can't ... be used" 更改为 "why isn't appropriate ..." 这反过来又将我的评论更改为回答，所以我把它作为一个发布。]
您可以对任何 LR(k) 解析算法使用左递归或右递归规则。
如果要构建树，右递归规则会导致解析过程变得有趣 属性：您必须保持与右递归一样深的堆栈以跟踪收集的节点。
人们会给你源文件，列表中包含一百万个项目，所以你的堆栈一定有那么深。使用正确的递归规则，这可能足够深，如果你有一个固定大小的堆栈，你 运行 超出 space。
通常使用处理器的自然下推堆栈来实现解析器堆栈。我们常见的操作系统（Windows、Linux）及其常见的编译器恰好为您提供 exactly such fixed size pushdown stacks，因此在某种意义上它们加剧了这个问题。
使用左递归规则，您可以在每个列表项之后进行归约，因此堆栈基本上可以是单位深度。这更友好：不会崩溃，并且可以很好地使用缓存。