快乐的上下文依赖运算符优先级

Question

我在这里有两个Happy代码片段,一个使用普通优先级规则,另一个使用依赖于上下文的优先级规则(这两个都在这里描述).

正常:

%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，并使用它们来设置两个产生式的优先级。但您没有声明任何终端的优先级。因此，当解析器生成器尝试检查可以减少的产生式和可以移动的终端的相对优先级时，它发现只有其中之一具有声明的优先级。在这种情况下，它总是会发生变化。