WikiDer > Syntaxbaum
EIN Syntaxbaum ist ein Baumstruktur die als Zwischenschritt bei der Umwandlung eines Codestücks in a . verwendet wird Datenstruktur. Es gibt zwei Arten: die Konkreter Syntaxbaum und der abstrakter Syntaxbaum.
Ort
Ein Benutzer einer Programmiersprache schreibt einen Code, der von allen anderen Benutzern der Programmiersprache gelesen werden kann. Der Computer kann den Code in dieser Form nicht ausführen. Der Code muss in eine für den Computer lesbare Form umgewandelt werden. Beim Konvertieren des Codes in a Datenstruktur, das besser für die Computerverarbeitung geeignet ist, verwendet a lexikalischer Analysator und ein Parser. Nach der Verarbeitung durch den lexikalischen Analysator und den Parser wird der Code in a Baumstruktur. Diese Baumstruktur wird als Syntaxbaum bezeichnet und dann weiter in eine Datenstruktur umgewandelt.
Der lexikalische Analysator durchsucht den Text nach Bedeutungseinheiten wie Zahlen, Variablen und Elementen, die zur Programmiersprache gehören (zum Beispiel das Element the Klasse). Der Parser prüft, ob diese Einheiten den Regeln der kontextfreien Grammatik entsprechen (diese Grammatik oder Syntax wird als kontextfrei bezeichnet, da sie von bestimmten Elementen einer Programmiersprache unabhängig ist). Wenn dies der Fall ist, wird ein Syntaxbaum gemäß einer Liste kontextfreier Referenzen erstellt.
Aufbau des Syntaxbaums
So funktioniert es: Immer wenn ein Element identifiziert wird, wird der Parser Taste create mit dem Wert oder Namen dieses Elements und optional a Elterntaste enthält den Typ dieses Elements. Dann sucht der Parser dieses Element in der Liste und folgt der Referenz. Das Ergebnis der Referenz wird ein neuer Elternknoten. Letztendlich ist die Referenz gleich der Wurzel des Baumes, nämlich Ausdruck. Dieser Vorgang wird wiederholt, bis alle Elemente des Codes verarbeitet wurden.
Zwei Arten von Syntaxbäumen
Es gibt zwei Arten von Syntaxbäumen, den konkreten Syntaxbaum und den abstrakten Syntaxbaum. Der abstrakte Syntaxbaum ist aus zwei Gründen eine Verbesserung des konkreten Syntaxbaums.
- Im abstrakten Syntaxbaum werden implizit bereits im konkreten Syntaxbaum enthaltene Informationen weggelassen. Ein Beispiel hierfür ist das Weglassen von Klammern um eine Operation. Aber auch überflüssige Elemente wie Kommentare oder Elemente aus dem Layout wie Leerzeichen oder das Zeichen ';' am Ende jeder Zeile werden weggelassen.
- Bei einem abstrakten Syntaxbaum kann die Liste der kontextfreien Referenzen so modifiziert werden, dass der Syntaxbaum kleiner wird. Nicht alle Referenzen führen zur Erstellung eines neuen Knotens. Dies geschieht durch Eingabe Konstrukteure.
Beispiel
Sehen wir uns ein Beispiel für den Aufbau eines abstrakten Syntaxbaums für den Ausdruck an: (a b) × 1
Wir verwenden diese Liste kontextfreier Referenzen:
| ICH WÜRDE | → | Var {cons("Var")} |
| Var | → | Exp |
| IntConst | → | Exp {cons("Int")} |
| Exp "x" Exp | → | Exp {cons("x")} |
| Exp " " Exp | → | Exp {cons(" ")} |
| Exp "-" Exp | → | Exp {Nachteile("-")} |
| Exp "=" Exp | → | Exp {cons("Eq")} |
| Exp ">" Exp | → | Exp {cons("Gt")} |
| "("Exp")" | → | Exp |
Die Variablen a und b sind vom Typ Bezeichner (Id) und die Referenz Id → Var ruft den Konstruktor Var ({cons(“Var“)}) auf, der einen Knoten namens „Var“ erzeugt. Die Zahl 1 ist vom Typ IntConst und die Referenz IntConst → Exp ruft den Konstruktor Int ({const(“Int”)}) auf, der einen Knoten namens „Int“ erzeugt. Für die Operationen und × werden auch Knoten erstellt, die jeweils mit der Art der Operation benannt sind.
Die letzte Referenz zeigt, dass Klammern keinen zusätzlichen Knoten erzeugen, da es keinen Konstruktor gibt, ein Merkmal des abstrakten Syntaxbaums.
Unten ist der abstrakte Syntaxbaum für den Ausdruck angegeben: (a b) × 1
_×_1.jpg)