Skip to main content
main-content

Ü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 Modellierung formaler Sprachen, regulärer Ausdrücke, abstrakter Automaten und zur automatisierten Compilergenerierung aus einer grafisch-visuellen Beschreibung stellt AtoCC miteinander vernetzte Komponenten zur Verfügung. Die Lern- und Arbeitsumgebung AtoCC wurde speziell für das Studium der theoretischen Informatik entwickelt und bereits an mehreren Hochschulen und Schulen erfolgreich eingesetzt. AtoCC 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

1. Einleitung

Zur Weihnachtszeit sind Flughäfen oft überfüllt und restlos ausgelastet. Jeder möchte rasch nach Hause in den Kreis der Familie. Weihnachten 2004 ging dieser Wunsch für ca. 30000 Reisende nicht in Erfüllung: Eine US-amerikanische Fluggesellschaft musste über 1100 Flüge streichen. Grund war ein Softwarefehler. Ein enormer Image-Schaden für diese Firma war die Folge.
Christian Wagenknecht, Michael Hielscher

2. Struktur von Programmen

Stößt man auf das Wort „Sprache“, wie im Titel dieses Buches, so denkt man wohl zuerst an die „natürliche Sprache“, d.h. an unsere Muttersprache oder eine Fremdsprache. Eine solche Sprache benutzen wir täglich.Wir verfügen über einen mehr oder weniger breiten Wortschatz und bilden Sätze durch Aneinanderreihung von Worten.
Christian Wagenknecht, Michael Hielscher

3. Grundbegriffe

Formale Sprachen enthalten Wörter. Wörter bestehen aus Zeichen. Sämtliche Zeichen eines Wortes stammen aus genau einem sich nicht erschöpfenden Alphabet.
Christian Wagenknecht, Michael Hielscher

4. Definition unendlicher Mengen

In Abschnitt 3.4 haben wir erfahren, dass eine Sprache L eine endliche oder im Allgemeinen eine abzählbar unendliche Teilmenge der Wortmenge A * über einem bestimmten Alphabet A ist. Die Elemente jeder Sprache sind Wörter aus A *.
Christian Wagenknecht, Michael Hielscher

5. Sprachübersetzer

Programme, die Programme einer Quellsprache in zugehörige Programme einer Zielsprache überführen, nennt man Compiler. Historisch hat sich der Bedarf an Compilern aus der Verwendung von Hochsprachen ergeben: Statt Anwendungsprogramme aus maschinennahen Instruktionen aufzubauen, verwendet man menschenfreundlichere Sprachelemente, um sie zu einem Programm in syntaktisch korrekter Weise zusammenzufügen. Damit diese Programme von einer „primitiven Zielmaschine“, genauer: einem Prozessor und dem Betriebssystem, verarbeitet werden können, ist eine entsprechende Übersetzung notwendig. Compiler sind derartige Übersetzungsprogramme.
Christian Wagenknecht, Michael Hielscher

6. Endliche Automaten und reguläre Sprachen

Aus dem vorhergehenden Kapitel haben wir die Motivation mitgenommen, einfache (Sub-)Sprachen mit (einfachen) Automaten zu beschreiben. Abstrakte Automaten dienen – ebenso wie formale Grammatiken – zur Definition formaler Sprachen, indem sie vorgegebene Wörter als Elemente einer bestimmten Sprache akzeptieren oder ablehnen. Daher werden sie auch Akzeptoren genannt.
Christian Wagenknecht, Michael Hielscher

7. Reguläre Ausdrücke

Reguläre Ausdrücke kennen wir bereits aus der Praxis. Hier wenden wir uns der deren Definition zu. Diese unterscheidet sich in Teilen von jener, die aus Gründen der einfacheren Eingabe per Tastatur in der Praxis verwendet wird.
Christian Wagenknecht, Michael Hielscher

8. Kellerautomaten und kontextfreie Sprachen

Endliche Automaten reichen zur Beschreibung beliebiger kontextfreier Sprachen nicht aus. Dies machen folgende Beispiele klar.
Christian Wagenknecht, Michael Hielscher

9. LL(k)-Sprachen

Aus der Kapitel 8 wissen wir, dass
  • Chomsky-Typ-2-Grammatiken und NKAs gleichberechtigte Beschreibungsmittel für die Klasse der kfS sind, und
  • die sog. deterministisch-kontextfreien Sprachen (dkfS), die durch DKAs beschrieben werden, eine Untermenge der kontextfreien bilden.
Christian Wagenknecht, Michael Hielscher

10. LR(k)-Sprachen

Die im Namen LR(k) verwendeten Abkürzungen haben folgende Bedeutungen:
  • Das erste (ganz links stehende) L steht für „Analyse des Eingabewortes von links nach rechts“. Wie bei DKAs definiert, arbeitet sich der Lesekopf konsequent von links nach rechts voran. Es gibt nicht etwa einen Rückgriff auf frühere Zeichen, etwa durch Zurückfahren (Linksbewegung) des Kopfes auf dem Eingabeband.
Christian Wagenknecht, Michael Hielscher

11. Sprachübersetzerprojekt

In diesem Kapitel soll der gesamten Entwicklungsprozess sowohl eines Interpreter als auch eines Compilers mit AtoCC anhand eines kleinen Projekts durchlaufen werden. Zur Motivation haben wir einen (hoffentlich) interessanten Anwendungsbezug ausgewählt: Es geht um Klingeltöne von Mobiltelefonen, die quasi jeder (vor allem der jüngeren Generation) aus dem Alltag kennt.
Christian Wagenknecht, Michael Hielscher

12. Turing-Maschine (TM) und Chomsky-Typ-0/1-Sprachen

Aus vorangehenden Kapiteln wissen wir, dass kfS mit NKA definiert werden.
Christian Wagenknecht, Michael Hielscher

Backmatter

Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise