TU Wien:Weiterführender Übersetzerbau VO (Krall)/Stoffzusammenfassung SS10

Vorwort

Dies ist eine Zusammenfassung des Weiterführenden Übersetzerbau Skriptums von Manfred Backhaus, Anton Ertl und Andreas Krall aus dem SS2010.

Grundlagen

Compiler

Ein Compiler ist ein Programm das Programme einer Quellsprache in eine Zielsprache übersetzen kann und dabei in seiner Implementierungssprache geschrieben ist. Ein Compiler kann auch in einger Generatorsprache geschrieben sein, die routinearbeiten abnimmt. Das theorätische Modell dazu ist die attributierte Grammatik. Der Syntax der zu übersetzenden Sprache wird durch eine Kontextfrei Grammtik definiert.

Interpreter

Ein Interpreter führt Programm aus die in seiner Interpretersrpache geschrieben sind. Er wird auch als abstrakte oder virtuelle Maschine bezeichnet.

Im Unterschied zum Compiler bietet der Interpreter Vorteile bei Programmen die große Auswahlen beinhalten oft geändert wird, ein Compilier bietet vorteile bei Programmen die Schleifen enthalten oder das Programm kaum geändert und oft ausgeführt wird.

Just-in-time Compiler kompliliert das Programm zur laufzeit.

Compiler-Interpreter

Eine Kombination aus Compiler und Interpreter bietet einige Vorteile. Dabei wird das Programm aus eine beliebigen Sprache mit einem Compiler in die Interpretersprache übersetzt und anschließend vom Interpreter ausgeführt. Die Interpretersprache ist debei meißt schneller zu interprieren als bei einem reinem Interpreter außerdem ist die Sprache von allen unnötigen Sourcecodeteilen bereinigt und komprimiert. Damit kann ein einmal übersetzes Programm auf verschiedenen Maschinen laufen dazu muss nur ein Interpreter für die jeweligen Maschine zur verfügung stehen. Auch der Compiler kann in der Interpretersprache verfasst sein.

Computerarchitektur und Assembler

Seicher

Der Speicher besteht aus 8bit Bytes von denen jedes eine eigene Adresse hat. Die Daten im Speicher können beliebig interpretiert werden (Befehel, Zahl, Zeichen, ...).

Datenstruktur

Arrays sind im speicher direkt hintereinander angeordner jedes Feld kann mit einem Offset von der Startadresse aus bereichnet werden.

Strukturen liegen ebenfalls direkt hintereindander und werden über einen offset der sich aus der größer der vorherigen Elemente in der Struktur und möglichwiese einem Padding(Zwischenraum) berechnen.

Verschachtelte Strukturen werden von außen nach innen aufgelöst, der Offset ist dabei der Speicherbefarf der inneren Objekte.

Register

Der Prozessor verfügt über einen sehr schnellen aber kleinen Speicher, die Register. Viele Befehle können nur mit mind einem Register arbeiten, somit muss zwischen Speicher und Register kopiert werden.

Daten im Speicher können über zwei Arten angesrochen werden direkt über die Adresse (movq $100, $rax) oder indirekt über die Adresse die dynamisch berechnet wird oder in einem anderen Speicher oder Register steht (movq (%rdi), %rax).

Maschinencode

Maschinencode sind befehle codiert als Bitmuster. Mittels Assambler oder Dissassambler kann zwischen Maschinen- und Assemblecode transformiert werden.

Befehle (siehe AMD64-Assembler-Handbuch )

Die meißten Systeme haben großteils die gleichen Befehle. Oft dient dabei ein Operand sowohl als Quelle wie auch als Ziel.

Adressen können über ein einfaches System zur laufzeit berechnet werden. o(r1,r2,f) Dabei ist o der Offset, R1 und R2 ein Register und f ein Multiplikator der 1,2,4 oder 8 sein kann. Die Adresse berechnet sich dann so: o + r1 + r2*f

Auf diese Adresse kan entweder mit movq 12(%rdi), %rax direkt zugegriffen werden, oder mit leaq kann die Adresse(nicht die Daten an der Adresse) in ein Register gespeichert werden.

Für eine Übersicht der Befehle siehe das AMD64-Assembler-Handbuch.

Funktionen

Aufrufkonventionen legen fest wie ein Unterprogramm aufzurufen ist, und welches Programm (Aufrufende, Caller oder Aufgerufne Callee) sich um sicherung der Register und Adresszeiger kümmern muss, sowie in welchen Registern die Übergabeparamter oder der Rückgabewert stehen.

Dabei Teilen sich die Register in Callee und Caller Saved Register. Callee Saved Register müssen vom Aufgerufenen Programm meißt auf den Stack gesichert werden bevor sie verändert werden. Bei Caller Saves Register übernimmt dies das Aufrufende Programm, wenn der Inhalt der Register auch später noch benöigt wird.

Struktur von Complilern

Phasen

Der Comiler teilt sich grundlegend in die Analyse und die Synthese Phase.

Die Analyse überprüft den Syntax des Quellpropgramms und ermittelt seine Struktur und überprüft die statische Semantik (zB Typen).

Die Synthese baut das Zielprogramm auf, mit besonderem Augenmerk auf optimierung und dynamischen Kontrollen.

Die Phasen lassen sich noch genauer unterteilen:

• Lexikalische Analyse (bilden von Token, Scanner, reguläre Asdrücke, endlicher Automat)
• Syntax Analyse (kontextfreie Grammatik, Parser, Ableitungsbaum, Kellerautomat, Syntaxbaum)
• Semantische Analyse (attributierte Grammatik, Symboltabelle, Typ Überprüfung, )
• Zwischencodeerzeugung(Prefix, Postfix, 4-Tupel-Code, Liniarisierung)
• Code Optimierung( maschinen abhängig und unabhängig, Schleifen, Konstante Ausdrücke, ...)
• Codeerzeugung (Registerbelegung)

Binder(Linker) und Lader(loader) verbinden einzelen Programmteile und machen daraus ein ausführbares Programm.

Das Laufzeitsystem wird benötigt um die Speicherverwaltung oder ähnliches durchzuführen. Das Programm greift auf Funktionen der Laufzeitumgebung, des Betriebssystems sowie der Hardware zu.

Ablaufsteuerung

Man kann Compiler in Ein-Pass und Mehr-Pass-Compiler unterteilen. Bei Ein-Pass-Compilern kann das Programm in einem Pass verzahnt zwischen den Phasen übersetzt werden. Das ist nur bei Programmen möglich, bei denen Deklarationen vor ihrer Verwendung stehen müssen. Ist das nicht der Fall muss das Programm mindesten in zwei Schritten übersetzt werden. Ein Ein-Pass-Compiler wird von der Syntaxanalyse gesteuert. Heutige Compiler auch der aus der Übung sind eine Mischform.

Lexikalische Analyse

Grundsymbole

• Wortsymbole(keywords) if, then, while, ...
• Bezeichner(identifier) funkt1, var1, i, ...
• Literale(literlas) 3.14, 7, 0x55, ...
• Spezialsymbole (delimiter) =, +, *, ...

Symbole werden durch reguläre Ausdrücke identifiziert. Reguläre Definitionen dienen zur bennenung von regulären Ausdrücken.

Zum erkennen von Symbolen werden endliche Automaten verwendet. Diese können als Zustanddiagramm oder als Zustandsmatrix dargestellt werden Die meißten Scanner-Generatoren erzeugen zuerst einen nicht deterministischen Automaten und wandeln diesen anschließend in einen deterministischen endlichen Automaten um:

• Im ersten Schritt wird jede Reguläre Definition rekursiv duch die dazugehörogen regulären Ausdrücke ersetzt
• Dann werden die regulären Ausdrücke durch einen NFA dargestellt (ersetzt)
• Umformung des NFA in einen DFA. Dabei wird vom Startzustand ausgegenagen und alle möglichen Folgezustände für ein Eingabezeichen des NFA bilden einen neuen Zustand im DFA.

Von den neuen Zuständen werden wieder alle mögliche Folgezustände für ein Eingabezeichen zu einem neuen Zustand zusammen gefasst. Dies wird solange wiederhohlt bis kein neuer Zustand mehr dazu kommt. Jeder neue Zustand der einen Endzustand vom NFA enthällt ist auch im DFA ein Endzustand.

• Minimierung des DFA. Dabei werden Zustände die mit den gleichen Eingabezeichen zu einem Endwort führen zusammengefasst.

Ausgabe-Aktionen

Ausgabe-Aktionen meinen das weitergeben der eingelesenen Symbole bzw Tokens für die weiteren Phasen. Dabei kommt es zu einigen Üblichen Aktionen:

• Zurückliefern des Tokens - Für jedes Token wird ein int Wert oder eine andere eindeutige Kennzeichnung zurückgeliefert.
• Eintragen in Tabellen - Bezeichner und Taballen werden oft um Speicher zu sparen in Tabellen eingetragen und anschließend die Refernz auf den Eintrag zurückgeliefert
• Behandlung von Wortsymbolen - Wortymbole (if, else, ...) werden entweder in eigenen Tabellen eintragen oder am Anfang der Bezeichner Tabelle gepseichert.
• Ausblenden von Zeichen - aller Zeichen die im weiteren Verlauf nicht mehr gebraucht werden (Leerzeichen, Zeilenumbrüche, ...) werden nicht weiter gegeben und somit ausgeblendet.

Analyse Verfahren

Die Analyse soll immer die am längsten Mögliche Zeichenfolge erkennen. Gibt es für eine Zeichnfolge ein eindeutiges Endsymbol kann mit diesem beendet werden. Gibt es dieses jedoch nicht (wie bei Zahlen), muss immer ein weiteres Zeichen zusätzlich eingelesen werden, das wenn es nicht mehr in den Regulären Ausdruck passt die Zeichnfolge beendet. Entweder man schreibt dieses Zeichen anschließend wieder zurück oder man ließt von anfang an ein Zeichen vorraus ein.

Man unerscheidet zwischen:

• Tabellengesteuerter Analyse - dabei gibt es einen Algorithmuss der in der Zustandmatrix der Tabelle nachsieht welcher Status als nächster erreicht wird.
• Ausprogammieren des Automaten - Dabei wird der Automat durch eine Funktion abgebildet die je nach dem ersten Zeichen durch eine Switch die richtigen Token auswählt und

die weiteren Verzweigungen und schleifen im Automaten durch if, for, while abbildet.

Syntax Analyse

Grundlagen

Die Syntax von Programmen wird durch die kontextfreie Grammatik (Grammatiken die in den linken Teil der Produktionen nur ein Nonterminal haben) beschrieben. Die Grammatik besteht aus Terminalen, Nonterminalen, Produktionen und einem Startsymbol. Ein Wort beseht aus Terminalen und Nonterminalen. Bei der Ableitung wird ein Nonterminal durch die in der Produktion definierten rechten Seite ersetzt. Bei der Linksableitung wird immer das am linkesten stehende Nonterminal ersetzt, umgekehrt bei der Rechtsableitung. Reduktion ist umgekehrt zur Ableitung eine Gruppe von Terminal und Nonterminalen wird durch das Nonterminal auf der linken Seite einer Produktion ersetzt. Bei der Linksreduktion wird zuerst mit links begonnen.

Eine Satzform ist ein Wort das vom Startsymbol aus ableitbar ist. Ein Satz ist eine Satzform die nur aus Terminalen besteht (zB ein Programm). Die Sprache ist die Menga aller Sätze (zB die Programmiersprache).

Grammatiken sind äquivalent wenn sie die selbe Sprache beschreiben.

RRPG - Regular Right Part Grammars

Dabei wird der Syntax der Programmiersprache durch Reguläre Asdrücke beschrieben. Auf der rechten Seite von Produktionen stehen reguläre Ausdrücke. Diese können dadurch aufgelöst werden, dass neu Nonterminal eingeführt werden und mit diesen Rekursionen gebildet werden.

Für Ausdrücke sollte darauf geachtet werden, dass die richtige Art der Rekursion verwendet wird, zB rechts oder linksrekursion bei Operatoren " + - + ". Jedoch ist zB bei Listen nur die Endreihenfolge relevant (die Elemente werden durch Trenner getrennt) und daher die Art der Rekusion nicht von bedeutung (doppelt, links, rechts, restlisten, alternierende-Rekursion, regüläre Schreibweise).

Diese Grammatiken die die Sprachen beschreiben werden auch dazu benutzt um die Sprachen zu analysieren, und somit festzustellen ob ein Wort in der Sprache enthalten ist oder nicht. Realisert wird dies durch Kellerautomaten.

Um diese Analyse durchzuführen werden zwei Funktionen benötigt die Mengen von Terminalsymbolen zurück geben:

• First(alpha) - gibt die Menge der Terminale mit welchen die aus alpha ableitbaren Satzformen beginnen können
• Follow(alpha) - gibt die Menga der Terminale an die einem Nonterminal in einer beliebigen Satzform folgen können

Top Down Analyse

Ein wird versucht einen Ableitungsbaum mittels einer gegebenen Grammatik für die Eingabesymbole zu finden. Dabei werden absteigend vom Startsymbol weg solange Linksableitungen ausgeführt bis alle Zeichen(Token) eingelesen wurden oder gestgestellt wurde, das nicht abgeleitet werden kann.

Man unterscheidet zwei Verfahren (ähnlich den Analyse Verfahren):

• Tabellengesteuert

Es gibt einen Kontrollalgorithmus, Jeder weitere Schritt wird duch eine Tabelle bestimmt. Als Eingabe wird das obersetste Kellersymbol und das vorderste Eingabesymbol(Token) betrachtet. Der Keller beginnt nur mit dem Startsymbold er Grammatik (und einem Endsymbol der kennzeichnet das der Keller leer ist). Steht im Keller ein Nonterminal wird es aus dem Keller gelesen (POP) und zu dem Nonterminal und dem Eingabsymbol wird der Eintrag in der Tabelle gesucht. Anschließend wird die Produktion, die sich im Feld der Tabelle befindet in umgekehrter Reihenfolge in den Keller gelegt. Wird vom Keller ein Terminal gelesen, muss das derzeitige Eingabesymbol das selbe Terminal sein. Wird vom Keller das Endzeichen gelesen, muss auch das Ende der Eingabesymbole erreicht sein.

Um die Tabelle zu füllen werden First und Follow benötigt, siehe Algorithmuss 5.15

• Rekursiver Abstieg

Bei dieser Methode wird für jedes Nonterminal eine Funktion gebildet. RRP Grammatiken lassen sich einfahc mit dieser Mehtode zu Parsen ausprogrammieren, da Wiederhohlungen durch schleifen ersetzt werden können.

Es können aber nicht alle Grammatiken mit diesen Mehtoden behandelt werden.

LL(1) Grammatiken

LL(1) Grammatik nennt man eine Grammatik die in der oben gennanten Top-Down Tabelle keine Mehrfacheinträg hat. (von Links nach Rechts mittels Linksableitung und einer Vorschau in der Eingabe von einem Symbol)

• alle First(alpha) müssen paarweise die Vereinigung {} haben
• höchstens ein alpha lässt sich nach epsilon ableiten
• Lässt einer der Alternativen eines Nonterminals zum Leerwort ableiten, so darf keine der anderen Alternativen mit einem Element aus Follow(N) anfangen

Wird die Top Down Analyse mit einer nicht LL(1) Grammatik durchgeführt kann es vorkommen das nicht klar is welche Produktion angewendet werden soll. Lösungsmöglichkeiten sind:

• Vorrausschauen um ein weiteres Eingabesymbol - LL(2)
• Verwendung Semantischer Information
• Rücksetzen im Kontroll-Algorithmus

Die Mehtode des Rekursiven Abstiegs kann mit Backtracking erweitert werden. Dabei wird der Keller auch zum speichern des bisherigen Ableitungsbaums verwendet. Damit können alle möglichen Ableitungen untersucht werden.

Bestimme nicht LL(1) Grammatiken können in LL(1) umgewandelt werden:

• Linksfaktorisierung - gleiche Anfänge von Alternativen von Nonterminalen werden herausgehoben und ein neuen Nonterminal eingeführt
• Linksrekursion - Linksrekursive Grammatiken sind für TopDown Analysen nicht geeignet, können aber Umgewandelt werden: A->Aa|b => A->bB B->aB|e

Ein Fehler muss nicht immer da liegen wo er erkannt wird. Die einfachste Fehlerbehandlung ist der Abbruch mit einer Möglichst genauen Fehlermeldung.

Bottom-Up-Analyse

Im gegensatz zur Top-Down-Analyse wird hier aufsteigend vorgegangen. Es werden so lange Linksreduktionen durchgeführt bis das Startsymbol erreicht ist. Oder erkannt wird das dies nicht möglich ist. Der Vorteil ist, das die Grammatiken auch Linkrekursionen und Alternativen mit gleichen Anfängen enthalten dürfen.

Wird auch shift-reduce Analyse genannt. Das Schieben eines Eingabesymbols in den Keller und das Reduzieren der obersten Kellersymbole, die der rechten Seite der Produktion entsprechten sind die wesentlich Aktionen dabei. Im Keller des Automaten stehen die abgeleiteten Grammatiksymbole.

LR-Grammatiken (Analyse von Links mittels Rechtsableitung). LR(1) sind immer genauso mächtig wie LR(k). LR-Grammmatiken können alle deterministisch analysierbaren Sprachen beschreiben.

Bei der LR-Analyse wird wieder ein gleichbeleibender Kontrollalgoritmus verwendet der mit Tabellen arbeitet. Folgend geht es um das Simple LR SLR(1) Verfahren.

Die Aktionen in den Tabellen sind:

• shift(Eingabesymbol in den Keller schieben)
• reduce p (reduziere um die Anzahl p)
• accept
• error

Es gibt zwei Tabllen:

• goto-Tabelle

Jede Zeile der Tabelle entspricht einem Zustand (Representiert durch eine Itemmenge, ein Item ist ein Produktion deren rechte Seite um die Marke "." erweitert ist, die Marke trennt Keller und Eingabefolge ). Die Spalten sind Nonterminale und in den Zellen stehen die neuen Zustände.

• action-Tabelle.

Die action Tabelle wird mit Hilfe der goto-Tabelle sowie der Follow und der First Menge erzeugt. Die Zeilen sind ie Zustände, die Spalten die Eingabesymbole und in den Feldern stehen shift, reduce, accept und error.

Durch Mehrdeutige Grammatiken enstehen bei LR-Methoden Mehrfacheintrage in den action-Tabellen. Mehrdeutige Grammatiken können mit Zusatzregeln eindeutig gemacht werden. Ein YACC werden solche Konflikte automatisch aufgelöst, bei reduce/reduce Konflikten (nicht klar mit welcher Prozedur zu reduzieren ist) bleider der frühere Eintrag bestehn, bei shift/reduce Konflikten (kann entweder sofort Reduziert werden oder zuerst ein Eingabesymbol verbraucht werden) wird der reduce Eintrag gestrichen.

LALR(1) ist ein Verfahren bei dem Zustände mit gleichen Items zusammengefasst werden. Der Parser verhällt sich wie der Ursprüungliche LR(1) Parser arbeitet aber effizienter.

LR(1) ist mächtiger als LALR(1) ist mächtiger als SLR(1)

Um so mächtiger um so mehr Grammatiken können sie verarabeiten. LR(1) Parser können auch LL(1) Grammatiken behandeln.

Wie schreibt man Grammatiken

• Finden von wichtigen Teilen des Programms, diesen werden Nonterminale zugeordnet
• Suchen von Beziehungen zwischen den Kategorien, Beziehungen werden durch Grammatikregeln beschrieben
• festlegen des konkreten Syntax (Reihenfolge der Symbole auf der rechten Seite, zusätzliche Terminalsymbole, ...)

Syntaxgesteuerte Übersetzung

Die Methoden beruhen auf Attributierter Grammatik. Da die Berechnung an die Grammatik bebunden ist, handelt es sich um Syntaxgesteuerte Übersetzung.

Attributierte Grammatik

Die attributierte Grammatik ist ein kontexfrei Grammatik mit den Erweiterungen, dass jedem Symbol Attribute zugeordnet werden können und jeder Produktion Regeln zugeordnet werden können.

Man unterscheidet zwischen ererbten Attributen, synthetisierten Atributen. Ererbete Attribute werden von anderen Symbolen an dieses weitergereicht und synthetisierte Attribute werden bei diesem Symbol erzeugt oder aus anderen Attributen zusammengesetzt.

Wie attributiert man Grammatiken

• Erzeugung von semantischen Kategorien
• Zuordnung von semantischen zu syntaktischen Kategorien
• Bestimmen der Attributauswertungsregeln

Die durch eine attributierte Grammatik spezifizierte Übersetzung kann man exemplarisch durch einen attributierten Ableitungsbam darstellen

Qualitätskriterien für die Attributierung

• Die Attributierung soll einfach und natürlich formuliert sein.
• die Attributierung muss vollständig sein
• die Attributierung muss zyklenfrei sein

S-Attributierte Grammatik

Wenn eine attributierte Grammatik nur syntetisierte Attribute enhällt heißt sie S-Attributierte Grammatik.

L-Attributierte Grammatik

Wenn alle Attribute in einem einzigen links-rechts Tiefendurchlauf berechnet werden können, nennt man die Grammatik L-Attributierte Grammatik (LAG, LAG(1)) In Produktionen dürfen ererbete Attribute nur von Attributen von Symbolen abhängen die links davon stehen.

Jede s Attributierte Grammatik ist auch L Attributierte Grammatik.

Übersetzungsschema

Eine L-Attributierte Grammatik kann man als Übersetzungsschema schreiben. Dabei werden die Regeln jeder Produktion, geordnet und so in die rechte Seite der Produktion eingesetzt, dass sie beim Tiefendurchlauf des Ableitungsbaums von links nach rechts ausgeführt werden können. Aus einem Übersetzungsschema kann sehr einfach ein Compiler generiert werden.

Top-Down-Compiler-Generator

Aus jedem Übersetzungschema, das auf einer LL-Grammatik basiert kann ein Ein-Pass-Top-Down-Compiler erzeugt werden.

• Für jedes Nonterminal wird eine Funktion erzeugt, eingabeparamter sind die ererbeten Attribute, Rückgabewert die Syntetisierten Attribute
• Für jedes Symbol der Rechten seite werden Aktionen durchgeführt
  • Terminal - Wertzuweisung bei syntetisierten Attributen
  • Nonterminal - Aufruf der richtigen Funktion
  • Aktionen - Aktion wird ausgeführt

Bottom-Up-Compiler-Generator

Aus einem Übersetzungschema auf Basis einer LR-Grammatik kann problemlos ein Bottom-Up-Compiler konstruiert werden, wenn die Grammatik S-attributiert ist. Syntetisierte Attribute werden in einem Attributkeller gespeichert.

Bei ererbten Attributen muss vorher die Grammatik transformiert werden, dabei stehen die ererbten Attribute unmittelbar vor dem Nonterminal und die syntetisierten am ende. Bei so eine Transformierung kann die LR-Eigenschaft verlohren gehen und es zu problem beim Parser kommen.

Ein-Pass-Übersetzung

Vorraussetung ist ien L-attributierte Grammatik (LAG) die entweder auf diner LL-Grammatik basiert (LLAG) oder auf eienr transformierten LR-Grammatik (LRAG).

Klassen für Ein-Pass-Übersetung ( Bottom Up kann LRAG und LLAG in einem Pass übersetzen)

• LAG
• LRAG Bottom Up
• LLAG Top Down

Mehrpass-Übersetzung

Ist die Ein Pass Übersetung nicht möglich wird ein Syntaxbaum generiert der beliebig durchlaufen werden kann um die Attribute zu generieren

zwei effiziente Methoden

• Pass-oriteniert - der Baum wird durchlaufen und immer die Attribute brechnet deren Abhängikeiten schon bekannt sind, bis alle Attribute berechnet wurden
• Visit-orientiert - der Baum wird nach den Attributabhängigkeiten durchlaufen, dazu wird zB für jedes Nonterminal eine eigen Auswertfunktion generiert

Semantische Analyse

Die wesentlich Aufgabe der Semantische Analyse ist die Typ-Überprüfung. Zentrale Datenstruktur für die Semantische Analyse ist die Symboltabelle. Semantische Analysen sollen die statische korrektheit des Programms sicherstellen.

Typen

Man unterscheidet zwischen staischen und dynamischen Typsystemen, statisch zur übersetzungzeit, dynamsich zur laufzeit. Ein Typ kann formal durch einen Typ-Ausdruck beschrieben werden. In vielen Sprachen können Namen für eingen Typen definiert werden. Man muss festellen welche Typen equivalent sind, dabei unterscheidet man zwei arten:

• Struktur Äquivalenz
• Namen Äquivalenz

Symboltabelle

Die Namen und Typen aller im Programm definierten Objekte werden in der Symboltabelle gesammelt. Typen können durch Zeigen auf einen Typbaum dargestellt werden. Die Symboltabelle ist ein Attribut in der attributierten Grammatik. Bei der Symboltabelle muss auf den Gültikeitsbereicht der Objekte geachtet werden.

Typüberprüfung

Die Typüberprüfung bezieht sich nur auf Ausdrücke. Man kann sagen die Typüberprüfung berechent die Typen der Ausdrücke. Dabei werden die Typen der Ausdrücke und Teilausdrücke in den Baum gepseicht und bei Operatorn auf korrektheit geprüft. Im Fehlerfall wird eine Meldung ausgegeben.

Typ-Konversion

Man untescheidet zwischen expliziter (wird im Programm angegeben) oder implizierter (addition von float mit int) Konversion. Typ-Überprüfungen und Operator Identifizierung können in den meisten Programmiersprachen in einem Durchlauf des Ausdrucksbaum mit inem sythetisiertem Attribut erfolgen, wenn der Ergebnisstyp eindeutig nur von den Operadentypen bestimmt wird.

Overloading

Ein Operand führt verschiedene Funktionen für verschiedene Typen durch.

Zwischendarstellung

Nach der Syntax und Semantischen Analyse kann das Programm prinzipiell Interpretiert werden. Die Dartellung eins Programms in diesem Stadium bezeichnet man als Zwischendartellunge. Eingige Bespiele: Syntaxbaum (Operatorbaum), Postfix- und Prefix-Code, Quadrupel-Cide

Syntaxbaum

Darstellung als Baum, jeder Knoten bestimmt eine Operation deren Operanden die anhängenden Teilbäume sind.