Regular Expressions

• introduced 1956 from S.C. Kleene, to describe the states of a FSA (model of nervous activity)
• REs describe the Form of character strings
• A string is matched by a RE if the string is a element of the class described by the RE
• REs are greedy
• Forms of REs:
  • basic REs (ed, sed, lex, ...)
  • extended REs (egrep, awk, regex(3), ...)
  • perl compatible REs (perl, libpcre, ...)
• Definition of a (extended) RE
  • A RE is one or more non-empty branches, separated by '|'. It matches anything that matches one of the branches
  • A branch is the concatenation of one or more pieces
  • A piece is an atom, possibly followed by a single(!) '*', '+', '?', or a bound
• Documentation
  • manpages regex(7), awk(1), lex(1)
  • Regular Expressions in the The Single UNIX ® Specification, Version 2
  • Compilers -- Principle, Techniques and Tools, by Aho Sethi and Ullman, Addison Wesley