Was bleibt für Laien eine Rekursion?

Laut einer Seite auf code.google.com ist "linke Rekursion" wie folgt definiert:

Die linke Rekursion bezieht sich nur auf jedes rekursive Nichtterminal, das, wenn es eine sententiale Form erzeugt, die sich selbst enthält, diese neue Kopie von sich links von der Produktionsregel erscheint.

Wikipedia bietet zwei verschiedene Definitionen:

1. In Bezug auf die kontextfreie Grammatik ist ein nicht-terminales r linksrekursiv, wenn das Symbol ganz links in einer der Produktionen von r ('Alternativen') entweder sofort (direkt / unmittelbar linksrekursiv) oder durch ein anderes nicht-terminales Symbol ist Definitionen (indirekt / versteckt links-rekursiv) werden erneut in r umgeschrieben.

2. "Eine Grammatik ist linksrekursiv, wenn wir ein nicht-terminales A finden, das schließlich eine sententiale Form mit sich selbst als linkem Symbol ableitet."

Ich fange gerade erst mit der Erstellung von Sprachen an und mache das in meiner Freizeit. Wenn es jedoch darum geht, einen Sprachparser auszuwählen, ist es ein Problem, das sofort im Vordergrund steht, ob die linke Rekursion von diesem Parser oder diesem Parser unterstützt wird . Das Nachschlagen von Begriffen wie "sententiale Form" führt nur zu weiteren Jargonlisten, aber die Unterscheidung der "linken" Rekursion muss fast etwas sehr Einfaches sein. Übersetzung bitte?

Eine Regel Rist linksrekursiv, wenn RSie zuerst herausfinden müssen, ob RÜbereinstimmungen vorliegen, um herauszufinden, ob Übereinstimmungen vorliegen. Dies geschieht, wenn es Rdirekt oder indirekt als erster Begriff in einer Produktion von sich selbst erscheint.

Stellen Sie sich eine Spielzeugversion der Grammatik für mathematische Ausdrücke vor, die nur addiert und multipliziert wird, um Ablenkung zu vermeiden:

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

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

Term ::= Number | Variable

Wie geschrieben, gibt es hier keine Linksrekursion - wir könnten diese Grammatik an einen Parser rekursiver Abstammung übergeben.

Angenommen, Sie haben versucht, es so zu schreiben:

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

Term ::= Number | Variable

Dies ist eine Grammatik, und einige Parser können damit umgehen, rekursive Abstiegsparser und LL-Parser jedoch nicht - weil die Regel für Expressionmit sich Expressionselbst beginnt . Es sollte offensichtlich sein, warum dies in einem Parser mit rekursivem Abstieg zu einer unbegrenzten Rekursion führt, ohne tatsächlich eine Eingabe zu verbrauchen.

Es spielt keine Rolle, ob sich die Regel direkt oder indirekt auf sich selbst bezieht; wenn Ahat eine Alternative , die beginnt mit Bund Bhat eine Alternative , die beginnt mit A, dann Aund Bsind beide indirekt linksrekursive und in einer rekursiven Abstieg Parser ihre Anpassungsfunktionen würden zu endlosen gegenseitigen Rekursion führen.

Ich werde versuchen, es in Laienbegriffe zu fassen.

Wenn Sie in Bezug auf den Analysebaum denken (nicht den AST, sondern den Besuch und die Erweiterung der Eingabe durch den Parser), führt die linke Rekursion zu einem Baum, der nach links und unten wächst. Die richtige Rekursion ist genau das Gegenteil.

Eine gängige Grammatik in einem Compiler ist beispielsweise eine Liste von Elementen. Nehmen wir eine Liste von Zeichenfolgen ("rot", "grün", "blau") und analysieren sie. Ich könnte die Grammatik auf einige Arten schreiben. Die folgenden Beispiele sind direkt links bzw. rechts rekursiv:

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

Die Bäume für diese Analyse:

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

Beachten Sie, wie es in Richtung der Rekursion wächst.

Dies ist kein wirkliches Problem, es ist in Ordnung, eine linksrekursive Grammatik schreiben zu wollen ... wenn Ihr Parser-Tool damit umgehen kann. Bottom-up-Parser kommen damit zurecht. So können modernere LL-Parser. Das Problem mit rekursiven Grammatiken ist nicht die Rekursion, sondern die Rekursion, ohne den Parser voranzutreiben, oder die Rekursion, ohne ein Token zu verbrauchen. Wenn wir beim Rekursieren immer mindestens 1 Token verbrauchen, erreichen wir schließlich das Ende der Analyse. Linke Rekursion ist definiert als Rekursion ohne Verbrauch, was eine Endlosschleife ist.

Diese Einschränkung ist lediglich ein Implementierungsdetail für die Implementierung einer Grammatik mit einem naiven Top-Down-LL-Parser (rekursiver Abstiegsparser). Wenn Sie sich an linksrekursive Grammatiken halten möchten, können Sie sich damit befassen, indem Sie die Produktion neu schreiben, um vor dem Rekursieren mindestens 1 Token zu verbrauchen. Auf diese Weise wird sichergestellt, dass wir nie in einer unproduktiven Schleife stecken bleiben. Für jede Grammatikregel, die linksrekursiv ist, können wir sie umschreiben, indem wir eine Zwischenregel hinzufügen, die die Grammatik auf nur eine Lookahead-Ebene reduziert und ein Token zwischen den rekursiven Produktionen verbraucht. (HINWEIS: Ich sage nicht, dass dies der einzige oder bevorzugte Weg ist, die Grammatik neu zu schreiben, sondern nur auf die verallgemeinerte Regel hinzuweisen. In diesem einfachen Beispiel ist die beste Option die Verwendung der rechtsrekursiven Form.) Da dieser Ansatz verallgemeinert ist, Ein Parser-Generator kann es implementieren, ohne den Programmierer (theoretisch) einzubeziehen. In der Praxis glaube ich, dass ANTLR 4 jetzt genau das tut.

Für die obige Grammatik würde die LL-Implementierung, die die linke Rekursion anzeigt, so aussehen. Der Parser würde mit der Vorhersage einer Liste beginnen ...

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();
    }
}

In Wirklichkeit haben wir es wirklich mit "naiver Implementierung" zu tun, dh. Wir haben zunächst einen bestimmten Satz vorhergesagt und dann die Funktion für diese Vorhersage rekursiv aufgerufen, und diese Funktion ruft naiv dieselbe Vorhersage erneut auf.

Bottom-up-Parser haben nicht das Problem rekursiver Regeln in beide Richtungen, da sie den Satzanfang nicht wiederholen, sondern den Satz wieder zusammensetzen.

Rekursion in einer Grammatik ist nur dann ein Problem, wenn wir von oben nach unten produzieren, dh. Unser Parser "erweitert" unsere Vorhersagen, wenn wir Token verbrauchen. Wenn wir nicht expandieren, sondern kollabieren (Produktionen werden "reduziert"), wie in einem Bottom-Up-Parser von LALR (Yacc / Bison), ist die Rekursion beider Seiten kein Problem.