#LyX 1.3 created this file. For more info see http://www.lyx.org/
\lyxformat 221
\textclass article
\begin_preamble
\usepackage{hyperref}
\hypersetup {
   pdftex=true,
   hyperindex=true,
   colorlinks=true,
   bookmarks=true,
   bookmarksnumbered=false,
   pdfpagemode=None,
   bookmarksopen=false,
   pdftitle=Vorlesungsmodul Praktische Mathematik,
   pdfauthor=Matthias Ansorg,
   pdfcreator=pdfTeX (Web2C 7.3.1) 3.14159-0.13d,
   pdfstartview=FitBH
}
\renewcommand\familydefault{\sfdefault}
\end_preamble
\language german
\inputencoding auto
\fontscheme default
\graphics default
\paperfontsize default
\spacing single 
\papersize a4paper
\paperpackage a4
\use_geometry 1
\use_amsmath 1
\use_natbib 0
\use_numerical_citations 0
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language danish
\quotes_times 2
\papercolumns 1
\papersides 1
\paperpagestyle default

\layout Title

Vorlesungsmodul Compilerbau
\newline 
- VorlMod Comp -
\layout Author

Matthias Ansorg
\layout Date

20.
 März 2003 bis 
\begin_inset ERT
status Collapsed

\layout Standard

\backslash 
today
\end_inset 


\layout Abstract

Studentische Mitschrift zur Vorlesung Compilerbau bei Prof.
 Dr.
 Michael Jäger (Wintersemester 2004/2005) im Studiengang Informatik an der
 Fachhochschule Gießen-Friedberg.
 Die mündliche Diplomprüfung kann häufig Grundlagenfragen wie »Was ist ein
 Compiler?« enthalten.
\begin_deeper 
\layout Itemize


\series bold 
Bezugsquelle:
\series default 
 Die vorliegende studentische Mitschrift steht im Internet zum Download
 bereit
\begin_inset LatexCommand \url[Persönliche Homepage Matthias Ansorg]{http://matthias.ansorgs.de/InformatikDiplom/Modul.Comp.Jaeger/Comp.pdf}

\end_inset 

.
\layout Itemize


\series bold 
Lizenz:
\series default 
 Diese studentische Mitschrift ist public domain, darf also ohne Einschränkungen
 oder Quellenangabe für jeden beliebigen Zweck benutzt werden, kommerziell
 und nichtkommerziell; jedoch enthält sie keinerlei Garantien für Richtigkeit
 oder Eignung oder sonst irgendetwas, weder explizit noch implizit.
 Das Risiko der Nutzung dieser studentischen Mitschrift liegt allein beim
 Nutzer selbst.
 Einschränkend sind außerdem die Urheberrechte der angegebenen Quellen zu
 beachten.
\layout Itemize


\series bold 
Korrekturen und Feedback:
\series default 
 Fehler zur Verbesserung in zukünftigen Versionen, sonstige Verbesserungsvorschl
äge und Wünsche bitte dem Autor per e-mail mitteilen: Matthias Ansorg <
\begin_inset LatexCommand \url{mailto:matthias@ansorgs.de}

\end_inset 

>.
 
\layout Itemize


\series bold 
Format:
\series default 
 Die vorliegende studentische Mitschrift wurde mit dem Programm LyX (graphisches
 Frontend zu 
\begin_inset ERT
status Collapsed

\layout Standard

\backslash 
LaTeX
\end_inset 

) unter Linux geschrieben und mit pdf
\begin_inset ERT
status Collapsed

\layout Standard

\backslash 
LaTeX
\end_inset 

 als pdf-Datei erstellt.
 Grafiken wurden mit dem Programm xfig unter Linux erstellt und als pdf-Dateien
 exportiert.
\layout Itemize


\series bold 
Dozent:
\series default 
 Prof.
 Dr.
 Michael Jäger.
\layout Itemize


\series bold 
Verwendete Quellen:
\series default 
 <quelle> {<quelle>}.
\layout Itemize


\series bold 
Klausur:
\begin_deeper 
\layout Itemize

Die Klausur orientiert sich nicht mehr an den (eher leichten) Klausuren
 der vorigen Jahre.
\layout Itemize

Bisher durften in den Klasuren bei Prof.
 Dr.
 Jäger keine Unterlagen oder sonstigen Hilfsmittel verwendet werden.
\layout Itemize

Die Klausur wird nach den Semesterferien gechrieben.
\end_deeper 
\end_deeper 
\layout Standard


\begin_inset LatexCommand \tableofcontents{}

\end_inset 


\layout Section

Organisation
\layout Standard

Im Wintersemester 2004/2005:
\layout Itemize

Hausübungen dürfen wie die Bonuaufgaben zu zweit gelöst werden.
\layout Itemize

Man kann sich nach Belieben eine Praktikumsgruppe aussuchen.
 Das Praktikum wird auf den Sun-Workstations durchgeführt.
\layout Itemize

Zur Entwicklung des SPL-Compilers enötigt man etliche Beratung.
 Es gibt deshalb auch Tutoren.
\layout Itemize

Im Praktikum werden C++, flex (lex-kompatibler Scannergenerator) und bison
 (yacc-kompatibler Compilergenerator) als Werkzeuge verwendet.
 yacc ist der Compilergenerator, die zum Industriestandard geworden ist.
 Unter Windows können die freien Versionen von 
\begin_inset LatexCommand \url{http://www.cygwin.com}

\end_inset 

 verwendet werden, unter Linux sind flex und bison standardmäßig verfügbar.
\layout Itemize

Voraussetzung für die Klausurteilnahme: 2 Hausübungen, die fristgerecht,
 formgerecht und korrekt abgeliefert werden müssen.
 Im Somersemester 2004 wurde eine semesterbegleitende Prüfung durchgeführt
 (SPL-Compiler als praktischer Prüfungsteil).
 Das hat sich nicht bewährt und wurde für das Wintersemester 2004/2005 wieder
 ausgesetzt.
\layout Itemize

Die Hausübungen sind nicht vergleichbar mit dem, was in den letzten Semestern
 gefordert wurde.
 Es sind kleine Ausschnitte des SPL
\begin_inset Foot
collapsed true

\layout Standard

straightline programming language
\end_inset 

-Compilers zu schreiben.
 Sie dienen nur dazu, die Studenten dazu zu bringen, am Praktikum dranzubleiben.
\layout Itemize

Die Teilnahmevoraussetzungen zur Klausur sind also niedrig, die Klausur
 wird jedoch schwer.
 Aus diesem Grund sollte möglichst jeder auch Bonuspunkte sammeln.
 
\layout Itemize

Die Bonusaufgaben (und gleichzeitig Aufgabenstellungen für die Übungen)
 bestehen darin, den kompletten SPL-Compiler zu schreiben.
 Sie sind zerlegt in möglichst unabhängige Teilaufgaben und können einzeln
 oder zu zweit gelöst werden (es gibt keine Ausnahmen).
\begin_deeper 
\layout Itemize

Die Aufgabenstellung ist minimalistisch: SPL ist eine sehr einfache Sprache,
 der Maschinencode wird für eine virtuelle Maschine (ECO32) erzeugt.
 ECO32 ist sehr stark an die MIPS-Architektur angelegt, es ist für den Compilerb
auer die einfachste vorstellbare Architektur, weil sie hauptsächlich mit
 Registern arbeitet.
\layout Itemize

Die Entwicklung des kompletten SPL-Compilers ist sehr zeitaufwändig
\layout Itemize

Es gibt Klausuraufgaben, etwa die manuelle Generierung von Maschinencode,
 die man beim ECO32 Compiler lernt, die man in der Klausur benötigt.
\end_deeper 
\layout Itemize

Näheres wird bei Ausgabe der Hausübungen und Bonusaufgaben bekanntgegeben.
\layout Itemize

Es wird wiederum das MOS-System zur Überprüfung der Ähnlichkeit von Code
 verwendet.
 Entwickelt am MIT, ein Plagiat-Erkennungssystem.
 Wer Code von anderen Gruppen kopiert, desse Lösung wird nicht gewertet.
 Durch das Programm MOS vom MIT können solche Strukturähnlichkeiten von
 Code erkannt werden.
 Es wurde auch schon von Prof.
 Geisse in der Veranstaltung Compilerbau im WS 2003/2004 eingesetzt.
\layout Itemize

Nur im letzten Drittel der Lehrveranstaltung, wenn es um die Codegenerierung
 geht, wird der Simulator ECO32 benötigt.
\layout Itemize

Alle Modalitäten zur Veranstaltung Compilerbau stehen auch auf der Internetseite
 von Prof.
 Jäger.
\layout Itemize

SPL-Compiler: Dabei wird ein Großteil der Lösung als Codegerüst vorgegeben,
 das ergänzt werden muss.
 
\layout Itemize

Auch in den Compilerbau-Veranstaltungen bei Prof.
 Geisse wurde ein SPL-Compiler programmiert.
 Die Unterschiede zur Veranstaltung von Prof.
 Jäger bestehen in der Menge des vorgegebenen Codes und der Bewertung von
 Teillösungen.
\layout Itemize

Die Teilnahme an den Praktika ist keine Prüfungsvoraussetzung, nur die Abgabe
 der Hausübungen.
\layout Section

Einführung
\layout Standard

Die Semantik von Programmen, d.i.
 die Wirkung von Programmen, kann formal beschrieben werden, z.B.
 mit denotationaler Semantik.
 Dazu werden Funktionen höherer Ordnung verwendet.
 Alternativ kann die Semantik formal operational beschrieben werden (als
 Verhalten einer einfachen virtuellen Maschine) oder algebraisch.
 In dieser Veranstaltung wird die Semantik informal beschrieben: als Beschreibun
g des Verhaltens von Programmen.
 Damit lassen sich natürlich keine Interpreter automatisch generieren wie
 etwa bei denotationaler Semantik.
 Man beachte, dass hier stets die Semantik der Programmiersprache gemeint
 ist, nicht die Semantik eines speziellen zu übersetzenden Programms in
 dieser Programmiersprache.
 Über letztere hat der Compiler keinerlei Kenntnis, er verarbeitet zu compiliere
nde Programme ja einfach mechanisch.
\layout Standard

Es gibt keinen Bereich in der Informatik, der so gut erforscht und dokumentiert
 wäre wie der Compilerbau.
 Der Prozess der Compilerentwicklung ist dadurch quasi standardisiert.
 Es gibt viele und gute Algorithmen auf diesem Gebiet, die auch theoretisch
 gut fundiert sind durch Theorien der Automaten und formalen Sprachen.
 Außerdem gibt es viel gute Literatur.
\layout Subsection

Lernziele
\layout Enumerate

Informatiker nutzen Compiler und sollten eine ungefähre Vorstellung von
 der Funktionsweise eines Compilers haben.
\layout Enumerate

Informatiker entwickeln Compiler.
\layout Enumerate

Compilerbau-Algorithmen werden auch überall dort eingesetzt, wo strukturierte
 Eingabetexte zu verarbeiten sind, etwa bei HTML und XML-Parsern.
\layout Enumerate

Vertiefte Kenntnis der grundlegenden Konzepte hinter Programmiersprachen,
 um andere Sprachen in kurzer Zeit erlernen zu können.
\layout Subsection

Inhalt
\layout Enumerate

Architektur eines Compilers
\layout Enumerate

Programmiersprachen-Konzepte
\layout Enumerate

Formale Beschreibungsmethoden von Programmiersprachen.
 Es werden zwar keine Methoden zur formalen Beschreibung der Semantik besprochen
, sondern Methoden zur Strukturerkennung.
\begin_deeper 
\layout Itemize

reguläre Ausdrücke (Muster zur Beschreibung von Wortmengen).
 Werden verwendet zur Erkennung von Tokens (Grundbausteine der Programme,
 Syntax).
 Tokens könnten auch mit Grammatik beschrieben werden, jedoch sind reguläre
 Ausdrücke nötig, um einen schnellen Compiler zu bauen.
\layout Itemize

Grammatik in EBNF.
 Werden verwendet zur Beschreibung, wie hierachische Konstrukte aus Tokens
 korrekt aufgebaut werden.
\end_deeper 
\layout Enumerate

Implementierung eines Scanners, der mit regulären Ausdrücken verschiedene
 Tokens erkennt, d.h.
 die lexikalische Analyse durchführt.
\layout Enumerate

Implementierung eines Parsers (der die Syntaxanalyse durchführt).
 Dazu gibt es zwei völlig unterschiedliche Klassen von Parser-Algorithmen:
\begin_deeper 
\layout Itemize

Bottom-up Algorithmen.
 In dieser Veranstaltung wird der Quellcode eines Bottom-up Parsers mit
 bison aus einer Grammatik erzeugt.
\layout Itemize

Top-down Parser.
 Ein solcher Top-down Parser wird in dieser Veranstaltung implementiert,
 weil es einfacher und schneller geht als bei Bottom-up Parsern.
\end_deeper 
\layout Enumerate

Kennenlernen von yacc bzw.
 bison (Parsergeneratoren)
\layout Enumerate

Kennenlernen von lex und flex (Scannergeneratoren)
\layout Enumerate

semantische Analyse: Typberechnungen und interne Repräsentation von Typen
 im Compiler.
 Typprüfungen sind recht komplex, weil es benutzerdefinierte hierachisch
 gegliederte Typen geben kann.
\layout Enumerate

syntaxorientierte Übersetzung.
 Das bedeutet, die Syntaxspezifikation enthält neben der eiegntlichen Grammatik
 auch weitere Aktionen, die der Compiler durchzuführen hat (Codererzeugung,
 Typprüfungen usw.).
 Es gibt dazu zwei Ansätze, die miteinander kombiniert werden, nämlich attributi
erte Grammatiken und Übersetzungsschemata.
 Durch diese weiteren Aktionen ist es möglich, mit yacc nicht nur einen
 reinen Parser, sondern tatsächlich einen vollständigen Compiler zu erzeugen.
\layout Enumerate

Einführung in die Codegenerierung.
 Die Erzeugung von Maschinencode geschieht am vereinfachten Modell einer
 MIPS-RISC-Architektur.
 Codeerzeugung für RISC-Maschinen ist wesentlich einfacher als für CISC-Maschine
n.
\layout Subsection

Anwendungen von Compilerbautechniken
\layout Itemize

Compiler.
 Ein Compiler ist ein Programm, das einen Quelltext aus einer höheren Programmie
rsprache in ein Maschinenprogramm (oder in Assembler) übersetzt.
\layout Itemize

Interpretierer.
 Ein Interpretierer interpretiert den Quelltext selbst statt ihn in Maschinencod
e zu übersetzten, der dann vom Prozessor ausgeführt würde.
 Java wird dagegen zuerst compiliert (in Maschinencode einer virtuellen
 Maschine, den Java-Bytecode) und der Java-Bytecode dann interpretiert durch
 die Java Virtual Machine.
\layout Itemize

Struktur-Editor.
 Ein Editor für strukturierte Texte, der die Struktur der zu erstellenden
 Texte kennt und entsprechende Unterstützung bietet wie etwa Syntax-Highlighting.
\layout Itemize

WWW-Browser.
 Er enthält einen Parser, der ganz entsprechend einem Parser für Compiler
 gebaut ist.
\layout Itemize

Programme für Text-Markup-Sprachen: XML, SGML, 
\begin_inset ERT
status Collapsed

\layout Standard

\backslash 
LaTeX
\end_inset 

.
\layout Itemize

SQL-Optimierer, der aus SQL-statements einen datenbankspezifischen Zugriffsplan
 erzeugt.
\layout Itemize

Reverse Engineering.
 Viele Firmen betreiben riesige Mengen an COBOL-Programmen, die schlecht
 dokumentiert sind und deren Programmierer nicht mehr leben.
 Um diese Programmen zu warten und zu erweitern, bedient man sich Softwaretools,
 die den vorhandenen Code natürlich auch analysieren müssen.
\layout Itemize

Seitenbeschreibungssprachen wie PDF, Postscript, HPGL.
\layout Itemize

Berechnung von Funktions- und Pfadüberdeckungen für Regressionstest.
\layout Subsection

Programmiersprachliche Grundbegriffe
\layout Standard

Dereferenzierung bedeutet: »Container zu wert«; »entferne den Container,
 gebe mir den Wert«, oder, wenn man sich beide als ineinander geschachtelt
 vorstellt: »entferne den Container«, übrig bleibt sein Wert.
 Werte von Containern können wieder Container sein - so bei Pointern und
 Pointern auf Pointern und Pointern dritten und höheren Grades.
 Auf der linken Seite einer Zuweisung muss stets ein Container stehen (sog.
 »L-Value«), auf der rechten Seite der Inhalt eines Containers (sog.
 »R-Value«, ermittelt durch automatische Dereferenzierung).
 Das bedeutet nicht, dass auf der linken Seite einer Zuweisung überhaupt
 keine Dereferenzierung erlaubt ist; denn das Ergebnis einer Dereferenzierung
 kann ein Container sein, wie in »
\family typewriter 
*zeiger = *zeiger * 2;
\family default 
«.
\layout Section

Architektur eines Compilers
\layout Subsection

Phasenmodell
\layout Standard

Es gibt unterschiedlich grobe Modelle zur Beschreibung von Compilern.
 Eine sehr grobe Einteilung:
\layout Enumerate

Compiler-Frontend: Der Teil eines Compilers, der sich am Quellcode orientiert.
\layout Enumerate

Compiler-Backend: Der Teil eines Compilers, der sich mit der Codegenerierung
 befasst.
\layout Standard

Ein feineres Modell ist die Unterteilung in Phasen.
 Die Zwischendarstellung ist gegenüber dem Quelltext eine redundanzfreie
 Darstellung, ohne jeden 
\begin_inset Quotes ald
\end_inset 

syntactic sugar
\begin_inset Quotes ard
\end_inset 

.
 Sie ist etwa durch Verwendung einer Baumstruktur optimiert für die Verarbeitung
 in der Maschine.
 Dabei wird die Symboltabelle als besondere compilerspezifische Datenstruktur
 verwendet, außerdem weitere übliche Dinge wie Bäume, Listen, Hashtabellen.
 Symboltabellen sind notwendig, um die Bedeutung eines Bezeichners herauszufinde
n.
 Denn Bezeichner sind »universelle Repräsentanten für etwas anderes«.
 Bezeichner haben eine Definitionsstelle (an der der Bezeichner mit seiner
 Bedeutung in die Symboltabelle aufgenommen wird) und beliebig viele Verwendungs
stellen, die die Informationen von der Definitionsstelle benötigen.
 Symboltabellen benutzen Datenstrukturen wie Hashtabellen oder B-Bäume zur
 effizienten Schlüssel-Wert-Zuordnung.
\layout Standard

Es gibt Verwendungsstellen, Deklarationen und Definitionen von Variable;
 dies ist zu verstehen im Sinne folgender Spezialisierung: jede Deklaration
 ist auch eine Verwendungsstelle, jede Definition ist auch eine Deklaration.
\layout Subsection

Beispiel für die Phasen der Compilierung
\layout Standard

Als Beispielsprache wird SPL verwendet.
 Sie weist große Ähnlichkeiten mit C und Pascal auf.
 Die Ergebnisse der einzelnen Phasen der Compilierung, in logischer Reihenfolge:
\layout Paragraph

Quellcode
\layout LyX-Code

proc demo(n:int, ref k:int) {
\layout LyX-Code

  k:=n*3;
\layout LyX-Code

}
\layout Paragraph

Tokens
\layout Standard

Hier nur der Tokenstrom, wie er von der lexikalischen Analyse für die Zuweisung
 erzeugt wird:
\layout LyX-Code

IDENT("k") ASGN IDENT("n") STAR INTLIT(3) SEMIC
\layout Paragraph

Abstrakte Syntax
\layout Standard

Hier nur die Abstrakte Syntax, wie sie von der syntaktischen Analyse für
 die Zuweisung erzeigt wird:
\layout Standard


\begin_inset Float figure
placement htbp
wide false
collapsed false

\layout Caption


\begin_inset LatexCommand \label{Abb_AbstrakteSyntax}

\end_inset 

Abstrakte Syntax einer Zuweisung
\end_inset 


\layout Standard

Es entsteht ein Syntaxbaum gemäß Abbildung 
\begin_inset LatexCommand \ref{Abb_AbstrakteSyntax}

\end_inset 

.
\layout Paragraph

Symboltabelle
\layout Standard

Hier der Zustand der Symboltabelle als Ergebnis der semantischen Analyse.
 Es werden Namen auf Eigenschaften abgebildet.
 Es gibt zwei Ebenen: Level 0 für lokale Variablen, Level 1 für eine Stufe
 globalere Variablen.
\layout LyX-Code

Level 0: n -> var: int
\layout LyX-Code

         k -> var: ref int 
\layout LyX-Code

Level 1: demo -> proc: (int, ref int)
\layout LyX-Code

         int -> type: int
\layout LyX-Code

         main -> proc: ()
\layout LyX-Code

         //dazu etliche Bibliotheksprozeduren, weil sie auch im 
\layout LyX-Code

         //Programm aufgerufen werden können
\layout Paragraph

Variablenallokation
\layout Standard

Hier wird festgelegt, welche Variablen welche Speicherplätze bekommen.
 Dies wird anhand der gesamten Prozedur demo behandelt.
 Ergebnis:
\layout LyX-Code

param 'n': fp+0 //fp = frame pointer
\layout LyX-Code

param 'k': fp+4
\layout LyX-Code

local vars: 0
\layout LyX-Code

proc calls: none //werden andere Prozeduren aufgerufen?
\layout Paragraph

Assemblercode
\layout Standard

Hier nur für die Zuweisung, weil alles andere noch zu kompliziert ist.
\layout LyX-Code

add    $8,$25,4    ;berechnet wird fp+4, die Adresse von k.
 fp in Register $25!
\layout LyX-Code

ldw    $8,$8,0     ;einfach indirekter Speicherzugriff: Inhalt von k :=
 Referenz
\layout LyX-Code

add    $9$25,0     ;berechnet wird fp+0, die Adresse von n.
 fp in Register $25!
\layout LyX-Code

ldw    $9,$9,0     ;Umwandlung Adresse in Inhalt - Wert holen
\layout LyX-Code

add    $10,$0,3    ;Konstante 3 nach $10, Register $0 liefert nach
\layout LyX-Code

                   ;RISC-Konvention immer "0"
\layout LyX-Code

mul    $9,$9,$10   ;$9 <- $9 * $10
\layout LyX-Code

stw    $9,$8,0     ;mem[$8+0] <- $9
\layout Paragraph

Maschinenprogramm
\layout Standard

Adressen von Daten und Funktionen werden im Assemblerprogramm noch symbolisch
 dargestellt, im Maschinenprogramm jedoch numerisch.
 Das ist der wesentliche Unterschied zwischen beiden Darstellungsformen;
 der Assembler hat die Aufgabe, die Transformation durchzuführen.
\layout Section

Die Phase der lexikalischen Analyse
\layout Standard

Die Aufgabe: konvertiere den Strom von Eingabezeichen des Quellprogramms
 in einen Strom von Tokens.
 Was sind Tokens? Nur festgelegt als informale Definition: ein Token ist
 das kleinste bedeutungstragende Element.
 Das können Einzelzeichen (etwa 
\begin_inset Quotes ald
\end_inset 

+
\begin_inset Quotes ard
\end_inset 

, 
\begin_inset Quotes ald
\end_inset 

3
\begin_inset Quotes ard
\end_inset 

 als Integerliteral) oder Zeichenketten (wie 
\begin_inset Quotes ald
\end_inset 

n123
\begin_inset Quotes ard
\end_inset 

 als Name) sein.
 Beispiele zu Token-Typen aus konkreten Programmen:
\layout Description

IDENT (Bezeichner) 
\family typewriter 
k ab123 das_Letzte
\layout Description

NUM (Zahl) 
\family typewriter 
123 0 0xAFFE
\layout Description

IF (Schlüsselwort für Bedingungen) 
\family typewriter 
if
\layout Description

COMMA (Komma) 
\family typewriter 
,
\layout Description

LE (kleiner oder gleich) 
\family typewriter 
<=
\layout Description

RPAREN (schließende Klammer) 
\family typewriter 
)
\layout Standard

Wie kann man nun spezifizieren, was in der lexikalischen Analyse als Token
 erkannt werden soll? Als Hilfmittel dazu dienen die regulären Ausdrücke.
\layout Subsection

Reguläre Ausdrücke
\layout Subsubsection

Definitionen
\layout Paragraph

Definition 
\begin_inset Quotes ald
\end_inset 

Sprache
\begin_inset Quotes ard
\end_inset 


\layout Standard

Eine Sprache ist eine Menge von Strings.
 Diese Menge ist typischerweise unendlich.
\layout Paragraph

Definition 
\begin_inset Quotes ald
\end_inset 

String
\begin_inset Quotes ard
\end_inset 


\layout Standard

Ein String ist eine endliche Folge von Zeichen.
\layout Paragraph

Definition 
\begin_inset Quotes ald
\end_inset 

Alphabet
\begin_inset Quotes ard
\end_inset 


\layout Standard

Die Menge aller zur Verfügung stehenden Zeichen.
\layout Subsubsection

Reguläre Ausdrücke
\layout Standard

Beispiel: Sprache, String und Aphabet.
 Die Sprache bestehe aus beliebig vielen 
\family typewriter 
a
\family default 
 gefolgt von genau einem 
\family typewriter 
b
\family default 
:
\layout LyX-Code

Alphabet = {a,b}
\layout LyX-Code

Sprache = {b,ab,aab,aaab,}
\layout Standard

Diese informale Beschreibung ist ungeeignet, da die Regel zur Ergänzung
 der Auslassung nicht explizit angegeben wurde.
 Die Beschreibung einer (regulären) Sprache geschieht durch 
\begin_inset Quotes ald
\end_inset 

reguläre Ausdrücke
\begin_inset Quotes ard
\end_inset 

.
 Jeder reguläre Ausdruck steht für eine Menge von Strings.
\layout Standard

Reguläre Ausdrücke werden rekursiv (d.i.
 induktiv) definiert, weil sie unendliche Mengen beschreiben.
 Der Endpunkt der Rekursion ist das einzelne Zeichen:
\layout Description

Zeichen: 
\family typewriter 
\series bold 
a
\family default 
\series default 
 steht für 
\family typewriter 
L(a)={a}
\family default 
.
 Der reguläre Ausdruck a steht für eine Sprache, die nichts enthält außer
 dem String a.
 Es muss zwischen regulären Ausdrücken (in Fettduck) und Strings von Sprachen
 unterschieden werden.
\layout Description

Alternative: 
\family typewriter 
\series bold 

\begin_inset Formula $\beta$
\end_inset 

|
\begin_inset Formula $\gamma$
\end_inset 


\family default 
\series default 
 steht für 
\family typewriter 
L(
\begin_inset Formula $\beta$
\end_inset 

|
\begin_inset Formula $\gamma$
\end_inset 

)=L(
\begin_inset Formula $\beta$
\end_inset 

)
\begin_inset Formula $\cup$
\end_inset 

L(
\begin_inset Formula $\gamma$
\end_inset 

)
\begin_deeper 
\layout Standard

Beispiel: 
\family typewriter 
\series bold 
a|b
\family default 
\series default 
 beschreibt 
\family typewriter 
L(a|b))=L(a)
\begin_inset Formula $\cup$
\end_inset 

L(b)={a}
\begin_inset Formula $\cup$
\end_inset 

{b}={a,b}
\end_deeper 
\layout Description

Konkatenation
\begin_inset Foot
collapsed true

\layout Standard

Manche Autoren schreiben einen Malpunkt 
\begin_inset Quotes ald
\end_inset 


\begin_inset Formula $\cdot$
\end_inset 


\begin_inset Quotes ard
\end_inset 

, der jedoch wie bei der Multiplikation auch weggelassen werden kann.
\end_inset 

: 
\begin_inset Formula $\beta\gamma$
\end_inset 

 steht für 
\begin_inset Formula $L\left(\beta\gamma\right)=\left\{ st\mid s\in L\left(\beta\right)\wedge t\in L\left(\gamma\right)\right\} $
\end_inset 


\begin_deeper 
\layout Standard

Beispiel
\begin_inset Foot
collapsed true

\layout Standard

Wie sonst auch in Ausdrücken können Klammern verwendet werden, um Vorrang
 auszudrücken.
\end_inset 

: 
\begin_inset Formula $a\left(b\mid c\right)$
\end_inset 

 steht für 
\begin_inset Formula $L\left(a\left(b\mid c\right)\right)=\left\{ st\mid s\in L\left(a\right)\wedge t\in L\left(b\mid c\right)\right\} =\left\{ st\mid s\in\left\{ a\right\} \wedge t\in\left\{ b,c\right\} \right\} ={ab,ac}$
\end_inset 


\end_deeper 
\layout Description

Epsilon: Der leere String.
 Es ist ein String, der keine Zeichen enthält, nicht die leere Menge.
 Man verwendet als Formelzeichen 
\begin_inset Formula $\varepsilon$
\end_inset 

.
 
\begin_inset Formula $\varepsilon$
\end_inset 

 steht für 
\begin_inset Formula $L\left(\varepsilon\right)=\left\{ \varepsilon\right\} $
\end_inset 

 (leerer String).
\layout Description

Kleene'scher\SpecialChar ~
Abschluss: 
\begin_inset Formula $\beta*$
\end_inset 

 steht für 
\begin_inset Formula $L\left(\beta*\right)=L\left(\varepsilon\right)\cup L\left(\beta\right)\cup L\left(\beta\beta\right)\cup\ldots$
\end_inset 


\begin_deeper 
\layout Standard

Beispiel: 
\begin_inset Formula $\left(ab\right)*$
\end_inset 

 steht für 
\begin_inset Formula $L\left(\left(ab\right)*\right)=L\left(\varepsilon\right)\cup L\left(ab\right)\cup L\left(abab\right)\cup\ldots=\left\{ \varepsilon,ab,abab,ababab,\ldots\right\} $
\end_inset 

.
 Aufgrund von Vorrangregeln ist 
\begin_inset Formula $ab*=a\left(b*\right)\neq\left(ab\right)*$
\end_inset 


\end_deeper 
\layout Subsubsection

Beispiele zu regulären Ausdrücken
\layout Enumerate

Binärzahlen, die Vielfache von 
\begin_inset Formula $2$
\end_inset 

 sind: 
\begin_inset Formula $\left(0\mid1\right)*0$
\end_inset 


\layout Enumerate

Strings aus 
\begin_inset Formula $a$
\end_inset 

 und 
\begin_inset Formula $b$
\end_inset 

, die keine zwei 
\begin_inset Formula $a$
\end_inset 

 hintereinander enthalten: 
\begin_inset Formula $b*\left(abb*\right)*\left(a\mid\varepsilon\right)$
\end_inset 


\layout Enumerate

Strings aus 
\begin_inset Formula $a$
\end_inset 

 und 
\begin_inset Formula $b$
\end_inset 

, die mindestens einmal zwei 
\begin_inset Formula $a$
\end_inset 

 hintereinander enthalten: 
\begin_inset Formula $\left(a\mid b\right)*aa\left(a\mid b\right)*$
\end_inset 


\layout Subsubsection

Anwendung von regulären Ausdrücken in Programmiersprachen
\layout Standard

Die bisher eingeführten Elemente der regulären Ausdrücke reichen aus, um
 jede reguläre Sprache zu beschreiben.
 Es ist jedoch mühsam.
 Deshalb führt man Abkürzungen ein
\begin_inset Foot
collapsed true

\layout Standard

Was genau hier möglich ist, steht in der Manualpage von lex und flex.
\end_inset 

:
\layout Itemize


\begin_inset Formula $\left[abcd\right]:=\left(a\mid b\mid c\mid d\right)$
\end_inset 


\layout Itemize


\begin_inset Formula $\left[b-e\right]:=\left(b\mid c\mid d\mid e\right)$
\end_inset 


\layout Itemize


\begin_inset Formula $\beta?:=\left(\beta\mid\varepsilon\right)$
\end_inset 

 Die Notation für 
\begin_inset Quotes ald
\end_inset 

optional
\begin_inset Quotes ard
\end_inset 

.
\layout Itemize


\begin_inset Formula $\beta+:=\left(\beta\beta*\right)$
\end_inset 


\layout Itemize


\begin_inset Formula $.:=\left(\textrm{irgendein Zeichen außer Zeilenumbruch}\right)$
\end_inset 


\layout Standard

Beispiel: die formale Spezifikation eines Scanners zur lexikalischen Analyse
 einer Programmiersprache.
 Sie besteht aus Zuordnungen von regulären Ausdrücken zu Tokens:
\layout LyX-Code

if                       -> IF
\layout LyX-Code

[a-z][a-z0-9]*           -> IDENT
\layout LyX-Code

[0-9]+                   -> NUM
\layout LyX-Code

0x[0-9a-fA-F]+           -> NUM
\layout LyX-Code


\backslash 
)                       -> RPAREN
\layout Standard

Problem: Eine Spezifikation wie die obige ist mehrdeutig:
\layout Itemize

Was ist 
\family typewriter 
if8
\family default 
? IDENT oder IF NUM?
\layout Itemize

Was ist 
\family typewriter 
if
\family default 
? IDENT oder IF?
\layout Standard

Diese Mehrdetigkeiten werden nach den folgenden zwei Regeln (in dieser Reihenfol
ge) aufgelöst:
\layout Description

längste\SpecialChar ~
Übereinstimmung Danach ist 
\family typewriter 
if8
\family default 
 ein IDENT.
 Die Mehrdeutigkeit 
\family typewriter 
if
\family default 
 kann nicht entschieden werden.
\layout Description

erste\SpecialChar ~
Regel Die zuerst genannte Regel hat Vorrang.
 Im obigen Beispiel steht die Regel für IF vor der für IDENT, also ist 
\family typewriter 
if
\family default 
 der Token IF.
\layout Section

Die Phase der Syntaxanalyse
\layout Standard

Die verschiedenen Parser, vom einfachsten zum mächtigsten:
\layout Description

LL(1)-Parser Ein Parser, der auf LL(1)-Grammatiken arbeitet.
 Auch Top-Down-Parser oder prädikativer Parser (
\begin_inset Quotes ald
\end_inset 

voraussagender Parser
\begin_inset Quotes ard
\end_inset 

) genannt.
 Die Abkürzung bedeutet:
\begin_deeper 
\layout Description

L (left) Die Eingabe wird von links nach rechts gelesen.
\layout Description

L (left) Der Syntaxbaum wird beim Parsen durch eine Linksableitung aufgebaut,
 d.h.
 es wird stets das am weitesten links stehende Nichtterminalsymbol als nächstes
 bearbeitet.
\layout Description

(1) (1) Ein Symbol Lookahead reicht aus, um eindeutig die nächste Regel
 zu bestimmen.
\layout Standard

Eine Grammatik, bei der mit einem Symbol Lookahead die richtige Regel zur
 Ableitung eines Nichtterminals eindeutig bestimmt ist, heißt LL(1)-Grammatik.
 Bedingungen: (sei 
\begin_inset Formula $\left\{ A\rightarrow\beta_{i}\right\} =\left\{ A\rightarrow\beta_{i}\mid\left(A\rightarrow\beta_{i}\right)\in P\right\} $
\end_inset 

)
\layout Itemize


\begin_inset Formula $\forall_{i\neq j}:FIRST\left(\beta_{i}\right)\cap FIRST\left(\beta_{j}\right)=\left\{ \right\} $
\end_inset 

 Das verbietet u.a.
 Linksrekursionen und gemeinsame Präfixe in den 
\begin_inset Formula $A\rightarrow\beta_{i}$
\end_inset 

.
\layout Itemize

wenn 
\begin_inset Formula $\epsilon\in FIRST\left(A\right)$
\end_inset 

: 
\begin_inset Formula $FIRST\left(A\right)\cap FOLLOW\left(A\right)=\left\{ \right\} $
\end_inset 


\end_deeper 
\layout Description

LR(0)-Parser Auch Bottom-Up-Parser oder Shift-Reduce-Parser genannt.
 Idee: der Parser akzeptiert es im Gegensatz zum LL(1)-Parser, wenn während
 dem Einlesen des Tokenstroms mehrere Produktionen existieren, die diese
 Tokenfolge erzeugen können; erst wenn eine rechte Regelseite vollständig
 eingelesen ist, muss die Regel eindeutig bestimmt sein.
 Die Entscheidung 
\begin_inset Quotes ald
\end_inset 

shift oder reduce
\begin_inset Quotes ard
\end_inset 

 wird bei LR(0) ohne Vorausschau getroffen.
 Eine Grammatik ohne Shift/Reduce-Konflikte heißt 
\begin_inset Quotes ald
\end_inset 

LR(0)-Grammatik
\begin_inset Quotes ard
\end_inset 

.
 Die Abkürzung bedeutet:
\begin_deeper 
\layout Description

L (left) Die Eingabe wird von links nach rechts gelesen.
\layout Description

R (right) Der Syntaxbaum wird beim Parsen durch eine Rechtsableitung aufgebaut,
 d.h.
 es wird stets das am weitesten rechts (auf dem Symbolstack) stehende Nichttermi
nalsymbol als nächstes bearbeitet.
\layout Description

(0) Kein Symbol Lookahead.
\end_deeper 
\layout Description

SLR(1)-Parser Die Abkürzung bedeutet: S (simple) LR-Parser mit einem Symbol
 Lookahead.
 Shift/Reduce-Konflikte werden durch Vorausschau gelöst: ein 
\begin_inset Formula $A$
\end_inset 

-Handle wird nur zu 
\begin_inset Formula $A$
\end_inset 

 reduziert, wenn das Lookahead-Token 
\begin_inset Formula $t\in FOLLOW\left(A\right)$
\end_inset 

 ist.
\layout Description

LALR(1)-Parser Die Abkürzung bedeutet: LA (lookahead) LR(1)-Parser.
 Es ist eine kompaktere, funktionell fast ebenso mächtige Variante des LR(1)-Par
sers.
 Dabei werden Zustände, die sich nur im FOLLOW-Token unterscheiden, zu einem
 zusammengefasst.
 Die Zustandsmenge wird dann nur ein Zehntel so groß.
\layout Description

LR(1)-Parser Sog.
 kanonischer LR(1)-Parser.
 Ein 
\begin_inset Formula $A$
\end_inset 

-Handle wird nur zu 
\begin_inset Formula $A$
\end_inset 

 reduziert, wenn das Lookahead-Token 
\begin_inset Formula $t\in\left\{ FOLLOW\left(A\right)\right\} $
\end_inset 

 ist und 
\begin_inset Formula $At$
\end_inset 

 in der aktuellen Satzform möglich ist.
 Es wird also der Kontext der 
\begin_inset Formula $A$
\end_inset 

-Handles berücksichtigt.
\layout Description

LR(k)-Parser Ein Parser, der auf LR(k)-Grammatiken arbeitet.
 Auch dieses mächtigste hier genannte Verfahren kann nicht beliebige kontextfrei
e Grammatiken verarbeiten: LR(k)-Grammatiken sind eine Untermenge davon.
 Early-Parser und Cocke-Kasami-Younger-Parser können beliebige kontextfreie
 Grammatiken verarbeiten.
\layout Section

Die Phase der semantischen Analyse
\layout Section

Die Phase Zwischencodeerzeugung
\layout Section

Die Phase Maschinencodeerzeugung
\layout Section

Aufgaben und Lösungen
\layout Subsection

Frame-Layout für eine SPL-Prozedur
\layout Paragraph

Aufgabenstellung
\layout Standard

Bestimmen Sie das Frame-Layout (Bestandteile in der richtigen Reihenfolge
 mit Größe in Bytes) für den Aktivierungsrahmen der nachfolgenden SPL-Prozedur
\layout LyX-Code

x.
 proc x (ref i:int) {
\layout LyX-Code

  var k: int;
\layout LyX-Code

  k:=i+1;
\layout LyX-Code

  i:=k;
\layout LyX-Code

  printi(i);
\layout LyX-Code

}
\layout Standard

Quelle: 
\begin_inset LatexCommand \cite[2004-WS, Bl.8, Aufg.6]{JaegerUebungen}

\end_inset 

.
\layout Paragraph

Lösung
\layout Standard


\begin_inset  Tabular
<lyxtabular version="3" rows="6" columns="4">
<features>
<column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
<column alignment="center" valignment="top" leftline="true" width="0">
<column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
<column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
<row topline="true" bottomline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

Adresse
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

Element
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

Größe
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

Beschreibung
\end_inset 
</cell>
</row>
<row topline="true" bottomline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $FP$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\family typewriter 
i
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $4$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

1.
 Parameter von 
\family typewriter 
x
\family default 
 (gehört zum vorigen Frame)
\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $FP-4$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\family typewriter 
k
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $4$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

lokale Variable
\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $FP-8$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

OldFramePtr
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $4$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

gerettetes Register $25 (Framepointer)
\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $FP-12$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

OldRetAdr
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $4$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

gerettetes Register $31 (Return-Adresse)
\end_inset 
</cell>
</row>
<row topline="true" bottomline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $FP-16$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\family typewriter 
Arg1
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $4$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

1.
 Parameter für Prozeduraufrufe in 
\family typewriter 
x
\end_inset 
</cell>
</row>
</lyxtabular>

\end_inset 


\layout Paragraph

Lösungsverfahren
\layout Standard

Siehe 
\begin_inset LatexCommand \cite[S.35]{Budweg}

\end_inset 

.
 Ein SPL-Stackframe besteht enthält (in Reihenfolge):
\layout Itemize

lokale Variablen der Prozedur
\layout Itemize

gerettetes Register $25 (Framepointer)
\layout Itemize

wenn die Prozedur weitere Prozeduraufrufe enthält:
\begin_deeper 
\layout Itemize

gerettetes Register $31 (Return-Adresse)
\layout Itemize

Parameter für Prozeduraufrufe in 
\family typewriter 
x
\end_deeper 
\layout Subsection

SPL in ECO32-Assembler übersetzen
\layout Paragraph

Aufgabenstellung
\layout Standard

Bestimmen Sie den ECO32-Assemblercode zur nachfolgenden SPL-Prozedur 
\family typewriter 
x
\family default 
.
 Die Prozedur 
\family typewriter 
printi
\family default 
 erwartet einen Wertparameter vom Typ 
\family typewriter 
int
\family default 
.
 (SP=$29, FP=$25, RET=$31, verfügbare Register: $8-$15).
\layout LyX-Code

proc x (ref i:int) {
\layout LyX-Code

  var k: int;
\layout LyX-Code

  k:=i+1;
\layout LyX-Code

  i:=k;
\layout LyX-Code

  printi(i);
\layout LyX-Code

}
\layout Standard

Quelle: 
\begin_inset LatexCommand \cite[2004-WS, Bl.8, Aufg.6]{JaegerUebungen}

\end_inset 

.
\layout Paragraph

Lösung
\layout LyX-Code

.export x
\layout LyX-Code

x:
\layout LyX-Code

  sub $29,$29,16         ; allocate frame 
\layout LyX-Code

  stw $25,$29,8          ; save old frame pointer 
\layout LyX-Code

  add $25,$29,16         ; setup new frame pointer 
\layout LyX-Code

  stw $31,$25,-12        ; save return register 
\layout LyX-Code

  add $8,$25,-4          ; $8 <- Adresse(k) 
\layout LyX-Code

  add $9,$25,0           ; $9 <- Adresse(i) 
\layout LyX-Code

  ldw $9,$9,0            ; $9 <- Wert(i) (=Adresse der ¨ubergebenen Var.)
 
\layout LyX-Code

  ldw $9,$9,0            ; $9 <- Wert(Wert(i)) (=Wert der ¨ubergebenen Var.)
\layout LyX-Code

  add $10,$0,1           ; $10 <- 1 
\layout LyX-Code

  add $9,$9,$10          ; $9 <- i+1 
\layout LyX-Code

  stw $9,$8,0            ; Wert(k) <- $9 
\layout LyX-Code

  add $8,$25,0           ; $8 <- Adresse(i) 
\layout LyX-Code

  ldw $8,$8,0            ; $8 <- Wert(i) (=Adresse der ¨ubergebenen Var.)
 
\layout LyX-Code

  add $9,$25,-4          ; $9 <- Adresse(k) 
\layout LyX-Code

  ldw $9,$9,0            ; ...
 
\layout LyX-Code

  stw $9,$8,0            
\layout LyX-Code

  add $8,$25,0           
\layout LyX-Code

  ldw $8,$8,0            
\layout LyX-Code

  ldw $8,$8,0            
\layout LyX-Code

  stw $8,$29,0           ; store arg #0 
\layout LyX-Code

  jal printi 
\layout LyX-Code

  ldw $31,$25,-12        ; restore return register 
\layout LyX-Code

  ldw $25,$29,8          ; restore old frame pointer 
\layout LyX-Code

  add $29,$29,16         ; release frame 
\layout LyX-Code

  jr $31                 ; return
\layout Paragraph

Lösungsverfahren
\layout Enumerate

Stackpointer auf untere Grenze des neuen Frames setzen (Frame allokieren)
\layout Enumerate

Framepointer sichern
\layout Enumerate

neuen Wert des Framepointers setzen (auf Stackpointer plus Framesize)
\layout Enumerate

Return-Register sichern
\layout Enumerate

[Befehle für den Prozedur-Rumpf]
\layout Enumerate

Return-Register wiederherstellen
\layout Enumerate

Framepointer wiederherstellen
\layout Enumerate

Stackpointer auf untere Grenze des vorigen Frames setzen (Frame freigeben)
\layout Enumerate

Rücksprung
\layout Section

Algorithmen für Klausuraufgaben
\layout Subsection

Grammatik in LL(1)-Grammatik transformieren
\layout Subsection

LL(1)-Parsertabelle bestimmen
\layout Standard

Am Beispiel folgender Grammatik:
\layout Standard


\begin_inset Formula \begin{eqnarray*}
S & \rightarrow & X\mid Yc\\
X & \rightarrow & aX\mid bY\\
Y & \rightarrow & dY\mid\epsilon\end{eqnarray*}

\end_inset 


\layout Enumerate

Schreibe alle Regeln einzeln, d.h.
 ohne Alternativen:
\begin_inset Formula \begin{eqnarray*}
S & \rightarrow & X\\
S & \rightarrow & Yc\\
X & \rightarrow & aX\\
X & \rightarrow & bY\\
Y & \rightarrow & dY\\
Y & \rightarrow & \epsilon\end{eqnarray*}

\end_inset 


\layout Enumerate

Fülle folgende Tabelle aus:
\begin_deeper 
\layout Itemize

Bestimme 
\begin_inset Formula $FIRST\left(\right)$
\end_inset 

 von allen vorkommenden Satzformen (
\begin_inset Formula $FIRST\left(e\right),e\in T$
\end_inset 

 sind dazu Zwischenergebnisse).
\layout Itemize

Bestimme 
\begin_inset Formula $FOLLOW\left(\right)$
\end_inset 

 von allen Nichtterminalsymbolen.
\layout Standard

Es macht dabei Sinn, die Nichtterminalsymbole auf der linken Seite der Produktio
nen in umgekehrter Reihenfolge ans Ende der Tabelle zu setzen.
\layout Standard


\begin_inset  Tabular
<lyxtabular version="3" rows="8" columns="3">
<features>
<column alignment="center" valignment="top" leftline="true" width="0">
<column alignment="center" valignment="top" leftline="true" width="0">
<column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
<row topline="true" bottomline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

Symbol
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $FIRST\left(\right)$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $FOLLOW\left(\right)$
\end_inset 


\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $X$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $\left\{ a,b\right\} $
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $\left\{ \$\right\} $
\end_inset 


\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $Y$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $\left\{ d,\epsilon\right\} $
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $\left\{ c,\$\right\} $
\end_inset 


\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $S$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $\left\{ a,b,c,d\right\} $
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $\left\{ \$\right\} $
\end_inset 


\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $Yc$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $\left\{ d,c\right\} $
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $aX$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $\left\{ a\right\} $
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $bY$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $\left\{ b\right\} $
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

\end_inset 
</cell>
</row>
<row topline="true" bottomline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $dY$
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\begin_inset Formula $\left\{ d\right\} $
\end_inset 


\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

\end_inset 
</cell>
</row>
</lyxtabular>

\end_inset 


\end_deeper 
\layout Enumerate

Gehe alle Produktionen 
\begin_inset Formula $P\rightarrow Satzform$
\end_inset 

 der Reihe nach durch
\begin_deeper 
\layout Itemize

trage 
\begin_inset Formula $P\rightarrow Satzform$
\end_inset 

 ein für alle Elemente 
\begin_inset Formula $e\in FIRST\left(Satzform\right)$
\end_inset 

 in die Zelle 
\begin_inset Formula $\left[P,e\right]$
\end_inset 


\layout Itemize

falls 
\begin_inset Formula $\epsilon\in FIRST\left(Satzform\right)$
\end_inset 

: trage 
\begin_inset Formula $P\rightarrow Satzform$
\end_inset 

 ein für alle Elemente 
\begin_inset Formula $e\in FOLLOW\left(P\right)$
\end_inset 

 in die Zelle 
\begin_inset Formula $\left[P,e\right]$
\end_inset 


\end_deeper 
\layout Subsection

Zustände eines LALR(1)-Parsers (z.B.
 yacc/bison-generierte Parser)
\layout Standard

Mögliche Optimierung: statt bei Eingabe von 
\begin_inset Formula $x$
\end_inset 

 (besser: 
\begin_inset Formula $\$ default$
\end_inset 

) in einen anderen Zustand zu verzweigen, der nur die Aufgabe hat 
\begin_inset Formula $A\rightarrow\epsilon$
\end_inset 

 zu reduzieren, kann man dies auch direkt vornehmen.
 Denn die 
\begin_inset Formula $A$
\end_inset 

 erhält man in diesem Sonderfall durch reduce ohne vorangehendes shift,
 d.h.
 weil nur ein Schritt notwendig ist muss man nicht in einen zweiten Zustand
 verzweigen.
\layout Subsection

Abstrakter Syntaxbaum eines SPL-Programms
\layout Standard

Hier die Syntax zur Darstellung entsprechend den Ausgabekonventionen des
 Referenzcompilers (übernommen aus den Funktionen 
\family typewriter 
show*()
\family default 
 in der Datei 
\family typewriter 
absyn.c
\family default 
 des Referenzcompilers).
 Argumente der Nodekonstruktoren, die auf 
\begin_inset Quotes ald
\end_inset 


\family typewriter 
N
\family default 

\begin_inset Quotes ard
\end_inset 

 enden zeigen dass hier ein weiterer Nodekonstruktor-Aufruf stehen muss.
 
\layout Enumerate


\family typewriter 
--empty--
\layout Enumerate


\family typewriter 
List(headN<5-12>,tailN<2|5-12>)
\family default 
 oder 
\family typewriter 
List(headN<5-12>)
\layout Enumerate


\family typewriter 
Nametype(name) 
\family default 
(beliebiger, durch einen einfachen Namen identifizierbarer Basistyp)
\layout Enumerate


\family typewriter 
Arraytype(size,typeN<3>)
\layout Enumerate


\family typewriter 
Typedecl(name,typeN<4>)
\layout Enumerate


\family typewriter 
Vardecl(name,typeN<3-4>)
\layout Enumerate


\family typewriter 
Procdecl(name,paramsN<2<8>>,declsN<2<6>>,bodyN<2<9-12>>)
\layout Enumerate


\family typewriter 
Param(name,typeN<3-4>,isref)
\layout Enumerate


\family typewriter 
Assign(varN<16-17>,exprN<13-15>)
\layout Enumerate


\family typewriter 
If(testN<13>,thenN<2<9-12>>,elseN<2<9-12>>)
\layout Enumerate


\family typewriter 
While(testN<13>,bodyN<2<9-12>>)
\layout Enumerate


\family typewriter 
Call(name,argsN<2<13-15>>)
\layout Enumerate


\family typewriter 
Op(name,leftexprN<13-15>,rightexprN<13-15>)
\layout Enumerate


\family typewriter 
Var(varN<16-17>)
\family default 
 (bestimmt den Wert einer Variablen)
\layout Enumerate


\family typewriter 
Int(value)
\layout Enumerate


\family typewriter 
Simplevar(name)
\layout Enumerate


\family typewriter 
Arrayvar(varN<16-17>,index)
\layout Standard

Hinweise:
\layout Itemize


\family typewriter 
List(headN,[tailN])
\family default 
 erhält als erstes Argument einen beliebigen Node-Konstruktor außer 
\family typewriter 
List()
\family default 
, als zweites (optionales) Argument den Node-Konstruktor 
\family typewriter 
List()
\family default 
.
\layout Itemize


\family typewriter 
Arraytype()
\family default 
 erhält als zweites Argument entweder 
\family typewriter 
Nametype()
\family default 
 (für Basistypen) oder 
\family typewriter 
Arraytype()
\family default 
.
\layout Itemize


\family typewriter 
Simplevar()
\family default 
 und 
\family typewriter 
Arrayvar()
\family default 
 geben den L-Value einer Variablen, notwendig auf der linken Seite einer
 Zuweisung.
 
\family typewriter 
Var(Simplevar())
\family default 
 und 
\family typewriter 
Var(Arrayvar())
\family default 
 geben den R-Value einer Variablen.
\layout Itemize

Ein SPL-Programm hat stets 
\family typewriter 
List()
\family default 
 als äußersten Node-Konstruktor: es ist eine Liste von Prozedur-Deklarationen.
\layout Section

Fragen und Anmerkungen
\layout Description

Skript\SpecialChar ~
S.38 »(Die Ableitbarkeitsrelation ist demzufolge der transitive und
 reflexive Abschluss der direkten Ableitbarkeit.)«
\layout Description

Skript\SpecialChar ~
S.39 »
\begin_inset Formula $\left\{ a^{n}b^{n}c^{n}\mid n\in N\right\} $
\end_inset 


\begin_inset Quotes ard
\end_inset 

 Was bedeutet Potenzierung mit einem Nichtterminalsymbol?
\layout Description

Skript\SpecialChar ~
S.40 Rechtsableitung und Linksableitung sind eigentlich unnötige Konzepte.
 Die Ableitung ist in beliebiger Reihenfolge durchführbar, sofern man die
 Ergebnisse der Ableitung in der ursprünglichen Reihenfolge der Nichtterminalsym
bole in 
\begin_inset Formula $w$
\end_inset 

 und nicht in der Reihenfolge der Ableitung konkateniert.
\layout Description

Skript\SpecialChar ~
S.50 Programmiersprachen sind keine regulären Sprachen, das heißt mit
 regulären Ausdrücen wird eine Programmiersprache nicht vollständig beschrieben.
 Eine kontextfreie Grammatik ist Obermenge der regulären Grammatik, d.h.
 eine kontextfreie Sprache enthält Bestandteile, die mit regulären Grammatiken
 beschrieben werden können.
 Oder anders gesagt: ein Wort in einer kontextfreien Sprache ist vollständig
 zerlegbar in Teilwörter in regulären Sprachen.
 Diese Teilwörter sind die Tokens.
 Nur die hierarchische Struktur, in der Tokens angeordnet sein dürfen, ist
 mit regulären Grammatiken nicht beschreibbar.
\layout Description

Skript\SpecialChar ~
S.51 Was ist Operator-Assoziativität? Sie kann sein:
\begin_deeper 
\layout Itemize

linksassoziativ (genauer: von links nach rechts)
\layout Itemize

rechtsassoziativ (genauer: von rechts nach links)
\layout Itemize

nicht-assoziativ; diese Operatoren können nicht in der Form 
\begin_inset Formula $x\circ y\circ z$
\end_inset 

 auftreten, denn ohne Assoziativität ist diese Form nicht interpretierbar
\layout Standard

Die Assoziativität eines Operators gibt die 
\begin_inset Quotes ald
\end_inset 

Ausführungsrichtung
\begin_inset Quotes ard
\end_inset 

 an, in der Operationen derselben Priorität ausgeführt werden.
 Beispiel: Operationen mit linksassoziativen Operatoren gleicher Priorität
 werden 
\begin_inset Quotes ald
\end_inset 

von links nach rechts
\begin_inset Quotes ard
\end_inset 

 ausgeführt, so dass 
\begin_inset Formula $w=x+y+z$
\end_inset 

 dasselbe ist wie 
\begin_inset Formula $w=\left(\left(x+y\right)+z\right)$
\end_inset 

.
 Das Wort »assoziativ« bedeutet dabei »verbindend«; es ist wohl so zu verstehen
 dass ein linksassoziativer Operator den links von ihm stehenden Teil des
 Ausdrucks als »verbundenen« (zusammengesetzten, komplexen, geklammerten)
 Ausdruck interpretiert.
 Beispiel: in 
\begin_inset Formula $x+y+z$
\end_inset 

 interpretiert der 
\begin_inset Formula $+$
\end_inset 

-Operator vor 
\begin_inset Formula $z$
\end_inset 

 den links von ihm stehenden Teil als 
\begin_inset Formula $\left(x+y\right)$
\end_inset 

, den rechts von ihm stehenden Teil als 
\begin_inset Formula $z$
\end_inset 

.
\layout Standard

Assoziativität hat nichts mit dem Assoziativitätsgesetz zu tun.
 Nach diesem muss die Assoziativität eines Operators, für den das Assoziativität
sgesetz gilt, gar nicht festgelegt werden, denn das Ergebnis ist unabhängig
 von der Auswertereihenfolge: 
\begin_inset Formula $\left(a+b\right)+c=a+\left(b+c\right)$
\end_inset 

.
 Trotzdem wird in Grammatiken die Assoziativität festgelegt, einfach um
 einem einheitlichen System zu folgen.
 Dürfte der Compiler die Auswertereihenfolge bei Mehrdeutigkeiten selbst
 wählen statt eine Fehlermeldung auszugeben, würden manche Fehler bei der
 Grammatikentwicklung schwerer erkennbar.
\layout Standard

Assoziativität funktioniert nur, wenn Operatoren gleicher Präzedenzstufe
 die gleiche Assoziativität zugewiesen wird!
\end_deeper 
\layout Description

Skript\SpecialChar ~
S.61 Was bedeutet 
\begin_inset Quotes ald
\end_inset 

(Die Teilmengen, die Endzustände repräsentieren, müssen einelementig sein,
 sonst ist die Token-Syntax mehrdeutig)
\begin_inset Quotes ard
\end_inset 

.
\layout Description

Skript\SpecialChar ~
S.71 »Ein Wort 
\begin_inset Formula $w\in\Sigma^{*}$
\end_inset 

unterscheidet zwei Zustände, falls 
\begin_inset Formula $A$
\end_inset 

 mit Eingabe 
\begin_inset Formula $w$
\end_inset 

 aus genau einem dieser Zustände einen Endzustand erreicht.« Was bedeutet
 das? Wir variieren 
\begin_inset Formula $A$
\end_inset 

, indem wir einen anderen Startzustand wählen und geben ihm dann das Eingabewort
 
\begin_inset Formula $w$
\end_inset 

.
 Aus Sicht von 
\begin_inset Formula $w$
\end_inset 

 gibt es zwei Äquivalenzklassen unserer Automatenvariationen: solche die
 
\begin_inset Formula $w$
\end_inset 

 akzeptieren (nach 
\begin_inset Formula $w$
\end_inset 

 in einem Endzustand sind) und solche die 
\begin_inset Formula $w$
\end_inset 

 nicht akzeptieren.
 Aus Sicht von 
\begin_inset Formula $w$
\end_inset 

 sind damit nur Zustände unterscheidbar, die zu einem unterschiedlichen
 Ergebnis führen wenn man sie als Startzustand festlegt: einer zu einem
 Automaten, der 
\begin_inset Formula $w$
\end_inset 

 akzeptiert und einer zu einem Automaten, der 
\begin_inset Formula $w$
\end_inset 

 nicht akzeptiert.
\layout Description

Skript\SpecialChar ~
S.85 Warum sollte es für Top-Down-Analyse durch rekursiven Abstieg
 einen Fehler bedeuten, wenn man ein Terminalsymbol findet, das nicht gleichzeit
ig das erste Symbol einer Regel (d.h.
 das lookahead-Symbol) ist?
\layout Description

Skript\SpecialChar ~
S.110-111 
\begin_inset Quotes ald
\end_inset 

Zu ergänzen sind noch die Reduktionen für alle Zustände mit reduzierbaren
 Elementen:« Das Verfahren wird zwar beschrieben auf S.
 107-108 (
\begin_inset Quotes ald
\end_inset 

Berechnung der Reduktionsaktionen
\begin_inset Quotes ard
\end_inset 

), jedoch ist nicht ersichtlich wie es zum hier dargestellten Ergebnis führt.
\layout Description

Skript\SpecialChar ~
S.112 Was bedeutet eigentlich 
\begin_inset Quotes ald
\end_inset 

LR
\begin_inset Quotes ard
\end_inset 

?
\layout Description

Skript\SpecialChar ~
S.113 
\begin_inset Quotes ald
\end_inset 

Die LR(1)-Elemente des entsprechenden DEA-Zustands sind folgende:
\begin_inset Quotes ard
\end_inset 


\begin_deeper 
\layout Itemize


\begin_inset Formula $\left[S\rightarrow b.Xb,\:\$\right]$
\end_inset 

 Das verlangt folgende Voraussetzungen, um zu 
\begin_inset Formula $S$
\end_inset 

 reduzieren zu können:
\begin_deeper 
\layout Itemize

weiteren Eingaben derart dass schließlich der Zustand 
\begin_inset Formula $bXb.$
\end_inset 

 entsteht
\layout Itemize

Folgesymbol von 
\begin_inset Formula $S$
\end_inset 

 ist 
\begin_inset Formula $\$$
\end_inset 

, äquivalent: Vorschausymbol im Zustand 
\begin_inset Formula $bXb.$
\end_inset 

 ist 
\begin_inset Formula $\$$
\end_inset 

; dies kann also noch nicht jetzt überprüft werden, sondern erst wenn 
\begin_inset Formula $bXb.$
\end_inset 

 erreicht ist
\end_deeper 
\layout Itemize


\begin_inset Formula $\left[X\rightarrow.a,\: b\right]$
\end_inset 

 Das verlangt folgende Voraussetzungen, um nach 
\begin_inset Formula $X\rightarrow a$
\end_inset 

 reduzieren zu können:
\begin_deeper 
\layout Itemize

weitere Eingaben derart dass schließlich der Zustand 
\begin_inset Formula $a.$
\end_inset 

 entsteht
\layout Itemize

Folgesymbol von 
\begin_inset Formula $X$
\end_inset 

 ist 
\begin_inset Formula $b$
\end_inset 

, äquivalent: Vorschausymbol im Zustand 
\begin_inset Formula $a.$
\end_inset 

 ist 
\begin_inset Formula $b$
\end_inset 


\end_deeper 
\layout Itemize


\begin_inset Formula $\left[X\rightarrow.,\: b\right]$
\end_inset 

 Das verlangt folgende Voraussetzungen, um nach 
\begin_inset Formula $X\rightarrow\epsilon$
\end_inset 

 reduzieren zu können:
\begin_deeper 
\layout Itemize

keine weiteren Eingaben, denn der Zustand 
\begin_inset Formula $\epsilon.$
\end_inset 

 ist bereits erreicht
\layout Itemize

Folgesymbol von 
\begin_inset Formula $X$
\end_inset 

 ist 
\begin_inset Formula $b$
\end_inset 

, äquivalent: Vorschausymbol um Zustand 
\begin_inset Formula $\epsilon.$
\end_inset 

 ist 
\begin_inset Formula $b$
\end_inset 

; dies kann jetzt überprüft werden, denn der Zustand 
\begin_inset Formula $\epsilon.$
\end_inset 

 ist bereits erreicht
\end_deeper 
\end_deeper 
\layout Bibliography
\bibitem {JaegerSkript}

Prof.
 Dr.
 Michael Jäger: 
\begin_inset Quotes ald
\end_inset 

Compilerbau
\begin_inset Quotes ard
\end_inset 

.
 Das offizielle Skript zu dieser Veranstaltung.
 Quelle: 
\begin_inset LatexCommand \url[Homepage von Prof. Jäger]{http://homepages.fh-giessen.de/~hg52/}

\end_inset 

, alternativ 
\begin_inset LatexCommand \url{http://m-jaeger.de/}

\end_inset 

.
 Das Skript enthält alles, was für die Klausur notwendig ist; dazu alle
 für das Praktikum relevante Dokumentation von flex und bison; dazu Literaturemp
fehlungen; jedoch nicht SPL-spezifischen Stoff für das Praktikum, vgl.
 dazu 
\begin_inset LatexCommand \cite{Budweg}

\end_inset 

.
\layout Bibliography
\bibitem {JaegerUebungen}

Prof.
 Dr.
 Michael Jäger: Übungsaufgaben, Hausübungen und Bonusaufgaben zur Veranstaltung
 Compilerbau.
 Quelle: 
\begin_inset LatexCommand \url{http://homepages.fh-giessen.de/~hg52}

\end_inset 

, alternativ: 
\begin_inset LatexCommand \url{http://m-jaeger.de}

\end_inset 

.
\layout Bibliography
\bibitem {JaegerKlausuren}

Prof.
 Dr.
 Michael Jäger: Klausuren zu Compilerbau.
 Ein Archiv alter Klausuren zu dieser Veranstaltung.
 Quelle: 
\begin_inset LatexCommand \url{http://homepages.fh-giessen.de/~hg52}

\end_inset 

.
\layout Bibliography
\bibitem {Budweg}

Boris Budweg: Mitschrift zu Compilerbau bei Prof.
 Dr.
 Hellwig Geisse; Wintersemester 2003/2004; FH Gießen-Friedberg.
 Veröffentlicht auch auf 
\begin_inset LatexCommand \url{http://homepages.fh-giessen.de/~hg52}

\end_inset 

.
\layout Bibliography
\bibitem {Webelsiep}

Webelsiep: Quellcodes zu Compilerbau.
 
\begin_inset LatexCommand \url{http://www.webelsiep.de/downloads/quellcode/compilerbau.zip}

\end_inset 

, referenziert unter 
\begin_inset LatexCommand \url{http://www.webelsiep.de/default.php?main=studium}

\end_inset 

, Bereich Quellcodes.
\layout Bibliography
\bibitem {Pommerening}

Tim Pommerening: Lernkartei zu Compilerbau.
 
\begin_inset LatexCommand \url{http://homepages.fh-giessen.de/~hg12061/studium/COBA_Lernkartei.rar}

\end_inset 

, referenziert auf 
\begin_inset LatexCommand \url{http://homepages.fh-giessen.de/~hg12061/}

\end_inset 

, Bereich Studium.
\layout Bibliography
\bibitem {Drachenbuch}

Aho, Setho, Ullman: 
\begin_inset Quotes ald
\end_inset 

Compilerbau
\begin_inset Quotes ard
\end_inset 

.
 In zwei Bänden.
 Das 
\begin_inset Quotes ald
\end_inset 

Drachenbuch
\begin_inset Quotes ard
\end_inset 

.
 Das Standard-Lehrbuch, das alle Methoden und Verfahren des Compilerbaus
 erklärt und diskutiert.
\layout Bibliography
\bibitem {Wirth}

Wirth: Implementierung einer Teilmenge von Oberon1.
 Es gibt eine Unmenge von solchen Büchern, die den Bau eines Compilers an
 einem Beispiel beschreiben statt verschiedenste Verfahren gegenüberzustellen.
 Diese Bücher haben wesentlich weniger Umfang als Lehrbücher wie 
\begin_inset LatexCommand \cite{Drachenbuch}

\end_inset 

.
\the_end