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大量使用属性语法，没有方向约束。我们只需构建完整的树并根据需要传播属性。

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

没有任何理由不能将此过程限制为LR属性。(有朝一日，我们将把兼容LR的属性推入解析阶段，以便在语义检查中使用它们)。

生成属性求值过程的设备本身就是一个对语法进行操作的属性求值器，这一点不应该让您感到惊讶。Bootstrapping还挺有趣的。