快乐的上下文相关运算符优先级 [英] Happy Context-Dependent Operator Precedence

问题描述

这里有两个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 
  

版本给出：

 加（Times（Vara）（Varb））（Times（Varc ）（Vard））
  

而上下文相关版本给出：

pre $ Times（Vara）（Plus（Varb）（Times（Varc）（Varc）））


这两个都不应该给出相同的输出吗？我在这里做错了什么，这使得它们生成不同的分析树？解析方案

依赖于上下文的优先级是一种非常令人误解的方式描述该特征。不过，前面章节中的优先级算法的描述在很大程度上是准确的。

正如它所说的，优先级比较总是在产品 （可以减少）和一个终端（可以移动）。这个简单的事实常常被设计优先权声明语法的决定所笼罩，好像优先权仅仅是终端的属性。

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

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

I have two snippets of Happy code here, one that uses normal precedence rules, and one that uses context-dependent precedence rules (both of which are described here).

Normal:

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

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

Context-dependent:

%left PLUS
%left TIMES
%%

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

Given the input:

a * b + c * d

The normal version gives:

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

whereas the context-dependent version gives:

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

Shouldn't these both give the same output? What am I doing wrong here that's making them generate different parse trees?

解决方案

"Context-dependent precedence" is a very misleading way of describing that feature. The description of the precedence algorithm in the preceding section is largely accurate, though.

As it says, a precedence comparison is always between a production (which could be reduced) and a terminal (which could be shifted). That simple fact is often clouded by the decision to design the precedence declaration syntax as though precedence were solely an attribute of the terminal.

The production's precedence is set by copying the precedence of the last terminal in the production unless there is an explicit declaration with %prec. Or to put it another way, the production's precdence is set with a %prec clause, defaulting to the precedence of the last token. Either way, you can only define the precedence of the production by saying that it is the same as that of some terminal. Since that is not always convenient, the parser generator gives you the option of using an arbitrary name which is not the name of a grammar symbol. The implementation is to treat the name as a terminal and ignore the fact that it is never actually used in any grammar rule, but logically it is the name of a precedence level which is to be assigned to that particular production.

In your first example, you let the productions default their precedence to the last (in fact, the only) terminal in each production. But in your second example you have defined two named precedence levels, PLUS and TIMES and you use those to set the precedence of two productions. But you do not declare the precedence of any terminal. So when the parser generator attempts to check the relative precedence of the production which could be reduced and the terminal which could be shifted, it finds that only one of those things has a declared precedence. And in that case, it always shifts.

这篇关于快乐的上下文相关运算符优先级的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！