Войти
В информатике сопоставление с образцом - это проверка заданного последовательность токенов на наличие составляющих некоторого шаблона. В отличие от распознавания образов, совпадение обычно должно быть точным: «совпадение будет или не будет». Шаблоны обычно имеют форму последовательностей или древовидных структур. Использование сопоставления с образцом включает вывод местоположений (если они есть) образца в последовательности токенов, для вывода некоторого компонента сопоставленного образца и для замены сопоставленного образца какой-либо другой последовательностью маркеров (т. Е. поиск и замена ).
Шаблоны последовательности (например, текстовая строка) часто описываются с помощью регулярных выражений и сопоставляются с использованием таких методов, как поиск с возвратом.
Шаблоны дерева используются в некоторых программах languages как общий инструмент для обработки данных на основе их структуры, например C#,F#,Haskell, ML, Rust, Scala, Swift и язык символьной математики Mathematica имеют специальный синтаксис для выражения шаблонов деревьев и языковая конструкция для условного выполнения и получение значения на ее основе. По причинам простоты и эффективности в этих шаблонах дерева отсутствуют некоторые функции, доступные в регулярных выражениях.
Часто можно указать альтернативные шаблоны, которые проверяются один за другим, что дает мощную конструкцию условного программирования . Сопоставление с образцом иногда включает поддержку охранников.
Анализ алгоритмы часто полагаются на сопоставление с образцом для преобразования строк в синтаксические деревья.
Первыми компьютерными программами, которые использовали сопоставление с образцом, были текстовые редакторы. В Bell Labs, Кен Томпсон расширил возможности поиска и замены, чтобы принимать регулярные выражения. Ранние языки программирования с конструкциями сопоставления с образцом включают SNOBOL с 1962 года, советский язык Refal с 1968 года с сопоставлением с образцом на основе дерева, SASL с 1976, NPL с 1977 года и KRC с 1981 года. Другим языком программирования с функциями сопоставления шаблонов на основе дерева было расширение Фреда Макбрайда LISP в 1970 году.
Простейшим шаблоном сопоставления с образцом является явное значение или переменная. В качестве примера рассмотрим простое определение функции в синтаксисе Haskell (параметры функции не в скобках, а разделены пробелами, = не присвоение, а определение):
f 0 = 1
Здесь 0 - одно значение шаблон. Теперь, когда для f задано 0 в качестве аргумента, шаблон совпадает, и функция возвращает 1. С любым другим аргументом сопоставление и, следовательно, функция терпят неудачу. Поскольку синтаксис поддерживает альтернативные шаблоны в определениях функций, мы можем продолжить определение, расширив его, чтобы принять более общие аргументы:
fn = n * f (n-1)
Здесь первый n- это шаблон с одной переменной, который будет соответствовать абсолютно любому аргументу и связывать его с именем n, которое будет использоваться в остальной части определения. В Haskell (в отличие от Hope ) шаблоны проверяются по порядку, поэтому первое определение по-прежнему применяется в очень конкретном случае, когда входной параметр равен 0, в то время как для любого другого аргумента функция возвращает n * f (n-1)с аргументом n.
Шаблон подстановки (часто записываемый как _) также прост: как и имя переменной, он соответствует любому значению, но не связывает это значение с каким-либо именем. Алгоритмы сопоставления подстановочных знаков в простых ситуациях сопоставления строк были разработаны в ряде рекурсивных и нерекурсивных разновидностей.
Более сложные шаблоны могут быть построены из примитивов из предыдущего раздела, обычно таким же образом, как значения создаются путем объединения других значений. Разница в том, что с частями переменных и подстановочных знаков шаблон не встраивается в одно значение, а соответствует группе значений, которые представляют собой комбинацию конкретных элементов и элементов, которым разрешено варьироваться в структуре шаблона..
Шаблон дерева описывает часть дерева, начиная с узла и указывая некоторые ветви и узлы и оставляя некоторые неопределенными с помощью переменной или шаблона подстановки. Можно подумать об абстрактном синтаксическом дереве языка программирования и алгебраических типах данных.
В Haskell следующая строка определяет алгебраический тип данных Color, который имеет единственный конструктор данных ColorConstructor, который обертывает целое число и строку.
data Color = ColorConstructor Integer String
Конструктор - это узел в дереве, а целое число и строка - это листья в ветвях.
Когда мы хотим написать functions, чтобы сделать Colorабстрактным типом данных, мы хотим записать функции в interface с типом данных, и, следовательно, мы хотим извлечь некоторые данные из типа данных, например, только строку или целую часть Color.
Если мы передаем переменную типа Color, как можем ли мы получить данные из этой переменной? Например, для функции, получающей целую часть Color, мы можем использовать простой шаблон дерева и написать:
integerPart (ColorConstructor theInteger _) = theInteger
Также:
stringPart (ColorConstructor _ theString) = theString
Создание этих функций можно автоматизировать с помощью синтаксиса записи данных Haskell.
Сопоставление с шаблоном можно использовать для фильтрации данных определенной структуры. Например, в Haskell для этого вида фильтрации можно использовать понимание списка :
[A x | A x <- [A 1, B 1, A 2, B 2]]
оценивается как
[A 1, A 2]
В Mathematica единственная существующая структура - это дерево, которое заполнено символами. В синтаксисе Haskell, который использовался до сих пор, это может быть определено как
data SymbolTree = Symbol String [SymbolTree]
Примерное дерево может тогда выглядеть как
Symbol "a" [Symbol " b ", Symbol" c "]
В традиционном, более подходящем синтаксисе символы записываются как есть, а уровни дерева представлены с использованием, так что, например, a [b, c]- это дерево с a в качестве родителя и b и c в качестве дочерних элементов.
Шаблон в системе Mathematica включает размещение символа "_" в позициях в этом дереве. Например, шаблон
A [_]
будет соответствовать таким элементам, как A [1], A [2] или, в более общем смысле, A [x], где x - это любой объект. В данном случае A- это конкретный элемент, а _обозначает часть дерева, которую можно изменять. Символ, добавленный к _, связывает совпадение с этим именем переменной, в то время как символ, добавленный к _, ограничивает совпадения узлами этого символа. Обратите внимание, что даже сами пробелы внутренне представлены как Пробелдля _и Пробел [x]для _x.
Функция Mathematica Casesфильтрует элементы первого аргумента, которые соответствуют шаблону во втором аргументе:
Cases [{a [1], b [1], a [2], b [2]}, a [_]]оценивает to
{a [1], a [2]}Сопоставление с образцом применяется к структуре выражений. В приведенном ниже примере
Cases [{a [b], a [b, c], a [b [c], d], a [b [c], d [e]]], a [b [ c], d, e]}, a [b [_], _]]возвращает
{a [b [c], d], a [b [c], d [e]]}, потому что только эти элементы будут соответствовать шаблону a [b [_], _]выше.
В системе Mathematica также можно извлекать структуры по мере их создания в процессе вычислений, независимо от того, как и где они появляются. Функция Traceможет использоваться для отслеживания вычислений и возврата возникающих элементов, соответствующих шаблону. Например, мы можем определить последовательность Фибоначчи как
fib [0 | 1]: = 1 fib [n _]: = fib [n-1] + fib [n-2]
Тогда мы можем задать вопрос: какова последовательность рекурсивных вызовов Фибоначчи для fib [3]?
Trace [fib [3], fib [_]]
возвращает структуру, которая представляет вхождения шаблона fib [_]в вычислительной структуре:
{fib [3 ], {fib [2], {fib [1]}, {fib [0]}}, {fib [1]}}В символьных языках программирования легко имеют шаблоны в качестве аргументов функций или элементов структур данных. Следствием этого является возможность использовать шаблоны, чтобы декларативно делать утверждения о фрагментах данных и гибко инструктировать функции, как работать.
Например, функция Mathematica Compileможет использоваться для создания более эффективных версий кода. В следующем примере детали не имеют особого значения; важно то, что подвыражение {{com [_], Integer}}инструктирует Compile, что выражения формы com [_]можно считать целые числа для целей компиляции:
com [i_]: = Binomial [2i, i] Compile [{x, {i, _Integer}}}, x ^ com [i], {{com [_], Integer}}]Почтовые ящики в Erlang также работают таким же образом.
Соответствие Карри – Ховарда между доказательствами и программами связывает сопоставление образцов в стиле ML с анализом случаев и доказательством исчерпания.
Самая распространенная форма сопоставления с образцом включает строки символов. Во многих языках программирования для представления регулярных выражений используется определенный синтаксис строк, которые представляют собой шаблоны, описывающие строковые символы.
Однако можно выполнить сопоставление некоторого строкового шаблона в рамках той же структуры, которая обсуждалась в этой статье.
В системе Mathematica строки представлены как деревья корневого StringExpression, а все символы по порядку являются дочерними по отношению к корню. Таким образом, чтобы соответствовать «любому количеству завершающих символов», необходим новый подстановочный знак ___ в отличие от _, который соответствовал бы только одному символу.
В Haskell и языках функционального программирования в целом строки представлены как функциональные списки символов. Функциональный список определяется как пустой список или элемент, созданный на основе существующего списка. В синтаксисе Haskell:
- пустой список x: xs - элемент x, построенный на списке xs
Таким образом, структура списка с некоторыми элементами element: list. При сопоставлении с образцом мы утверждаем, что определенный фрагмент данных равен определенному образцу. Например, в функции:
head (element: list) = element
Мы утверждаем, что первый элемент аргумента headназывается element, и функция возвращает это. Мы знаем, что это первый элемент из-за способа определения списков: единственный элемент, созданный на основе списка. Этот единственный элемент должен быть первым. Пустой список вообще не будет соответствовать шаблону, поскольку пустой список не имеет заголовка (первого созданного элемента).
В этом примере мы не используем list, поэтому мы можем игнорировать его и, таким образом, написать функцию:
head (element: _) = element
Эквивалентное преобразование Mathematica выражается как
head [element,]: = element
Например, в Mathematica
StringExpression [" a ", _]
будет соответствовать строке, состоящей из двух символов и начинающейся с" a ".
Тот же шаблон в Haskell:
['a', _]
Могут быть введены символические сущности для представления множества различных классов соответствующих свойств строки. Например,
StringExpression [LetterCharacter, DigitCharacter]
будет соответствовать строке, состоящей сначала из буквы, а затем из числа.
В Haskell guard можно использовать для достижения тех же совпадений:
[буква, цифра] | isAlpha letter isDigit digit
Основным преимуществом манипуляции с символьной строкой является то, что она может быть полностью интегрирована с остальной частью языка программирования, а не быть отдельным подразделением специального назначения. Вся мощь языка может быть использована для создания самих шаблонов или анализа и преобразования программ, которые их содержат.
SNOBOL (StriNg Oriented and symBOlic Language) - язык компьютерного программирования, разработанный в период с 1962 по 1967 год в ATT Bell Laboratories Дэвид Дж. Фарбер, Ральф Э. Грисволд и.
SNOBOL4 отличается от большинства языков программирования тем, что имеет шаблоны как первоклассный тип данных (т. Е. Тип данных, значениями которого можно манипулировать всеми способами, разрешенными для любого другого типа данных в язык программирования) и предоставив операторы для шаблона конкатенации и чередования. Строки, сгенерированные во время выполнения, можно рассматривать как программы и выполнять.
СНОБОЛ довольно широко преподавался в крупных университетах США в конце 1960-х - начале 1970-х годов и широко использовался в 1970-х и 1980-х годах в качестве языка манипулирования текстом в гуманитарных науках.
С момента создания СНОБОЛА более новые В таких языках, как Awk и Perl, стало модным манипулирование строками с помощью регулярных выражений. Однако шаблоны SNOBOL4 включают в себя BNF грамматики, которые эквивалентны контекстно-свободным грамматикам и более эффективны, чем регулярные выражения.
 | В Wikibook Haskell есть страница по теме: Сопоставление с образцом |
 | На Wikimedia Commons есть a, относящийся к сопоставлению с образцом. |
