Regular Expression in both Python and Perl

Regular expressions

I would like to share some highlights of my past experience that connected to Regular Expressions. It is a summary or quick reference that will help you to use regular expressions in your duties.

Let me start with a brief explanation what we could use in Python.

Python programming language has the re API. 
Those functions from the API are used widely:

• compile - this function compile expression and result could be used later in your program. So, you could improve performance of your program if this regular expression is used very often, just by reducing costs on compilation.
• search - with this function you will be able to find first occurrence of the expression in your text.
• match - this function tries to match the string to the regular expression starting from the beginning of the string. 
• findall - this function returns all matches in the string.

Comparing to Python, Perl has no special API, or, let's call it - library, you could use regular expressions inside your program or script by using special syntax.

Basic syntax

What we should know about regex basics:

• ^ - marker that notifies a regex engine to start search from the beginning of the string.
• $ - marker that notifies a regex engine to end search with the end of the string.
• . - dot in regular expressions means any kind of symbols except a newline.
• | - this symbol works like logical OR operator, it allows us to use different alternate variants that could occurs in particular position.
• ( and ) - round brackets are used as borders for operations that includes the OR symbol | or in grouping operations.

Character classes

Character classes are used to define set of characters, and only one of them should be in particular position to match regular expression. The square brackets [ and ] is used for this purpose. Regular expressions support definition of a range of symbols, using dash between first symbol and last symbol, as well as using ^ symbol to denote that any symbols, except those, that were defined in set, should be in this position to satisfy regular expression.

Quantifiers

On this step we already know how we can describe a symbol in certain position.

What will be in case if we would like to check this behavior across neighborhoods of the symbol?

For this purpose we can use quantifiers:

• ? - means that particular symbol or expression (remember, we can use round brackets for grouping) is optional and is not required to be in checked string to satisfy to regular expression.
• * - means that particular symbol or expression can occurs 0 or more times in a row.
• + - means that particular symbol or expression can occurs 1 or more times in a row, so, it means that it definitely should be in this place to satisfy to regular expression.
• { and } - curly brackets, it is last type of brackets that we didn't talk about till this time. This type of brackets is used to define an interval, that includes possible occurrence of particular symbol or expression to match to regular expression. Value can be a single number like this: {amount} (it means that particular expression should occurs exactly this number of times in a row) or it can be a range in format: {left, right}, where both borders are inclusive (in this case occurrence should lay in this range to match the regular expression).

Escaping

Definition of such set of special symbols (and it is only a basics!) raises a constraint or a question: "What we should do, if string, that should be processed, contains one or more of them?". For this case the escaping mechanism could be used. Several approaches can be used if we are talking about the Python programming language:

• First one is related to using \ symbol, to inform regular expression processor that symbol followed by should not be recognized as a special one. But, it doesn't work within [ ] range.
• Second one is related to using of Python's raw strings. This approach is related to putting the r symbols before the string to notify interpreter that it is a raw string. In this case any kind of combinations like r'\n' will be interpreted as two different symbols '\' and 'n', not like a special symbol '\n'.
• Third one is related to usage of functionality of regular expression in Python, in details it is re.escape function.

Shorthands

In real life a lot of different types or classes of symbols, like english alphabet, digits, symbols for punctuation and so on. Several of such classes can be specified by using \ symbol that followed by a one special symbol or abbreviation. Those classes are:

• Special characters (mostly used):

• \t - symbol of tabulation.
• \r - carriage return.
• \n - new line.

• Ranges of characters:

• \s - space symbols or shortcut for range [ \t\r\n\f\v].
• \S - all symbols except space symbols. This range can be described as [^ \t\r\n\f\v] or [^\s].
• \w - alphabetic symbols that can be covered by following range [a-zA-Z0-9_].
• \W - non-alphabetic symbols. The same analogue that can be noticed with \s and \S, range of symbols are [^a-zA-Z0-9_].
• \d and \D it is a range that includes numbers from 0 to 9 inclusively and range which include all symbols, except numbers.

• Special indicators:
• \b - this symbol is used to match boundary of the word. The word is a set of characters from group \w, so, \b points to a border between \w and \W, as well as point between start of the string and \w and end of the string and \w.
• \B - this symbol is opposite to \b 

Modes

Several modes can be applied to improve flexibility of regular expressions:

• i - ignore case.
• g - continue search after the moment when first occurrence found and returned.
• m - multiline mode.
• x - spaces and text after symbol # will be ignored, like a comments in regular expressions.
• s - the . symbol will satisfy to any symbols, as well as symbol of new line.

In Python those modes are part of the re module and has two versions - short and long. For example mode to ignore case of letters can be used in following ways: re.I and re.IGNORECASE. This mode should be used as a second parameter of the compile function.

Backreference and Grouping

The grouping is useful when we would like to get more details from the match or decrease a size of regular expression. Such king of capturing calls as grouping. Round brackets ( ) are used for such purpose. Please note, that if round brackets are part of the expression, so, they should be escaped.

Index of the group is important if we what to get access to this group, make that, to information that matches to this group. Index is calculated very easily: if we consider the regular expression as a tree with full expression as a root, and groups as nodes and leaves, so the index of the group is the index of a node or a leave during the DFS (Depth First Search). Let's consider following example:

regular expression: (exp1 (exp2) exp3 (exp4)) exp5 (exp6 (exp7))
group 0: exp1 exp2 exp3 exp4 exp5 exp6 exp7
group 1: exp1 exp2 exp3 exp4
group 2: exp2
group 3: exp4
group 4: exp6 exp7
group 5: exp7

In some cases index of a group is useless to identification. Regular expressions has capability to add special labels or names to identify particular group. Syntax of group's definition is changed to the following (?P<name_or_label>expression). Please notice, that symbol P is highlighted, the reason why I did that is: this symbol is important when we are working with Python but can be omitted in Perl. Perl supports both cases: with symbol P and without it.

It is time to talk about the backreference. It is a useful capability to check that different part of the expression has the same value. It can be the check that the same year is used across the document or the same person is mentioned in different locations of a contract. To check that it is possible to mark one group that matches to particular text and use it to check that the same text in other places. Syntax of such functionality might be different and depends on language.
Python: (?P=name) for groups that has names; \index - for group that can be accessed via index
Perl: \k<name> for named groups; \gindex or \g{index} - for group that can be accessed via index; \g{-shift} or \g-shift - reference to group the occurred previously (shift steps before)

Additional and important case is related to situation when groups are used widely in regular expression and it is a good if groups that has useless information has no index, so, access via index will be only for groups with useful details or data. The following syntax of group's definition is used in this case (?:expression).

Search & Replace

The search (re.search) behavior is differ from match (re.match) behavior in Python (link), and the difference is that match start comparison from the beginning but search from a position in the string, just to be able to identify a match into the string. This behavior is default for Perl, so, it was the reason why I started all my expression previously with symbol ^.
The replace functionality is covered by function re.sub in Python and expression s/<expression_to_find>/<text_to_replace_with>/.

Lookaround

It can be required to check that sub-part of regular expression is located before or after particular position in checked string. For that purpose regular expression has feature of lookahead and lookbehind. If it is required to check that specific text occurs before the position we should use positive lookbehind feature: (?<=expression)another_expression. In this case to satisfy match, a text that satisfy to expression must occurs before a text that satisfy to another_expression. The same analogue of positive lookahead feature; it can be described as another_expression(?=expression). In this case, match will be successful only when a text in the position is matched to another_expression and after that text must match to the expression. Both features are positive lookarounds, but regular expressions has features to check or match negative lookarounds: it is negative lookahead and negative lookbehind. Templates for those features are: another_expression(?!expression) for negative lookahead and (?<!expression)another_expression for negative lookbehind.

Note:  Lookbehinds at Python needs to be fixed-width, and so you have to avoid alternations in a lookbehind pattern that are of different length.

Compilation

Both Python and Perl supports compilation of regular expressions. It is important if you will use this regular expression more than one time. Before processing of regular expression the regular expression routine will compile the expression to special object and use it to match the string. So, it is very useful to use such technique to increase performance of your application.
In Python you should use the re.compile function to do that, in Perl, when you define the regular expression, you should use the qr sequence before it.
The benefit from compilation is depends on regular expression itself. Here is just one of examples that I used to catch the speed-up.
Consider following regular expression: 'with (a|an|the|this) ' and compiled version regex_compiled = compile(regex_str)
Let's try to identify all matches of this expression in text of rfc793 (https://tools.ietf.org/html/rfc793).
The program reads the text line by line and tries to match the string and eventually it should be about 38 matches across 5248 lines. To identify those matches both functions perform_match_with_compile_regexp and perform_match_with_string_regexp was used. Detailed description can be found on my GitHub account - link
A few additional details about the implementation:

1. To track the execution time the timeit module has been used. 
2. Number of executions of the main method has been taken from the range [10, 50, 100, 250, 500, 750, 1000].
3. Number of iterations to calculate the average is 10.

Result of the execution is on the following graph:

As we can see for this particular example improvement is about 3x.

Raw data from the experiment can be found  by this link.

Start of match

This functionality is available in Perl, in details you can read it here, in perldoc. In few words, this option is allows you to start next match on the same string where the latest match were finished.

Mode modifier

As it was mentioned before, several modes can be apply to regular expression. But it is possible to apply several of them only to selected part of regular expression. Such modes are i, m, s, x. Description of them can be found in special section above. This feature is possible to use with combination (?mode:expression). Of course, if it is possible to apply a modifier on a part of string, it should be possible to turn off a global mode on a part of regular expression, it can be done with following syntax (?-mode:expression).  
There is one additional feature that exists in both Perl and Python but has different meaning:

• Perl allows to turn on/off usage of a mode till end of the regular expression. Both expressions (?mode) to turn on and (?-mode) to turn off should be used for that purpose.
• The same options in Python is used without subexpression - they will be applied to whole expression! For the purpose such flags should be placed at the beginning of the regular expressions, otherwise result is undefined.

Atomic grouping

This sort of grouping is used to prevent look back to another attempt to identify the match, even if it is not possible to find a match with rest of expression. The following syntax is used for that purpose: (?>expression). This syntax is supported in Perl, but in Python it is possible to get the same effect by following expression: (?>expression) is equals to (?=(expression))\n, where \n is a particular group that matches to expression.
If we consider a quantors where a difficult grouping is not required, the same effect is reached by adding a + sign after the quantor, for example, for quantors *, +, ?, {number, number}, the expression will be looks like that: *+, ++, ?+, {number, number}+.
The purpose of that capability is to reduce the time that will be required to identify match and as a result to improve performance.

Conditional

Regular expressions provides capability to choose the regular expression with dependency on previous matched subexpression. The syntax for this functionality is (?(expression)regex_true|regex_false) - this expression is an equivalent of if-then-else expression; and (?(expression)regex_true) - this expression is an equivalent of if-then expression. expression in this syntax is back reference to previous expression.

Lazy quantifiers

One of the first topics in this article was related to quantifiers, symbols or combination of symbols like *, +, ?, {number, number}.  The purpose of these quantifiers is to define how many times an expression should appears in processed string, like a string of joined substrings where each substring is matched to the expression. Those quantifiers are executed as much time as possible in the sentence, but regular expression engine also looks back to have successful match of full expression. As a result, name of such quantifiers is greedy quantifiers. Regular expression engine allows us to mark cases when it is required to execute such quantifiers as less time as possible: to do that the special mark ? should be placed after the quantifier: *?, +?, ??, {number, number}?.

Books / Articles / Sites

1. Regular Expression Pocket Reference, 2nd Edition (link) - short and sweet reference. This book helped me a lot with preparing of simple regular expressions.
2. Programming Perl, 4th Edition (link) - of course, this book about Perl, but it also contains an article about regular expressions, so, you can find it useful or double useful if your duties connects with Perl. I read this book and it helped me with one of my tasks that was connected to regular expressions and Perl.
3. Regular Expressions from Princeton University (link)
4. My favorite site where we can 'play' with regular expressions and see detailed results - https://regex101.com/ but you can also use this one http://www.regexpal.com/
5. Mastering Regular Expressions, 3rd Edition (link) - very good book if you would like to go in details of the regular expressions.
6. You may also enjoy by this course from CodeSchool - https://www.codeschool.com/courses/breaking-the-ice-with-regular-expressions
7. HackerRank challenges: https://www.hackerrank.com/domains/regex/re-introduction
8. Stepik.org course prepared by me available here. You need to register to participate :-)