Сопоставление с образцом
 | Эта статья нуждается в дополнительных ссылок для проверки . ( февраль 2011 г. ) |
В информатике — сопоставление с образцом это проверка заданной последовательности токенов на наличие составляющих некоторого шаблона . В отличие от распознавания образов , совпадение обычно должно быть точным: «либо совпадение, либо не совпадение». Шаблоны обычно имеют форму последовательностей или древовидных структур . Использование сопоставления с образцом включает вывод местоположений (если таковые имеются) шаблона в последовательности токенов, вывод некоторого компонента совпавшего шаблона и замену совпадающего шаблона некоторой другой последовательностью токенов (т. е. поиск и замена ).
Шаблоны последовательностей (например, текстовая строка) часто описываются с помощью регулярных выражений и сопоставляются с использованием таких методов, как возврат с возвратом .
Древовидные шаблоны используются в некоторых языках программирования в качестве общего инструмента для обработки данных на основе их структуры, например C# , [1] Ф# , [2] Хаскелл , [3] ML , Питон , [4] Рубин , [5] Ржавчина , [6] Скала , [7] Быстрый [8] и язык символьной математики Mathematica имеет специальный синтаксис для выражения древовидных шаблонов и языковую конструкцию для условного выполнения и поиска значений на его основе.
Часто можно предложить альтернативные шаблоны, которые опробуются один за другим, что дает мощную конструкцию условного программирования. Сопоставление с образцом иногда включает поддержку охранников . [ нужна цитата ]
История [ править ]
![[икона]](/wiki/File:Wiki_letter_w_cropped.svg){kind=small} | Этот раздел нуждается в расширении . Вы можете помочь, дополнив это . ( май 2008 г. ) |
Ранние языки программирования с конструкциями сопоставления шаблонов включают 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 , который определяет красно-черное дерево и функцию для его повторной балансировки после вставки элемента, показывает, как сопоставить более сложную структуру, созданную рекурсивным типом данных. Компилятор во время компиляции проверяет, что список случаев является исчерпывающим и ни один из них не является избыточным.
типа цвет = Красный | Черный
тип ' дерево = Пусто | дерево Цветное * ' дерево * ' a * ' дерево
let rebalance 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 [ править ]
В Mathematica единственной существующей структурой является дерево , заполненное символами. В синтаксисе Haskell , используемом до сих пор, это можно определить как
данные SymbolTree = символов Строка [ SymbolTree ]
Пример дерева может выглядеть так
Символ «а» [ Символ «б» [], Символ «в» []]
В традиционном, более подходящем синтаксисе символы записываются такими, какие они есть, а уровни дерева представляются с помощью [], так что, например a[b,c] — это дерево, в котором a является родителем, а b и c — дочерними элементами.
Шаблон в Mathematica предполагает размещение символа «_» в позициях этого дерева. Например, шаблон
А[_]
будет соответствовать таким элементам, как A[1], A[2] или, в более общем смысле, A[ x ], где x — любой объект. В этом случае, A является конкретным элементом, а _обозначает кусок дерева, который можно варьировать. Символ, добавленный к _ привязывает совпадение к этому имени переменной, в то время как символ добавляется к _ограничивает совпадения узлами этого символа. Обратите внимание, что даже сами пробелы внутренне представлены как Blank[] для _ и Blank[x] для _x.
Функция Математики 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 ]}}
Декларативное программирование [ править ]
В языках символьного программирования шаблоны легко использовать в качестве аргументов функций или элементов структур данных. Следствием этого является возможность использовать шаблоны для декларативного создания утверждений об фрагментах данных и гибкого указания функциям, как действовать.
Например, Mathematica функция Compileможет использоваться для создания более эффективных версий кода. В следующем примере детали не имеют особого значения; важно то, что подвыражение {{com[_], Integer}} поручает Compile что выражения формы com[_] можно считать целыми числами для целей компиляции :
com [ i_ ] := Биномиальный [ 2 i , i ]
Компилировать [{ x , { i , _Integer }}, x ^ com [ i ], {{ com [ _ ], Integer }}]
Почтовые ящики в Эрланге тоже работают таким же образом.
Соответствие Карри -Ховарда между доказательствами и программами связывает ML сопоставление шаблонов в стиле с анализом случаев и доказательством путем исчерпывания .
Сопоставление с образцом и строки [ править ]
Безусловно, наиболее распространенной формой сопоставления с образцом являются строки символов. Во многих языках программирования для представления регулярных выражений используется определенный синтаксис строк, которые представляют собой шаблоны, описывающие строковые символы.
Однако можно выполнить некоторое сопоставление строкового шаблона в той же среде, которая обсуждалась в этой статье.
Древовидные шаблоны для строк [ править ]
В Mathematica строки представлены в виде деревьев корня StringExpression, а все символы по порядку — дочерними элементами корня. Таким образом, чтобы соответствовать «любому количеству конечных символов», необходим новый подстановочный знак ___, в отличие от _, который соответствует только одному символу.
В Haskell и функциональных языках программирования в целом строки представлены в виде функциональных списков символов. Функциональный список определяется как пустой список или элемент, созданный на основе существующего списка. В синтаксисе Haskell:
[] — пустой список
x : xs — элемент x, созданный на основе списка xs
Таким образом, структура списка с некоторыми элементами такова: element:list. При сопоставлении с образцом мы утверждаем, что определенный фрагмент данных соответствует определенному шаблону. Например, в функции:
голова ( элемент : список ) = элемент
Мы утверждаем, что первый элемент headАргумент называется элементом, и функция возвращает его. Мы знаем, что это первый элемент из-за способа определения списков: один элемент создается в списке. Этот единственный элемент должен быть первым. Пустой список вообще не будет соответствовать шаблону, поскольку у пустого списка нет заголовка (первого созданного элемента).
В примере мы не используем list, поэтому мы можем игнорировать это и написать функцию:
голова ( элемент : _ ) = элемент
Эквивалентное преобразование Mathematica выражается как
голова[элемент,]:=элемент
Примеры шаблонов строк [ править ]
В системе Mathematica, например,
StringExpression["a",_]
будет соответствовать строке, состоящей из двух символов и начинающейся с «а».
Тот же шаблон в Haskell:
[ 'а' , _ ]
Символические сущности могут быть представлены для представления множества различных классов соответствующих характеристик строки. Например,
StringExpression[БуквенныйСимвол, ЦифровойСимвол]
будет соответствовать строке, состоящей сначала из буквы, а затем из цифры.
В Haskell охранники для достижения тех же совпадений можно использовать :
[ буква , цифра ] | isAlpha буква && isDigit цифра
Основное преимущество манипуляций с символьными строками заключается в том, что они могут быть полностью интегрированы с остальной частью языка программирования, а не представлять собой отдельный подраздел специального назначения. Вся мощь языка может быть использована для создания самих шаблонов или для анализа и преобразования программ, которые их содержат.
СНОБОЛ [ править ]
SNOBOL ( Строко-ориентированный и символический язык ) — язык компьютерного программирования, разработанный между 1962 и 1967 годами в лабораториях AT&T Bell Laboratories Дэвидом Дж. Фарбером , Ральфом Э. Грисволдом и Иваном П. Полонски .
SNOBOL4 отличается от большинства языков программирования тем, что шаблоны являются первоклассным типом данных ( т. е. типом данных, значениями которого можно манипулировать всеми способами, разрешенными для любого другого типа данных в языке программирования), а также наличием операторов для конкатенации и чередования шаблонов. . Строки, сгенерированные во время выполнения, можно рассматривать как программы и выполнять.
SNOBOL довольно широко преподавался в крупных университетах США в конце 1960-х и начале 1970-х годов и широко использовался в 1970-х и 1980-х годах в качестве языка манипулирования текстом в гуманитарных науках .
С момента создания SNOBOL новые языки, такие как Awk и Perl, сделали модными манипуляции со строками с помощью регулярных выражений . Однако шаблоны SNOBOL4 включают в себя грамматики BNF , которые эквивалентны контекстно-свободным грамматикам и более эффективны, чем регулярные выражения . [12]
См. также [ править ]
- Язык разметки искусственного интеллекта (AIML) для языка ИИ, основанный на сопоставлении шаблонов речи.
- AWK язык
- Шаблон Coccinelle соответствует исходному коду C
- Соответствующие подстановочные знаки
- глобус (программирование)
- Исчисление шаблонов
- Распознавание нечетких образов
- PCRE Perl-совместимые регулярные выражения, распространенная современная реализация сопоставления строковых шаблонов, портированная на многие языки.
- Диалект синтаксического анализа REBOL для сопоставления с образцом, используемый для реализации языковых диалектов.
- Символическая интеграция
- Теговый союз
- Том (язык сопоставления с образцом)
- СНОБОЛ — язык программирования, основанный на одном виде сопоставления с образцом.
- Язык шаблонов — метафорический, заимствованный из архитектуры.
- Сопоставление графиков
Ссылки [ править ]
- Книга Mathematica, глава Раздел 2.3: Шаблоны
- Отчет Haskell 98, глава 3.17 Сопоставление с образцом .
- Справочное руководство Python, глава 6.3 Операторы присваивания .
- Чистый язык программирования , глава 4.3: Шаблоны
- ^ «Сопоставление с образцом — Руководство по C#» .
- ^ «Сопоставление с образцом — Руководство по F#» .
- ^ Нежное введение в Haskell: шаблоны
- ^ «Что нового в Python 3.10 — документация Python 3.10.0b3» . docs.python.org . Проверено 6 июля 2021 г.
- ^ «pattern_matching — Документация для Ruby 3.0.0» . docs.ruby-lang.org . Проверено 6 июля 2021 г.
- ^ «Синтаксис шаблонов — язык программирования Rust» .
- ^ «Сопоставление с образцом» . Документация Скала . Проверено 17 января 2021 г.
- ^ «Шаблоны — язык программирования Swift (Swift 5.1)» .
- ^ Джоэл Мозес, «Символическая интеграция», Проект MIT MAC MAC-TR-47, декабрь 1967 г.
- ^ Канаторе, Алессандро (2003). «Алгоритмы сопоставления подстановочных знаков» .
- ^ «Случаи — документация на языке Wolfram» . ссылка.wolfram.com . Проверено 17 ноября 2020 г.
- ^ Гимпель, Дж. Ф. 1973. Теория дискретных шаблонов и их реализация в SNOBOL4. Коммун. ACM 16, 2 (февраль 1973 г.), 91–100. DOI= http://doi.acm.org/10.1145/361952.361960 .
Внешние ссылки [ править ]
- Представления: расширение сопоставления шаблонов Haskell
- Николаас Н. Остерхоф, Филип К. Ф. Хёльценшпис и Ян Купер. Шаблоны приложений . Презентация на выставке «Тенденции в функциональном программировании», 2005 г.
- JMatch : язык Java , дополненный сопоставлением с образцом.
- ShowTrend : Сопоставление шаблонов онлайн для цен на акции
- Неполная история текстового редактора QED Денниса Ритчи - представляет историю регулярных выражений в компьютерных программах.
- Реализация языков функционального программирования, страницы 53–103 Саймона Пейтона Джонса, опубликовано Prentice Hall, 1987.
- Немерль, сопоставление с образцом .
- Эрланг, сопоставление с образцом .
- Реквизит: язык сопоставления шаблонов на основе C++, 1999 г.
- PatMat: библиотека сопоставления шаблонов C++, основанная на SNOBOL / SPITBOL.
- Темур Куция. Плоское соответствие . Журнал символических вычислений 43 (12): 858–873. Подробно описывает плоское сопоставление в системе Mathematica.
- Язык сопоставления шаблонов языка EasyPattern для непрограммистов
| Базы данных органов управления : Национальные |
|---|
