警告：yacc 语法中有 2 reduce/reduce 个冲突 [-Wconflicts-rr]

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", );  } 
    ;

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 声明中只允许初始化。相当 straight-forward:

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

您做错的是通过使用 lists 而不是 items 扩展混合列表来创建混合列表。这是不明确的，因此会导致 reduce/reduce 冲突。

上面的工作（和你原来的一样）是因为 init_list 和 init_or_id_list 永远不会出现（如 non-terminals）在推导的同一点。其中一个明确遵循 const 关键字，另一个明确遵循 var 关键字。这是幸运的，因为纯赋值列表可以满足两个产生式，如果它们共享一个上下文，就会产生 reduce/reduce 冲突。这个问题也是可以解决的，因为它偶尔会出现，所以我会添加解决方案，尽管我强调它与这个特定问题不相关。（不过，这可能与后来 reader 有类似问题的人有关。）

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

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

警告：yacc 语法中有 2 reduce/reduce 个冲突 [-Wconflicts-rr]

warning: 2 reduce/reduce conflicts [-Wconflicts-rr] in yacc grammar

c

parsing

yacc

bison