parsing - 快乐的上下文相关运算符优先级

Question

我这里有两段 Happy 代码，一段使用普通优先规则，另一段使用上下文相关的优先规则(均描述为 here)。

普通的:

%left '+'
%left '*'
%%

Exp :: { Exp }
    : Exp '+' Exp { Plus $1 $3 }
    | Exp '*' Exp { Times $1 $3 }
    | var         { Var $1 }

上下文相关:

%left PLUS
%left TIMES
%%

Exp :: { Exp }
    : Exp '+' Exp %prec PLUS  { Plus $1 $3 }
    | Exp '*' Exp %prec TIMES { Times $1 $3 }
    | var                     { Var $1 }

给定输入:

a * b + c * d

普通版给出:

Plus (Times (Var "a") (Var "b")) (Times (Var "c") (Var "d"))

而上下文相关的版本给出:

Times (Var "a") (Plus (Var "b") (Times (Var "c") (Var "c")))

这两者不应该给出相同的输出吗？我在这里做错了什么导致它们生成不同的解析树？

Answer 1

“上下文相关的优先级”是描述该功能的一种非常误导性的方式。不过，上一节中对优先算法的描述在很大程度上是准确的。

正如它所说，优先比较总是在生产(可以减少)和终端(可以转移)之间进行。这个简单的事实经常被设计优先声明语法的决定所掩盖，就好像优先只是终端的一个属性。

产生式的优先级是通过复制产生式中最后一个终端的优先级来设置的，除非有明确的声明 %prec .或者换句话说，产生式的优先级设置为 %prec子句，默认为最后一个标记的优先级。无论哪种方式，您只能通过说它与某些终端的相同来定义生产的优先级。由于这并不总是很方便，解析器生成器为您提供了使用不是语法符号名称的任意名称的选项。实现是将名称视为终端并忽略它从未在任何语法规则中实际使用的事实，但从逻辑上讲，它是分配给该特定产生式的优先级的名称。

在您的第一个示例中，您让产品将其优先级默认为每个产品中的最后一个(实际上是唯一的)终端。但是在您的第二个示例中，您已经定义了两个命名的优先级，PLUS 和 TIMES，并且您使用它们来设置两个产生式的优先级。但是您没有声明任何终端的优先级。因此，当解析器生成器尝试检查可以减少的产生式和可以移动的终端的相对优先级时，它发现其中只有一个具有声明的优先级。在这种情况下，它总是会发生变化。