Сопоставление с образцом в программировании: проверка последовательностей на соответствие заданному шаблону. Точное соответствие, регулярные выражения, поиск и замена.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Сопоставление с образцом — это проверка заданной последовательности токенов на наличие составляющих некоторого образца. Сопоставление с образцом в функциональном программировании — это использование переменных критериев сопоставления при определении абстрактных образцов для сопоставления.
Act of checking a given sequence of tokens for the presence of the constituents of some pattern
pattern matching in functional programming
the use of variable matching criteria in defining abstract patterns to match
В информатике сопоставление с образцом — это проверка заданной последовательности токенов на наличие составляющих некоторого образца. В отличие от распознавания образов, сопоставление обычно должно быть точным: "либо есть совпадение, либо его нет". Образцы обычно имеют форму последовательностей или древовидных структур. Области применения сопоставления с образцом включают вывод местоположений (при наличии) образца в последовательности токенов, вывод отдельных компонентов сопоставленного образца и замену сопоставленного образца другой последовательностью токенов (то есть поиск и замена). Последовательные образцы (например, текстовая строка) часто описываются с помощью регулярных выражений и сопоставляются с использованием таких методов, как возврат. Древовидные образцы используются в некоторых языках программирования как универсальный инструмент для обработки данных на основе их структуры, например, C#, F#, Haskell, ML, Python, Ruby, Rust, Scala, Swift и язык символьных вычислений Mathematica имеют специальный синтаксис для выражения древовидных образцов и языковую конструкцию для условного выполнения и извлечения значений на их основе. Часто можно задавать альтернативные образцы, которые перебираются последовательно, что обеспечивает мощную конструкцию условного программирования. Сопоставление с образцом иногда включает поддержку охранных условий.
In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact: "either it will or will not be a match." The patterns generally have the form of either sequences or tree structures. Uses of pattern matching include outputting the locations (if any) of a pattern within a token sequence, to output some component of the matched pattern, and to substitute the matching pattern with some other token sequence (i. e., search and replace). Sequence patterns (e. g., a text string) are often described using regular expressions and matched using techniques such as backtracking. Tree patterns are used in some programming languages as a general tool to process data based on its structure, e. g. C#, F#, Haskell, ML, Python, Ruby, Rust, Scala, Swift and the symbolic mathematics language Mathematica have special syntax for expressing tree patterns and a language construct for conditional execution and value retrieval based on it. Often it is possible to give alternative patterns that are tried one by one, which yields a powerful conditional programming construct. Pattern matching sometimes includes support for guards.
История
Ранние языки программирования с конструкциями сопоставления с образцом включают COMIT (1957), SNOBOL (1962), Refal (1968) с сопоставлением с образцом на основе деревьев, Prolog (1972), St Andrews Static Language (SASL) (1976), NPL (1977) и Kent Recursive Calculator (KRC) (1981). Многие текстовые редакторы поддерживают сопоставление с образцом различных видов: редактор QED поддерживает поиск по регулярным выражениям, а некоторые версии TECO поддерживают оператор OR при поиске. Компьютерные алгебраические системы обычно поддерживают сопоставление с образцом для алгебраических выражений.
Early programming languages with pattern matching constructs include COMIT (1957), SNOBOL (1962), Refal (1968) with tree based pattern matching, Prolog (1972), St Andrews Static Language (SASL) (1976), NPL (1977), and Kent Recursive Calculator (KRC) (1981). Many text editors support pattern matching of various kinds: the QED editor supports regular expression search, and some versions of TECO support the OR operator in searches. Computer algebra systems generally support pattern matching on algebraic expressions.
Сопоставление шаблонов и струн
Наиболее распространенная форма сопоставления с образцом включает в себя строки символов. Во многих языках программирования для представления регулярных выражений, являющихся шаблонами, описывающими символы в строках, используется определенный синтаксис строк. Однако сопоставление строк с образцом возможно выполнять в той же структуре, которая рассматривалась в данной статье.
By far the most common form of pattern matching involves strings of characters. In many programming languages, a particular syntax of strings is used to represent regular expressions, which are patterns describing string characters. However, it is possible to perform some string pattern matching within the same framework that has been discussed throughout this article.
СНОБОЛ
SNOBOL (StriNg Oriented and symBOlic Language) — это язык программирования, разработанный в 1962–1967 годах в лабораториях AT&T Bell Дэвидом Дж. Фарбером, Ральфом Э. Грисуолдом и Иваном П. Полонским. SNOBOL4 выделяется среди большинства языков программирования тем, что рассматривает шаблоны как полноценный тип данных (то есть тип данных, значениями которого можно оперировать всеми способами, допустимыми для любого другого типа данных в языке программирования) и предоставляет операторы для конкатенации и чередования шаблонов. Строки, генерируемые в процессе выполнения, могут рассматриваться как программы и выполняться. SNOBOL широко преподавался в крупных университетах США в конце 1960-х и начале 1970-х годов и широко использовался в 1970-х и 1980-х годах как язык для обработки текста в гуманитарных науках. После создания SNOBOL более новые языки, такие как Awk и Perl, сделали популярным манипулирование строками с помощью регулярных выражений. Однако шаблоны SNOBOL4 охватывают грамматики BNF, которые эквивалентны контекстно-свободным грамматикам и более мощны, чем регулярные выражения.
SNOBOL (StriNg Oriented and symBOlic Language) is a computer programming language developed between 1962 and 1967 at AT&T Bell Laboratories by David J. Farber, Ralph E. Griswold and Ivan P. Polonsky. SNOBOL4 stands apart from most programming languages by having patterns as a first class data type (i. e. a data type whose values can be manipulated in all ways permitted to any other data type in the programming language) and by providing operators for pattern concatenation and alternation. Strings generated during execution can be treated as programs and executed. SNOBOL was quite widely taught in larger US universities in the late 1960s and early 1970s and was widely used in the 1970s and 1980s as a text manipulation language in the humanities. Since SNOBOL's creation, newer languages such as Awk and Perl have made string manipulation by means of regular expressions fashionable. SNOBOL4 patterns, however, subsume BNF grammars, which are equivalent to context free grammars and more powerful than regular expressions.