Left Up Begriffe in Programmiersprachen

Reguläre Ausdrücke

Theorischer Hintergrund

Definition

Reguläre Grammatiken sind die Typ 3 Grammatiken der Chomsky-Hierarchie.
Eine reguläre Grammatik ist links- oder rechtslinaer ....

Reguläre Ausdücke

Reguläre Ausdrücke sind eine andere Form der Beschreibung:

Sei A eine Menge von Zeichen (Alphabeth) und a,b reguläre Ausdrücke. Weitere Ausdrücke lassen sich wie folgt rekursiv definieren:

∅:
Der Ausdruck, der der leeren Menge entspricht
λ :
die leere Zeichenkette
z :
Ein Zeichen aus dem Alphabeth bezeichnet sich selber
ab:
Die Konkatination/Hintereinanderschreibung
a*:
eine Folge von a
a|b:
die Alternative

Zusammenhang mit Automaten

Reguläre Ausdrücke können mit endlich erkennenden Automaten erkannt werden.

Grenzen

Pumpinglemma

Praktische Verwendung

Die regulären Ausdrücke aus der Theorie werden durch weitere Konstrukte ergänzt:
^:
Zeilenanfang
$:
Zeilenende
[z1-zn] :
ein Zeichen aus der Menge z1,z2,...zn
[^z1-zn] :
das Komplement der Menge
. :
ein beliebiges Zeichen
a? :
a | λ
a+ :
aa*

Es gibt auch Erweiterungen, die Wörter erkennen können, die weit über die Grenzen hinausgehen, z.B. Rückwärtsreferenzen:

([A-Za-z]+)="[^"]*" [^<>] \1="[^"]*"
sucht ein doppeltes Attribut in einem XML-Text, der gegen die Regel verstösst, das keine Attribute doppelt vorkommen darf.

([A-Za-z]+)\1\1
: Ein Wort, dass dreifach hintereinander vorkommt: Meines erachtens kann man dieses nicht mit kontextfreien Grammatiken (der nächst mächtigeren Sprachklasse erkennen.

(Trotzdem ist es interessant, dass gewisse Konstrukte ihre Grenzen haben. Da kann man im Informatikstudium etwas lernen. Diese Erweiterungen sind dann eine Herausforderungen an die Theorie ...)

Anwendung

Mustersuche

Scanner bei Compileren, automatisch erzeugt durch Tools

Java

Man beachte: \ ist ein escape-Character auch in Java, deshalb muss er wiederum escapped werden, z.B \S muss \\S geschrieben werden [Vogel].

C#/.NET

Bibliotheken

PCRE - Perl Compatible Regular Expressions

Verweise

Informatik- und Netzwerkverein Ravensburg e.V Rudolf Weber