如何避免 shift/reduce 与多个操作数的产生冲突

Question

对于定义图形的简单语言，我有以下冲突规则：

  rm_arcs: RM ARC VARNAME VARNAME ref_exp ref_exp 
    {
      $$ = new RmArcNodes(, , , ); 
    }
  | RM ARC VARNAME ref_exp ref_exp 
    {
      $$ = new RmArcNodes(, , ); 
    }

Which bisons 说它会导致 3 shift/reduce 次冲突。

ref_exp规则定义如下：

ref_exp : STRCONST
          {
            auto symbol = string_table();
            $$ = new StringExp(symbol);
          }
        | INTCONST
          {
             auto symbol = id_table();
             $$ = new IntExp(symbol);
          }
        | VARNAME
          {
            auto varname = var_tbl();
            if (varname == nullptr)
              {
                stringstream s;
                s << "var name " <<  << " not found";
                $$ = new ErrorExp(s.str());
              }
            else
              $$ = varname;
          }
;

有没有什么简单的方法可以重写语法来消除这些冲突并且不修改语言？

此致

Answer 1

你应该能够通过简单地向 Bison 更清楚地解释你想要什么来做到这一点。添加 ref_exp_without_varname 产生式（实现显而易见）。

然后改变

rm_arcs: RM ARC VARNAME VARNAME ref_exp ref_exp 
   | RM ARC VARNAME ref_exp ref_exp

进入

rm_arcs: RM ARC VARNAME ref_exp_without_varname ref_exp
       | RM ARC VARNAME VARNAME ref_exp
       | RM ARC VARNAME VARNAME ref_exp ref_exp

我认为这应该是一样的但没有冲突，因为我明确地消除了第 4 个条目的歧义。

Answer 2

问题是语法读完RM ARC VARNAME后又收到另一个VARNAME，不知道用哪个规则工作，导致shift reduce冲突。

一种解决方法是：

%token RM ARC VARNAME STRCONST INTCONST

%%

rm_arcs:
        RM ARC VARNAME ref_exp_list
    ;

ref_exp_list:
        VARNAME
    |   ref_exp_list ref_exp
    ;

ref_exp:
        STRCONST
    |   INTCONST
    |   VARNAME
    ;

这允许在第一个 VARNAME 之后有任意数量的 ref_exp 值，但这些值中的第一个必须是 VARNAME。您将有一个语义操作来限制列表的长度（因此 RM ARC VARNAME VARNAME INT_CONST INT_CONST INT_CONST 将被拒绝）。

如何避免 shift/reduce 与多个操作数的产生冲突

How to avoid shift/reduce conflict with a production of several operands

c++

bison