Reguläre Ausdrücke

1. Einrichten

Lege im Terminal (StrgJ) einen Ordner an, lade das Logfile hinein und öffne den Ordner mit StrgK StrgO:

mkdir /workspace/regex
cd /workspace/regex
wget https://workspace.hackschule.de/regex/starter/access.log

access.log ist das Logfile der Website einer ausgedachten Schule, von einem Dienstag im Oktober. Die Adressen darin sind erfunden: 10.12.… ist das Netz der Schule, die anderen stammen aus Bereichen, die für Beispiele reserviert sind (RFC 5737).

2. Suchen im Logfile

Eine Zeile im Logfile

Jede Zeile hat denselben Aufbau, das Format heißt combined und ist das, was der Webserver nginx von selbst schreibt:

198.51.100.17 - - [27/Oct/2026:08:03:27 +0100] "GET /favicon.ico HTTP/1.1" 200 4048 "https://www.example.org/" "Mozilla/5.0 (iPhone; …)"

Vorn steht die Adresse, die gefragt hat, in eckigen Klammern die Zeit. In Anführungszeichen folgt die Anfrage selbst: die Methode GET (eine Seite holen) oder POST (ein Formular abschicken), der Pfad und die Version von HTTP. Dahinter stehen der Status, mit dem der Server geantwortet hat, und wie viele Bytes er geschickt hat. 200 heißt »hier ist die Seite«, 304 »du hast sie schon«, 404 »gibt es nicht«, und eine Zahl ab 500 heißt, dass beim Server selbst etwas schiefging. Die letzten zwei Teile sind die Seite, von der jemand kam, und das Programm, mit dem er gefragt hat.

Das einfachste Muster ist ein Wort. grep gibt jede Zeile aus, in der es vorkommt:

grep POST access.log

Drei Leute haben das Kontaktformular abgeschickt. Mit -c zählt grep die Zeilen, statt sie auszugeben. Wie viele Seiten wurden nicht gefunden? Bevor du es ausprobierst:

grep -c 404 access.log
grep 404 access.log | grep -v '" 404 '

Zeichenklassen und Wiederholungen

Für den Status 404 reicht ein festes Muster. Für »alle Fehler, die mit 4 anfangen« nicht mehr: Das sind 400, 403, 404 und so weiter. Hier beginnen die regulären Ausdrücke. Mit -E versteht grep sie (E steht für extended). [0-9] ist eine Zeichenklasse: ein einziges Zeichen, eines von 0 bis 9. {2} dahinter heißt »das Zeichen davor zweimal«:

grep -E '" 4[0-9]{2} ' access.log

Neben den Zeilen mit 404 steht darin eine mit 403: Jemand wollte /lehrerzimmer.html sehen und durfte nicht. Die einfachen Anführungszeichen um das Muster sorgen dafür, dass das Terminal das Muster so an grep weitergibt, wie es dasteht, mit den Leerzeichen und dem ".

Die Bausteine, aus denen reguläre Ausdrücke bestehen, stehen im Handbuch; hier sind sie, damit du nachschlagen kannst:

Der Punkt

Programme, die Websites nach Lücken absuchen, fragen nach Dateien, die es auf vielen Websites gibt, etwa nach der Anmeldung von WordPress oder nach phpMyAdmin. Viele davon enden auf .php. Wer im Logfile nach solchen Anfragen sucht, muss an den Punkt denken: Was er in einem regulären Ausdruck bedeutet, steht in der Tabelle oben.

Anfang und Ende der Zeile

^ ist der Anfang einer Zeile, $ ihr Ende. Beide passen auf kein Zeichen, sondern auf eine Stelle im Text; sie heißen Anker. ^# passt nur auf Zeilen, die mit # beginnen, ^$ auf leere Zeilen. Ohne Anker passt ein Muster überall in der Zeile, auch weit hinten.

Herausschneiden und zählen

Mit -o gibt grep nicht die ganze Zeile aus, sondern nur das Stück, auf das das Muster passt. Dahinter kann ein | die Ausgabe an das nächste Programm weitergeben, eine Pipe: sort sortiert die Zeilen, uniq -c fasst gleiche Zeilen, die untereinanderstehen, zu einer zusammen und schreibt davor, wie oft sie vorkamen. So zählst du, welche Pfade am häufigsten verlangt wurden:

grep -E -o '"GET [^ ]+' access.log | sort | uniq -c | sort -n

[^ ] ist eine Zeichenklasse mit ^ am Anfang, also jedes Zeichen außer dem Leerzeichen, und + heißt »einmal oder öfter«. [^ ]+ passt so auf den ganzen Pfad, bis zum Leerzeichen dahinter. Das letzte sort -n sortiert nach der Zahl vorn, das Häufigste steht unten.

Weitere Schalter von grep, -i für Groß und Klein, -n für die Nummer jeder Zeile und -r für ganze Ordner, stehen im Handbuch unter Reguläre Ausdrücke mit grep.

3. In deinem Programm

grep beantwortet Fragen, die man einmal stellt. Soll ein Programm das Logfile jede Nacht lesen und am Morgen eine Übersicht schreiben, kommen die Ausdrücke in den Code. In Ruby steht ein regulärer Ausdruck zwischen zwei Schrägstrichen, /" 404 /, und ist ein Objekt wie ein String oder eine Zahl. Lege log.rb an:

# Das Logfile des Webservers, gelesen mit regulären Ausdrücken
lines = File.readlines('access.log', chomp: true)
line = lines[3]

puts line
p line =~ /HTTP/
p line =~ /" 404 /
p lines.count { |l| l =~ /" 404 / }

File.readlines liest die Datei als Liste von Zeilen, chomp: true nimmt jeder ihr Zeilenende ab. =~ sucht den Ausdruck im String und gibt den Index zurück, an dem der erste Treffer beginnt, oder nil, wenn es keinen gibt. Weil nil in einem if als falsch zählt und jede Zahl als wahr, zählt count damit die Zeilen mit einem Treffer, wie grep -c. Starte das Programm:

ruby log.rb

HTTP beginnt am Index 65. " 404 kommt in dieser Zeile nicht vor, obwohl 4048 darin steht, und 18 Zeilen haben den Status 404, wie bei grep.

grep beantwortet Fragen, die man einmal stellt. Soll ein Programm das Logfile jede Nacht lesen und am Morgen eine Übersicht schreiben, kommen die Ausdrücke in den Code. In Python stehen die Funktionen dafür im Modul re, und der Ausdruck ist ein String. Man schreibt ihn als Raw-String mit einem r davor, r'" 404 ', damit Python die Backslashes darin nicht selbst auswertet. Lege log.py an:

# Das Logfile des Webservers, gelesen mit regulären Ausdrücken
import re

with open('access.log') as f:
    lines = f.read().splitlines()
line = lines[3]

print(line)
print(re.search(r'HTTP', line))
print(re.search(r'" 404 ', line))
print(sum(1 for l in lines if re.search(r'" 404 ', l)))

splitlines zerlegt die Datei in eine Liste von Zeilen, ohne die Zeilenenden. re.search sucht den Ausdruck im String und gibt ein Match-Objekt zurück, das sagt, wo der erste Treffer steht, oder None, wenn es keinen gibt. Weil None in einem if als falsch zählt und jedes Match-Objekt als wahr, zählt die letzte Zeile damit die Zeilen mit einem Treffer, wie grep -c. Starte das Programm:

python3 log.py

span=(65, 69) sind die Indizes, an denen der Treffer HTTP beginnt und hinter dem er endet. " 404 kommt in dieser Zeile nicht vor, obwohl 4048 darin steht, und 18 Zeilen haben den Status 404, wie bei grep.

Teile herausholen: Gruppen

Ob ein Muster passt, ist oft nur die halbe Frage. Ein Programm will wissen, was an dieser Stelle steht: welcher Pfad, welcher Status. Dafür gibt es Gruppen: Was im Ausdruck in runden Klammern steht, merkt sich das Match-Objekt einzeln.

m = line.match(/"(GET|POST) (\S+) /)
p m[0]
p m[1]
p m[2]

m = re.search(r'"(GET|POST) (\S+) ', line)
print(m.group(0))
print(m.group(1))
print(m.group(2))

def status(line)
    m = line.match(/" (…) /)
    return nil if m.nil?
    …
end

# Der Status einer Zeile als Zahl, oder nil, wenn die Zeile keinen hat
def status(line)
    m = line.match(/" (\d{3}) /)
    return nil if m.nil?
    m[1].to_i
end

def status(line):
    m = re.search(r'" (…) ', line)
    if m is None:
        return None
    return …

# Der Status einer Zeile als Zahl, oder None, wenn die Zeile keinen hat
def status(line):
    m = re.search(r'" (\d{3}) ', line)
    if m is None:
        return None
    return int(m.group(1))

Mit status wird die Übersicht eine Zeile. tally zählt, wie oft jeder Wert in einer Liste vorkommt; hänge sie ans Ende von log.rb an:

p lines.map { |l| status(l) }.tally

Mit status wird die Übersicht eine Zeile. Ein Counter aus dem Modul collections zählt, wie oft jeder Wert vorkommt; schreib unter import re die Zeile from collections import Counter und hänge ans Ende von log.py an:

print(Counter(status(l) for l in lines))

4. Eingaben prüfen

Ein Formular fragt nach einer Postleitzahl, einem Geburtsdatum, einem Benutzernamen. Bevor ein Programm damit arbeitet, prüft es, ob die Eingabe so aussieht, wie sie aussehen soll. Das ist die zweite große Arbeit regulärer Ausdrücke, und ein Fehler darin hat einen anderen Fehler als beim Suchen: Eine Suche, die eine Zeile zu viel findet, sieht man; eine Prüfung, die eine falsche Eingabe durchlässt, merkt niemand, bis etwas kaputtgeht.

Postleitzahlen

Eine deutsche Postleitzahl hat fünf Ziffern, als Ausdruck \d{5}. Bevor du ihn in ein Programm schreibst:

# Eingaben prüfen, bevor ein Programm mit ihnen arbeitet
def postcode?(text)
    text.match?(/\A\d{5}\z/)
end

['10115', '1011', 'D-10115 Berlin', '101150'].each do |text|
    puts "#{text.inspect} #{postcode?(text)}"
end

# Eingaben prüfen, bevor ein Programm mit ihnen arbeitet
import re


def is_postcode(text):
    return re.fullmatch(r'\d{5}', text) is not None


for text in ['10115', '1011', 'D-10115 Berlin', '101150']:
    print(repr(text), is_postcode(text))

plz = /\A\d{5}\z/
puts '10115'.match?(plz)            # true
puts '1011'.match?(plz)             # false

text = 'Am 3.10. und am 24.12. ist frei.'
p text =~ /\d+\./                  # 3
p text.scan(/\d+\.\d+\./)           # ["3.10.", "24.12."]
puts text.gsub(/\d+/, '#')          # Am #.#. und am #.#. ist frei.

if (m = text.match(/(\d+)\.(\d+)\./))
  puts "Tag #{m[1]}, Monat #{m[2]}" # Tag 3, Monat 10
end

import re

print(bool(re.fullmatch(r"\d{5}", "10115")))   # True: der ganze String passt
print(bool(re.fullmatch(r"\d{5}", "1011")))    # False

text = "Am 3.10. und am 24.12. ist frei."
print(re.findall(r"\d+\.\d+\.", text))       # ['3.10.', '24.12.']
print(re.sub(r"\d+", "#", text))              # Am #.#. und am #.#. ist frei.

m = re.search(r"(\d+)\.(\d+)\.", text)
if m:
    print(f"Tag {m.group(1)}, Monat {m.group(2)}")   # Tag 3, Monat 10

Ein Datum

Ein Datum, wie man es in Deutschland schreibt: zwei Ziffern für den Tag, ein Punkt, zwei für den Monat, ein Punkt, vier für das Jahr, 24.12.2026. \d{2}\.\d{2}\.\d{4} beschreibt die Form, nimmt aber auch 45.17.2026 an. Ein besserer Ausdruck lässt nur Tage von 01 bis 31 und Monate von 01 bis 12 durch. Dafür braucht es kein Rechnen, sondern Alternativen: Ein Tag ist eine 0 mit einer Ziffer von 1 bis 9 dahinter, oder eine 1 oder 2 mit irgendeiner Ziffer, oder eine 3 mit einer 0 oder 1.

def date?(text)
    text.match?(/\A(0[1-9]|…|…)\.(…|…)\.\d{4}\z/)
end

# Ein Datum wie 24.12.2026: Tag 01 bis 31, Monat 01 bis 12, ein Jahr mit vier Ziffern
def date?(text)
    text.match?(/\A(0[1-9]|[12][0-9]|3[01])\.(0[1-9]|1[0-2])\.\d{4}\z/)
end

def is_date(text):
    return re.fullmatch(r'(0[1-9]|…|…)\.(…|…)\.\d{4}', text) is not None

# Ein Datum wie 24.12.2026: Tag 01 bis 31, Monat 01 bis 12, ein Jahr mit vier Ziffern
def is_date(text):
    return re.fullmatch(r'(0[1-9]|[12][0-9]|3[01])\.(0[1-9]|1[0-2])\.\d{4}', text) is not None

Ein Benutzername

Die nächste Regel schreibst du ohne Kasten; die Prüfung sagt dir, bei welchem Namen dein Ausdruck sich irrt:

def username?(text)
    text.match?(/\A[a-z]…\z/)
end

def is_username(text):
    return re.fullmatch(r'[a-z]…', text) is not None

E-Mail-Adressen

Bei E-Mail-Adressen sieht es aus, als ginge es genauso: ein Name, ein @ und dahinter ein Name mit Punkten. Bevor du weiterliest:

Wenn ein Ausdruck hängt

Am 2. Juli 2019 waren viele Websites weltweit für 27 Minuten nicht erreichbar. Die Firma Cloudflare, über deren Rechner sie laufen, hatte eine neue Regel gegen Angriffe eingespielt, und darin stand ein regulärer Ausdruck, der bei manchen Anfragen so lange probierte, dass die Prozessoren nichts anderes mehr taten (der Bericht von Cloudflare). Die meisten Programmiersprachen prüfen einen Ausdruck nämlich, indem sie einen Weg durch ihn versuchen und, wenn er nicht passt, zurückgehen und den nächsten Weg nehmen, Backtracking genannt. (a+)+b lässt sich auf aaaa auf sehr viele Weisen aufteilen: alle vier a in einem a+, oder 3 und 1, oder 2 und 2, oder 1, 1, 1 und 1 … Fehlt am Ende das b, probiert ein solches Programm sie alle, und mit jedem a mehr werden es doppelt so viele.

Wie man Ausdrücke prüft, ohne je zurückzugehen, hat Ken Thompson schon 1968 aufgeschrieben, und das steckt im letzten Teil dieser Seite. Russ Cox erklärt in Regular Expression Matching Can Be Simple And Fast, warum viele Sprachen es trotzdem anders machen: Rückverweise und andere Erweiterungen gehen nur mit Backtracking.

5. Vom Ausdruck zum Automaten

In Endliche Automaten hast du Automaten gebaut, die ein Wort Zeichen für Zeichen lesen und am Ende Ja oder Nein sagen. Ein regulärer Ausdruck sagt auch Ja oder Nein zu einem Wort. Das ist kein Zufall: Aus jedem regulären Ausdruck lässt sich ein endlicher Automat bauen, der genau die Wörter annimmt, auf die der Ausdruck passt. Mit Klassen wie [0-9] und {5} wird es nur länger; die Bausteine, die man wirklich braucht, sind vier: ein Zeichen, zwei Stücke hintereinander, | und *.

Aus Bausteinen wird ein Automat

Für jeden Baustein gibt es ein kleines Stück Automat, und die Stücke werden ineinandergesteckt, wie die Klammern im Ausdruck. Damit das einfach bleibt, dürfen die Stücke ε-Übergänge haben: Pfeile mit einem ε, die der Automat nehmen darf, ohne ein Zeichen zu lesen. Ein Automat mit ε-Übergängen ist ein NEA, der zusätzlich raten darf, ob er so einen Pfeil nimmt.

Ein regulärer Ausdruck beschreibt eine Sprache, und die Thompson-Konstruktion baut daraus einen NEA, Stück für Stück aus wenigen Bausteinen. Jeder Baustein hat einen Start und einen akzeptierenden Zustand, und die Bausteine werden mit ε-Übergängen verbunden. Die Bilder in diesem Abschnitt zeichnet Automatron, und genau so sehen die Automaten dort aus. Es baut nach dieser Konstruktion, lässt aber ε-Übergänge weg, die nur ein Stück an das nächste hängen.

Mehr dazu

• Wikipedia: Ken Thompson
• swtch.com
• Computer History Museum: ken thompson
• Wikipedia: Grep
• cl.cam.ac.uk
• go.dev

Ken Thompson (geboren 1943). Du suchst im Terminal mit grep? Das hat er 1973 geschrieben; der Name kommt aus seinem Texteditor, wo der Befehl g/re/p hieß: global, regular expression, print. Wie man aus einem regulären Ausdruck einen Automaten baut, hatte er schon 1968 beschrieben: die Thompson-Konstruktion.

Das Terminal selbst läuft unter Linux, und Linux funktioniert wie Unix, das er ab 1969 mit Dennis Ritchie schrieb. Unten rechts in VS Code steht UTF-8: Die Kodierung hat er 1992 mit Rob Pike auf ein Tischset in einem Diner gezeichnet. Und die Sprache Go hat er mit erfunden.

Foto: A. C. Diller, 2019, CC BY-SA 4.0, zugeschnitten (Wikimedia Commons)

Regular Expression Search Algorithm, Ken Thompson, Communications of the ACM, 1968. Auf vier Seiten baut Thompson aus einem regulären Ausdruck einen NEA und verfolgt beim Suchen alle Zustände zugleich, in denen er sein könnte; sein Programm übersetzt den Ausdruck dafür gleich in Maschinencode für den Rechner IBM 7094: frei bei der ACM.

Symbol, Verkettung, Alternative und Kleenesche Hülle reichen für jeden regulären Ausdruck; positive Hülle und Option sind Abkürzungen: a+ ist aa*, a? ist »a oder nichts«.

Mehr dazu

• Wikipedia: Stephen Cole Kleene
• MacTutor: Kleene
• Wikipedia: Kleene star
• Wikipedia: Regular expression
• Wikipedia: Grep
• Wikipedia: Regular language

Stephen Cole Kleene (1909–1994), Mathematiker in Madison, Wisconsin. Jedes * in einem regulären Ausdruck, bei grep oder in der Suche von VS Code, ist sein Stern.

1951 wollte er wissen, welche Muster ein Netz aus Nervenzellen erkennen kann, und erfand dafür die Bausteine, die heute reguläre Ausdrücke heißen, zwanzig Jahre bevor es grep gab. Er bewies auch, dass sie und endliche Automaten genau dasselbe können.

Foto: Harold N. Hone, um 1963, gemeinfrei (Wikimedia Commons)

Representation of Events in Nerve Nets and Finite Automata, Stephen C. Kleene, Forschungsbericht RM-704 der RAND Corporation, 1951; 1956 gedruckt im Buch Automata Studies, herausgegeben von Claude Shannon und John McCarthy. Hier stehen die regulären Ausdrücke zum ersten Mal, noch als regular events, mit dem Stern und dem Beweis, dass sie und endliche Automaten dieselben Sprachen beschreiben: frei bei RAND.

Die Kleenesche Hülle einer Sprache L, geschrieben L^*, sind alle Wörter, die sich aus beliebig vielen Wörtern von L zusammensetzen lassen, auch aus keinem: Das leere Wort ε gehört immer dazu. Die positive Hülle L⁺ lässt das leere Zusammensetzen weg: mindestens ein Wort von L; L⁺ ist dasselbe wie L L^*. Größere Ausdrücke werden aus diesen Bausteinen zusammengesetzt, von innen nach außen; für (a|b)*aa steckt der Baustein für a|b im Baustein für *, und danach kommen zwei a:

Im Handbuch nachschlagen

Ein Wort lesen

Fertig zusammengesetzt hat so ein Automat viele Zustände und ε-Übergänge. Kleiner geht es oft von Hand. Der Ausdruck a(a|b)*a passt auf die Wörter aus a und b, die mit einem a anfangen und mit einem a aufhören und mindestens zwei Zeichen haben. Als NEA: Das erste a führt nach q₁, (a|b)* ist die Schleife in q₁, und bei jedem a rät der Automat, ob es das letzte ist. Schalte durch und ändere das Wort:

Vom Automaten zum Ausdruck

Es geht auch umgekehrt: Zu jedem endlichen Automaten gibt es einen regulären Ausdruck, der genau die Wörter beschreibt, die er annimmt. Beides zusammen hat Stephen Kleene 1951 bewiesen, dessen Kasten oben steht; es heißt heute Satz von Kleene. Reguläre Ausdrücke und endliche Automaten sind zwei Schreibweisen für dieselben Sprachen, die regulären Sprachen: Der Ausdruck ist leichter zu schreiben, der Automat leichter auszuführen.

Dieser Automat liest Binärzahlen:

Was kein Ausdruck kann

Ein Editor zeigt dir, ob eine Klammer in deinem Programm fehlt. Könnte er das mit einem regulären Ausdruck prüfen?

6. Zusammenfassung

• Ein regulärer Ausdruck ist ein Muster für Text: Zeichen stehen für sich, [0-9] ist eine Zeichenklasse, *, +, ? und {n} wiederholen, | heißt »oder«, Klammern fassen zusammen und bilden Gruppen, \ nimmt einem Sonderzeichen seine Bedeutung.
• Suchen heißt: Der Ausdruck passt irgendwo, wie bei grep oder =~. Prüfen heißt: Er passt auf den ganzen Text, mit \A und \z in Ruby oder re.fullmatch in Python.
• Ein Ausdruck prüft die Form, nicht die Bedeutung: 31.02.2026 sieht aus wie ein Datum. Wo die Regeln lang werden, wie bei E-Mail-Adressen, prüft man grob und lässt den Rest ein Programm tun.
• Backtracking kann bei manchen Ausdrücken unvorstellbar lange dauern. Ein Automat liest jedes Zeichen nur einmal.
• Satz von Kleene: Reguläre Ausdrücke und endliche Automaten beschreiben dieselben Sprachen, die regulären Sprachen.

7. Wie geht es weiter?

• Kellerautomaten. Mit einem Stack als Gedächtnis prüft ein Automat Klammern und Wörter wie aaabbb: Kellerautomaten.
• Grammatiken. Regeln, die sich selbst benutzen, beschreiben Programmiersprachen; Grammatiken zeigt, wie man sie liest und aus ihnen ein Programm macht, das Ausdrücke prüft.
• Automatron. Zu jedem Ausdruck aus |, *, +, ? und Klammern zeichnet Automatron den NEA, den DEA und den kleinsten DEA, mit allen Schritten dazwischen.
• Ausprobieren im Editor. In VS Code sucht StrgF mit regulären Ausdrücken, wenn du AltR drückst; alle Treffer werden markiert, und beim Ersetzen steht $1 für die erste Gruppe. Mehr dazu und die Links zum Nachschlagen stehen im Handbuch unter Reguläre Ausdrücke.