String Pattern

A String Pattern is a pattern that describes a string set.

• AKA: Regular Expression, Search String Pattern.
• Context:
  • It can range from being a Lexical String Pattern to being a Regular String Expression.
  • It can be an Input to a String Pattern Matching Task.
  • It can be a member of a String Pattern Set.
  • ...
• Example(s):
  • any Lexical String Pattern.
    • the sequence of characters "car" in any context, such as "car", "cartoon", or "bicarbonate"
    • the word "car" when it appears as an isolated word (with a spacecharacter before and after).
  • any Regular String Expression.
    • a dollar sign immediately followed by one or more digits, and then optionally a period and exactly two more digits.
    • the word "car" when preceded by the word "blue" or "red"
  • any Syntactic Pattern, if the string is based on a Formal Grammar.
  • any Lexico-Syntactic Pattern, if the string is based on a Formal Grammar.
  • …
• Counter-Example(s):
  • any Graph Pattern.
  • any Itemset Pattern.
• See: Parse Tree, Sequence Pattern.

---

---

References

2009

• (Wikipedia, 2009) ⇒ http://en.wikipedia.org/wiki/Regular_expression
  • In computing, regular expressions provide a concise and flexible means for identifying strings of text of interest, such as particular characters, words, or patterns of characters. Regular expressions (abbreviated as regex or regexp, with plural forms regexes, regexps, or regexen) are written in a formal language that can be interpreted by a regular expression processor, a program that either serves as a parser generator or examines text and identifies parts that match the provided specification.
• The first computer programs to use pattern matching were text editors. At Bell Labs, Ken Thompson extended the seeking and replacing features of the QED editor to accept regular expressions. Early programming languages with pattern matching constructs include SNOBOL from 1962, SASL from 1976, NPL from 1977, and KRC from (1981). The first programming language with tree-based pattern matching features was Fred McBride's extension of LISP, in 1970. [1]
  • Regular expressions are used by many text editors, utilities, and programming languages to search and manipulate text based on patterns. For example, Perl, Ruby and Tcl have a powerful regular expression engine built directly into their syntax. Several utilities provided by Unix distributions — including the editor ed and the filter grep — were the first to popularize the concept of regular expressions.
• http://www.regular-expressions.info/
  • A regular expression (regex or regexp for short) is a special text string for describing a search pattern. You can think of regular expressions as wildcards on steroids. You are probably familiar with wildcard notations such as *.txt to find all text files in a file manager. The regex equivalent is .*\.txt$.
• (Wikipedia, 2009) ⇒ http://en.wikipedia.org/wiki/Parsing_expression_grammar
  • A parsing expression grammar, or PEG, is a type of analytic formal grammar that describes a formal language in terms of a set of rules for recognizing strings in the language. A parsing expression grammar essentially represents a recursive descent parser in a pure schematic form that expresses only syntax and is independent of the way an actual parser might be implemented or what it might be used for. Parsing expression grammars look similar to regular expressions or context-free grammars (CFG) in Backus-Naur form (BNF) notation, but have a different interpretation.
  • Unlike CFGs, PEGs cannot be ambiguous; if a string parses, it has exactly one valid parse tree. This suits PEGs well to parsing computer languages, but not natural languages.

2007

• (Stubblebine, 2007) ⇒ Tony Stubblebine. (2007). “Regular Expression Pocket Reference, 2nd edition." O'Reilly. ISBN:0596514271
  • QUOTE: This handy little book offers programmers a complete overview of the syntax and semantics of regular expressions that are at the heart of every text-processing application. Ideal as a quick reference, Regular Expression Pocket Reference covers the regular expression APIs for Perl 5.8, Ruby (including some upcoming 1.9 features), Java, PHP, .NET and C#, Python, vi, JavaScript, and the PCRE regular expression libraries

2002

• (Navarro & Raffinot, 2002) ⇒ Gonzalo Navarro, and Mathieu Raffinot. (2002). “Flexible Pattern Matching in Strings." Cambridge University Press.
  • String matching problems range from the relatively simple task of searching a single text for a string of characters to searching a database for approximate occurrences of a complex pattern.

1997

• (Open Group, 1997) ⇒ Open Group. (1997). “Regular Expressions, The Single UNIX Specification, Version 2.

1987

• (Karp & Rabin, 1987) ⇒ Richard M. Karp, and Michael O. Rabin. (1987). “Efficient Randomized Pattern-Matching Algorithms.” In: IBM Journal of Research and Development, 31(2).

1977

• (Knuth et al., 1977) ⇒ Donald E. Knuth, James H. Morris, Jr., and Vaughan R. Pratt. (1977). “Fast Pattern Matching in Strings.” In: SIAM Journal on Computing, 6(2).

1975

• (Aho & Corasick, 1975) ⇒ Alfred V. Aho, and Margaret J. Corasick. (1975). “Efficient String Matching: An aid to bibliographic search.” In: Communications of the ACM, 18(6).

---