0

我读过 yacc 为 LALR(1) 语法生成自下而上的解析器。我有一个 Java 1 的语法，可用于生成三个地址代码，并且严格来说是 LALR(1)，但我使用的翻译方案使其具有 L 属性。现在我已经读到 L 属性的 LR 语法在自下而上解析期间无法翻译。那么，这里是否可以使用 yacc？如果是，yacc 如何解决这个问题？

4

1 回答 1

1

除非你问一个具体的、详细的问题，否则你不会得到一个好的答案。这是一种方法的模糊草图。

对于自下而上的解析器来说，综合属性显然不是问题，因为它们是在相应终端的最终归约动作中计算的。所以问题归结为“自下而上的解析器如何计算继承的属性？”

由于语法是 L 属性的，我们知道任何继承的属性都是从其左兄弟的属性计算出来的。Yacc/bison 允许将动作插入右侧的任何位置，并且这些“中间规则动作”（MRA） 在遇到时执行。MRA 正好可以使用它的左兄弟姐妹，因此这就是计算继承属性所需的全部内容。

但是，这并没有显示该属性实际上是如何被继承的。插入到某个规则中的语法符号之前的 MRA 当然可以用于部分计算该符号的继承属性，但继承属性也可以使用子项的综合属性。

为此，我们需要做两件事：

  1. 在非终结符之前插入一个 MRA，它将左兄弟属性聚集在一起。由于 MRA 也是语法符号，因此该 MRA 将是最后一个左兄弟，实际上是终端孩子中最小的叔叔。（您不一定需要 MRA；您可以插入一个“标记”：一个非终端，其唯一的生产是空的，其动作是 MRA 主体。但这不太方便，因为动作必须达到语义前面的语法符号的值。或者你可以把产生式分成两部分，这样两个动作都是最终的。）

  2. 在终端的还原动作中访问叔叔的属性。

    Bison/yacc 通过让您使用非 positibd 符号索引来引用解析器堆栈中的插槽来允许第二步。特别$0是指在父产生式中紧接在非终结符之前的符号（我在上面所说的叔叔）。当然，要做到这一点，您必须确保 uncle 在出现非终结符的每个产生式中都是相同的非终结符（或至少具有相同的语义类型）。这可能需要添加一些标记。

    说到语义值，你也许可以让自己满意，给定非终结符的所有叔叔都是相同的，或者至少具有相同的类型。但是bison不做这个分析，所以如果你弄错了它也不会警告你。当心！作为另一个结果，你必须告诉 bison 类型是什么，所以你不能只写$0：你需要$<tag>0.

笔记：

在 L 属性的 LR 文法中处理继承的属性并不总是可能的，因为在遇到非终结符的那一刻，解析器可能还不知道非终结符实际上将构成分析树的一部分. 这个问题不会出现在 LL 语法中，因为在 LL 解析中，解析器只能预测一个非终结符，如果输入的其余部分有效，则该非终结符保证存在于解析中。

任何 LL 文法都可以自下而上解析，因此 L 属性的 LL 文法没有问题。但是自下而上的解析器可以做得更好；它不需要完整的语法是 LL。只有那些即将被分配继承属性的非终端的决策点需要是 LL-deterministic。

这种限制是通过在非终端紧接之前放置 MRA 或标记的技术来实施的。换句话说，在 LR 语法的某些点添加标记（或 MRA）可能会使 LR 属性无效。野牛手册中对这个问题有很好的讨论，所以我在这里不再详述，只观察一个细节。

上面概述的用于传播继承属性的技术在战略点使用 MRA（或标记）来保存继承属性。为了继续进行解析，必须减少这些产生式，因此如上面提到的野牛手册部分所述，可能需要重新排列语法以消除冲突。在极少数情况下，这种重写甚至是不可能的。

但是，消除冲突可能仍会导致在某些非终结符需要该值的情况下传播继承属性的语法，而不能保证最终将减少非终结符。在这种情况下，继承的属性将被不必要地计算，然后被忽略。但这应该不是问题。属性概念中固有的概念是属性是功能性的。换句话说，计算没有副作用。

没有副作用意味着属性语法解析器应该可以自由地以尊重属性依赖性的任何顺序评估属性。特别是，这意味着您可以通过将属性计算转换为延续来轻松实现属性的正确评估，这种技术有时被称为惰性评估或“thunking”。

但是总是有人想精确地使用 MRA 来产生副作用。一种非常常见的副作用是将三地址代码打印到输出流。另一种是改变持久性数据结构，例如符号表。这不再是 L 属性解析，因此此处提供的建议可能不适用于此类应用程序。

于 2020-04-16T10:40:28.090 回答