Shift/reduce 解析包含以双斜杠结尾的斜杠分隔字段的数据格式时出错

Question

我正在解析一系列行，其中每行包含多个字段。字段由斜杠分隔。最后一行以两个斜线结束。每行末尾的几个字段是可选的；省略时，相应的斜杠同样被省略。我遇到 shift/reduce 冲突。

我创建了一个最小可重现示例来说明。只有一行，包含两个字段，第二个字段是可选的，该行以两个斜杠结尾。以下是两个示例输入：

/1/2//

/1//

下面是我的词法分析器和解析器。 Bison 引发 shift/reduce 错误消息。我想我知道为什么 Bison 会引发 shift/reduce 错误：在解析第一个字段后（例如，在解析“1”之后）遇到斜杠，Bison 不知道是减少（只有一个字段）还是转移（即将到来的第二个领域）。因此存在歧义，因此出现 shift/reduce 错误。那是对的吗？有没有办法修改语法以消除歧义？

这是我的 .l 文件：

%{
#include "helloworld.tab.h"
%}

%%
"/"             { return yytext[0]; }
[ ]+
[0-9]+          { return(DGT); }
%%
int yywrap(){ return 1;}

这是我的 .y 文件：

int yylex(void);
extern FILE *yyin;
void yyerror(const char* msg);
%}

%token DGT

%%
test: row '/' '/' 
 ;
 
row: '/' DGT '/' DGT        
 | '/' DGT                   
 ;
%%

int main(int argc, char *argv[])
{  
    yyin = fopen(argv[1], "r");
    
    yyparse();
    
    fclose(yyin);
    
    return 0;
}

void yyerror(const char *msg)
{
  fprintf(stderr, "%s\n", msg);
}

Answer 1

这是一个简单的解决方案，实际上与您开始使用的更通用的语法相似：

/* This extra production allows the parser to recognise multiple lines
 * It requires that your lexer returns `'\n'` when it reads one.
 */
file  : %empty | file line '\n'
line  : fields '/' '/'
fields: %empty | fields field
field : '/' DGT

这里最大的区别是解析器总是从到那时为止看到的字段中生成 fields，这意味着开始字段的 / 和/ 开始行尾指示器。

当然，行尾指示符在这种情况下有点多余，因为语法也恰好坚持该行以换行符结束。把它放在一个单独的产品中有点武断，但它似乎更符合你的实际问题。

Shift/reduce 解析包含以双斜杠结尾的斜杠分隔字段的数据格式时出错

Shift/reduce error in parsing a data format containing slash-separated fields that end in a double slash

bison

flex-lexer

yacc

lex