28
$\begingroup$

I am looking for some interesting applications of regular expressions.

Can you name any unusual, or unobvious, cases where regexes find their application?

$\endgroup$
  • 1
    $\begingroup$ They're not regular, but finite state transducers can be used to generate and recognize complicated morphology, such as Finnish numerals. $\endgroup$ – phipsgabler May 7 at 7:31
  • 4
    $\begingroup$ Testing divisibility of integers $\endgroup$ – Griffin May 7 at 14:03
  • 1
    $\begingroup$ @griffin you should make an answer out of your comment $\endgroup$ – melfnt May 7 at 16:11
  • 3
    $\begingroup$ Follow the regex tag on Stack Overflow and you'll find a constant stream of unusual and unobvious (not to mention inadvisable) cases. $\endgroup$ – chrylis -cautiouslyoptimistic- May 7 at 17:12
  • 2
    $\begingroup$ Parsing HTML $\endgroup$ – badroit May 8 at 3:51

11 Answers 11

40
$\begingroup$

I don't know if this question belongs here (the answer could be subjective and depend on your definition of "unusual") but here is my favorite unusual application of regex:

converting T9 input (2-9) to English text.

For example if the user wants to write hello they presses 42556. Convert the input to [ghi][def][jkl][jkl][mno] and test this regex against the whole vocabulary: the word hello will match.

| cite | improve this answer | |
$\endgroup$
  • 10
    $\begingroup$ @chrylis-onstrike- I think you would be far better off performance-wise by doing the converse, i.e. building a DFA (≈ trie) out of the whole dictionary mapped to T9 keys and then running the T9 input against that to see what state you end up in. $\endgroup$ – Aaron Rotenberg May 7 at 17:48
  • 4
    $\begingroup$ I can't imagine the phone which used T9 input and would have the processing power to do this in a reasonable time. $\endgroup$ – Michael Hampton May 8 at 4:40
  • $\begingroup$ Why were my comments and the one by @chrylis-on-strike- deleted? $\endgroup$ – melfnt May 10 at 7:12
17
$\begingroup$

From this page, here's a regex for validating an RFC822-compliant email address

(?:(?:\r\n)?[ \t])*(?:(?:(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t]
)+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:
\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(
?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ 
\t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\0
31]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\
](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+
(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:
(?:\r\n)?[ \t])*))*|(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z
|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)
?[ \t])*)*\<(?:(?:\r\n)?[ \t])*(?:@(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\
r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[
 \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)
?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t]
)*))*(?:,@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[
 \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*
)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t]
)+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*)
*:(?:(?:\r\n)?[ \t])*)?(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+
|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r
\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:
\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t
]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031
]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](
?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?
:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?
:\r\n)?[ \t])*))*\>(?:(?:\r\n)?[ \t])*)|(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?
:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?
[ \t]))*"(?:(?:\r\n)?[ \t])*)*:(?:(?:\r\n)?[ \t])*(?:(?:(?:[^()<>@,;:\\".\[\] 
\000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|
\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>
@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"
(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t]
)*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\
".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?
:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[
\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*|(?:[^()<>@,;:\\".\[\] \000-
\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(
?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)*\<(?:(?:\r\n)?[ \t])*(?:@(?:[^()<>@,;
:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([
^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\"
.\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\
]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*(?:,@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\
[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\
r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] 
\000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]
|\\.)*\](?:(?:\r\n)?[ \t])*))*)*:(?:(?:\r\n)?[ \t])*)?(?:[^()<>@,;:\\".\[\] \0
00-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\
.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,
;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?
:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*
(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".
\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[
^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]
]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*\>(?:(?:\r\n)?[ \t])*)(?:,\s*(
?:(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\
".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(
?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[
\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t
])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t
])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?
:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|
\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*|(?:
[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\
]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)*\<(?:(?:\r\n)
?[ \t])*(?:@(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["
()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)
?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>
@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*(?:,@(?:(?:\r\n)?[
 \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,
;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t]
)*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\
".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*)*:(?:(?:\r\n)?[ \t])*)?
(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".
\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:
\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\[
"()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])
*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])
+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\
.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z
|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*\>(?:(
?:\r\n)?[ \t])*))*)?;\s*)

The original definition is a context-free grammar, hence the unwieldy regex

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ "The original definition is a context-free grammar, hence the unwieldy regex" Could you expand on that? I'm curious. $\endgroup$ – user76284 May 8 at 5:36
  • 1
    $\begingroup$ If it's a context-free grammar, doesn't that mean there would still be cases that are valid according to the grammar but can't be matched by the regular expression? $\endgroup$ – kutschkem May 8 at 8:43
  • 4
    $\begingroup$ @kutschkem: It's not a regular expression, it's a regex. Regexes are much more powerful than regular expressions. Depending on the flavor, I wouldn't be surprised to find out they are Turing-complete modulo resource limits in the engine. E.g. there are regex flavors that have named subgroups, recursion, and choice. $\endgroup$ – Jörg W Mittag May 8 at 9:10
  • 2
    $\begingroup$ @kutschkem if you read the page you'll find that the one thing that got changed is that nested comments aren't supported. Apparently everything else is a regular language that the RFC expressed as a CFG. $\endgroup$ – ratchet freak May 8 at 10:11
13
$\begingroup$

Again, I don't know how unusual it is, but Paul Heckbert introduced regular expressions in path tracing to distinguish the light transport paths that various algorithms can correctly solve.

| cite | improve this answer | |
$\endgroup$
12
$\begingroup$

How about fighting cancer with the power of regex?

https://www.sciencedirect.com/science/article/pii/S2352914819303120

Title: Regular expression based pattern extraction from a cell - Specific gene expression data

Abstract: Cancer cells are formed when active genes stop functioning properly. Timely activation of a gene is governed through the combined effort of multiple Transcription Factors (TFs). TFs are proteins that bind on DNA in a sequence-specific manner. It is difficult to trace the target and role of TFs in the gene regulation process. The same element acts differently in different places, similar to the way the same word has a different meaning in a different context. This approach treats the cell line in a language context, whereas the genes and TFs are the symbols or letters of the language. Different combination of symbols forms a sequence with repetitive patterns. Identifying and analysing such frequently occurring patterns will give a better insight into the cell. This work mainly aims to identify such patterns found in the cell line using regular expression technique. The patterns generated in this work can be chosen as a feature for identifying the effect of regulatory elements in the genomic region. For improving readability identity of each character present in the pattern is documented in the form of a text file. Acute Myeloid Leukaemia (AML) data from GEO repository and the related two TFs binding narrow peak data, calibrated in K562 cell line from ENCODE consortium are taken as a case study.

| cite | improve this answer | |
$\endgroup$
11
$\begingroup$

A simple PCRE expression (not exactly an regular expression, this one includes a +?) can say if an unary number is non-prime (so when it doesn't match, the unary number is prime): http://stackoverflow.com/questions/3296050/ddg#3296068

edit: thanks to @Pseudonym to point out that expresion was PCRE and not ERE or RE

| cite | improve this answer | |
$\endgroup$
  • 14
    $\begingroup$ PCRE accepts more languages than regular expressions. Exercise: Show that regular expressions cannot find prime numbers. (Hint: Use the pumping lemma.) $\endgroup$ – Pseudonym May 7 at 1:00
  • 2
    $\begingroup$ @Pseudonym : you may be right, I thought it could be just rewritten without the perl syntax as an ERE but the (11+?) part may be pcre only $\endgroup$ – Olivier Dulac May 7 at 9:16
  • 1
    $\begingroup$ FYI: codegolf.stackexchange.com/questions/19262/… $\endgroup$ – nhahtdh May 8 at 7:56
  • 1
    $\begingroup$ Also +? in the prime checking regex doesn't make the regex not "regular" (in CS term). The thing that makes the regex non-"regular" is the backreference \1 $\endgroup$ – nhahtdh May 11 at 3:41
7
$\begingroup$

One of the best ones I've seen using regex is to 'shift a number right by half a bit', i.e. to divide a number by $\sqrt 2$ and return the closest integer! Take a look at @Deadcode's Code Golf answer here.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

It's debatable whether it's "unusual", since it's a classic Unix program, but Lex is probably not the first think people imagine when they think of Regexes.

Lex (or the newer variant, Flex) uses regular expressions for tokenization, in something like a compiler or interpreter. So you have one regular expression for matching strings, one for integers, one for the if token, etc.

Matching things like this with regular expressions doesn't seem that unusual. But the interesting part is what's done with them. The regular expressions are combined by Lex into a single minimal DFA for matching all of the tokens, and a representation of this DFA is written to a C file.

So multiple regular expressions are turned into one DFA, and minimized, at compile time.

The compiler's code can then invoke the generated lexer to retrieve the next token from a string of source code, which can then be parsed into a hierarchical structure (a related tool called Yacc can be used for that).

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Actually, (f)lex IS the first thing I think of when I think of regular expressions :-) Perhaps the oddest thing I've used it for was a solution to the 2D water fill problem. $\endgroup$ – jamesqf May 7 at 16:25
2
$\begingroup$

As an example of regular expressions not applied to strings, regular path queries (RPQs) are essentially regular expressions on paths that are widely used in the context of graph queries.

Need to find ancestors in a graph query language like SPARQL? You can write

?x (:mother|:father)* ?y

This will return all pairs of nodes in a directed edge-labelled graph where the edge labels on the path match the regular expression (:mother|:father).

Similar regular-expression-like patterns are used in popular graph databases, like Neo4j.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

You can use regular expressions to define a kind of constraint on the types of the leaves of a data structure. The example pictured below is a binary tree which, when traversed from left to right, yields a sequence of elements of type b, followed by a leaf with no data, followed by leaves of type a. We can describe this with a regular expression like b*1a*. There is now a procedure for converting the original tree type, and the regular expression, into a tree type constrained by the regexp. A special case is the example of zippers.

You can read a bit about it here and a paper giving the details is Polynomial Functors Constrained by Regular Expressions.

Briefly: the transition matrix for the regular expression is reinterpreted as a bunch of "simultaneous" equations defining a collection of types through mutual recursion. For example, the tree pictured might be defined in Haskell like so:

data Tree11 a b  =  Leaf11 a
                 |  Fork11  (Tree12 a b)  (Tree11 a b)
                 |  Fork11' (Tree11 a b)  (Tree21 a b)
data Tree22 a b  =  Leaf22 b
                 |  Fork22  (Tree22 a b)  (Tree12 a b)
                 |  Fork22' (Tree21 a b)  (Tree22 a b)
data Tree21 a b  =  Fork21  (Tree22 a b)  (Tree11 a b)
                 |  Fork21' (Tree21 a b)  (Tree21 a b)

The three definitions here correspond to entries in the transition matrix of the finite state machine recognising b*1a*.

Dissected Tree

(By the way, this particular example can be thought of as representing the intermediate state of a recursive algorithm to walk the tree converting b's to a's. Normally in such a recursive algorithm, the stack "keeps track" of where you are. But by making your current state explicit like this it allows you to remove the dependence on the stack and rewrite the algorithm with tail-recursion.)

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Raku (formerly known as Perl 6) parses raku scripts with Perl 6 regular expressions which directly outputs an AST, used by the interpreter. This means that modules in raku can modify the grammar of the language itself.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Test if a positive integer is a multiple of 3:

^([0369]|[258][0369]*[147]|[147]([0369]|[147][0369]*[258])*[258]|[258][0369]*[258]([0369]|[147][0369]*[258])*[258]|[147]([0369]|[147][0369]*[258])*[147][0369]*[147]|[258][0369]*[258]([0369]|[147][0369]*[258])*[147][0369]*[147])*$

Original article: https://www.quaxio.com/triple/

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.