Advanced   Java   Services

Reguläre Ausdrücke

Das Durchsuchen von Texten nach bestimmten Stellen oder eventuelles Ersetzen von Textteilen durch andere Textteile ist eine der Standardaufgaben, die immer wieder bewältigt werden müssen. Dazu gibt es die Metasprache der regulären Ausdrücke. Erfunden wurde diese Sprache von dem Mathematiker und Logiker Stephen Cole Kleene (January 5, 1909, Hartford, Connecticut, United States – January 25, 1994, Madison, Wisconsin)

Der Computerpionier Kenneth Lane Thompson (Mitarbeiter der Bell Laboratories, einer Nachfolgefirma der Firme AT&T Bell Telephone Laboratories) entwarf in den 50-er Jahren einen Texteditor, der die von Kleene eingeführte Notation übernahm um damit Zeichenfolgen in Texten zu suchen. Kurze Zeit später übertrug er dieses Werkzeug auf den UNIX-Editor ed und entwarf anschließend auch das berühmten UNIX-Kommando grep (g-lobal r-egular e-xpression p-rint).

Siehe dazu

http://en.wikipedia.org/wiki/Regular_expression

http://en.wikipedia.org/wiki/Stephen_Cole_Kleene

http://en.wikipedia.org/wiki/Ken_Thompson

http://en.wikipedia.org/wiki/Bell_Labs

http://en.wikipedia.org/wiki/Grep

Reguläre Ausdrücke sind ein Mittel um Zeichenfolgen in Texten zu finden (regular exprssions are a means to match patterns in text files) und ggf. zu modifizieren. Dazu bedient man sich einer Metasprache. Die zu suchende Zeichenfolge muß man in einen regulären Ausdruck übersetzen. Zusammen mit dem zu durchsuchenden Text wird dieser einer Art Suchmaschine übergeben. Das Ergebnis kann dann ein boolescher Wert sein (true oder false) oder auch eine Reihe von Indizes, die den jeweiligen Beginn der Zeichenfolge angeben. Je nachdem welche Zeichenfolge man suchen will kann das Erstellen des pasenden regulären Ausdrucks sehr einfach, aber auch sehr schwer sein. Das von Kleene entwickelte Werkzeug ist sehr mächtig, aber nicht immer einfach zu verwenden. Jede moderne Programmiersprache verfügt über die Fähigkeit mit regulären Ausdrücken zu arbeiten.

Wir werden Begriffe wie Literal, Zeichenfolge, Metazeichen (metacharacter), Zielstring oder Suchstring, Suchausdruck oder Pattern, Escape Sequenz verwenden. Dazu ist es notwendig deren Bedeutung eindeutig zu beschreiben. Hierzu dient die folgende Tabelle.

Es gibt drei Varianten des Suchens in einer Zeichenfolge.

• Suchen nach direkter Übereinstimmung (match)
• Suche nach Teilen in einem Ganzen (find)
• Zerlegen durch Angabe von Trennzeichen (split)

Wir beginnen mit der Suche nach Teilen in einem Ganzen.

In diesen Beispielen suchen wir nicht nach einer genauen Übereinstimmung (exact match), sondern wollen das Pattern als Teil des Zielstrings finden, sozusagen die Nadel im Heuhaufen.

Die obigen Beispiele geben uns eine Ahnung von der Mächtigkeit der neuen Sprache. Bevor wir in diese Zeichenvielfalt einsteigen schauen wir uns an wie einige der obigen Beispiel mit Java codiert werden. Hierzu gibt es die Klassen Pattern und Matcher aus dem Package java.util.regex. In den meisten Fällen braucht man nur wenige der angebotenen Methoden. Der folgende Code zeigt das Vorgehen am ersten obigen Beispiel.

private static void beispiel01()
{
   String searchString = "abrakadabra";
   String pattern = "adab";

   Pattern p = Pattern.compile(pattern);
   Matcher m = p.matcher(searchString);

   while (m.find())
   {
      System.out.print(m.start() + " ");
      // liefert die indizes, wo das pattern vorkommt: 5
   }

} // end beispiel 01

Mit Hilfe der statischen Methode compile() aus Pattern wird ein Patternobjekt erzeugt. Mit der Methode matcher() übergibt man den Suchstring und erhält ein Objekt vom Typ Matcher. Die Methode find(), liefert nun solange true, solange es noch Fundstellen gibt. Hat man eine Stelle gefungen, so kann man sich mit start() die jeweiligen Anfangsindizes der Fundstellen geben lassen.

private static void beispiel02()
{
   searchString = "abbabbabba";
   pattern = "abba";
   Pattern p = Pattern.compile(pattern);
   Matcher m = p.matcher(searchString);

   while (m.find())
   {
      System.out.println(m.start() + " ");
   }
   // start() liefert die indizes 0 und 6
}

Es gibt nur zwei Treffer, das mittlere abba ist kein Treffer, da eine erneute Suche erst nach den gefunden Zeichen wieder aufgenommen wird. Trefferketten sind immer disjunkt. In Beispiel 3 ergibt das d von Gmund den einzigen Treffer an der Position 10. Interessant Ist das vierte Beispiel. Durch den vorangestellten Backslash wird das d zu einem Metazeichen und veranlaßt eine Suche nach Ziffern.

private static void beispiel04()
{
   searchString = "83703 Gmund am Tegernsee";
   pattern = "\\d";
   Pattern p = Pattern.compile(pattern);
   Matcher m = p.matcher(searchString);

   while (m.find())
   {
      System.out.println(m.start() + " ");
   }
   // start() liefert die indizes 0 1 2 3 4
}

private static void beispiel09()
{
   String searchString = "Die Isar und die Isarauen";
   String pattern = "\\bIsar\\b"; // sucht nach Isar als ganzes Wort
   Pattern p = Pattern.compile(pattern);
   Matcher m = p.matcher(searchString);

   while (m.find())
   {
      System.out.println(m.start() + " ");
   }
   // start() liefert den index 4
}

Bei den letzten beiden Beispielen ist Vorsicht geboten. Der Backslash sagt dem regex-Parser, daß der Buchstabe als ein Sonderzeichen behandelt werden soll und eine bestimmte Bedeutung besitzt, die der Parser kennt. In diesen Fällen steht \d für eine beliebige Ziffer von 0 bis 9 und \b für Wortgrenzen wie etwa einem Leerzeichen. Das Pattern \bIsar\b besteht also aus zwei Sonderzeichen, die der Parser als solche erkennt und vier Buchstaben. Da wir diese Pattern aber als String übergeben, muß der Backslash zusätzlich maskiert werden, denn in einem String bedeutet jeder Backslash die Einleitung zu einer Escapesequenz. Das Schema ist ansonsten immer das gleiche. Nur die Suchstrings und die Pattern ändern sich. Wir weisen nochmal darauf hin, daß mit find() die Suche nach Teilen in einem Ganzen realisiert wird, es wird also nicht der gesamte Zielstring mit dem Pattern verglichen. Dafür gibt es die Methode matches(). Beispiele hierzu später.

• Die Zeichenketten von Treffern sind immer getrennte Bereiche und Überlappen sich nicht.
• The find() method scans the input sequence looking for the next subsequence that matches the pattern.
• Enthält das Pattern ein mit einem Backslash eingeleitetes Sonderzeichen,
  so muß dieses in einem String durch einen zusätzlichen Backslash maskiert werden.

Die obigen Beispiele lassen uns die Mächtigkeit regulärer Ausdrücke erahnen. Neben sehr einfachen Suchmustern, die nur aus Buchstaben bestehen gibt es offensichtlich Zeichen wie u.a. ^, $, [, ] die eine besondere Bedeutung haben. Es gibt aber auch Buchstaben, die durch einen vorangestellten Backslash maskiert werden und dadurch zu einem Metazeichen werden wie \b und \d. Hinter diesen zweistelligen Metazeichen verbergen sich sog. Zeichenklassen. Zeichenklassen werden weiter unten erklärt. Der Backslash spielt noch eine weitere wichtige Rolle, denn er wird auch gebraucht um aus einem Metazeichen ein suchbares Zeichen zu machen. Auch hier spricht man von Maskierung. Wir können also folgende Regeln notieren:

• Ein Metazeichen ist entweder ein NICHT-Buchstabe (^, $, [, etc.) oder ein Buchstabe mit einem vorangestelltem Backslash (\d, \w. etc.).
• Ein einstelliges Metazeichen (^, $, [, etc.) wird durch einen vorangestellten Backslash zu einem suchbaren Zeichen.

Man beachte die Maskierung in den Beispielen 09, 15 und 16.

Ganz schön viel! Da diese Metazeichen alle mehr oder weniger miteinander kombinierbar sind, können die Patterns rasch zu sehr komplexen Gebilden heranwachsen, sodaß Kommentare, was mit einem Pattern eigentlich gesucht wird, äußerst nützlich sind. Für interessantere Beispiele brauchen wir aber noch ein wenig Theorie.

In der Liste der Metazeichen tauchen bereits Gruppen und Klassen ohne nähere Erklärung auf. Jetzt schauen wir uns das genauer an. Gruppen erkennt man an den runden Klammern, Zeichenklassen an den eckigen Klammern. Für einige Zeichenklassen gibt es Kurzschreibweisen. Gruppen und Zeichenklassen sind die Strukturelemente die zusammen mit den Metazeichen die Mächtigkeit der regulären Ausdrücke ausmachen.

Eine Gruppe wird durch ein paar runde Klammern definiert. Es gibt immer mindestens eine Gruppe, so ist etwa das Suchpattern adab aus Zeile 1 der obigen Tabelle eigentlich eine kürzere Schreibweise für (adab). Eine Gruppe ist also ein Suchpattern, daß aus einen oder mehreren Zeichen besteht. Gibt es nur eine Gruppe kann man die Klammern einfach weglassen. Klingt sehr einfach, aber es gibt folgende zusätzliche Regeln.

• Eine Gruppe besteht aus einem oder mehreren Zeichen und wird in runde Klammern eingeschlossen.
  
  
• Das Pattern als Ganzes bildet die erste Gruppe. Für diese Gruppe können die runden Klammern weggelassen werden.
  
  
• Ein Pattern kann mehr als eine Gruppe enthalten.
  
  
• Gruppen können geschachtelt werden.
  
  
• Gruppen können durch ein logisches oder (mit dem Zeichen |) verknüpft werden.

Hinweis für Logiker: Unter Voraussetzung der Aussage 3 sind die Aussagen 4 und 5 äquivalent.

Einige Beispiele

Da im letzten Beispiel keine Bereichsangabe möglich ist verwenden wir die oder-Verknüpfung.

Zeichenklassen sind ein weiteres mächtiges Instument innerhalb regulärer Ausdrücke. Eine Zeichenklasse wird durch ein Paar eckige Klammern begrenzt. Eine Zeichenklasse steht immer nur für ein einziges Zeichen in einem Suchstring. So heißt [abc] nicht, daß man nach der der Gruppe abc sucht, sondern daß man a oder b oder c sucht. Mit dem logischen Operator | für oder kann man diese Zeichenklasse auch so schreiben [a|b|c], was aber den Ausdruck eher unübersichtlicher macht.

Das Minuszeichen fungiert als Bereichszeichen. Die Zeichenklasse [a-f] steht also für den Buchstaben a oder b oder c oder d oder f, [a-fA-F] steht dann für eine Hexziffer größer als 9, egal ob groß- oder kleingeschrieben.

Neben dem Zeichen für oder | gibt es noch die zwei weitere logische Operatoren.

Das Caret ^ ist ein logisches NICHT, hat also innerhalb von eckigen Klammern eine völlig andere Bedeutung als außerhalb der eckigen Klammern (siehe die Tabelle der Metazeichen). Zudem hat es eine klammernde Wirkung, so bedeutet [^abc] "weder a noch b noch c" (aber sonst alles) und nicht etwa "b oder c aber nicht a".

Das doppelte Ampersand && ist das Zeichen für den logischen "und zugleich"-Operator oder in der Sprache der Mengenlehre das Zeichen für Durchschnitt, so bedeutet etwa [a-z&&def] nur die Zeichen d oder e oder f was ja gleichbedeutend mit [d-f] ist. Zeichenklassen mit dem "und zugleich"-Operator lassen sich oft zu leichter verständlichen einfacheren Zeichenklassen umformen. So läßt sich der Ausdruck [a-z&&[^def]] vereinfachen zu [a-cg-z].

Die Beispiel unten zeigen auch, daß die Gruppenklammer in einer Zeichenklasse ignoriert wird. Man kann in einer Zeichenklasse keine Gruppen bilden, auch die für Gruppen existierenden Wiederholungszeichen werden innerhalb einer Zeichenklasse ignoriert, siehe dazu die Beispiele 10 und 11.

Einige Beispiele

Vorsicht Fallen

Weitere Fallen

Im folgenden Beispiel wollen wir in einer HTML-Datei, die nicht W3C-konform ist, fehlerhaft geschriebene Tags finden. Wir beschränken uns dabei eine längere Zeichenkette, in der wir Zeichenketten der Form color=#abcdef finden wollen, also eine unkorrekte Farbangabe. Andere Fehler berücksichtigen wir nicht (den font-Tag etc.). Wir simulieren die Datei durch einen String, der folgendermaßen aussieht:

String searchString = "color=#abcdef\n" +
                      "xyzcolor=#090909 \n" +
                      "bgcolor=#ABCdef\n" +
                      "<font color=#ff0000 size=5>A</font><font size=3>dvanced</font>\n" +
                      "   <font color=#ff0000 size=5>\n" +
                      "<td width=17% bgcolor=#eaf5ff  >\n";

Schritt 1

Wir bauen nun unser Pattern schrittweise auf. Das erste Pattern sieht folgendermaßen aus:

color=#[a-fA-F0-9]{6}

Wir suchen also nach Einträgen die mit color=# beginnen gefolgt von 6 Hexziffern groß- oder kleingeschrieben. Wir verwenden die folgende Methode

private static void beispiel()
{
   String searchString = "color=#abcdef\n" +
                         "xyzcolor=#090909 \n" +
                         "bgcolor=#ABCdef\n" +
                         "<font color=#ff0000 size=5>N</font><font size=3>otadvanced</font>\n" +
                         "   <font color=#ff0000 size=5>\n" +
                         "<td width=17% bgcolor=#eaf5ff  >\n";

   String pattern = "color=#[a-fA-F0-9]{6}"; //

   int[] startPositions = getStartPositions(searchString, pattern); //
   int[] endPositions = getEndPositions(searchString, pattern); //
   String[] match = getMatches(searchString, pattern);

   int start, end;
   for (int i=0; i < startPositions.length; i++)
   {
     start = startPositions[i];
     end = endPositions[i];
     System.out.println("start " + start + "  end " + end);
     System.out.println( match[i]);
   }
}

Sie stützt sich auf die drei Hilfsmethoden getStartPositions(searchString, pattern), getEndPositions(searchString, pattern) und getMatches(searchString, pattern). Die zentralen Methoden aus der Klasse Matcher, die uns zum Ziel führen, heißen find(), start(), end() und group(). Siehe hierzu auch die Übung am Ende der Seite.

private static int[] getStartPositions(String searchString, String pattern)
{
   Matcher m = getMatcher(searchString, pattern);
   ArrayList al = new ArrayList();

   while (m.find())
   {
      al.add(m.start());
   }

   int[] pos = new int[al.size()];

   for (int i = 0; i < pos.length; i++)
   {
      pos[i] = new Integer(al.get(i).toString()).intValue();
   }
   return pos;
}

private static int[] getEndPositions(String searchString, String pattern)
{
   Matcher m = getMatcher(searchString, pattern);
   ArrayList al = new ArrayList();

   while (m.find())
   {
      al.add( m.end() );
   }

   int[] pos = new int[al.size()];

   for (int i = 0; i < pos.length; i++)
   {
      pos[i] = new Integer(al.get(i).toString()).intValue();
   }

   return pos;
}

private static String[] getMatches(String searchString, String pattern)
{
   Matcher m = getMatcher(searchString, pattern);
   ArrayList al = new ArrayList();

   while (m.find())
   {
     al.add( m.group() );
   }

   return al.toArray( new String[]{} );
}

Wir bekommen folgendes Ergebnis

start 0  end 13
color=#abcdef
start 17  end 30
color=#090909
start 34  end 47
color=#ABCdef
start 54  end 67
color=#ff0000
start 123  end 136
color=#ff0000
start 161  end 174
color=#eaf5ff

Schritt 2

Wir wollen auch die bgcolor-Einträge erfassen und ergänzen unser Pattern zu

(bg)?(color=#)[a-fA-F0-9]{6}

das liefert uns

start 0  end 13
color=#abcdef
start 17  end 30
color=#090909
start 32  end 47
bgcolor=#ABCdef
start 54  end 67
color=#ff0000
start 123  end 136
color=#ff0000
start 159  end 174
bgcolor=#eaf5ff

Schritt 3

Eigentlich suchen wir nur Einträge innerhalb eines Tags. Wir nehmen uns zuerst den Anfang vor. Sowohl vor und nach dem < können Zeichen auftauchen, die uns nicht interessieren. Wichtig ist aber nur, daß wir unsere Suche ab < beginnen. Wir ergänzen also unser Suchpattern zu

<.*(bg)?(color=#)[a-fA-F0-9]{6}

und bekommen folgendes Ergebnis

start 48  end 67
<font color=#ff0000
start 114  end 136
<font color=#ff0000
start 145  end 174
<td width=17% bgcolor=#eaf5ff

Schritt 4

Das ist schon sehr brauchbar. Nun wollen wir noch das Endetag mit aufnehmen. Nach der Hexgruppe können ja noch eine ganze Reihe von Zeichen kommen bis zum korrespondierenden Endetag. Eigentlich alles, außer dem Endetag selbst, und diese Formulierungen führt uns zu [^>]*> und damit zu dem Pattern

<.*(bg)?(color=#)[a-fA-F0-9]{6}[^>]*>

Ergebnis:

start 48  end 75
<font color=#ff0000 size=5>
start 123  end 150
<font color=#ff0000 size=5>
start 151  end 183
<td width=17% bgcolor=#eaf5ff  >

Die drei Methoden sind zwar praktisch, aber von der Performance her nicht praxistauglich. Für einen einzigen Suchvorgang wird das Pattern von der Patternmachine dreimal erzeugt und der SuchString wird dreimal durchlaufen. Schreiben Sie eine Methode, die in einem Suchdurchlauf alle Start- und Endpositionen und alle Matches sammelt und diese gebündelt zurückgibt. Dazu kann man etwa eine Klasse schreiben, deren Objekte das Gesamtergebnis aufnehmen können, dann kann man ein Objekt dieser Klasse zurückgeben.

Zum Matchen bietet die Klasse Pattern die Methode static boolean matches(String regex, CharSequence input) an. Die Methode compiliert das im ersten Argument übergebene Pattern selbst und wendet es dann auf das im zweiten Argument übergebene Objekt an. Das Interface CharSequence ist der Basistyp für alle Zeichenketten. In der Klasse String gibt es seit 1.4 die Methode public boolean matches(String regex), die sich auf die gleichnamige Methode aus der Klasse Pattern stützt.

Im folgenden Beispiel erarbeiten wir uns ein Pattern für Telefonnummern.

Telefonnummern werden immer wieder leicht verschieden geschrieben. Wir wollen einige Schreibvarianten aufzeichnen und dazu dann einen regulären Ausdruck finden. Unser Pattern soll für die folgenden Schreibvarianten passen:

089 - 345 6789
089 - 3456 789
089 - 3456789
02345 - 4455 6677
02345 -44556677
02345-44556677
0234544556677

Analyse:

Ziffer 0 am Anfang, dann zwei bis vier Ziffern, 0 oder 1 Leerzeichen, 0 oder 1 BindeStrich, 0 oder 1 Leerzeichen, 3 oder 4 Ziffern, 0 oder 1 Leerzeichen, 3 oder 4 Ziffern.

Pattern

0\d{2,4}\s?[\-]?\s?\d{3,4}\s?\d{3,4}

Als String

0\\d{2,4}\\s?[\\-]?\\s?\\d{3,4}\\s?\\d{3,4}

Aufmerksamen Lesern wird aufgefallen sein, daß das obige Pattern einen Schönheitsfehler hat. Es läßt auch Nullen in der Telefonnummer selbst zu. Ändern Sie das Pattern entsprechend ab.

Auch hier gibt es die split-Methoden sowohl in der Klasse Pattern als auch in der Klasse String

String[]  split(CharSequence input)
          Splits the given input sequence around matches of this pattern.

String[]  split(CharSequence input, int limit)
          Splits the given input sequence around matches of this pattern.

String[]  split(String regex)
          Splits this string around matches of the given regular expression.

String[]  split(String regex, int limit)
          Splits this string around matches of the given regular expression.

Ein beliebtes Beispiel ist das Zerlegen eines Textes in einzelne Worte. Zwei kleine Beispiele hierzu.

private static void splitDemo01()
{
  String toSplit = "eins    zwei drei www...straub.as";
  String pattern = "[\\s\\.]+";

  String[] words = toSplit.split(pattern);
  for(int i=0; i < words.length; i++)
  {
    System.out.println(i + " " + words[i]);
  }
}

Ergebnis

0 eins
1 zwei
2 drei
3 www
4 straub
5 as

private static void splitDemo02()
{
  String toSplit = "eins    zwei! drei? - vier, fünf; www...straub.as";
  String pattern = "[\\s\\.,;!?]+";

  String[] words = toSplit.split(pattern);
  for(int i=0; i < words.length; i++)
  {
    System.out.println(i + " " + words[i]);
  }
}

Ergebnis

0 eins
1 zwei
2 drei
3 -
4 vier
5 fünf
6 www
7 straub
8 as