Skip to main content
main-content

2022 | Buch

Formale Sprachen, abstrakte Automaten und Compiler

Lehr- und Arbeitsbuch mit FLACI für Grundstudium und Fortbildung

share
TEILEN
insite
SUCHEN

Über dieses Buch

Die eher abstrakten Inhalte der Theoretischen Informatik werden aus praktischen Anwendungsbeispielen heraus motiviert, anschaulich vermittelt und in Übungen vertieft. Durch das gesamte Buch hindurch zieht sich das Vorhaben, einen Compiler für eine Sprache mit grafischen Effekten herzustellen. An den entsprechenden Stellen werden die dafür notwendigen Beiträge erarbeitet und Aspekte automatisierter Compilergenerierung thematisiert.

Zur Definition und Simulation formaler Sprachen mit regulären Ausdrücken, formalen Grammatiken und abstrakten Automaten sowie zur automatisierten Compilergenerierung aus einer grafisch-visuellen Beschreibung stellt die Lern- und Arbeitsumgebung FLACI miteinander vernetzte Komponenten zur Verfügung. Da es sich um eine Web-Anwendung (ohne JAVA) handelt, entfällt jeglicher Installations- und Aktualisierungsaufwand. FLACI wurde speziell für das Studium der theoretischen Informatik entwickelt und bereits an mehreren Hochschulen und Schulen erfolgreich eingesetzt. FLACI vertieft Theoriewissen durch praktische Übungen und attraktive Anwendungsprojekte aus dem Grafik- und Audiobereich. Übersetzung und Verarbeitung mehr oder weniger komplexer Sprachen finden wir heute beispielsweise auch in modernen Web-Applikationen.

Inhaltsverzeichnis

Frontmatter
Kapitel 1. Einleitung
Zusammenfassung
Menschen verwenden Sprachen, um miteinander zu kommunizieren. Hierfur bilden sie grammatikalisch (syntaktisch) korrekte Satze, die eine Bedeutung (Semantik) besitzen. Auf diese Weise findet Informationsubertragung/-austausch statt.
Christian Wagenknecht, Michael Hielscher
Kapitel 2. Formale Grammatiken
Zusammenfassung
In Abschnitt 1.7 haben wir erfahren, dass eine Sprache L eine endliche oder im Allgemeinen eine abzahlbar unendliche Teilmenge der Wortmenge A* uber einem ¨bestimmten Alphabet A ist. Die Elemente jeder Sprache sind Worter aus A*.
Christian Wagenknecht, Michael Hielscher
Kapitel 3. Endliche Automaten und reguläre Sprachen
Zusammenfassung
Die Online-Reservierung eines Hotelzimmer ist heute eine sehr einfache Sache: Sofern ein Zimmer im gewünschten Zeitraum verfügbar ist, kann es entweder sofort bezogen (b) oder reserviert (r) werden. Dies wird in Abbildung 3.1 als Zustandsmodell aus der Perspektive eines Hotelzimmers systematisch dargestellt.
Christian Wagenknecht, Michael Hielscher
Kapitel 4. Reguläre Ausdrücke (RA)
Zusammenfassung
Am 2. Juli 2019 traf es Cloudflare: Innerhalb weniger Minuten verlor der Dienstleister 80 Prozent seiner Serverkapazität. Tausende Webseiten waren nicht mehr erreichbar. Dropbox, Cloudbase, Discord, Shopify und Zendesk gehörten zu den betroffenen Cloudflare-Kunden. Cloudflare brauchte Stunden, um die Infrastruktur wieder hochzufahren – alles nur wegen weniger eigentlich korrekter Zeichen.
Christian Wagenknecht, Michael Hielscher
Kapitel 5. Sprachübersetzer
Zusammenfassung
Programme, die Programme einer Quellsprache in zugehörige Programme einer Zielsprache überführen, nennt man Compiler, s. Abschnitt 1.2. Historisch hat sich der Bedarf an Compilern aus der Verwendung höherer, problemorientierter, algorithmischer Programmiersprachen (kurz: Hochsprachen) ergeben: Statt Anwendungsprogramme aus maschinennahen Instruktionen aufzubauen, fügt man leicht lesbare Sprachelemente in syntaktisch korrekter Weise zu einem Programm zusammen. Damit diese Programme von einer „primitiven Zielmaschine“, genauer: einem Prozessor und dem Betriebssystem, verarbeitet werden können, ist eine entsprechende Übersetzung (Compilation) notwendig.
Christian Wagenknecht, Michael Hielscher
Kapitel 6. Kellerautomaten und kontextfreie Sprachen
Zusammenfassung
Endliche Automaten reichen zur Beschreibung beliebiger kontextfreier Sprachen nicht aus. Dies belegen die folgenden Beispielsprachen.
Christian Wagenknecht, Michael Hielscher
Kapitel 7. LL(k)-Sprachen
Zusammenfassung
Aus Kapitel 6 wissen wir, dass
  • Chomsky-Typ-2-Grammatiken und NKAs gleichberechtigte Beschreibungsmittel fur die Klasse der kfS sind, und
  • deterministisch-kontextfreien Sprachen (dkfS), die durch DKAs beschrieben werden, eine echte Untermenge der kontextfreien Sprachen bilden.
Christian Wagenknecht, Michael Hielscher
Kapitel 8. LR(k)-Sprachen
Zusammenfassung
Die im Namen LR(k) verwendeten Abkurzungen haben folgende Bedeutungen.
Christian Wagenknecht, Michael Hielscher
Kapitel 9. Sprachubersetzerprojekte
Zusammenfassung
In Abschnitt 5.2, s. Seite 128, wurde die „klassische Architektur“ eines Compilers beschrieben. Sie besteht aus einem Analyseteil (Parsing eines gegebenen Wortes im Quellcode) und einem Syntheseteil (Zielcodegenerierung).
Christian Wagenknecht, Michael Hielscher
Kapitel 10. TURING-Maschine (TM) und CHOMSKY-Typ-0/1-Sprachen
Zusammenfassung
In den vorangehenden Kapiteln haben wir vor allem reguläre und kontextfreie Sprachen betrachtet. Ihre besondere Bedeutung erwächst aus deren praktischen Anwendungen.
Christian Wagenknecht, Michael Hielscher
Backmatter
Metadaten
Titel
Formale Sprachen, abstrakte Automaten und Compiler
verfasst von
Prof. Dr. Christian Wagenknecht
Dr. Michael Hielscher
Copyright-Jahr
2022
Electronic ISBN
978-3-658-36853-1
Print ISBN
978-3-658-36852-4
DOI
https://doi.org/10.1007/978-3-658-36853-1

Premium Partner