Dopasowanie wzorca - Pattern matching

Ten artykuł dotyczy dopasowywania wzorców w programowaniu funkcjonalnym . W przypadku innych zastosowań zobacz dopasowywanie ciągów i rozpoznawanie wzorców .
Aby zapoznać się z zastosowaniem kryteriów dopasowywania zmiennych w definiowaniu abstrakcyjnych wzorców do dopasowania, zobacz wyrażenie regularne .

W informatyce , pasujące do wzorca jest aktem sprawdzając daną sekwencję z żetonów na obecność składników jakiegoś wzoru . W przeciwieństwie do rozpoznawania wzorców dopasowanie zazwyczaj musi być dokładne: „albo będzie, albo nie będzie”. Wzorce mają zazwyczaj postać sekwencji lub struktur drzewiastych . Zastosowania dopasowywania wzorców obejmują wyprowadzanie lokalizacji (jeśli istnieją) wzorca w sekwencji symboli, aby wyprowadzić jakiś komponent dopasowanego wzorca i zastąpienie wzorca dopasowania inną sekwencją symboli (tj. search and replace ).

Wzorce sekwencji (np. ciąg tekstowy) są często opisywane za pomocą wyrażeń regularnych i dopasowywane za pomocą technik takich jak wycofywanie .

Wzorce drzew są używane w niektórych językach programowania jako ogólne narzędzie do przetwarzania danych na podstawie ich struktury, np. C# , F# , Haskell , ML , Python , Ruby , Rust , Scala , Swift oraz symboliczny język matematyki Mathematica mają specjalną składnię do wyrażania drzewa wzorców i konstrukcji języka do warunkowego wykonywania i wyszukiwania wartości na ich podstawie.

Często możliwe jest podanie alternatywnych wzorców, które są wypróbowywane jeden po drugim, co daje potężną konstrukcję programowania warunkowego . Dopasowywanie wzorców czasami obejmuje wsparcie dla strażników .

Algorytmy analizowania często opierają się na dopasowaniu wzorców do przekształcania ciągów znaków w drzewa składni .

Historia

Wczesne języki programowania z konstrukcjami dopasowywania wzorców obejmują COMIT (1957), SNOBOL (1962), Refal (1968) z dopasowywaniem wzorców opartym na drzewie, Prolog (1972), SASL (1976), NPL (1977) i KRC (1981).

Wiele edytorów tekstu obsługuje różnego rodzaju dopasowywanie wzorców: edytor QED obsługuje wyszukiwanie według wyrażeń regularnych , a niektóre wersje TECO obsługują operator OR w wyszukiwaniu.

Systemy algebry komputerowej generalnie obsługują dopasowywanie wzorców na wyrażeniach algebraicznych.

Zobacz także: Wyrażenie regularne § Historia

prymitywne wzory

Najprostszym wzorcem w dopasowywaniu wzorców jest jawna wartość lub zmienna. Rozważmy na przykład prostą definicję funkcji w składni Haskella (parametry funkcji nie są w nawiasach, ale są oddzielone spacjami, = nie jest przypisaniem, ale definicją): 

f 0 = 1

Tutaj 0 jest pojedynczym wzorcem wartości. Teraz, gdy jako argument f podano 0, wzorzec dopasowuje się i funkcja zwraca 1. Przy każdym innym argumencie dopasowanie, a tym samym funkcja, kończy się niepowodzeniem. Ponieważ składnia obsługuje alternatywne wzorce w definicjach funkcji, możemy kontynuować definicję rozszerzając ją o bardziej ogólne argumenty: 

f n = n * f (n-1)

Tutaj pierwszy njest pojedynczym wzorcem zmiennej, który dopasuje absolutnie każdy argument i zwiąże go z nazwą n, która będzie używana w pozostałej części definicji. W Haskell (w przeciwieństwie przynajmniej do Hope ) wzorce są próbowane w kolejności, więc pierwsza definicja nadal obowiązuje w bardzo specyficznym przypadku, gdy dane wejściowe są równe 0, podczas gdy dla każdego innego argumentu funkcja zwraca, n * f (n-1)gdzie n jest argumentem.

Wzorzec wieloznaczny (często zapisywany jako _) jest również prosty: podobnie jak nazwa zmiennej, pasuje do dowolnej wartości, ale nie wiąże jej z żadną nazwą. Algorytmy dopasowywania symboli wieloznacznych w prostych sytuacjach dopasowywania ciągów zostały opracowane w wielu odmianach rekurencyjnych i nierekurencyjnych.

Wzory drzew

Bardziej złożone wzorce można budować z prymitywnych wzorców z poprzedniej sekcji, zwykle w taki sam sposób, jak wartości są budowane przez łączenie innych wartości. Różnica polega więc na tym, że w przypadku części zmiennych i symboli wieloznacznych, wzorzec nie tworzy pojedynczej wartości, ale pasuje do grupy wartości, które są kombinacją konkretnych elementów i elementów, które mogą się zmieniać w ramach struktury wzorca .

Wzorzec drzewa opisuje część drzewa, zaczynając od węzła i określając niektóre gałęzie i węzły, pozostawiając niektóre nieokreślone ze zmiennym lub wzorcem wieloznacznym. Pomocne może być myślenie o abstrakcyjnym drzewie składni języka programowania i algebraicznych typach danych .

W Haskell poniższy wiersz definiuje algebraiczny typ danych, Colorktóry ma pojedynczy konstruktor danych, ColorConstructorktóry otacza liczbę całkowitą i łańcuch. 

data Color = ColorConstructor Integer String

Konstruktor jest węzłem w drzewie, a liczba całkowita i łańcuch to liście w gałęziach.

Gdy chcemy napisać funkcji , aby uczynić Colorto abstrakcyjny typ danych , pragniemy funkcji zapisu do interfejsu z typem danych, a tym samym chcemy wyodrębnić pewne dane od typu danych, na przykład, tylko ciąg, czy tylko część całkowitą Color.

Jeśli przekażemy zmienną typu Color, jak możemy uzyskać dane z tej zmiennej? Na przykład, aby funkcja pobierała część całkowitą z Color, możemy użyć prostego wzorca drzewa i napisać: 

integerPart (ColorConstructor theInteger _) = theInteger

Również: 

stringPart (ColorConstructor _ theString) = theString

Tworzenie tych funkcji można zautomatyzować dzięki składni rekordów danych Haskella .

Ten przykład Ocamla, który definiuje czerwono-czarne drzewo i funkcję do ponownego zrównoważenia go po wstawieniu elementu, pokazuje, jak dopasować się do bardziej złożonej struktury generowanej przez rekurencyjny typ danych. 

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 *)

Filtrowanie danych za pomocą wzorców

Dopasowywanie wzorców może służyć do filtrowania danych o określonej strukturze. Na przykład, w Haskell do tego rodzaju filtrowania można użyć rozumienia listy : 

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

ocenia do 

[A 1, A 2]

Dopasowywanie wzorców w Mathematica

W Mathematica jedyną istniejącą strukturą jest drzewo wypełnione symbolami. W dotychczas używanej składni Haskella można to zdefiniować jako 

data SymbolTree = Symbol String [SymbolTree]

Przykładowe drzewo mogłoby wtedy wyglądać 

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

W tradycyjnej, bardziej odpowiedniej składni, symbole są pisane []takimi, jakimi są, a poziomy drzewa są reprezentowane za pomocą , tak że na przykład a[b,c]drzewo ma a jako rodzica, a b i c jako dzieci.

Wzór w Mathematica polega na umieszczeniu „_” na pozycjach w tym drzewie. Na przykład wzór 

A[_]

dopasuje elementy takie jak A[1], A[2] lub bardziej ogólnie A[ x ], gdzie x jest dowolną jednostką. W tym przypadku Ajest to element betonowy, natomiast _oznacza kawałek drzewa, który można zmieniać. Symbol dodany do _wiąże dopasowanie z nazwą tej zmiennej, podczas gdy symbol dodany do _ogranicza dopasowania do węzłów tego symbolu. Zauważ, że nawet same puste miejsca są wewnętrznie reprezentowane jako Blank[]for _i Blank[x]for _x.

Funkcja Mathematica Casesfiltruje elementy pierwszego argumentu, które pasują do wzorca w drugim argumencie: 

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

ocenia do 

{a[1], a[2]}

Dopasowywanie wzorców dotyczy struktury wyrażeń. W poniższym przykładzie 

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

zwroty 

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

ponieważ tylko te elementy będą pasować do a[b[_],_]powyższego wzoru .

W Mathematica możliwe jest również wyodrębnianie struktur tak, jak powstają w trakcie obliczeń, niezależnie od tego, jak i gdzie się pojawiają. Funkcja Tracemoże służyć do monitorowania obliczeń i zwracania powstałych elementów, które pasują do wzorca. Na przykład możemy zdefiniować ciąg Fibonacciego jako 

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

Następnie możemy zadać pytanie: Mając fib[3], jaka jest sekwencja rekurencyjnych wywołań Fibonacciego? 

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

zwraca strukturę, która reprezentuje wystąpienia wzorca fib[_]w strukturze obliczeniowej: 

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

Programowanie deklaratywne

W symbolicznych językach programowania łatwo jest mieć wzorce jako argumenty funkcji lub jako elementy struktur danych. Konsekwencją tego jest możliwość używania wzorców do deklaratywnego tworzenia oświadczeń o fragmentach danych i elastycznego instruowania funkcji, jak mają działać.

Na przykład funkcja MathematicaCompile może służyć do tworzenia bardziej wydajnych wersji kodu. W poniższym przykładzie szczegóły nie mają szczególnego znaczenia; ważne jest to, że podwyrażenie {{com[_], Integer}}instruuje, Compileże wyrażenia postaci com[_]mogą być przyjmowane jako liczby całkowite dla celów kompilacji: 

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

Skrzynki pocztowe w Erlangu również działają w ten sposób.

Korespondencja Curry-Howard między dowodami i programów dotyczy ML -Style dopasowywania wzorców do analizy przypadków i dowodów przez wyczerpanie .

Dopasowanie wzorców i ciągi

Zdecydowanie najczęstszą formą dopasowywania wzorców są ciągi znaków. W wielu językach programowania do reprezentowania wyrażeń regularnych, które są wzorcami opisującymi znaki łańcuchowe, używana jest określona składnia łańcuchów.

Jednak możliwe jest wykonanie dopasowania niektórych wzorców ciągów w ramach tej samej struktury, która została omówiona w tym artykule.

Wzory drzew dla ciągów

W Mathematica łańcuchy są reprezentowane jako drzewa korzenia StringExpression, a wszystkie znaki w kolejności jako dzieci korzenia. Tak więc, aby dopasować „dowolną liczbę końcowych znaków”, potrzebny jest nowy symbol wieloznaczny ___, w przeciwieństwie do _, który pasowałby tylko do jednego znaku.

W Haskell i ogólnie w funkcjonalnych językach programowania, łańcuchy są reprezentowane jako funkcjonalne listy znaków. Lista funkcjonalna jest definiowana jako pusta lista lub element skonstruowany na istniejącej liście. W składni Haskella: 

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

Struktura listy z niektórymi elementami jest więc element:list. Podczas dopasowywania wzorców zapewniamy, że pewna część danych jest równa pewnemu wzorcowi. Na przykład w funkcji: 

head (element:list) = element

Twierdzimy, że pierwszy element headargumentu nosi nazwę element, a funkcja go zwraca. Wiemy, że jest to pierwszy element ze względu na sposób definiowania list, pojedynczy element skonstruowany na liście. Ten pojedynczy element musi być pierwszy. Pusta lista w ogóle nie pasowałaby do wzorca, ponieważ pusta lista nie ma nagłówka (pierwszego konstruowanego elementu).

W przykładzie nie ma dla nas zastosowania list, więc możemy go zignorować i w ten sposób napisać funkcję: 

head (element:_) = element

Równoważna transformacja Mathematica jest wyrażona jako 

head[element, ]:=element

Przykładowe wzorce ciągów

Na przykład w Mathematica 

StringExpression["a",_]

dopasuje ciąg, który ma dwa znaki i zaczyna się od "a".

Ten sam wzór w Haskell: 

['a', _]

Encje symboliczne można wprowadzić, aby reprezentować wiele różnych klas odpowiednich cech łańcucha. Na przykład, 

StringExpression[LetterCharacter, DigitCharacter]

dopasuje ciąg składający się najpierw z litery, a następnie z liczby.

W Haskell strażników można było użyć do osiągnięcia tych samych meczów: 

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

Główną zaletą manipulacji ciągami symbolicznymi jest to, że można je całkowicie zintegrować z resztą języka programowania, zamiast być oddzielną jednostką podrzędną specjalnego przeznaczenia. Całą moc języka można wykorzystać do budowania samych wzorców lub analizowania i przekształcania programów, które je zawierają.

SNOBOL

Główny artykuł: SNOBOL

SNOBOL ( ang. String Oriented and symBOlic Language ) to język programowania komputerowego opracowany w latach 1962-1967 w AT&T Bell Laboratories przez Davida J. Farbera , Ralpha E. Griswolda i Ivana P. Polonsky'ego .

SNOBOL4 wyróżnia się na tle większości języków programowania przez posiadanie wzorców jako pierwszorzędnego typu danych ( tj. typu danych, którego wartościami można manipulować na wszystkie sposoby dozwolone dla dowolnego innego typu danych w języku programowania) oraz poprzez zapewnienie operatorów do łączenia wzorców i alternatywy . Ciągi generowane podczas wykonywania mogą być traktowane jako programy i wykonywane.

SNOBOL był dość powszechnie nauczany na większych amerykańskich uniwersytetach w późnych latach 60. i wczesnych 70. XX wieku i był szeroko stosowany w latach 70. i 80. jako język manipulacji tekstem w humanistyce .

Od czasu powstania SNOBOL, nowsze języki, takie jak Awk i Perl, sprawiły, że manipulacja ciągami znaków za pomocą wyrażeń regularnych stała się modna. Jednak wzorce SNOBOL4 zawierają gramatyki BNF , które są odpowiednikami gramatyk bezkontekstowych i mają większe możliwości niż wyrażenia regularne .

Zobacz też

Bibliografia

Linki zewnętrzne