Eingefassten Text erkennen

(Auszug aus "Reguläre Ausdrücke" von Jeffrey E. F. Friedl)

Einen Text in Anführungszeichen oder eine IP-Adresse zu erkennen sind nur zwei Aufgaben aus einer ganzen Klasse von ähnlich gelagerten Problemen: Man will Text erkennen, der durch bestimmte Begrenzer eingefasst (oder getrennt) ist. Die Begrenzer bestehen häufig aus mehreren Zeichen. Beispiele dazu:

• Kommentare in C, die durch ›/*‹ und ›*/‹ begrenzt werden
• HTML-Tags, also Text, der durch spitze Klammern (<...>) wie bei <CODE> eingefasst ist
• Text zwischen HTML-Tags herausholen, z.B. den Text ›Hier●klicken!‹ aus dem Link ›<A●HREF="...">Hier●klicken!</A>‹
• Eine Zeile aus einer .mailrc-Datei erkennen. Diese Datei kann E-Mail-Aliases in der Art

  alias  Kürzel   volle-Adresse

  enthalten, wie etwa ›alias jeff jfriedl@regex.info‹. (Hier sind die Begrenzungszeichen einfach die Leerzeichen zwischen den Wörtern sowie auch die Zeilenenden.)
• Text zwischen Anführungszeichen erkennen und dabei zulassen, dass mittendrin mittels Backslash geschützte Anführungszeichen auftreten, wie im Beispiel:

  a passport needs a "2\"x3\" photo" of the holder.

• Das Parsen von CSV-Dateien (»comma-separated values«, durch Kommas getrennte Werte, ein häufiges Austauschformat bei Datenbanken)

Das Problem kann allgemein so angegangen werden:

1. Finde die öffnenden Begrenzungszeichen.
2. Finde den eigentlichen Text
   (das heißt »alles, was nicht zum schließenden Begrenzer gehört«).
3. Finde die schließenden Begrenzungszeichen.

Wie Sie schon gesehen haben, kann es bei Punkt 2, »alles, was nicht zum schließenden Begrenzer gehört«, schwierig werden, wenn die Begrenzer aus mehreren Zeichen bestehen oder wenn sie im eigentlichen Text vorkommen können.

Geschützte Anführungszeichen in Strings in Anführungszeichen zulassen

Im Beispiel 2\"x3\" ist der Begrenzer das Anführungszeichen ("Gänsefüßchen"), aber mittendrin können wieder Anführungszeichen vorkommen, sofern sie mit einem Backslash geschützt sind. Die öffnenden und schließenden Begrenzungszeichen sind einzelne Zeichen und damit einfach zu behandeln. Schwieriger ist es mit dem Text dazwischen.

Klares Denken hilft hier: Wenn ein Zeichen kein Anführungszeichen ist (also ˹[^"]˼), dann passt es sicher. Wenn es ein Anführungszeichen ist, dann ist es nur dann zugelassen, wenn davor ein Backslash steht. Wenn wir die Formulierung »wenn davor« wörtlich in eine Lookbehind-Zusicherung (siehe Lookahead; Lookbehind) übersetzen, erhalten wir ˹"([^"]|(?<=\\)")*"˼, dies erkennt das 2\"x3\"-Beispiel korrekt.

Das ist aber auch das perfekte Beispiel, wie sich ungewollte Treffer in eine scheinbar korrekte Regex einschleichen können. Die Regex funktioniert nicht in allen Fällen. Wir möchten, dass die Regex auf den unterstrichenen Teil in diesem etwas albernen Text passt:

Darth-Symbol: "/-|-\\" oder "[^-^]"

Aber tatsächlich wird Folgendes gefunden:

Darth-Symbol: "/-|-\\" oder "[^-^]"

Das liegt daran, dass vor dem schließenden Begrenzungszeichen im ersten String tatsächlich ein Backslash auftritt. Dieser Backslash ist selbst durch einen weiteren Backslash geschützt, er schützt nicht das nachfolgende Anführungszeichen (und dieses Anführungszeichen ist tatsächlich das schließende Begrenzungszeichen). Unser Lookbehind-Konstrukt erkennt nicht, dass das Escape-Zeichen selbst geschützt ist, und es kann ja auch sein, dass davor eine ganze Reihe von ›\\‹-Sequenzen auftritt – vielleicht war das Lookbehind doch keine so gute Idee. Wir sollten die geschützten Zeichen schon beim ersten Durchsuchen des Strings erkennen, nicht erst hinterher.

Wir konzentrieren uns jetzt auf die Dinge, die wir zwischen den öffnenden und schließenden Begrenzern zulassen wollen. Jedes geschützte Zeichen ist zulässig ˹(\\.)˼, und außerdem jedes Zeichen außer dem Begrenzungszeichen ˹([^"])˼. Das ergibt ˹"(\\.|[^"])*"˼.

Toll, Problem gelöst! Leider stimmt hier wieder etwas nicht. Auch hier gibt es Strings, die unerwünschte Treffer ergeben, zum Beispiel, wenn das schließende Anführungszeichen fehlt:

"You need a 2\"x3\" photo.

Warum wird hier ein Treffer gefunden? Erinnern wir uns an die Erfahrung aus dem Abschnitt Gierig oder genügsam – der Treffer geht vor. Zunächst wird in der Tat der gesamte Text bis zum Punkt erkannt. Danach aber geht die Maschine, weil kein schließendes Anführungszeichen gefunden wird, mittels Backtracking zurück bis zum Zustand:

im Text: ›...2\"x3▵\"●...‹

in der Regex: ˹(\\.|▵[^"])˼

An diesem Punkt passt ˹[^"]˼ auf den Backslash, und das Anführungszeichen danach wird fälschlicherweise als schließendes Zeichen erkannt.

Wir lernen daraus:

Wenn mittels Backtracking ein unerwünschter Treffer aus einer Alternation gefunden wird, ist das ein Zeichen dafür, dass auch die erwünschten Treffer nur aus der Anordnung der Alternativen entstehen.

Wären die Alternativen in der Regex vertauscht, würden die geschützten Anführungszeichen nicht übersprungen. Das Problem ergibt sich daraus, dass die eine Alternative auf etwas passt, was wir eigentlich der anderen Alternative überlassen wollten.

Wie können wir das reparieren? Wie beim Problem mit den Fortsetzungszeilen müssen wir sicherstellen, dass es keine andere Möglichkeit als die vorgesehene gibt, einen Backslash zu erkennen. Wir ändern also ˹[^"] in ˹[^\\"]˼. Das berücksichtigt, dass sowohl das Anführungszeichen als auch der Backslash in diesem Zusammenhang »speziell« sind und entsprechend behandelt werden müssen. Das Resultat ˹"(\\.|[^\\"])*"˼ funktioniert denn auch. (Auch eine funktionierende Regex kann für einen NFA oft noch effizienter gemacht werden; Sie werden dieses Beispiel unter Die Kunst, reguläre Ausdrücke zu schreiben erneut antreffen, siehe Ein ernüchterndes Beispiel.)

Aus dem Beispiel können Sie also Folgendes lernen:

Beim Aufbau einer Regex müssen auch die Fälle berücksichtigt werden, die nicht erkannt werden sollen, besonders auch unerwartete oder »falsche« Daten.

Die Regex funktioniert, aber es gäbe auch andere Reparaturmöglichkeiten. Wenn possessive Quantoren (siehe Possessive Quantoren) oder atomare Gruppen (siehe Atomare Klammern) unterstützt werden, könnte man die Regex auch durch ˹"(\\.|[^"])*+"˼ oder ˹"(?>(\\.|[^"])*)"˼ ersetzen. Beides funktioniert, und doch wird das Problem hier eher vertuscht als gelöst. Es wird einfach verhindert, dass die Maschine mittels Backtracking dorthin zurückkrebst, wo Probleme entstehen könnten.

Wenn Sie verstehen, wie der possessive Quantor oder die atomare Gruppe hier hilft, ist das sehr wertvoll. Dennoch werden wir mit der ersten Reparaturmöglichkeit fortfahren, weil sie eher anwendbar ist. Eigentlich könnte man hier zur ersten Reparatur auch noch den possessiven Quantor oder die atomare Klammer anwenden – nicht um das Problem zu lösen, denn das ist schon beseitigt, sondern um die Mustersuche effizienter zu machen, denn so wird ein Fehlschlag viel schneller erkannt.

  

<< zurück

vor >>

 

 

 

---

F