为什么在某些情况下我不能使用令牌作为优先标记

Question

假设这段代码有效：

left '*'
left '+'

expr: expr '+' expr
    | expr '*' expr
    ;

我想定义另一个优先标记，例如：

left MULTIPLY
left PLUS

expr: expr '+' expr %prec PLUS
    | expr '*' expr %prec MULTIPLY
    ;

但这实际上并没有效果。

我认为这两种形式应该是等价的，但事实并非如此。

这不是实际问题。我只是想知道这种现象的原因和原理。

谢谢。

Answer 1

Yacc 优先级规则实际上并不是关于表达式的优先级，尽管它们可以用于此目的。相反，它们是一种明确解决转移/归约冲突（并且仅转移/归约冲突）的方法。

了解它的工作原理需要了解移位/归约（自​​下而上）解析的工作原理。基本思想是从输入中读取令牌符号并将这些令牌推送（“移位”）到堆栈上。当堆栈顶部的符号与语法中某些规则的右侧匹配时，您可以“减少”该规则，从堆栈中弹出符号并用规则左侧的单个符号替换它们。您重复此过程，移动标记并减少规则，直到您读取整个输入并将其减少为起始符号的单个实例，此时您已成功解析整个输入。

上述问题（以及解析器生成器的整个机制正在解决的问题）的基本问题是知道何时减少规则以及何时移动令牌（如果两者都可能）。解析器生成器（yacc 或 bison）构建一个状态机，用于跟踪哪些符号已被移位，因此知道当前可能有哪些“部分匹配”规则，并将移位限制为那些可以匹配更多此类规则的标记。如果所讨论的语法不是 LALR(1)，则此方法不起作用，因此在这种情况下 yacc/bsion 会报告移位/归约或归约/归约冲突。

优先级规则解决移位减少冲突的方式是为语法中的某些标记和规则分配优先级。每当要移动的标记和要减少的规则之间存在移位/归约冲突，并且两者都有优先级时，它将执行优先级较高的一个。如果它们具有相同的优先级，那么它会查看与优先级关联的%left//标志——意味着减少，意味着移位，而%right意味着两者都不做，并将其视为语法错误。%nonassoc%left%right%nonassoc

剩下的唯一棘手的部分是令牌和规则如何获得优先级。%left令牌从它们所在的//指令中获取令牌%right，%nonassoc该指令也设置了顺序。%prec规则从指令或右侧最右边的终端获得优先权。所以当你有：

%left '*'
%left '+'

expr: expr '+' expr
    | expr '*' expr
    ;

您正在使用指令设置'*'和的优先级，并且这两个规则从这些标记中获取其优先级。'+'%left

当你有：

%left MULTIPLY
%left PLUS

expr: expr '+' expr %prec PLUS
    | expr '*' expr %prec MULTIPLY
    ;

您正在设置标记的优先级MULTIPLY，PLUS然后显式设置规则以具有这些优先级。但是，您没有为标记'*'和设置任何优先级'+'。因此，当两个规则之一与'*'or之间存在移位/归约冲突时'+'，优先级不会解决该冲突，因为令牌没有优先级。