CSC/ECE 517 Fall 2009/wiki1b 5 13

Regular Expressions:

A pattern matching language used to match user defined patterns within text strings/files. Regular expressions gained popularity with the Unix ed and grep (grep derived from ed's search command g/re/p[1]). Since then regular expressions have been incorporated into text editors, command utilities and programming languages.

Regular Expression Engines:

There are two prominent types of regular expression engines; DFA (Deterministic Finite Automaton) and NFA (Nondeterministic Finite Automaton). NFA is found primarily in modern scripting languages, while DFA is found in older parsers.

DFA (Deterministic Finite Automaton) : State machine based algorithm that keeps track of all matches in progress. As soon as a match is made it returns "leftmost match wins"[2]; with the exception of alternation matches (<substring1>|<substring2>). If all alternation options match then the longest match will be selected - "longest leftmost match wins". Non-greedy searches are not supported since they are nondeterministic in nature. ie A.c =~ AbcvAbcAdd returns Abc DFA Languages : lex, awk, vi(m)

NFA (Nondeterministic Finite Automaton) : Greedy search routine that keeps track where the algorithm branches to determine if the most greedy match succeeds; will roll back to original position for subsequent less greedy matches. Supports non-greedy matches (ie match 0 or 1 times). ie A.c =~ AbcvAbcAdd matches both occurrences of Abc in the string. NFA Types:

• Traditional NFA : gives preference to the earliest substring in alternation matches (dog|doggy). (dog|doggy) =~ doggy returns dog. (doggy|dog) =~ doggy returns doggy.
• POSIX NFA : handles alternation matches like DFA engines. ie (dog|doggy) =~ doggy return doggy.

Traditional NFA languages : Perl, Python, Ruby, Java, PHP, JavaScript

POSIX NFA : mawk[3]

DFA vs NFA

Since the DFA engine is deterministic its performance can be bounded by its search set. NFA performance isn't as well defined since, the NFA can roll back on itself to find a less greedy match. Effectively redoing the regular expression search for the less greedy case. Those interesting in the theory and performance differences should review the following page: http://swtch.com/~rsc/regexp/regexp1.html

Regular Expression Support in Programming Languages:

All examples are the same that want to get the month, day and year from the following format (mm-dd-yyyy).

Perl

Perl has built in language support for regular expressions without requiring additional package loads or imports. Regular expression matches and returns are stored in special after match variables that are considered "reserved" variable names ($1, $2... or \1, \2....).

Example

   $date = '01-02-2001'
   $date =~ '(\d\d)-(\d\d)-(\d\d\d\d)'
   $1 => '01'
   $2 => '02'
   $3 => '2001'

Reg Ex Construct	Perl Syntax	Optional Modifier
Match	m/pattern1/pattern2/
Substitution	s/search_pat/replace_pat/	g - multiple replace
Split	split /seperator/, string

Python

Python has built in support via the import of the 're' package that comes standard in the Python installation libraries. Regular expression matches and returns are stored in regular expression objects that are accessed through '.' notation.

Example

   import re
   date = '01-02-2001'
   date_match = re.search(r'(\d\d)-(\d\d)-(\d\d\d\)', date)
   month   = date_match.group(1) => '01'
   day     = date_match.group(2) => '02'
   year    = date_match.group(3) => '2001'

Python allows for regular expressions to be "pre-compiled" at run time through the use of the re.compile() function. "Pre-compiled" regular expressions will exist while they are scoped which can result in a performance increase if the same regex is going to be used multiple times.

Reg Ex Construct	Explanation
match(string)	returns an object if the test string matches regex pattern (\Astring). Not widely used since the match has to match from beginning of the string.
search(string)	returns an regex object if the test string is in the string.
sub(replace_string, string)	returns the string with substituion
split(split_string[, max_split=x])	splits the string based upon the given split_string. Can be bounded by max_split.

Ruby

Ruby has built in language support for regular expressions without addition package loads or imports. Ruby being "Perl but even better"[4] supports Perl style =~ or =! regular expression matches as well as a more OO approach via <string>.match(). Regular expression returns are stored in after match variables as well as in return regular expression objects.

Option 1, use Ruby's version of Perl syntax:

   date = '01-02-2001'
   date =~ '(\d\d)-(\d\d)-(\d\d\d\d)'
   $1 => '01'
   $2 => '02'
   $3 => '2001'

Option 2, use Ruby's OO version of regular expressions by using the STRING objects match method.

   date_match = date.match('(\d\d)-(\d\d)-(\d\d\d\d)')
   month   = date_match[1] => '01'
   day     = date_match[2] => '02'
   year    = date_match[3] => '2001'

Option 3, use Ruby's OO version of regular expressions by using the Regexp object.

   date_match = Regexp.new('(\d\d)-(\d\d)-(\d\d\d\d)')
   date = date_match.match(date)
   month = date[1] => '01'
   day   = date[2] => '02'
   year  = date[3] => '2001'

Like the python re.compile, the use of Regexp.new/compile also scopes the regular expression object for repeated use in code blocks.

JavaScript

JavaScript has support for pattern matching within the String objects or if more advanced features are desired the RegExp object can be utilized. RegEx matches are returned as an array or -1 (-1 indicates no match).

Example:

   var date  = "01-02-2001";
   var regex = new RegExp("(\d\d)-(\d\d)-(\d\d\d\d)");
   var match_array = RegExp.exec(date)
   match_array[1] => '01'
   match_array[2] => '02'
   match_array[3] => '2001'

Java

Java doesn't have built in native support for regular expressions but Sun and others have developed Regular Expression packages that can be imported to allow for regular expression functionality. Since regular expressions are an add-on and Java is strictly typed there is more syntactic overhead to produce a Java based regular expression.

Example:

   PatternObj date_pat = new PatternObj("(\d\d)-(\d\d)-(\d\d\d\d)");
   MatcherObj date_mat = date_pat('01-02-2001');
   date_mat.Group(1)  => '01'
   date_mat.Group(2)  => '02'
   date_mat.Group(3)  => '2001'

PHP

PHP has built in support via the preg() method routine. Regular expression matches are returned in user defined arrays.

Example:

   preg_match('(\d\d)-(\d\d)-(\d\d\d\d)', '01-02-2001', $date_mat)
   $date_mat[1] => '01'
   $date_mat[2] => '02'
   $date_mat[3] => '2001'

Below are some of the regular expressions Characters and support in different languages

Reg Ex Construct	Perl	PHP	Python	Java	Ruby	Java script
Word Character (a-zA-Z)	\w	\w	\w	\w	\w	\w
Non-Word Character	\W	\W	\W	\W	\W	\W
Digit character	\d	\d	\d	\d	\d	\d
Non- digit Chracter	\D	\D	\D	\D	\D	\D
White space character	\s	\s	\s	\s	\s	\s
Non-White space character	\S	\S	\S	\S	\S	\S
Start of string or after newline in multi -line mode	^	^	^	^	^	^
matching end of line	$	$	$	$	$	$
Start of search string in all modes	\A	\A	\A	\A	\A	\A
End of string	\z	\z	\z	\z	\z	\z
End of String before newline	\Z	\Z	\Z	\Z	\Z	\Z
Word boundary (distance between last word character and Non word character)	\b	\b	\b	\b	\b	\b
Non- Word boundary	\B	\B	\B	\B	\B	\B
Matching any single character in bracket	[...]	[...]	[...]	[...]	[...]	[...]
Matching any single character not inside bracket	[^...]	[^...]	[^...]	[^...]	[^...]	[^...]
New line character	\n	\n	\n	\n	\n	\n
Tab character	\t	\t	\t	\t	\t	\t
Form feed	\f	\f	\f	\f	\f	\f
esc character	\e	\e	\e	\e	\e	\e
Octal character	\octal	\octal	\octal	\Ooctal	\octal	\octal
Character specifying one or two digit hexa code	\xhex	\xhex	\xhh	\xhex	-	\xhh
Character specifying 4-digit hexa code	\x{hex}- any hex digit character	\x{hex}-any hexa code	\uhhhh	-	-	\uhhhh
Case insensitive mode	i	i	i	i	i	i
Case match mode	m	m	m	m	m	m
Ignore white space mode	x	x	x	x	x	x
Group sub pattern and capture sub pattern	(...)	(...)	(...)	(...)	(...)	(...)
Match zero or more times or few as possible	*	*	*	*	*	*
Match one or more times or few as possible	+	+	+	+	+	+
Match exactly n times	{n}	{n}	{n}	{n}	{n}	{n}
match n times or more	{n,}	{n,}	{n,}	{n,}	{n,}	{n,}
Positive lookahead	(?=...)	(?=...)	(?=...)	(?=...)	(?=...)	(?=...)
Negative lookahead	(?!...)	(?!...)	(?!...)	(?!...)	(?!...)	(?!...)
Positive look behind	(?<=...)	(?<=...)	(?<=...)	(?<=...)	(?<=...)	(?<=...)
Negative look behind	(?<!...)	(?<!...)	(?<!...)	(?<!...)	(?<!...)	(?<!...)