Как найти сдвиг / уменьшить конфликт в этом файле YACC?

Question

Когда я пытаюсь использовать yacc для следующего файла, я получаю конфликты ошибок: 1 смещение / уменьшение Как я могу найти и исправить конфликт?

/* C-Minus BNF Grammar */

%token ELSE
%token IF
%token INT
%token RETURN
%token VOID
%token WHILE

%token ID
%token NUM

%token LTE
%token GTE
%token EQUAL
%token NOTEQUAL
%%

program : declaration_list ;

declaration_list : declaration_list declaration | declaration ;

declaration : var_declaration | fun_declaration ;

var_declaration : type_specifier ID ';'
                | type_specifier ID '[' NUM ']' ';' ;

type_specifier : INT | VOID ;

fun_declaration : type_specifier ID '(' params ')' compound_stmt ;

params : param_list | VOID ;

param_list : param_list ',' param
           | param ;

param : type_specifier ID | type_specifier ID '[' ']' ;

compound_stmt : '{' local_declarations statement_list '}' ;

local_declarations : local_declarations var_declaration
                   | /* empty */ ;

statement_list : statement_list statement
               | /* empty */ ;

statement : expression_stmt
          | compound_stmt
          | selection_stmt
          | iteration_stmt
          | return_stmt ;

expression_stmt : expression ';'
                | ';' ;

selection_stmt : IF '(' expression ')' statement
               | IF '(' expression ')' statement ELSE statement ;

iteration_stmt : WHILE '(' expression ')' statement ;

return_stmt : RETURN ';' | RETURN expression ';' ;

expression : var '=' expression | simple_expression ;

var : ID | ID '[' expression ']' ;

simple_expression : additive_expression relop additive_expression
                  | additive_expression ;

relop : LTE | '<' | '>' | GTE | EQUAL | NOTEQUAL ;

additive_expression : additive_expression addop term | term ;

addop : '+' | '-' ;

term : term mulop factor | factor ;

mulop : '*' | '/' ;

factor : '(' expression ')' | var | call | NUM ;

call : ID '(' args ')' ;

args : arg_list | /* empty */ ;

arg_list : arg_list ',' expression | expression ;

Answer 1

Как указывал mientefuego, у вашей грамматики есть классическая проблема "болтаться в другом". Вы можете решить эту проблему, назначив приоритет правилам, вызывающим конфликт.

Правило, вызывающее конфликт:

selection_stmt : IF '(' expression ')' statement
               | IF '(' expression ')' statement ELSE statement ;

Сначала начните с того, что ELSE и LOWER_THAN_ELSE (псевдо-токен) неассоциативны:

%nonassoc LOWER_THAN_ELSE
%nonassoc ELSE

Это дает ELSE больший приоритет над LOWER_THAN_ELSE просто потому, что LOWER_THAN_ELSE объявляется первым.

Затем в конфликтующем правиле вы должны назначить приоритет действиям сдвига или уменьшения:

selection_stmt : IF '(' expression ')' statement    %prec LOWER_THAN_ELSE ;
               | IF '(' expression ')' statement ELSE statement ;

Здесь более высокий приоритет отдается смещению. Я включил вышеупомянутые исправления и перечислил полную грамматику ниже:

/* C-Minus BNF Grammar */

%token ELSE
%token IF
%token INT
%token RETURN
%token VOID
%token WHILE

%token ID
%token NUM

%token LTE
%token GTE
%token EQUAL
%token NOTEQUAL

%nonassoc LOWER_THAN_ELSE
%nonassoc ELSE
%%

program : declaration_list ;

declaration_list : declaration_list declaration | declaration ;

declaration : var_declaration | fun_declaration ;

var_declaration : type_specifier ID ';'
                | type_specifier ID '[' NUM ']' ';' ;

type_specifier : INT | VOID ;

fun_declaration : type_specifier ID '(' params ')' compound_stmt ;

params : param_list | VOID ;

param_list : param_list ',' param
           | param ;

param : type_specifier ID | type_specifier ID '[' ']' ;

compound_stmt : '{' local_declarations statement_list '}' ;

local_declarations : local_declarations var_declaration
                   | /* empty */ ;

statement_list : statement_list statement
               | /* empty */ ;

statement : expression_stmt
          | compound_stmt
          | selection_stmt
          | iteration_stmt
          | return_stmt ;

expression_stmt : expression ';'
                | ';' ;

selection_stmt : IF '(' expression ')' statement    %prec LOWER_THAN_ELSE ;
               | IF '(' expression ')' statement ELSE statement ;

iteration_stmt : WHILE '(' expression ')' statement ;

return_stmt : RETURN ';' | RETURN expression ';' ;

expression : var '=' expression | simple_expression ;

var : ID | ID '[' expression ']' ;

simple_expression : additive_expression relop additive_expression
                  | additive_expression ;

relop : LTE | '<' | '>' | GTE | EQUAL | NOTEQUAL ;

additive_expression : additive_expression addop term | term ;

addop : '+' | '-' ;

term : term mulop factor | factor ;

mulop : '*' | '/' ;

factor : '(' expression ')' | var | call | NUM ;

call : ID '(' args ')' ;

args : arg_list | /* empty */ ;

arg_list : arg_list ',' expression | expression ;

Answer 2

возможно вам стоит попробовать yacc -v <filename>, он генерирует вывод деталей.

Я проверил здесь, и ваше грамматическое описание не сработало в классической задаче "висящий еще".

Взгляните на эту статью в Википедии .

Answer 3

Гм, правильный ответ на эту проблему обычно: ничего не делать .

Ожидаются конфликты Shift / Reduce с неоднозначными грамматиками. Это не ошибки , это конфликты .

Конфликт будет разрешен путем предпочтения сдвига, а не уменьшения, что, как правило, решает проблему канонического повисшего остального.

И даже у бизона есть оператор% Ожидайте n , чтобы вы не получили предупреждение о конфликте S / R, когда есть точно n конфликтов.

Answer 4

Эта статья предлагает альтернативное решение, опубликованное ardsrk.

Answer 5

Сначала получите конечный автомат от yacc . Состояние, которое может быть смещено или уменьшено, представляет конфликт сдвига / уменьшения. Найдите его, а затем разрешите конфликт, переписав грамматику.