Practical Programming Techniques: String Processing with Regular Expressions

Regular Expression Facilities

Regular expressions are a grammatical notation for defining string syntax, but without general recursion. See previous notes on Nonrecursive Syntax: The Regular Expression Metalanguage.

Regular expressions are widely supported in modern programming languages and tools.

• Programming language support is found in scripting and other programming languages.
  • Regular Expressions in Perl
  • Python Regular Expression HOWTO and documentation.
  • Regular Expressions in Javascript.
  • PHP supports both Perl-Compatible and POSIX Extended regular expressions.
  • The Java 2 Platform Standard Edition version 1.4.0 provides the java.util.regex package.
• Lexical analyzer generators such as flex can generate very efficient scanning tools.
• Many Unix programming tools use regular expressions.
  • sed, a stream editor
  • grep, a string searching program.
• Editors use regular expression for powerful search and replace operations.
  • Emacs info on Regular Expression Search
  .

Typical Regular Expression Syntax

Here we summarize the main features common to most regular expression facilities.

• Base Rule 1: Any printable ASCII character that is not a metacharacter (".", "^", "$", "/", etc.) is regular expression which matches itself.
• Base Rule 2: "." is a regular expression which matches any single character. (So "..." matches a field of length 3).
• Base Rule 3: "^" is a regular expression which matches the beginning of a line. (So "^From:" only matches the string "From:" appearing at the beginning of a line.
• Base Rule 4: "$" is a regular expression which matches the end of a line.
• Base Rule 5: The character "\" followed by any metacharacter is a regular expression that stands for that metacharacter. (Thus "\." matches ".", "\^" matches "^ and "\\" matches "\".)
• Base Rule 6: [] are set bracket metacharacters. [123] matches any one of the characters 1, 2 or 3. It stands for the set of the three single character strings "1", "2" and "3". Inside set brackets, "-" between two characters is used to specify a contiguous range of ASCII characters. Thus [A-Z] matches any upper case letter, and [A-Za-z0-9] matches any alphanumeric character. If the set is to include "-" as character, then it must be first, e.g., [-A-Z] matches and upper case letter or a hyphen. If the first character in the set brackets is "^", then the set is interpreted as all the characters not listed. Thus [^0-9] matches any character that is not a digit.
• Inductive Rule 1: If A and B are regular expressions, then AB matches concatenations of A and B.
• Inductive Rule 2: If A and B are regular expressions, then A|B is a regular expression that matches stands matched by either A or B.
• Inductive Rule 3: If A is a regular expression, then A* is a regular expression that matches zero or more occurrences of A.
• Inductive Rule 4: If A is a regular expression, then A+ is a regular expression that matches one or more occurrences of A.
• Inductive Rule 5: (Perl) If A is a regular expression and m and n are integers, then A{m,n} is a regular expression that matches from m to n occurrences of A. Thus [0-9]{2-4} matches a string of 2, 3 or 4 digits. Either m or n may be omitted, in which case there is no lower or upper bound, respectively, on the number of matches.
• Inductive Rule 6: If A is a regular expression, then (A) is an equivalent regular expression (Perl). The function of the parentheses is for grouping and substring selection. For example, the Perl statement

    ($hrs, $min, $sec) = 
        $timeStr =~ m/([0-9]+):([0-5][0-9]):([0-5][0-9])/;
  

  could select three subfields from $timeStr and assign them to appropriate variables. Here the Perl "m//" syntax is used to specify the regular expression for matching. Substring selection may also be used for matching and replacement with the "s///" syntax. For example:

    $timeStr =~ 
       s/([0-9]+):([0-5][0-9]):([0-5][0-9])/\2 min., \3 sec. after \1/;
  

  This is an operation that might change $timeStr from "4:25:18" to "25 min., 18 sec. after 4". In this example, the notation \1 stands for the first matched substring, \2 the second matched substring and so on.

  In other Unix tools, grouping uses "\(" and "\)" instead of "(" and ")". In those tools "(" and ")" simply stand for themselves. For example, in the "ex" or "vi" editors, a match and replace command might be:

  s/\([0-9]+\):\([0-5][0-9]\):\([0-5][0-9]\)/\2 min., \3 sec. after \1/;
  

• Precedence rule: of the two binary operations of concatenation and alternation, concatenation always takes precedence. If If A, B and C are regular expressions, then A|BC is interpreted as A|(BC) not (A|B)C.