Wie in Entfernen der linken Rekursion erläutert, gibt es zwei Möglichkeiten, die linke Rekursion zu entfernen.
Was normalerweise benutzt wird, um die linke Rekursion mit ANTLR zu entfernen (nicht zu haben)? Ich habe Flex / Bison für Parser verwendet, aber ich muss ANTLR verwenden. Die einzige Sache, die ich besorgt über die Verwendung von ANTLR (oder LL-Parser in general) ist links Rekursion Entfernung.
Ich habe etwas mit der folgenden Grammatik experimentiert.
%Vor%Nach der Entfernung der linken Rekursion bekomme ich die folgende
%Vor%Ich könnte mir die folgende ANTLR-Darstellung einfallen lassen. Obwohl es relativ einfach und geradlinig ist, scheint die Grammatik, die nicht die linke Rekursion hat, der bessere Weg zu sein.
%Vor%Wenn Sie die Grammatik schreiben, dann versuchen Sie natürlich, es zu schreiben, um die Fallstricke Ihres speziellen Parsergenerators zu vermeiden.
Normalerweise erhalte ich nach meiner Erfahrung ein Referenzhandbuch für die (ältere) Sprache von Interesse, und es enthält bereits eine Grammatik oder Eisenbahndiagramme, und es ist was es ist.
In diesem Fall wird die Entfernung der linken Rekursion aus einer Grammatik von Hand gemacht. Es gibt keinen Markt für Tools zum Entfernen von Linksrekursionen. Wenn Sie einen solchen Code hätten, wäre er auf eine Grammatiksyntax spezialisiert, die nicht mit der Grammatiksyntax übereinstimmt, die Sie haben.
Diese Entfernung ist in vielen Fällen eine Frage des Schweißes, und es gibt normalerweise nicht viel davon. Also die übliche Herangehensweise ist dein Grammatikmesser rauszuholen und es zu tun.
Ich denke nicht, wie Sie Linksrekursionen entfernen, wie ANTLR Bäume bekommt. Sie müssen zuerst die linke Rekursion durchführen, oder ANTLR (welcher LL-Parser-Generator Sie auch verwenden) wird Ihre Grammatik einfach nicht akzeptieren.
Es gibt diejenigen von uns, die nicht wollen, dass der Parsergenerator ernsthafte Einschränkungen für das, was wir für eine kontextfreie Grammatik schreiben können, enthält. In diesem Fall möchten Sie etwas wie einen GLR-Parser-Generator verwenden, der die Links- oder Rechtsrekursion mit Leichtigkeit handhabt. Unvernünftige Menschen können sogar auf eine automatisierte AST-Generierung bestehen, ohne dass der Grammatik-Schreiber dies tun muss. Ein Tool, das beides kann, finden Sie im DMS Software Reengineering Toolkit .
Betrachten Sie etwas wie eine typische Parameterliste:
%Vor%Da Sie mit Parametern keine Priorität oder Assoziativität in Betracht ziehen, ist es recht einfach, auf die richtige Rekursion umzustellen, auf Kosten einer zusätzlichen Produktion:
%Vor%In den schwerwiegendsten Fällen möchten Sie vielleicht etwas Zeit im Drachenbuch verbringen. Dies wird hauptsächlich in Kapitel 4 behandelt.
Soweit es die Ernsthaftigkeit betrifft, bin ich mir ziemlich sicher, dass ANTLR einfach keine Grammatik akzeptieren wird, die linke Rekursion enthält, was es in die Kategorie "absolute Notwendigkeit" bringen würde.
In praktischer Hinsicht, wie ernst Entfernen der linken Rekursion in ANTLR? Ist dies ein Showstopper in der Verwendung von ANTLR?
Ich glaube, Sie haben ein Missverständnis der Linksrekursion. Es ist eine Eigenschaft der Grammatik, nicht des Parsergenerators oder der Interaktion zwischen dem Parsergenerator und der Spezifikation. Es passiert, wenn das erste Symbol auf der rechten Seite einer Regel gleich dem Nicht-Terminal ist, das der Regel selbst entspricht.
Um das inhärente Problem hier zu verstehen, müssen Sie etwas darüber wissen, wie ein rekursiver-absteigender (LL) Parser funktioniert. In einem LL-Parser wird die Regel für jedes nicht terminale Symbol durch eine dieser Regel entsprechende Funktion implementiert. Also, nehme an, ich habe eine Grammatik wie folgt:
%Vor%Dann würde der Parser (ungefähr) so aussehen:
%Vor%Was passiert jedoch, wenn ich die Grammatik folgendermaßen ändere?
%Vor% Vermutlich möchte ich, dass diese Grammatik eine Sprache wie c*b repräsentiert. Die entsprechende Funktion im LL-Parser würde so aussehen:
Also können wir keine Linksrekursion haben. Schreiben Sie die Grammatik wie folgt um:
%Vor%und der Parser ändert sich wie folgt:
%Vor%(Disclaimer: Dies ist meine rudimentäre Annäherung an einen LL-Parser, der nur zu Demonstrationszwecken in Bezug auf diese Frage gedacht ist. Er enthält offensichtliche Fehler.)
Ich kann nicht für ANTLR sprechen, aber im Allgemeinen die Schritte, um eine linke Rekursion des Formulars zu eliminieren:
%Vor%ist es zu ändern:
%Vor% (Beachten Sie, dass B mindestens einmal angezeigt werden muss)
oder, wenn ANTLR die Kleene-Schließung nicht unterstützt, können Sie Folgendes tun:
%Vor%Wenn Sie ein Beispiel für Ihre Regeln angeben, bei denen es Konflikte gibt, kann ich eine bessere, spezifischere Antwort liefern.
Tags und Links antlr compiler-theory