В информатике сопоставление с образцом — это проверка заданной последовательности токенов на наличие составляющих некоторого шаблона . В отличие от распознавания образов , совпадение обычно должно быть точным: «либо совпадение, либо не совпадение». Шаблоны обычно имеют форму последовательностей или древовидных структур . Использование сопоставления с образцом включает вывод местоположений (если таковые имеются) шаблона в последовательности токенов, вывод некоторого компонента совпавшего шаблона и замену совпадающего шаблона некоторой другой последовательностью токенов (т. е. поиск и замена ).
Шаблоны последовательностей (например, текстовая строка) часто описываются с помощью регулярных выражений и сопоставляются с использованием таких методов, как возврат с возвратом .
Древовидные шаблоны используются в некоторых языках программирования в качестве общего инструмента для обработки данных на основе их структуры, например 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), и Кентский рекурсивный калькулятор (KRC) (1981).
Многие текстовые редакторы поддерживают сопоставление шаблонов различных типов: редактор QED поддерживает поиск по регулярным выражениям , а некоторые версии TECO поддерживают оператор OR при поиске.
Системы компьютерной алгебры обычно поддерживают сопоставление с образцом алгебраических выражений. [9]
Самый простой шаблон сопоставления с образцом — это явное значение или переменная. В качестве примера рассмотрим простое определение функции в синтаксисе Haskell (параметры функции не заключаются в круглые скобки, а разделяются пробелами, = — это не присвоение, а определение):
ж 0 = 1 Здесь 0 — это шаблон с одним значением. Теперь, когда f в качестве аргумента присваивается 0, шаблон совпадает, и функция возвращает 1. При любом другом аргументе сопоставление и, следовательно, функция завершаются неудачно. Поскольку синтаксис поддерживает альтернативные шаблоны в определениях функций, мы можем продолжить определение, расширив его, включив в него более общие аргументы:
ж п знак равно п * ж ( п - 1 ) Здесь первым nявляется шаблон одной переменной, который будет соответствовать абсолютно любому аргументу и связывать его с именем n, которое будет использоваться в остальной части определения. В Haskell (в отличие, по крайней мере, от Hope ) шаблоны проверяются по порядку, поэтому первое определение по-прежнему применимо в очень специфическом случае, когда входное значение равно 0, в то время как для любого другого аргумента функция возвращает значение n * f (n-1)n в качестве аргумента.
Шаблон подстановочного знака (часто обозначаемый как _) также прост: как и имя переменной, он соответствует любому значению, но не привязывает это значение к какому-либо имени. Алгоритмы сопоставления подстановочных знаков в простых ситуациях сопоставления строк были разработаны в ряде рекурсивных и нерекурсивных разновидностей. [10]
Более сложные шаблоны могут быть построены из примитивных шаблонов из предыдущего раздела, обычно так же, как значения создаются путем объединения других значений. Разница в том, что с переменными и подстановочными знаками шаблон не объединяется в одно значение, а соответствует группе значений, которые представляют собой комбинацию конкретных элементов и элементов, которые могут изменяться в пределах структуры шаблона. .
Шаблон дерева описывает часть дерева, начиная с узла и указывая некоторые ветви и узлы, а некоторые оставляя неуказанными с помощью шаблона переменной или подстановочного знака. Возможно, будет полезно подумать об абстрактном синтаксическом дереве языка программирования и алгебраических типах данных .
В Haskell следующая строка определяет алгебраический тип данных Color, который имеет один конструктор данных ColorConstructor, который обертывает целое число и строку.
Цвет данных = Целочисленная строка ColorConstructor Конструктор — это узел дерева, а целое число и строка — это листья в ветвях.
Когда мы хотим написать функции для создания Colorабстрактного типа данных , мы хотим написать функции для взаимодействия с типом данных, и поэтому мы хотим извлечь некоторые данные из типа данных, например, только строку или только целую часть Color.
Если мы передадим переменную типа Color, как мы сможем получить данные из этой переменной? Например, чтобы функция могла получить целочисленную часть Color, мы можем использовать простой древовидный шаблон и написать:
целочисленная часть ( 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 , Дерево ( Красный , Дерево ( Красный , б , 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[]for _и Blank[x]for _x.
Функция Mathematica Casesфильтрует элементы первого аргумента, которые соответствуют шаблону во втором аргументе: [11]
Случаи [{ a [ 1 ], b [ 1 ], a [ 2 ], b [ 2 ]}, a [ _ ] ] оценивается как
{ а [ 1 ], а [ 2 ]} Сопоставление с образцом применяется к структуре выражений. В примере ниже
Случаи [ { a [ b ], a [ b , c ], a [ b [ c ], d ], a [ b [ c ], d [ e ]], a [ b [ c ], d , e ]} , а [ б [ _ ], _ ] ] возвращает
{ а [ б [ с ], d ], а [ б [ с ], d [ е ]]} потому что только эти элементы будут соответствовать приведенному выше шаблону 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 также работают таким же образом.
Соответствие Карри -Ховарда между доказательствами и программами связывает сопоставление шаблонов в стиле ML с анализом случаев и доказательством путем исчерпывания .
Безусловно, наиболее распространенной формой сопоставления с образцом являются строки символов. Во многих языках программирования для представления регулярных выражений используется определенный синтаксис строк, которые представляют собой шаблоны, описывающие строковые символы.
Однако можно выполнить некоторое сопоставление строкового шаблона в той же среде, которая обсуждалась в этой статье.
В системе Mathematica строки представлены в виде деревьев корня StringExpression, а все символы по порядку — дочерними элементами корня. Таким образом, чтобы соответствовать «любому количеству конечных символов», необходим новый подстановочный знак ___, в отличие от _, который соответствует только одному символу.
В Haskell и функциональных языках программирования в целом строки представлены в виде функциональных списков символов. Функциональный список определяется как пустой список или элемент, созданный на основе существующего списка. В синтаксисе Haskell:
[] — пустой список x : xs — элемент x, созданный на основе списка xs Таким образом, структура списка с некоторыми элементами такова element:list. При сопоставлении с образцом мы утверждаем, что определенный фрагмент данных соответствует определенному шаблону. Например, в функции:
голова ( элемент : список ) = элемент Мы утверждаем, что первый элемент headаргумента ' называется element, и функция возвращает его. Мы знаем, что это первый элемент из-за способа определения списков: один элемент создается в списке. Этот единственный элемент должен быть первым. Пустой список вообще не будет соответствовать шаблону, поскольку у пустого списка нет заголовка (первого созданного элемента).
В этом примере мы не используем list, поэтому можем игнорировать его и написать функцию:
голова ( элемент : _ ) = элемент Эквивалентное преобразование Mathematica выражается как
голова[элемент,]:=элемент
В системе Mathematica, например,
StringExpression["a",_]
будет соответствовать строке, состоящей из двух символов и начинающейся с «а».
Тот же шаблон в Haskell:
[ 'а' , _ ] Символические сущности могут быть введены для представления множества различных классов соответствующих характеристик строки. Например,
StringExpression[БуквенныйСимвол, ЦифровойСимвол]
будет соответствовать строке, состоящей сначала из буквы, а затем из цифры.
В Haskell для достижения тех же совпадений можно использовать охранники :
[ буква , цифра ] | буква isAlpha && цифра isDigit Основное преимущество манипуляций с символьными строками заключается в том, что они могут быть полностью интегрированы с остальной частью языка программирования, а не представлять собой отдельный подраздел специального назначения. Вся мощь языка может быть использована для создания самих шаблонов или для анализа и преобразования программ, которые их содержат.
SNOBOL ( StrNg Oriented and SymBOlic Language ) — язык компьютерного программирования, разработанный между 1962 и 1967 годами в лабораториях AT&T Bell Laboratories Дэвидом Дж. Фарбером , Ральфом Э. Грисволдом и Иваном П. Полонски.
SNOBOL4 отличается от большинства языков программирования тем, что шаблоны являются первоклассным типом данных ( т. е . типом данных, значениями которого можно манипулировать всеми способами, разрешенными для любого другого типа данных в языке программирования), а также наличием операторов для конкатенации и чередования шаблонов. . Строки, сгенерированные во время выполнения, можно рассматривать как программы и выполнять.
SNOBOL довольно широко преподавался в крупных университетах США в конце 1960-х и начале 1970-х годов и широко использовался в 1970-х и 1980-х годах в качестве языка манипулирования текстом в гуманитарных науках .
С момента создания SNOBOL новые языки, такие как Awk и Perl, сделали модными манипуляции со строками с помощью регулярных выражений . Однако шаблоны SNOBOL4 включают в себя грамматики BNF , которые эквивалентны контекстно-свободным грамматикам и более эффективны, чем регулярные выражения . [12]
