我怎样才能消除同一个操作员的轮班归约冲突

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 作为 "binary operator"，所以我无法解决通过将优先级设置为运算符来解决此冲突。

也许我可以通过以某种方式向 stmt

添加另外两条规则来合并 program 规则和 stmts 规则

stmts : function CRLF stmts
    | function

不过我觉得这个方法（能不能实际使用）不是很漂亮，所以请问有没有其他的解决方法

Answer 1

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

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

由于语法不明确，解析器无法判断需要哪些备选方案。这就是造成冲突的原因。

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

顺便说一下，在编写 LR 文法时，您应该始终首选左递归。右递归通常不会产生冲突，它与您当前的问题无关，但它确实会导致不必要的 Iarge 解析堆栈，并且 units 和 stmts 等列表的减少将从执行从右到左，因为组件从堆栈中弹出，这通常不是预期的。

我怎样才能消除同一个操作员的轮班归约冲突

How can I eliminate shift-reduce conflicts by the same operator

grammar

parsing

bison

shift-reduce-conflict

lr