Dlaczego lewa rekurencja jest zła?

Dlaczego w konstrukcji kompilatora należy wyeliminować lewą rekurencję w gramatyce? Czytam, że dzieje się tak, ponieważ może powodować nieskończoną rekurencję, ale czy nie jest to prawdą również w przypadku prawidłowej gramatyki rekurencyjnej?

Lewe gramatyki rekurencyjne niekoniecznie są złe. Gramatyki te można łatwo analizować za pomocą stosu, aby śledzić już przeanalizowane frazy, tak jak ma to miejsce w parserze LR .

Przypomnijmy, że lewostronna reguła gramatyki CF ma postać:$G = (V,\Sigma,R,S)$

$\alpha \rightarrow \alpha \beta$

z elementem i elementem . (Zobacz pełną formalną definicję krotki tam ).V β V ∪ Σ ( V , Σ , R , S $\alpha$$V$$\beta$$V \cup \Sigma$$(V,\Sigma,R,S)$

Zazwyczaj jest w rzeczywistości sekwencją terminali i terminali, a dla istnieje inna reguła, w której nie pojawia się po prawej stronie.α $\beta$$\alpha$$\alpha$

Za każdym razem, gdy parser gramatyki odbiera nowy terminal (z leksera), terminal ten jest przesuwany na stos: operacja ta nazywana jest przesunięciem .

Za każdym razem, gdy prawa strona reguły jest dopasowywana przez grupę kolejnych elementów u góry stosu, ta grupa jest zastępowana przez pojedynczy element reprezentujący nowo dopasowane wyrażenie. Ta zamiana nazywa się redukcją .

Przy prawidłowej gramatyce rekurencyjnej stos może rosnąć w nieskończoność, aż nastąpi redukcja, co znacznie ograniczy możliwości analizy. Jednak lewe rekurencyjne pozwolą kompilatorowi wygenerować redukcje wcześniej (w rzeczywistości tak szybko, jak to możliwe). Zobacz wpis na Wikipedii, aby uzyskać więcej informacji.

Rozważ tę zasadę:

example : 'a' | example 'b' ;

Rozważmy teraz parser LL próbujący dopasować niepasujący ciąg znaków, taki jak 'b'ta reguła. Ponieważ 'a'nie pasuje, spróbuje dopasować example 'b'. Ale aby to zrobić, musi się zgadzać example... i to właśnie starało się zrobić. Może utknąć, próbując na zawsze sprawdzić, czy można go dopasować, ponieważ zawsze próbuje dopasować ten sam strumień tokenów do tej samej reguły.

Aby temu zapobiec, musiałbyś parsować od prawej strony (co jest dość rzadkie, o ile widziałem, i zamiast tego spowodowałby właściwą rekurencję problemu), sztucznie ograniczyć dozwoloną liczbę zagnieżdżeń lub dopasować token przed rozpoczęciem rekurencji, więc zawsze jest przypadek podstawowy (czyli gdzie wszystkie tokeny zostały zużyte i nadal nie ma pełnego dopasowania). Ponieważ reguła rekurencyjna jest już trzecia, nie ma tego samego problemu.

(Wiem, że to pytanie jest już dość stare, ale w przypadku, gdy inni ludzie mają to samo pytanie ...)

Czy pytasz w kontekście parserów rekurencyjnego zejścia? Na przykład dla gramatyki expr:: = expr + term | term, dlaczego coś takiego (lewy rekurencyjny):

// expr:: = expr + term
expr() {
   expr();
   if (token == '+') {
      getNextToken();
   }
   term();
}

jest problematyczne, ale nie to (prawda rekurencyjna)?

// expr:: = term + expr
expr() {
   term();
   if (token == '+') {
      getNextToken();
      expr();
   }
}

Wygląda na to, że obie wersje expr()same się nazywają. Ale istotną różnicą jest kontekst - tj. Bieżący token, kiedy wykonuje się to połączenie rekurencyjne.

W lewym przypadku rekurencyjnym expr()ciągle wywołuje się z tym samym tokenem i nie robi się żaden postęp. W odpowiednim przypadku rekurencyjnym zużywa część danych wejściowych w połączeniu z term()i token PLUS przed nawiązaniem połączenia z expr(). W tym momencie wywołanie rekurencyjne może wywołać termin, a następnie zakończyć przed ponownym przejściem do testu if.

Rozważmy na przykład parsowanie 2 + 3 + 4. Lewy rekursywny parser wywołuje expr()nieskończenie długo, gdy utknął na pierwszym tokenie, podczas gdy prawy rekurencyjny parser zużywa „2 +” przed expr()ponownym wywołaniem . Drugie połączenie z expr()dopasowaniem „3 +” i połączenie expr()z tylko 4 pozostałymi. 4 pasuje do terminu, a parsowanie kończy się bez żadnych wywołań expr().

Z instrukcji Bison:

„Dowolną sekwencję można zdefiniować za pomocą rekurencji lewej lub prawej, ale zawsze należy używać rekurencji lewej , ponieważ może ona analizować sekwencję dowolnej liczby elementów z ograniczoną przestrzenią stosu. Prawa rekurencja zajmuje miejsce na stosie Bizona w proporcjonalnie do liczby elementów w sekwencji, ponieważ wszystkie elementy muszą zostać przesunięte na stos, zanim reguła będzie mogła zostać zastosowana nawet raz. Aby uzyskać dodatkowe wyjaśnienie, zobacz Algorytm parsera Bison. ”

http://www.gnu.org/software/bison/manual/html_node/Recursion.html

Zależy to więc od algorytmu analizatora składni, ale jak stwierdzono w innych odpowiedziach, niektóre analizatory składni mogą po prostu nie działać z lewą rekurencją