shift/reduce冲突yacc

Question

请参阅以下yacc代码。如果我去掉生产因子：'!‘expr，解析冲突就消失了。这是怎么回事？

%{
#include <stdio.h>
#include <ctype.h>

%}


%token TRUE
%token FALSE


%%
line    : line expr '\n'    {   printf("%d\n", $2); }
    | line '\n'
|
;
expr    :   expr "or" term  {   printf("expr : expr or term\n"); $$ = $1 | $3; }
|   term        {   printf("expr : term\n");     }
;
term    :   term "and" factor   {   printf("term : term and factor\n"); $$ = $1 & $3; }
|   factor      {   printf("term : factor\n");  }
;
factor  :   '(' expr ')'    {   printf("factor : (expr)\n"); $$ = $2; }
|   '!' expr    {   printf("factor : !expr\n"); $$ = !$2;   }
|   TRUE        {   printf("factor : TRUE\n");  }
|   FALSE       {   printf("factor : FALSE\n"); }
;
%%

#include "lex.yy.c"

int main(int argc, char** argv)
{
while (yyparse() == 0) {
    }

    return 0;
}

Answer 1

在我看来，冲突可能是因为当解析器看到'!‘时，它在重写'expr’时遇到了问题。忽略“factor”的其他结果，具体来看这两个结果：

expr    : expr "or" term  { printf("expr : expr or term\n"); $$ = $1 | $3; }
        | term            { printf("expr : term\n"); }
        ;

factor  : '!' expr        { printf("factor : !expr\n"); $$ = !$2; }

因为expr是递归的，所以当解析器看到'!‘时，它知道否定适用于下面的expr，但是如果你写"！TRUE OR TRUE"，那么这个否定只适用于第一个true，还是适用于整个析取？

编辑:换句话说，它不能决定是否需要移动" or“或减少"expr”。

在yacc中设置-v命令行选项将生成一个包含各种好处的.output文件，包括shift/reduce冲突的诊断信息。它将向您显示DFA的所有状态以及冲突发生的位置，有时还会向您显示确切的原因。

在“术语”和“因子”之间逻辑地将否定放在他们自己的产品中，应该会起到作用。

Answer 2

如果您将factor: ! expr更改为factor: ! factor，冲突将会消失。

仅分析第一个冲突，问题是term可能会简化为expr或成为更复杂的term。如果没有!，只需使用一个前视符号即可做出此决定。

请注意，shift/reduce冲突不一定是错误。冲突可以通过转换来解决，这很可能是您想要的。大多数实际的产生式语法都包含许多shift/reduce冲突。