STP021: Reguläre Ausdrücke

1:36:46
 
Teilen
 

Manage episode 332411773 series 2920733
Von Stefan Majewsky and Xyrillian Noises entdeckt von Player FM und unserer Community - Das Urheberrecht hat der Herausgeber, nicht Player FM, und die Audiodaten werden direkt von ihren Servern gestreamt. Tippe auf Abonnieren um Updates in Player FM zu verfolgen oder füge die URL in andere Podcast Apps ein.

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

32 Episoden