 |
|||
| HSG |
|
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](anw1.png)
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
- Regulärer Ausdruck -ooowiki
- Metazeichen - wikipedia
- Metasprache - wikipedia
- Regulärer Ausdruck - wikipedia
- Formale Sprache - wikipedia
- Formale Grammatik - wikipedia
- Alphabet - wikipedia
- Token - wikipedia
- Lexikalischer Scanner - wikipedia
- Alphabet - wikipedia
- regulärer Ausdruck in openoffice
- Deterministischer endlicher Automat - wikipedia
- Reguläre Sprache - wikipedia
- Automaten-Baukasten
- NFA --> DFA
- DFA --> Regulärer Ausdruck
- Minimierung eines DFA
- Rechenregeln für reguläre Ausdrücke
- Vereinfachung eines regulären Ausdrucks
- Systematische Erstellung eines Akzeptors
- {anbn|n aus IN} ist nicht regulär