c - 转移/减少 Bison 中的冲突

Question

我的 Bison 解析器中有很多错误，即使它运行良好，我也想了解这些冲突。代码如下:

词法分析器:

id          ([[:alpha:]]|_)([[:alnum:]]|_)*
%%

{id} {
  yylval.val=strdup(yytext);
  return(ID);
}

解析器:

%union {
char* val;
}

%token<val> ID
%type<val> DD1 DD

%start Input

%%

Input:
      %empty
    | DD
;
DD:
    DD1 ID {$$=strcat($1, $2);}
DD1:
      %empty {$$=strdup("");}
    | ID    {$$=$1;}
;
%%

错误是:1 转移/减少冲突 和 由于冲突而无用的规则:%empty...有人可以帮助我吗？谢谢。

ps:这不是我的实际代码，我知道 strcat 不会工作等，这只是问题的概述。

Answer 1

当解析器看到 ID 处于包含项目的状态时

DD <- . DD1 ID 

和

DD1 <- . ID, 

...它不知道是否应该对 DD 进行 epsilon-reduce 并继续处理具有状态的项目

 DD <- DD1 . ID

或移动ID并继续到具有项目的状态

 DD1 <- ID .

这是您的 S/R 冲突。生成的解析器总是倾向于转移来解析 S/R，因此归约永远不会发生，因此 DD1: %empty 规则毫无用处。

您可以简单地切换第三条规则的顺序来解决此问题，并且 DD 仍然是“一个或两个 ID”。

DD:
    ID DD1 {$$=strcat($1, $2);}