В информатике сопоставление с образцом — это действие по проверке заданной последовательности токенов на наличие составляющих некоторого образца . В отличие от распознавания образов , сопоставление обычно должно быть точным: «либо это будет, либо нет». Образцы обычно имеют форму последовательностей , либо древовидных структур . Использование сопоставления с образцом включает вывод местоположений (если таковые имеются) образца в последовательности токенов, вывод некоторого компонента сопоставленного образца и замену сопоставленного образца некоторой другой последовательностью токенов (т. е. поиск и замена ).
Шаблоны последовательностей (например, текстовая строка) часто описываются с помощью регулярных выражений и сопоставляются с использованием таких методов, как поиск с возвратом .
Древовидные шаблоны используются в некоторых языках программирования как общий инструмент для обработки данных на основе их структуры, например, C# , [1] F# , [2] Haskell , [3] ML , Python , [4] Ruby , [5] Rust , [6] Scala , [7] Swift [8] и язык символьной математики Mathematica имеют специальный синтаксис для выражения древовидных шаблонов и языковую конструкцию для условного выполнения и извлечения значений на его основе.
Часто можно задать альтернативные шаблоны, которые проверяются один за другим, что дает мощную конструкцию условного программирования. Сопоставление шаблонов иногда включает поддержку охранников . [ необходима цитата ]
Ранние языки программирования с конструкциями сопоставления с образцом включают COMIT (1957), SNOBOL (1962), Refal (1968) с сопоставлением с образцом на основе дерева, Prolog (1972), St Andrews Static Language ( SASL ) (1976), NPL (1977) и Kent Recursive Calculator (KRC) (1981).
Многие текстовые редакторы поддерживают сопоставление с шаблонами различных видов: редактор QED поддерживает поиск по регулярным выражениям , а некоторые версии TECO поддерживают оператор OR в поиске.
Системы компьютерной алгебры обычно поддерживают сопоставление шаблонов с алгебраическими выражениями. [9]
Простейшим шаблоном в сопоставлении с образцом является явное значение или переменная. Для примера рассмотрим простое определение функции в синтаксисе Haskell (параметры функции не в скобках, а разделены пробелами, = — это не присваивание, а определение):
ф 0 = 1 Здесь 0 — это шаблон с одним значением. Теперь, когда f дается как аргумент 0, шаблон сопоставляется, и функция возвращает 1. С любым другим аргументом сопоставление и, следовательно, функция терпят неудачу. Поскольку синтаксис поддерживает альтернативные шаблоны в определениях функций, мы можем продолжить определение, расширив его для принятия более общих аргументов:
f n = n * f ( n - 1 ) Здесь первый n— это шаблон с одной переменной, который будет соответствовать абсолютно любому аргументу и связывать его с именем n для использования в остальной части определения. В Haskell (в отличие, по крайней мере, от Hope ) шаблоны проверяются по порядку, поэтому первое определение по-прежнему применяется в очень специфическом случае ввода 0, тогда как для любого другого аргумента функция возвращает n * f (n-1)значение n в качестве аргумента.
Шаблон подстановочных знаков (часто записываемый как _) также прост: как и имя переменной, он соответствует любому значению, но не связывает значение с каким-либо именем. Алгоритмы для сопоставления подстановочных знаков в простых ситуациях сопоставления строк были разработаны в ряде рекурсивных и нерекурсивных разновидностей. [10]
Более сложные шаблоны могут быть построены из примитивных из предыдущего раздела, обычно таким же образом, как значения строятся путем объединения других значений. Разница тогда в том, что с переменными и подстановочными частями шаблон не строится в одно значение, а соответствует группе значений, которые являются комбинацией конкретных элементов и элементов, которым разрешено изменяться в пределах структуры шаблона.
Шаблон дерева описывает часть дерева, начиная с узла и указывая некоторые ветви и узлы, а некоторые оставляя неуказанными с помощью шаблона переменной или подстановочного знака. Может быть полезно подумать об абстрактном синтаксическом дереве языка программирования и алгебраических типах данных .
В Haskell следующая строка определяет алгебраический тип данных Color, имеющий один конструктор данных ColorConstructor, который оборачивает целое число и строку.
данные Цвет = ColorConstructor Целое число Строка Конструктор — это узел в дереве, а целое число и строка — это листья в ветвях.
Когда мы хотим написать функции для создания Colorабстрактного типа данных , мы хотим написать функции для взаимодействия с типом данных, и, таким образом, мы хотим извлечь некоторые данные из типа данных, например, только строку или только целую часть Color.
Если мы передадим переменную типа Color, как мы можем получить данные из этой переменной? Например, для функции, которая получает целую часть Color, мы можем использовать простой шаблон дерева и написать:
integerPart ( ColorConstructor theInteger _ ) = theInteger Также:
stringPart ( ColorConstructor _ theString ) = theString Создание этих функций можно автоматизировать с помощью синтаксиса записей данных Haskell .
Этот пример OCaml , который определяет красно-черное дерево и функцию для его повторной балансировки после вставки элемента, показывает, как сопоставлять более сложную структуру, сгенерированную рекурсивным типом данных. Компилятор проверяет во время компиляции, что список случаев является исчерпывающим и ни один из них не является избыточным.
тип цвет = Красный | Черный тип ' дерево = Пусто | Дерево цвета * ' дерево * ' а * ' дерево пусть перебалансировка t = сопоставление t с | Дерево ( Черный , Дерево ( Красный , Дерево ( Красный , a , x , b ), y , c ), z , d ) | Дерево ( Черный , Дерево ( Красный , a , x , Дерево ( Красный , b , y , c )), z , d ) | Дерево ( Черный , a , x , Дерево ( Красный , Дерево ( Красный , b , y , c ), z , d )) | Дерево ( Черный , a , x , Дерево ( Красный , b , y , Дерево ( Красный , c , z , d ))) -> Дерево ( Красный , Дерево ( Черный , a , x , b ), y , Дерево ( Черный , c , z , d )) | _ -> t (* случай «объединить все», если ни один предыдущий шаблон не совпал *)Сопоставление с образцом может использоваться для фильтрации данных определенной структуры. Например, в Haskell для такого рода фильтрации можно использовать списочное понимание :
[ А х | А х <- [ А 1 , Б 1 , А 2 , Б 2 ]] оценивает
[А 1, А 2]
В Mathematica единственная существующая структура — это дерево , которое заполнено символами. В синтаксисе Haskell , который использовался до сих пор, это можно было бы определить как
данные SymbolTree = Строка символа [ SymbolTree ] Пример дерева может выглядеть так:
Символ "а" [ Символ "б" [], Символ "в" []] В традиционном, более подходящем синтаксисе символы записываются так, как они есть, а уровни дерева представляются с помощью [], так что, например, a[b,c]это дерево с a в качестве родительского элемента, а b и c в качестве дочерних элементов.
Шаблон в Mathematica подразумевает размещение "_" в позициях в этом дереве. Например, шаблон
А[_]
будет соответствовать таким элементам, как A[1], A[2] или, в более общем смысле, A[ x ], где x — любая сущность. В этом случае — Aэто конкретный элемент, а _обозначает часть дерева, которая может быть изменена. Символ, добавленный к , _связывает соответствие с этим именем переменной, в то время как символ, добавленный к , _ограничивает соответствия узлами этого символа. Обратите внимание, что даже сами пробелы внутренне представлены как Blank[]для _и Blank[x]для _x.
Функция Mathematica Casesфильтрует элементы первого аргумента, которые соответствуют шаблону во втором аргументе: [11]
Случаи [{ а [ 1 ], б [ 1 ], а [ 2 ], б [ 2 ]}, а [ _ ] ] оценивает
{ а [ 1 ], а [ 2 ]} Сопоставление с образцом применяется к структуре выражений. В примере ниже
Случаи [ { а [ б ], а [ б , в ], а [ б [ в ], г ], а [ б [ в ], г [ е ]], а [ б [ в ], г , е ]}, а [ б [ _ ], _ ] ] возвращается
{ а [ б [ в ], г ], а [ б [ в ], г [ д ]]} поскольку только эти элементы будут соответствовать шаблону a[b[_],_]выше.
В Mathematica также возможно извлекать структуры по мере их создания в ходе вычислений, независимо от того, как или где они появляются. Функцию Traceможно использовать для мониторинга вычислений и возвращать элементы, которые возникают и соответствуют шаблону. Например, мы можем определить последовательность Фибоначчи как
фиба [ 0 | 1 ] := 1 фиб [ n_ ] := фиб [ n -1 ] + фиб [ n -2 ] Затем мы можем задать вопрос: учитывая fib[3], какова последовательность рекурсивных вызовов Фибоначчи?
Трассировка [ фиб [ 3 ], фиб [ _ ]] возвращает структуру, которая представляет вхождения шаблона fib[_]в вычислительную структуру:
{ фиб [ 3 ], { фиб [ 2 ], { фиб [ 1 ]}, { фиб [ 0 ]}}, { фиб [ 1 ]}}В символических языках программирования легко использовать шаблоны в качестве аргументов функций или элементов структур данных. Следствием этого является возможность использовать шаблоны для декларативного создания утверждений о фрагментах данных и гибкого указания функциям, как работать.
Например, функция MathematicaCompile может использоваться для создания более эффективных версий кода. В следующем примере детали не имеют особого значения; важно то, что подвыражение {{com[_], Integer}}указывает Compile, что выражения формы com[_]могут предполагаться целыми числами для целей компиляции:
com [ i_ ] := Биномиальное [ 2 i , i ] Компилировать [{ x , { i , _Integer }}, x ^ com [ i ], {{ com [ _ ], Integer }}] Почтовые ящики в Erlang работают аналогичным образом.
Соответствие Карри–Ховарда между доказательствами и программами связывает сопоставление шаблонов в стиле машинного обучения с анализом случаев и доказательством методом исчерпания .
Наиболее распространенная форма сопоставления с образцом включает строки символов. Во многих языках программирования для представления регулярных выражений используется определенный синтаксис строк, которые являются образцами, описывающими символы строк.
Однако можно выполнить сопоставление строковых шаблонов в рамках той же структуры, которая обсуждалась в этой статье.
В Mathematica строки представлены как деревья корня StringExpression, а все символы по порядку — как потомки корня. Таким образом, для соответствия «любому количеству конечных символов» необходим новый подстановочный знак ___ в отличие от _, который соответствовал бы только одному символу.
В Haskell и функциональных языках программирования в целом строки представлены в виде функциональных списков символов. Функциональный список определяется как пустой список или элемент, созданный на основе существующего списка. В синтаксисе Haskell:
[] — пустой список x : xs — элемент x, созданный на основе списка xs Структура для списка с некоторыми элементами, таким образом element:list, . При сопоставлении с образцом мы утверждаем, что определенный фрагмент данных равен определенному образцу. Например, в функции:
голова ( элемент : список ) = элемент Мы утверждаем, что первый элемент headаргумента называется element, и функция возвращает this. Мы знаем, что это первый элемент, поскольку списки определяются как один элемент, построенный на списке. Этот один элемент должен быть первым. Пустой список вообще не будет соответствовать шаблону, так как пустой список не имеет head (первого элемента, который создается).
В этом примере нам не нужно list, поэтому мы можем его проигнорировать и записать функцию:
голова ( элемент : _ ) = элемент Эквивалентное преобразование Mathematica выражается как
голова[элемент, ]:=элемент
В Mathematica, например,
СтроковоеВыражение["a",_]
будет соответствовать строке, состоящей из двух символов и начинающейся с «a».
Тот же шаблон в Haskell:
[ 'а' , _ ] Символические сущности могут быть введены для представления множества различных классов соответствующих признаков строки. Например,
СтроковоеВыражение[БукваСимвол, ЦифраСимвол]
будет соответствовать строке, которая сначала состоит из буквы, а затем из цифры.
В Haskell для достижения тех же совпадений можно использовать защитные элементы :
[ буква , цифра ] | isAlpha буква && isDigit цифра Главное преимущество символической манипуляции строками заключается в том, что она может быть полностью интегрирована с остальной частью языка программирования, а не быть отдельным, специальным подразделением. Вся мощь языка может быть использована для построения самих шаблонов или анализа и преобразования программ, которые их содержат.
SNOBOL ( StriNg Oriented and symBOlic Language ) — язык программирования, разработанный в 1962—1967 годах в лабораториях AT&T Bell Laboratories Дэвидом Дж. Фарбером , Ральфом Э. Грисволдом и Иваном П. Полонским.
SNOBOL4 отличается от большинства языков программирования тем, что имеет шаблоны как тип данных первого класса ( т. е. тип данных, значениями которого можно манипулировать всеми способами, разрешенными для любого другого типа данных в языке программирования) и предоставляет операторы для конкатенации и чередования шаблонов . Строки, сгенерированные во время выполнения, можно рассматривать как программы и выполнять.
SNOBOL довольно широко преподавался в крупных университетах США в конце 1960-х и начале 1970-х годов и широко использовался в 1970-х и 1980-х годах как язык обработки текстов в гуманитарных науках .
С момента создания SNOBOL новые языки, такие как Awk и Perl, сделали модной обработку строк с помощью регулярных выражений . Однако шаблоны SNOBOL4 включают в себя грамматики BNF , которые эквивалентны контекстно-свободным грамматикам и более мощны, чем регулярные выражения . [12]
