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

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

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

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

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

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
Источник

2 ответа

Решение

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

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

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

list: COMMAND
      | COMMAND SEPARATOR
      | COMMAND SEPARATOR list
      ;

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

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

list: COMMAND
      | COMMAND SEPARATOR
      | list SEPARATOR COMMAND
      ;

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

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

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

list: separatedlist
      | separatedlist SEPARATOR
      ;

separatedlist: COMMAND
               | separatedlist SEPARATOR COMMAND
               ;

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

Источник

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

list: command
    | command separator
    | list separator command

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

list: command
    | command separator
    | command separator list

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

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

list_no_trailer: command
               | list_no_trailer separator command

list: list_no_trailer
    | list_no_trailer separator

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

Источник
Другие вопросы по тегам