解析器如何解决移位/减少冲突?

Question

我有一个算术表达式的语法，它可以解决文本文件中的表达式数量(每行一个)。在编译 YACC 时，我收到消息 2 移位减少冲突。但我的计算是正确的。如果解析器提供正确的输出，它如何解决移位/减少冲突。就我而言，有什么方法可以在 YACC 语法中解决它。

雅克语法

Calc  : Expr               {printf(" = %dn",$1);} 
| Calc Expr          {printf(" = %dn",$2);}
| error              {yyerror("nBad Expressionn ");}
;
Expr  : Term               { $$ = $1;         }
| Expr '+' Term      { $$ = $1 + $3;    }
| Expr '-' Term      { $$ = $1 - $3;    }
;
Term  : Fact               { $$ = $1;         }
| Term '*' Fact      { $$ = $1 * $3;    }
| Term '/' Fact      { if($3==0){ 
yyerror("Divide by Zero Encountered.");
break;}
else
$$ = $1 / $3;    
}
;
Fact  : Prim               { $$ = $1;        }
| '-' Prim           { $$ = -$2;       }
;      
Prim  : '(' Expr ')'       { $$ = $2;        }
| Id                 { $$ = $1;        }
;
Id    :NUM                 { $$ = yylval;    }
;

我应该做什么更改来消除语法中的此类冲突？

Answer 1

Bison/yacc 通过选择换档来解决移位-减少冲突。这在野牛手册的"换档-减少冲突"一节中进行了解释。

您的问题是您的输入只是一系列Expr，它们之间没有任何分隔符。这意味着：

4 - 2

可以是一个表达式(4-2)，也可以是两个表达式(4，-2)。由于野牛生成的解析器总是喜欢移位，因此解析器会选择将其解析为一个表达式，即使它是在两行上键入的：

4
-2

如果你想允许用户在没有任何分隔符的情况下键入这样的表达式，那么你可以忍受冲突(因为它是相对良性的)，或者你可以把它编入你的语法中，但这需要做更多的工作。要将其放入语法中，您需要定义两种不同类型的Expr：一种(这是您在顶层使用的那个)不能以一元减号开头，另一种(您可以在其他任何地方使用)允许以一元减号开头。

我怀疑您真正想做的是使用换行符或其他类型的表达式分隔符。这就像将换行符传递到解析器并将Calc更改为Calc: | Calc 'n' | Calc Expr 'n'一样简单。

---

我确定这出现在 SO 的其他地方，但我找不到它。因此，以下是禁止在表达式开头使用一元减号的方法，以便您可以在没有分隔符的情况下一起运行表达式。非终端起始n_不能以一元减号开头：

input:  %empty | input n_expr { /* print $2 */ }
expr:   term | expr '+' term | expr '-' term
n_expr: n_term | n_expr '+' term | n_expr '-' term
term:   factor | term '*' factor | term '/' factor
n_term: value | n_term '+' factor | n_term '/' factor
factor: value | '-' factor
value:  NUM | '(' expr ')'

这将解析与您的语法相同的语言，但不会产生移位-归约冲突。由于它解析相同的语言，因此输入

4
-2

仍将解析为单个表达式;要获得预期的结果，您需要键入

4
(-2)