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

В цялата граматика на 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 и т.н. Тоест поредица от КОМАНДИ, разделени със SEPARATOR, с незадължителен СЕПАРАТОР в края.

И това е опростената версия на вашата ляво-рекурсивна граматика, която дава конфликт на изместване/намаляване в 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
@Kyle: Да, не е двусмислено. Промених отговора си. Но сега това не е кой знае какъв отговор. - 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

Конфликтът във вашата версия идва от факта, че след анализиране на „команда“ и виждане на разделител на lookahed, той не знае дали да изтегли това като незадължителен разделител след командата или да намали командата при предположението че това е разделител на списък и ще има друга команда веднага след него. Ще са необходими 2 знака за предварителен преглед за това, така че вашата граматика е LR(2), но не и LR(1)

person Chris Dodd    schedule 08.11.2009