next up previous
Nächste Seite: Über dieses Dokument ...

Reguläre Ausdrücke und Endliche Automaten

Christian Seidel, Magnus Finkenzeller, Andrea Stubbe, Sabine Unterpieringer, Andreas Hauser, Gulnas Galianova

07.11.2002

Some people, when confronted with a problem, think ``I know, I'll use regular expressions.''
Now they have two problems.

- Jamie Zawinski

Reguläre Ausdrücke
(engl.: regular expressions)

Überblick

Zwei wichtige Zeichen

/ausdruck/

Schrägstriche (Slashes) schließen einen regulären Ausdruck ein z.B. /abc/

\Sonderzeichen leitet sonderzeichen ein bzw. hebt auf z.B. \b oder \\

Zeichenklassen

. (Punkt), Wildcard

stellt ein beliebiges Zeichen dar (außer \n: Newline) z.B. /./ 'a' oder 'B' oder '9' oder '&' etc.

$[$Zeichenklasse$]$

eckige Klammern fassen eine Zeichenklasse zusammen
z.B. /[nN]/ 'n' oder 'N'

- (Minus), Bereichsoperator
``ein Zeichen zwischen ...und ...''
z.B. /[a-z]/ ein Kleinbuchstabe ('a' oder 'b' oder 'c' etc.)

^ (Zirkumflex, Caret direkt hinter [ ), Negation
``jedes Zeichen außer ...''
z.B. $\verb\vert/[^a]/\vert$ jedes Zeichen außer 'a' (also 'b' oder '7' oder '&' etc.)

Vordefinierte Zeichenklassen

\d: eine Ziffer [0-9] (z.b. 5)
\w: ein Wortzeichen [a-zA-Z0-9_] (a)
\s: ein Leerraum [ \t\n\f\r]
(Leerzeichen, Tabulator, Newline,
Zeilen-/Seitenvorschub, Wagenrücklauf)

Komplemente dazu: jeweils in Großbuchstaben, \D, \W, \S

Gruppierende Muster

Folge:
z.B. abc, d.h. a gefolgt von b gefolgt von c

Auswahl:
[abc] = Zeichenklasse (s.o.), Alternative Einzelzeichen, a oder b oder c

sabine$\vert$andrea = Alternative Zeichenketten, sabine oder andrea

Multiplikatoren:

az? =
ein oder kein Zeichen, 'a' oder 'az'
az* =
'kleene star', Asterisk;
kein oder beliebig viele Zeichen, 'a', 'az', 'azz', 'azzz';
bzw. /.*/ , 'a', 'ab', 'sabine', 'aaaa', ...
az+ =
'kleene plus', ein oder mehr zeichen matched 'az', 'azz', 'azzz', ...
x{n,m} =
allgemeiner Multiplikator n bis m Vorkommnisse
z.B. x{2,4} = 'xx', 'xxx' oder 'xxxx';
Sonderfälle: {5}: genau 5; {5, }: mindestens 5;

Klammern als Zwischenspeicher/Register
(nicht in allen Sprachen):

() =
Gruppierung, Speicher
z.B. apfel.birne = apfel$<$beliebiges zeichen$>$birne
apfel(.)birne$\backslash$1 = apfel$<$zeichen$>$birne$<$gleiches zeichen$>$
wobei $\backslash$1 = erste klammer
(entsprechend $\backslash$2: zweite klammer etc.),
z.B. $\backslash$a(.)b(.*)c$\backslash$2d$\backslash$1 = z.B. aXbYYZZcYYZZdX
(?: ) =
bloß als Klammer verwenden, nicht als Speicherplatz zählen

anchors, anker:

^ =
Zirkumflex, Caret; Beginn einer Zeile (am Beginn einer Zeichenkette)
z.B. ^hallo findet nur 'hallo' am Zeilenanfang

$\$$ =
Ende einer Zeile (am Ende einer Zeichenkette)
z.B. bye$\$$ findet nur 'bye' am Zeilenende

$\backslash$b =
Wortgrenze
z.B. fred$\backslash$b = 'fred' oder 'alfred' aber nicht 'frederick'
bzw. $\backslash$bund = 'und' oder 'unding' aber nicht 'rund', 'gesund', ...
bzw. $\backslash$bhand$\backslash$b = 'hand' aber nicht 'anhand' oder 'handlung'
= Anfang/Ende einer Zeichenkette, aber auch $\backslash$w$\backslash$W oder $\backslash$W$\backslash$w

$\backslash$B =
keine Wortgrenze,
$\backslash$Ban$\backslash$B =
'hand' oder 'sandig', aber nicht 'an' oder 'andrea'

Präzendenz von hoch nach niedrig:
$Klammern \gg Multiplikatoren \gg Folgen und Anker \gg Auswahl$

z.B. a$\vert$bc$\vert$d 'a' oder 'bc' oder 'd'
(Folge steht über Auswahl)

z.B. $\verb\vert^\vert$x$\vert$y 'x' am Zeilenanfang oder 'y' an beliebiger Stelle

z.B. $\verb\vert^\vert$(x$\vert$y) 'x' oder 'y' am Zeilenanfang

Deterministische endliche Automaten
(engl.: deterministic finite state automata)

Erklärungen:

1. Automaten sind Systeme, die abhängig von der Eingabe bestimmte Aktionen ausführen.

2. Automaten sind einfache Modelle für Computer, in dessen Speicher nur ``der aktuelle Zustand'' steht.

Wozu werden Automaten verwendet?

Verwendungen für Automaten finden sich unter anderem:

Definition:

Ein Automat besteht zwingend aus einem 5-Tuppel von:

  1. einer endlichen Zahl an Zuständen,
  2. einer endlichen Menge an Äusserungen, die der Automat versteht (Eingabesymbole z.B.: Alphabet),
  3. einem Anfangszustand,
  4. einer endlichen Zahl von Endzuständen,
  5. Übergängen von einem Zustand in den nächsten Zustand.

Beispiel:

Steuerung einer Schiebetür: ( das + stellt hier den Übergang von einem Zustand in den nächsten dar)

q0 (Anfangszustand): Die Tür ist zu, und niemand steht davor.
+
q1: Die Tür ist zu, und jemand steht davor.
+
q2: Die Tür ist auf, und jemand steht davor.
+
q3: Die Tür ist auf, und niemand steht davor.
+
q4 ( Endzustand): Die Tür ist zu, und niemand steht davor.

Den Automat ``interessiert'' es nicht, was in Zustand vorher war. Er sucht immer nur den nächsten Zustand.

Nichtdeterministische endliche Automaten
(engl.: nondeterministic finite state automata)

Erklärung

Nichtdeterministische Endliche Automaten sind genau wie Deterministische nur mit dem Unterschied, dass sie Verzweigungen erlauben an denen zwei oder mehr nächste Zustände möglich sind.

Deterministisch

\includegraphics[scale=0.8]{FSA.eps}

Nichtdeterministisch

\includegraphics[scale=0.8]{DFA.eps}

Was passiert an einer mehrdeutigen Kreuzung?

Strategien

DSA in Perl 

sub match
{
  my @word = @{$_[0]};
  my $state = $_[1];
  foreach my $c (@word)
  {
    if($state->{$c} eq 'end')
    { return "success"; }
    elsif(exists $state->{$c})
    { $state = $state->{$c}; }
    else
    { return "failed"; }
  }
}

NSA in Perl 

sub match
{
  my $index;
  my @word = @{$_[0]};
  my $state = $_[1];
  foreach my $c (@word)
  {
    $index++;
    if($state->{$c} eq 'end')
    { return "success"; }
    elsif(exists $state->{$c})
    {
      foreach $path (@{$state->{$c}})
      {
        my @rest = @word[$index .. @word];
        if(match(\@rest, $path) eq "success")
        {return "success";}
      }
    }
    else { return "failed"; }
  }
}

Literatur

Daniel Jurafsky, James H. Martin:
Speech and Language Processing
(Draft of September 28, 1999)

Jeffrey E.F. Friedl:
Mastering Regular Expressions
(Second Edition, 2002)

next up previous
Nächste Seite: Über dieses Dokument ...
Andy 2002-11-07