Зубр-сдвиг / уменьшение конфликтов

Question

Я знаю, что в коде Bison можно ожидать некоторых конфликтов сдвига / уменьшения, и обычная грамматика C выдает ее для if/else, Тем не менее, у меня есть грамматика, которая производит 330 других конфликтов сдвига / уменьшения. Является ли это признаком серьезной проблемы с моей грамматикой? Должен ли я тратить время на поиск каждого конфликта и пытаться разрешить или проверить его правильность? Я использую обычный LALR-парсер.

Редактировать:

Вот моя грамматика, я лишил всех действий и прочего.

%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

%skeleton "lalr1.cc"
%defines
%parse-param { Wide::LexedFile& l }
%parse-param { Wide::ParsedFile&  p }
%lex-param { Wide::LexedFile& l }
%lex-param { Wide::ParsedFile& p }
%define namespace Wide

%token CASE DEFAULT IF ELSE SWITCH WHILE DO FOR CONTINUE BREAK RETURN
%code requires {
#include <string>
#include <vector>
#define YYDEBUG 1
#include "ParsedFile.h"
}
%code provides {
#include "yylex.h"
}
%start program
%locations

%%

program
    : namespace_scope_definitions;

var 
    : ;//VAR;

type_expression
    : expression
    { $$ = $1; }

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
    : namespace_definition 
    | function_definition 
    | variable_definition 
    | accessibility_definition 
    | using_definition 
    | type_definition ;

namespace_scope_definitions
    : namespace_scope_definition
    | namespace_scope_definitions namespace_scope_definition ;

type_scope_definition
    : static_function_definition
    | static_variable_definition
    | destructor_definition
    | accessibility_definition
    | using_definition
    | constructor_definition 
    | type_definition;

type_scope_definitions
    : type_scope_definition
    | type_scope_definitions type_scope_definition ;

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

constructor_definition
    : THIS runtime_arguments statements_or_inits;

statement_or_init
    : ':' IDENTIFIER function_call_expression
    | compound_statement;

statements_or_inits
    : statement_or_init
    | statements_or_inits statement_or_init;

compiletime_arguments
    : runtime_arguments
    | ;

runtime_arguments
    : '(' ')'
    | '(' function_argument_list ')';

return_type_expression
    : PTR_OP type_expression 
    | ;

function_definition
    : name_or_qualified_name runtime_arguments compiletime_arguments return_type_expression 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_function_definition
    : STATIC function_definition
    | function_definition;

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

variable_definition
    : var IDENTIFIER variable_assignment expression ';'
    | var type_expression IDENTIFIER variable_assignment expression ';'
    | var type_expression IDENTIFIER ';'
    | var 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 '}';
    | '{' '}';

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

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

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
    | 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
    | var IDENTIFIER variable_assignment expression
    | var type_expression IDENTIFIER variable_assignment expression;

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
    | case_statements default_statement;

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;

statements
    : statement
    | statements statement;

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

Я сделал небольшой шаг вперед. Вы были правы - это был один и тот же конфликт снова и снова. Оказывается, я пытался удалить ключевое слово из грамматики, комментируя содержание правила (в частности, правило var), поэтому всякий раз, когда Bison сталкивался с чем-то, что использовало его, он не знал, уменьшать или нет пустое правило. Теперь у меня есть только три смещения / уменьшения... и два уменьшения / уменьшения... конфликта.

Таким образом, я думаю, что мой ответ на первоначальный вопрос был да, это действительно плохой признак иметь 330 сдвигов / сокращений конфликтов.

Answer 1

Без просмотра файла грамматики я не могу сказать, является ли это проблемой. Если вы получаете столько конфликтов сдвига / уменьшения, это почти наверняка означает, что написанная грамматика неоднозначна. Тем не менее, очень вероятно, что здесь происходит, по крайней мере, если вы пишете на C-подобном языке, что вы не указали приоритеты для арифметических выражений. Вы назначили приоритеты всем своим операторам?

Кстати, у вас есть зубр создать файл y.output, содержащий читабельную версию состояний парсера и переходов? Если нет, я бы настоятельно рекомендовал сделать это, так как практически невозможно отладить сдвиг / уменьшение конфликтов без этой дополнительной информации.

Вероятно, стоит исправлять ошибки такого рода, так как при таком количестве конфликтов я предполагаю, что одна и та же проблема повторяется несколько раз. В качестве альтернативы, вы могли бы переключиться на более общий анализатор, такой как анализатор GLR (также поддерживаемый bison), но я предполагаю, что из-за большого количества конфликтов проблема заключается в неоднозначности, которую более мощные анализаторы не могут разрешить.