wake-up-neo.net

Erstellen eines abstrakten Syntaxbaums mit einer Liste von Tokens

Ich möchte eine AST aus einer Liste von Token erstellen. Ich erstelle eine Skriptsprache und habe bereits den Teil zur lexikalischen Analyse ausgeführt, aber ich habe keine Ahnung, wie ich eine AST erstellen soll. Die Frage ist also, wie nehme ich so etwas:

Word, int
Word, x
SYMBOL, =
NUMBER, 5
SYMBOL, ;

und in einen abstrakten Syntaxbaum konvertieren? Am liebsten würde ich dies tun ohne eine Bibliothek wie ANTLR oder was auch immer, ich würde lieber versuchen, es selbst von Grund auf zu tun. Wenn es sich jedoch um eine sehr komplexe Aufgabe handelt, macht es mir nichts aus, eine Bibliothek zu verwenden :) Danke

35
metro-man

Der grundlegende Trick besteht darin, zu erkennen, dass die Analyse, wie auch immer sie durchgeführt wird, in inkrementellen Schritten erfolgt, einschließlich des Lesens der Token nacheinander.

Bei jedem inkrementellen Schritt besteht die Möglichkeit, einen Teil der AST zu erstellen, indem AST Fragmente kombiniert werden, die mit anderen inkrementellen Schritten erstellt wurden. Dies ist eine rekursive Idee, die sich letztendlich darin niederschlägt, AST Blattknoten für Token zu erstellen, wenn diese gescannt werden. Diese Grundidee kommt in so ziemlich allen AST-Parsern vor.

Wenn man einen rekursiven Abstiegsparser erstellt, erstellt man im Endeffekt ein kooperierendes System von rekursiven Prozeduren, von denen jede ein Nichtterminal in der jeweils implementierten Grammatik erkennt. Für das reine Parsen gibt jede Prozedur einfach einen Booleschen Wert für "Nicht-Terminal (nicht) erkannt" zurück.

Um ein AST mit einem rekursiven Abstiegsparser zu erstellen, werden diese Prozeduren so entworfen, dass sie zwei Werte zurückgeben: den Booleschen Wert "Anerkannt" und, falls erkannt, ein AST, der (irgendwie) für den Parser erstellt wurde nichtterminal. (Ein häufiger Hack ist die Rückgabe eines Zeigers, der für "nicht erkannt" ungültig ist oder auf das konstruierte AST verweist, wenn "erkannt"). Die resultierende AST für eine einzelne Prozedur wird erstellt, indem die ASTs aus den von ihr aufgerufenen Unterprozeduren kombiniert werden. Dies ist für Blattprozeduren, die ein Eingabetoken lesen und sofort einen Baum erstellen können, ziemlich trivial.

Der Nachteil dabei ist, dass man den rekursiven Abstieg manuell codieren und mit den Baumbildungsschritten ergänzen muss. Im Großen und Ganzen ist das eigentlich ziemlich einfach für kleine Grammatiken zu programmieren.

Nehmen wir für das Beispiel von OP an, dass wir diese Grammatik haben:

GOAL = ASSIGNMENT 
ASSIGNMENT = LHS '=' RHS ';' 
LHS = IDENTIFIER 
RHS = IDENTIFIER | NUMBER

OK, unser rekursiver Abstiegsparser:

boolean parse_Goal()
{  if parse_Assignement()
   then return true
   else return false
}

boolean parse_Assignment()
{  if not Parse_LHS()
   then return false
   if not Parse_equalsign()
   then throw SyntaxError // because there are no viable alternatives from here
   if not Parse_RHS()
   then throw SyntaxError
   if not Parse_semicolon()
   the throw SyntaxError
   return true
}

boolean parse_LHS()
{  if parse_IDENTIFIER()
   then return true
   else return false
}

boolean parse_RHS()
{  if parse_IDENTIFIER()
   then return true
   if parse_NUMBER()
   then return true
   else return false
}

boolean parse_equalsign()
{  if TestInputAndAdvance("=")  // this can check for token instead
   then return true
   else return false
}

boolean parse_semicolon()
{  if TestInputAndAdvance(";")
   then return true
   else return false
}

boolean parse_IDENTIFIER()
{  if TestInputForIdentifier()
   then return true
   else return false
}

boolean parse_NUMBER()
{  if TestInputForNumber()
   then return true
   else return false
}

Lassen Sie es uns nun überarbeiten und einen abstrakten Syntaxbaum erstellen:

AST* parse_Goal() // note: we choose to return a null pointer for "false"
{  node = parse_Assignment()
   if node != NULL
   then return node
   else return NULL
}

AST* parse_Assignment()
{  LHSnode = Parse_LHS()
   if LHSnode == NULL
   then return NULL
   EqualNode = Parse_equalsign()
   if EqualNode == NULL
   then throw SyntaxError // because there are no viable alternatives from here
   RHSnode = Parse_RHS()
   if RHSnode == NULL
   then throw SyntaxError
   SemicolonNode = Parse_semicolon()
   if SemicolonNode == NULL
   the throw SyntaxError
   return makeASTNode(ASSIGNMENT,LHSNode,RHSNode)
}

AST* parse_LHS()
{  IdentifierNode = parse_IDENTIFIER()
   if node != NULL
   then return IdentifierNode
   else return NULL
}

AST* parse_RHS()
{  RHSnode = parse_IDENTIFIER()
   if RHSnode != null
   then return RHSnode
   RHSnode = parse_NUMBER()
   if RHSnode != null
   then return RHSnode
   else return NULL
}

AST* parse_equalsign()
{  if TestInputAndAdvance("=")  // this can check for token instead
   then return makeASTNode("=")
   else return NULL
}

AST* parse_semicolon()
{  if TestInputAndAdvance(";")
   then return makeASTNode(";")
   else return NULL
}

AST* parse_IDENTIFIER()
{  text = TestInputForIdentifier()
   if text != NULL
   then return makeASTNode("IDENTIFIER",text)
   else return NULL
}

AST* parse_NUMBER()
{  text = TestInputForNumber()
   if text != NULL
   then return makeASTNode("NUMBER",text)
   else return NULL
}

Ich habe einige Details offensichtlich vertuscht, aber ich gehe davon aus, dass der Leser keine Probleme haben wird, sie auszufüllen.

Parser-Generator-Tools wie JavaCC und ANTLR generieren im Grunde rekursive Descent-Parser und verfügen über Funktionen zum Konstruieren von Bäumen, die sehr ähnlich funktionieren.

Parser-Generator-Tools, die Bottom-Up-Parser (YACC, Bison, GLR, ...) erstellen, erstellen auch AST Knoten im gleichen Stil. Es gibt jedoch keine rekursiven Funktionen. Stattdessen wird mit diesen Tools ein Stapel von Tokens verwaltet, die angezeigt und auf Nicht-Endgeräte reduziert werden. Die Knoten AST sind auf einem parallelen Stapel aufgebaut; Wenn eine Reduktion auftritt, werden die AST Knoten auf dem Teil des Stapels, der von der Reduktion abgedeckt wird, kombiniert, um einen nicht-terminalen AST Knoten zu erzeugen, um sie zu ersetzen. Dies geschieht mit "Null-Größe" -Stapelsegmenten für Grammatikregeln, die zu leer sind und dazu führen, dass AST Knoten (normalerweise für "leere Liste" oder "fehlende Option") scheinbar aus dem Nichts erscheinen.

Das Schreiben von Parsern rekursiver Abstammung, die Bäume bauen, ist mit kleinen Sprachen ziemlich praktisch.

Ein Problem mit echten Sprachen (ob alt und altbacken wie COBOL oder heiß und glänzend wie Scala) ist, dass die Anzahl der Grammatikregeln ziemlich groß ist, was durch die Verfeinerung der Sprache und das Beharren auf dem jeweiligen Sprachausschuss, der dafür zuständig ist, erschwert wird Füge ständig neue Extras hinzu, die von anderen Sprachen angeboten werden ("Sprachneid", siehe das evolutionäre Rennen zwischen Java, C # und C++). Wenn man nun einen rekursiven Parser schreibt, gerät dies außer Kontrolle und man tendiert dazu, Parser-Generatoren zu verwenden. Aber auch mit einem Parser-Generator ist das Schreiben des gesamten benutzerdefinierten Codes zum Erstellen von AST - Knoten ein großer Kampf (und wir haben nicht diskutiert, was zum Entwerfen einer guten "abstrakten" Syntax im Vergleich zum Ersten erforderlich ist das fällt mir ein). Die Einhaltung der Grammatikregeln und die AST Erstellung von Goo werden mit zunehmender Skalierbarkeit und ständiger Weiterentwicklung immer schwieriger. (Wenn Ihre Sprache erfolgreich ist, möchten Sie sie innerhalb eines Jahres ändern.) Selbst das Schreiben der AST - Gebäuderegeln ist daher umständlich.

Im Idealfall möchte man nur eine Grammatik schreiben und einen Parser und einen Baum bekommen. Sie können dies mit einigen neueren Parser-Generatoren tun: Unser DMS Software Reengineering Toolkit akzeptiert vollständige kontextfreie Grammatiken und erstellt automatisch einen AST , keine Arbeit seitens des Grammatikingenieurs; Das tun sie seit 1995. Die ANTLR-Leute haben das 2014 endlich herausgefunden, und ANTLR4 bietet jetzt eine solche Option an.

Letzter Punkt: Ein Parser (auch mit einem AST) ist kaum eine Lösung für das eigentliche Problem, das Sie lösen möchten, was auch immer es war. Es ist nur ein Grundstein und sehr zum Schock für die meisten Parser-Neulinge, es ist der kleinste Teil eines Tools, das Code manipuliert. Google meinen Aufsatz über das Leben nach dem Parsen (oder überprüfe meine Biografie) für weitere Details.

94
Ira Baxter

Es ist überhaupt nicht schwer; Tatsächlich ist es eines der einfachsten Dinge, die ich je getan habe. Die allgemeine Idee ist, dass jede Struktur (auch Parser-Regeln genannt) nur eine Liste anderer Strukturen ist. Wenn eine parse () -Funktion aufgerufen wird, durchlaufen sie nur ihre untergeordneten Strukturen und weisen sie an, sie zu analysieren. Dies ist keine Endlosschleife. Token sind Strukturen, und wenn sie mit parse () aufgerufen werden, scannen sie die Lexer-Ausgabe. Sie sollten auch einen Namen zur Identifizierung haben, dies ist jedoch nicht erforderlich. parse () würde normalerweise einen Analysebaum zurückgeben. Durchsuchen Bäume sind wie Strukturen - Listen von Kindern. Es ist auch gut, ein "Text" -Feld und dessen übergeordnete Struktur zur Identifizierung zu haben. Hier ist ein Beispiel (Sie möchten es besser organisieren und den Nullwert für echte Projekte handhaben):

public void Push(ParseTree tree) { // ParseTree
    children.add(tree);
    text += tree.text;
}

public ParseTree parse() { // Structure
    ParseTree tree = new ParseTree(this);
    for(Structure st: children) {
        tree.Push(st.parse());
    }
    return tree;
}

public ParseTree parse() { // Token
    if(!lexer.nextToken() || !matches(lexer.token))
        return null;
    ParseTree tree = new ParseTree(this);
    tree.text = lexer.token;
    return tree;
}

Dort. Rufen Sie die Syntaxanalyse der Hauptstruktur auf (), und Sie erhalten eine AST. Dies ist natürlich ein sehr gutes Beispiel und wird nicht sofort funktionieren. Es ist auch nützlich, "Modifikatoren" zu haben. z.B. Spiel Kind 3 einmal oder mehrmals, Kind 2 ist optional. Das ist auch einfach zu machen; Speichern Sie sie in einem Array, dessen Größe der Anzahl Ihrer untergeordneten Elemente entspricht, und überprüfen Sie dies beim Parsen:

public void setModifier(int id, int mod) {
    mods[id] = mod;
}

public ParseTree parse() {
    ...
    ParseTree t;
    switch(mods[i]) {
        case 1: // Optional
            if((t = st.parse()) != null) tree.Push(t);
        case 2: // Zero or more times
            while((t = st.parse()) != null) tree.Push(t);
        ...
        default:
            tree.Push(st.parse());
    }
    ...
}
1
jv110