Bison shift/reduce do 块冲突

Question

我无法解决 shift/reduce 冲突。

我正在尝试编写 while 循环语法：

while expression do code() end

问题出在do关键字上

我的一个表达式是一个调用表达式，它也接受一个可选的回调块，例如：

function_call() do print("callback") end

这似乎又导致了 while 循环的 do 关键字中的 shift/reduce 冲突。

所以如果我这样做：

while call() do stuff() end

它反而试图将 do 与函数调用相匹配，并弄乱了整个解析。

Ruby 具有非常相似的语法，但它似乎正确地支持 while 循环而不是表达式的 do 关键字。在 Ruby 中，如果需要，您可以将回调放在括号中，这也是我想解决这个问题的理想方式：

while (call() do stuff() end) do more_stuff() end

我该如何克服这个问题？我在运算符优先级定义上搞砸了很多，但似乎没有任何效果，你会如何解决这个问题？ ruby 是如何做到正确的？

这是重现问题的完整语法：

%token IDENT DO END WHILE

%%

program:
       %empty
       |
       stmts
       ;

stmts:
     stmt
     |
     stmts ';' stmt
     |
     stmts ';'
     ;

opt_stmts:
         %empty
         |
         stmts
         ;

opt_semi:
        %empty
        |
        ';'
        ;

term:
    ';'
    |
    DO opt_semi
    ;

while_loop:
          WHILE expr term opt_stmts END
          |
          WHILE term opt_stmts END
          ;

stmt:
    expr
    |
    while_loop
    ;

expr:
    IDENT
    |
    call
    |
    '(' expr ')'
    ;

do_block:
        DO '|' args '|' opt_stmts END
        |
        DO opt_stmts END
        ;

call:
    IDENT '(' args ')'
    |
    IDENT '(' args ')' do_block
    |
    IDENT do_block
    ;

args:
    %empty
    |
    expr
    |
    args ',' expr
    |
    args ','
    ;

%%

旁注：我正在使用 Jison，它是 JavaScript 的野牛克隆，因为我正在为 JavaScript 编写编译器，但这应该不是问题，因为这是一个一般语法问题和我写的上面的最小片段也已通过原始 Bison 运行。

Answer 1

您已经确定了问题 -- 可能是 WHILE..DO 的一部分或可能是 call-DO 的一部分的 DO 的歧义。这特别困难，因为 DO 在这两种情况下都是可选的，但语法是这样的，一些 DO 可能只与 WHILE 或调用相关联，这取决于它们之后的各种事情，这意味着非歧义的情况不能无论如何都没有更多的前瞻性识别。它还遇到了一些 LALR 与 LR 问题，这也使它变得困难（并且也意味着你不能使用优先级来解决它。）

您可以通过重构语法来解决它，其方式与处理悬空 else 问题的方式大致相同——拆分 expr 规则并仅允许不以 call-DO 结尾的表达式在 WHILE 语句中。这样，WHILE 之后的 DO（而不是在括号中）将始终与 WHILE 相关联，而不是调用。它确实稍微改变了语言——带有可选 ';' 的 WHILE..DO 与中间的调用 DO（没有括号）将被拒绝为语法错误（第一个 DO 将与 WHILE 和第二个 DO 不能是 call-DO，因为 DO 后面紧跟着 ';'.

对于您的示例，这意味着将 expr 规则拆分为 call-DO 大小写和所有其他表达式大小写：

expr: non_call_do_expr | call_withdo ;
non_call_do_expr: IDENT | call_nodo | '(' expr ')' ;


call_nodo: IDENT '(' args ')' ;

call_withdo:
    IDENT '(' args ')' do_block |
    IDENT do_block ;

如果您添加任何其他 expr 规则，则需要将它们添加到 non_call_do_expr 规则中除非它们（可以）以 call-DO 结束.在这种情况下，您需要针对这两种情况的两个版本，这与解决悬空 else 情况的语句所需要的完全一样。 while 然后变成：

while_loop:
          WHILE non_call_do_expr term opt_stmts END |
          WHILE term opt_stmts END ;

Bison shift/reduce do 块冲突

Bison shift/reduce conflict for do block

syntax

parsing

bnf

bison