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

 (github.com/c0stya)
1 Punkte von GN⁺ 2025-02-09 | 1 Kommentare | Auf WhatsApp teilen
  • TRRE ist eine Spracherweiterung, die regulären Ausdrücken den Operator : hinzufügt, um Texttransformationen direkt auszudrücken. Bereitgestellt wird sie als experimentelles, grep -E-ähnliches CLI-Tool trre.
  • Die Grundform ist ein transduktives Paar, das wie a:b ein Eingabemuster in ein Ausgabemuster umwandelt. Löschen wird als Transformation mit leerem String wie x: dargestellt, Einfügen entsprechend als :x.
  • Wie bei normalen regulären Ausdrücken lassen sich Alternativen, Wiederholungen und Zeichenbereichs-Transformationen verwenden; Beispiele wie cat:dog, [a:A-z:Z] und eine Caesar-Chiffre sind enthalten.
  • Intern baut die Implementierung statt eines FSA für normale reguläre Ausdrücke einen Finite State Transducer (FST) auf, der Eingabe-Ausgabe-Paare verarbeitet; eine experimentelle On-the-fly-Determinierung wird ebenfalls unterstützt.
  • Derzeit gibt es keine vorab gebauten Binaries; man muss selbst bauen. Stabilisierung von DFT, vollständige Unicode-Unterstützung, Vervollständigung der ERE-Funktionen und effiziente Bereichsverarbeitung stehen noch auf der TODO-Liste.

Das Problem, das TRRE lösen will

  • Gewöhnliche reguläre Ausdrücke sind nützlich, um Muster in Texten zu finden, bei der Textbearbeitung kann die Logik zur Gruppenverarbeitung jedoch wie ein Nachbearbeitungsschritt wirken und komplex werden.
  • TRRE erweitert die Sprache regulärer Ausdrücke, um Pattern Matching und Textänderungen in denselben Ausdruck zu bringen.
  • Die Kernsyntax hat die Form pattern-to-match:pattern-to-generate; das einfachste Beispiel ist a:b, das a in b umwandelt.
  • Das CLI-Tool trre ist eine Implementierung, die dieses Konzept demonstriert und sich ähnlich wie grep -E anfühlt.

Grundsyntax für Transformationen

  • String-Ersetzungen werden wie cat:dog geschrieben.
    • echo 'cat' | ./trre 'cat:dog' gibt dog aus.
    • Dasselbe Ergebnis lässt sich auch als zeichenweise Transformation mit (c:d)(a:o)(t:g) erzielen.
  • Wie bei sed kann es genutzt werden, um alle Treffer innerhalb eines Strings zu ersetzen.
    • Wendet man lamb:cat auf Mary had a little lamb. an, wird daraus Mary had a little cat..
  • Löschen wird ausgedrückt, indem die rechte Seite leer bleibt: string_to_delete:.
    • (x:)or entfernt in xor das x und erzeugt or.
    • a: ersetzt im standardmäßigen Scan Mode alle a durch ein leeres Symbol und entfernt sie damit.
    • Mit einer Klammerausdrucksform wie [aie]: lassen sich mehrere Zeichen entfernen.
  • Einfügen wird ausgedrückt, indem die linke Seite leer bleibt: :string_to_insert.
    • (:x)or fügt vor or ein x ein und erzeugt xor.
    • had a (:little )lamb fügt little innerhalb des Kontexts ein.

Transformationen auf regulären Ausdrücken

  • TRRE unterstützt wie normale reguläre Ausdrücke Alternativen mit |.
    • (c:b)at|(d:h)og wandelt cat dog in bat hog um.
  • Wiederholungsoperatoren können ebenfalls auf Transformationen angewendet werden.
    • (cat:dog)* wandelt catcatcat in dogdogdog um.
    • Im standardmäßigen Scan Mode wird bereits cat:dog wiederholt angewendet und erzeugt dasselbe Ergebnis.
  • Nutzt man Wiederholung im linken Muster, können mehrere Eingaben konsumiert und in eine einzelne Ausgabe umgewandelt werden.
    • (cat)*:dog wandelt catcatcat in dog um.
  • Verwendet man * oder + im rechten Muster, kann eine Endlosschleife entstehen.
    • Ausdrücke wie :a* sollte man vermeiden.
    • Wenn eine endliche Wiederholung nötig ist, gibt man die Anzahl an, etwa :(repeat-10-times){10}.

Bereichstransformationen und Generatoren

  • Zeichenbereichs-Transformationen werden wie [a:A-z:Z] geschrieben.
    • Damit lässt sich regular expressions in REGULAR EXPRESSIONS umwandeln.
  • Ein Beispiel für eine Caesar-Chiffre ist enthalten.
    • [a:b-y:zz:a] wandelt caesar cipher in dbftbs djqifs um.
    • [a:zb:a-z:y] wandelt dies wieder zurück in caesar cipher.
  • Wie ein Generator kann aus einer einzelnen Eingabe auch mehrere Ausgaben erzeugt werden.
    • Standardmäßig wird der erste mögliche Treffer verwendet.
    • Mit der Option -a werden alle möglichen Ausgaben erzeugt.
  • Wendet man etwa :(0|1){3} auf eine leere Eingabe an, lassen sich 3-Bit-Binärsequenzen von 000 bis 111 erzeugen.
  • Kombiniert man :(0|1){,3}? mit -ma, entstehen Ausgaben in Form von Teilmengen mit Länge höchstens 3.

Sprachspezifikation und Operatorpräzedenz

  • Informell ist TRRE als Paar pattern-to-match:pattern-to-generate definiert.
  • Das linke pattern-to-match kann ein String oder ein regulärer Ausdruck sein.
  • Das rechte pattern-to-generate ist üblicherweise ein String, kann aber ebenfalls ein regulärer Ausdruck sein.
  • Der Operator : wird derzeit als nicht assoziativ behandelt; eine Form TRRE:TRRE ist syntaktisch nicht erlaubt.
    • Diese Form hätte zwar die natürliche Bedeutung einer Komposition der von TRRE definierten Relationen, könnte aber die Komplexität erhöhen und ist daher noch ausgeschlossen.
  • Die Operatorpräzedenz ist von hoch nach niedrig wie folgt:
    • Escape-Zeichen \
    • Klammerausdrücke []
    • Gruppierung ()
    • Wiederholung * + ? {m,n}
    • Konkatenation
    • Transduktion :
    • Alternative |

Modi und Gierigkeit

  • trre unterstützt zwei Modi.
    • Scan Mode: der Standardmodus, in dem Transformationen sequenziell angewendet werden.
    • Match Mode: wird mit dem Flag -m verwendet und prüft, ob der gesamte String zum Ausdruck passt.
  • Die Option -a erzeugt alle möglichen Ausgaben.
  • Der Modifikator ? macht die Operatoren *, + und {,} non-greedy.
    • <(.:)*> gibt bei <cat><dog> <> aus.
    • <(.:)*?> gibt bei derselben Eingabe <><> aus.
  • Beispiele zum Ändern von Inhalten innerhalb von Tags oder Klammern sind ebenfalls enthalten.
    • <(.*?:cat)> wandelt <dog> <mouse> in <cat> <cat> um.

FST-basierte Implementierung und Determinierung

  • TRRE baut intern einen Finite State Transducer (FST) auf.
  • Ein FST ähnelt einem Finite State Automaton (FSA), wie es bei normalen regulären Ausdrücken verwendet wird, verarbeitet aber statt einfacher Strings Eingabe-Ausgabe-Paare.
  • Die wichtigsten Unterschiede von TRRE sind:
    • Es definiert eine binäre Relation zwischen zwei regulären Sprachen.
    • Für die Inferenz wird statt eines FSA ein FST verwendet.
    • Für die Performance wird experimentelle On-the-fly-Determinierung unterstützt.
  • In regulären Regex-Engines ermöglicht Determinierung, nichtdeterministische Automaten in deterministische Automaten umzuwandeln und so Inferenz in linearer Zeit bezogen auf die Länge des Eingabestrings zu erreichen.
  • Auch bei TRRE ist ein ähnlicher Ansatz möglich, aber nicht jeder nichtdeterministische Transducer NFT lässt sich in einen deterministischen Transducer DFT umwandeln.
    • Wenn es zwei „bad“ Cycles mit demselben Eingabelabel gibt, kann die Zustandserzeugung in eine Endlosschleife geraten.
    • Es gibt Methoden, solche Schleifen zu erkennen, sie sind aber teuer.

Performance und Installationsstatus

  • Für einfache Ersetzungen wird ein Beispiel gezeigt, in dem die standardmäßige nichtdeterministische Version etwas langsamer als sed ist.
    • ./trre '(vodka):(VODKA)': real 0m0.046s
    • sed 's/vodka/VODKA/': real 0m0.024s
  • Für komplexere Aufgaben gibt es ein Beispiel, in dem die deterministische Version trre_dft schneller als sed ist.
    • sed -e 's/\(.*\)/\U\1/': real 0m0.508s
    • ./trre_dft '[a:A-z:Z]': real 0m0.131s
  • Vorab gebaute Binaries werden noch nicht bereitgestellt.
  • Zur Installation klont man das Repository und baut sowie testet es mit make && sh test.sh.
  • Auf der TODO-Liste stehen noch folgende Punkte:
    • stabile DFT-Version
    • vollständige Unicode-Unterstützung
    • Vervollständigung der ERE-Funktionen
      • Negation ^ innerhalb von []
      • Zeichenklassen
      • Ankersymbole $^
    • effiziente Bereichsverarbeitung

Referenzierte Ansätze

Verwandte Beiträge

1 Kommentare

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

  • Ich bin gespannt, wohin dieses Projekt führt. Allerdings wirkt die Operatorpräzedenz unnatürlich, und andere in diesem Thread scheinen ähnlich zu empfinden.
    Bei cat:dog erwartet man intuitiv, dass es wie (cat):(dog) ist, nicht wie ca(t:d)og.

    • In vielerlei Hinsicht eine interessante Idee.
      Dass cat:dog nicht als (cat):(dog), sondern als ca(t:d)og interpretiert wird, hat mich auch verwirrt. Wenn man sich aber vor Augen führt, dass wir alle reguläre Ausdrücke ein wenig falsch verwenden, ergibt es Sinn. Reguläre Ausdrücke sollte man „eigentlich“ nicht als Matcher, sondern als String-Generatoren betrachten; formal kann man cat|dog daher als Erweiterung zu einer Menge wie {catog,cadog} auffassen.
      Beim Matching nimmt man dann diese String-Menge und führt ein Substring-Matching gegen einen größeren Text durch. Das Problem ist, dass die meisten realen Regex-Engines nicht so funktionieren und aus Gründen der Erwartungskonformität oder Effizienz allerlei seltsame Verhaltensweisen haben.
      Wenn man verschiedene Regex-Tools ausprobiert, kommen Varianten wie (cat)|(dog) oder (cat)|(dog)|(ca[td]og) heraus. Aus einer formelleren Sicht ist es daher meiner Meinung nach korrekt, dass cat:dog ca(t:d)og erzeugt und nicht (cat):(dog). Aber weil wir reguläre Ausdrücke jahrzehntelang als Matching-Werkzeuge missbraucht haben, die auf Nutzererwartungen zugeschnitten sind, setzen inzwischen alle Klammern um den Ausdruck, den sie ersetzen wollen.
      Dieser Vorschlag ist interessant und gut gestaltet, fühlt sich aber letztlich so an, als wolle er reguläre Ausdrücke zu ihrem ursprünglichen Generator-Modell zurückführen. Das Problem liegt weniger in der Grammatik als in den Werkzeugen.
      Ich habe früher etwas in diesem Umfeld gemacht; wenn man reguläre Ausdrücke noch nie als Generatoren von String-Mengen betrachtet hat, kann man hier damit herumspielen: https://onlinestringtools.com/generate-string-from-regex
      Allerdings ist auch das Verhalten solcher Generator-Tools sehr spezifisch. Die Tools, die ich verwendet habe, hatten verschiedene Möglichkeiten, den Generator einzuschränken, etwa durch Vorgaben für Closures.
    • Danke für das Feedback; über die Präzedenz denke ich selbst noch nach, sie könnte sich also ändern.
      Wenn man sie hinter die Konkatenation verschiebt, können andere Probleme entstehen. Zum Beispiel müsste bei einem nicht-assoziativen : vielleicht cat:dog:mouse illegal sein; ich bin mir nicht sicher, wie man damit umgehen sollte.
      In der aktuellen Version wird Epsilon, also der leere String, eingefügt. Wenn man zum Beispiel jedes zweite Zeichen überspringend entfernen will, kann man technisch ..: ausführen, also .(.:eps).
      Das Ergebnis von echo 'abcde' | ./trre '..:' ist 'ace'.
      Eigentlich könnte die :-Verknüpfung auch die Bedeutung einer Komposition regulärer Relationen haben, aber das erschien mir im Moment zu komplex.
    • Bereichstransformationen sind ähnlich. Statt [a:A-z:Z] wäre [a-z:A-Z] besser; und statt [a:b-y:zz:a] würde ich eine Form wie [a-y:b-z;z:a] vorschlagen.

  • Wenn dich endliche Transduktoren und verwandte Werkzeuge interessieren, lohnt sich ein Blick auf XFST (Xerox Finite-State Transducer). Es wird seit über 20 Jahren in Anwendungen der Computerlinguistik eingesetzt.
    Ein finnischer Forscher von PARC kam einmal in eine UT-Vorlesung und zeigte, wie man mit FSTs finnische Morphologie verarbeitet; schon oberflächlich betrachtet war das ziemlich beeindruckend.

    • Das wollte ich auch erwähnen. Link zum Kaplan-Paper: https://aclanthology.org/J94-3001.pdf
      Es beschreibt die Arbeit, die bei PARC gemacht wurde.
    • http://hfst.github.io/ ist die moderne Open-Source-Version von XFST. Es umfasst foma und OpenFst und dürfte fast alles können, was trre macht, und noch mehr.
    • Pynini könnte ebenfalls interessant sein. Es ist ein Python-Wrapper für OpenFst und bringt viele Komfortfunktionen mit.
      OpenFst ist eine wirklich hervorragende Bibliothek für Transduktoren. Auch die Pynini-Tutorials mit Anwendungsfällen, die unter anderem bei Johns Hopkins als Aufgaben erstellt wurden, sind recht gut.
      [1] https://www.openfst.org/twiki/bin/view/GRM/Pynini
      [2] https://www.openfst.org/

  • Wenn du nach einer Alternative zu Standard-Regex suchst, insbesondere wenn Gruppenlogik schwierig ist oder du wartbare Ausdrücke möchtest, könnte die Rosie Pattern Language passen.
    https://gitlab.com/rosie-pattern-language/rosie/-/blob/maste...
    https://rosie-lang.org/about/

  • Cool. Um 1997 herum habe ich meine Informatik-Diplomarbeit über endliche Transduktoren geschrieben, und es war deutlich weniger trivial, als ich erwartet hatte.
    Die Aufgabe bestand darin, Komposition und DFA zu implementieren, wo möglich, einschließlich zusammengesetzter Transduktoren. Es ging um die „Algebra endlicher Transduktoren“, der Anwendungsfall war Morphologie. Das Thema war stark unterschätzt, sodass ich etwa in der Mitte aufhören musste. Daher: Respekt.
    Zur Syntax frage ich mich, ob du wirklich möchtest, dass : stärker bindet als die Konkatenation ab.

    • Anfang der 2000er habe ich OpenFST in der Bioinformatik verwendet. Zum Herumspielen war es interessant, aber für meine damalige Arbeit letztlich nicht nützlich.
      Schön zu sehen, dass das Projekt 20 Jahre später immer noch weiterläuft: https://www.openfst.org/twiki/bin/view/FST/WebHome
    • Den Abschluss faktisch davon abhängig zu machen, ob man „Regex stark genug bearbeiten kann“, ist eine ziemlich kühne Entscheidung.
    • Stimmt. Transduktoren sind ein sehr altes Thema. Aus irgendeinem Grund waren sie nie so stark mit bestimmten Sprachen verknüpft wie reguläre Ausdrücke.
      Ob : stärker binden sollte als Konkatenation, weiß ich noch nicht sicher. Ich habe mir etwa 100 Beispiele angesehen und fand die aktuelle Variante, also dass : niedriger bindet als ., natürlicher; im Code lässt sich das aber buchstäblich durch Ändern einer einzigen Zahl umstellen. Deshalb habe ich es hier gepostet: Ich brauche echtes Feedback.

  • Sobald man irgendeine Art von struktureller Ersetzung vornehmen möchte, wirkt dieser Ansatz nicht mehr ausreichend. Zum Beispiel möchte man manchmal so etwas wie s/"([^"]*)"/'$1'/ machen
    Darüber hinaus wäre es nützlicher, wenn man innerhalb von [^"] das, was auf ['] matcht, durch \' ersetzen könnte
    Allgemeiner gesagt: Da ein regulärer Ausdruck für das Matchergebnis faktisch einen Parse Tree definiert, wäre es nützlich, allgemeinere Transformationen auf diesem Baum durchführen zu können

    • Wenn ich es richtig verstanden habe, erledigt der folgende ttre-Ausdruck das Gewünschte:
      ":'(':(\\')|[^"'])*":'
    • Wenn ich es richtig verstanden habe, möchtest du den Inhalt innerhalb eines "..."-Blocks ändern und die Anführungszeichen in einfache Anführungszeichen ' umwandeln
      Das geht mit diesem Ausdruck:
      echo '"hello world" "hello again!"' | ./trre "\":'.+?:-\":'"
      Das Ergebnis ist '-' '-'
      Das heißt, mit dem Ausdruck ".+?:-" wird der Text innerhalb von "" durch das Zeichen - ersetzt und zugleich werden die umgebenden Anführungszeichen geändert. Das Fragezeichen bedeutet nicht-gieriger Modus

  • Die Behauptung „Reguläre Ausdrücke sind ein hervorragendes Werkzeug, um Muster in Text zu finden, fühlten sich für das Bearbeiten von Text aber immer unnatürlich an“ scheint das ganze Projekt zu tragen, aber es gibt kein einziges Beispiel
    Ich verstehe nicht, warum reguläre Ausdrücke fürs Bearbeiten unnatürlich sein sollen. Ich weiß auch nicht, was hier mit Bearbeiten gemeint ist, und auch nicht, warum Leute mit Gruppen Schwierigkeiten haben
    Dieses Projekt hat viele Syntaxbeispiele, aber ich sehe nicht, warum es besser sein soll als normale reguläre Ausdrücke. Mit ein paar Beispielen nach dem Muster „die Standard-Regex-Version sieht so aus, meine Version so, und deshalb wird es einfacher“ könnte ich das Projekt vermutlich verstehen

    • Reguläre Ausdrücke haben meiner Meinung nach meist den Charakter von einmal schreiben und nie wieder anfassen. Einen Prototyp zu bauen, der darüber hinausblickt, ist eine gute Möglichkeit, eine bessere Zukunft in diesem Bereich zu erkunden
    • Berechtigter Punkt. Das klarste Beispiel ist, wenn man nur innerhalb eines Kontexts ersetzen muss
      Wenn man zum Beispiel nur das y zwischen x und z durch Y ersetzen möchte, würde man das in Python ungefähr so machen:
      pattern = r'(x)y(z)'
      replacement = r'\1Y\2'
      result = re.sub(pattern, replacement, text)
      Ich würde das gern durch das Muster xy:Yz ersetzen:
      result = re.trre('xy:Yz', text)
      Wenn x und z komplexere Muster oder selbst reguläre Ausdrücke sind, kann dieser Ansatz bequemer sein
    • Es ist wohl richtig zu sagen, dass reguläre Ausdrücke allein keine Bearbeitungsfunktion bereitstellen. Es gibt Gruppen, aber um diese Gruppen zusammenzusetzen, muss man eine andere Sprache wie sed verwenden
    • Es geht um Ersetzung. Mit der Syntax des Autors lassen sich Ersetzungen ausdrücken, wörtlich gesagt eintippen, leichter
      Gutes Projekt

  • Der C-Code macht wirklich Spaß zu lesen. Sehr schön, ich lese ihn gerade
    Nur ein kurzer Kommentar: Der Link zu theory.pdf im README ist kaputt. Das PDF liegt im Verzeichnis docs/, daher muss in die URL nur docs/ aufgenommen werden

    • Danke für das Feedback und den Hinweis auf den Tippfehler. Ist behoben. Tatsächlich sind meine C-Kenntnisse ziemlich eingerostet, daher bin ich etwas unsicher

  • Es heißt, man solle * oder + auf der rechten Seite vermeiden, weil das zu Endlosschleifen führen kann. Könnte man das nicht einfach verbieten?
    Ich verstehe, dass die Syntax-Spezifikation dadurch schwieriger wird, aber ich sehe keinen guten Grund, es beizubehalten

    • Berechtigter Punkt, und ich stimme zu. Im Moment wäre es wohl besser, das zu deaktivieren
      Der ursprüngliche Grund war, dass ich eine interessante Operation namens Komposition von Transducern implementieren wollte. Man kann einfache Operationen auf Strings ausführen und trre wie Filter zusammensetzen, aber ich habe das noch nicht fertiggestellt. Daher ist der Einwand absolut berechtigt

  • Spannende Erkundung, aber es fehlen Beispiele dafür, warum es in der Praxis besser ist. Natürlich kann es auch sein, dass ich mich einfach zu lange an reguläre Ausdrücke gewöhnt habe
    Zum Beispiel sehe ich nicht, warum (cat):(dog) in trre besser ist als s/cat/dog, oder was an (x:)or besser ist als s/xor/or. Fast alle Beispiele lassen sich in meinem Kopf relativ leicht auf reguläre Ausdrücke abbilden
    Wenn es einen zentralen Vorteil gibt, dann vermutlich bei der Gruppenlogik, daher wäre es gut, wenn sich die Beispiele darauf konzentrieren würden. Es scheint besser, zuerst zu erklären, warum das die bessere Wahl ist, noch bevor man die Grundsyntax erklärt
    Beim Caesar-Chiffre-Beispiel wirkt die Funktion „das rückwärts anwenden“ sehr nötig. Das ist eine häufige Anforderung bei vielen Textersetzungen und in diesem Beispiel besonders klar. Der Programmiererkopf ruft sofort: „Warum muss ich dieselbe Logik zweimal ausdrücken?“
    Ich weiß noch nicht, ob es nützlich ist, aber Alternativen zu einem lange etablierten Status quo zu erkunden, ist großartig. Solche Versuche haben zwar oft eine hohe Wahrscheinlichkeit, nicht erfolgreich zu sein, aber die Erkundung an sich ist schön anzusehen

  • Die Spezifikation wirkt ziemlich unvollständig. Schon das erste Beispiel ist seltsam:
    $ echo 'cat' | trre 'c:da:ot:g'
    dog
    Ich verstehe nicht, was hier passiert. Die Grammatik sieht so aus:
    TRRE <- TRRE* TRRE|TRRE TRRE.TRRE
    TRRE <- REGEX REGEX:REGEX
    Was ist hier der Parse Tree? Warum wird c nicht zu da? Oder warum wird c nicht entfernt und da zu ot geändert?
    Die Idee, eine intuitivere Such-/Ersetzungssemantik als Gruppenoperatoren zu haben, ist gut. Zu MS-DOS-Zeiten konnte man Dinge wie ren .log .txt machen, und es funktionierte; aus heutiger Bash-Denkweise ergibt das keinen Sinn, aber auf den ersten Blick war die Absicht sehr klar.

    • Das ist ein Problem der Operatorpräzedenz und der Tokenisierung. In dieser Sprache sind Tokens einzelne Zeichen, und zwischen den Zeichen gibt es einen unsichtbaren Operator.
      Wenn man diesen Operator explizit ~ nennt, sieht das Beispiel so aus:
      $ echo 'cat' | trre 'c:d~a:o~t:g'
      dog
      Mit überflüssigen Klammern sieht es so aus:
      $ echo 'cat' | trre '(c:d)~(a:o)~(t:g)'
      dog
    • Die Grammatik ist in der Spezifikation unvollständig. Die vollständige Grammatik ist komplexer. Die aktuelle Version sollte wohl aus der Dokumentation entfernt werden; im Moment sorgt sie tatsächlich für Verwirrung.
      Dass c nicht zu da wird, liegt ausschließlich an der Präzedenz. Wenn ich mir diese Diskussion ansehe, habe ich wohl die falsche Präzedenz gewählt, und das stiftet Verwirrung.
      Die aktuelle Präzedenz-Tabelle sieht so aus:
      | 1 | Escape-Zeichen | \ |
      | 2 | Klammerausdruck | [] |
      | 3 | Gruppierung | () |
      | 4 | Wiederholung einzelner Zeichen in ERE | * + ? {m,n} |
      | 5 | Transformation | : |
      | 6 | Verkettung | . (implizit) |
      | 8 | Alternative | | |
      Daher bindet : stärker als ., also die implizite Verkettung.
    • Stimmt, die Spezifikation ist unvollständig. Das Löschbeispiel zeigt, dass auch der leere String ein REGEX sein kann. Dann kann man im Grunde an jeder Position beliebig viele leere String-Regexe annehmen, wodurch es unendlich viele Parses gibt.
      Wenn man stattdessen verlangt, dass Regexe nicht leer sein dürfen, geht das Löschbeispiel kaputt, aber die Mehrdeutigkeit verschiebt sich zur Verkettung: Es ist dann unklar, ob es (((c:d)(a:o))(t:g)) oder ((c:d)((a:o)(d:g))) ist. Wenn man Assoziativität annimmt, dürfte dieser Unterschied keine Rolle spielen.
    • Vom Verhalten her wirkt es wie c:d, a: – also nichts – und ot:g.
      Aber beim erneuten Lesen ist es definitiv verwirrend, und theoretisch ist der Einwand berechtigt. Nachdem ich das Repository gelesen hatte, war ich selbst der Meinung, dass c zu da werden müsste, aber sicher bin ich mir nicht.