Musterabgleich - Pattern matching

In der Informatik ist Mustervergleich der Vorgang, bei dem eine gegebene Sequenz von Token auf das Vorhandensein der Bestandteile eines Musters überprüft wird . Im Gegensatz zur Mustererkennung muss die Übereinstimmung in der Regel exakt sein: "Entweder es wird eine Übereinstimmung geben oder nicht." Die Muster haben im Allgemeinen entweder die Form von Sequenzen oder Baumstrukturen . Zu den Verwendungen des Musterabgleichs gehören das Ausgeben der Positionen (falls vorhanden) eines Musters innerhalb einer Token-Sequenz, das Ausgeben einiger Komponenten des übereinstimmenden Musters und das Ersetzen des übereinstimmenden Musters durch eine andere Token-Sequenz (dh Suchen und Ersetzen ).

Sequenzmuster (z. B. eine Textzeichenfolge) werden oft mit regulären Ausdrücken beschrieben und mit Techniken wie Backtracking abgeglichen .

Baummuster werden in einigen Programmiersprachen als allgemeines Werkzeug verwendet, um Daten basierend auf ihrer Struktur zu verarbeiten, z. B. C# , F# , Haskell , ML , Python , Ruby , Rust , Scala , Swift und die symbolische Mathematiksprache Mathematica haben eine spezielle Syntax zum Ausdrücken von Baum Muster und ein darauf basierendes Sprachkonstrukt zur bedingten Ausführung und zum Abrufen von Werten.

Oft ist es möglich, alternative Muster anzugeben, die nacheinander ausprobiert werden, was ein mächtiges Konstrukt der bedingten Programmierung ergibt . Der Musterabgleich umfasst manchmal die Unterstützung für Wächter .

Parsing- Algorithmen beruhen oft auf Mustervergleichen, um Strings in Syntaxbäume umzuwandeln .

Geschichte

Frühe Programmiersprachen mit Mustervergleichskonstrukten sind COMIT (1957), SNOBOL (1962), Refal (1968) mit baumbasiertem Mustervergleich, Prolog (1972), SASL (1976), NPL (1977) und KRC (1981).

Viele Texteditoren unterstützen verschiedene Arten von Mustervergleichen: Der QED-Editor unterstützt die Suche mit regulären Ausdrücken , und einige Versionen von TECO unterstützen den OR-Operator bei Suchen.

Computeralgebrasysteme unterstützen im Allgemeinen einen Mustervergleich bei algebraischen Ausdrücken.

Primitive Muster

Das einfachste Muster beim Mustervergleich ist ein expliziter Wert oder eine Variable. Betrachten Sie als Beispiel eine einfache Funktionsdefinition in Haskell-Syntax (Funktionsparameter sind nicht in Klammern, sondern durch Leerzeichen getrennt, = ist keine Zuweisung, sondern eine Definition):

f 0 = 1

Hier ist 0 ein Einzelwertmuster. Immer wenn f als Argument 0 angegeben wird, stimmt das Muster überein und die Funktion gibt 1 zurück. Bei jedem anderen Argument schlägt die Übereinstimmung und damit die Funktion fehl. Da die Syntax alternative Muster in Funktionsdefinitionen unterstützt, können wir die Definition fortsetzen und sie um allgemeinere Argumente erweitern:

f n = n * f (n-1)

Hier ist das erste nein einzelnes Variablenmuster, das mit absolut jedem Argument übereinstimmt und es an den Namen n bindet, um im Rest der Definition verwendet zu werden. In Haskell (im Gegensatz zu zumindest Hope ) werden Muster der Reihe nach ausprobiert, so dass die erste Definition auch in dem sehr speziellen Fall gilt, dass die Eingabe 0 ist, während die Funktion für jedes andere Argument n * f (n-1)mit n als Argument zurückgibt .

Das Platzhaltermuster (oft als _) ist ebenfalls einfach: Wie ein Variablenname entspricht es jedem Wert, bindet den Wert jedoch nicht an einen Namen. Algorithmen zum Abgleichen von Wildcards in einfachen String-Matching-Situationen wurden in einer Reihe von rekursiven und nicht-rekursiven Varianten entwickelt.

Baummuster

Komplexere Muster können aus den primitiven Mustern des vorherigen Abschnitts erstellt werden, normalerweise auf die gleiche Weise, wie Werte durch Kombinieren anderer Werte gebildet werden. Der Unterschied besteht dann darin, dass bei variablen und Wildcard-Teilen ein Muster nicht in einen einzelnen Wert eingebaut wird, sondern einer Gruppe von Werten entspricht, die die Kombination der konkreten Elemente und der Elemente sind, die innerhalb der Struktur des Musters variieren dürfen .

Ein Baummuster beschreibt einen Teil eines Baums, indem es mit einem Knoten beginnt und einige Zweige und Knoten angibt und einige mit einem Variablen- oder Platzhaltermuster unspezifiziert lässt. Es kann hilfreich sein, sich den abstrakten Syntaxbaum einer Programmiersprache und algebraische Datentypen vorzustellen .

In Haskell definiert die folgende Zeile einen algebraischen Datentyp Colormit einem einzelnen Datenkonstruktor ColorConstructor, der eine Ganzzahl und eine Zeichenfolge umschließt.

data Color = ColorConstructor Integer String

Der Konstruktor ist ein Knoten in einem Baum und die ganze Zahl und der String sind Blätter in Zweigen.

Wenn wir Funktionen schreiben möchten, um Coloreinen abstrakten Datentyp zu erstellen , möchten wir Funktionen schreiben, die mit dem Datentyp verbunden sind, und möchten daher einige Daten aus dem Datentyp extrahieren, zum Beispiel nur den String oder nur den ganzzahligen Teil von Color.

Wenn wir eine Variable vom Typ Color übergeben, wie können wir dann die Daten aus dieser Variablen herausholen? Damit eine Funktion beispielsweise den ganzzahligen Teil von erhält Color, können wir ein einfaches Baummuster verwenden und schreiben:

integerPart (ColorConstructor theInteger _) = theInteger

Sowie:

stringPart (ColorConstructor _ theString) = theString

Die Kreationen dieser Funktionen können durch Haskells Daten automatisiert werden Datensatz - Syntax.

Dieses Ocaml- Beispiel, das einen Rot-Schwarz-Baum und eine Funktion zum Neuausgleich nach dem Einfügen von Elementen definiert, zeigt, wie eine komplexere Struktur, die von einem rekursiven Datentyp generiert wird, abgeglichen wird.

type color = Red | Black
type 'a tree = Empty | Tree of color * 'a tree * 'a * 'a tree

let rebalance t = match t with
    | Tree (Black, Tree (Red, Tree (Red, a, x, b), y, c), z, d)
    | Tree (Black, Tree (Red, a, x, Tree (Red, b, y, c)), z, d)                                  
    | Tree (Black, a, x, Tree (Red, Tree (Red, b, y, c), z, d))
    | Tree (Black, a, x, Tree (Red, b, y, Tree (Red, c, z, d)))
        ->  Tree (Red, Tree (Black, a, x, b), y, Tree (Black, c, z, d))
    | _ -> t (* the 'catch-all' case if no previous pattern matches *)

Daten mit Mustern filtern

Der Mustervergleich kann verwendet werden, um Daten einer bestimmten Struktur zu filtern. In Haskell könnte beispielsweise ein Listenverständnis für diese Art der Filterung verwendet werden:

[A x|A x <- [A 1, B 1, A 2, B 2]]

bewertet zu

[A 1, A 2]

Mustervergleich in Mathematica

In Mathematica ist die einzige Struktur, die existiert, der Baum , der mit Symbolen gefüllt ist. In der bisher verwendeten Haskell- Syntax könnte dies definiert werden als

data SymbolTree = Symbol String [SymbolTree]

Ein Beispielbaum könnte dann so aussehen

Symbol "a" [Symbol "b" [], Symbol "c" []]

In der traditionellen, besser geeigneten Syntax werden die Symbole so geschrieben, wie sie sind, und die Ebenen des Baums werden mit dargestellt [], so dass zum Beispiel a[b,c]ein Baum mit a als Eltern und b und c als Kindern vorliegt.

Ein Muster in Mathematica beinhaltet das Setzen von "_" an Positionen in diesem Baum. Zum Beispiel das Muster

A[_]

wird Elemente wie A[1], A[2] oder allgemeiner A[ x ] zuordnen, wobei x eine beliebige Entität ist. In diesem Fall Aist das konkrete Element, während _das variierbare Baumstück bezeichnet wird. Ein vorangestelltes Symbol _bindet die Übereinstimmung an diesen Variablennamen, während ein angehängtes Symbol _die Übereinstimmungen auf Knoten dieses Symbols beschränkt. Beachten Sie, dass sogar Leerzeichen selbst intern als Blank[]for _und Blank[x]for dargestellt werden _x.

Die Mathematica-Funktion Casesfiltert Elemente des ersten Arguments, die dem Muster im zweiten Argument entsprechen:

Cases[{a[1], b[1], a[2], b[2]}, a[_] ]

bewertet zu

{a[1], a[2]}

Der Mustervergleich gilt für die Struktur von Ausdrücken. Im Beispiel unten,

Cases[ {a[b], a[b, c], a[b[c], d], a[b[c], d[e]], a[b[c], d, e]}, a[b[_], _] ]

kehrt zurück

{a[b[c],d], a[b[c],d[e]]}

weil nur diese Elemente dem a[b[_],_]obigen Muster entsprechen .

In Mathematica ist es auch möglich, Strukturen zu extrahieren, wie sie im Laufe der Berechnung entstehen, unabhängig davon, wie oder wo sie erscheinen. Die Funktion Tracekann verwendet werden, um eine Berechnung zu überwachen und die auftretenden Elemente zurückzugeben, die einem Muster entsprechen. Zum Beispiel können wir die Fibonacci-Folge definieren als

fib[0|1]:=1
fib[n_]:= fib[n-1] + fib[n-2]

Dann können wir die Frage stellen: Gegeben fib[3], was ist die Folge rekursiver Fibonacci-Aufrufe?

Trace[fib[3], fib[_]]

gibt eine Struktur zurück, die die Vorkommen des Musters fib[_]in der Berechnungsstruktur darstellt:

{fib[3],{fib[2],{fib[1]},{fib[0]}},{fib[1]}}

Deklarative Programmierung

In symbolischen Programmiersprachen ist es einfach, Muster als Argumente für Funktionen oder als Elemente von Datenstrukturen zu verwenden. Eine Folge davon ist die Fähigkeit, mit Hilfe von Mustern deklarativ Aussagen über Daten zu treffen und Funktionen flexibel in der Bedienung anzuweisen.

Zum Beispiel kann die Mathematica- Funktion Compileverwendet werden, um effizientere Versionen des Codes zu erstellen. Im folgenden Beispiel spielen die Details keine besondere Rolle; Wichtig ist, dass der Unterausdruck {{com[_], Integer}}anweist, Compiledass Ausdrücke der Form für die Kompilierung com[_]als ganze Zahlen angenommen werden können :

com[i_] := Binomial[2i, i]
Compile[{x, {i, _Integer}}, x^com[i], {{com[_],  Integer}}]

Auch Mailboxen in Erlang funktionieren auf diese Weise.

Die Curry-Howard-Korrespondenz zwischen Beweisen und Programmen verbindet den Mustervergleich im ML- Stil mit der Fallanalyse und dem Beweis durch Erschöpfung .

Mustervergleich und Strings

Die bei weitem gebräuchlichste Form des Mustervergleichs umfasst Zeichenfolgen. In vielen Programmiersprachen wird eine bestimmte Syntax von Strings verwendet, um reguläre Ausdrücke darzustellen, bei denen es sich um Muster handelt, die String-Zeichen beschreiben.

Es ist jedoch möglich, einige Zeichenfolgenmusterabgleiche innerhalb desselben Frameworks durchzuführen, das in diesem Artikel beschrieben wurde.

Baummuster für Saiten

In Mathematica werden Strings als Bäume der Wurzel StringExpression und alle Zeichen der Reihe nach als Kinder der Wurzel dargestellt. Um also "beliebig viele nachgestellte Zeichen" zu finden, wird ein neuer Platzhalter ___ benötigt, im Gegensatz zu _, das nur einem einzelnen Zeichen entsprechen würde.

In Haskell und funktionalen Programmiersprachen im Allgemeinen werden Strings als funktionale Zeichenlisten dargestellt . Eine funktionale Liste ist definiert als leere Liste oder als Element, das auf einer bestehenden Liste aufgebaut ist. In Haskell-Syntax:

[] -- an empty list
x:xs -- an element x constructed on a list xs

Die Struktur für eine Liste mit einigen Elementen ist also element:list. Beim Mustervergleich stellen wir fest, dass ein bestimmtes Datenelement einem bestimmten Muster entspricht. Zum Beispiel in der Funktion:

head (element:list) = element

Wir behaupten, dass das erste Element von head's Argument Element heißt, und die Funktion gibt dies zurück. Wir wissen, dass dies aufgrund der Definition von Listen das erste Element ist, ein einzelnes Element, das auf einer Liste aufgebaut ist. Dieses einzelne Element muss das erste sein. Die leere Liste würde dem Muster überhaupt nicht entsprechen, da eine leere Liste keinen Kopf hat (das erste Element, das konstruiert wird).

Im Beispiel haben wir keine Verwendung für list, können es also ignorieren und schreiben die Funktion:

head (element:_) = element

Die äquivalente Mathematica-Transformation wird ausgedrückt als

head[element, ]:=element

Beispiel-String-Muster

In Mathematica zum Beispiel

StringExpression["a",_]

findet eine Zeichenfolge, die aus zwei Zeichen besteht und mit "a" beginnt.

Das gleiche Muster in Haskell:

['a', _]

Symbolische Entitäten können eingeführt werden, um viele verschiedene Klassen relevanter Merkmale einer Zeichenfolge darzustellen. Zum Beispiel,

StringExpression[LetterCharacter, DigitCharacter]

findet eine Zeichenfolge, die zuerst aus einem Buchstaben und dann aus einer Zahl besteht.

In Haskell könnten Wachen verwendet werden, um die gleichen Matches zu erzielen:

[letter, digit] | isAlpha letter && isDigit digit

Der Hauptvorteil der symbolischen String-Manipulation besteht darin, dass sie vollständig in den Rest der Programmiersprache integriert werden kann, anstatt eine separate Untereinheit für spezielle Zwecke zu sein. Die gesamte Leistungsfähigkeit der Sprache kann genutzt werden, um die Muster selbst aufzubauen oder die Programme, die sie enthalten, zu analysieren und zu transformieren.

SNOBOL

SNOBOL ( String Oriented and symBOlic Language ) ist eine Computerprogrammiersprache, die zwischen 1962 und 1967 in den AT&T Bell Laboratories von David J. Farber , Ralph E. Griswold und Ivan P. Polonsky entwickelt wurde .

SNOBOL4 hebt mich von den meisten Programmiersprachen durch Muster als mit erstklassigem Datentyp ( dh einen Datentyp , deren Werte in den Programmiersprache zu jedem anderen Datentyp erlaubte in allen Arten manipuliert werden kann) und von den Betreibern zur Muster Bereitstellung Verkettung und abwechselnd . Während der Ausführung generierte Strings können als Programme behandelt und ausgeführt werden.

SNOBOL wurde in den späten 1960er und frühen 1970er Jahren an größeren US-Universitäten gelehrt und in den 1970er und 1980er Jahren als Sprache zur Textmanipulation in den Geisteswissenschaften verwendet .

Seit der Gründung von SNOBOL haben neuere Sprachen wie Awk und Perl die String-Manipulation mittels regulärer Ausdrücke in Mode gebracht. SNOBOL4-Muster subsumieren jedoch BNF- Grammatiken, die kontextfreien Grammatiken entsprechen und mächtiger als reguläre Ausdrücke sind .

Siehe auch

Verweise

Externe Links