bison - バイソンシフト/競合の削減

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がそれを使用していたものに遭遇したときはいつでも、キーワードを減らすかどうかがわかりませんでした。空のルール。現在、シフト/リデュースは3つ、リデュース/リデュースは2つしかありません。

したがって、元の質問に対する私の答えは「はい」だったと思います。330のシフト/削減の競合があることは本当に悪い兆候です。

score 0 · Accepted Answer

あなたの文法ファイルを見ないと、これが問題であるかどうかはわかりません。これだけ多くのシフト/削減の競合が発生している場合は、ほぼ確実に、記述されている文法があいまいであることを意味します。ただし、少なくともCのような言語を作成している場合、ここで行われていることは、算術式の優先順位を指定していないことである可能性が非常に高くなります。すべてのオペレーターに優先順位を割り当てましたか？

ところで、バイソンにパーサーの状態と遷移の人間が読めるバージョンを含むy.outputファイルを作成させていますか？そうでない場合は、そうすることを強くお勧めします。その追加情報なしでシフトをデバッグしたり、競合を減らしたりすることは事実上不可能だからです。

この種のエラーを修正することはおそらく価値があります。これは、この多くの競合により、単一の問題が複数回複製されていると想定しているためです。または、GLRパーサー（bisonでもサポートされています）などのより一般的なパーサーに切り替えることもできますが、この多くの競合があるため、問題はあいまいさであり、より強力なパーサーでは解決できないと思います。

bison - バイソンシフト/競合の削減

1 に答える 1

Related

Reference