yacc中生成IR码时如何避免冲突？

Question

%nonassoc NO_ELSE
%nonassoc ELSE

stmt_conditional
     : IF '(' expr { show_if_begin(); } ')' stmt_compound { show_if_end(); } %prec NO_ELSE
     | IF '(' expr { show_if_begin(); } ')' stmt_compound { show_if_else(); }  ELSE stmt_compound { show_if_end(); }

由于stmt_compound会生成IR，所以show_if_begin()应该在stmt_compound之前。但是，这会导致 yacc 中的 reduce/reduce 冲突。如何解决这个问题？

已编辑

这是我试过的方法，但没有用。

stmt_conditional
     : stmt_cond_if { show_if_end(); } %prec NO_ELSE
     | stmt_cond_if { show_if_else(); } ELSE stmt_compound { show_if_end(); }
     ;

stmt_cond_if
     : IF '(' expr { show_if_begin(); } ')' stmt_compound

Answer 1

你的变体不起作用的原因是你需要无限的 lookakead 来区分这两种 if 语句。当您的解析器查看一个 IF 令牌时，它不知道它是否会看到 ELSE 或 NO_ELSE，或者如果是的话，它何时会期待一个，但它必须决定要转移到哪里现在[=46] =] 以便处理表达式。

解决方案是找出更常见的东西，以便在需要时准确做出决定。

stmt_conditional : stmt_cond_if { ... } else_part ; else_part : %prec NO_ELSE | ELSE stmt_compound { ... } ;

理论上，解析器生成器应该能够自动重构这些规则，但规则中间的代码块阻止yacc这样做。即使是其他方面相同的规则中的空代码块也会阻止它们被展平。那是因为 yacc 将代码块的内容视为黑框。它不知道这些动作 的意思 并且不得不假设它们都可能意味着不同的东西，即使文本是相同的。

您可以验证当您删除这些操作时，冲突就消失了。当然，没有动作的 yacc 语法用处不大。

自然地，这个 factoring-out 统一了您对 THEN 的操作，这些操作最初对于 else 和 no-else 变体是不同的。没有办法解决这个问题。您必须编写对这两种情况都适用的操作。

Edit 实际上，这样的代码块由 yacc 处理，方法是为每个 [=55= 创建一个新的不可见规则和一个新的 non-terminal ] 行动。引用 yacc 页面：

Actions that do not terminate a rule are actually handled by Yacc by manufacturing a new nonterminal symbol name, and a new rule matching this name to the empty string. The interior action is the action triggered off by recognizing this added rule.

正是这些无形的规则实际上导致了语法冲突。因此，另一种解决方案是保留规则原样，但将操作移至各自规则的末尾。我个人还是喜欢手动分解出通用部分。 -- 结束编辑.

没有 %prec 会有一个 shift/reduce 警告，因为

if (x) if (y) do_something else do_something_else

是有歧义的：当解析器看到else时，它不知道它是属于内部的if（移位）还是外部的（归约）。默认行为是移动，这是我们通常想要的。 %prec 明确说明并消除警告。

请注意，这仍然可能会影响您其余的语法。如果您可以更改语法，我建议您从 C-like compound-statement-based 语法切换到 ENDIF-based 语法，例如艾达

yacc中生成IR码时如何避免冲突？

How to avoid conflicts when generating IR codes in yacc?

c

yacc