Formale Sprachen, abstrakte Automaten und Compiler | springerprofessional.de

Springer Professional

Top

2014 | Book

Read chapter Read first chapter

Formale Sprachen, abstrakte Automaten und Compiler

Lehr- und Arbeitsbuch für Grundstudium und Fortbildung

Authors: Christian Wagenknecht, Michael Hielscher

Publisher: Springer Fachmedien Wiesbaden

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access

About this book

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.

Advertisement

Table of Contents

Frontmatter

1. Einleitung

Zusammenfassung

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

Zusammenfassung

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

Zusammenfassung

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

Zusammenfassung

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

Zusammenfassung

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

Zusammenfassung

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

Zusammenfassung

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

Zusammenfassung

Endliche Automaten reichen zur Beschreibung beliebiger kontextfreier Sprachen nicht aus. Dies machen folgende Beispiele klar.

Christian Wagenknecht, Michael Hielscher

9. LL(k)-Sprachen

Zusammenfassung

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

Zusammenfassung

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

Zusammenfassung

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

Zusammenfassung

Aus vorangehenden Kapiteln wissen wir, dass kfS mit NKA definiert werden.

Christian Wagenknecht, Michael Hielscher

Backmatter

Title: Formale Sprachen, abstrakte Automaten und Compiler
Authors: Christian Wagenknecht
Michael Hielscher
Copyright Year: 2014
Publisher: Springer Fachmedien Wiesbaden
Electronic ISBN: 978-3-658-02692-9
Print ISBN: 978-3-658-02691-2
DOI: https://doi.org/10.1007/978-3-658-02692-9

Premium Partner