W kategoriach laika, czym jest rekurencja?

Według jednej strony na code.google.com „lewą rekurencję” definiuje się następująco:

Lewa rekurencja odnosi się tylko do każdego rekurencyjnego nieterminala, który, gdy tworzy sentymentalną formę zawierającą się, ta nowa kopia sama pojawia się po lewej stronie reguły produkcji.

Wikipedia oferuje dwie różne definicje:

1. Jeśli chodzi o gramatykę bezkontekstową, nieterminalny r jest rekurencyjny w lewo, jeśli skrajny lewy symbol w którejkolwiek z produkcji r („alternatywy”) albo natychmiast (bezpośrednio / natychmiast lewostronnie rekurencyjny), albo poprzez inne nieterminalne definicje (pośrednie / ukryte lewostronnie rekurencyjne) przepisują ponownie na r.

2. „Gramatyka jest lewostronnie rekurencyjna, jeśli znajdziemy jakiś nieterminalny A, który ostatecznie uzyska formę sentymentalną z samym sobą jako lewym symbolem”.

Właśnie zaczynam od tworzenia języków i robię to w wolnym czasie. Jednak jeśli chodzi o wybranie parsera językowego, to czy parser rekurencyjny jest obsługiwany przez ten parser, czy ten parser jest problemem, który natychmiast pojawia się na pierwszym planie . Wyszukiwanie terminów takich jak „forma sentymentalna” prowadzi tylko do dalszych list żargonu, ale rozróżnienie „lewej” rekurencji prawie musi być czymś bardzo prostym. Tłumaczenie proszę?

Reguła Rjest lewostronnie rekurencyjna, jeśli, aby dowiedzieć się, czy Rmecze, najpierw musisz dowiedzieć się, czy Rmecze. Dzieje się tak, gdy Rpojawia się, bezpośrednio lub pośrednio, jako pierwszy termin w niektórych produkcjach samego siebie.

Wyobraź sobie zabawkową wersję gramatyki dla wyrażeń matematycznych, z dodawaniem i mnożeniem, aby uniknąć rozproszenia:

Expression ::= Multiplication '+' Expression
            || Multiplication

Multiplication ::= Term '*' Term
                 || Term

Term ::= Number | Variable

Jak napisano, nie ma tu lewej rekurencji - moglibyśmy przekazać tę gramatykę parserowi rekurencyjnemu.

Załóżmy jednak, że próbowałeś napisać to w ten sposób:

Expression ::= Expression '*' Expression
            || Expression '+' Expression
            || Term

Term ::= Number | Variable

Jest to gramatyka i niektóre parsery mogą sobie z tym poradzić, ale parsery rekurencyjnego opadania i parsery LL nie mogą - ponieważ reguła dla Expressionzaczyna się Expressionsama. Powinno być oczywiste, dlaczego w parserze z opadaniem rekurencyjnym prowadzi to do nieograniczonej rekurencji bez faktycznego zużywania jakichkolwiek danych wejściowych.

Nie ma znaczenia, czy reguła odnosi się do siebie bezpośrednio, czy pośrednio; jeśli Ama alternatywę, która zaczyna się od B, i Bma alternatywę, która zaczyna się od A, wtedy Ai Boba są pośrednio lewostronne, a w parserze rekurencyjnym-opadającym ich funkcje dopasowania doprowadziłyby do nieskończonej wzajemnej rekurencji.

Postaram się przełożyć to na warunki dla laika.

Jeśli myślisz w kategoriach drzewa parsowania (nie AST, ale odwiedziny parsera i rozszerzenie danych wejściowych), lewa rekurencja powoduje, że drzewo rośnie w lewo i w dół. Właściwa rekurencja jest dokładnie odwrotna.

Na przykład, powszechną gramatyką w kompilatorze jest lista elementów. Weźmy listę ciągów („czerwony”, „zielony”, „niebieski”) i parsujemy ją. Mogę napisać gramatykę na kilka sposobów. Następujące przykłady są odpowiednio odpowiednio lewe lub prawe rekurencyjne:

arg_list:                           arg_list:
      STRING                              STRING
    | arg_list ',' STRING               | STRING ',' arg_list 

Drzewa dla tych analiz:

         (arg_list)                       (arg_list)
          /      \                         /      \
      (arg_list)  BLUE                  RED     (arg_list)
       /       \                                 /      \
   (arg_list) GREEN                          GREEN    (arg_list)
    /                                                  /
 RED                                                BLUE

Zwróć uwagę, jak rośnie w kierunku rekurencji.

To naprawdę nie jest problem, dobrze jest napisać lewą gramatykę rekurencyjną ... jeśli twoje narzędzie do analizowania składni może to obsłużyć. Parsery oddolne radzą sobie dobrze. Podobnie mogą być bardziej nowoczesne parsery LL. Problem z gramatami rekurencyjnymi nie polega na rekurencji, jest to rekurencja bez posuwania się parsera lub rekurencja bez zużywania tokena. Jeśli zawsze zużyjemy co najmniej 1 żeton, gdy się powtórzymy, w końcu dojdziemy do końca analizy. Lewa rekurencja jest definiowana jako rekurencja bez konsumowania, która jest nieskończoną pętlą.

Ograniczenie to jest jedynie szczegółem implementacji gramatyki z naiwnym parserem LL z góry na dół (parser rekurencyjnego opadania). Jeśli chcesz pozostać przy lewej gramatyce rekurencyjnej, możesz sobie z tym poradzić, przepisując produkcję, aby zużyła co najmniej 1 token przed rekurencją, dzięki czemu nigdy nie utkniemy w nieproduktywnej pętli. Dla każdej reguły gramatyki, która jest lewostronnie rekurencyjna, możemy przepisać ją przez dodanie reguły pośredniej, która spłaszcza gramatykę do tylko jednego poziomu wyprzedzenia, zużywając token między produkcjami rekurencyjnymi. (UWAGA: Nie mówię, że jest to jedyny sposób lub preferowany sposób przepisania gramatyki, wskazując jedynie ogólną regułę. W tym prostym przykładzie najlepszą opcją jest użycie formy rekurencyjnej z prawej). Ponieważ takie podejście jest uogólnione, generator parsera może go zaimplementować bez udziału programisty (teoretycznie). W praktyce uważam, że ANTLR 4 właśnie to robi.

Dla powyższej gramatyki implementacja LL wyświetlająca lewą rekurencję wyglądałaby tak. Analizator składni zaczynałby się od przewidywania listy ...

bool match_list()
{
    if(lookahead-predicts-something-besides-comma) {
       match_STRING();
    } else if(lookahead-is-comma) {
       match_list();   // left-recursion, infinite loop/stack overflow
       match(',');
       match_STRING();
    } else {
       throw new ParseException();
    }
}

W rzeczywistości mamy do czynienia z „naiwnym wdrażaniem”, tj. początkowo przewidzieliśmy dane zdanie, następnie rekurencyjnie wywołaliśmy funkcję dla tej prognozy, a ta funkcja naiwnie wywołuje tę samą prognozę ponownie.

Parsery oddolne nie mają problemu z regułami rekurencyjnymi w obu kierunkach, ponieważ nie dokonują ponownej analizy początku zdania, działają poprzez złożenie zdania z powrotem.

Rekurencja w gramatyce stanowi problem tylko wtedy, gdy produkujemy z góry na dół, tj. nasz parser działa poprzez „rozszerzanie” naszych przewidywań w miarę konsumowania tokenów. Jeśli zamiast się rozwijać, zwiniemy się (produkcje są „zmniejszone”), tak jak w analizatorze oddolnym LALR (Yacc / Bison), wówczas rekurencja jednej ze stron nie stanowi problemu.