Bison中的Shift/reduce冲突

Question

我是Bison的新手，遇到了移进/规约冲突的问题......我正在尝试从文件中加载到数组data[]：

struct  _data
{
  char name[50]; 
  char surname[50]; 
  int year;
} data[1000];

这是我 bison 代码的一部分：

%token ID NUM NL EOF 

%%

File   : List EOF
       ;
List   : Record
       | List Record
       ;
Record : Name Surname Year NL  { count++; }
       | NL                    { count++; }
       | /*empty*/
       ;
Name   : ID                    { strcpy(data[count].name, yytext); }
       ;
Surname: ID                    { strcpy(data[count].surname, yytext); }
       ;
Year   : NUM                   { data[count].year= atoi(yytext); }
       ;

%%            

我遇到了这个错误：

conflicts: 5 shift/reduce

我哪里做错了，有什么想法吗？

- Zrinka

Answer 1

你可以使用-v选项让bison生成一个包含更多信息的.output文件，这有助于你诊断移位/归约冲突。特别是，它会显示每个解析器状态，包括项目列表，并指示哪些状态存在冲突。

但在这种情况下，问题相当简单。简化后的问题如下：

List  : Record

Record: Something
      | /* Nothing */

忽略 Something 的定义，问题在于一个 List 可以由任意数量的 Records 构成，一个 Record 可以为空。这意味着任何内容都可以被解析为空的任意数量的 Records，这是完全模糊不清的。输入中的任何两个连续的 Somethings 可以由 0、1、2、42 或 273 个空的 Records 分隔开。由于解析器无法确定是开始解析新的 Something（移位）还是发出空的 Record（规约），它会抱怨存在移位/规约冲突。

解决方案也很简单。我们可以看到一个非空的 Something 必须以 NL 结尾；假定意图是 File 由任意数量的 Records 组成，每个记录占一行。因此我们可以改写为：

List  : Record
      | List NL Record

Record: Name Surname Year
      | %empty

现在一个空的或者非空的Record，必须跟着一个NL 或者任何可以跟在List之后的东西（在这种情况下为输入结束指示符，尽管通常不需要显式添加这样的规则）。它不能直接跟在另一个Record之后。

- rici