STP021: Reguläre Ausdrücke

Schlüsseltechnologie

ttimeless hat sich ein Thema gewünscht und mit Beginn von Xyrills Recherchen angefangen, es zu bereuen. Es stellt sich heraus, dass das Thema zwar abstrakt, aber dennoch spannend ist. Außerdem gibt es im zweiten Teil der Sendung noch praktische Dinge zu lernen.

Shownotes

• Motivation: reguläre Ausdrücke verstehen
  • etwas Theorie ist notwendig, um die Eigenschaften und Grenzen von regulären Ausdrücken zu verstehen
  • quasi eine Erstsemestervorlesung -> Anekdote Xyrill: Büchlein "Einblick ins Studium"

Siehe Wikipedia:

Grammatik bezeichnet in der Linguistik jede Form einer systematischen Sprachbeschreibung. Dabei steht der Begriff der Grammatik einmal für das Regelwerk selbst, auf der anderen Seite aber auch für die Theorie über eine bestimmte Sprache oder Sprachfamilie.

• im Kontext der Informatik: formale Grammatiken für formale Sprachen

  • formale Sprache: Menge von Symbolketten ("Wörter"), die aus Symbolen ("Alphabet") zusammengesetzt werden
  • formale Grammatik: endlich große Beschreibung einer (im Allgemeinen unendlich großen) formalen Sprache
  • Beispiele: Programmiersprachen, Tastenkombos in Videospielen, Münzeinwurf in Verkaufsautomat
  • Abwägung: komplexere Grammatiken sind flexibler, aber auch aufwändiger (z.B. Tastatureingaben vs. Sprachsteuerung)

• Chomsky-Hierarchie: Klassifikation von formalen Grammatiken in aufsteigender Striktheit und absteigender Flexibilität

  • Beschreibung der entsprechenden formalen Grammatiken: hier nicht, zu technisch
  • zu jeder Ebene der Chomsky-Hierarchie gehört ein Maschinenmodell, dass entsprechende Grammatiken akzeptieren kann
  • Typ 3: reguläre Grammatiken mittels endlichem Zustandsautomat (Beispiel: Münzeinwurf in Verkaufsautomat)
  • Typ 2: kontextfreie Grammatiken mittels Kellerautomat (Beispiel: balancierte Klammerpaare)
  • Typ 1 und 0 mittels Turingmaschinen (erst mit beschränktem, dann mit unbeschränktem Speicher)

• Beispiel für grafische Repräsentation von Grammatiken: siehe SQLite-Dokumentation

• reguläre Grammatiken im Alltag: reguläre Ausdrücke; formale Definition mit vier Grundbausteinen

Grundbaustein	Beispielausdruck	Findet z.B.
Zeichen(folge)	Ausdruck	Ausdruck
Alternative	Ausdruck|Ausdrücke	Ausdruck und Ausdrücke
Gruppierung	Ausdr(uck|ücke)	Ausdruck und Ausdrücke
Sternquantor	to*ll	tll, toll, tooll, toooll, etc.

• in der Praxis weitere Bausteine, um häufige Anwendungen zu vereinfachen

Zusatzbaustein	Definition	Beispielausdruck	Findet z.B.
Zeichenklasse	[ABC...] = A|B|C|...	positive Ganzzahl: 0|[1-9][0-9]*	0, 42, 900, aber nicht 0815
feste Zeichenklasse	\s für Whitespace, \d = [0-9] für Ziffern, etc.
beliebiges Zeichen	.	Klammerausdruck: (.*)	(2 + 4), (siehe oben), aber auch (siehe oben (oder nicht)
Fragezeichenquantor	A? = (|A)	Ganzzahl mit Vorzeichen: [+-]?(0|[1-9][0-9]*)	+0, -42, 23
Fixquantor	z.B. A{3} = AAA, A{2,4} = AAA?A?	Postleitzahl: [0-9]{5}	01127, 50616
Plusquantor	A+ = AA*	Domainname: ([a-zA-Z0-9-]+\.)*[a-zA-Z0-9-]+	www.example.com
Anker	^ für Zeilenanfang, $ für Zeilenende, \b für Wortgrenze	Schulz\b	Schulz, aber nicht Schulze

• Problem in der Praxis: Escaping

  • z.B. Klammern sind Teil der Syntax; um eine Klammer im Eingabetext darzustellen, schreibt man "\("

• Regexen lernen

  • Online
    • LearnRegex ist ein interaktives Tutorial zum Erlernen von regulären Ausdrücken, in englischer Sprache.
    • Mit Regex Crossword kann man spielerisch besonders das Lesen regulärer Ausdrücke üben.
  • Apps
    • Regex-Kreuzworträtsel auf dem Mobiltelefon
    • Mehrere Ausdrücke mit regulären Ausdrücken erfassen bzw. ausschließen