"obvious" shift/reduce 错误不超过 6 个标记

Question

我有一个语法，如下图所示，其中语句有一个错误子句，可以包含任意数量的语句。错误子句必须以 END 结束（如 shell 中的 case/esac）。在没有错误子句的情况下，语句可以终止，但不必如此。

野牛报告显示 2 s/r 冲突。在每种情况下，冲突都与如何处理终止符有关：

shift，进入只减少它的状态，或者
减少它

这对我来说似乎是一个没有区别的区别，但我无法向野牛解释。

我确信我遗漏了一些基本的东西。我希望有人能解释它是什么。

%token ERROR ARG

%right WALK RUN
%left  KLAW NUR 
                        
%%

statements:     statement
        |       statements statement
                ;

statement:      walk
        |       run
                ;

args:           ARG
        |       args ARG
                ;

on_error:       ERROR statements
                ;

walk:           WALK ARG args on_error KLAW
        |       WALK ARG args
        |       WALK ARG args          KLAW 
                ;

run:            RUN ARG args on_error NUR
        |       RUN ARG args          nur
                ;

nur:            %empty
        |       NUR
        ;

这是我正在查看的部分报告：

State 12

    6 args: args . ARG
    8 walk: WALK ARG args . on_error KLAW
    9     | WALK ARG args .
   10     | WALK ARG args . KLAW

    ERROR  shift, and go to state 14
    ARG    shift, and go to state 15
    KLAW   shift, and go to state 16

    KLAW      [reduce using rule 9 (walk)]
    $default  reduce using rule 9 (walk)

    on_error  go to state 17
...
State 16

   10 walk: WALK ARG args KLAW .

    $default  reduce using rule 10 (walk)

Answer 1

考虑以下短程序（六个标记，但我通过省略 ARG 作弊，因为它们只是杂乱无章。你可以假装每个 WALK 之后至少有两个 ARG，但这对问题。为了清楚起见，我还对 WALK 进行了下标）

WALK-1 ERROR WALK-2 KLAW WALK-3 KLAW

这是什么意思？选项是（KLAW 编号以匹配他们的 WALK）：

    WALK-1
      ERROR WALK-2
    KLAW-1
    WALK-3 KLAW-3

或

    WALK-1
      ERROR WALK-2 KLAW-2
            WALK-3
    KLAW-1

我猜它们有不同的语义；在第一个中，WALK-3 总是在 WALK-1 之后运行，而在第二个中，它仅在 WALK-1.

中出现错误时运行

您可能误读了 Bison 向您呈现的状态 table。在状态 12 中，冲突选项是减少使用生产 9 (walk: WALK ARG args) 留下 KLAW 以匹配其他一些 WALK，或者转移 KLAW 然后减少使用生产 10 (walk: WALK ARG args KLAW)，表示KLAW匹配thisWALK.

您也可能想知道为什么您的优先声明没有效果。

优先规则用于解决冲突，例如在状态 12 中，先行标记可能会被移动或保留，直到经过一次或多次归约。解决方案是将前瞻标记的优先级（在本例中为 KLAW）与可以降低的产生式的优先级（walk: WALK ARG args）进行比较。如果先行标记具有更高的优先级，则移动先行标记；如果生产具有更高的优先级，则生产减少。如果它们具有相同的优先级，则应用关联性（减少 %left；移位 %right）。

很好，但是 Bison 如何计算 walk: WALK ARG args 的优先级？简单的答案是，Bison 在生产中使用 last 终端的优先级，在本例中为 ARG。但是 ARG 没有声明的优先级，所以产生式的优先级是未指定的，只有当规则和标记都定义了优先级时才适用优先级解析。

为了让优先级解析有用，您必须：

将 ARG 添加到您的优先声明中，或
使用 %prec (q.v.) 将产生式与不同的终端符号相关联。

"obvious" shift/reduce 错误不超过 6 个标记

"obvious" shift/reduce error in 6 tokens or less

bison

yacc