pasujące do wzorca - Pattern matching


Z Wikipedii, wolnej encyklopedii

W informatyce , pasujące do wzorca jest aktem sprawdzając daną sekwencję żetonów na obecność składników jakiegoś wzoru . W przeciwieństwie do rozpoznawania wzorców , mecz zwykle musi być dokładne „albo będzie albo nie będzie to mecz” Wzory na ogół mają postać zarówno sekwencji lub struktury drzewa . Zastosowania dopasowywania wzorców obejmują wyprowadzania lokalizacje (jeśli istnieje) wzorca sekwencji wewnątrz symboliczną, do wyjścia jakiś składnik dopasowane wzorem i zastąpić wzór pasujący do innej sekwencji tokenu (tj wyszukiwania i zamiany ).

Wzorce sekwencji (np łańcuch tekstowy) są często opisywane za pomocą wyrażeń regularnych i dopasowywane za pomocą technik takich jak backtracking .

Wzory drzewa są wykorzystywane w niektórych językach programowania jako ogólne narzędzie do przetwarzania danych na podstawie jego struktury, np Haskell , ML , Scala i symboliczny język matematyki Mathematica mają specjalną składnię do wyrażania wzory drzewa i język skonstruować dla realizacji warunkowego i pobierania wartości w oparciu o niego. Ze względów prostoty i efektywności, te wzory drzewa brakuje niektórych funkcji, które są dostępne w wyrażeniach regularnych.

Często jest to możliwe, aby dać alternatywne wzory, które są sprawdzane jeden po drugim, co daje potężną warunkowego programowania konstruktu . Pasujące do wzorca zawiera czasami wsparcie dla strażników .

Przepisywanie termin i wykres przepisywanie języki polegać na wzór pasujący do zasadniczy sposób program ocenia się wynik.

Historia

Pierwsze programy komputerowe do wykorzystania wzorców dopasowania były edytorów. W Bell Labs , Ken Thompson rozszerzył poszukiwania i zastępujące funkcje edytora QED przyjąć wyrażeń regularnych . Wczesne języki programowania z Pattern Matching konstruktów obejmują snobol od 1962 roku, radziecki język Refal z 1968 roku z drzewa opartego dopasowywania wzorców, SASL Od 1976 NPL od 1977 roku, a KRC od 1981. Kolejny język programowania oparty na drzewie wzorzec dopasowania funkcji był Fred McBride'a rozszerzenie LISP , w 1970 roku.

prymitywne wzory

Najprostszy wzór w dopasowywaniu wzorców wyraźna wartość lub zmienna. Na przykład, należy rozważyć prosty definicji funkcji składni Haskell (parametry funkcyjne nie znajdują się w nawiasach, lecz są oddzielone od przestrzeni, = nie jest zadanie, ale rozdzielczości):

 f 0 = 1

Tu 0 jest pojedynczy wzorzec wartość. Teraz, gdy f jest podany jako argument 0 pasuje do wzorca, a funkcja zwraca 1. Z każdego innego argumentu, a tym samym dopasowanie funkcji fail. Jak składnia wspiera alternatywne wzory w definicji funkcji, możemy kontynuować definicję rozszerzając go do podjęcia bardziej ogólnych argumentów:

 f n = n * f (n-1)

W tym przypadku pierwsza njest pojedyncza zmienna wzór, który będzie pasował do absolutnie żadnego argumentu, i wiążą się z n nazwy być stosowane w innych definicji. W Haskell (w przeciwieństwie do co najmniej Nadzieja ), wzory są sprawdzone w porządku więc pierwsza definicja nadal ma zastosowanie w bardzo szczególnym przypadku wejścia będącego 0, natomiast w przypadku jakiegokolwiek innego argumentu funkcja zwraca n * f (n-1)z n jest argument.

Wildcard wzór (często zapisywane jako _) jest prosta: jak nazwa zmiennej, to pasuje do żadnej wartości, ale nie wiąże się wartość do każdej nazwy. Algorytmy dopasowania symboli wieloznacznych w prostych sytuacjach smyczkowych dopasowywania zostały opracowane w szeregu cyklicznych odmian i nierekursywnych.

wzory drzewa

Bardziej skomplikowane wzory mogą być zbudowane z prymitywnych poprzedniego odcinka, zwykle w ten sam sposób, jak wartości są budowane poprzez połączenie inne wartości. Różnica jest zatem, że przy zmiennej i wieloznacznych części, wzór nie tworzy w pojedynczą wartość, lecz pasuje do grupy wartości, które stanowią połączenie elementów betonowych i elementów, które mogą się zmieniać w strukturze wzoru ,

Drzewo wzór opisuje część drzewie zaczynając od węzła i określając niektóre oddziały i węzły i pozostawiając jakiś nieokreślony ze zmiennym lub wieloznaczne wzorca. To może pomóc myśleć o drzewo składniowe języka programowania i algebraicznych typów danych .

W Haskell następujący wiersz definiuje algebraicznych typ danych Color, który ma jeden konstruktor danych ColorConstructor, która otacza liczbą całkowitą i ciąg.

 data Color = ColorConstructor Integer String

Konstruktor jest węzeł w drzewie i całkowitą i ciąg są liście w oddziałach.

Gdy chcemy napisać funkcje , aby Colorsię abstrakcyjny typ danych , chcemy napisać funkcje połączone bezpośrednio z typem danych, a tym samym chcemy wyodrębnić niektórych danych z typem danych, na przykład, tylko ciąg lub tylko część całkowitą Color,

Jeśli mamy przekazać zmienną, która jest typu barwnego, w jaki sposób możemy uzyskać dane z tej zmiennej? Na przykład dla funkcji, aby uzyskać część całkowitą Color, możemy użyć prostego drzewa wzór i zapisu:

 integerPart (ColorConstructor theInteger _) = theInteger

Także:

 stringPart (ColorConstructor _ theString) = theString

Kreacje z tych funkcji można zautomatyzować przez składni rekordu danych w Haskell.

Filtrowanie danych z wzorami

Dopasowanie wzorca może być wykorzystywane do filtrowania danych o określonej strukturze. Na przykład w Haskell listowego mogłyby zostać wykorzystane do tego rodzaju filtracji:

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

ocenia się

[A 1, A 2]

pasujące do wzorca w Mathematica

W Mathematicą , jedyna struktura występuje to drzewa , która jest wypełniana przez symbole. W Haskell składni pory, może być zdefiniowany jako

 data SymbolTree = Symbol String [SymbolTree]

Przykładem drzewo mógłby wtedy wyglądać

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

W tradycyjnym, bardziej odpowiedniej składni, symbole są zapisywane są one i poziomy drzewa są reprezentowane za pomocą [], tak, że na przykład a[b,c]jest drzewo A jako rodzica, B i C, jak dzieci.

Wzór w Mathematica polega oddanie „_” na stanowiskach w tym drzewie. Na przykład, wzór

A[_]

pasuje elementy, takie jak A [1] A [2], lub ogólniej [ x ] w którym x jest każda jednostka. W tym przypadku, Ajest to element betonowy, gdy _oznacza kawałek drzewie, które mogą być zmieniane. Symbol poprzedzał _wiąże dopasowanie do tej nazwy zmiennej podczas symbolem dołączane do _ogranicza mecze na węzłach tego symbolu. Zauważ, że nawet wygasza sami są wewnętrznie reprezentowane Blank[]przez _i Blank[x]dla _x.

Funkcja Mathematica Casesfiltruje elementy pierwszego argumentu, że pasuje do wzorca w drugim argumencie:

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

ocenia się

 {a[1], a[2]}

Pasujące do wzorca odnosi się do struktury wyrażeń. W przykładzie poniżej

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

powraca

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

ponieważ tylko te elementy będą pasować do wzorca a[b[_],_]wyżej.

W Mathematica, możliwe jest również, aby wyodrębnić struktur, ponieważ są one tworzone w trakcie obliczeń, niezależnie od tego, w jaki sposób i gdzie się one pojawią. Funkcja Tracemoże być stosowany do monitorowania obliczeń i powrót elementów, które powstają, które pasują do wzoru. Na przykład, można zdefiniować Fibonacciego jako

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

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

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

powraca struktury, która reprezentuje wystąpienia wzoru fib[_]struktury obliczeniowej:

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

programowanie deklaratywne

W językach programowania symboliczne, jest to łatwe do wzorców jako argumenty funkcji lub jako elementy struktury danych. Konsekwencją tego jest możliwość korzystania z wzorców do deklaratywnie składania oświadczeń o fragmenty danych oraz elastycznie instruować funkcje, jak działać.

Na przykład, Mathematica funkcja Compilemoże być używana do bardziej wydajne wersje kodu. W poniższym przykładzie dane nie szczególnie sprawa; liczy się to, że podwyrażenie {{com[_], Integer}}poucza Compile, że wyrażenia postaci com[_]może być traktowane jako liczby całkowite do celów kompilacji:

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

Skrzynek pocztowych w Erlang również działa w ten sposób.

Korespondencja Curry-Howard między dowodami i programów dotyczy ML -Style wzór pasujący do rozróżniana analizy i dowód przez wyczerpanie .

pasujące do wzorca i smyczki

Zdecydowanie najbardziej rozpowszechnioną formą dopasowywania wzorców polega na ciągi znaków. W wielu językach programowania, szczególny składnia strun jest używany do reprezentowania wyrażeń regularnych, które są wzory opisujące ciąg znaków.

Jednak możliwe jest, aby wykonać jakiś wzór pasujący ciąg w tych samych ramach, które zostały omówione w niniejszym artykule.

wzory drzewa dla ciągów

W Mathematica, ciągi są reprezentowane jako drzewa korzeni StringExpression i wszystkich znaków w kolejności jak dzieci korzenia. Dlatego, aby dopasować „dowolną ilość znaków spływu”, nowy wieloznaczny ___ jest potrzebne w przeciwieństwie do _ która pasuje tylko jeden znak.

W Haskell i funkcjonalnych języków programowania w ogóle, ciągi są reprezentowane funkcjonalnych listach znaków. Lista funkcyjną określa się jako pusty liście lub element zbudowanego na istniejącej listy. W składni Haskell:

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

Struktura o listę z niektórych elementów jest sposób element:list. Podczas dopasowywania wzorca, możemy stwierdzić, że pewien fragment danych jest równa pewnego wzorca. Na przykład, w funkcji:

 head (element:list) = element

możemy stwierdzić, że pierwszym elementem head„argument jest nazywany elementem, a funkcja zwraca to. Wiemy, że jest to pierwszy element ze względu na sposób wykazy są zdefiniowane, pojedynczego elementu skonstruowanego na liście. Ten pojedynczy element musi być pierwszy. Pusta lista nie pasuje do wzorca w ogóle, jak pusta lista nie posiada głowicę (pierwszy element, który jest zbudowany).

W tym przykładzie mamy żadnego pożytku list, więc możemy go pominąć, a więc napisać funkcję:

 head (element:_) = element

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

head[element, ]:=element

Wzory przykład łańcuch

W Mathematicą np

StringExpression["a",_]

dopasuje ciąg znaków, który ma dwa znaki i zaczyna się od „a”.

Ten sam wzór w Haskell:

 ['a', _]

Podmioty symboliczne mogą być wprowadzane do reprezentowania wiele różnych klas istotnych cech sznurku. Na przykład,

StringExpression[LetterCharacter, DigitCharacter]

dopasuje łańcuch, który składa się z małej litery, a potem numer.

W Haskell, strażnicy mogą być wykorzystane do osiągnięcia tych samych mecze:

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

Główną zaletą symbolicznej manipulacji ciąg jest to, że może on być całkowicie zintegrowane z resztą języka programowania, zamiast oddzielnego, specjalnego przeznaczenia podjednostki. Cała moc języka można wykorzystać do budowania wzorców same lub analizować i przekształcenie programów, które je zawierają.

snobol

Snobol ( String Oriented i symboliczny język ) to język programowania opracowany komputerowo między 1962 a 1967 w AT & T Bell Laboratories przez Davida J. Farber , Ralph E. Griswold i Ivan P. Polonsky .

SNOBOL4 wyróżnia się od większości języków programowania poprzez wzorce jako typ danych pierwszej klasy ( czyli typ danych, których wartości można manipulować na wszystkie sposoby dopuszczonych do innego typu danych w języku programowania) oraz zapewnienie operatorom na wzór konkatenacji i przemienności , Struny generowane podczas wykonywania mogą być traktowane jako programy i stracony.

Snobol został dość powszechnie nauczane w większych uniwersytetów amerykańskich pod koniec 1960 i na początku 1970 roku i był powszechnie stosowany w latach 1970 i 1980 jako języka manipulacji tekst w humanistyce .

Od stworzenia snobol, w nowszych języków takich jak Awk i Perl dokonały manipulacji ciągów za pomocą wyrażeń regularnych modne. Wzory SNOBOL4 jednak podciągnąć BNF gramatyk, które są równoważne z gramatyk bezkontekstowych i mocniejsze niż wyrażeń regularnych .

Zobacz też

Referencje

Linki zewnętrzne