|
|
[ Zurück ] [ Zurück (Seitenende) ] [ Seitenende ] [ Überkapitel ] [ Bitte Skript-Fehler melden ]
Reguläre Ausdrücke (RA) in XFST
Beispiel 5.2.1 (Einlesen und Kompilieren eines RA mit xfst).
read regex RA ; # EA auf
Stack
define varname RA ; # EA als
Variable
Beziehung zwischen RA, DEA und formalen Sprachen
Zu jedem regulären Ausdruck RA existiert mindestens ein EA, der die vom RA bezeichnete reguläre
Sprache akzeptiert.
|
|
Zulässige Einzelsymbole
Jedes der folgenden alphanumerischen Symbole x bezeichnet als regulärer Ausdruck (RA) die Sprache {x}:
%-geschütztes Zeichensymbol (escape symbol)
Spezialsymbole
Das Zeichen % gefolgt von einem der folgenden Symbole x
0 ? + * | . , : ; - / % ~ ( ) [ ] { } " \
bezeichnet als RA die Sprache {x}.
Hinweise
Mehrzeichensymbol
Jedes Zeichen x zwischen doppelten Hochkommata ausser
\, " und getippter Zeilenwechsel
bezeichnet als RA die Sprache {x}.
Hinweis
Zwischen Hochkommata verlieren alle Zeichen ihre Sonderbedeutung.
Backslash-Notation zwischen doppelten Hochkommata
Backslash-Notation für nicht-druckbare Zeichen
und numerische Zeichenkodes
sind zwischen doppelten Hochkommata möglich.
Hinweise
Symbole aus mehreren Zeichen (multicharacter symbols)
Mehrzeichensymbol
Jede Folge von normalen Zeichen oder %-geschützten Zeichen ist ein Mehrzeichensymbol x, das als RA die Sprache {x} bezeichnet.
Hinweis
Mehrzeichensymbole werden von einem endlichen Automaten in einem einzigen Zustandübergang konsumiert.
Zitierte Mehrzeichensymbole
Auch Mehrzeichensymbole lassen sich mit doppelten Hochkommata zitieren. Es gelten die gleichen
Regeln wie bei den Einzelzeichensymbole. In zitierten Symbolen verliert % seine Rolle als
Escape-Zeichen.
Guter Programmierstil
Epsilon-Symbol
Das Ziffern-Zeichen 0 ist ein Spezial-Symbol, das als RA die Sprache {ϵ} bezeichnet.
Hinweise
Um die Ziffer 0 als Einzelzeichen zu erhalten, muss sie geschützt oder zitiert werden.
Die Sprache {ϵ} kann mit "" oder [] notiert werden.
Any-Symbol
Das Zeichen ? ist ein Spezial-Symbol, das als RA die Sprache aller Zeichenketten aus 1 Symbol
bezeichnet.
Hinweis
Dank der Mehrzeichensymbole ist in xfst der Vorrat an Symbolen (das Alphabet) über den Zeichensatz hinaus unbeschränkt erweiterbar.
Reguläre Operatorenausdrücke in xfst
Wenn die beiden RA A und B die Sprachen A bzw. B bezeichnen, dann bezeichnet der
RA
Beispiel 5.2.9 (Präzedenz von Operatoren). Welcher der beiden RA entspricht dem Zustandsdiagramm?
Klammernotation für Konkatenation
Jeder RA wie {TEXT} steht für die Konkatenation aller Einzelzeichen, die zwischen den geschweiften
Klammern notiert sind: [T E X T].
Beispiel 5.2.10 (xfst und Zustandsdiagramm).
Hinweis
Endliche Automaten speichern Lexika kompakter als Suchbäume (Buchstabenbäume, Trie), weil für die Wörter nicht bloss die gemeinsamen Präfixe, sondern auch die gemeinsamen Suffixe nur einmal repräsentiert sind.
Operatoren für Komplemente
Wenn der RA A die Sprache A über Σ bezeichnet, dann bezeichnet der RA
Universale Sprache, Komplement und Subtraktion
Die Sprache Σ∗ notiert sich in xfst als [ ?* ] und heisst universale Sprache . Für das Sprach-Komplement von A gilt die folgende Äquivalenz
[ ˜ A ] = [?* - A ].
Was gilt für das Komplement des Alphabets?
? als RA-Symbol vs. ? als Kantenbeschriftung in EA
Das ANY-Symbol ? steht als RA für die Sprache aller Zeichenketten der Länge 1.
Im regulären Ausdruck ?*, der die universale Sprache bezeichnet, bedeutet das Fragezeichen nicht dasselbe wie als Kantenbeschriftung. Die Verwendung des gleichen Zeichens für unterschiedliche Zwecke mag verwirren. Die Funktion als Kantenbeschriftung und als regulärer Ausdruck lässt sich aber immer leicht unterscheiden.
Definition 5.2.12 (UNKNOWN-Symbol). Das UNKNOWN-Symbol ? an den Kantenübergängen von EA steht für diejenigen Symbole des Eingabealphabets, welche nicht explizit im xfst-Sigma aufgeführt sind, d.h. noch unbekannt sind.
Wozu kann es nützlich sein, das Alphabet nicht vollständig aufzählen zu müssen?
Operatoren für Enthalten-Sein
Wenn der RA A die Sprache A über Σ bezeichnet, dann bezeichnet der RA
Alle Wörter, welche mindestens ein ’ch’ enthalten, dem ein anderer Buchstabe als ’s’ vorangeht: [$ [ \s c h ]]
Operator für Beschränkung via Kontext (restriction)
Der RA [ A => L _ R ] (expression restriction) restringiert alle Vorkommen von Teilzeichenketten
a aus A. Jedem a muss eine Zeichenkette aus L vorangehen und eine Zeichenkette aus R
nachfolgen.
Beispiel 5.2.14. Die Sprache von [ a => b _ c ] umfasst das Wort back-to-back oder bc, aber nicht das Wort cab oder pack.
Schrittweise Definition von [ A => L _ R ]
define VorAKeinL [~[?* L]] A ?* ;
define NachAKeinR ?* A [~[R ?*]] ;
define WederVorAKeinLNochNachAKeinR ~VorAKeinL & ~NachAKeinR ;
Hinweis
Die Sprache des Restriktions-Ausdrucks schränkt nur diejenigen Zeichenketten ein, welche als Teilzeichenkette ein Wort a aus A enthalten.
Wortende verankern in der Kontext-Beschränkung
Die Spezialmarkierung für Wortende
Die Kontexte in [ A => L _ R ] sind gegen Aussen implizit mit der universalen Sprache konkateniert: [ A => ?* L _ R ?*]. Die Spezialmarkierung .#. bedeutet in den Kontexten Verankerung am Wortende und verhindert so die implizite Verkettung. Im EA ist .#. nicht vorhanden, es kann aber wie ein Symbol in die RA eingefügt werden.
Operator für Beschränkung des Kontexts (restriction)
Der RA [ A <= L _ R ] (context restriction) erlaubt Kontexte aus L gefolgt von R nur, wenn
dazwischen eine Teilzeichenketten a aus A vorkommt.
Beispiel 5.2.16. Die Sprache von [ a <= b _ c ] umfasst das Wort back-to-back oder cb, aber nicht das Wort bc oder bxc.
Hinweis
Der Operator [ A <=> L _ R ] vereinigt die Beschränkungen. A ist ausserhalb von L und R verboten (expression restriction) und der Kontext L _ R ist verboten, ausser ein String aus A steht dazwischen (context restriction).
