c - 警告 : 2 reduce/reduce conflicts [-Wconflicts-rr] in yacc grammar

Question

我有以下yacc语法:

%{
#include  <stdio.h>
extern FILE* yyin;
extern char* yytext;

%}

%token VAR ID_NAME TYPE_STRING TYPE_BOOL TYPE_NUMBER
%token CONST VALUE_STRING VALUE_BOOL VALUE_NUMBER

%%

program
    : declarations
    ;

declarations
    : declaration
    | declarations declaration
    ;

declaration
    : var_declaration
    | const_declaration
    ;

value
    : VALUE_BOOL
    | VALUE_STRING
    | VALUE_NUMBER
    ;

assignment
    : ID_NAME '=' value
    ;

assignments
    : assignment
    | assignments ',' assignment
    ;

id_list
    : ID_NAME
    | id_list ',' ID_NAME
    ;

declaration_expression
    : assignments
    | id_list
    | assignments ',' declaration_expression
    | id_list ',' declaration_expression
    ;

var_declaration
    : VAR ':' type declaration_expression ';' { printf("%s var\n", $1);  } 
    ;

const_declaration: CONST ':' type assignments ';' {printf("const\n");}
    ;

type: TYPE_NUMBER 
    | TYPE_STRING
    | TYPE_BOOL
    ;

%%
void yyerror (char const *s) {
    fprintf (stderr, "%s\n", s);
}

int main(int argc, char** argv[])
{

    yyparse();
    return 0;
}

它应该描述一种允许变量和常量声明形式的小语言:var:<type> <variables_names or variables_initializations>和const:<type> <constants_initialization> .

我想添加对以下语法的支持:

var:<type> var1, var2=<value>, var3;

类似这样的:var:<type> (<variables_names>|<variable_initializations>)+ .

为了实现这一点，我在语法中添加了以下修改:

assignments
    : assignment
    | assignments ',' assignment
    ;

id_list
    : ID_NAME
    | id_list ',' ID_NAME
    ;

declaration_expression
    : assignments
    | id_list
    | assignments ',' declaration_expression
    | id_list ',' declaration_expression
    ;

我认为这将启用 (<variables_names>|<variable_initializations>)+部分。但我得到了 reduce/reduce冲突，由于这些行:

    | assignments ',' declaration_expression
    | id_list ',' declaration_expression

我做错了什么？

Answer 1

如果我理解正确的话，您希望在 var 声明中允许混合使用裸变量名称和变量初始化，并且仅在 const 声明中进行初始化。这非常简单:

initialization : ID '=' value
init_list      : initialization | init_list ',' initialization
init_or_id     : initialization | ID
init_or_id_list: init_or_id
               | init_or_id_list ',' init_or_id

const_declaration: CONST ':' type init_list
var_declaration  : VAR   ':' type init_or_id_list

您做错的地方是通过使用列表而不是项目扩展混合列表来创建混合列表。这是不明确的，因此会导致减少/减少冲突。

上面的方法有效(就像你原来的那样)，因为 init_list 和 init_or_id_list 永远不会出现(作为非终结符)在推导中的同一点。其中一个明确地遵循 const 关键字，另一个明确地遵循 var 关键字。这是幸运的，因为纯分配列表将满足两个产生式，如果它们共享上下文，这将产生归约/归约冲突。这个问题也是可以解决的，并且由于它偶尔会出现，因此我将添加解决方案，尽管我强调它与这个特定问题不相关。 (不过，这可能与后来遇到类似问题的读者相关。)

为了使两种可能的列表语法明确，有必要确保潜在的纯赋值列表始终是来自混合列表的不同产生式的派生。所以我们可以这样写:

init_list: initialization | init_list initialization
init_or_id_list: ID
               | init_list ',' ID
               | init_or_id_list ',' init_or_id

现在，init_or_id_list 必须包含至少一个 ID 项，因此它不能与 init_list 混淆。但现在我们使用最终结果，我们需要记住接受混合列表的上下文需要允许两种列表可能性:

pure_list: init_list
mixed_list: init_list | init_or_id_list