解析器如何解决 shift/reduce 冲突？

Question

我有一个算术表达式的语法，它解决了文本文件中表达式的数量（每行一个）。在编译 YACC 时，我收到消息 2 shift reduce conflicts。但我的计算是正确的。如果解析器给出正确的输出，它如何解决 shift/reduce 冲突。就我而言，有什么方法可以在 YACC 语法中解决它。

YACC 语法

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

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

Answer 1

Bison/yacc 通过选择转移来解决 shift-reduce 冲突。 Shift-Reduce 冲突部分的 bison manual 对此进行了解释。

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

4 - 2

可以是一个表达式（4-2），也可以是两个表达式（4、-2）。由于 bison-generated 解析器总是喜欢移位，因此解析器将选择将其作为一个表达式来解析，即使它是分两行输入的：

4
-2

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

我怀疑您真正想做的是使用换行符或其他某种表达式分隔符。这就像将换行符传递给解析器并将 Calc 更改为 Calc: | Calc '\n' | Calc Expr '\n'.

一样简单

我确定它出现在 SO 的其他地方，但我找不到它。所以这里是你如何禁止在表达式的开头使用一元减号，这样你就可以运行表达式在一起而不用定界符。以 n_ 开头的 non-terminals 不能以一元减号开头：

input:  %empty | input n_expr { /* print  */ }

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

解析与您的语法相同的语言，但不会产生 shift-reduce 冲突。由于它解析相同的语言，因此 input

4
-2

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

4
(-2)

解析器如何解决 shift/reduce 冲突？

How does a parser solves shift/reduce conflict?

parsing

yacc

shift-reduce-conflict