Bison-shift/reduce conflicts

Question

Bisonコードでは、いくつかのシフト/リダクションの競合が予想され、通常のC文法ではif/elseが生成されることがわかります。しかし、私は他のシフト/リダクションの競合を生成する文法を持っています。これは私の文法に深刻な問題の兆候ですか？私は、各競合を捜す時間を費やして、それを解決するか、正当性を検証しようとするべきでしょうか？私は通常の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はそれを使用していた何かに遭遇したときに、空のルール。今私は3つのshift/reduce ...と2つのreduce/reduce ... conflictsしか持っていません。

私は元の質問への私の答えははいだったと思いますが、それは330シフト/減少の競合を持つことは本当に悪い兆候です。

Answer 1

文法ファイルを見ても、問題があるかどうかはわかりません。この多くのシフト/リダクションの競合が発生している場合は、書かれた文法があいまいであることをほぼ確実に意味します。しかし、少なくともC言語のような言語を書くのであれば、ここで何が起こっているのかは、あなたが算術式の優先順位を指定していないということでしょう。すべての事業者に優先順位を付けましたか？

ところで、バイソンに人間が読める形式のパーサーの状態と遷移を含むy.outputファイルを作成させていますか？もしそうでないならば、私はそうすることを強くお勧めします。その余分な情報なしでshift/reduce競合をデバッグすることは事実上不可能です。

この種のエラーを修正する価値はありますが、これは多くのコンフリクトがあるため、複数の問題が1回複製されていると想定しているためです。あるいは、GLRパーサー（bisonもサポート）のようなより一般的なパーサーに切り替えることができますが、このような多くのコンフリクトがあると、よりパワフルなパーサーが解決できない問題があいまいであると想定しています。