parsing - LR 属性解析器技术

Question

我想知道 LR 属性解析器可以做什么以及它是如何实现的。

yacc 生成的解析器允许在属性源是使用 $0、$-1 等规范语法位于左侧的兄弟时继承属性。使用 S -> A B B 将能够从 A 继承一个综合属性，但不能从 S 继承一些东西。我认为这是通过在堆栈中查找 B 的 1 个元素来完成的会是A。

现在 zyacc 文档 says它们允许 LR 属性语法，我猜这与 yacc 允许的差不多。仅对于 zyacc 而言，这些属性是使用非终结符(如参数)指定的，而不仅仅是在语义操作中访问的。是否有任何其他差异，例如 LR 属性比 yacc 继承的属性更强大，或者 LR 属性的实现方式不同(不仅仅是查看堆栈)。

Answer 1

LR 属性语法的要点是使信息在左侧上下文中可见，可用于正确的扩展。

想象一下你的语法有

      R -> X S Y;
      S -> A B;

你已经同意 S 可以看到从 X 合成的属性。事实上，这些属性可以在 X 的解析完成时可用。如果做得好，A 和 B 应该可以使用这些属性，因为它们被解析了, 作为从 S 继承的属性。

据我所知，YACC 没有实现任何这些，除非您想将 X 的解析树的存在计算为解析 X 的“综合”属性。

如何实现属性语法取决于你想做什么。我公司的主要产品 DMS 大量使用属性语法，没有方向限制。我们只需构建完整的树并根据需要传播属性。

我们所做的是预先计算，对于每个节点类型，它可能继承的属性集[及其类型]，以及它可能合成的集合，并为每个节点合成一个结构。在属性评估时，这些结构通过一个非常快速的访问哈希表与树节点相关联。对于每个节点类型，我们检查数据流(哪个子节点使用哪个继承属性，哪个子节点使用其他子节点的合成属性)。我们据此计算执行顺序，使所有属性以安全(生成前使用)顺序计算，并生成一个过程来为该节点类型完成此操作，该过程调用子过程。然后属性评估包括为文法根调用生成的过程。 (事实上​​ ，我们实际上生成了一个偏序来评估 child ，并使用 DMS 的实现并行编程语言的功能生成一个偏序并行调用，确保在非常大的 AST 上使用多个内核进行快速评估)。

没有任何理由不能将此过程限制为 LR 属性。 (总有一天我们会将 LR 兼容的属性插入解析阶段，以允许它们在语义检查中使用)。

生成属性评估过程的设备本身就是一个对语法进行操作的属性评估器，您应该不会感到惊讶。自举有点有趣。