野牛 reduce/reduce 冲突

Question

我写了下面的语法：

%union{
    string *s;
    float num;
}
%token div_token mod_token sqrt_token it_token abs_token
%token <num> num_token 
%token <s> Stampa
%type <num> E


%left '+' '-'
%left '*' '/' div_token mod_token
%left UMINUS
%left abs_token sqrt_token


%%

Program: Program Line '\n'   { }
| Line  '\n' { }
;

Line: Stampa    {cout<<*<<endl;}
| E         {cout<<<<endl; broj = ;}
| it_token      {cout<<broj<<endl;}
;

E: E '+' E {$$ =  + ;}
| E '-' E {$$ =  - ;}
| E '*' E {$$ =  * ;}
| E '/' E {if(!=0) 
              $$ =  / ;
            else
              yyerror("Deljenje nulom");
            }
| mod_token E E {$$ = (float)((int) % (int));}
| div_token E E {$$ = (float)((int)( / ));}
| sqrt_token E  { $$ = sqrt(); }
| '(' E ')' {$$=;}
| abs_token E { $$ = abs();}
| '-' E %prec UMINUS {$$=-;}
| num_token {$$ = ;}
;

现在，bison 发现了 8 个 reduce/reduce 冲突。当我删除行

| '-' E %prec UMINUS {$$=-;}

有none。我认为优先级和关联属性定义明确。谁能告诉我如何解决冲突？

Answer 1

Now, bison found 8 reduce/reduce conflicts. When I delete line

| '-' E %prec UMINUS {$$=-;}

there are none. I think priorities and associative property are well defined. Can someone tell me how to resolve conflicts?

这应该可以解决问题：

%union{
      string *s;
      float num;
}
%token div_token mod_token sqrt_token it_token abs_token
%token <num> num_token 
%token <s> Stampa
%type <num> E

%left '+' '-'
%left '*' '/' div_token mod_token
%left UMINUS
%left abs_token sqrt_token

%%

Program: Program Line '\n'   { }
| Line  '\n' { }
;

Line: Stampa    {cout<<*<<endl;}
| E         {cout<<<<endl; broj = ;}
| it_token      {cout<<broj<<endl;}
;

E: E '+' E {$$ =  + ;}
| E '-' E {$$ =  - ;}
| E '*' E {$$ =  * ;}
| E '/' E {if(!=0) 
                $$ =  / ;
                    else
                yyerror("Deljenje nulom");
          }
| E mod_token E {$$ = (float)((int) % (int));}
| E div_token E {$$ = (float)((int)( / ));}
| sqrt_token E  { $$ = sqrt(); }
| '(' E ')' {$$=;}
| abs_token E { $$ = abs();}
| '-' %prec UMINUS E {$$=-;}
| num_token {$$ = ;}
;

这解决了几个问题。你的意思可能是：

| E mod_token E {$$ = (float)((int) % (int));}
| E div_token E {$$ = (float)((int)( / ));}

并且这样写更清楚：

| '-' %prec UMINUS E {$$=-;}

您可以看到与产生 xyz.output:

的 bison 选项 -v 的冲突

state 35

    6 E: E . '+' E
    7  | E . '-' E
    7  | E '-' E .
    8  | E . '*' E
    9  | E . '/' E
   15  | '-' E 

.

    div_token   reduce using rule 7 (E)
    div_token   [reduce using rule 15 (E)]
    mod_token   reduce using rule 7 (E)
    mod_token   [reduce using rule 15 (E)]
    sqrt_token  reduce using rule 7 (E)
    sqrt_token  [reduce using rule 15 (E)]
    abs_token   reduce using rule 7 (E)
    abs_token   [reduce using rule 15 (E)]
    num_token   reduce using rule 7 (E)
    num_token   [reduce using rule 15 (E)]
    '+'         reduce using rule 7 (E)
    '+'         [reduce using rule 15 (E)]
    '-'         reduce using rule 7 (E)
    '-'         [reduce using rule 15 (E)]
    '*'         reduce using rule 15 (E)
    '/'         reduce using rule 15 (E)
    '\n'        reduce using rule 15 (E)
    '('         reduce using rule 7 (E)
    '('         [reduce using rule 15 (E)]
    ')'         reduce using rule 15 (E)
    $default    reduce using rule 7 (E)

div_token 和 mod_token 上的运算符缩减值得怀疑。语法的歧义是由应用于两个表达式 E.

的这些运算符引起的

编辑

也许您希望保留前缀 div 和 mod 运算符。如果是这样，您需要消除语法歧义。一种可能的解决方案是：

| mod_token F F {$$ = (float)((int) % (int));}
| div_token F F {$$ = (float)((int)( / ));}
| F
;
F: '(' E ')' {$$=;}
| sqrt_token E  { $$ = sqrt(); }
| abs_token E { $$ = abs();}
| '-' %prec UMINUS E {$$=-;}
| num_token {$$ = ;}
;

并添加F的类型：

%type <num> E F

Answer 2

优先关系仅用于解决shift/reduce 冲突。它们不能用于解决 reduce/reduce 冲突，因为优先级比较总是在 production（可以减少）和 token 之间（可以移动）。

考虑到这一点，考虑解析表达式的过程：

div 7 - 3 - 2

（假设 div 是你写 div_token 的方式）。

每个 - 可以是中缀减法运算符或前缀否定运算符。在这种情况下，由于 div 后面必须正好跟两个表达式，因此恰好有一个减号必须是中缀。但是哪个？是吗

div (7-3) (-2)

或

div (7) (-3-2)

当然，其他情况也是可能的。如果表达式是 div 7 - 3 - 2 a，则唯一有效的解析将是 div ((7-3)-2) 8，而如果表达式是 div div 7 - 3 - 2，则解析必须是 div (div 7 (-3)) (-2)。

您可以通过让 bison 使用 -v 选项创建解析报告并查看生成的 .output 文件来更深入地了解冲突。根据您的语法，该报告显示 reduce/reduce 冲突处于状态 35，即：

State 35

    6 E: E . '+' E
    7  | E . '-' E
    7  | E '-' E .
    8  | E . '*' E
    9  | E . '/' E
   15  | '-' E .

    div_token   reduce using rule 7 (E)
    div_token   [reduce using rule 15 (E)]

(actions truncated for space)

可能的减少对应LR项末尾有.，分别是E '-' E .和'-' E .。对于大多数（但不是全部）前瞻标记，这些减少中的任何一个都是可能的。（如果 * 是先行字符，* 优先于 E: E '-' E 规则排除了第一次减少的可能性；类似地 /。）

像这样混合中缀和前缀表达式通常不是一个好主意，正是因为这种歧义。

野牛 reduce/reduce 冲突

Bison reduce/reduce conflicts

bison

reduce-reduce-conflict