0

我对此很陌生，我试图了解这里发生了什么，我得到两个班次减少冲突。我有语法（如果我遗漏了一些东西，我可以添加所需的规则）：

%start translation_unit

%token EOF      0               "end of file"

%token                      LBRA        "["
%token                      RBRA        "]"
%token                      LPAR        "("
%token                      RPAR        ")"
%token                      DOT         "."
%token                      ARROW       "->"
%token                      INCDEC      "++ or --"
%token                      COMMA       ","
%token                      AMP         "&"
%token                      STAR        "*"
%token                      ADDOP       "+ or -"
%token                      EMPH        "!"
%token                      DIVOP       "/ or %"
%token                      CMPO        "<, >, <=, or >="
%token                      CMPE        "== or !="
%token                      DAMP        "&&"
%token                      DVERT       "||"
%token                      ASGN        "="
%token                      CASS        "*=, /=, %=, +=, or -="
%token                      SEMIC       ";"
%token                      LCUR        "{"
%token                      RCUR        "}"
%token                      COLON       ":"

%token                      TYPEDEF     "typedef"
%token                      VOID        "void"
%token                      ETYPE       "_Bool, char, or int"
%token                      STRUCT      "struct"
%token                      ENUM        "enum"
%token                      CONST       "const"
%token                      IF          "if"
%token                      ELSE        "else"
%token                      DO          "do"
%token                      WHILE       "while"
%token                      FOR         "for"
%token                      GOTO        "goto"
%token                      CONTINUE    "continue"
%token                      BREAK       "break"
%token                      RETURN      "return"
%token                      SIZEOF      "sizeof"

%token<string>              IDF         "identifier"
%token<string>              TYPEIDF     "type identifier"
%token<int>                 INTLIT      "integer literal"
%token<string>              STRLIT      "string literal"

/////////////////////////////////

%%

/////////////////////////////////

primary_expression:
    IDF
    | INTLIT
    | STRLIT
    | LPAR expression RPAR
    ;

postfix_expression:
    primary_expression
    | postfix_expression LBRA expression RBRA
    | postfix_expression LPAR argument_expression_list_opt RPAR
    | postfix_expression DOT IDF
    | postfix_expression ARROW IDF
    | postfix_expression INCDEC
    ;

argument_expression_list_opt:
    %empty
    | argument_expression_list
    ;

argument_expression_list:
    assignment_expression
    | argument_expression_list COMMA assignment_expression
    ;

unary_expression:
    postfix_expression
    | INCDEC unary_expression
    | unary_operator cast_expression
    | SIZEOF LPAR type_name RPAR
    ;

unary_operator:
    AMP
    | STAR
    | ADDOP
    | EMPH
    ;

cast_expression:
    unary_expression
    ;

multiplicative_expression:
    cast_expression
    | multiplicative_expression STAR cast_expression
    | multiplicative_expression DIVOP cast_expression
    ;

additive_expression:
    multiplicative_expression
    | additive_expression ADDOP multiplicative_expression
    ;

relational_expression:
    additive_expression
    | relational_expression CMPO additive_expression
    ;

equality_expression:
    relational_expression
    | equality_expression CMPE relational_expression
    ;

logical_AND_expression:
    equality_expression
    | logical_AND_expression DAMP equality_expression
    ;

logical_OR_expression:
    logical_AND_expression
    | logical_OR_expression DVERT logical_AND_expression
    ;

assignment_expression:
    logical_OR_expression
    | unary_expression assignment_operator assignment_expression
    ;

assignment_operator:
    ASGN 
    | CASS
    ;

expression:
    assignment_expression
    ;

constant_expression:
    logical_OR_expression
    ;

declaration:
    no_leading_attribute_declaration
    ;

no_leading_attribute_declaration:
    declaration_specifiers init_declarator_list_opt SEMIC
    ;

init_declarator_list_opt:
    %empty
    | init_declarator_list
    ;

declaration_specifiers:
    declaration_specifier
    | declaration_specifier declaration_specifiers
    ;

declaration_specifier:
    storage_class_specifier
    | type_specifier_qualifier
    ;

init_declarator_list:
    init_declarator
    | init_declarator_list COMMA init_declarator
    ;

init_declarator:
    declarator
    ;

storage_class_specifier:
    TYPEDEF
    ;

type_specifier:
    VOID
    | ETYPE
    | struct_or_union_specifier
    | enum_specifier
    | typedef_name
    ;

struct_or_union_specifier:
    struct_or_union IDF LCUR member_declaration_list RCUR
    | struct_or_union IDF
    ;

struct_or_union:
    STRUCT
    ;

member_declaration_list:
    member_declaration
    | member_declaration_list member_declaration
    ;

member_declaration:
    specifier_qualifier_list member_declarator_list_opt SEMIC
    ;

member_declarator_list_opt:
    %empty
    | member_declarator_list
    ;

specifier_qualifier_list:
    type_specifier_qualifier
    | type_specifier_qualifier specifier_qualifier_list
    ;

type_specifier_qualifier:
    type_specifier
    | type_qualifier
    ;

member_declarator_list:
    member_declarator
    | member_declarator_list COMMA member_declarator
    ;

member_declarator:
    declarator
    ;

enum_specifier:
    ENUM IDF LCUR enumerator_list RCUR
    | ENUM IDF LCUR enumerator_list COMMA RCUR
    | ENUM IDF
    ;

enumerator_list:
    enumerator
    | enumerator_list COMMA enumerator
    ;

enumerator:
    ENUM
    | ENUM ASGN constant_expression
    ;

type_qualifier:
    CONST
    ;

pointer:
    STAR type_qualifier_list_opt
    | STAR type_qualifier_list_opt pointer
    ;

pointer_opt:
    %empty
    | pointer
    ;

declarator:
    pointer_opt direct_declarator
    ;

direct_declarator:
    IDF
    | LPAR declarator RPAR
    | array_declarator
    | function_declarator
    ;

abstract_declarator:
    pointer
    | pointer_opt direct_abstract_declarator
    ;

direct_abstract_declarator:
    LPAR abstract_declarator RPAR
    | array_abstract_declarator
    | function_abstract_declarator
    ;

direct_abstract_declarator_opt:
    %empty
    | direct_abstract_declarator
    ;

array_abstract_declarator:
    direct_abstract_declarator_opt LBRA assignment_expression RBRA
    ;

function_abstract_declarator:
    direct_abstract_declarator_opt LPAR parameter_type_list RPAR
    ;

array_declarator:
    direct_declarator LBRA assignment_expression RBRA
    ;

function_declarator:
    direct_declarator LPAR parameter_type_list RPAR
    ;

type_qualifier_list_opt:
    %empty
    | type_qualifier_list
    ;

type_qualifier_list:
    type_qualifier
    | type_qualifier_list type_qualifier
    ;

parameter_type_list:
    parameter_list
    ;

parameter_list:
    parameter_declaration
    | parameter_list COMMA parameter_declaration
    ;

parameter_declaration:
    declaration_specifiers declarator
    | declaration_specifiers abstract_declarator_opt
    ;
abstract_declarator_opt:
    %empty
    | abstract_declarator
    ;

type_name:
    specifier_qualifier_list abstract_declarator_opt
    ;

typedef_name:
    TYPEIDF
    ;

statement:
    matched
    | unmatched
    | other
    ;

other:
    expression_statement
    | compound_statement
    | jump_statement
    ;

matched:
    selection_statement_c
    | iteration_statement_c
    ;

unmatched:
    selection_statement_o
    | iteration_statement_o
    ;

compound_statement:
    LCUR block_item_list_opt RCUR
    ;

block_item_list_opt:
    %empty
    | block_item_list
    ;

block_item_list:
    block_item
    | block_item_list block_item
    ;

block_item:
    declaration
    | statement
    ;

expression_statement:
    expression_opt SEMIC
    ;

expression_opt:
    %empty
    | expression
    ;

selection_statement_o:
    IF LPAR expression RPAR statement
    | IF LPAR expression RPAR matched ELSE unmatched
    ;

selection_statement_c:
    IF LPAR expression RPAR matched ELSE matched
    ;

iteration_statement_o:
    WHILE LPAR expression RPAR unmatched
    | FOR LPAR expression_opt SEMIC expression_opt SEMIC expression_opt RPAR unmatched
    ;

iteration_statement_c:
    WHILE LPAR expression RPAR matched
    | DO statement WHILE LPAR expression RPAR SEMIC
    | FOR LPAR expression_opt SEMIC expression_opt SEMIC expression_opt RPAR matched
    ;

jump_statement:
    RETURN expression_opt SEMIC
    ;

translation_unit:
    external_declaration
    | translation_unit external_declaration
    ;

external_declaration:
    function_definition
    | declaration
    ;

function_definition:
    declaration_specifiers declarator compound_statement
    ;

/////////////////////////////////

%%

我得到了这种转变/减少冲突：

State 156

   85 declarator: pointer_opt . direct_declarator
   91 abstract_declarator: pointer_opt . direct_abstract_declarator

    "("           shift, and go to state 187
    "identifier"  shift, and go to state 44

    "("       [reduce using rule 111 (direct_abstract_declarator_opt)]
    ^^conflict with previous "(" ^^
    $default  reduce using rule 111 (direct_abstract_declarator_opt)

...

State 197

   91 abstract_declarator: pointer_opt . direct_abstract_declarator

    "("  shift, and go to state 213
    "("       [reduce using rule 111 (direct_abstract_declarator_opt)]
    ^^conflict^^

    $default  reduce using rule 111 (direct_abstract_declarator_opt)

所以我将其理解为：当我得到“（”时，我可以做两件事。首先，从 direct_declarator 我得到 LPAR 声明符 RPAR，其中 LPAR 是“（”
......或......
我可以减少 direct_abstract_declarator->array_abstract_declarator-> direct_abstract_declarator_opt->direct_abstract_declarator->LPAR abstract_declarator RPAR 其中 LPAR 又是“（”。所以我无法决定走哪条路正确？
我应该如何解决这个冲突？还是我完全看错了？

4

1 回答 1

1

创建 shift-reduce 冲突的最简单方法之一是引入一个表示可选实例的新非终结符：

something_opt
    : something
    | %empty

有时这会奏效，但更常见的情况是，在某些上下文中something可能是可选的，也可能不是可选的。换句话说，您有两种不同的产品，它们使用something：

a: something something_else "END_A"
b: something_opt something_else "END_B"

这不是模棱两可的，但它不能用一个标记前瞻来解析，因为在something被识别之后，解析器必须决定是否将其减少为something_opt，如果以下文本结果是 ，这将是必要的b。something_opt在语义上基本上没有意义；有一个something或没有一个something。如果没有那个细节，解析器就没有问题；它可以继续解析something_else，然后根据是否遇到END_Aor END_B，它可以决定是减少 ana还是 a b。

解决方法很简单：不用定义something_opt，而是简单地复制产生式，这样一个产生式有something，另一个没有。

在您的情况下，有问题的可选非终端是direct_abstract_declarator_opt：

direct_abstract_declarator_opt:
    %empty
    | direct_abstract_declarator
 
array_abstract_declarator:
    direct_abstract_declarator_opt LBRA assignment_expression RBRA

function_abstract_declarator:
    direct_abstract_declarator_opt LPAR parameter_type_list RPAR

这些是唯一使用它的地方，所以我们可以通过复制其他两个非终端的产品来摆脱它：

array_abstract_declarator:
    direct_abstract_declarator LBRA assignment_expression RBRA
    | LBRA assignment_expression RBRA

function_abstract_declarator:
    direct_abstract_declarator LPAR parameter_type_list RPAR
    | LPAR parameter_type_list RPAR

如果可能的话，你应该使用这个模型来编写带有可选非终结符的语法。它确实需要复制语义动作，但希望语义动作只是对 AST 节点构建器的简单调用。它会为你省去很多不必要的悲伤。

于 2021-11-12T19:03:43.947 回答