ruby-mine

von WoNáDo

Auch diesmal dreht es sich um Reguläre Ausdrücke in Ruby. Nachdem die Quantoren das letzte Mal im Mittelpunkt standen, ist es diesmal die Atomare Gruppierung.

Atomare Gruppierungen

Kurz und schmerzlos: Atomare Gruppen sind Teile regulärer Ausdrücke, die in speziellen Klammern stehen: /(?>…)/, wobei ... irgendein Teilausdruck ist.

Schön – aber was soll das Ganze?

Nehmen wir mal den regulären Ausdruck /^.*a/ und wenden ihn auf den String 'xxax' an. Der Ausdruck ist durch ^ verankert, muss also ab dem Anfang passen. .*, welches gierig ist, nimmt nun im ersten Ansatz alles, was es bekommen kann, also 'xxax'. Nun versucht die Mustermaschine noch 'a' zu erkennen – und scheitert, weil das String-Ende erreicht ist.

Also schaut die Maschine nach, was die schon verarbeiteten Musterelemente ihr an Alternativen gelassen haben. Sie findet, dass * ihr sagt: ich gebe mich notfalls auch mit weniger zufrieden, woraufhin .* nur noch Anspruch auf 'xxa' erhebt. Das hilft der Maschine immer noch nicht weiter, da a nun mal nicht auf das nun kommende 'x' passt. Beim nächsten Versuch nimmt .* dann nur noch 'xx', so dass die Mustermaschine das dann folgende 'a' erkennen kann. Da kein weiteres Musterelement folgt, wurde die Mustererkennung erfolgreich abgeschlossen.

Hier machte die Mustermaschine Backtracking, was nichts anderes bedeutet, als dass sie bei Misserfolg zu vorher schon benutzten Musterelementen zurückgeht und diese nach Alternativen befragt. Wenn sie welche angeboten bekommt, probiert sie weiter. Das macht sie so lange, bis sie alle Musterelemente erfolgreich abgearbeitet hat oder bis sie bei Misserfolg keine Alternativen mehr angeboten bekommt.

Das kann natürlich ganz schön viel Arbeit bedeuten.

Speziell dann, wenn ein Muster nicht auf einen String passt, wird es manchmal richtig kritisch. Nehmen wir wieder /^.*a/ als Muster, jedoch 'x' * 100 als String. Jetzt nimmt .* zuerst 100 Zeichen, dann 99, …, dann 1, dann keins – und die Mustermaschine hat trotz der 101 Versuche keinen Erfolg. Wenn wir es jetzt etwas verrückter machen, nämlich /^.*.*a/ nehmen (das macht man zwar nicht wirklich, es ist aber erlaubt), dann hat die Mustermaschine noch ein bisschen mehr zu tun. Das erste .* lässt wieder 101 mögliche Positionen zu. Das zweite lässt auch Alternativen zu, und zwar abhängig von der Position, die das erste .* bei seinem aktuellen Versuch hat. Sei p die Position, bei der das erste .* gerade beendet ist, dann kann das zweite 101-p Alternativen anbieten. Insgesamt gibt es jetzt also schon 5252 (=5151+101) Alternativen, die von der Mustermaschine durchprobiert werden müssen.

Kann man das irgendwie verhindern? Nun, sehr oft kann man sich mit die atomaren Gruppierungen helfen.

Das funktioniert dadurch, dass am Ende einer atomaren Klammerung /(?>…)/ alle möglichen Alternativen, die durch die Teilmuster ... angeboten werden, gelöscht werden. Diese Klammerung ist für die Mustermaschine sozusagen eine Art Einbahnstrasse: Von rechts kommt sie nicht an die einzelnen Teile ran, sie kann die Klammerung nur von links betreten.

Auf unser erstes Beispiel bezogen ergibt sich eine erste Überraschung – eine böse! Schreiben wir also /^.*a/ entsprechend um zu /^(?>.*)a/ und wenden es auf 'xxax' an.

'xxax'.match(/^(?>.*)a/) # => nil

Wieso denn das nun? – Tja, jetzt haben wir dem gierigen .* erlaubt, alles zu nehmen und nichts mehr herzugeben. Die Mustermaschine kann das 'a' nach dem Ende des Strings nicht finden und fragt die Atomare Klammerung nach Alternativen. Die hat jedoch laut ihrem speziellen Auftrag alle weiteren Angebote von .* weggeworfen und sagt nun der Maschine, dass sie nichts hat. Da das ^ am Anfang auch keine Alternativen anbietet, weiss die Mustermaschine nicht mehr weiter und gibt auf.

Es gibt natürlich auch Beispiele, bei denen der Einsatz von atomaren Gruppen sehr einfach geht. Ein Beispiel aus Theater-Skripten, bei denen der Name der sprechenden Person am Anfang steht, gefolgt von einem Doppelpunkt. Wenn man nun diesen Namensteil entfernen will, geht das klassisch und mit atomaren Klammern:

s = 'Gerda: Fete ist angesagt!'
s.match(/^[^:]*: ?(.*)$/)[1]
#-> "Fete ist angesagt!" 
s.match(/^(?>[^:]*): ?(.*)$/)[1]
#-> "Fete ist angesagt!" 

Ein Fehler aus der Pickaxe

Man muss allerdings sehr aufpassen, wenn man Ausdrücke umarbeiten will. Seite 327 der gedruckten Ausgabe von “Programming Ruby – Second Edition” (Kapitel 22 - The Ruby Language, The Basic Types, Regular Expressions, Regular Expression Extensions) enthält eine fehlerhafte Umsetzung im Beispiel zu /(?>re)/ (ich habe diesen Fehler letztes Jahr gemeldet, er dürfte also in den Ebook-Ausgaben schon korrigiert sein.)

Dort wird der Ausdruck /a.*b.*a/ ungewandelt zu /a(?>.*b).*a/. Da der atomare Unterausdruck ein gieriges .* enthält, wird also immer das letzte 'b' im Text erkannt. Wenn hinter diesem kein 'a' mehr kommt, kann das Muster nie passen, weil die atomare Klammerung alle weiteren Möglichkeiten ihrer Aufgabe entsprechend verschweigt. Das Originalmuster passt aber sehr wohl auf einen Teil des Strings 'xaxbxaxbx'. Hier kann man sich mit der nicht-gierigen Version .*? helfen.

Das Beispiel mal ausgeführt:

text = 'xaxbxaxbx'
pattern = /a.*b.*a/
if md = text.match(pattern)
  puts "'#{text}'.match(/#{pattern.source}/): " +
    #{md.pre_match}<#{md[0]}>#{md.post_match}" 
else
  puts "'#{text}'.match(/#{pattern.source}/): " +
    "- kein Match -"
end
pattern = /a(?>.*b).*a/
if md = text.match(pattern)
  puts "'#{text}'.match(/#{pattern.source}/): " +
    "#{md.pre_match}<#{md[0]}>#{md.post_match}"
else
  puts "'#{text}'.match(/#{pattern.source}/): " +
    "- kein Match -"
end
pattern = /a(?>.*?b).*a/
if md = text.match(pattern)
  puts "'#{text}'.match(/#{pattern.source}/): " +
    "#{md.pre_match}<#{md[0]}>#{md.post_match}"
else
  puts "'#{text}'.match(/#{pattern.source}/): " +
    "- kein Match -"
end

zeigt das erwartete Ergebnis:

'xaxbxaxbx'.match(/a.*b.*a/): x<axbxa>xbx
'xaxbxaxbx'.match(/a(?>.*b).*a/): - kein Match -
'xaxbxaxbx'.match(/a(?>.*?b).*a/): x<axbxa>xbx

Zum Abschluss dieses Teils noch ein nettes kleines Beispiel, welches die oben geschilderten Zeitprobleme und die möglichen Lösungen durch atomare Ausdrücke recht drastisch aufzeigt.

require 'benchmark'

uebel = 'xxaxxb' * 100 + 'c'
uebler = 'xxaxxb' * 100

nr = 100
m = n = am = an = nil  # muss ausserhalb des Blockes bekannt sein
Benchmark.bm 15 do |test|
  test.report 'match' do 100.times do
    m = uebel.match(/a.*b.*c/)
  end end
  test.report 'no match' do 100.times do
    n = uebler.match(/a.*b.*c/)
  end end
  test.report 'atomar match' do 100.times do
    am = uebel.match(/a(?>.*?b).*c/)
  end end
  test.report 'atomar no match' do 100.times do
    an = uebler.match(/a(?>.*?b).*c/)
  end end
end

puts "Ergebnis 'match': #{(m)?(m[0].length):(m.inspect)}"
puts "Ergebnis 'no match': #{(n)?(n[0].length):(n.inspect)}"
puts "Ergebnis 'atomar match': #{(am)?(am[0].length):(am.inspect)}"
puts "Ergebnis 'atomar no match': #{(an)?(an[0].length):(an.inspect)}"

Das Ergebnis, besonders die zweite Zeile des Reports, spricht Bände.

                     user     system      total        real
match            0.010000   0.000000   0.010000 (  0.020000)
no match        29.552000   0.010000  29.562000 ( 29.582000)
atomar match     0.010000   0.000000   0.010000 (  0.010000)
atomar no match  1.132000   0.000000   1.132000 (  1.132000)
Ergebnis 'match': 599
Ergebnis 'no match': nil
Ergebnis 'atomar match': 599
Ergebnis 'atomar no match': nil

Die letzten vier Zeilen der Ausgabe sollen nur zeigen, dass ich nicht geschummelt habe. Das Muster mit der atomaren Klammerung erkennt genauso viele Zeichen wie das Originalmuster ohne die Klammerung, und es erkennt genau so wenig den String in 'uebler' wie das Original – nur lässig ungefähr 25 mal schneller…

Wer Lust und genügend Zeit hat, kann den Test auch mit den Strings 'xxaxxb' * 1000 oder 'xxaxxb' * 10000 probieren – wobei genügend Zeit durchaus bedeuten kann, dass man seinen Urururur(ur)*enkeln testamentarisch die Bitte hinterlässt, hin und wieder mal nach einem Ergebnis zu schauen.

Was folgt daraus? Wenn Reguläre Ausdrücke mehrfach * oder + geschachtelt oder nacheinander enthalten, sollten diese unter Benutzung atomarer Klammerung umformuliert werden. Gibt das Schwierigkeiten, bleibt eigentlich nur ein tieferes Studium vom Friedl (Jeffrey E. F. Friedl: Mastering Regular Expressions, 2003, O’Reilly, Köln.) Oder man versucht die anstehende Aufgabe anders zu lösen (beispielsweise durch mehrere Ausdrücke und Programmierung).