Левая рекурсия в грамматике приводит к конфликтам

Во всей грамматике Bison я использую правую рекурсию, и я читал, что левая рекурсия лучше, потому что ей не нужно сначала строить весь стек.

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

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

Редактировать:
Но я думаю, что мне все равно следует включить конкретный пример, так как мое понимание немного меньше, чем полное :-) Изменение «команды разделителя списка» на «список разделителей команд» разрешает конфликт .

State 9 conflicts: 3 shift/reduce


Grammar

    0 $accept: input $end

    1 input: error NEWLINE
    2      | input NEWLINE
    3      | input list NEWLINE
    4      | /* empty */

    5 list: command
    6     | command separator
    7     | list separator command

    8 separator: SEMI
    9          | L_OR
   10          | L_AND

   11 command: variable_assignment
   12        | external_w_redir
   13        | external_w_redir AMP
   14        | pipeline
   15        | pipeline AMP

...

state 9

    5 list: command .
    6     | command . separator

    SEMI   shift, and go to state 18
    L_AND  shift, and go to state 19
    L_OR   shift, and go to state 20

    SEMI      [reduce using rule 5 (list)]
    L_AND     [reduce using rule 5 (list)]
    L_OR      [reduce using rule 5 (list)]
    $default  reduce using rule 5 (list)

    separator  go to state 22

c grammar yacc bison lalr
person Kyle Brandt    schedule 08.11.2009    source источник
comment
Можете ли вы опубликовать минимальный пример, где вы наблюдаете этот эффект? Я не думаю, что это работает таким образом, и я предполагаю, что у вас есть какие-то другие проблемы с вашей грамматикой. У Bison не должно быть проблем с левой или правой рекурсией, даже если левая рекурсия более эффективна.   -  person Thomas Padron-McCarthy    schedule 08.11.2009
comment
@Thomas Padron-McCarthy: обновлено, чтобы включить y.output Bison в режиме отладки.   -  person Kyle Brandt    schedule 08.11.2009

Ответы (2)


arrow_upward
4
arrow_downward

РЕДАКТИРОВАТЬ:

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

Вот упрощенная версия вашей исходной праворекурсивной грамматики:

list: COMMAND
      | COMMAND SEPARATOR
      | COMMAND SEPARATOR list
      ;

Эта грамматика соответствует (если я еще не более запутался, чем я думаю, что, конечно, возможно) входным данным C, CS, CSC, CSCS, CSCSC, CSCSCS и т. д. То есть последовательность КОМАНД, разделенных СЕПАРАТОРОМ, с необязательным РАЗДЕЛИТЕЛЕМ в конце.

А это упрощенная версия вашей леворекурсивной грамматики, которая дает конфликт сдвига/свертки в Bison:

list: COMMAND
      | COMMAND SEPARATOR
      | list SEPARATOR COMMAND
      ;

Если я все правильно расширил, эта грамматика соответствует входным данным C, CS, CSC, CSSC, CSCSC, CSSCSC и т. д. Это не двусмысленно, но не эквивалентно вашей леворекурсивной грамматике. Список КОМАНД не может иметь РАЗДЕЛИТЕЛЬ в конце, а РАЗДЕЛИТЕЛИ между КОМАНДАМИ могут быть удвоены.

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

Если важно, чтобы конечный разделитель был необязательным, а грамматика должна быть леворекурсивной, я бы предложил переписать его:

list: separatedlist
      | separatedlist SEPARATOR
      ;

separatedlist: COMMAND
               | separatedlist SEPARATOR COMMAND
               ;

Но я бы не стал беспокоиться о левом или правом, если только ваши списки не действительно длинные, или вы не собираетесь запускать свой синтаксический анализатор на очень ограниченном оборудовании. Я не думаю, что это имеет большое значение на современных настольных компьютерах.

person Thomas Padron-McCarthy    schedule 08.11.2009
comment
Если это так, я не понимаю, как это становится двусмысленным с этим изменением. Вот весь результат y.output: pastebin.org/51936 - person Kyle Brandt; 08.11.2009
comment
@ Кайл: Да, это не двусмысленно. Я изменил свой ответ. Но сейчас это не очень ответ. - person Thomas Padron-McCarthy; 08.11.2009
comment
Я только что заметил тот факт, что он также соответствует разделителям, а это не то, чего я хочу. Итак, я думаю, мне нужен правильный рекурсивный пример или выяснить, как получить то, что соответствует вашему первому примеру, используя левую рекурсию. - person Kyle Brandt; 08.11.2009
comment
Но я хочу этот необязательный последний SEP, потому что это может быть точка с запятой, что нормально. Я просто проверю, что последний разделитель не && или || в функции действия. - person Kyle Brandt; 08.11.2009

arrow_upward
1
arrow_downward

Путаница/ошибки, кажется, исходят из продукции для списка. Ваша левая рекурсивная версия:

list: command
    | command separator
    | list separator command

Ваша правильная рекурсивная версия:

list: command
    | command separator
    | command separator list

Эти два набора правил на самом деле совершенно разные, соответствующие разным вещам. Первый соответствует одной или нескольким командам с разделителями между ними и необязательным дополнительным разделителем после каждой команды. >. Второй вариант аналогичен, за исключением того, что он позволяет использовать дополнительный необязательный разделитель после команды LAST.

Предполагая, что вы действительно хотите, это леворекурсивная версия последнего, вы хотите

list_no_trailer: command
               | list_no_trailer separator command

list: list_no_trailer
    | list_no_trailer separator

Конфликт в вашей версии возникает из-за того, что после синтаксического анализа «команды» и просмотра разделителя он не знает, следует ли вытащить его в качестве необязательного разделителя после команды или уменьшить команду в соответствии с предположением что это разделитель списка, и сразу после него будет другая команда. Для этого потребуется 2 символа просмотра вперед, поэтому ваша грамматика LR (2), но не LR (1)

person Chris Dodd    schedule 08.11.2009