Bison/YACC - 避免减少/减少与两个否定规则的冲突

Question

以下语法（其中 INTEGER 是数字序列）会引起归约/归约冲突，因为例如 -4 可以通过 expr -> 来归约。 -expr 或 expr ->数字 -> -整数。在我的语法中，num 和 expr 返回不同的类型，因此我必须区分 -num 和 -expr。我的目标是 -5 减少 num，而例如 -(...) 是一个 expr。我怎样才能做到这一点？

%token      INTEGER

%left       '+'     '-'

%%

start: expr
    ;

expr: expr '+' expr
    | expr '-' expr
    | '-' expr
    | '(' expr ')'
    | num
    ;

num:  INTEGER
    | '-' INTEGER
    ;
%%

Answer 1

对于这种特定情况，您可以将否定表达式的规则更改为

expr: '-' '(' expr ')'

仅识别带括号的表达式上的否定。然而，这不会识别双重否定（例如 - - x），更重要的是，它不会扩展，因为如果您尝试添加其他一元运算符，它就会中断。

现在，您可以简单地将 num 规则放在 expr 规则之前，并允许默认的减少/减少冲突解决方案来处理它（将使用文件中出现的第一个规则）如果两者都可能），但这有点丑陋，因为每次运行 bison 时都会收到这些冲突警告，并且当您不知道到底发生了什么时忽略它们是一个坏主意。

解决这种歧义的一般方法是分解语法，将有问题的规则分成两个规则，并在每个上下文中使用适当的版本，这样就不会发生冲突。在这种情况下，您可以将 expr 拆分为 num_expr（对于以 num 开头的表达式）和 non_num_expr（对于其他表达式）表达式：

expr: num_expr | non_num_expr ;

num_expr: num_expr '+' expr
        | num_expr '-' expr
        | num
        ;

non_num_expr: non_num_expr '+' expr
            | non_num_expr '-' expr
            | '-' non_num_expr
            | '(' expr ')'
            ;

基本上，以 RHS 上的 expr 开头的 expr 的每条规则都需要重复，并且 expr 的其他用途可能需要复制更改为变体之一以便避免冲突。

不幸的是，在这种情况下，它不能干净地工作，因为您使用优先级来解决表达式语法固有的歧义，而因子规则会妨碍这一点——额外的一步规则会导致问题。因此，您需要将这些规则排除在外（在 RHS 上使用 expr 复制每条规则 - 一个使用 num_expr 版本，另一个使用 non_num_version< /code> 或者您需要使用优先级/关联性的额外规则重构语法。

expr: expr '+' term
    | expr '-' term
    | term
;

term: non_num_term | num_term ;

non_num_term: '-' non_num_term
            | '(' expr ')'
;

num_term: num ;

请注意，在这种情况下，num/non_num 分解是在 term 而不是 expr 上完成的

Answer 2

您不清楚为什么 num 需要表示负数。我无法判断您是否在语法中的其他地方使用了 num 。您也没有说明为什么您希望 num 和 expr 不同。

通常，负数是在词法分析器级别处理的。在您的情况下，规则类似于 -?[0-9]+。这根本就不再需要 num 了，结果如下：

expr: expr '+' expr
    | expr '-' expr
    | '-' expr
    | '(' expr ')'
    | INTEGER
    ;

编辑： Chris Dodd 有道理。因此，您需要将否定完全移至解析器中。您仍然摆脱 num，只是不要在 INTEGER 词法分析器模式中测试负数（即模式类似于 [0-9]+，这就是你现在正在做的事情，对吧？）。我上面给出的 expr 规则不会改变。

• 负数 (-5) 解析为：'-' INTEGER，变为 '-' expr（选择 5），然后 expr（选择 3）。
• 两个整数之间的差异 (3-2) 解析为 INTEGER '-' INTEGER，即变为 expr - expr（选择 5 两次），然后expr（选择2）。
• 整数和负整数 (5--1) 之间的差异将解析为 INTEGER '-' '-' INTEGER，即变为 expr '-' ' -' expr（选择 5 两次），然后 expr '-' expr（选择 3），然后 expr（选择 2）。

等等。根本问题是你在两个不同的地方进行否定，并且没有办法不产生歧义。