Was ist ein Baumparser in ANTLR und muss ich einen schreiben?

StackOverflow https://stackoverflow.com/questions/697755

Frage

Ich schreibe einen Lexer/Parser für eine kleine Teilmenge von C in ANTLR, der in einer Java-Umgebung ausgeführt wird.Ich bin neu in der Welt der Sprachgrammatiken und in vielen ANTLR-Tutorials wird ein AST – Abstract Syntax Tree erstellt. Bin ich gezwungen, einen zu erstellen und warum?

War es hilfreich?

Lösung 2

ich fand diese Antwort zur Frage zu jGuru von Terence Parr, dem Erfinder von ANTLR.Ich habe diese Erklärung von der verlinkten Seite kopiert Hier:

Mit Aktionen innerhalb des Parsers können nur einfache, sogenannte syntaxgesteuerte Übersetzungen durchgeführt werden.Diese Art von Übersetzungen kann nur Konstrukte ausspucken, die Funktionen von Informationen sind, die zu diesem Zeitpunkt in der Analyse bereits vorhanden sind.Mit Baumparsern können Sie ein Zwischenformular durchlaufen und diesen Baum manipulieren, indem Sie ihn über mehrere Übersetzungsphasen schrittweise in ein endgültiges Formular umwandeln, das problemlos als neue Übersetzung wieder ausgedruckt werden kann.

Stellen Sie sich ein einfaches Übersetzungsproblem vor, bei dem Sie eine HTML-Seite mit dem Titel „Es gibt n Elemente“ ausdrucken möchten, wobei n die Anzahl der Bezeichner ist, die Sie im Eingabestream gefunden haben.Die IDs müssen nach dem Titel wie folgt gedruckt werden:

<html>
<head>
<title>There are 3 items</title>
</head>
<body>
<ol>
<li>Dog</li>
<li>Cat</li>
<li>Velociraptor</li>
</body>
</html>

aus der Eingabe

Dog
Cat
Velociraptor

Wie können Sie also mit einfachen Aktionen in Ihrer Grammatik den Titel berechnen?Sie können nicht, ohne die gesamte Eingabe zu lesen.Ok, jetzt wissen wir also, dass wir eine Zwischenform brauchen.Das Beste ist normalerweise ein AST, den ich gefunden habe, da er die Eingabestruktur aufzeichnet.In diesem Fall ist es nur eine Liste, aber sie verdeutlicht meinen Standpunkt.

Ok, jetzt wissen Sie, dass ein Baum für alles andere als einfache Übersetzungen eine gute Sache ist.Wie erhalten Sie bei einem gegebenen AST eine Ausgabe davon?Stellen Sie sich einfache Ausdrucksbäume vor.Eine Möglichkeit besteht darin, die Knoten im Baum zu spezifischen Klassen wie PlusNode, IntegerNode usw. zu machen.Dann bitten Sie einfach jeden Knoten, sich selbst auszudrucken.Für die Eingabe 3+4 hätten Sie einen Baum:

+ | 3 -- 4

und Klassen

class PlusNode extends CommonAST {
  public String toString() {
    AST left = getFirstChild();
    AST right = left.getNextSibling();
    return left + " + " + right;
  }
}

class IntNode extends CommonAST {
  public String toString() {
    return getText();
  }
}

Bei einem gegebenen Ausdrucksbaum können Sie ihn mit t.toString() wieder in Text übersetzen.Also, was ist daran falsch?Scheint großartig zu funktionieren, oder?In diesem Fall scheint es gut zu funktionieren, weil es einfach ist, aber ich behaupte, dass Baumgrammatiken selbst für dieses einfache Beispiel besser lesbar sind und formalisierte Beschreibungen genau dessen sind, was Sie in PlusNode.toString() codiert haben.

expr returns [String r]
{
    String left=null, right=null;
}

: #("+" left=expr right=expr) {r=left + " + " + right;}
| i:INT                       {r=i.getText();}
;

Beachten Sie, dass der spezifische Klassenansatz („heterogenes AST“) tatsächlich einen vollständigen Parser mit rekursivem Abstieg für #(+ INT INT) von Hand in toString() codiert.Als Parser-Generator-Leute sollte Ihnen das Angst machen.;)

Die Hauptschwäche des heterogenen AST-Ansatzes besteht darin, dass er nicht bequem auf Kontextinformationen zugreifen kann.In einem rekursiv absteigenden Parser ist der Zugriff auf Ihren Kontext einfach, da er als Parameter übergeben werden kann.Sie wissen auch genau, welche Regel welche andere Regel aufrufen kann (ist dieser Ausdruck beispielsweise eine WHILE-Bedingung oder eine IF-Bedingung?), indem Sie sich die Grammatik ansehen.Die obige PlusNode-Klasse existiert in einer losgelösten, isolierten Welt, in der sie keine Ahnung hat, wer ihre toString()-Methode aufrufen wird.Schlimmer noch: Der Programmierer kann beim Lesen nicht erkennen, in welchem ​​Kontext es aufgerufen wird.

Zusammenfassend funktioniert das Hinzufügen von Aktionen zu Ihrem Eingabeparser für sehr einfache Übersetzungen, bei denen:

  1. Die Reihenfolge der Ausgabekonstrukte ist dieselbe wie die Eingabereihenfolge
  2. Alle Konstrukte können aus Informationen generiert werden, die bis zu dem Punkt analysiert wurden, an dem Sie sie ausspucken müssen

Darüber hinaus benötigen Sie eine Zwischenform – die AST ist normalerweise die beste Form.Die Verwendung einer Grammatik zum Beschreiben der Struktur des AST ist analog zur Verwendung einer Grammatik zum Parsen Ihres Eingabetextes.Formalisierte Beschreibungen in einer domänenspezifischen Hochsprache wie ANTLR sind besser als handcodierte Parser.Aktionen innerhalb einer Baumgrammatik haben einen sehr klaren Kontext und können bequem auf Informationen zugreifen, die von aufrufenden Regeln übergeben werden.Auch Übersetzungen, die den Baum für Multipass-Übersetzungen manipulieren, sind mit einer Baumgrammatik viel einfacher.

Andere Tipps

ein AST mit ANTLR Erstellen in die Grammatik aufgenommen. Sie müssen dies nicht tun, aber es ist ein wirklich gutes Werkzeug für kompliziertere Anforderungen. Dies ist ein Tutorial auf Baumkonstruktion Sie verwenden können.

Im Grunde genommen mit ANTLR, wenn die Quelle analysiert wird immer, haben Sie ein paar Optionen. Sie können Code oder eine AST unter Verwendung von Rewrite-Regeln in der Grammatik erzeugen. Ein AST ist im Grunde einen in Speicher Darstellung Ihrer Quelle. Von dort gibt es viel Sie tun können.

Es gibt eine Menge zu antlr. Wenn Sie nicht bereits haben, würde ich empfehlen das Buch bekommen .

Ich denke, die Schaffung der AST ist optional. Das Abstract Syntax-Baum ist für die nachfolgende Verarbeitung wie semantische Analyse des analysierten Programms nützlich.

Nur Sie können entscheiden, ob Sie einen erstellen müssen. Wenn Ihr einziges Ziel syntaktische Validierung ist dann brauchen Sie nicht ein zu generieren. In javacc (ähnlich ANTLR) gibt es ein Dienstprogramm genannt JJTree , die die Erzeugung des AST ermöglicht. So stelle ich mir das in ANTLR ist optional auch.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top