消除二元运算的移位/归约错误

Question

fsyacc 正在为所有二进制操作发出移位/归约错误。

我有这个递归产生式：

scalar_expr:
    | scalar_expr binary_op scalar_expr { Binary($2, $1, $3) }

更改它以

scalar_expr:
    | constant binary_op constant { Binary($2, Constant($1), Constant($3)) }

消除错误（但这不是我想要的）。优先级和关联性定义如下：

%left BITAND BITOR BITXOR
%left ADD SUB
%left MUL DIV MOD

这是列表文件的摘录，显示了产生错误的状态（另一个状态也有相同的错误）。

state 42:
  items:
    scalar_expr -> scalar_expr . binary_op scalar_expr
    scalar_expr -> scalar_expr binary_op scalar_expr . 

  actions:
    action 'EOF' (noprec):   reduce scalar_expr --> scalar_expr binary_op scalar_expr
    action 'MUL' (explicit left 9999):   shift 8
    action 'DIV' (explicit left 9999):   shift 9
    action 'MOD' (explicit left 9999):   shift 10
    action 'ADD' (explicit left 9998):   shift 6
    action 'SUB' (explicit left 9998):   shift 7
    action 'BITAND' (explicit left 9997):   shift 11
    action 'BITOR' (explicit left 9997):   shift 12
    action 'BITXOR' (explicit left 9997):   shift 13

您可以看到解析器在所有情况下都会发生变化，我认为这是正确的。至少我还没有发现行为不正确的情况。

我怎样才能重述语法来消除这些错误？

Answer 1

binary_op 实际上是一个产生式吗，即您有类似的内容：

binary_op:
   | ADD { OpDU.Add }
   | SUB { OpDU.Sub }
   ...

如果是这样，我认为这就是问题所在，因为我假设您定义的优先规则不会在 constant binary_op 常量中得到遵守代码>.您需要显式枚举每个 scalar_expr 模式，例如

scalar_expr:
    | scalar_expr ADD scalar_expr { Binary(OpDU.Add, $1, $3) }
    | scalar_expr SUB scalar_expr { Binary(OpDU.Sub, $1, $3) }
    ...

（我认为没有任何方法可以使用 FsYacc 抽象掉这种重复性）

Answer 2

正如斯蒂芬在他的回答中指出的那样，如果您将运算符移至单独的生产中，则运算符的优先级规则将不适用。这很奇怪，因为您发布的状态似乎正确地尊重了它们。

但是，您应该能够声明和应用显式优先级规则，例如您可以将它们定义为：

%left ADD_SUB_OP
%left MUL_DIV_OP

并像这样应用它们：

scalar_expr:
    | scalar_expr add_sub_ops scalar_expr %prec ADD_SUB_OP { Binary($2, $1, $3) }
    | scalar_expr mul_div_ops scalar_expr %prec MUL_DIV_OP { Binary($2, $1, $3) }

这样您仍然需要定义多个规则，但您可以将具有相同优先级的所有运算符分组到一个组中（请注意，我选择的名称是一个很差的示例；您可能希望使用反映优先级或描述其中的运算符的名称，以便清楚地了解它们所表示的含义）。

我认为这个解决方案是否值得取决于每组操作员的数量。