1

假设此代码有效：

left '*'
left '+'

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

我想定义其他优先级标记，例如：

left MULTIPLY
left PLUS

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

然而这实际上并不有效。

我想这两种形式应该是等价的，但是，它们不是。

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

谢谢。

4

3 回答 3

4

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

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

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

优先规则解决移位减少冲突的方式是通过为语法中的某些标记和规则分配优先级。每当要移动的令牌和要减少的规则之间存在移位/减少冲突时，并且两者都有优先级，它将执行具有更高优先级的那个。如果它们具有相同的优先级，那么它会查看与优先级关联的//标志——%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之间存在移位/减少冲突时'+'，优先级不会解决它，因为令牌没有优先级。

于 2013-09-21T20:27:50.893 回答
3

你说你不是在试图解决一个具体的、实际的问题。从你的问题来看，我对你如何尝试使用优先标记有点困惑。

我想你会发现你不需要经常使用优先级标记。重写语法以明确说明优先级，通常对读者来说更简单、更清晰。要使乘法和除法的优先级高于加法和减法，您可以执行以下操作（示例改编自 John Levine, lex & yacc 2/e, 1992）：

%token NAME NUMBER

%%

stmt : NAME '=' expr
     | expr
     ;

expr : expr '+' term
     | expr '-' term
     | term
     ;

term : term '*' factor
     | term '/' factor
     | factor
     ;

factor : '(' expr ')'
       | '-' factor
       | NUMBER
       ;

在您的示例中，PLUS并且MULTIPLY不是真正的令牌；您不能将它们与'+'and互换使用'*'。莱文称它们为伪代币。它们在那里将您的产品链接回您定义的优先级列表%left和%nonassoc声明。他给出了这个例子，说明%prec即使“-”标记的优先级较低，您也可以使用一元减高优先级：

%token NAME NUMBER
%left '-' '+'
%left '*' '/'
%nonassoc UMINUS

%%

stmt : NAME '=' expr
     | expr
     ;

expr : expr '+' expr
     | expr '-' expr
     | expr '*' expr
     | expr '/' expr
     | '-' expr %prec UMINUS
     | '(' expr ')'
     | NUMBER
     ;

总而言之，我建议遵循我的第一个代码示例的模式，而不是第二个；使语法明确。

于 2012-06-11T23:29:18.333 回答
0

Shift-reduce 冲突是尝试减少生产与转移令牌和移动到嵌套状态之间的冲突。当 Bison 解决冲突时，它不会比较两条规则并选择其中一条 - 它比较它想要减少的一条规则和你想要在其他规则中转移的令牌。如果您有两条规则要转换，这可能会更清楚：

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

这一切令人困惑的原因是 Bison 为“减少”规则提供优先级的方式是将其与令牌（默认情况下规则中的最后一个终端或 prec 声明中的令牌）相关联，然后它使用优先级表将该令牌与您尝试转移的令牌进行比较。基本上，prec 声明仅对冲突的“减少”部分有意义，并且它们不计入转换部分。

看到这一点的一种方法是使用以下语法

command: IF '(' expr ')' command               %prec NOELSE
       : IF '(' expr ')' command ELSE command

在此语法中，您需要在减少第一条规则或移动 ELSE 标记之间进行选择。您可以通过为 ')' 标记和 ELSE 标记提供优先权，或者通过使用 prec 声明并为 NOELSE 而不是 ')' 提供优先权来做到这一点。如果您尝试对第二个进行 prec 声明，它将被忽略，并且 Bison 将继续尝试在优先表中查找 ELSE 令牌的优先级。

于 2013-09-21T14:13:50.173 回答