WikiDer > Attribut Grammatik

EIN Attributgrammatik ist ein formale Methode zur Angabe von Struktureigenschaften von a Programmiersprache bis zum Produktionsregeln von a kontextfreie Grammatik durch Regeln zur (kontextsensitiven) Struktur der Sprache ergänzt werden.

Attributgrammatiken können verwendet werden, um strukturelle Eigenschaften einer Sprache zu spezifizieren, die in einer Sprache, wenn überhaupt, schwierig sind. kontextfreie Grammatik aufgestellt werden kann. Beispiele sind die Anforderungen, die eine Sprache an die Verwendung verschiedener Sprachen stellt Datentypen in Ausdrücken und die Anforderung, dass a Variable muss vor der Verwendung deklariert werden.

Syntaxgerichtete Übersetzung und verzierte Syntaxbäume

Attributgrammatiken sind eine Formalisierung des Prinzips von Syntaxgerichtete Übersetzung. Bei der Syntax-gerichteten Übersetzung ist die Terminal- und Nichtterminalsymbole einer kontextfreien Grammatik eine oder mehrere Attribute (Eigenschaften) zugewiesen. zusätzlich Produktionsregeln der Grammatik um Regeln erweitert, um diese Attribute zu berechnen. Das Ergebnis ist ein Syntaxgerichtete Definition erwähnt und seine Verwendung Syntaxgerichtete Übersetzung.

Es analysieren eines Eingabetextes unter Verwendung einer Grammatik ergibt a Syntaxbaum auf. Das Knoten in diesem Baum entsprechen Produktionsregeln aus der Grammatik. Bei der Syntax-gesteuerten Übersetzung verwenden wir diese Knoten als Datensätze, in denen ein oder mehrere Attribute gespeichert werden können. Durch Durchlaufen des Syntaxbaums in der richtigen Reihenfolge und Ausführen der Attributregeln der Produktionsregel, die diesem Knoten für jeden Knoten entspricht, werden alle Attribute in den Knoten ausgefüllt. Ein solcher Syntaxbaum, in dem zusätzliche Informationen in den Knoten gespeichert sind, heißt a dekorierter Syntaxbaum oder kommentierter Syntaxbaum erwähnt.

Wenn die Zeilen in einer Syntax-gerichteten Definition nicht Nebenwirkungen es gibt eine Attributgrammatik.

Obwohl bei der Umsetzung Programmiersprachen Wenn nicht immer eine formale, explizit formulierte Attributgrammatik verwendet wird, wird das zugrunde liegende Prinzip der Syntax-gesteuerten Übersetzung in fast allen Compiler benutzt.

Beispiel

Nehmen wir als Beispiel eine Attributgrammatik für einfache arithmetische Ausdrücke wie "(3 6)*2". Die folgende Grammatik beschreibt die erlaubten Ausdrücke:

ausdrücken ::= Ausdr' ' Begriff | Ausdruck '-' Term | Begriff Begriff ::= Term '*' Faktor | Term '/' Faktor | Faktor Faktor ::= '('Ausdruck')' | ganze Zahl

Wir erstellen eine Attributgrammatik, die den Wert gültiger Ausdrücke berechnet. Dazu verbinden wir mit allen nicht-terminalen Symbolen ein symbolen Wert-Attribut, das den numerischen Wert des Teils des Ausdrucks enthält, der durch dieses nicht-terminale Symbol dargestellt wird. Für alle Produktionsregeln geben wir an, wie der Wert, der dem nicht-terminalen Symbol links zugeordnet ist, aus den Werten der Symbole rechts abgeleitet werden kann. Der Einfachheit halber nummerieren wir die Teile von Produktionsregeln wo nötig, schreiben sie komplett aus und fügen ein Startsymbol mit einer entsprechenden Produktionsregel hinzu.

Das Ergebnis eines Ausdrucks kann nun berechnet werden, indem man einen Syntaxbaum von unten nach oben (von den Blättern bis zur Wurzel) durchläuft und jedes Mal, wenn wir zu einem Knoten kommen, die entsprechende Zeile verwenden, um das Attribut zu berechnen und im Knoten auf zu treffen . Wenn wir alle Knoten haben, von denen der letzte die Wurzel ist (die Wurzel entspricht in unserer Beispielgrammatik immer der Start-Produktion), dann enthält die Wurzel das Ergebnis der Berechnung.

Obwohl es ziemlich umständlich ist, den Wert von Ausdrücken auf diese Weise anzugeben, kann dies eine Reihe von Vorteilen haben. Wir haben jetzt einen Ausgangspunkt für den Entwurf eines Programms, das das Ergebnis dieser Arten von Ausdrücken berechnen kann. Wenn wir bereits einen Parser haben, der gültige Ausdrücke erkennen kann, können wir ihn auch die Berechnung übernehmen lassen. Dazu fügen wir an jeder Stelle, an der der Parser eine Produktionsregel „erkennt“, den Code ein, der die entsprechende Attributregel ausführt. Wenn wir noch keinen Parser haben, können wir a Parser-Generator. Bei den meisten Parser-Generatoren können Sie Aktionen angeben: Fragmente von Programmcode, die einer bestimmten Produktionsregel zugeordnet sind und ausgeführt werden, wenn diese Produktionsregel verwendet wird. Wir müssen dann nur noch die Attributregeln in der obigen Attributgrammatik in gültigen Code umwandeln und können sie dann als Aktionen in die Grammatik einfügen. Der Parser-Generator erzeugt dann ein Programm, das Ausdrücke nicht nur erkennt, sondern auch verarbeiten kann.

Derivative, zusammengesetzte und intrinsische Attribute

Wir können die in einer Attributgrammatik verwendeten Attribute in drei Typen unterteilen:

Compound (normalerweise mit dem englischen Begriff synthetisiert angegeben)

Bei zusammengesetzten Attributen wird der Wert des Attributs des Nichtterminalsymbols auf der linken Seite einer Produktionslinie durch die Attribute des Terminalsymbols und der Nichtterminalsymbole auf der rechten Seite der Produktion bestimmt. Dies bedeutet, dass in einem Syntaxbaum der Wert dieses Attributs in einem Knoten durch die Werte dieses Attributs in den Kindern dieses Knotens bestimmt wird. Diese Attribute bewegen sich sozusagen nach oben in Richtung der Wurzel des Syntaxbaums. Die Blätter des Syntaxbaums haben keine zusammengesetzten Attribute. In unserem Beispiel, der Attributgrammatik für die obigen Ausdrücke, sind alle Attribute zusammengesetzt (außer dem Wertattribut des Terminalsymbols ganze Zahl).

Abgeleitet (normalerweise mit dem englischen Begriff vererbt angegeben)

Bei einem abgeleiteten Attribut hängt der Wert des Attributs in einem Knoten des Syntaxbaums vom Wert der Attribute in Knoten ab, die keine Kindknoten des Knotens sind, sondern beispielsweise Eltern- oder Nachbarknoten. Die Informationen in abgeleiteten Attributen wandern also im Syntaxbaum sozusagen nach unten oder seitwärts.

intrinsisch

Intrinsische Attribute werden nicht von anderen Attributen abgeleitet. Der Wert dieser Attribute kommt „von außen“. In unserem obigen Beispiel gilt dies für die letzte Produktion (Faktor → Integer). Das 'Wert'-Attribut des nicht-terminalen Symbols Faktor wird nicht von einem anderen Attribut abgeleitet, sondern kommt von außen über die hypothetische Konstruktion string_to_int(integer.text), die wir gewählt haben, um anzuzeigen, dass wir den Text, den der Scanner als ganze Zahl erkennt, in die richtige Zahl umwandeln.

Zusammengesetzte Attribute sind in der Praxis am häufigsten. Eine Attributgrammatik, die wie unser obiges Beispiel nur aus zusammengesetzten und intrinsischen Attributen besteht, heißt a S-attributierte Grammatik erwähnt. Mit einer solchen S-attributierten Grammatik lassen sich alle Attribute in einem Syntaxbaum berechnen, indem man die Knoten von unten nach oben anklickt (Prost) herstellen. Bei Grammatiken, die nicht S-attributiert sind und daher auch abgeleitete Attribute haben, ist die Reihenfolge, in der die Knoten verarbeitet werden können, meist weniger klar. In manchen Fällen gibt es möglicherweise nicht einmal eine sinnvolle Reihenfolge, beispielsweise wenn das Attribut eines oder mehrerer Knoten direkt oder indirekt von sich selbst abhängt, wodurch ein Kreis entsteht.

Siehe auch

• Van Wijngaarden-Grammatik