Sprachen Material Lehrgang Darstellung reguläre Sprachen kontextfreie Sprachen Chomsky-Hierarchie xml abc Compiler
Pfad: Startseite / Fächer / Informatik / Theorie / Sprachen / reguläre Sprachen
Autor: mk
16.04.2010 08:49
736
reguläre Sprachen und endliche Automaten

Aufgabe 1

In der odt-Datet maier.odt ist immer wieder der Name 'Maier' in verschiedenen Schreibweisen versteckt. Verwende 'Bearbeiten/Suchen&ersetzen' um mittels eines regulären Ausdrucks diese Stellen zu finden. Auf welche Anzahl kommst du?

Anwendung

In der Datei sub00.py soll rx durch r[x] ersetzt werden. Dabei steht x für eine Ziffer. Das lässt sich in Openoffice mit Hilfe von regulären Ausdrücken erledigen. Was sind hier Metazeichen? Was bedeutet $1? Wie muss der reguläre Ausdruck verändert werden, damit x auch eine ganze Zahl sein darf?

Ersetzen von rx durch r[x], x Ziffer

Aufgabe 2

Lade die Datei regex.odt mit OpenOffice und durchsuche sie nach Zeichenketten, die dem regulären Ausdruck [+\-]?[0-9]+(,[0-9]+)? entsprechen. Erläutere den Ausdruck, insbesondere \- . Welche Zeichen in obigem regulären Ausdruck sind Metazeichen?

Aufgabe 3

Lies den Artikel 'Reguläre Sprachen, reguläre Ausdrücke' von Helmut Richter, Leibniz-Rechenzentrum München bis einschließlich Seite 4 (von 16).

Aufgabe 4

Lass dir vom Goldparser zu dem regulären Ausdruck [+-]?[0-9]+(,[0-9]+)? automatisch einen Automaten konstruieren. Gib dazu

Dezimalzahl = [+-]?[0123456789]+(','[0123456789]+)?
"Start Symbol" = <Dezimalzahl>
<Dezimalzahl> ::= Dezimalzahl

ein. Wie geht Goldparser mit dem Metazeichen '-' um? Wozu dient ein Programm wie Goldparser? Teste die Worterkennung an einigen Beispielen. Wie stellt Goldparser den endlichen Automaten zur Token-Entdeckung dar? Wie geht Goldparser mit whitespaces um? Erweitere die Grammatik um 'Bezeichner'.

Dezimalzahl = [+-]?[0123456789]+(','[0123456789]+)?
Bezeichner = {letter}({letter}|{digit})*
"Start Symbol" = <Worte>
<Worte> ::= <Wort><Worte>
<Worte> ::= <Wort>
<Wort> ::= <Dezimalzahl>|<Bezeichner>
<Dezimalzahl> ::= Dezimalzahl
<Bezeichner> ::= Bezeichner

Aufgabe 5

Übersetze den Automaten zur Dezimalzahl-Erkennung nach JFlap und teste ihn. Kürze dabei Zeichenklassen mit einzelnen Buchstaben ab, z.B. z für eine Ziffer

Schreibe in Delphi eine boolesche Funktion is_Dezimalzahl und teste sie. Vorlage: is_real

Aufgabe 6

Wir wollen verstehen, wie der Goldparser es prinzipiell macht, aus einem regulären Ausdruck einen endlichen Automaten zu konstruieren. Dazu sind zunächst folgende Seiten nützlich:

Entwickle nun zu einigen Elementen von regulären Ausdrücken 'Übersetzungsschablonen' zu Automaten. Ziel ist es, einen regulären Ausdruck wie [+-]?[0-9]+(,[0-9]+)? schematisch (mit Hilfe von JFlap) in einen Automaten zu übersetzen.

Aufgabe 6a

erste Ideen zum Scanner:
Für einen einfachen Scanner könnte man sich nun auf die Token 'Bezeichner' (Schlüsselwörter als Bezeichner), 'Zahl', 'Whitespace' beschränken. Das Prinzip sollte gleichbleiben. Aus den zu den Tokens gehörigen DEAs lässt sich nun ein DEA mit mehreren Endzuständen konstruieren, die das Erkennen des entsprechenden Tokens anzeigen. Um das komplette Token zurückgeben zu können, müssen die gelesenen Zeichen in einem Puffer gespeichert werden. Das Ende eines Tokens kann man erst erkennen, wenn das aktuelle Zeichen den Automaten zum Verlassen eines Endzustand veranlasst. Tritt dieses 'Ereignis' (es gibt die Ereignisse 'Bezeichner verlassen', 'Zahl verlassen' usw) ein, so wird ein Eintrag in die Symboltabelle (=Tokentabelle?) gemacht in der Art: Bezeichner|a23|kein Schlüsselwort oder Zahl|-12,34 , allgemein Tokenart|Tokenwert|Zusatz(?). Whitespaces würden zwar erkannt, aber nicht eingetragen werden. Der Tokenwert ergibt sich aus dem Pufferinhalt. Der Puffer wird geleert. Der Automat wird auf den Anfangszustand gesetzt und beginnt mit dem Zeichen, das zur 'Ereignisbehandlung' geführt hat, die weitere Verarbeitung. Ein Übergang in einen Fehlerzustand bricht die Verarbeitung ab. Trifft man auf das Ende der Zeichenkette, so führt das zu einem Fehler oder - wenn der Automat in einem Endzustand war - zu einer abschließenden Ereignisbehanndlung.

Aufgabe 7

Zu jedem regulären Ausdruck gibt es einen zugeordneten Automaten. Gibt es zu jedem Akzeptor auch einen regulären Ausdruck?

Aufgabe 8

Welche Grammatiken beschreiben reguläre Sprachen? Wie hängen diese Grammatiken mit den Automaten zusammen? Hilfe

Aufgabe 9

Reguläre Sprachen sind nicht ausdrucksstark genug. Die Sprache {anbn|n aus IN} ist nicht regulär. Welcher wichtiger Struktur von Programmiersprachen entspricht das?

Links