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

Question

我这里有两段 Happy 代码，一段使用普通优先级规则，另一段使用上下文相关优先级规则（两者均有描述 here）。

正常：

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

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

上下文相关：

%left PLUS
%left TIMES
%%

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

给定输入：

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

"Context-dependent precedence" 是一种非常具有误导性的描述该功能的方式。不过，上一节中对优先算法的描述基本上是准确的。

正如它所说，优先级比较总是在 production（可以减少）和 terminal（可以是转移）。这个简单的事实常常被设计优先级声明语法的决定所蒙蔽，就好像优先级只是终端的一个属性。

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

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

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

Happy Context-Dependent Operator Precedence

parsing

haskell

happy