Show HN: Transduktive reguläre Ausdrücke für die Textbearbeitung

 (github.com/c0stya)
1 Punkte von GN⁺ 2025-02-09 | 1 Kommentare | Auf WhatsApp teilen

  • TRRE: transduktive reguläre Ausdrücke

  • Zusammenfassung
    • Eine Erweiterung regulärer Ausdrücke für Textbearbeitung und grep-ähnliche Kommandozeilen-Tools.
    • Es ist ein Prototyp und sollte nicht in produktiven Umgebungen verwendet werden.

  • Einführung

    • Reguläre Ausdrücke sind nützliche Werkzeuge, um Muster in Texten zu suchen.
    • Für die Textbearbeitung wirken sie nicht ganz natürlich, daher wird eine Erweiterung vorgeschlagen.
    • Sie werden transduktive reguläre Ausdrücke oder trre genannt.
    • Mit dem Symbol : werden Transformationen definiert.
    • a:b ist die einfachste Form und ersetzt a durch b.
    • Zur Demonstration des Konzepts wurde ein Kommandozeilen-Tool namens trre erstellt.

  • Beispiele

    • Grundlagen

      • cat in dog ändern: 
        $ echo 'cat' | trre 'c:da:ot:g'
dog
      • Wie bei sed alle Treffer einer Zeichenkette ersetzen: 
        $ echo 'Mary had a little lamb.' | trre '(lamb):(cat)'
Mary had a little cat.
      • Löschen: 
        $ echo 'xor' | trre '(x:)or'
or
      • Einfügen: 
        $ echo 'or' | trre '(:x)or'
xor

    • Reguläre Ausdrücke durch Transformation

      • Verwendung von Alternation: 
        $ echo 'cat dog' | trre 'c:bat|d:hog'
bat hog
      • Mit Star die Transformation wiederholen: 
        $ echo 'catcatcat' | trre '((cat):(dog))*'
dogdogdog

    • Bereichstransformation

      • Transformation von Zeichenbereichen: 
        $ echo "regular expressions" | trre "[a:A-z:Z]"
REGULAR EXPRESSIONS

    • Generator

      • trre kann für eine einzelne Eingabe mehrere Ausgabestrings erzeugen.
      • Binärsequenz: 
        $ echo '' | trre -ma ':(0|1){3}'
000  001  010  011  100  101  110  111

  • Sprachspezifikation

    • trre ist als Paar aus Pattern-Matching:Pattern-Generation definiert.
    • Pattern-Matching kann ein String oder ein regulärer Ausdruck sein.
    • Pattern-Generation ist normalerweise ein String, kann aber auch regex sein.

  • Warum es funktioniert

    • trre konstruiert einen speziellen Automaten namens endlicher Zustandswandler (FST).
    • Ein FST verarbeitet Eingabe-Ausgabe-Paare.

  • Designentscheidungen und offene Fragen

    • Es sind mehrere Entscheidungen nötig, etwa zur Assoziativität und Priorität von : sowie zu implizitem Epsilon.

  • Modi und Gierigkeit

    • trre unterstützt zwei Modi:
      • Scan-Modus (Standard): Transformationen werden sequenziell angewendet.
      • Match-Modus: Der gesamte String wird gegen den Ausdruck geprüft.

  • Determinisierung

    • Der Prozess, einen nichtdeterministischen Automaten in einen deterministischen umzuwandeln, ist wichtig.

  • Leistung

    • Die NFT-Version (nichtdeterministisch) ist etwas langsamer als sed.
    • Bei komplexen Aufgaben kann trre_dft (die deterministische Version) besser als sed abschneiden.

  • TODO

    • Vervollständigung des ERE-Funktionsumfangs, vollständige Unicode-Unterstützung, effiziente Bereichsverarbeitung usw.

  • Literaturhinweise

    • Inspiriert von Artikeln von Russ Cox sowie Arbeiten von Cyril Allauzen und Mehryar Mohri.

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-02-09
Hacker-News-Kommentare

  • Cool, ich bin gespannt, wie sich dieses Projekt weiterentwickelt

    • Die Operatorpriorität wirkt nicht natürlich
    • Es ist seltsam, dass cat:dog als ca(t:d)og statt als (cat):(dog) interpretiert wird

  • XFST (Xerox Finite-State Transducer) wird empfohlen

    • Ein Tool, das seit über 20 Jahren in der Computerlinguistik verwendet wird
    • Es wird ein Beispiel erwähnt, bei dem FST für die morphologische Analyse des Finnischen verwendet wird

  • Rosie Pattern Language wird als Alternative zu Standard-Regular-Expressions empfohlen

  • Es wird die Erfahrung geteilt, 1997 eine Arbeit über Finite-State-Transducer geschrieben zu haben

    • Das Thema war morphologische Analyse und wurde als unterschätztes Thema gesehen
    • Es wird gefragt, ob es richtig ist, die Syntax so festzulegen, dass : stärker bindet als ab

  • Es wirkt nicht ausreichend, wenn man strukturelle Ersetzungen durchführen will

    • Da der reguläre Ausdruck einen Syntaxbaum für den gematchten Teil definiert, wäre es nützlich, allgemeine Transformationen des Baums durchführen zu können

  • Es werden Zweifel an der Behauptung geäußert, dass reguläre Ausdrücke für Textbearbeitung unnatürlich seien

    • Der Zweck des Projekts hängt von dieser Behauptung ab, aber es gibt keine Beispiele
    • Es ist unklar, warum Menschen Schwierigkeiten mit der Verwendung von Gruppen haben
    • Es werden Beispiele benötigt, die erklären, warum die Grammatik dieses Projekts besser sein soll als reguläre Ausdrücke

  • Der C-Code wird für seine große Sauberkeit gelobt

    • Der Link theory.pdf im README ist fehlerhaft und sollte korrigiert werden

  • Es werden Zweifel an dem Rat geäußert, * oder + nicht zu verwenden

    • Das würde die Grammatik zwar komplexer machen, aber es wäre wohl besser, sie trotzdem zuzulassen

  • Das erste Beispiel wirkt seltsam

    • Das Ergebnis von echo 'cat' | trre 'c:da:ot:g' wirkt merkwürdig
    • Es ist schwer zu verstehen, wie der Syntaxbaum aufgebaut wird
    • Die Such-/Ersetzungsweise aus der MS-DOS-Zeit wirkt intuitiver

  • Es wird bezweifelt, dass die Beispiele echte Programmausgaben sind

    • Möglicherweise fehlt das Verständnis der Grammatik, aber die Beispiele wirken fehlerhaft
    • Das Ergebnis von echo 'cat dog' | trre 'c:bat|d:hog' wirkt seltsam