|
Notationskonventionen für reguläre Ausdrücke unter xfst: Termini, Symbole, Operatoren und Befehle
|
| Sana | 02.06.2021 | | Hajmi | 16,93 Kb. | | #14724 |
Notationskonventionen für reguläre Ausdrücke unter XFST:
Termini, Symbole, Operatoren und Befehle
XFST steht für Xerox Finite State Tools. Es handelt sich um eine Sammlung von Programmen, die das Erstellen, Kombinieren und Testen von endlichen Automaten am Computer ermöglichen. Die Tools wurden bereits mit Hinblick auf die Verwendung zur morphologischen Analyse/Generierung konzipiert.
Ein regulärer Ausdruck (regex) definiert eine reguläre Sprache, die implementiert werden kann als Endlicher Automat (engl. FSA)
Ein Paar von 2 Sprachen wird als Relation bezeichnet, d. h. als eine Untermenge des kartesischen Produkts der Elemente der 2 Sprachen. Eine Relation von 2 regulären Sprachen ist ebenfalls regulär. Sie kann implementiert werden als Transduktor (engl. Transducer). Auch eine Relation kann durch einen regulären Ausdruck beschrieben werden. Dabei gilt folgende Konvention: statt , der aus der Mathematik bekannten Darstellung geordneter Paare, wird a:b geschrieben, wobei die linke Seite als die obere Seite, die rechte als die untere Seite der Sprache bezeichnet wird.
Beim Gebrauch von FSA-Technologie für morphologische Analysen bezeichnet
konventionell die Oberseite den Analyse-String, die Unterseite den Oberflächenstring. Jede Sprache kann auch als Identitätsrelation (d. h. bestehend aus Paaren wie a:a, b:b, aa:aa) betrachtet werden.
Leider sehen in XFST viele Symbole für geläufige Finite State-Operationen etwas anders aus als sonst:
?: steht für ein beliebiges Zeichen (abhängig vom betr. Sigma), nicht für Optionalität,.
* und + stehen für Kleene-Star und Kleene-Plus, wie gewohnt.
[ a b c ] eckige Klammern dienen zum Gruppieren statt runder Klammern (a b c).
Runde Klammern (a) stehen für Optionalität.
0 steht für Epsilon, daher steht "0" oder %0 für eine echte 0.
| steht wie gewohnt für die Vereinigung.
A B (mit Abstand) steht für die Konkatenation. (ohne Abstände geschrieben wird „AB“ als spezielles „Multicharacter Symbol“ aufgefasst). Statt A B geht auch {AB}.
~A steht für das Komplement von A, d. h. alle (beliebig langen) Strings, die nicht A sind, bzw. die Subtraktion As von der universalen Sprache = [?* - A].
A&B steht für die Schnittmenge von A und B.
Reguläre Relationen sind unter Subtraktion und Schnitt nicht geschlossen, d. h. das Resultat dieser Operationen ist nicht mehr (generell) regulär.
Deshalb wird v. a. zum Filtern von Relationen nicht der Schnitt, sondern eine andere Operation verwendet, die Komposition (Symbol: .o.).
Komposition ist das "Hintereinanderschalten" (Kaskadieren) von 2 (oder mehr) Transduktoren, wobei die Oberseite des unteren der Unterseite des oberen entspricht.
Bsp.: define A [a:b].o.[b:f]; A ist der Transduktor [a:f]
Noch wichtiger sind die sog. Ersetzungsregeln:
A -> B || C _ D heisst: Ersetze jedes A der Oberseite, das zwischen C und D (auf der Oberseite) steht, auf der Unterseite durch ein B. ( ein .#. in den Kontexten steht für die Wortgrenze).
<- steht für dieselbe Operation in umgekehrter Richtung: von der Unter- zur Oberseite.
[..] -> A wird gebraucht für Epenthese-Regeln (0 wird zu A)
Einige wichtige XFST-Befehle:
up Oberflächenstring = analysiere
down Analysestring = generiere Oberflächenform
read regex X = erzeuge den Transduktor zu X und lege ihn auf den Stack
define Var = weise der Variablen Var den obersten Transduktor auf dem Stack zu
lower = generiere alle Unterseiten-Strings des obersten Transduktors auf dem Stack
words = generiere alle String-Paare des obersten Transduktors auf dem Stack
|
| |
