如何消除同一个运算符的shift-reduce冲突

Question

我打算使用bison来解析一些脚本语言，用这种语言我可以编写如下代码：

a = input()
b = a + 1
function myfunc
    a = input()
    b = a + 1
end function

我发现这个街区

a = input()
b = a + 1

在函数定义内部和外部都可以使用相同的规则stmts来减少，所以我编写了如下代码

%{
#include <stdio.h>
#include <string>
#include <sstream>
#include <iostream>
#include <stdarg.h>
#include <tuple>

using namespace std;
%}

%debug

%token CRLF EXP FUNCTIONBEGIN FUNCTIONEND

%start program

%%

stmt : EXP
    |
stmts : stmt CRLF stmts
    | stmt
function : FUNCTIONBEGIN CRLF stmts CRLF FUNCTIONEND
unit : function
    | stmts
program : unit
    | unit CRLF program

%%

当然，这段代码不能工作，因为有一个shift/reduce冲突

State 3

    3 stmts: stmt . CRLF stmts
    4      | stmt .

    CRLF  shift, and go to state 9

    CRLF      [reduce using rule 4 (stmts)]
    $default  reduce using rule 4 (stmts)

我认为这个冲突是由于我的program规则和stmts规则都使用了相同的终端CRLF作为“二元操作符”，所以我不能通过为操作符设置优先级来解决这个冲突。

也许我可以通过将另外两个规则添加到stmt中，将program规则和stmts规则合并在一起

stmts : function CRLF stmts
    | function

然而，我认为这种方法(它是否可以实际工作)并不是很好，所以我问是否有其他解决方案

Answer 1

该问题与CRLF令牌无关。相反，这是您对program的定义。program是一系列的unit，其中每个单元都是function或stmts。但是stmts不是一个“单位”，它的名字是复数就暗示了这一点。stmts是一系列的stmt。

假设我们有一个由三个语句组成的程序。那是多少个unit？它是由所有三个语句组成的一个stmts吗？还是两个，一个有两个语句，另一个只有一个？或者反过来呢？或者甚至是三个unit，每个stmts包含一条语句？

由于语法不明确，解析器无法分辨出这些选项中的哪个是所需的。这就是造成冲突的原因。

最简单的解决方案是将生产unit: stmts更改为单数：unit: stmt。这样就没有歧义了；包含三个语句的program恰好有三个unit，每个都有一个stmt。

顺便说一下，在编写LR文法时，您应该始终倾向于使用左递归。右递归通常不会产生冲突，它与您当前的问题没有任何关系，但它确实会导致不必要的庞大解析堆栈，并且当组件从堆栈中弹出时，units和stmts等列表的缩减将从右向左执行，这通常不是预期的结果。