von WoNáDo
In Teil 8 dreht sich alles um die dynamischen Relativbezüge. Darunter verstehe ich die in der Beschreibung von Oniguruma unter back reference with nest level aufgeführten Möglichkeiten, dynamisch auf den Wert eines Untermusters, benannt oder unbenannt, zugreifen zu können, wobei man die gewünschte relative Stack-Position angeben kann. Alle diesbezüglichen Unklarheiten kann dieser Artikel (hoffentlich) beseitigen.
Die vollständige Beschreibung der in Oniguruma vorhandenen Möglichkeiten für reguläre Ausdrücke befindet sich hier.
Auch diesmal wieder die Anmerkung, dass die Beispiele nur als erklärende Programme für die betrachteten regulären Ausdrücke dienen. Gerade im Zusammenhang mit den dynamischen Relativbezügen lassen sich nicht leicht Beispiele finden, für die man diese Technik wirklich benötigt - aber vielleicht fällt ja jemandem, der das hier liest, eine Killer-Anwendung ein.
Nun aber los.
Nachfolgend der Teil der Oniguruma-Dokumentation, der die entsprechenden Elemente beschreibt. Die beiden zugehörigen Beispiele stehen dort ohne Erklärung, weshalb ich sie hier weglasse. Das erste der beiden stammt aus dem Teil 5 dieser Serie und führte dazu, dass diese Konstruktionen in Oniguruma eingeführt wurden, wobei die jetzige Form weit über die ursprüngliche Anforderung hinausging. Auf dieses Beispiel werde ich anschliessend noch einmal kurz eingehen.
8. Back reference
...
back reference with nest level
level: 0, 1, 2, ...
\k< n+level> (n >= 1)
\k< n-level> (n >= 1)
\k'n+level' (n >= 1)
\k'n-level' (n >= 1)
\k< name+level>
\k< name-level>
\k'name+level'
\k'name-level'
Destinate relative nest level from back reference position.
Diese dynamischen Relativbezüge lösen ein Problem, welches bei Programmiersprachen wie Ruby praktisch unbekannt ist. Die Oniguruma-Möglichkeit, durch \g< sub> einen Unterausdruck eines regulären Ausdrucks quasi als Unterprogramm auch rekursiv aufzurufen zu können, sollte doch im Prinzip wie bei folgendem Ruby-Programm funktionieren.
1 2 3 4 5 6 7 8 9 10 |
def a x = 42 b() puts "x in a: #{x}" end def b x = 84 puts "x in b: #{x}" end a() |
Die Ausgabe ist wie erwartet.
x in b: 84 x in a: 42
Leider funktioniert das aber nicht so, da bei diesen erweiterten regulären Ausdrücken alle Gruppennamen oder -nummern global gelten. Das entsprechende Ruby-Programm ist dann ein anderes.
1 2 3 4 5 6 7 8 9 10 |
def a $x = 42 b() puts "$x in a: #{$x}" end def b $x = 84 puts "$x in b: #{$x}" end a() |
Das Ergebnis ist dementsprechend.
$x in b: 84 $x in a: 84
Für die Palidromsuche begann ich zuerst einmal mit einem rekursiven Muster.
(?<o>|\w|(?:(?<i>\w)\g<o>\k<i>)) |
Interessant ist dabei die letzte Alternative, die auch den rekursiven Aufruf durch \g< o> enthaelt. Hier suche ich ein Wortzeichen in einer benannten Gruppe (?< i>\w), welches ich nach dem Aufruf mittels \k< i> noch einmal benötige. Dies funktioniert nun leider deshalb nicht, weil während des rekursiven Aufrufs diese Gruppe bei längeren Palindromen noch einmal ausgeführt wird, wodurch sich der zugeordnete Wert verändert.
Meine damalige Anfrage an das Oniguruma-Team betraf dieses Problem. Ich benötigte eine Möglichkeit auf die Ergebnisse von Gruppen innerhalb des gleichen Aufrufniveaus zugreifen zu können, quasi wie bei lokalen Variablen. Oniguruma wurde dann insoweit erweitert, dass diese Möglichkeit ein Spezialfall wurde, den ich in den Palidrombeispielen in Teil 5 dieser Serie benutzte (näheres dazu findet sich dort).
(?<o>|\w|(?:(?<i>\w)\g<o>\k<i-0>)) |
Die allgemeinen neuen Konstruktionen fand ich ehrlich gesagt etwas verwirrend. Nachdem mir inzwischen die Möglichkeiten klar geworden sind, bleibe ich trotzdem ein wenig skeptisch, weil es ausgesprochen unübersichtlich bleibt, auf was denn zugegriffen wird. Bei den Ruby-Beispielen würde es in etwas bedeuten, dass man anhand der relativen Aufruftiefe auf Variablen anderer, auch schon beendeter Methoden, wild zugreifen könnte. Das Problem liegt natürlich darin begründet, dass reguläre Ausdrücke mit rekursiven Unterprogrammtechniken für Untergruppierungen eher schwierig zusammenpassen.
Bei etwas komplexeren dynamischen Relativbezügen stellte ich schnell fest, dass ich ohne strukturierte Hilfsmittel nicht weiterkam. Es war für alle Beispiele, auch die nachfolgenden, anfangs ein Ratespiel mit Experimenten, welches relative Niveau ich denn einsetzen muss. Ich habe mir darum eine Notation überlegt, die zumindest dann hilfreich ist, wenn Backtracking nicht berücksichtigt werden muss. Sie ist mit Sicherheit nicht einmal annähernd der Weisheit letzter Schluss, aber ich kam damit schon etwas weiter. Bevor ich zu den regulären Ausdrücken komme erkläre ich deshalb erst einmal diese Notation.
Text: Hier stehen die konsumierten Zeichen
5: Links stehen die Aufrufniveaus.
4: Bei 0 begint die Ausführung des
3: regulären Ausdrucks, jedes \g<...>
2: führt auf eine höhere Stufe und
1: jedes (implizite) return führt auf
0: die nächstniedrigere Stufe
Step: a b c d e f g h i j k l m n o p q r s t
Durch die Buchstaben a bis t wird die
Abarbeitungsreichenfolge innerhalb des
regulären Ausdrucks dargestellt
In der ersten Zeile stehen hinter dem Label Text: die während der Ausführung durch den regulären Ausdruck konsumierten Zeichen und zwar in der Reihenfolge und an der Stelle, an der sie genommen wurden (siehe weiter unten). Weitere Zeilen beginnen mit einer Ziffer, gefolgt von einem Doppelpunkt. Jede Zeile repräsentiert ein Aufrufniveau während des Pattern-Matching-Prozesses (=Anwendung des regulären Ausdrucks auf einen String). Die letzte Zeile enthält immer die Buchstabenfolge a bis t (bei Bedarf auch mehr oder weniger), durch die die Ausführungsreihenfolge dargestellt wird. Dadurch kann ich mich beispielsweise im Text zu einem Beispiel auf den achten Arbeitsschritt im Niveau vier einfach durch h4 beziehen.
Text: 5: In diesem Bereich stehen die 4: jeweiligen Aktionen, die durch 3: die Ausführung des regulären 2: Ausdrucks angestossen werden. 1: 0: Step: a b c d e f g h i j k l m n o p q r s t
In dem Bereich, der rechts von den Niveaubezeichnern 0: bis 5: steht (mehr benötige ich für die Beispiele nicht) stehen die jeweiligen Aktionen, die in der nachfolgenden Liste beschrieben sind.
. -> Die Ausführung des regulären Ausdrucks
verarbeitet ein Zeichen. Das Zeichen ist
bei "Text" aufgeführt.
> -> Es wird das benannte Untermuster "x" durch
x "\g" ausgeführt. Die Ausführung beginnt
an der durch ">" gekennzeichneten Stelle
ein Niveau höher.
< -> Die Ausführung eines Untermusters wird
beendet. Die weitere Ausführung erfolgt ein
Niveau tiefer unter diesem Symbol.
$ -> Die Ausführung wird beendet.
x:m-n -> Es wird der Wert des benannten Untermusters
x:m+n "x" benötigt, und zwar von einem bestimmten
Niveau. "m" ist dabei das Niveau, auf dem
dieser Ausdruck steht und "+/-n" die Angabe
in diesem Ausdruck. Das gesuchte Niveau
ergibt sich ganz einfach durch Ausführung
der Addition/Subtrakton.
Ich hoffe, dass diese Kurzbeschreibung ausreicht die nachfolgenden Beispiele zu verstehen.
Wie alle nachfolgenden Beispiele ist auch dieses ohne einen Gedanken an praktische Anwendung entstanden. Es dient ausschliesslich Demonstrationszwecken. Ich will mit dem Muster eine Sequenz von jeweils einem Buchstaben und einer Ziffer, die in runde Klamern eingeschlossenen sind, abgeschlossen von einem Buchstaben und einer Ziffer in eckigen Klammern suchen, wobei in diesem Beispiel der Buchstabe, der in der letzten runden Klammerung vorkommt auch in der abschliessenden eckigen auftreten soll. Da ich das Beispiel (wie auch alle weiteren) ausführlich kommentiert habe, sollte es niemandem, der die bisherigen Teile der Serie verstanden hat, grössere Probleme bereiten - bis auf das \k< c-0>, um das sich aber letztendlich dieser ganze Artikel dreht.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
p '(y1)(x2)[x3]'.match(/(?<c> # Definition Untermuster <c> [a-z] # Erkenne Kleinbuchstaben ){0} # Ende Untermuster <c> (?<b> # Definition Untermuster <b> \g<c> # Aufruf von Untermuster <c> [0-9] # Erkenne Ziffer \) # Erkenne "Klammer zu" \g<a> # Aufruf von Untermuster <a> ){0} # Ende Untermuster <b> (?<a> # Definition Untermuster <a> \( # Erkenne "Klammer auf" \g<b> # Aufruf von Untermuster <b> | # Oder \[ # Erkenne "Eckige Klammer auf" # ****************************************** \k<c-0> # Erkenne von Untermuster <c> auf # gleichem Aufrufniveau gefundenen # String # ****************************************** [0-9] # Erkenne Ziffer \] # Erkenne "Eckige Klammer zu" ){0} # Ende Untermuster <a> # Hauptmuster \A # Erkenne Stringanfang \g<a> # Aufruf von Untermuster <a> \z # Erkenne Stringende /x) # Musterende # Ergebnis: # => #<MatchData "(y1)(x2)[x3]" c:"x" b:"y1)(x2)[x3]" a:"(y1)(x2)[x3]"> |
Zwei Fragen ergeben sich hier sofort. Erstens die, warum bei \k< c-0> die Null steht, zweitens, warum die mit b benannte Gruppe nach der Abarbeitung den Wert y1)(x2)[x3] hat. Schauen wir uns deshalb mal das zum Beispiel gehörende Ausführungsdiagramm an.
Text: ( y 1 ) ( x 2 ) [ x 3 ] 5: > . < > . c:5-0 . . < 4: > c . . a < 3: > . < > . b < 2: > c . . a < 1: > . b < 0: a $ Step: a b c d e f g h i j k l m n o p q r s t
Im Hauptmuster, wo die Abarbeitung beginnt, ist die erste nennenswerte Aktion der Aufruf der Gruppe a, was an Position a0 steht. Die Abarbeitung beginnt direkt darüber an Position a1, gekennzeichnet durch >. Als nächstes wird eine öffnende Klammer verlangt, was durch den Punkt an Position b1 und die hinter dem Label Text: an dieser Position stehende öffnende Klammer dokumentiert ist. Ich hoffe, dass das Prinzip der Darstellung jetzt klar ist, ich also nicht seitenweise alle Einzelschritte durchgehen muss.
Der nächste Neues bringende Schritt befindet sich an Position f3, nämlich das implizite Return nach dem Ende des Aufrufs von Gruppe c (Position d2 und d3). Hierbei wird nicht nur zum nächsten Element der den Aufruf enthaltenden Gruppe gegangen (an Position f2 wird in Gruppe b mit dem Erkennen der Ziffer 1 weitergemacht), sondern der Gruppe c wird dadurch auch für das Niveau 3 ein Wert zugewiesen (man könnte auch Niveau 2 nehmen, also das Niveau, auf dem der Aufruf stattfand, was aber unerheblich ist, wenn man es für alle Gruppen macht, weil die für den Bezug wichtigen Differenzen der Niveaus gleichbleiben).
Das letzte neue Element taucht an Position q5 auf, und zwar c:5-0. Die 5 bedeutet nur, dass sich diese Referenz auf Niveau fünf befindet, -0 heisst, dass man von fünf etwas abziehen soll, nichts in diesem Fall, und c bedeutet, dass man auf dem sich ergebenden Niveau, 5 also, nach der letzten Abarbeitung der Gruppe c suchen muss. Der resultierende String findet sich dann hinter dem Label Text: als die Konkatenation aller Zeichen, die von dieser Abarbeitung zwischen > und <, also zwischen den Positionen k5 und m5, verarbeitet wurden. Im Beispiel ist das der Buchstabe x, der nun anstelle von c:5-0 gesucht und gefunden wird. Nun ist also geklärt, warum bei \k< c-0> die Null steht.
Falls jetzt jemandem übel ist, empfehle ich eine kurze Pause.
Bleibt noch offen, warum b nach der Abarbeitung den Wert y1)(x2)[x3] hat. Weiter oben habe ich geschrieben, dass ein implizites Return aus einer Gruppe auf dem aktuellen Niveau den der Gruppe zugeordneten Wert setzt. Jede derartige Zuweisung setzt aber auch den globalen Wert der Gruppe, der ja keine Niveauangabe enthält und nach erfolgreichem Pattern-Matching als einziger zur Verfügung steht. Für b ergibt sich nun, dass das letzte Return an Position t2 steht, zu dem die Bearbeitung an Position c2 begann. Wenn man sich die zugehörenden Zeichen hinter dem Label Text: ansieht, erkennt man, dass sie genau dem Ergebnis y1)(x2)[x3] entsprechen.
Falls jetzt noch, auch nach mehrfachem lesen, irgend etwas unklar bleibt, bitte ich um einen Kommentar. Entweder fehlt noch eine genauere Erklärung oder ich habe einen Fehler eingetippt, was ich bei dieser Materie keinesfalls ausschliessen will.
Ich will diesmal eine Struktur wie im vorigen Beispiel suchen, nur dass der Buchstabe, der in der vorletzten runden Klammerung vorkommt, auch in der abschliessenden eckigen auftreten soll.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
p '(y1)(x2)[y3]'.match(/(?<c> # Definition Untermuster <c> [a-z] # Erkenne Kleinbuchstaben ){0} # Ende Untermuster <c> (?<b> # Definition Untermuster <b> \g<c> # Aufruf von Untermuster <c> [0-9] # Erkenne Ziffer \) # Erkenne "Klammer zu" \g<a> # Aufruf von Untermuster <a> ){0} # Ende Untermuster <b> (?<a> # Definition Untermuster <a> \( # Erkenne "Klammer auf" \g<b> # Aufruf von Untermuster <b> | # Oder \[ # Erkenne "Eckige Klammer auf" # ****************************************** \k<c-2> # Erkenne von Untermuster <c> zwei # Aufrufniveaus tiefer gefundenen # String # ****************************************** [0-9] # Erkenne Ziffer \] # Erkenne "Eckige Klammer zu" ){0} # Ende Untermuster <a> # Hauptmuster \A # Erkenne Stringanfang \g<a> # Aufruf von Untermuster <a> \z # Erkenne Stringende /x) # Musterende # Ergebnis: # => #<MatchData "(y1)(x2)[y3]" c:"x" b:"y1)(x2)[y3]" a:"(y1)(x2)[y3]"> |
Die nachstehende Analyse lässt dann hoffentlich leicht erkennen, warum diesmal der dynamische Relativbezug \k< c-2> lautet.
Text: ( y 1 ) ( x 2 ) [ y 3 ] 5: > . < > . c:5-2 . . < 4: > c . . a < 3: > . < > . b < 2: > c . . a < 1: > . b < 0: a $ Step: a b c d e f g h i j k l m n o p q r s t
Hat es jeder erkannt? - Nein? - An Position q5 steht c:5-2, also wird auf Niveau 3 der letzte Wert für die Gruppe c gesucht. Fündig wird man beim Return (<) an Position f3, wozu der String y gehört.
Ihr müsst zugeben, dass es so kompliziert nicht war, den Pattern-Matching-Vorgang zu analysieren - den richtigen Relativbezug beim Programmieren zu finden, ist ein anderes Thema. Darauf gehe ich vielleicht in einem anderen Beitrag ein, falls ich selber ein paar Kochrezepte finde.
Die Thematik ist die der ersten beiden Beispiele, nur dass ich diesmal die Aufrufstruktur der Gruppen etwas verändert habe. Warum? - Nun, ich will schliesslich auch einmal einen positiven dynamischen Relativbezug zeigen. Viel erklären werde ich nicht mehr. Zum einen tun mir langsam die Finger weh, von den stärker werdenden Kopfschmerzen einmal abgesehen, zum anderen müsste ich mich auch überwiegend wiederholen.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
p '(y1)(x2)[x3]'.match(/(?<c> # Definition Untermuster <c> [a-z] # Erkenne Kleinbuchstaben ){0} # Ende Untermuster <c> (?<b> # Definition Untermuster <b> \g<c> # Aufruf von Untermuster <c> [0-9] # Erkenne Ziffer ){0} # Ende Untermuster <b> (?<a> # Definition Untermuster <a> \( # Erkenne "Klammer auf" \g<b> # Aufruf von Untermuster <b> \) # Erkenne "Klammer zu" \g<a> # Aufruf von Untermuster <a> | # Oder \[ # Erkenne "Eckige Klammer auf" # ****************************************** \k<c+1> # Erkenne von Untermuster <c> ein # Aufrufniveau hoeher gefundenen # String # ****************************************** [0-9] # Erkenne Ziffer \] # Erkenne "Eckige Klammer zu" ){0} # Ende Untermuster <a> # Hauptmuster \A # Erkenne Stringanfang \g<a> # Aufruf von Untermuster <a> \z # Erkenne Stringende /x) # Musterende # Ergebnis: # => #<MatchData "(y1)(x2)[x3]" c:"x" b:"x2" a:"(y1)(x2)[x3]"> |
Das zugehörige Analyseschema sieht dann so aus.
Text: ( y 1 ) ( x 2 ) [ x 3 ] 4: > . < 3: > . < > c . < > . c:3+1 . . < 2: > c . < > . b . a < 1: > . b . a < 0: a $ Step: a b c d e f g h i j k l m n o p q r s t
An Position q3 steht c:3+1, also wird auf Niveau 4 der letzte Wert für die Gruppe c gesucht. Der findet sich an Return-Position m4, so dass sich x als Wert ergibt.
Dieses Muster nun noch einmal modifiziert, um den Buchstaben der vorletzten runden Klammerung zu suchen.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
p '(y1)(x2)[y3]'.match(/(?<c> # Definition Untermuster <c> [a-z] # Erkenne Kleinbuchstaben ){0} # Ende Untermuster <c> (?<b> # Definition Untermuster <b> \g<c> # Aufruf von Untermuster <c> [0-9] # Erkenne Ziffer ){0} # Ende Untermuster <b> (?<a> # Definition Untermuster <a> \( # Erkenne "Klammer auf" \g<b> # Aufruf von Untermuster <b> \) # Erkenne "Klammer zu" \g<a> # Aufruf von Untermuster <a> | # Oder \[ # Erkenne "Eckige Klammer auf" # ****************************************** \k<c+0> # Erkenne von Untermuster <c> auf # gleichem Aufrufniveau gefundenen # String # ****************************************** [0-9] # Erkenne Ziffer \] # Erkenne "Eckige Klammer zu" ){0} # Ende Untermuster <a> # Hauptmuster \A # Erkenne Stringanfang \g<a> # Aufruf von Untermuster <a> \z # Erkenne Stringende /x) # Musterende # Ergebnis: # => #<MatchData "(y1)(x2)[y3]" c:"x" b:"x2" a:"(y1)(x2)[y3]"> |
Das Analyseschema sieht so aus.
Text: ( y 1 ) ( x 2 ) [ y 3 ] 4: > . < 3: > . < > c . < > . c:3+0 . . < 2: > c . < > . b . a < 1: > . b . a < 0: a $ Step: a b c d e f g h i j k l m n o p q r s t
Diesmal ganz kurz. Es wird der letzte c-Wert auf Niveau 3 gesucht, welcher durch das Return an Position f3 festgelegt wird und y lautet. c hat nach Abschluss des Pattern-Matching den Wert x, weil die Gruppe auf Niveau 4 später an Position m4 noch einmal einen Wert erhält, der dann das globale Ergebnis ist.
Kurz und knapp - übersichtlich und strukturiert kann man diese dynamischen Relativbezüge wahrlich nicht nennen. Viel mehr kann ich darüber noch nicht aussagen, weil ich bisher noch nicht über Kochrezepte für diese Ausdrücke verfüge. Die hier vorgestellte Notation hilft mir zwar bei der Analyse weiter, allerdings nicht wirklich bei der Konstruktion von Relativbezügen, wenn diese sich nicht auf die gleiche Gruppe beziehen. Inwieweit diese Art der dynamischen Relativbezüge wirklich bei echten Problemen hilfreich sein können ist mir auch noch nicht klar. Mal sehen, vielleicht fällt ja irgend jemandem etwas ein, eventuell sogar mir in der nächsten Zeit.
So erstaunlich es klingen mag, aber zwei Sachen fehlen mir noch im Zusammenhang mit den statischen und dynamischen Relativbezügen. Ich werde diesbezüglich demnächst mal ein paar Zeilen in Ruby-Core schreiben.
Einmal betrifft das die fehlende Möglichkeit benannte und unbenannte Gruppen gleichzeitig in einem Ausdruck benutzen zu können. Im Teil 7 (statische Relativbezüge) benutzte ich Relativbezüge in Untermustern, damit ich diese mehrfach in ein Muster einsetzen kann. Wenn nun das Hauptmuster auch Gruppen beinhaltet, auf die man später irgendwie Bezug nehmen will, gibt es das Problem, dass man die zugehörige Gruppennummer oder Relativadresse kennen müsste. Dies liesse sich vermeiden, wenn man die gewünschten Gruppen benennen könnte.
Soweit ich die Beschreibungen verstanden habe, lässt Oniguruma dies prinzipiell zu, nur ist der zugehörige Schalter beim Compilieren normalerweise ausgeschaltet.
Die zweite Sache hat mit den dynamischen Relativbezügen im gleichen Problemumfeld zu tun. Dynamische Relativbezüge beinhalten immer eine absolut zu benennende Gruppe, sei es durch Nummer oder durch Namen. Es ist derzeit nicht möglich beispielsweise die vorletzte Gruppe drei Niveaus höher zu formulieren, also auch relative statische Referenzen zuzulassen.
Die wäre aber ausgesprochen hilfreich, wenn man dynamische Relativbezüge in Untermustern einsetzen will.
Nu will ich aber nicht mehr weiterschreiben...
Bitte bei allen Unklarheiten hier oder im Ruby-Forum einen Kommentar schreiben!
Kommentar schreiben
Kommentare
boah...also jetzt versteh ich, was du meinst, wenn du von dem Gebrauch starker Kopfschmerztabletten redest. Konstruktives kann ich vorerst noch nicht beitragen. Dafür schwirrt mir der Kopf noch zuviel und ich hab glaub ich auch noch nicht alles 100%ig verstanden.