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

Question

以下语法(其中INTEGER是数字序列)引起减少/减少冲突,因为例如-4可以通过expr - > -expr或expr - > num - > -INTEGER来减少.在我的语法中,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_expra 开头的 for 表达式num和non_num_exprfor 其他表达式：

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

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

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

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