Seminar Übersetzung künstlicher Sprachen im SS 2009 Marco A. Castillo Syntaxgerichtete Übersetzung und Typüberprüfung Sommersemester 2009

Seminar Übersetzung künstlicher Sprachen im SS 2009

Marco A. Castillo

Syntaxgerichtete Übersetzung und Typüberprüfung

Sommersemester 2009

2Seminar Übersetzung künstlicher Sprachen im SS 2009

Agenda

Motivation und Einordnung

Syntaxgerichtete ÜbersetzungSyntaxgerichtete Definition

Auswertungsreihenfolge für syntaxgerichtete Definition

Verfahren zur syntaxgerichteten Übersetzung

Implementierung von L-attributierter syntaxgerichteten Definition

TypüberprüfungDynamische und statische Überprüfung

Typsysteme

Regeln für die Typüberprüfung

Fazit


Motivation und Einordnung

Von der Quellsprache zur Zielmaschine


Syntaxgerichtete Übersetzung

Syntaxdefinition

Kontextfreie Grammatik

Beschreibung der hierarchischen Struktur einer Programmiersprache

if (Ausdruck) Anweisung else Anweisung

stmt → if (expr) stmt else stmt

Syntaxgerichtete Definition

Kontextfreie Grammatik

Grammatiksymbole + Attributen

Produktionen + Semantikregeln

Produktion

E → E1 + T

Semantikregel

E.code = E1.code|| T.code||‘+‘



Attribute in Grammatiken



Syntaxgerichtete Definition eines einfachen Taschenrechners



Kommentierter Parse-Baum für 3*5+4


Auswertungsreihenfolge für syntaxgerichtete Definitionen

AbhängigkeitsgraphInformationsfluss zwischen den Attributinstanzen

Kanten drücken die durch Semantikregeln auferlegten Einschränkungen aus

Abhängigkeitsgraph

Informationsfluss zwischen den Attributinstanzen

Kanten drücken die durch Semantikregeln auferlegten Einschränkungen aus



S-attributierte Definition• Alle Attribute sind synthetisiert • Abhängigkeitsgraph mit zirkulären Bezügen wird nicht

zugelassen • Auswertungsreihenfolge garantiert • Auswertung durch Botton Up Reihenfolge

postorder (N) {

for (jedes Kind C von N von links aus) postorder (C);

fasse Attribute von/mit N zusammen;}



L-attributierte Definition• Zwischen den mit der Produktion verbundenen Attritbuten

verlaufen die Kanten im Abhängigkeitsgraphen nur von links nach rechts

• Attribute sind synthetisiert oder vererbt (eingeschränkt) • Vererbte Attribute sind mit dem Regelkopf verbunden • Auswertung durch eine Top Down Reihenfolge

dfvisit (N) { for (jeden Nachfolger M von N von links nach rechts)

werte ererbte Attribute aus;dfvisit (M);

werte die synthetisierten Attribute von N aus; }


Anwendung der syntaxgerichtete Übersetzung

Syntaxbaum

Verdichteter Parse-Baum

Jeder Knoten eines Syntaxbaums stellt ein Konstrukt dar

Die Kinder des Knotens repräsentieren die sinnvollen Komponente des Konstrukts

Zwischendarstellung


Syntaxgerichtete Übersetzungsschemata

Ergänzende Notation zur syntaxgerichteten Definition

Kontextfreie Grammatik mit Programmfragmenten, die in die Produktionsrümpfe eingebettet sind

Programmfragmente (semantische Aktionen) können an jeder Stelle eines Produktionsrumpfes erscheinen

Auswertungsreihenfolge der semantischen Regeln durch Position gegeben

Aktionen werden mit {..} eingeschlossen

Verfahren zur syntaxgerichteten Übersetzung

Ergänzende Notation zur syntaxgerichteten Definition

Kontextfreie Grammatik mit Programmfragmenten die in die Produktionsrümpfe eingebettet sind

Programmfragmente (semantische Aktionen) können an jeder Stelle eines Produktionsrumpfes erscheinen.

Auswertungsreihenfolge der semantischen Regeln durch Position gegeben

Aktionen werden mit {..} eingeschlossen

rest → + term {printf (‚+‘}; rest 1



Ausdrücke in Infix-Notation (9-5)+2 oder 9-(5+2)

Ausdrücke in Postfix-Notation 9 5 – 5 + oder 9 5 2 + -



S

( 9 – 5) + 2



(9 – 5) + 2



(9 – 5) + 2

99 5 9 5 –9 5 – 2 9 5 – 2 +


Implementierung von L-attributierten syntaxgerichteten Definitionen

Übersetzung beim Durchlaufen eines Parse-BaumesAufbauen und Kommentieren des Parse-Baumes

Aufbauen des Parse-Baumes, Hinzufügen von Aktionen und Ausführen der Aktionen in Postorder

Übersetzung während des ParsernsVerwenden eines rekursiven absteigenden Parsers

Generieren von Code im laufenden Betrieb

Implementieren einer syntaxgerichteten Übersetzung zusammen mit einem LL-Parser

Implementieren einer syntaxgerichteten Übersetzung zusammen mit einem LR-Parser

Übersetzung beim Durchlaufen eines Parse-BaumesAufbauen und Kommentieren des Parse-Baumes

Aufbauen des Parse-Baumes, Hinzufügen von Aktionen und Ausführen der Aktionen in Postorder

Übersetzung während des ParsernsVerwenden eines rekursiven absteigenden Parsers

Generieren von Code im laufenden Betrieb

Implementieren einer syntaxgerichteten Übersetzung zusammen mit einem LL-ParserImplementieren einer syntaxgerichteten Übersetzung zusammen mit einem LR-Parser



L-attributierte syntaxgerichtete (LL-Grammatik)

Aktionen in den Produktionen eingebettet

Übersetzung während der LL-Syntaxanalyse

L-attributierte syntaxgerichtete Definitionen und LL-Syntaxanalyse

L-attributierte syntaxgerichtete (LL-Grammatik)

Aktionen in den Produktionen eingebettet

Übersetzung während der LL-Syntaxanalyse

• Aktionsdatensatz: • Enthält einen Zeiger auf ausführbaren Code (meist Auswertung

von ererbten Attributen)• Synthetisierungsdatensatz:

• Enthält Anweisungen zur Synthese von Attributen und Aktionen (kopieren der synthetisierten Attribute in andere Datensätze weiter unten im Stack)


Dynamische und statische Überprüfung

Wir unterscheiden zwischen

Statischen Überprüfung (während der Kompilierung)

Dynamischen Überprüfung (zur Laufzeit)

Statische Überprüfung

Typüberprüfung

Überprüfung der Kontrollflusses

Überprüfung auf Eindeutigkeit

Auf Namen bezogene Überprüfung

Dynamische Überprüfung

Dynamische Typüberprüfung ist erforderlich, wenn der Typ von Variablen und Objekten nur zur Laufzeit bestimmt werden kann


TypüberprüfungWas wird überprüft?

Ob Operatoren und Operanden kompatibel sind

Welche Programmelemente haben einen Typ?

Konstanten

Variablen

Ausdrücke

Parameter

Welche Attribute werden durch Typen festgelegt?

Werte von Konstanten

Wertebereiche / Operationen für Variable, Ausdrücke, Parameter

Übergabemechanismus für Parameter

Verwendung von Informationen über Typen

Ermittlung des Speicherbedarf

Erzeugung von Code für die Umwandlung von einem Typ in einen anderen

Ermittlung des Resultatttyps


Typüberprüfung - Beispiele

x div y → x, y müssen vom Typ integer sein.

array [INDEX] of …. → INDEX muss Ordnungstyp sein.

procedure p(formal_1: Typ_1, var formal 2: Typ 2);

……

p (aktuell_1, aktuell_2);- aktuell_1 mit formal_1 verträglich?- aktuell_2 mit formal_2 verträglich?- aktuell_2 muss eine Variable sein.


Typsysteme Was ist ein Typsystem?

Ein Typsystem für eine Programmiersprache ist eine Menge von Regeln, die die korrekte Verwendung von Typen im Kontext bestimmen.

Für bestimmte Konstrukte muss der Typ gegeben sein (Definition) und für andere kann der Typ aus der Struktur bestimmt werden.

Ein Typsystem heißt stark, wenn alle möglichen statischen Typkonflikte zur Übersetzungszeit erkannt werden können.

Ein Typsystem besteht aus gewissen Basistypen (Typnamen) und Konstruktoren, mit denen neue Typen aus vorhandenen konstruiert werden können.

Mit den Konstruktoren werden Typausdrücke gebildet


Typüberprüfung von Ausdrücke


Typüberprüfung von Anweisung


Fazit

Der allgemeine Ansatz für die syntaxgerichtete Übersetzung besteht darin, einen Parser- oder Syntaxbaum zu konstruieren und dann die Werte der Attribute an dem Knoten des Baumes zu berechnen, indem diese Knoten aufgesucht werden.

Zwei Notationen möglich

Syntaxgerichtete Definition. Sie verbergen viele Implementierungsdetails und befreien den Benutzer von der expliziten Spezifikation der Reihenfolge, in der die Übersetzung stattfindet

Übersetzungsschemata legen die Reihenfolge fest, in der die semantischen Regeln auszuwerten sind, daher erlauben sie es, einige Implementierungsdetails zu zeigen.


Fazit


Fazit

TypüberprüfungWichtig, um mögliche Programmfehler fest zu stellen

Statische und dynamische Überprüfung

if <complex test> the 5 else <type error>


Backup-Folien



Syntaxgerichtete Übersetzung für while-Anweisungen

L-attributierte syntaxgerichtete Definitionen und LL-Syntaxanalyse

Syntaxgerichtete Übersetzung für while-Anweisungen


Backup-Folien

Attribut Auswertung


Backup-Folien

Attributierte LR – Grammatik für Ausdrücke (Infix → Postfix)


Backup-Folien

Attributierte LL – Grammatik für Ausdrücke (Infix → Postfix)


Backup-Folien


Backup-Folien

Typ-Ausdrücke


Backup-Folien

Grafische Darstellung von Typausdrücke


Backup-Folien

Syntaxgesteuerte Überprüfung von Typen


Backup-Folien

Übersetzungsschema für Deklarationen


Backup-Folien

Übersetzungsschema für Anweisungen


Backup-Folien

Äquivalenz von Typen


Backup – Folien

Überprüfung der strukturellen Äquivalenz


Backup – Folien

Namensäquivalenz


Backup – Folien

Strukturäquivalenz


Backup-Folien

Ererbte Attribute - Typdeklarationen


Backup-Folien


Backup-Folien

Wie kommt man zu einen Übersetzungsschema

Documents

Seminar Übersetzung künstlicher Sprachen im SS 2009 Marco A. Castillo Syntaxgerichtete Übersetzung und Typüberprüfung Sommersemester 2009