Bison 中的冲突类型

Question

%token<val>num 
%left '+' '-'

shift/reduce 冲突示例：

Expr:num {$$=};
     |Expr '+' Expr;{};
     |Expr '-' Expr;{};

我想识别 reduce/reduce 冲突。当两个或多个规则应用于相同的输入序列（令牌）

时，就会发生这种情况

例如：

Prod: proda|prodb
     proda :'x'
     prodb : 'x'

任何人都可以提供一些如何轻松识别 reduce/reduce 冲突的想法吗？

Answer 1

好吧，您几乎已经描述了冲突之间的区别。问题是什么？

shift/reduce 冲突意味着 bison 不知道他是否应该 shift（再读取一个终端并将其放在栈顶）或 reduce（转换多个terminals/non-terminals 在堆栈上变成一个新的 non-terminal)。 shift/reduce 表示I don't know - should I apply a rule now or wait a bit, read some text and apply another rule there? 这种冲突通常用shift 操作解决。

reduce/reduce冲突是指有两种或两种以上的方式减少栈顶的terminals/non-terminals。 reduce/reduce 表示 I don't know - should I apply this rule or that rule now?。这个冲突比shift/reduce严重得多——语法有歧义，确实有问题。

通常最好不要识别reduce/reduce，但避免。从一开始就清楚地知道你想做什么。不时修改你的语法。您是否有可能刚刚重新发明了另一条规则？

在调试现有冲突时，bison -v 选项会创建一个 *.output 文件，其中包含对所有冲突的非常长的描述。第一次阅读非常困难，需要了解一些 LR1 parsing 是如何进行的，但阅读它的好处也很大。

Answer 2

最简单的方法是创建 y.output 文件。

使用命令yacc -v parser_name.y。这将为您创建 yacc 工作方式的输出。找到 yacc 说你的冲突所在的状态，然后了解 point sign 是非常重要的。在文件中。

如果您的输出文件是这样的：

4 |Expr. '+' Expr;{};

表达式后的点号是在对你说：“我读过 Expr，在输入时我有‘+’。

Reduce-Reduce 当你遇到这样的情况时会出现冲突：

NON_TERMINAL1: Expr.
NON_TERMINAL2: Expr.

在这种情况下，你有 Expr。在规则的末尾，Yacc 不知道要执行哪个 reduce，这就是 Reduce-Reduce 冲突。

Bison 中的冲突类型

Types of conflicts in Bison

bison

yacc