In der Formensprache der Theorie der Informatik, ist Linksrekursion ein Spezialfall der Rekursion.

In Bezug auf die kontextfreie Grammatik wird eine nicht-terminale linksrekursive wenn die am weitesten links stehende Symbol in einem der "Produktionen entweder unmittelbar oder durch einen anderen nicht-terminale Definitionen schreibt wieder.

Definition

"Eine Grammatik ist links rekursiv, wenn wir eine Nicht-Terminal A, die schließlich leiten eine Satzform mit sich selbst als links-Symbol kann zu finden."

Sofortige Linksrekursion

Sofortige Linksrekursion in Regeln der Form auftritt,

wo und sind Sequenzen von Nichtterminalen und Terminals, und nicht mit zu beginnen. Zum Beispiel die Regel

wird sofort nach links-rekursive. Die Rekursiver Abstieg für diese Regel könnte wie folgt aussehen:

und eine Rekursiver Abstieg würde in Endlosschleife fallen, wenn sie versuchen, eine Grammatik, die diese Regel enthält analysieren.

Indirekte Linksrekursion

Indirekte Linksrekursion in seiner einfachsten Form kann wie folgt definiert werden:

vielleicht geben die Ableitung

Allgemeiner gesagt, für die Nichtterminale, indirekte Linksrekursion können als von der Form definiert werden:

wo sind Sequenzen von Nichtterminalen und Terminals.

Aufnahme Linksrekursion in Top-down-Analyse

Eine formale Grammatik, die links Rekursion enthält, kann nicht von einer LL-Parser oder andere naive rekursiven Abstiegs-Parser analysiert, wenn es nicht zu einer schwach äquivalent rechten rekursive Form überführt werden. Im Gegensatz dazu ist Linksrekursion für LALR Parser bevorzugt, da es in Stackverbrauch niedriger als richtige Rekursion führt. Allerdings können mehr anspruchsvolle Top-down-Parser allgemeinen kontextfreien Grammatiken durch die Verwendung von Plankürzungen umsetzen. Im Jahr 2006, Frost und Hafiz beschrieben einen Algorithmus, der mehrdeutig Grammatiken mit direktem linksrekursive Produktionsregeln aufnimmt. Das Algorithmus wurde zu einem vollständigen Parsing-Algorithmus erweitert, um Platz für indirekte als auch direkte Links-Rekursion in polynomieller Zeit und kompakte Polynom-size Darstellungen der potenziell exponentielle Anzahl der Syntaxbäume für hoch mehrdeutig Grammatiken durch Frost, Hafiz und Callaghan in generieren 2007. Die Autoren dann den Algorithmus implementiert als eine Reihe von Parser Kombinatoren in der Haskell-Programmiersprache geschrieben.

Entfernen Linksrekursion

Entfernen unmittelbar links Rekursion

Die allgemeinen Algorithmus zu entfernen unmittelbar links Rekursion folgt. Mehrere Verbesserungen an diesem Verfahren vorgenommen wurden, einschließlich der in "Entfernen Linksrekursion von kontextfreien Grammatiken" beschriebenen, von Robert C. Moore geschrieben. Für jede Regel der Form

woher:

• A eine linksrekursive Nonterminal
•  ist eine Sequenz von Terminalen und Terminals, die nicht null ist
•  ist eine Sequenz von Terminalen und Anschlüsse, die nicht mit A. hat starten

ersetzen Sie die A-Produktion um der Produktion:

Und erstellen Sie ein neues Nichtterminal

Das neu erstellte Symbol wird oft der "Schwanz", oder der "Rest" bezeichnet.

Als Beispiel betrachten wir die Regel

Dies könnte neu geschrieben werden, um links Rekursion zu vermeiden

Die letzte Regel passiert, entspricht dem etwas kürzeren Form zu sein

Entfernen indirekten linken Rekursion

Wenn die Grammatik hat keine -Productions und nicht zyklisch ist, kann diese allgemeinen Algorithmus angewendet werden, um indirekte Linksrekursion zu entfernen:

Ordnen Sie die Nichtterminale in irgendeiner festen Reihenfolge.

Fallstricke

Die oben genannten Transformationen entfernen linken Rekursion durch die Schaffung einer rechts rekursive Grammatik; aber dies ändert die Assoziativität der unsere Regeln. Linksrekursion macht linken Assoziativität; Recht Rekursion macht rechts Assoziativität. Beispiel: Wir beginnen mit einer Grammatik:

Nach angewendet Standardtransformationen mit den Links-Rekursion zu entfernen, haben wir die folgende Grammatik:

Parsen der Zeichenfolge 'a - a - a' mit dem ersten Grammatik in einer LALR Parser würde im Syntaxbaum geführt haben:

Dieser Syntaxanalysebaum wächst auf der linken Seite, die anzeigt, dass das "-" Operator bleibt assoziativ darstellt - a.

Aber jetzt, da wir die Grammatik verändert, sieht unsere Parse-Baum wie folgt aus:

Wir sehen, dass der Baum wächst auf der rechten Seite, was ein -. Wir haben die Assoziativität der Bediener geändert '-', ist es nun rechtsassoziativ.

Das Problem ist, dass normale Arithmetik erfordert linken Assoziativität. Mehrere Lösungen sind: schreiben Sie die Grammatik, um rekursive gelassen werden, oder schreiben Sie die Grammatik mit mehr Terminale, um die richtige Rangfolge / Assoziativität, oder wenn mit YACC oder Bison, gibt es Betreiber Erklärungen% links,% rechts und% nonassoc, die sagen, zwingen der Parser-Generator, der zu zwingen Assoziativität.