c - 转移/减少冲突 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 文件，其中包含各种好东西，包括移位/归约冲突的诊断信息。它会向您展示 DFA 的所有状态以及发生冲突的位置，有时还会向您展示确切原因。

在他们自己的产品中逻辑上将否定放在“术语”和“因素”之间“应该可以解决问题。