Regulärer Ausdruck

  • Regex / RegExp

  • Suchmuster

  • Zeichenkette, die eine Mengen von Zeichenketten mittels bestimmter syntaktischer Regeln beschreibt

  • in UNIX-Werkzeugen schon lange vorhanden

  • Syntax differiert je nach Werkzeug und Version

  • POSIX: BRE / ERE - Basic/Extended Regular Expression

    Feature

    BRE

    ERE

    . ^ $ […] [^…]

    ja

    ja

    Kleene-Stern

    *

    *

    Quantoren + ?

    + ?

    Quantor Min/Max

    \{min,max\}

    {min,max}

    Gruppierung

    \(…\)

    (…)

    Quantoren wirken auf Gruppen

    ja

    ja

    Rückwärtsreferenzen

    \1 bis \9

    Alternation

    |

  • siehe auch: Regular Expressions

  • GNU-Versionen von grep/sed: BRE/ERE funktionell identisch, bei ERE kein Backslash vor ? + () {}

  • Perl hat eine sehr leistungsfähige RegExp-Maschine, die andere Implementierungen beeinflusste, auch bzgl. der Notation

  • PCRE (Perl Compatible Regular Expressions) ist eine unabhängige C-Implementierung von Philip Hazel, die sich syntaktisch und semantisch an Perl 5 orientiert

  • von Henry Spencer stammt eine andere leistungsfähige RegExp-Bibliothek in C (sie ist in Tcl integriert); siehe auch regex - Henry Spencer’s regular expression libraries

RegExps in Tools und Programmiersprachen

  • Sed / Grep 

    # major release bei RHEL/Fedora ermitteln
# Scientific Linux release 6.5 (Carbon)
# Fedora release 22 (Twenty Two)
sed -e 's/.*release //' -e 's/[. ].*//' /etc/redhat-release

echo -e 'python 3.4\nperl 5.8' | sed -r 's/(\<.*\>)[[:space:]](\<.*\>).*/\2 \1/'

echo -e 'python 3.4 rossum\nperl 5.8 wall\nphp 5.4 lerdorf' |
  sed -r 's/(.*)[[:space:]]+([[:digit:].]+)(.*)/\2 \1 von\3/'

echo -e 'aa aa\naa cc\nbb bb' | sed -nr '/([^ ]+) \1/p'

echo aaa | sed 's/.*/& &/'

# analog mit grep/egrep
echo -e 'aa aa\naa cc\nbb bb' | grep '\([^ ]\+\) \1'
echo -e 'aa aa\naa cc\nbb bb' | egrep '([^ ]+) \1'

# Wortgrenze \b, Wortanfang \<, Wortende \>
echo '123 456 789' | egrep -o '\b.'
echo '123 456 789' | sed -n 's/\b/*/gp'

# Wortanfang/Wortende getrennt behandeln
echo '123 456 789' | sed -n 's/\</*/gp'
echo '123 456 789' | sed -n 's/\>/*/gp'
echo '123 456 789' | sed -e 's/\</*/g' -e 's/\>/\&/g'

  • Bash 

    datum=23.10.2015
if [[ $datum =~ ^([0-9]{1,2})\.([0-9]{1,2})\.([0-9]{4})$ ]]
then
  echo "Tag  : ${BASH_REMATCH[1]}"
  echo "Monat: ${BASH_REMATCH[2]}"
  echo "Jahr : ${BASH_REMATCH[3]}"
  echo "Datum: ${BASH_REMATCH[0]}"
else
  echo 'Syntaxfehler!'
fi

# klassisches Globbing bietet Mustersuche, aber keinen Kleene-Stern
#
#   * ? [...] [^...] [!...]
#
# Korn-Shell-Muster:
#
#   @(Muster-Liste) genau ein Vorkommen der Muster
#   +(Muster-Liste) mindestens ein Vorkommen der Muster
#   *(Muster-Liste) kein, ein oder mehrere Vorkommen der Muster
#   ?(Muster-Liste) kein oder genau ein Vorkommen der Muster
#   !(Muster-Liste) keines der angegebenen Muster

shopt -s extglob
for i in anton berta caesar dora emil anna
do
  [[ $i == @(a*|*i*) ]] && echo "1: $i"
  [[ $i == !(e*) ]] && echo "2: $i"
  [[ $i == ???? ]] && echo "3: $i"
done

    siehe auch Bash Hackers Wiki: Patterns and pattern matching

  • Vim

    • Online-Hilfe: 

      :help pattern

    • Beachte: 

      :set magic

    • Reguläre Ausdrücke bei VIM

    • ersetze alle Wörter aller mit einer Ziffer beginnenden Zeilen durch ihr Uppercase-Äquivalent: 

      :g/^[0-9]/s/\<.\{-\}\>/\U&\E/g

    • Unicode-Zeichensuche wird unterstützt: 

      /\%u20AC     Matches the character specified with up to four hexadecimal characters.
/\%U1234abcd Matches the character specified with up to eight hexadecimal characters.

    • Vim 7.4 hat 2 RegExp-Maschinen: 

      :help NFA
      Vim includes two regexp engines:
1. An old, backtracking engine that supports everything.
2. A new, NFA engine that works much faster on some patterns, but does not
   support everything.
      Vim will automatically select the right engine for you.  However, if you run
into a problem or want to specifically select one engine or the other, you
can prepend one of the following to the pattern:
      \%#=0   Force automatic selection.  Only has an effect when
        'regexpengine' has been set to a non-zero value.
\%#=1   Force using the old engine.
\%#=2   Force using the NFA engine.
      You can also use the 'regexpengine' option to change the default.

  • Java

    • Match.java 

      public class Match {
  public static void main(String[] args) throws Exception {
    String s = "die Autobahn-Meisterei";
    // der gesamte String muss passen
    String regex = ".*(?i)autobahn[- ]?meisterei.*";
    if (s.matches(regex)) {
      System.out.println("OK: " + s);
    }
  }
}

    • Datum.java 

      // Datumsangaben im Format TT.MM.(JJ)JJ erkennen
import java.util.regex.*;

public class Datum {
  public static void main(String[] args) throws Exception {
    String date = "23.10.2015";
    Pattern p = Pattern.compile("^(\\d\\d)\\.(\\d\\d)\\.(\\d\\d(?:\\d\\d)?)$");
    Matcher m = p.matcher(date);
    if (m.find()) {
      String tag   = m.group(1);
      String monat = m.group(2);
      String jahr  = m.group(3);
      System.out.printf("OK: %s-%s-%s\n", tag, monat, jahr);
    }
  }
}

    • Replace.java 

      import java.util.regex.*;

public class Replace {
  public static void main(String[] args) {
    String text = "A<br>B<BR>C";
    Pattern p = Pattern.compile("<br>", Pattern.CASE_INSENSITIVE);
    Matcher m = p.matcher(text);
    String result = m.replaceAll(" $0 ");
    System.out.println(result);
  }
}

  • Perl

    • Match.pl 

      my $s = "die Autobahn-Meisterei";
if ($s =~ m/autobahn[- ]?meisterei/i) { print "OK\n"; }

    • Datum.pl 

      # Datumsangaben im Format TT.MM.(JJ)JJ erkennen

my $date  = "23.10.2015";
my $regex = qr!^(\d\d)\.(\d\d)\.(\d\d(?:\d\d)?)$!;
if ($date =~ m/$regex/) {
  print "OK: $1-$2-$3\n";
}

    • Replace.pl 

      my $s = "A<br>B<BR>C";
$s =~ s#<br># $& #ig;
print "$s\n";

  • Awk

    • Datum.sh 

      # Datumsangaben im Format TT.MM.(JJ)JJ erkennen

echo '23.10.2015' | awk '/^[0-9][0-9]\.[0-9][0-9]\.[0-9][0-9]([0-9][0-9])?$/'
echo '23.10.15'   | awk --re-interval '/^([0-9]{2}\.){2}([0-9]{2}){1,2}$/'
echo '23.10.2015' | awk --re-interval '/^([[:digit:]]{2}\.){2}([[:digit:]]{2}){1,2}$/'

{
  echo 'PID 17'
  echo 'PID 5'
  echo 'PID 392'
  echo 'dummy 1000'
  echo 'PID 22'
} | awk 'match($0, /^PID ([[:digit:]]+)/, arr) { if (arr[1] > max) max = arr[1] } END { print max + 1 }'

echo '---'
{
  echo '2015-10-23'
  echo '23.10.2015 14:05:03'
  echo '23.10.2015'
} | awk -f Datum.awk

    • Datum.awk 

      # Umwandlung des Datumsformats: Version 1
# 2004-04-07 --> 07.04.2004
function date_change(s)
{
  return gensub(/^([0-9]+)-([0-9]+)-([0-9]+).*/, "\\3.\\2.\\1", "h", s)
}

# Umwandlung des Datumsformats: Version 2
# 07.04.2004 14:05:03 --> 20040407
function date_change_2(s)
{
  return gensub(/^([0-9]+)\.([0-9]+)\.([0-9]+) .*/, "\\3\\2\\1", "h", s)
}

{
  print $0 "|" date_change($0) "|" date_change_2($0)
}

    • Replace.awk 

      BEGIN {
  IGNORECASE = 1
  s = "A<br>B<BR>C"
  gsub(/<br>/, " & ", s)
  print s
}

RegExp-Modi

  • typisch:

    • IGNORECASE (?i)

    • MULTILINE (?m)

    • DOTALL (?s)

    • VERBOSE (?x)

  • in der Shell: 

    echo 'aa AA aA Aa bb' | grep -oi 'aa'
echo 'aa AA aA Aa bb' | pcregrep -o '(?i)aa'

  • bei Python: 

    re.findall('^A.*', 'Anton\nAugust\nBerta')
re.findall('(?m)^A.*', 'Anton\nAugust\nBerta')

re.findall('.*', 'Anton\nAugust\nBerta')
re.findall('(?s).*', 'Anton\nAugust\nBerta')

regex.search('A.*t', 'Anton\nAugust\nBerta')
regex.search('(?s)A.*t', 'Anton\nAugust\nBerta')

regex.search('(?x) \d+ . \d+ ', '111.33')
regex.search('\d+ . \d+ ', '111.33')
regex.search('\d+.\d+', '111.33')

RegExp-Syntax

RegExp-Maschinen

  • die folgenden Informationen stammen primär aus dem Buch
    Reguläre Ausdrücke von Jeffrey Friedl (3. Auflage)

  • Friedl unterscheidet 4 Maschinen-Typen:

    Typ

    Programme

    DFA

    die meisten Versionen von awk und egrep, flex, lex, MySQL, Procmail

    traditioneller NFA

    GNU Emacs, die meisten Versionen von grep und sed, less, more, .NET, PCRE, Perl, PHP, Python, Ruby, vi

    POSIX-NFA

    mawk, GNU Emacs (falls gewünscht)

    Hybrider NFA/DFA

    GNU awk/grep/egrep, Tcl

  • DFA: Deterministic Finite Automaton, deterministischer endlicher Automat

  • NFA: Nondeterministic Finite Automaton, nichtdeterministischer endlicher Automat

  • 2 Grundregeln:

    • der früheste, also am weitesten links beginnende Treffer gewinnt

    • die Standard-Quantoren * + ? {} sind gierig

  • NFAs:

    • sind RegExp-gesteuert: die Maschine wird von der RegExp kontrolliert, geht also die RegExp elementweise durch

    • Backtracking ist ein zentrales Konzept: Teile der RegExp und des Textes können ggf. viele Male untersucht werden, da bei Fehlschlägen zu früheren Entscheidungspunkten zurückgekehrt wird

    • 2 Backtracking-Regeln:

      • bei der Wahl zwischen "ausprobieren" und "überspringen" (z.B. bei einem Unterausdruck mit Quantor) wird bei gierigen Quantoren stets zuerst ausprobiert, bei nicht-gierigen dagegen übersprungen

      • bei einem Fehlschlag wird die zuletzt gespeicherte Möglichkeit angesteuert (Stack)

    • die Struktur der RegExps bestimmt, wie die Maschine vorgeht

    • bei ungünstig konstruierten RegExps dauert die Suche ggf. "unendlich" lange

    • traditioneller NFA:

      • ausdrucksstärkster Typ von RegExp-Maschinen

      • man kann exakt den jeweils interessanten Treffer suchen

      • die Alternation ist geordnet

    • POSIX-NFA:

      • muss den längsten Treffer finden

      • die Alternation ist gierig

  • DFAs

    • sind textgesteuert: der Text wird zeichenweise durchlaufen, die Maschine kehrt nie zurück (kein Backtracking)

    • jedes gelesene Zeichen bestimmt eindeutig (deterministisch) den Folgezustand der Maschine

    • arbeiten sehr schnell, ihre Mustererkennung ist sehr konsistent

    • die Struktur des Musters beeinflusst die Arbeitsweise der Maschine nicht

    • sie finden (in allen bekannten Implementierungen) den längsten möglichen Treffer, wobei ein kürzester Gesamttreffer grundsätzlich möglich wäre (kürzester Weg im Zustandsgraphen)

    • sie können folgende Merkmale nicht haben:

      • einfangende geklammerte Unterausdrücke und Rückwärtsreferenzen

      • Lookaround und andere zusammengesetzte Zusicherungen der Länge Null

        • sie verbrauchen keinen Text, sondern finden nur die Position, an der der Unterausdruck passt

      • nicht-gierige Quantoren und geordnete Alternation

      • possessive Quantoren und atomare Gruppen

        • wenn ein solcher geklammerter Unterausdruck einmal gepasst hat, findet in ihm kein Backtracking mehr statt

        • der gesamte Unterausdruck ist atomar, kann also beim Backtracking nur geschlossen, nicht aber teilweise zurückgenommen werden

        • possessive Quantoren sind generell gierig

  • hybride Maschinen:

    • einfacher und effektiver Ansatz bei GNU grep: nutzt nach Möglichkeit einen DFA und einen NFA nur dann, wenn Rückwärtsreferenzen benötigt werden

    • ähnlich bei GNU awk:

      • nutzt für "Passt-das-Tests" den sehr schnellen DFA von grep (der nur den kürzesten frühesten Treffer findet) und den NFA, um den Treffer exakt zu bestimmen

      • so kann es bei gensub() einfangende Klammern und Rückwärtsreferenzen unterstützen

    • Henry Spencers Maschine vereint die Vorteile von DFAs und NFAs:

      • die Struktur der RegExps beeinflusst die Arbeitsweise der Maschine viel weniger als bei traditionellen NFAs

      • da sie nicht an bestimmten Problemen von NFAs leidet, kann man sich als RegExps-Autor viele Optimierungen sparen

      • bietet Lookaround, einfangende Klammern, Rückwärtsreferenzen, nicht-gierige Quantoren und den längsten Treffer laut POSIX

RegExps-Beispiele bei Shell-Tools

# Suche mit Äquivalenzklasse
echo 'mañana' | egrep -o 'a[[=n=]]a'

# Zeichen zwischen \Q und \E werden literal behandelt
echo 'a\bc' | pcregrep '\Q\b\E'

# den Maschinentyp ermitteln
#
# traditionelle NFA?
# - häufigster Maschinen-Typ
# - nicht-gierige Quantoren sind typisch (bei DFA nicht möglich und bei POSIX
#   nicht standardkonform)
#
echo 'nfa not' | egrep -o 'nfa|nfa not'    # nfa not ==> DFA (POSIX theoretisch möglich)
echo 'nfa not' | pcregrep -o 'nfa|nfa not' # nfa     ==> traditionell
echo 'nfa not' | sed -rn '/nfa|nfa not/p'  # not nfa ==> DFA (POSIX theoretisch möglich)

# DFA oder POSIX?
#  - DFA hat keinen einfangende Klammern und Rückwärtsreferenzen, Hybridsysteme
#    können sie haben
#  - NFA braucht bei folgender Suche meist länger oder stürzt ab
echo '=XX==============================' | egrep 'X(.+)+X' # sehr schnell, DFA
echo '=XX==============================' | awk '/X(.+)+X/' # dito

# sed -E
# /* Undocumented, for compatibility with BSD sed.  */
#   case 'E':
#   case 'r':
echo '=XX==============================' | sed -En '/X(.+)+X/p' # auch sehr schnell
echo '=XX==============================' | sed -rn '/X(.+)+X/p' # dito

echo '=XX==============================' | pcregrep 'X(.+)+X'   # scheitert
# pcregrep: pcre_exec() error -8 while matching this line:
# =XX==============================
# pcregrep: error -8 means that a resource limit was exceeded
# pcregrep: check your regex for nested unlimited loops

# gierig vs. nicht-gierig
echo 'abcde abcde' | pcregrep -o '.*e'  # abcde abcde
echo 'abcde abcde' | pcregrep -o '.*?e' # abcde
                                        #  abcde

# Unicode-Eigenschaft \{N} - numerisches Zeichen
echo 'äöü1abc2' | pcregrep -o '\p{N}'   # �
                                        # 1
                                        # 2

# normale einfangende Klammer mit Backtracking
echo Dürrröhrsdorf | pcregrep '(r.*){5}'    # Dürrröhrsdorf
echo Dürrröhrsdorf | pcregrep -o '(r.*){5}' # rrröhrsdorf
echo Dürrröhrsdorf | pcregrep '(r.*)f'      # Dürrröhrsdorf

# mit atomarer Gruppe
echo Dürrröhrsdorf | pcregrep '(?>r.*){5}' # kein Treffer
echo Dürrröhrsdorf | pcregrep '(?>r.*)'    # Dürrröhrsdorf
echo Dürrröhrsdorf | pcregrep '(?>r.*)f'   # kein Treffer

# rekursive Muster
# \1 bezieht sich hier bei PCRE in jedem Schritt auf den Match des vorherigen
# Schrittes in der durch den Quantor + erzeugten Iteration; das Muster muss
# erlauben, dass Schritt 1 ohne Rückwärtsreferenz auskommt
echo 'aaaa'    | pcregrep -o '(a|b\1)+' # aaaa
echo 'aaaaba'  | pcregrep -o '(a|b\1)+' # aaaaba
echo 'aba'     | pcregrep -o '(a|b\1)+' # aba
echo 'abaaba'  | pcregrep -o '(a|b\1)+' # abaaba
echo 'ababbaa' | pcregrep -o '(a|b\1)+' # ababbaa
echo 'ab'      | pcregrep -o '(a|b\1)+' # a

# bedingte Unterausdrücke
# die schließende Klammer wird nur gesucht, wenn es eine öffnende gab
echo '(abc)' | pcregrep -o '(\()?[^()]+(?(-1)\))' # (abc)
echo 'abc)'  | pcregrep -o '(\()?[^()]+(?(-1)\))' # abc
echo '(abc'  | pcregrep -o '(\()?[^()]+(?(-1)\))' # abc

# rekursive Muster: finde einen Ausdruck mit korrekt verschachtelten Klammern
echo '()'               | pcregrep -o '(?x)\( ( [^()]++ | (?R) )* \)'    # ()
echo '(abcd)'           | pcregrep -o '(?x)\( ( [^()]++ | (?R) )* \)'    # (abcd)
echo '(a(b(c)))'        | pcregrep -o '(?x)\( ( [^()]++ | (?R) )* \)'    # (a(b(c)))
echo '(xx(x(abcd)x)xx)' | pcregrep -o '(?x)\( ( [^()]++ | (?R) )* \)'    # (xx(x(abcd)x)xx)

# mit zusätzlichen äußeren Klammern kann man hier \1 nutzen, um die Rekursion
# auf diesen Unterausdruck zu beschränken
echo '(xx(x(abcd)x)xx)' | pcregrep -o '(?x)(\( ( [^()]++ | (?1) )* \))'  # (xx(x(abcd)x)xx)

# auch relative Nummern sind möglich
# (?-2) bezieht sich auf die vorletzte offene Klammer, die der Rekursion
# vorausgeht
echo '(xx(x(abcd)x)xx)' | pcregrep -o '(?x)(\( ( [^()]++ | (?-2) )* \))' # (xx(x(abcd)x)xx)

# eine mit (?| beginnende Gruppe setzt in jeder Alternative die Nummer der
# einfangenden Klammern zurück; \1 bezieht sich daher auf den jeweiligen
# Treffer
echo 'abcabc' | pcregrep -o '(?|(abc)|(def))\1' # abcabc
echo 'abcdef' | pcregrep -o '(?|(abc)|(def))\1'
echo 'defdef' | pcregrep -o '(?|(abc)|(def))\1' # defdef
echo 'defabc' | pcregrep -o '(?|(abc)|(def))\1'

# Steuerung des Backtrackings
# der aktive Unterausdruck wird bei *ACCEPT erfolgreich beendet
echo 'AAD' | pcregrep -o 'A((?:A|B(*ACCEPT)|C)D)' # AAD
echo 'ACD' | pcregrep -o 'A((?:A|B(*ACCEPT)|C)D)' # ACD
echo 'AB'  | pcregrep -o 'A((?:A|B(*ACCEPT)|C)D)' # AB
echo 'ABD' | pcregrep -o 'A((?:A|B(*ACCEPT)|C)D)' # AB

# wenn C fehschlägt, wird zu FAIL gegangen; damit scheitert der ganze
# Unterausdruck sofort, da es keine weiteren Alternativen gibt; es erfolgt kein
# Backtracking zu A, sondern ein Übergang zu D
echo 'ABD'  | pcregrep -o '(?x)A (B(*THEN)C | (*FAIL)) | D' # D
echo 'ABCD' | pcregrep -o '(?x)A (B(*THEN)C | (*FAIL)) | D' # ABC
                                                            # D
# negatives leeres Lookahead (?!) wirkt wie (*FAIL*)
echo 'ABCD' | pcregrep -o '(?x)A (B(*THEN)C | (?!)) | D'    # ABC
                                                            # D

RegExps-Beispiele bei Python

import re, regex, pcre

# Python hat nur Wortgrenze \b, keinen Wortanfang \< und kein Wortende \>
# man kann das mit Lookaround formulieren
# \< entspricht (?<!\w)(?=\w)
# \> entspricht (?<=\w)(?!\w)

# regex unterstützt Mengenoperationen bei Zeichenklassen:
# Vereinigung, Differenz, symmetrische Differenz, Durchschnitt
#
# Bsp.: [ab&&cd] und [[a||b]&&[c||d]] sind äquivalent

# Multiline-Modus
regex.findall('(?m).\.$', 'aa.\nbb.\ncc.')
# ['a.', 'b.', 'c.']
regex.findall('(?m).\.\Z', 'aa.\nbb.\ncc.')
# ['c.']

# gierig vs. nicht-gierig
pcre.search(r'.*e', 'abcde abcde')
# <pcre.Match object; span=(0, 11), match='abcde abcde'>
pcre.search(r'.*?e', 'abcde abcde')
# <pcre.Match object; span=(0, 5), match='abcde'>

# nur gruppierende, nicht einfangende Klammer, hier gleich mit Modusmodifikator
# im Muster
regex.search(r'(?:(?i)saturday|sunday)', '1 saturday 2 sunday 3 monday')[:]
# ('saturday',)
# das kann man abkürzen
regex.search(r'(?i:saturday|sunday)', '1 saturday 2 sunday 3 monday')[:]
# ('saturday',)
# einfangende Klammer
regex.search(r'((?i)saturday|sunday)', '1 saturday 2 sunday 3 monday')[:]
# ('saturday', 'saturday')

# Rücksetzen des Match-Starts mit \K
# die vor \K gefundenen Zeichen werden nicht in den Treffer übernommen
regex.search(r'(\w\w\K\w\w\w)', 'abcdef')[:]
# ('cde', 'abcde')
# bei der Suche von rechts nach links
regex.search(r'(?r)(\w\w\K\w\w\w)', 'abcdef')[:]
# ('bc', 'bcdef')
regex.search(r'foo\Kbar', 'foobar')
# <regex.Match object; span=(3, 6), match='bar'>
regex.search(r'foo\Kbar1', 'foobar')
regex.search(r'foo\Kbar', 'fobar')

# Such-Anker \G
# beschreibt die Position, an der jede Suche begann bzw. fortgesetzt wurde;
# kann für aufeinanderfolgende Suchen sowie in negativen Lookbehinds variabler
# Länge zu deren Begrenzung genutzt werden
#
regex.findall(r"\w{2}", "abcd ef")
# ['ab', 'cd', 'ef']
regex.findall(r"\G\w{2}", "abcd ef")
# ['ab', 'cd']
# 1. Suche startet bei Position 0 und findet 'ab'
# 2. Suche startet bei Position 2 und findet 'cd'
# 3. Suche startet bei Position 4 und findet nichts, da \G ein Weiterschalten
#    der Startposition unterbindet

# Test auf Typ der Regexp-Maschine
pcre.search(r'X(.+)+X', '=XX======================================================')
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
#   File "/home/hot/mypy2/lib/python2.7/site-packages/pcre.py", line 164, in search
#     return compile(pattern, flags).search(string)
#   File "/home/hot/mypy2/lib/python2.7/site-packages/pcre.py", line 36, in search
#     return Match(self, string, pos, endpos, flags)
# pcre.PCREError: [Errno -8] failed to match pattern

# läuft sich tot
re.search(r'X(.+)+X', '=XX======================================================')

# sehr schnell
regex.search(r'X(.+)+X', '=XX======================================================')

# Unicode-Zeichensequenz
s = 'äöü1abc2'
regex.findall(r'\p{N}', s)
# ['1', '2']

# mit span kann man den Treffer leicht herausspalten
s = '  aaaaa bb'
re.search(r'aaa', s)
# <_sre.SRE_Match object; span=(2, 5), match='aaa'>
s[2:5]
# 'aaa'

regex.search(r'(a|b)+', 'a')
# <regex.Match object; span=(0, 1), match='a'>

# rekursives Muster \1 scheitert hier, anders als bei PCRE
regex.search(r'(a|b\1)+', 'a')
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
#   File "/afs/tu-chemnitz.de/ubc/PYTHON/PYTHON_343/SL6_64/lib/python3.4/site-packages/regex.py", line 265, in search
#     return _compile(pattern, flags, kwargs).search(string, pos, endpos,
#   File "/afs/tu-chemnitz.de/ubc/PYTHON/PYTHON_343/SL6_64/lib/python3.4/site-packages/regex.py", line 513, in _compile
#     caught_exception.pos)
# _regex_core.error: cannot refer to an open group at position 6

pcre.search(r'(a|b\1)+', 'a')
# <pcre.Match object; span=(0, 1), match='a'>

# Lookaround kombiniert
# vor foo müssen 3 Ziffern und 3 andere Zeichen folgen, wobei Letztere nicht
# 999 sein dürfen
regex.search(r'(?<=\d{3}(?!999)...)foo', '222998foobar')
# <regex.Match object; span=(6, 9), match='foo'>
regex.search(r'(?<=\d{3}(?!999)...)foo', '222999foobar')

# bedingte Unterausdrücke
# eine schließende Klammer wird nur gesucht, wenn es eine öffnende gab
regex.search(r'(?x)( \( )?    [^()]+    (?(1) \) )', '(abc')
# <regex.Match object; span=(1, 4), match='abc'>
regex.search(r'(?x)( \( )?    [^()]+    (?(1) \) )', '(abc)')
# <regex.Match object; span=(0, 5), match='(abc)'>

# anders als bei PCRE ist -1 unzulässig
regex.search(r'(?x)( \( )?    [^()]+    (?(-1) \) )', '(abc)')
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
#   File "/afs/tu-chemnitz.de/ubc/PYTHON/PYTHON_343/SL6_64/lib/python3.4/site-packages/regex.py", line 265, in search
#     return _compile(pattern, flags, kwargs).search(string, pos, endpos,
#   File "/afs/tu-chemnitz.de/ubc/PYTHON/PYTHON_343/SL6_64/lib/python3.4/site-packages/regex.py", line 513, in _compile
#     caught_exception.pos)
# _regex_core.error: bad character in group name at position 30

# rekursive Muster und possessive Quantoren
# Beispiel: (?:...)++ entspricht der atomaren Gruppe (?>(?:...)+)
#
# finde einen Ausdruck mit korrekt verschachtelten Klammern
regex.search(r'(?x)\( ( [^()]++ | (?R) )* \)', '(abc)')
# <regex.Match object; span=(0, 5), match='(abc)'>

regex.search(r'(?x)\( ( [^()]++ | (?R) )* \)', '(((abc)))')
# <regex.Match object; span=(0, 9), match='(((abc)))'>

regex.search(r'(?x)\( ( [^()]++ | (?R) )* \)', '(x(xx(abc)x)xx)')
# <regex.Match object; span=(0, 15), match='(x(xx(abc)x)xx)'>

regex.search(r'(?x)\( ( [^()]++ | (?R) )* \)', '(x(xx(abc)x)xx')
# <regex.Match object; span=(2, 12), match='(xx(abc)x)'>

regex.search(r'(?x)\( ( [^()]++ | (?R) )* \)', '(x(xx(abc)x)xx))')
# <regex.Match object; span=(0, 15), match='(x(xx(abc)x)xx)'>

regex.search(r'(?x)(\( ( [^()]++ | (?-2) )* \))', '(x(xx(abc)x)xx))')
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
#   File "/afs/tu-chemnitz.de/ubc/PYTHON/PYTHON_343/SL6_64/lib/python3.4/site-packages/regex.py", line 265, in search
#     return _compile(pattern, flags, kwargs).search(string, pos, endpos,
#   File "/afs/tu-chemnitz.de/ubc/PYTHON/PYTHON_343/SL6_64/lib/python3.4/site-packages/regex.py", line 513, in _compile
#     caught_exception.pos)
# _regex_core.error: bad inline flags: no flags after '-' at position 23

# eine mit (?| beginnende Gruppe setzt in jeder Alternative die Nummer der
# einfangenden Klammern zurück; \1 bezieht sich daher auf den jeweiligen
# Treffer
regex.search(r'(?|(abc)|(def))\1', 'abcabc')
# <regex.Match object; span=(0, 6), match='abcabc'>
regex.search(r'(?|(abc)|(def))\1', 'abcdef')
regex.search(r'(?|(abc)|(def))\1', 'defdef')
# <regex.Match object; span=(0, 6), match='defdef'>
regex.search(r'(?|(abc)|(def))\1', 'defabc')

Effizienz

  • Friedl beschreibt diverse Optimierungen, die die Effizienz der Suche mehr oder minder stark verbessern können

  • hilfreich sein kann u.a.:

    • Neukompilierungen von RegExps vermeiden

    • nicht-einfangende Klammern verwenden, wenn sie nur der Gruppierung dienen

    • unnötige Klammern weglassen

    • unnötige Zeichenklassen weglassen: \. statt [.]

    • ggf. Anker am Anfang verwenden, z.B. bei '\A.*'

    • literalen Text herausstellen, z.B. xx* statt x+ oder kl(?:ipp|ar) statt (?:klipp|klar)

    • Anker herausstellen: ^(?:abc|123) statt ^abc|^123

    • $ am Ende ausklammern: (...|...)$ statt (...$|...$)

    • atomare Gruppen und possessive Quantoren nutzen

  • Beispiel aus dem PCRE-Manual 

    Possessive quantifiers can be used in conjunction with lookbehind assertions
to specify efficient matching of fixed-length strings at the end of subject
strings. Consider a simple pattern such as
    abcd$
    when applied to a long string that does not match. Because matching proceeds
from left to right, PCRE will look for each "a" in the subject and then see if
what follows matches the rest of the pattern. If the pattern is specified as
    ^.*abcd$
    the initial .* matches the entire string at first, but when this fails (because
there is no following "a"), it backtracks to match all but the last character,
then all but the last two characters, and so on. Once again the search for "a"
covers the entire string, from right to left, so we are no better off. However,
if the pattern is written as
    ^.*+(?<=abcd)
    there can be no backtracking for the .*+ item; it can match only the entire
string. The subsequent lookbehind assertion does a single test on the last four
characters. If it fails, the match fails immediately. For long strings, this
approach makes a significant difference to the processing time.

Links und Literatur