Bison 语法中的歧义

Question

我的 Bison 语法有问题。我有一对很好的转变/减少，还有六个减少/减少。问题是我不明白减少/减少冲突是如何发生的，因为解析器应该知道先从标记中选择哪个。

%token STRING_LITERAL
%token INTEGER
%token FLOAT
%token CHARACTER
%token PTR_OP INC_OP DEC_OP LEFT_OP RIGHT_OP LE_OP GE_OP EQ_OP NE_OP
%token AND_OP OR_OP MUL_ASSIGN DIV_ASSIGN MOD_ASSIGN ADD_ASSIGN
%token SUB_ASSIGN LEFT_ASSIGN RIGHT_ASSIGN AND_ASSIGN
%token XOR_ASSIGN OR_ASSIGN STATIC CATCH DOUBLE_COLON ELLIPSIS FUNCTION VAR
%token SIZEOF
%token GOTO
%token AUTO  
%token THIS VAR_ASSIGN
%token NAMESPACE
%token TRY
%token TYPE
%token DECLTYPE
%token PUBLIC
%token PRIVATE
%token PROTECTED
%token USING
%token THROW
%token FRIEND
%token COMPILETIME
%token RUNTIME
%token VIRTUAL
%token ABSTRACT 
%token CASE DEFAULT IF ELSE SWITCH WHILE DO FOR CONTINUE BREAK RETURN
%%

global_scope_definition
    : namespace_definition
    | function_definition
    | variable_definition
    | using_definition
    | type_definition;

global_scope_definitions
    : global_scope_definition
    | global_scope_definitions global_scope_definition

program
    : global_scope_definitions;

type_expression
    : expression

variable_assignment
    : VAR_ASSIGN;

name_or_qualified_name
    : IDENTIFIER
    | name_or_qualified_name '.' IDENTIFIER;

namespace_definition
    : NAMESPACE name_or_qualified_name '{' namespace_scope_definitions '}';

accessibility_definition
    : PUBLIC ':'
    | PRIVATE ':'
    | PROTECTED ':'
    | FRIEND ':';

using_definition
    : USING IDENTIFIER '=' name_or_qualified_name ';'
    | USING name_or_qualified_name ';';

type_definition
    : TYPE IDENTIFIER type_literal;

namespace_scope_definition
    : accessibility_definition
    | global_scope_definition;

namespace_scope_definitions
    : namespace_scope_definition
    | namespace_scope_definitions namespace_scope_definition;

accessibility_modifier
    : PUBLIC
    | PROTECTED
    | PRIVATE
    | FRIEND;

accessibility_block
    : phase_block
    | accessibility_modifier phase_block;

phase_modifier
    : COMPILETIME
    | RUNTIME;

phase_block
    : definition_block
    | phase_modifier definition_block;

definition_block
    : default_definition_block
    | STATIC static_definition_block
    | VIRTUAL virtual_definition_block
    | ABSTRACT abstract_definition_block;

static_definition_block
    : '{' static_definitions '}';

static_definitions
    : static_definition
    | static_definitions static_definition;

static_definition
    : variable_definition
    | function_definition;


abstract_definition_block
    : '{' abstract_definitions '}';

abstract_definitions
    : abstract_definition
    | abstract_definitions abstract_definition;

abstract_definition
    : function_definition; 

virtual_definition_block
    : '{' virtual_definitions '}';

virtual_definitions
    : virtual_definition
    | virtual_definitions virtual_definition;

virtual_definition
    : function_definition;


default_definition_block
    : '{' default_definitions '}';

default_definitions
    : default_definition
    | default_definitions default_definition;

default_definition
    : variable_definition
    | function_definition
    | constructor_definition
    | destructor_definition
    | type_definition;

type_scope_definition
    : using_definition
    | default_definition
    | accessibility_block;

type_scope_definitions
    : type_scope_definition
    | type_scope_definitions type_scope_definition;

destructor_definition
    : '~' TYPE '(' ')' compound_statement;

constructor_definition
    : TYPE function_definition_arguments statements_and_inits;

statements_and_inits
    : inits compound_statement
    | compound_statement;

init
    : ':' IDENTIFIER function_call_expression;

inits
    : init
    | inits init;

function_definition_arguments
    : '(' ')'
    | '(' function_argument_list ')';

function_definition
    : type_expression IDENTIFIER function_definition_arguments compound_statement
    | type_expression IDENTIFIER function_definition_arguments function_definition_arguments compound_statement;

function_argument_definition
    : IDENTIFIER
    | type_expression IDENTIFIER
    | IDENTIFIER variable_assignment expression
    | type_expression IDENTIFIER variable_assignment expression
    | IDENTIFIER variable_assignment '{' expressions '}'
    | type_expression IDENTIFIER variable_assignment '{' expressions '}';

function_argument_list
    : function_argument_definition
    | function_argument_list ',' function_argument_definition;

static_variable_definition
    : STATIC variable_definition
    | FRIEND variable_definition
    | STATIC FRIEND variable_definition
    | variable_definition;

variable_definition
    : IDENTIFIER variable_assignment expression ';'
    | type_expression IDENTIFIER variable_assignment expression ';'
    | type_expression IDENTIFIER ';'
    | type_expression IDENTIFIER function_call_expression ';';

base_class_list
    : ':' type_expression
    | base_class_list ',' type_expression;

type_literal
    : base_class_list '{' type_scope_definitions '}'
    | '{' type_scope_definitions '}'
    | base_class_list '{' '}'
    | '{' '}';

literal_expression
    : INTEGER
    | FLOAT
    | CHARACTER
    | STRING_LITERAL
    | AUTO
    | THIS
    | TYPE type_literal;

primary_expression    
    : literal_expression
    | '(' expression ')'
    | IDENTIFIER;

expression
    : variadic_expression;

variadic_expression
    : assignment_expression
    | assignment_expression ELLIPSIS;

assignment_operator
    : '='
    | MUL_ASSIGN
    | DIV_ASSIGN
    | MOD_ASSIGN
    | ADD_ASSIGN
    | SUB_ASSIGN
    | LEFT_ASSIGN
    | RIGHT_ASSIGN
    | AND_ASSIGN
    | XOR_ASSIGN
    | OR_ASSIGN;

assignment_expression
    : logical_or_expression
    | unary_expression assignment_operator assignment_expression;

logical_or_expression
    : logical_and_expression
    | logical_or_expression OR_OP logical_and_expression;

logical_and_expression
    : inclusive_or_expression
    | logical_and_expression AND_OP inclusive_or_expression;

inclusive_or_expression
    : exclusive_or_expression
    | inclusive_or_expression '|' exclusive_or_expression;

exclusive_or_expression
    : and_expression
    | exclusive_or_expression '^' and_expression;

and_expression
    : equality_expression
    | and_expression '&' equality_expression;

equality_expression
    : relational_expression
    | equality_expression EQ_OP relational_expression
    | equality_expression NE_OP relational_expression;

comparison_operator
    : '<'
    | '>'
    | LE_OP 
    | GE_OP;

relational_expression
    : shift_expression
    | relational_expression comparison_operator shift_expression;

shift_operator
    : LEFT_OP
    | RIGHT_OP;

shift_expression
    : additive_expression
    | shift_expression shift_operator additive_expression;

additive_operator
    : '+'
    | '-';

additive_expression
    : multiplicative_expression
    | additive_expression additive_operator multiplicative_expression;

multiplicative_operator
    : '*'
    | '/'
    | '%';

multiplicative_expression
    : unary_expression
    | multiplicative_expression multiplicative_operator unary_expression;

lambda_expression
    : '[' capture_list ']' function_argument_list compound_statement
    | '[' capture_list ']' compound_statement;
    | '[' ']' function_argument_list compound_statement
    | '[' ']' compound_statement;


default_capture
    : '&' | '=' ;

capture_list
    : default_capture comma_capture_list
    | comma_capture_list;

comma_capture_list
    : variable_capture
    | comma_capture_list ',' variable_capture;

variable_capture
    : '&' IDENTIFIER
    | '=' IDENTIFIER
    | AND_OP IDENTIFIER;

unary_operator
    : '&'
    | '*'
    | '+'
    | '-'
    | '~'
    | '!'
    | INC_OP
    | DEC_OP;

unary_expression
    : unary_operator unary_expression
    | SIZEOF '(' expression ')'
    | DECLTYPE '(' expression ')'
    | lambda_expression
    | postfix_expression;

postfix_expression
    : primary_expression  { $$ = $1; }
    | postfix_expression '[' expression ']'
    | postfix_expression function_call_expression
    | postfix_expression '.' IDENTIFIER
    | postfix_expression PTR_OP IDENTIFIER
    | postfix_expression INC_OP
    | postfix_expression DEC_OP
    | postfix_expression FRIEND;

expressions
    : expression
    | expressions ',' expression;

function_argument
    : expression
    | IDENTIFIER variable_assignment '{' expressions '}'
    | IDENTIFIER variable_assignment expression;

function_arguments
    : function_argument
    | function_arguments ',' function_argument;

function_call_expression
    : '(' function_arguments ')'
    | '(' ')';

initializer_statement
    : expression
    | IDENTIFIER variable_assignment expression
    | type_expression IDENTIFIER variable_assignment expression;

destructor_statement
    : expression '~' TYPE '(' ')' ';';

return_statement
    : RETURN expression ';'
    | RETURN ';';

try_statement
    : TRY compound_statement catch_statements;

catch_statement
    : CATCH '(' type_expression IDENTIFIER ')' compound_statement;

catch_statements
    : catch_statement
    | catch_statements catch_statement
    | CATCH '(' ELLIPSIS ')' compound_statement
    | catch_statements CATCH '(' ELLIPSIS ')' compound_statement;

for_statement_initializer
    : initializer_statement ';'
    | ';';

for_statement_condition
    : expression ';'
    | ';';

for_statement_repeat
    : expression
    | ;

for_statement
    : FOR '(' for_statement_initializer for_statement_condition for_statement_repeat ')' statement;

while_statement
    : WHILE '(' initializer_statement ')' statement;

do_while_statement
    : DO statement WHILE '(' expression ')';

switch_statement
    : SWITCH '(' initializer_statement ')' '{' case_statements '}';

default_statement
    : DEFAULT ':' statements;

case_statement
    : CASE expression DOUBLE_COLON statements;

case_statements
    : case_statement 
    | case_statements case_statement { $1.push_back($2); $$ = std::move($1); }
    | case_statements default_statement { $1.push_back($2); $$ = std::move($1); };

if_statement
    : IF '(' initializer_statement ')' statement
    | IF '(' initializer_statement ')' statement ELSE statement;

continue_statement
    : CONTINUE ';';

break_statement
    : BREAK ';';

label_statement
    : IDENTIFIER ':';

goto_statement
    : GOTO IDENTIFIER ';';

throw_statement
    : THROW ';'
    | THROW expression ';';

runtime_statement
    : RUNTIME compound_statement;

compiletime_statement
    : COMPILETIME compound_statement;

statement
    : compound_statement
    | return_statement
    | try_statement
    | expression ';'
    | static_variable_definition
    | for_statement
    | while_statement
    | do_while_statement
    | switch_statement
    | if_statement
    | continue_statement
    | break_statement
    | goto_statement
    | label_statement
    | using_definition 
    | throw_statement
    | compiletime_statement
    | runtime_statement
    | destructor_statement ;

statements
    : statement
    | statements statement;

compound_statement
    : '{' '}'
    | '{' statements '}';

%%

这是我的语法。 Bison 对 function_argument_definition 和 primary_expression 之间以及 function_argument_definition 和 function_argument 之间假定的歧义提出了质疑。然而，我非常确定，当它遇到此类事情时，它应该已经知道该选择哪个。我该如何解决这些歧义？

Answer 1

考虑到这些规则

function_definition:
    type_expression IDENTIFIER function_definition_arguments compound_statement

variable_definition:
    type_expression IDENTIFIER function_call_expression ';'

可以以多种方式出现在同一上下文中，因此编译器无法知道它正在查看哪个，直到到达 variable_definition 中的 ; 或 function_definition 中 compound_statement 中的 {。因此，它无法判断它是处理 function_definition_arguments 还是 function_call_expression，从而导致您看到的reduce/reduce 冲突。

要自己发现此类问题，您需要使用 -v 选项运行 bison 以生成显示其构建的状态机的 .output 文件。然后，您查看存在冲突的状态并回溯，看看它是如何到达这些状态的。在您的示例中，状态 280 有（两个）reduce/reduce 冲突。达到此目的的一种方法是状态 177，它并行解析 function_definition_arguments 和 function_call_expression —— 解析器处于其中任何一个都合法的状态。状态 177 来自状态 77，状态 77 来自状态 26，它显示了我上面复制的两条规则。