TU Wien:Übersetzerbau VU (Ertl, Krall)/Ausarbeitung Vorlesungsprüfung mündlich SS10

Struktur von Compilern

Phasen eines Compilers

Zwei grundlegende Phasen: Analyse und Synthese

Analyse: Syntax des Quellcodes wird überprüft und Struktur ermittelt. Die statische Semantik wird überprüft und ausgewertet. Die statische Semantik umfaßt semantische Eigenschaften des Programms, die zur Übersetzungszeit festliegen (insbesondere Typen von Objekten).

3 Phasen: Lexikalische Analyse, Syntax-Analyse und Semantische Analyse

Synthese: Baut das Zielprogramm auf. Optimierungen und dynamische Kontrollen (z.B. Indexüberprüfung).

3 Phasen: Zwischencode-Erzeugung, Code-Optimierung, Code-Erzeugung

Analyse

Lexikalische Analyse (oder auch Scanner)

Teilt den Quelltext in zusammengehörende Token (z.B. Schlüsselwörter, Zahlen oder Operatoren) und deren Attribut. Der Aufbau von Symbolen kann durch reguläre Ausdrücke exakt spezifiert werden. Zum Erkennen von Symbolen werden endliche Automaten verwendet.

Syntax-Analyse (oder auch Parser)

überprüft ob die von der lexikalischen Analyse gelieferten Token der Grammatik entspricht und bildet einen Ableitungsbaum.

Semantische Analyse

behandelt die Bedeutung von Symbolen (dh Beziehungen zwischen den Symbolen und den von ihnen bezeichneten Objekten zB Konstanten, Variablen). Sie trägt die Art und Typ der von Symbolen bezeichneten Objekte in die Symboltabelle ein. Ihre zentrale Aufgabe ist das type-checking. Attributierte Grammatik ist die Basis für die semantische Analyse. Das Ergebnis der Analyse ist ein attributierter Syntaxbaum.

Synthese

Zwischencode-Erzeugung

Der attributierte Syntaxbaum kann schon als Darstellung des Programms gesehen werden. Bei der Zwischencode-Erzeugung wird der attributierte Syntaxbaum linearisiert. Dh in einem Tiefendurchlauf von links nach rechts abgearbeitet. Insbesondere werden Sprungbefehle erzeugt.<

Code-Optimierung

Bei der Code-Optimierung wird versucht das Programm zu vereinfachen, um Speicherplatz und/oder Laufzeit einzusparen. Dabei unterscheidet man zwischen maschinenunabhängigen und maschinenabhängigen Optimierungen. Beispiel für maschinenunabhängige Optimierung: "Auswertung konstanter Ausdrücke". Bei maschinenabhängige Optimierungen werden spezielle Befehle der Zielmaschine genutzt.

Code-Erzeugung

Bei der Code-Erzeugung wird ein Objektprogramm durch den Assembler generiert, das auf einer realen Maschine ablaufen kann.

Was ist ein abstrakter Syntaxbaum?

if a > 0:
 x = 4

in baumsyntax

Die Blätter sind die Terminale und die Zwischenknoten die Operatoren.

Was ist ein Kellerautomat?

Ein Kellerautomat ist ein endlicher Automat mit einem Kellerspeicher (Stack). (Ein Kellerautomat mit zwei Kellerspeichern ist gleichmächtig zur Turingmaschine)

Die Eingabe wird zeichenweise von links nach rechts verarbeitet. Wenn es möglich ist, wird das Eingabezeichen sofort verarbeitet, wenn nicht, wird es in den Kellerspeicher gelegt und die Bearbeitung sobald wie möglich nachgeholt.

Was sind Kontextbeziehungen?

Der Zusammenhang zwischen Symbolen und den von ihnen bezeichneten Objekten (zB Konstanten, Variablen). Kommt bei der semantischen Analyse type checking) vor.

Was ist ein Binder?

Binder = linker. Wenn es die Möglichkeit gibt, Programme auf verschiedene Module(Dateien) aufzuteilen und getrennt zu übersetzen, übernimmt der Linker das Auflösen der Referenzen und das zusammensetzen der Teil zu einem ausführbaren Programm.

Was sind Vorteile eines Mehr-Pass-Compilers?

Bei einem Ein-Pass-Compiler wird das Quellprogramm in einem Durchlauf übersetzt. Wenn das Quellprogramm vom Compiler mehrfach gelesen wird, spricht man von einem Mehr-Pass-Compiler. Ein-Pass-Compiler sind nur möglich, wenn die Programmiersprache es zuläßt. ZB müssen alle Deklarationen textlich vor ihrer Verwendung stehen. Optimierungen sind nur sehr beschränkt möglich. Beim Mehr-Pass-Compiler können Deklarationen textlich auch nach ihrer Verwendung stehen. Dazu muß der Compiler im ersten Schritt alle Deklarationen analysieren (und in der Symboltabelle speichern) und in der zweiten Phase das Zielprogramm aufbauen.

Vorteil: Optimierungen sind möglich. Deklarationen können nach ihrer textlichen Verwendung stehen. Braucht weniger Hauptspeicher da Pässe nacheinander geladen werden.

Nachteil: Dauert länger, da mehrere Durchläufe.

Computerarchitektur und Assembler

Wie stellt man Strukturen (Arrays (mehrdimensional)) im Speicher dar?

Skriptum S15+16

Was ist der Unterschied zwischen Maschinencode und Assemblercode?

Maschinencode ist quasi die Bitrepräsentation von Assemblercode - also Assemblerbefehl und Operatoren codiert. Und ist daher nur sehr schlecht lesbar. Mit Assamblen und Disassamblern kann der Assamblercode in Maschinencode und zurück transformiert werden.

Was sind Aufrufkonventionen?

"Calling convention" ist die Vereinbarung wie eine Methode aufgerufen wird. Wie Daten (Parameter) einer Funktion übergeben werden, in welchem Register der Rückgabewert einer Funktion zu liegen hat, in welcher Reihenfolge die Parameter auf den Stack gelegt werden, welche Register von der aufgerufenden Funktion zerstört werden dürfen und welche nicht (callee save vs. caller save), ....

Die Konventionen sind so gestaltet, dass jede beliebige Funktion jede andere beliebige Funktion aufrufen kann, ohne viel über diese wissen zu müssen.

Was sind caller(callee)-saved Register?

Register, die entweder von der aufrufenden(caller) bzw aufgerufenen(callee) Funktion gesichert werden müssen. Caller Save Register werden vor dem Funktionsaufruf auf dem Stack gesichert und danach wieder hergestellt. Callee Save Register werden zu Beginn der Funktion am Stack gesichert und am Ende wiederhergestellt.

Beim Callee-saving werden nur die von der aufrufenden Funktion verwendeten und von der aufgerufenen Funktion veränderten Register gespeichert. Im Gegensatz dazu werden beim Caller-Saving alle Register-Inhalte gespeichert, was ein wenig mehr Overhead bzgl Stack-Space und Execution-Time bedeutet, allerdings weniger Programmieraufwand ist.

Lexikalische Analyse

Was sind Grundsymbole (Literale, Bezeichner)?

Grundsymbole werden vom Scanner erkannt. Dabei wird unterschieden zwischen: Keywords (if, then,..), Identifier (Namen für definierte Objekte, Variablen, Funktionen zB i,j), Literale (3.14) und Spezialsymbole (+,-).

Was ist ein regulärer Ausdruck?

ist eine Zeichenkette und beschreibt eine bestimmte Menge von Zeichenketten mit Hilfe bestimmte syntaktischer Regeln. Zu jedem regulären Ausdruck existiert ein endlicher Automat, der dieselbe Sprache akzeptiert.

Was ist der Unterschied zwischen regulärem Ausdruck und regulärer Definition?

Skriptum 3.1 (Seite 24): Reguläre Definitionen dienen zur Benennung und übersichtlichen Schreibweise von Regulären Ausdrücken.
"Drachenbuch":
Wenn $\Sigma$ ein Alphabet mit Basissymbolen ist, dann ist eine reguläre Definition eine Folge von Definitionen der Form
$d_{1}\rightarrow r_{1}$
$d_{2}\rightarrow r_{2}$
$.$
$.$
$.$
$d_{n}\rightarrow r_{n}$

Dabei ist jeweils $d_{i}$ ein eindeutiger Name und jedes $r_{i}$ ein regulärer Ausdruck über den Symbolen aus $\Sigma \cup \lbrace d_{1},d_{2},...,d_{i-1}\rbrace$, d.h. den Basissymbolen und den bis dahin definierten Namen. Die Tatsache, dass $r_{i}$ nur aus Symbolen aus $\Sigma$ un den bisher definierten Namen bestehen kann, erlaubt es, für jedes $r_{i}$ einen regulären Ausdruck über $\Sigma$ dadurch zu konstruieren, dass sämtliche Namen für reguläre Ausdrücke iterativ durch die zugehörigen Ausdrücke ersetzt werden. Würde in $r_{i}$ ein $d_{i}$ vorkommen mit $j>=i$, dann könnte $r_{i}$ unter Umständen rekursiv definiert sein und der Ersetzungsprozeß würde nie terminieren.

TIL Skriptum: Reguläre Definitionen dienen als Zusammenfassung bzw. Abkürzung regulärer Teilausdrücke. Sie erhöhen allerdings nicht die Ausdruckskraft regulärer Ausdrücke sondern dienen lediglich der leichteren lesbarkeit. Es dürfen deswegen durch Verweundung regulärer Definitionen keine direkten oder indirekten Rekursionen entstehen.

Skriptum 3.2 (Seite 25): Bei regulären Definitionen wird jedem Symbol eine Aktionsfolge oder eine Prozedur zugeordnet.

Sonstiges: Eine reguläre Definition gibt einem bestimmten regulären Ausdruck einen Namen, welcher in anderen regulären Ausdrücken verwendet werden kann.

Ausgabe-Aktionen

Bei der Lexikalischen Analyse werden eingelesene Zeichenfolgen auch umcodiert. Typische Ausgabe-Aktionen sind:

• Zurückliefern des Tokens: Token werden zurückgegeben.
• Eintragung in Tabellen: Identifier und Konstanten werden oft in Tabellen gespeichert und müssen einmalig eingetragen werden.
• Behandlung von Wortsymbolen: Falls ein Wortsymbol (if, then, else, ..) erkannt wird, wird das entsprechend Token ausgegeben.
• Ausblenden von Zeichen (Kommentare, Spaces, Tabulator, ..): also keine Ausgabe für Zeichen, die für den Compiler nicht wichtig sind.

Syntax-Analyse

Was ist eine kontextfreie Grammatik?

Auf der linken Seite der Ersetzungsregel steht immer genau ein Nonterminal.

Ist definiert durch das 4-Tupel(N,T,P,S).

• N ist die Menge der Non-Terminal Symbole - können weiter abgeleitet werden
• T ist die Menge der Terminal Symbole - also nicht weiter ableitbare Symbole
• P ist die Menge der Produktionen. Auf der linken Seite steht genau ein Nonterminal, rechts ein Wort (=eine beliebige Folge von Nonterminalen und Terminalen)
• S ist das Startsymbol

Was ist eine Ableitung (Reduktion)?

Eine Ableitung ist die Anwendung von Produktionen auf ein Wort (=eine beliebige Folge von Nonterminalen und Terminalen). Bei der Linksableitung wird jeweils das am weitest links stehende Nonterminal des Wortes durch die rechte Seite einer entsprechenden Produktion ersetzt. Die Reduktion macht genau das Gegenteil: ein Teil eines Wortes, das einer rechten Seiten einer Produktion entspricht wird durch die zugehörigen Non-Terminale ersetzt. Das Ergebnis von Ableitungen bzw Reduktionen kann durch einen Ableitungsbaum (parse tree) dargestellt werden.

Was ist ein Ableitungsbaum (Unterschied zu Syntaxbaum)?

Ein Ableitungsbaum beschreibt die baumförmige Darstellung einer Ableitung. Er beginnt mit dem Startsymbol. Die inneren Knoten sind Non-Terminale und die Blätter Terminal-Symbole. Beim Syntaxbaum fallen die (nicht benötigten) Non-Terminal-Symbole weg.

"Drachenbuch": Ein Syntax-Baum ist eine komprimierte Darstellung eines Parse-Baums, bei dem die Operatoren die inneren Knoten bilden und die Operanden eines Operators die Söhne des Knotens für diesen Operator sind.

Wann sind Grammatiken äquivalent?

Zwei Grammatiken sind äquivalent wenn sie dieselbe Sprache beschreiben.

Dies kann ausgenutzt werden um Grammatiken so umzuformen, dass ungünstige Eigenschaften entfernt werden.

Was sind regular right Part Grammars?

A regular right part grammar (also R R P grammar or R R P G ) G with endmarkers is a 4-tuple (N, T, P, ~-Sq) where N and T are finite sets of nonterminals and terminals, respectively, S in N is the goal symbol, F and -q in T are the left and right endmarkers, FS-~is the goal string, and P is a finite set of productions of the form A --~ w where A , the left part, is in N and w, the right part, is a nontrivial multiple-entry nondeterminis- tic FSM recognizing a subset of (N U T - {F, q})*. A production with left part A (there may be several such productions) is called an A-production. A state in the right part of an A-production is said to be associated with A.

oder

• Verwendung von regulären Ausdrücken auf der rechten Seite von Produktionen
• Umformung in BNF durch auflösen der Rekursionen indem Zusatznonterminale eingefügt werden

Was ist First und Follow?

"First" gibt für eine Grammatik an, mit welchen Terminalsymbolen Satzformen beginnen können. "Follow" gibt für eine Grammatik an, welche Terminalsymbole dem Nonterminal folgen können.

Eine First Menge kann folgendermaßen berechnet werden:

1. Wenn X ein Terminal, dann ist FIRST(X) = {X}

2. Gibt es eine Produktion der Form (X → ε), so füge ε zu FIRST(X) hinzu

3. Gibt es eine Produktion der Form (X → Y1 Y2 . . . Yn ), so füge zunächst FIRST(Y1 ) \ {ε} zu FIRST(X) hinzu. Sollte gelten ε ∈ FIRST(Y1 ), d. h. Y1 lässßt sich zu ε reduzieren, so füge auch FIRST(Y2 ) \ {ε} hinzu. Sollte wiederum Y2 ε-ableitbar sein, fahre wie gehabt fort, bis du auf ein Yi stöt, das nicht ε-ableitbar ist. Sollten alle Yi ε-ableitbar sein, dann (und nur dann) füge auch ε zu FIRST (X) hinzu.

Ein Beispiel:

X → aZ

X → a

Z → ε

Beginnen wir mit der ersten Regel für X: X → aZ. Unter Beachtung der 3. Regel müssen wir First(Y1) == First(a) zu First(X) hinzufügen. First(a) berechnet sich aus der ersten Regel und ist {a}. Da First(a) nicht auf ε ableitbar ist müssen wir das nach a kommende Z laut 3. Regel nicht mehr weiter berücksichtigen. Nun fahren wir fort mit X → a. Daraus kann kein neuer Eintrag für First(X) gewonnen werden. Also weiter mit Z → ε. Hier wird die 2. Regel angeandt. First(Z) = {ε}

Das Endergebnis lautet:

First(X) = {a} First(Z) = {ε}

shift-reduce-Analyse (=Bottom-Up-Analyse)

Es wird mit der gegebenen Grammatik versucht einen Ableitungsbaum für eine gegebene Symbolfolge zu finden. Dabei wird aufsteigend (bottom-up) vorgegangen. Dh vom Eingabewort werden solange Linksreduktionen durchgeführt, bis zum Startsymbol reduziert wurde (oder feststeht, daß das nicht möglich ist). Hat den Vorteil, daß die zugrundeliegende Grammatik auch Linksrekursionen und gleiche Anfänge enthalten kann.

Tabellen der LR-Analyse

Bei der LR-Analyse gibt es die Analysetabellen, Action- und Goto-Tabellen. Die Analysetabellen wird durch Zustände (Zeilen) und Grammatiksymbole (Spalten) indiziert. Sie beinhalten Aktionen (action-Tabelle) bzw Folgezustände (goto-Tabelle).

Mögliche Aktionen sind: shift (Eingabesymbol auf den Stack), reduce p (Produktion p reduzieren), accept (korrektes Ende), error (fehlerhaftes Ende)

Jede Zeile der goto-Tabelle entspricht einem Zustand repräsentiert durch eine Item-Menge (Item = Produktion, deren rechte Seite um eine Marke erweitert ist).

Für die Generierung der Action-Tabelle werden die First- und Follow-Mengen der Grammatiksymbole und die goto-Tabelle benötigt.

Was ist ein zulassiges Präfix?

Eine Folge von Anfangssymbolen einer Satzform, die rechts nicht über den Ansatz hinausgeht, heißt zulässiges Präfix. Dh sie steht zur gänze im Keller (Skriptum Seite 35, Skriptum 2012/13 Seite 62 oben).

Ist LR(2) mächtiger als LR(1)?

LR-Grammatik = Analyse von Links nach Rechts mittels Rechtsableitung (=Linksreduktion) Eine LR-Grammatik mit Vorausschau 1 ist genauso mächtig wie solche mit mehr Vorausschau, da jede Sprache, die mit einer LR(k) Grammatik beschrieben werden kann, auch mit LR(1) beschrieben werden kann. Es kann aber in manchen Fällen von Vorteil sein, eine LR(k) mit k >= 2 Grammatik zu verwenden, da damit einfachere Syntaxanalysetabellen erstellt werden. Die gleiche Tabelle mit LR(1) erstellt kann unter Umständen sehr viel komplexer sein.

Was macht man bei Mehrdeutigkeiten?

Es werden Zusatzregeln definiert. Bei A + A * A zb, daß die Operatoren + und * linksassoziativ sind und * höhere Priorität als + hat.

Hierarchie der Analyse-Verfahren

Mächtigkeit: kontextfrei > LR(1) > LALR(1) > SLR(1) > LR(0)

Mächtigere Verfahren können komplexere Grammatiken verarbeiten. Die weniger mächtigen Verfahren erzeugen uU Doppeleinträge (=Shift/Reduce oder Reduce/Reduce Konflikte) beim Aufbau der Tabellen, die mächtigere Verfahren noch eindeutig behandeln können.

Syntaxgesteuerte Übersetzung

Was ist eine attributierte Grammatik (synthetisierte/ererbte Attribute)?

Eine attributierte Grammatik ist eine kontextfreie Grammatik mit folgenden Erweiterungen:

• Jedem Grammatiksymbol können Attribute zugenordnet werden (synthetisierte oder vererbte).
• Jeder Produktion können Regeln zugenordnet werden.

A->X

b=f(c1,c2,..)

b ist ein synthetisiertes Attribut des Symbols A der linken Seite oder ein vererbtes Attribut des Symbols X der rechten Seite. c1,.. sind ererbte Attribute des Symbols der linken Seite oder synthetisierte Attribute der Symbole der rechten Seite.

Abhängigkeitsgraph (bei der Attributauswertung)

Skriptum S.50+51

Symboltabelle

In einer Symboltabelle werden alle im Quellprogramm deklarierten Objekte und deren Typen gesammelt.

Codeerzeugung

Was bedeutet Befehlsauswahl, Befehlsanordnung, Registerbelegung?

Befehlsauswahl: Die Operationen der Zwischendarstellung werden zu Befehlen der Zielmaschine zusammengefasst. Der Datenflußgraph wird in Bäume aufgeteilt, die Maschinenbefehlen entsprechen.

Befehlsanordnung: Die Befehle werden im Hinblick auf eine schnelle Ausführung auf Pipeline- oder superskalaren Prozessoren angeordnet.

Registerbelegung: Die während der früheren Phasen verwendeten Pseudoregister werden durch Maschinenregister ersetzt.

Was ist ein Datenflussgraph?

Ein Datenflussgraph ist ein gerichteter Graph, dessen Knoten Instruktionen darstellen. Die Kanten zwischen den Knoten beschreiben die zugrunde liegenden Datenabhängigkeiten.

Was ist eine Baumgrammatik?

Auf der rechten Seite der Produktion stehen Bäume anstatt Terminale bzw Nonterminale. Wird bei der Codeerzeugung verwendet.

Dürfen Baumgrammatiken mehrdeutig sein?

Ja, Baumgrammatiken dürfen mehrdeutig sein. Es sollte allerdings die Möglichkeit mit der optimalen Ausführungszeit und/oder Speicherverbrauch ausgewählt werden. Dafür werden bei jeder Regel noch die Kosten (also Ausführungszeit oder Platzbedarf) hinzugefügt.

Was sind Kettenregeln?

Eine Regel der Form Nonterminal1->Nonterminal2 führt zur Schwierigkeiten bei der Berechnung der Kosten, da auf die Kosten eines Nonterminals desselben Teilbaums zurückgegriffen wird, der eventuell noch nicht vollständig berechnet ist.

Ist die Befehlsauswahl für Bäume (DAGs) optimal?

DAG = Directed Acyclic Graph (gerichteter azyklischer graph) Für Bäume gibt es optimale Verfahren für die Befehlsauswahl. Für gerichtete azyklische Graphen nicht.

Literatur

• Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullmann. Compilerbau Teil 1. Oldenbourg. 2. Auflage (1999) ISBN 3-486-25294-1