我试图了解自下而上解析期间 L 属性语法和计算属性之间的关系是什么。是否总是可以在创建语法树期间为每个上下文无关文法或仅针对某些选定文法（如 LR(k)）计算所有属性？让我们假设允许进行一些转换，例如添加新的非终结符和 epsilon 产生式。我一直在寻找这方面的一些信息，但我找不到。
问问题
150 次
1 回答
0
如果您可以自下而上从左到右构建解析树，那么您可以计算 L 属性。这是一个重言式，因为 L 属性是您可以自下而上从左到右计算的那些属性。您如何设法进行解析是无关紧要的。
广义 LR 解析算法允许您从下到上从左到右解析，但条件是在给定时刻可能有多个可能的解析可用。（事实上，如果不要求语法明确，则整个输入的解析可能不止一次。）
在实践中，在您知道解析节点是最终解析的一部分之前计算解析节点的属性可能非常低效。同样在实践中，人们会在此处插入有关具有副作用的操作的警告，但计算解析节点的属性本身并不是副作用，如果它对宇宙有其他影响，那么我们将不再处于数学理论的领域。
此外，如果语法是明确的，则可能解析的数量可能是输入长度的指数。大多数广义 LR 算法构造解析图而不是解析树，这可以仅使用多项式空间来表示可能的树的指数数量。但这需要在不同的解析之间共享节点，这在属性计算方面可能是不可能的，因为要共享的节点可能具有不同的属性。
在这里，我认为值得重新审视上面提到的副作用问题，因为计算节点的属性值可能不是副作用。如果您正在构建一个在构建过程中可观察到的持久结构（解析树），那么将属性分配给该结构的组件肯定会产生副作用。另一方面，如果结构在其构建过程中在外部不可见，那么将属性分配给组件就没有关系。在这种情况下，最好将 L 属性视为可以在（完全构造的）解析树的单个深度优先从左到右遍历中计算的属性。
于 2020-06-21T15:35:35.073 回答