ruby-mine

exploring the mine

Reguläre Ausdrücke, Teil 5: Benannte Gruppen, Palindrome, Taschenrechner und Klammergebirge.

von wonado am 17.09.2006 (15 Uhr)

von WoNáDo

Auch dieser Beitrag betriff Ruby 1.9. Kein Beispiel läuft mehr mit Ruby 1.8, geschweige denn mit Ruby 1.6. Wer weitergehende und genaue Informationen zur ab Ruby 1.9 benutzten Mustermaschine “Oniguruma” haben möchte, findet diese auf der offiziellen Seite, insbesondere benutze ich hier die Informationen, die in “RE.txt” stehen.

Da Ruby 1.9 eine Version ist, die sich mitten in der Entwicklung befindet (eine stabile Version 1.9.1 ist erst für Weihnachten 2007 geplant) und Oniguruma ständig weiterentwickelt wird, kann sich noch vieles ändern. Von diesen Änderungen an Oniguruma sind auch die Beispiele dieses Textes betroffen.

Die Beispiele unter den Überschriften “Benannte Gruppen”, “Taschenrechner” und “Klammergebirge” laufen alle mit der Version “ruby-1.9.0-20060415-i386-mswin32″ unter Windows. Ältere Versionen von Ruby 1.9 sollte man nicht benutzen.

Für die Beispiele zu “Palindrome” muss derzeit noch eine eigene Ruby-Version zusammengestellt werden, da Eigenschaften von Oniguruma benutzt werden, die erst ab Version 4.2.0 verfügbar sind. Wie man dies unter Windows machen kann ist im Ruby-Forum im Beitrag Hat jemand schon einmal YARV kompiliert? diskutiert und beschrieben.

Eine Bitte habe ich vorab. In diesem Artikel werden überwiegend neue Leitungsmerkmale benutzt, die sich noch ändern können oder deren Benutzung von Ruby aus geändert werden kann. Falls jemandem auffällt, dass sich Beispiele nicht (mehr) so wie dargestellt verhalten, bitte ich um einen beschreibenden Kommentar zum Artikel, damit auch andere am Wissen teilhaben können.

Alles klar? - na dann gehts los!

Benannte Gruppen

Wir haben ständig seit dem ersten Beitrag die einfangenden gruppierenden Klammern /(…)/ benutzt, sowie die zugehörigen Bezüge im Muster oder in der Ersetzung. Das Beispiel dazu war das Muster /\b(\w+)\b.*\b\1\b/, welches ein doppelt vorkommendes Wort im String erkennt.

Ab Ruby 1.9 gibt es nun ausserdem noch die “benannte Gruppe”. Sie gestattet Bezüge auf die Gruppe durch selbst vergebene Bezeichner, statt durch die strukturell vorgegebene Nummer der Klammerstruktur (die sich immer auf die öffnende Klammer einer einfangenden Gruppe bezieht). Das erleichtert natürlich Änderungen und ist (meist) übersichtlicher.

Syntaktisch stellt sich die benannte Gruppe so dar: /(?<name>…)/, wobei /…/ wie üblich durch irgendeinen regulären (Unter-)Ausdruck ersetzt werden muss. Der Bezeichner “name” unterliegt den Regeln für Variablennamen. Er muss mit einem Kleinbuchstaben oder Underline beginnen. Ein einfaches Beispiel zeigt Benutzung und Einschränkungen.

irb(main):001:0> puts "abba".match(/(?<c1>.)(?<c2>.)\k<c2>\k<c1>/)
abba
=> nil
irb(main):002:0> "abba".match(/(?<1>.)(?<2>.)\k<2>\k<1>/)
SyntaxError: compile error
(irb):2: invalid group name <1>: /(?<1>.)(?<2>.)\k<2>\k<1>/
        from (irb):2:in `Kernel#binding'
irb(main):003:0> "abba".match(/(?<A>.)(?<B>.)\k<B>\k<A>/)
SyntaxError: compile error
(irb):3: invalid group name <A>: /(?<A>.)(?<B>.)\k<B>\k<A>/
        from (irb):3:in `Kernel#binding'

Zugegebenermassen sieht das nun eher nach mehr Schreibarbeit aus, weil ‘abba‘.match(/(.)(.)\2\1/) den gleichen Effekt hat, aber wenn man umfangreichere Ausdrücke hat braucht man nicht immer, wenn man eine neue Gruppe einfügt, die Nummerierung bei den Bezügen ändern.

Was passiert, wenn benannte Gruppen und normale einfangende Gruppen gemischt werden? Schauen wir doch einfach mal nach.

irb(main):001:0> "abba".match(/(?<a1>.)(.)\2\k<a1>/)
SyntaxError: compile error
(irb):1: numbered backref/call is not allowed. (use name): /(?<a1>.)(.)\2\k<a1>/
        from (irb):1:in `Kernel#binding'

Das ist also nicht erlaubt. Wenn man Bezüge in einem Muster hat, dann entweder normale einfangende Gruppen oder benannte Gruppen.

Wie gestaltet sich der Zugriff auf die benannten Gruppen von Ruby aus? - Bisher blieb alles im regulären Ausdruck, damit also unter Oniguruma-Kontrolle. Das ist zwar schon was, aber wollen doch auch mit den erkannten Gruppen in Ruby arbeiten, sei es analysierend über String#match oder String#scan, oder über String#sub oder String#gsub verändernd (die /g?sub!/-Varianten beziehe ich hier mit ein).

Fangen wir mal ganz einfach an, also mit String#match.

md="abba".match(/(?<a1>.)(?<a2>.)\k<a2>\k<a1>/) # => #<MatchData:0x2bf0488>
md[0] # => "abba"
md[1] # => "a"
md[2] # => "b"
md[:a1] # => "a"
md[:a2] # => "b"
md['a1'] # => "a"
md['a2'] # => "b"

Bei String#match kann man auf die Ergebnisse sowohl über eine Gruppennummer zugreifen, als auch über die Gruppenbezeichner, die als Symbol oder String angegeben werden können.

Die Vergabe der Nummern orientiert sich an den Positionen der öffnenden Klammern der benannten Gruppen, während andere Gruppierungen keine Rolle spielen. Das sieht man hier:

1
2
3
4
5
6
7

md='abcdef'.match(/(.)(?<x1>.)(?:.)(.)(?<x2>.)/) # => #<MatchData:0x2a5de88>
md[0] # => "abcde"
md[1] # => "b"
md[2] # => "e"
md[3] # => nil
md[:x1] # => "b"
md[:x2] # => "e"

Es ist übrigens erlaubt mehreren benannten Gruppen den gleichen Namen zu geben. Das Ergebnis kann dann allerdings leicht zu Verwirrungen führen.

1
2
3
4
5

md='abac'.match(/(?<x>.)c|(?<x>.)b/) # => #<MatchData:0x2a5f878>
md[0] # => "ab"
md[1] # => nil
md[2] # => "a"
md[:x] # => "a"

Wie erklärt sich das? - Es zieht offensichtlich die zweite benannte Gruppe. Da diese den Namen x trägt, verwundert der Inhalt von md[:x] nicht, er entspricht den Erwartungen. Da aber gleichzeitig auch Nummern für die benannten Gruppen vergeben werden, ist diese zweite Gruppe auch noch über md[2] erreichbar. Lautet der Text nun ‘acab‘ ändert sich nichts bei md[:x], wohl aber beim Zugriff über die Position:

1
2
3
4

md='acab'.match(/(?<x>.)c|(?<x>.)b/) # => #<MatchData:0x2a5f878>
md[:x] # => "a"
md[1] # => "a"
md[2] # => nil

Wenn während eines Mustervergleichs mehrfach erfolgreich eine durch den gleichen Namen bezeichnete Gruppe auftritt, ist über den Bezeichner nur die letzte erfolgreiche Gruppe verfügbar, während über die Position alle erreichbar sind.

1
2
3
4
5

md='abc'.match(/(?<x>.)(?<x>.)(?<x>.)/) # => #<MatchData:0x2a5f10c>
md[1] # => "a"
md[2] # => "b"
md[3] # => "c"
md[:x] # => "c"

Bevor wir zu String#scan, String#sub und String#gsub kommen gibt es noch ein paar Neuigkeiten.

Um es vorweg zu nehmen - ich stand bei der Formulierung der folgenden Zeile nicht unter Drogen …

irb(main):001:0> p 'abc'.match(/(Otto ist doof){0}/)[0]
""

Was soll das denn nun? - ich formuliere hier ein Muster (Otto ist doof) und sage “bitte Null mal anwenden”. Das zieht natürlich immer und liefert den Leerstring "", also was soll denn so ein Blödsinn bringen?

Ich mach es gleich noch mal schlimmer.

irb(main):001:0> p 'abc'.match(/(?<n>Otto ist doof){0}/)[0]
""

Da ich offensichtlich noch mehr schreiben will, habe ich der Gruppe noch einen Namen gegeben.

Wo führt uns das aber hin? - ich habe eine komplizierte Art und Weise benutzt an jeder beliebigen Stelle etwas der Länge 0 zu finden - ich könnte es weglassen, denn Bezüge darauf, wie /\1/ oder /\k<n>/ liefern den Leerstring, passen also auch immer und überall …

… gibt es denn überhaupt eine sinnvolle Anwendung für so etwas?

KLAMMER AUF

Wir alle haben schon oft Methoden definiert, also irgendwo am Anfang eines Programms etwas wie

1
2
3

def otto
  puts 'otto lebt!'
end

geschrieben. Natürlich wollen wir an dieser Stellen nichts von der Methode otto, wir wollen sie aber später mal benutzen können.

KLAMMER ZU

Tja, das wäre natürlich sinnvoll - … wenn es eine Möglichkeit gäbe in einem regulären Ausdruck gezielt Unterausdrücke (mit Namen oder nur durch Nummern identifiziert) wie Methoden aufzurufen!

Ab Ruby 1.9 mit Oniguruma geht genau das!

Ich will hier nicht versuchen mir schnell ein realistisch anmutendes Beispiel aus den Fingern zu saugen, es reicht auch ein künstliches. Der Rest ist erst mal “selber ein bisschen rumspielen”.

irb(main):001:0> md='abba'.match(/(?<x>.){0}a\g<x>\k<x>a/)
=> #<MatchData:0x2a5e6bc>
irb(main):002:0> md[:x]
=> "b"

Die Konstruktion /\g<name>/ ruft eine benannte Gruppe wie eine Methode/Funktion auf. Das kann man, wenn man auf benannte Gruppen verzichtet, auch mit den klassischen gruppierenden Klammern machen.

irb(main):001:0> md='abba'.match(/(.){0}a\g<1>\1a/)
=> #<MatchData:0x2a5f65c>
irb(main):002:0> md[1]
=> "b"

Wie sieht es aber mit den anderen Möglichkeiten in Ruby aus? - Nun, soweit ich das bisher erkunden konnte, nicht so einfach wie mit String#match. In String#scan werden, sofern überhaupt Gruppen definiert sind, nur die Positionsnummern verarbeitet, während kein Zugriff auf die Gruppenbezeichnungen besteht.

Wird String#scan mit Block benutzt, kann man im Block über das “MatchData”-Objekt $~ oder die Klassenmethode Regexp.last_match, wie bei String#match auf die jeweils aktuellen Match-Ergebnisse zugreifen. Das sieht dann im Beispiel so aus:

irb(main):001:0> "ab".scan(/(?<x>.)/)
=> [["a"], ["b"]]
irb(main):002:0> "ab".scan(/(?<x>.)/){|i|p i}
["a"]
["b"]
=> "ab"
irb(main):003:0> "ab".scan(/(?<x>.)/){p $~[:x]}
"a"
"b"
=> "ab"

Vorteilhaft kann sich die Benutzung des eben besprochenen Aufrufs von Gruppen auswirken. Ohne diese Möglichkeit hat man oft Probleme, wenn sich zwei Gruppen in verschiedenen Zweigen einer Alternative befinden.

irb(main):001:0> "rasbuavb".scan(/(.)a|(.)b/){|i|p i}
["r", nil]
[nil, "s"]
["u", nil]
[nil, "v"]
=> "rasbuavb"

In diesem Fall steht das Ergebnis entweder als erstes oder als zweites Element zur Verfügung. Man ist also gezwungen bei der Auswertung noch Abfragen auf not nil einzubauen. Nimmt man statt dessen den Aufruf einer Gruppe, kann man das wesentlich einfacher gestalten.

irb(main):002:0> "rasbuavb".scan(/(.){0}\g<1>a|\g<1>b/){|i|p i}
["r"]
["s"]
["u"]
["v"]
=> "rasbuavb"

Da in beiden Zweigen die erste Gruppe aufgerufen wird, steht das Ergebnis auch immer im ersten Element bereit.

Die Ersetzungsmethoden funktionieren wieder etwas anders. Einfaches String#sub arbeitet mit den seitens Oniguruma vorgegebenen Referenzen auf Gruppen. Die positionsbezogenen Gruppierungen sind verfügbar, beinhalten aber jeweils den Leerstring.

irb(main):001:0> puts 'axbx'.sub(/(?<r>.)x(?<s>.)x/, '\k<s>\k<r>')
ba
=> nil
irb(main):002:0> puts 'axbx'.sub(/(?<r>.)x(?<s>.)x/, '\2\1')

=> nil

Bleibt noch die globale Ersetzung. Da sieht es entsprechend aus.

irb(main):001:0> 'axbxcxdx'.gsub(/(?<r>.)x(?<s>.)x/, '\k<s>\k<r>')
=> "badc"
irb(main):002:0> 'axbxcxdx'.gsub(/(?<r>.)x(?<s>.)x/, '\2\1')
=> ""

Wenn man statt der Ersetzung einen Block nimmt, wird man normalerweise wohl auf die Variablen $1 etc. zurückgreifen, also auf die Positionen. Ein direkter Zugriff auf die Gruppennamen ist meiner aktuellen Kenntnis nach nicht (direkt) möglich.

irb(main):001:0> 'axbx'.sub(/(?<i>.)x(?<j>.)x/){|k|p k;p $1;p $2;'u'+$2}
"axbx"
"a"
"b"
=> "ub"
irb(main):002:0> 'axbxcxdx'.gsub(/(?<i>.)x(?<j>.)x/){|k|p k;p $1;p $2;'u'+$2}
"axbx"
"a"
"b"
"cxdx"
"c"
"d"
=> "ubud"

Man kann jedoch, wie schon angesprochen, mit den MatchData-Objekten im Block arbeiten.

irb(main):003:0> 'axbxcxdx'.gsub(/(?<i>.)x(?<j>.)x/){|k|p $~[:i]}
"a"
"c"
=> ""

Damit will ich die Einführung in die Benutzung benannter Gruppen ab Ruby 1.9 beenden.

Palindrome

Aus der Wikipedia: Palindrome sind Zeichenketten, die von vorn und hinten gelesen gleich bleiben (wie zum Beispiel das Wort Rentner). Darüber hinaus werden auch Worte, Wortreihen oder Sätze als Palindrome bezeichnet, die rückwärts gelesen einen Sinn haben (wie zum Beispiel die Worte Lager - Regal).

Das will ich noch insofern erweitern, als dass Gross-/Kleinbuchstaben als identisch angesehen werden. Ausserdem werden alle Nicht-Wortsymbole ignoriert. Das ist auch nötig um das bekannte Palindrom “Ein Neger mit Gazelle zagt im Regen nie!” als solches zu erkennen.

Vorab noch etwas anderes. Um festzustellen, ob ein vorgegebener String nach der obigen Spezifikation ein Palindrom ist, benötigt man in Ruby keine komplexe Mustererkennung. Das geht auch einfacher.

1
2
3
4
5
6
7
8
9
10
11
12

palindrome = [ "Rentner?",
               "Renner?",
               "Ein Rentner! Renner-Rentner? Nie!",
               "Rentner, Rentner!",
               "Paul",
               "Ein Neger mit Gazelle \nzagt im Regen nie!",
               "Huhu, ich bin bestimmt kein Palindrom!" ]

palindrome.each do |text|
  geknetet = text.downcase.gsub(/\W+/, '')
  puts "'#{text}' ist #{(geknetet.eql?(geknetet.reverse))?'':'k'}ein Palindrom"
end

Gibt das aus, was wir erwarten konnten:

'Rentner?' ist ein Palindrom
'Renner?' ist ein Palindrom
'Ein Rentner! Renner-Rentner? Nie!' ist ein Palindrom
'Rentner, Rentner!' ist ein Palindrom
'Paul' ist kein Palindrom
'Ein Neger mit Gazelle
zagt im Regen nie!' ist ein Palindrom
'Huhu, ich bin bestimmt kein Palindrom!' ist kein Palindrom

Ich nehme das Beispiel aber trotzdem hier auf, weil sich sehr schön der Einsatz der neuen Musterelemente zeigen lässt, und weil man mit der obigen Techniken nicht so leicht in Richtung einer gewünschten “Palindrom-Suchmaschine” kommt - in diese Richtung will ich aber, auch wenn am Ende noch ein paar Kleinigkeiten fehlen werden.

Der Ansatz benutzt rekursive Muster, braucht also eine entsprechende Definition für “Palindrom” - also los mit dem ersten Versuch!

Ein Palindrom ist ein leerer String, ein einzelnes Zeichen oder ein String, der das gleiche erste und letzte Zeichen enthält, und dessen “innerer Rest” ein Palindrom ist. Die Anfangsdefinitionen unterscheiden Palindrome mit einer geraden (”leerer String”) und ungeraden (”ein einzelnes Zeichen”) Anzahl Zeichen. Der Rest sagt, dass man ein neues Palindrom erhält, indem man an ein existierendes vorne und hinten das gleiche Zeichen anfügt.

Damit können wir erst einmal beginnen. Um daraus einen regulären Ausdruck zu formen fehlt uns noch ein ganz neues Sprachelement von Oniguruma (deshalb läuft das hier erst ab Oniguruma 4.2.0). Wie bei ganz normalen rekursiven Methoden wollen wir die Ergebnisse der verschachtelten Aufrufe an der richtigen Stelle nutzen. Dazu dient hier die Konstruktion /\k<i-0>/, die angibt, dass das Ergebnis der durch k benannten Gruppe des gleichen Rekursionsniveaus (/k-0/) benutzt werden soll.

Als Ergänzung ist es noch nützlich zu wissen, dass in Alternativen leere Elemente erlaubt sind, die dann den Leerstring erkennen. Man darf also /(|a)/ schreiben, was gleichbedeutend mit /a??/ ist.

Erster Versuch.

1
2
3
4
5
6
7
8
9
10
11
12
13

palindrome = [ "Rentner?",
                    "Rentner",
                    "Renner?",
                    "Renner",
                    "a",
                    "bb",
                    "aba",
                    "abba" ]

palindrome.each do |text|
  md = text.match(/^(?<o>|\w|(?:(?<i>\w)\g<o>\k<i-0>))$/im)
  puts "'#{text}' ist #{(md)?'':'k'}ein Palindrom"
end

Da kommt dann raus:

'Rentner?' ist kein Palindrom
'Rentner' ist ein Palindrom
'Renner?' ist kein Palindrom
'Renner' ist ein Palindrom
'a' ist ein Palindrom
'bb' ist ein Palindrom
'aba' ist ein Palindrom
'abba' ist ein Palindrom

Wie gewünscht, werden erst einmal echte Palindrome erkannt, allerdings werden immer noch Satzzeichen berückssichtigt. Das Muster /(?<o>|\w|(?:(?<i>\w)\g<o>\k<i-0>))/ ist also noch nicht ausreichend.

Wie? - Das Muster ist unverständlich? - Na, dann nehmen wir es doch mal auseinander!

Ganz aussen steht alles, um die benannte Gruppe o (Palindromerkennung) zu definieren. Bleibt /|\w|(?:(?<i>\w)\g<o>\k<i-0>)/ übrig. Das sind wiederum die drei Möglichkeiten der Definition, “” (Leerstring), /\w/ (ein einzelnes Zeichen) oder /(?<i>\w)/ (ein Zeichen) gefolgt von /\g<o>/ (ein Palindrom, rekursiver Aufruf) gefolgt von /\k<i-0>)/ (das eben erkannte eine Zeichen). Das ganze eingepackt zwischen /^/ und /$/, also in unserem Fall der komplette String.

Da das nun klarer ist, können wir Stück für Stück die Unschönheiten beseitigen. Kommen wir anfangs noch einmal auf die Definition zurück - “… ein leerer String, ein einzelnes Zeichen …”.

Das mag in seiner Klarheit jeden Mathematiker begeistern, zufriedenstellend ist es aber nicht. Ich möchte nicht allen Ernstes “q” oder “bb” als Palindrom bezeichnen. Man kann das zwar nach belieben festlegen, aber ich fange einfach man bei drei Buchstaben an. Dann muss das Muster an zwei Stellen geändert werden, und zwar muss für eine gerade Anzahl Zeichen das Minimum auf vier Zeichen, statt des leeren Strings gesetzt werden, und für eine ungerade Anzahl auf drei Zeichen, statt des einzelnen Zeichens. Die entsprechenden Musterteile sind /(?<m1>\w)\w\k<m1-0>/ (drei Zeichen) und /(?<m2>\w)(?<m3>\w)\k<m3-0>\k<m2-0>/ (vier Zeichen). Der Rest verändert sich nicht. Für die bessere Lesbarkeit benutze ich den “Extended Mode”, der Leerzeichen und Zeilnumbrüche im Muster erlaubt.

Also ran.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

palindrome = [ "Rentner?",
               "Rentner",
               "Renner?",
               "Renner",
               "a",
               "bb",
               "aba",
               "abba" ]

p =/^(?<o>(?<m1>\w)\w\k<m1-0> |
      (?<m2>\w)(?<m3>\w)\k<m3-0>\k<m2-0> |
      (?:(?<i>\w)\g<o>\k<i-0>))$/imx
palindrome.each do |text|
  md = text.match(p)
  puts "'#{text}' ist #{(md)?'':'k'}ein Palindrom"
end

Raus kommt nun:

'Rentner?' ist kein Palindrom
'Rentner' ist ein Palindrom
'Renner?' ist kein Palindrom
'Renner' ist ein Palindrom
'a' ist kein Palindrom
'bb' ist kein Palindrom
'aba' ist ein Palindrom
'abba' ist ein Palindrom

Das funktioniert erst einmal. Nun fehlt noch, dass Leerzeichen, Satzzeichen, Zeilenumbrüche, also alle “Nicht-Wortzeichen”, ignoriert werden.

Um das zu erreichen erlaube ich vor und nach jedem Wortzeichen eine beliebige Anzahl (auch 0) anderer Zeichen, die bei der Palindrombestimmung ignoriert werden. Dafür definiere ich die benannte Gruppe /(?<l>\W*)/, die an allen in Frage kommenden Stellen durch /\g<l>/ aufgerufen wird.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

palindrome = [ "Rentner?",
               "Renner?",
               "Ein Rentner! Renner-Rentner? Nie!",
               "Rentner, Rentner!",
               "Paul",
               "Ein Neger mit Gazelle \nzagt im Regen nie!",
               "Huhu, ich bin bestimmt kein Palindrom!" ]

p =/^(?<o>(?<l>\W*)(?<m1>\w)\g<l>\w\g<l>\k<m1-0>\g<l> |
      \g<l>(?<m2>\w)\g<l>(?<m3>\w)\g<l>\k<m3-0>\g<l>\k<m2-0>\g<l> |
      (?:\g<l>(?<i>\w)\g<l>\g<o>\g<l>\k<i-0>\g<l>))$/imx

palindrome.each do |text|
  md = text.match(p)
  puts "'#{text}' ist #{(md)?'':'k'}ein Palindrom"
end

gibt:

'Rentner?' ist ein Palindrom
'Renner?' ist ein Palindrom
'Ein Rentner! Renner-Rentner? Nie!' ist ein Palindrom
'Rentner, Rentner!' ist ein Palindrom
'Paul' ist kein Palindrom
'Ein Neger mit Gazelle
zagt im Regen nie!' ist ein Palindrom
'Huhu, ich bin bestimmt kein Palindrom!' ist kein Palindrom

Damit sind wir jetzt fast fertig. Es bleibt noch die Frage, wie das gefundene Muster als Suchmaschine für Palindrome einsetzbar ist. Dafür entferne ich jetzt die Anker /^/ und /$/ und lasse es mit String#scan über einen String laufen.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

palindrom = <<TEXT
Rentner, Renner und Paule.
Ein Rentner? Renner-Rentner? Nie!
Rentner-Rentner? Paule!
Ein Neger mit Gazelle
zagt im Regen nie! Jawoll!
TEXT

p =/(?<o>(?<l>\W*)(?<m1>\w)\g<l>\w\g<l>\k<m1-0>\g<l> |
      \g<l>(?<m2>\w)\g<l>(?<m3>\w)\g<l>\k<m3-0>\g<l>\k<m2-0>\g<l> |
      (?:\g<l>(?<i>\w)\g<l>\g<o>\g<l>\k<i-0>\g<l>))/imx

n = 0
palindrom.scan(p) do
  puts "Palindrom #{n+=1}: #{$~[0].sub(/^\W+/,'').sub(/\W+$/,'').gsub(/\W+/,' ')}"
end

Ergibt das Suchergebnis:

Palindrom 1: Rentner
Palindrom 2: Renner
Palindrom 3: Ein Rentner Renner Rentner Nie
Palindrom 4: Rentner
Palindrom 5: Rentner
Palindrom 6: Ein Neger mit Gazelle zagt im Regen nie

Wunderbar - das funktioniert! Es fällt sofort auf, dass die Suche “non greedy” abläuft. Es wird immer die kürzest mögliche Lösung gesucht. Um das zu ändern müsste ein völlig anderes Muster gefunden werden. Wenn man diese Version auf einen Beliebigen Text loslässt erhält man auch unerwünschte Ergebnisse, da “scan” nicht daran gehindert wird, mitten im Wort anzufangen oder zu enden. Auch diesbezüglich müsste etwas getan werden, wobei die vielen /\g<l>/ berücksichtigt werden müssen.

Das alles mache ich aber nicht mehr!

Zum Ende noch ein Verhalten, welches mir nicht klar ist. Die vielen /\W*/, die ja de facto überall im Muster vorkommen, lassen ein “gewisses Unendlichkeitsproblem” vermuten, wenn nicht schnell etwas gefunden wird. Erstaunlicherweise tritt es nicht auf - aber - wenn ich das Muster ändere, indem ich direkt /\W*/ einsetze geht das nur bis zu folgender Reduzierung gut.

1
2
3

p =/(?<o>(?<l>\W*)(?<m1>\w)\W*\w\W*\k<m1-0>\W* |
      \W*(?<m2>\w)\W*(?<m3>\w)\W*\k<m3-0>\W*\k<m2-0>\W* |
      (?:\W*(?<i>\w)\g<l>\g<o>\W*\k<i-0>\W*))/imx

Wenn ich den letzten Bezug /\g<l>/ in der letzten Zeile direkt durch /\W*/ ersetze, braucht scan plötzlich unendlich lange. Hat jemand eine Erklärung für diesen Effekt oder habe ich irgendetwas übersehen.

Taschenrechner

Dieses Beispiel werde ich nur kurz kommentieren, da die Analyse des zentralen regulären Ausdrucks nach dem bisher gesagten relativ einfach sein müsste. Ich will mit diesem Beispiel andeuten, wie die neuen Möglichkeiten echte Syntaxanalyse unterstützen können.

Es handelt sich um einen kleinen Rechner, der Zuweisungen und Benutzung von Variablen erlaubt. Die Variablen werden durch “keys” eines “Hash” realisiert. Alle Variablen sind mit 0 initialisiert. Die eingegebenen Ausdrücke werden in einen eventuellen Zuweisungsteil an eine Variable und den eigentlichen arithmetischen Ausdruck zerlegt. Der Ausdruck wird dann mithilfe von eval ausgeführt und das Ergebnis ausgegeben, sowie an eine Variable zugewiesen, sofern das angefordert war. Nach Eingabe von quit beendet sich der Rechner und gibt abschliessend noch die Werte der benutzten Variablen aus.

Damit von eval nur korrekte arithmetische Ausdrücke bearbeitet werden, und nicht etwa gefährliche Anweisungen, muss die Eingabe vollständig syntaktisch analysiert werden. Das geschieht durch die Definitionen für das Muster pattern. Die ersten sechs Zeilen sind Definitionen, die erst später aufgerufen werden (erkennbar an /(…){0}/). Die Arbeit beginnt in der siebten Zeile, welche die vorherigen Definitionen benutzt. Die entsprechen der üblichen Syntaxdefinition von “Expression”, “Token” und “Factor”, sowie den Beschreibungen für Zahlen und Variablen.

Da das Muster nur der syntaktischen Analyse und nicht dem Aufbau eines AST (Abstract Syntax Tree) dient, braucht man sich nicht um die Details der Umsetzung von (verbotener) Linksrekursion zur (erlaubten) Rechtsrekursion kümmern. Es soll ja nur verhindert werden, dass eval gefährliche Daten erhält.

Ansonsten werden aus der Eingabe noch alle Leerzeichen entfernt und im Ausdruck benutzte Variablen werden durch den Zugriff auf den Hash ersetzt, also beispielsweise wird otto zu vars[‘otto‘].

Mehr gibt es eigentlich nicht zu sagen, lassen wir “Ruby” sprechen.

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
33
34

pattern = / (?<e>\g<t>\+\g<e>|\g<t>-\g<e>|\g<t>){0}
            (?<t>|\g<f>\*\g<t>|\g<f>\/\g<t>|\g<f>){0}
            (?<f>[-+]?\g<id>|\(\g<e>\)){0}
            (?<id>\g<n>|\g<v>){0}
            (?<n>[a-zA-Z_]\w*){0}
            (?<v>\d+(\.\d+)?){0}
            ^((?<var>\g<n>)=)?(?<expr>\g<e>)$
          /x

vars = Hash.new(0)
basbind = binding

# print 'input> ' # nur bei interaktiver Benutzung sinnvoll
while (!(inp = DATA.gets).chomp.match(/^quit$/i))
  if (md = inp.chomp.gsub(/\s+/,'').match(pattern))
    expr = md[:expr].gsub(/([a-zA-Z_]\w*)/, 'vars["\1"]')
    erg = eval(expr, basbind)
    vars[md[:var]] = erg if md[:var]
    puts "#{inp.chomp}, Ergebnis> #{(md[:var])?(md[:var]+'='):""}#{erg}"
  else
    puts "+++++ Inkorrekte Eingabe: '#{inp.chomp}'"
  end
#  print 'input> ' # nur bei interaktiver Benutzung sinnvoll
end
puts '***** Variablen *****'
vars.keys.sort.each{|v|puts "#{v}=#{vars[v]}"}
puts '******* Ende ********'
__END__
30+12
a = 30 + 12
b = 2*a
c = -(a*a+5)
d = (6+5*a)*c
quit

Die interaktive Benutzung ist hier nur simuliert, aber die Ergebnisse sind korrekt.

30+12, Ergebnis> 42
a = 30 + 12, Ergebnis> a=42
b = 2*a, Ergebnis> b=84
c = -(a*a+5), Ergebnis> c=-1769
d = (6+5*a)*c, Ergebnis> d=-382104
***** Variablen *****
a=42
b=84
c=-1769
d=-382104
******* Ende ********

Abschliessend nur noch eine Alternative für die Erstellung des Musters pattern. Wenn man auf diese Art und Weise vorgehen will muss man die Auswertungsregeln der Backslashes beachten, sonst kann man auf die Nase fallen - ich bin das auch schon öfter!

1
2
3
4
5
6
7
8

e = '(?<e>\g<t>\+\g<e>|\g<t>-\g<e>|\g<t>){0}'
t = '(?<t>|\g<f>\*\g<t>|\g<f>\/\g<t>|\g<f>){0}'
f = '(?<f>[-+]?\g<id>|\(\g<e>\)){0}'
id = '(?<id>\g<n>|\g<v>){0}'
n = '(?<n>[a-zA-Z_]\w*){0}'
v = '(?<v>\d+(\.\d+)?){0}'
inpat = '^((?<var>\g<n>)=)?(?<expr>\g<e>)$'
pattern = Regexp.new(e+t+f+id+n+v+inpat)

Muster zur Syntaxanalyse lassen sich durchaus bei der Prüfung von Eingabefeldern in GUI-Anwendungen sinnvoll anwenden.

Klammergebirge

Unter WoNáDos Vergewaltigungen Regulärer Ausdrücke - Fall 1 findet Ihr ein Muster, welches balanzierte Klammerung erkennt. Es steht dort noch mit einem Trick versehen, der damals wegen eines Fehlers in Oniguruma nötig war. Ausserdem sollte sich jeder auch “murphy”s Änderungsvorschläge ansehen. Hier liegt wirklich der “Teufel im Detail” - allerdings lohnt es sich, da das Muster wirklich anwendbar ist. Hier ist es ohne problematisierende Details in einer Version, die aktuell lauffähig ist.

Es dient dazu balancierte Klammerung zu erkennen, versucht also ähnlich wie /.*/ beliebige Zeichen zuzulassen, jedoch müssen immer die gleiche Anzahl öffnender und schliessender Klammern in diesem Teil vorkommen. Das Module sieht so aus.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

module Matchelements
  def bal(lpar='(', rpar=')')
    raise RegexpError,
      "wrong length of left bracket '#{lpar}' in bal" unless lpar.length == 1
    raise RegexpError,
      "wrong length of right bracket '#{rpar}' in bal" unless rpar.length == 1
    raise RegexpError,
      "identical left and right bracket '#{lpar}' in bal" if lpar.eql?(rpar)
    lclass, rclass = lpar, rpar
    lclass = '\\' + lclass if lclass.match(/[\-\[\]]/)
    rclass = '\\' + rclass if rclass.match(/