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

18

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

/* 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 ;
    
задан neuromancer 15.11.2009 в 13:48
источник

5 ответов

19

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

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

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 ;
    
ответ дан ardsrk 15.11.2009 в 15:11
источник
  • Почему я должен сначала сделать ELSE и LOWER_THAN_ELSE (псевдо-токен) не ассоциативным? –  new_perl 02.08.2011 в 03:45
  • Oh. Я не обратил на это внимания. Это не кажется необходимым, поскольку ELSE и LOWER_THAN_ELSE не имеют одинакового приоритета. –  ardsrk 02.08.2011 в 17:38
  • % nonassoc необходимо. Использование только% токена не будет сообщать бизону о старшинстве. –  user764754 19.11.2011 в 21:38
  • И все это дает тот же результат, что и исходный yacc. Возможно, было бы полезно указать, что исходный конфликт ожидается и был правильно разрешен по умолчанию yacc, предпочитая сдвиг. –  DigitalRoss 11.01.2014 в 19:01
6

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

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

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

    
ответ дан user211430 15.11.2009 в 14:21
источник
  • +1 для ссылки на болтающуюся другую статью! –  Chethan Ravindranath 13.12.2011 в 13:47
4

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

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

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

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

    
ответ дан DigitalRoss 12.01.2013 в 00:11
источник
  • % expect - самое страшное изобретение. Это как сказать вашему отделу контроля качества: «Мы ожидаем 5 ошибок, поэтому отправляйте их, если количество ошибок составляет ровно 5». Не существует различия между ошибкой, которая является сообщением с ошибкой и ошибкой, которая форматирует ваш жесткий диск. :-) Спасибо, я исправил ссылку на правильный! –  Ron Burk 10.01.2014 в 18:54
  • Но ... но ... конфликты s / r не являются ошибками. Это правда, что выделение конкретных конфликтов было бы предпочтительнее, но конфликты не совсем в правилах как таковые, они находятся в сгенерированном конечном автомате. Таким образом, мы kludge это с% ожидать. Добро пожаловать в реальный мир. –  DigitalRoss 11.01.2014 в 18:59
0

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

    
ответ дан Yuval F 15.11.2009 в 13:58
источник
0

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

    
ответ дан Tomato 02.04.2012 в 06:30
источник
  • Правильная ссылка: marvin.cs.uidaho.edu/Teaching/CS445/danglingElse.html –  Shantha Kumara 08.02.2014 в 19:29
  • ___ answer1737613 ___ <div class="post-text" itemprop="text"> <p> Как заметил митенфеуго, у вас в грамматике есть классическая проблема «болтаться». Вы можете решить проблему, назначив приоритет правилам, вызывающим конфликт. </P> <p> Правило, вызывающее конфликт: </p> %pre% <p> Сначала запустите, сделав ELSE и LOWER_THAN_ELSE (псевдо-токен) не ассоциативными: </p> %pre% <p> Это дает ELSE больше приоритета над LOWER_THAN_ELSE просто потому, что сначала объявлен LOWER_THAN_ELSE. </p> <p> Затем в конфликтующем правиле вы должны назначить приоритет либо действию сдвига, либо уменьшению: </p> %pre% <p> Здесь более высокий приоритет присваивается смещению. Я включил вышеупомянутые исправления и перечислил полную грамматику ниже: </p> %pre%     </DIV> ___ qstntxt ___ <div class="post-text" itemprop="text"> <p> Когда я пытаюсь использовать yacc в следующем файле, я получаю конфликты ошибок: 1 shift / reduce Как я могу найти и исправить конфликт? </P> %pre%     </DIV> ___ qstnhdr ___ Как найти конфликт сдвига / уменьшения в этом файле yacc? ___ answer1737475 ___ <div class="post-text" itemprop="text"> <p> Сначала вы получите <a href="http://tldp.org/HOWTO/Lex-YACC-HOWTO-7.html"> вывод конечного автомата из yacc </a>. Состояние, которое может быть сдвинуто или уменьшено, представляет собой конфликт сдвига / сокращения. Найдите его, а затем разрешите конфликт, переписав грамматику. </P>     </DIV> ___ answer1737520 ___ <div class="post-text" itemprop="text"> <p> Возможно, вам стоит попробовать %code% , он генерирует выходные данные. </p> <p> Я тестировал здесь, и ваше описание грамматики не срабатывает в классической проблеме «болтаться». </p> <p> Взгляните на <a href="http://en.wikipedia.org/wiki/Dangling_else"> эту статью в Википедии </a>. </p>     </DIV> ___ commmment8224347 ___ Почему я должен сначала сделать ELSE и LOWER_THAN_ELSE (псевдо-токен) не ассоциативным? ___ commmment8235699 ___ Oh. Я не обратил на это внимания. Это не кажется необходимым, поскольку ELSE и LOWER_THAN_ELSE не имеют одинакового приоритета. ___ answer9970919 ___ <div class="post-text" itemprop="text"> <p> <a href="http://marvin.cs.uidaho.edu/Teaching/CS445/danglingElse.html"> Эта статья </a> дает альтернативное решение для одного, отправленного ardsrk. </p>     </DIV> ___ commmment10072866 ___% nonassoc необходимо. Использование только% токена не будет сообщать бизону о старшинстве. ___ commmment31678650 ___ И все это дает тот же результат, что и исходный yacc. Возможно, было бы полезно указать, что исходный конфликт ожидается и был правильно разрешен по умолчанию yacc, предпочитая сдвиг. ___ commmment10503672 ___ +1 для ссылки на болтающуюся другую статью! ___ commmment31651335 ___% expect - самое страшное изобретение. Это как сказать вашему отделу контроля качества: «Мы ожидаем 5 ошибок, поэтому отправляйте их, если количество ошибок составляет ровно 5». Не существует различия между ошибкой, которая является сообщением с ошибкой и ошибкой, которая форматирует ваш жесткий диск. :-) Спасибо, я исправил ссылку на правильный! ___ commmment32720789 ___ Правильная ссылка: marvin.cs.uidaho.edu/Teaching/CS445/danglingElse.html ___ commmment31678606 ___ Но ... но ... конфликты s / r не являются ошибками. Это правда, что выделение конкретных конфликтов было бы предпочтительнее, но конфликты не совсем в правилах как таковые, они находятся в сгенерированном конечном автомате. Таким образом, мы kludge это с% ожидать. Добро пожаловать в реальный мир. ___ answer14288156 ___ <div class="post-text" itemprop="text"> <p> Ах, правильный ответ на эту проблему обычно: <strong> <em> ничего не делать </em> </strong>. </p> <p> Сдвиг / уменьшение конфликтов <em> ожидается </em> с неоднозначными грамматиками. Они не являются <em> ошибками </em>, они <em> конфликты </em>. </Р> <p> Конфликт будет разрешен, если вы предпочитаете сдвиг по сокращению, что просто помогает решить проблему канонического болтания. </p> <p> И у bison даже есть выражение% expect <em> n </em>, чтобы вы не получили предупреждение о конфликте S / R, когда есть ровно <em> n </em>. </p>     </DIV> ___ –  Tomato 10.02.2014 в 07:41