1

我写了以下语法： 

%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<<*$1<<endl;}
| E         {cout<<$1<<endl; broj = $1;}
| it_token      {cout<<broj<<endl;}
;

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

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

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

没有了。我认为优先级和关联属性定义明确。有人可以告诉我如何解决冲突吗？

4

2 回答 2

2

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

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

没有了。我认为优先级和关联属性定义明确。有人可以告诉我如何解决冲突吗？

这应该可以解决问题：

%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<<*$1<<endl;}
| E         {cout<<$1<<endl; broj = $1;}
| it_token      {cout<<broj<<endl;}
;

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

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

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

更清楚的是写下以下内容：

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

您可以看到与 bison 选项的冲突，-v该选项产生xyz.output：

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)$2 % (int)$3);}
| div_token F F {$$ = (float)((int)($2 / $3));}
| F
;
F: '(' E ')' {$$=$2;}
| sqrt_token E  { $$ = sqrt($2); }
| abs_token E { $$ = abs($2);}
| '-' %prec UMINUS E {$$=-$2;}
| num_token {$$ = $1;}
;

并添加类型F：

%type <num> E F
于 2017-07-10T16:24:42.407 回答
1

优先关系仅用于解决移位/减少冲突。它们不能用于解决归约/归约冲突，因为优先级比较总是在产生式（可以归约）和令牌（可以移动）之间进行。

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

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)。

-v您可以通过要求 bison 使用该选项创建解析报告并查看.output生成的文件来更深入地了解冲突。根据您的语法，该报告显示减少/减少冲突处于状态 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)

可能的减少对应于.末尾带有 a 的 LR 项，即E '-' E .和'-' E .。对于大多数（但不是全部）前瞻令牌，这些减少中的任何一个都是可能的。（如果是前瞻字符，*则规则的优先级E: E '-' E排除了第一次归约的可能性；对于 . 也是如此。）*/

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

于 2017-07-10T17:16:50.423 回答