LR属性解析器技术

Question

我想了解LR-属性解析器能做什么以及它是如何实现的。

使用$0，$-1等规范语法时，yacc生成的解析器允许继承属性，当属性来源是位于其左侧的一个兄弟节点时。对于S -> A B，B可以从A继承合成属性，但无法从S继承。我认为这是通过在堆栈中向下查找1个元素（即A）来完成的。

现在，zyacc文档指出，他们允许LR-属性语法，这可能与yacc允许的相同或者更多。只是在zyacc中，这些属性是由非终端符号（类似参数）指定的，并且不仅仅在语义动作中访问。是否还有其他差异，例如LR-属性比yacc继承属性更强大，或者LR-属性的实现方式不同（不只是向下查找堆栈）？

- user764754

Answer 1

LR属性文法的目的是使左侧上下文中的信息对右侧扩展可见。

想象一下，如果您的语法规则具有这样的特点：

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

你已经同意S可以看到从X合成的属性。实际上，在解析X完成时，这些属性可以在那里使用。如果正确完成，这些属性应该作为继承属性从S解析时可用于A和B。

据我所知，YACC没有实现任何这方面的内容，除非你想将X的解析树的存在视为解析X的“合成”属性。

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

我们所做的是为每种节点类型预先计算它可能继承的属性[及其类型]集合，以及它可以合成的集合，并为每个结构体进行合成。在属性评估时，这些结构体通过非常快速的访问哈希表与树节点相关联。对于每种节点类型，我们检查数据流（哪个子节点使用哪个继承属性，哪些子节点使用其他子节点的合成属性）。从中我们计算出一个执行顺序，以使所有属性按照安全的（在消耗之前生成）顺序被计算，并生成一个过程来完成该节点类型的操作，该过程调用子过程。属性评估然后包括调用语法根的生成过程。（实际上，我们确实为评估子节点生成了一个“部分顺序”，并使用DMS的实现并行编程语言的能力生成了一个部分顺序的并行调用，以确保在非常大的AST上使用多个核心进行快速评估）。

没有任何理由限制此过程仅适用于LR属性。（有一天，我们将把LR兼容属性推入解析阶段，以允许在语义检查中使用它们）。

毋庸置疑，生成属性评估过程的设备本身就是一个属性评估器，它作用于语法。启动这个过程有点有趣。

- Ira Baxter

---

谢谢，您的意思是zyacc允许继承之前已合成的属性，但不一定是在使用这些属性的同一选择项中吗？ - user764754

好吧，应该允许；我不知道 zyacc 实际上是做什么的。你为什么不试一下呢？如果你写了它做不了的事情，如果它被设计得很好，它会报错。 - Ira Baxter