<p>Some examples of regular languages with practical importance:</p>

<ul>
<li>(reasonable) email adresses (see comments for caveats)</li>
<li>(well-formed) URLs (or even URI in general)</li>
<li>the set of valid identifiers in any HPL</li>
<li>a set of inappropriate words you want to filter from chat/comments/board</li>
<li>the set of TCP headers (I guess)</li>
</ul>

<p>There certainly are many, many more examples; in fact, every time you use regex as a programmer and do not use backreferences/groups (!) you define a regular language for some purpose.</p>

CC BY-SA 3.0
2011-07-17T05:21:00.987Z
The subset of reasonable email addresses are regular.  Full RFC 5321 email recognition is at least as hard as the Dyck language and thus nonregular.
Charles
CC BY-SA 3.0
2011-07-17T10:19:46.823Z
Interesting! Can you please elaborate which feature causes this? Wikipedia claims that email adresses have a maximum length; if that is true, the language is trivially regular (but that is an "artificial" constraint, true).
Raphael
CC BY-SA 3.0
2011-07-17T16:30:50.180Z
That's true, I guess I was talking about what you'd get without the length restriction.  I'll look up my attempt at an RFC 5322 parser tomorrow and see if I can tell you what it was; I can't remember offhand.
Charles
CC BY-SA 3.0
2011-10-08T22:10:54.483Z
@Charles, you seem to have forgotten to get back with the results of checking your parser. Last time I wrote an e-mail address validator based on the RFC the only thing stopping me from making it a single regex was the length the thing would have been - I don't recall any nesting structure.
Peter Taylor
CC BY-SA 3.0
2011-10-08T23:09:55.083Z
@PeterTaylor: [addr-spec in RFC 5322](http://tools.ietf.org/html/rfc5322#section-3.4.1) allows comments in various places, and comments can be nested.  For example, if I am not mistaken, `tsuyoshi.ito @ (this is just an example (so this address does not (probably) exist)) example.com` is a valid addr-spec.  Although this is _not_ what most people would recognize as an email address, those who say “email addresses as defined in RFC cannot be parsed by a regular expression” usually mean this fact.
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-09T03:31:16.337Z
@TsuyoshiIto: Yes, that's precisely what I meant.
Charles
CC BY-SA 3.0
2011-10-09T18:55:17.457Z
@Charles: By the way, addr-spec in RFC 5322 is different from Mailbox in [RFC 5321](http://tools.ietf.org/html/rfc5321#section-4.1.2).  The latter is a regular language unless I am mistaken.
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-09T19:29:27.897Z
@TsuyoshiIto: I agree the two are different.  I'd have to look at 5321 carefully to see if it is regular or not.  But what I was actually thinking about in my Jul 17 comment was 5322.
Charles
CC BY-SA 3.0
2011-07-16T08:58:45.433Z
2011-10-10T05:14:47.480Z
2011-10-10T05:14:47.480Z
Raphael
<p>Most <a href="http://en.wikipedia.org/wiki/Check_digit">check digit</a> algorithms can be implemented as regular expressions. This includes the UPC, EAN, bank routing number, ISBN-13, Luhn, and Verhoef systems described in the linked article, because each of these operates on a single digit of input at a time using a repeating pattern of operations on the digits.</p>

CC BY-SA 3.0
2011-10-09T10:58:44.547Z
This is a nice example! Do you happen to know a web site or text book that gives a fully worked-out example of a regular expression that implements a real-world check digit algorithm? (I tried to do some googling but only found claims that regular expressions cannot be used for this... :)
Jukka Suomela
CC BY-SA 3.0
2011-10-09T17:25:04.247Z
I don't, sorry. It was more a theoretical observation based on the fact that they define regular languages. It might be the case that the corresponding regular expressions are somewhat cumbersome.
David Eppstein
CC BY-SA 3.0
2011-10-09T20:31:39.533Z
I wonder if these languages (and their simpler versions, such as summing all digits modulo something) are also natural examples of regular languages that admit a small and simple state machine, but the smallest regular expression is huge...
Jukka Suomela
CC BY-SA 3.0
2011-10-09T02:18:26.977Z
2011-10-09T02:18:26.977Z
David Eppstein
<p>Regular expressions can parse regular languages. There are many characterizations of regular languages, as witnessed by <a href="http://en.wikipedia.org/wiki/Regular_language" rel="nofollow">the Wikipedia page on regular languages</a> (and you should have looked at it before asking, just like I did before answering). For example, they are precisely those languages that can be expressed by prefix grammars, or regular grammars.</p>

CC BY-SA 3.0
2011-07-15T20:43:39.667Z
Thanks, I did look at that page. I didn't see what I was looking for there.
Eric Wilson
CC BY-SA 3.0
2011-07-15T20:48:12.813Z
Ok, but did you see it when you looked again? It explicitly tells you that regular expressions parse the same family of languages as prefix grammars.
Andrej Bauer
CC BY-SA 3.0
2011-07-15T20:50:29.467Z
it's possible the OP wants "languages in the wild"
Suresh Venkat
CC BY-SA 3.0
2011-07-15T20:52:21.220Z
It's also possible that the OP doesn't know what a prefix grammer is.
Eric Wilson
CC BY-SA 3.0
2011-07-16T08:04:58.030Z
I see. Languages in the wild that can be parsed by regexps: phone numbers, dates, apache web server logs, commands in a text-base adventure game, GPS locations, political slogans that win elections, etc. Not every language has to be complex.
Andrej Bauer
CC BY-SA 3.0
2011-07-15T20:41:21.197Z
2011-07-15T20:41:21.197Z
Andrej Bauer
<p>I see your rant and I raise you a <a href="https://stackoverflow.com/questions/4231382/regular-expression-pattern-not-matching-anywhere-in-string/4234491#4234491">Tom Christiansen contribution</a>.  :-}</p>

<p>I'll take a little license and interpret your question to mean, "Please name some examples where regexes are natural and appropriate."</p>

<p>Small jobs, and in particular one-off jobs, are underappreciated, it seems to me.  Suppose that you have one file to parse (maybe you are screen scraping, or maybe you have a data dump from last year and you need to extract the sixth column if it does not start with "%" or "#").  I use a lot of regexes for that.</p>

<p>Another example of small jobs are URL changers, such as in the config file format for Apache (<a href="http://httpd.apache.org/docs/2.0/mod/core.html#locationmatch" rel="nofollow noreferrer">one of many examples here</a>), or Django's <a href="https://docs.djangoproject.com/en/dev/topics/http/urls/" rel="nofollow noreferrer">urls.py</a>.</p>

CC BY-SA 3.0
2011-07-16T11:43:57.373Z
2011-07-16T11:43:57.373Z
2017-05-23T12:40:09.333Z
Jim Hefferon
<p>I believe (unless I'm mistaken, in which case I would really like somebody to correct my error) that x86 assembly language can be parsed by a regular expression.</p>

<p>Regular expressions are good for searching text (pattern matching). Simple computational problems can also be expressed in terms of finite automata... although most interesting ones cannot.</p>

CC BY-SA 3.0
2011-07-15T20:50:11.540Z
Well, with certain restrictions on addressing modes, perhaps...
aegrisomnia
CC BY-SA 3.0
2011-07-15T20:48:11.740Z
2011-07-15T20:48:11.740Z
aegrisomnia
<p>Many text markup languages are regular or nearly regular:</p>

<p><a href="https://en.wikipedia.org/wiki/Troff" rel="nofollow noreferrer">troff</a>-style markup is regular.</p>

<p>I think <a href="https://cstheory.stackexchange.com/help/formatting">Markdown</a> would be regular if links were always specified inline (as is required in comments).</p>

<p><a href="https://en.wikipedia.org/wiki/Help:Wiki_markup" rel="nofollow noreferrer">Wikipedia markup</a> was regular for a while and still is for the most part.</p>

<p>HTML is mostly regular.  The subset of HTML in which no element may be directly nested or nested within itself is regular, as far as I can see; if this limitation were imposed on today's web, we wouldn't really lose any power.  For sites that work with nested <code>table</code>s or <code>div</code>s, let's allow them to be nested three or four deep.  The resulting restricted HTML describes most (valid) web documents, and it is regular.</p>

<p>What makes using regular expressions for matching fragments of HTML a bad idea is HTML's pervasive reliance on matching pairs to identify subfragments (<em>begin tag - end tag, begin comment - end comment, begin quote - end quote</em>), but only allowing <em>unlimited</em> nesting depth of such pairs makes HTML nonregular, and while HTML allows that, it is often not used and not really needed.</p>

CC BY-SA 3.0
2016-10-19T12:36:36.073Z
It's hard to imagine a modern web site -- using a library like Bootstrap -- without lots of nested `div`s.
Eric Wilson
CC BY-SA 3.0
2016-10-19T13:39:31.427Z
Aren't most of those `div`s generated with JavaScript? I.e. they occur in the DOM tree, but not in the HTML.
reinierpost
CC BY-SA 3.0
2016-10-19T14:11:45.363Z
No. Here is a simple example of Bootstrap HTML: http://getbootstrap.com/components/#panels-heading

The grid stuff is the ubiquitous example: http://getbootstrap.com/css/#grid-example-basic
Eric Wilson
CC BY-SA 3.0
2016-10-20T11:01:32.273Z
Mmm ... indeed, that doesn't look like it's limited to some bounded depth in practice. I've changed my text accordingly.
reinierpost
CC BY-SA 3.0
2016-10-18T22:03:19.197Z
2016-10-20T11:03:09.247Z
2017-04-13T12:32:28.117Z
reinierpost
<blockquote>
  <p>Practically speaking, what are examples of languages or grammars that regex can always parse successfully?</p>
</blockquote>

<p>A short answer is: Probably nothing that you call a language.</p>

<p>In theoretical computer science (TCS), a <em>language</em> simply means a set of words.  But in most cases, what people call a “language” outside TCS has some recursive structure.  “Recursive structure” is ambiguous here, but intuitively regular expressions cannot parse them because regular expressions even cannot parse <a href="http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Use_of_lemma" rel="nofollow noreferrer">balanced parentheses</a>.</p>

<p>Many compilers use regular expressions for <a href="http://en.wikipedia.org/wiki/Lex_%28software%29" rel="nofollow noreferrer">lexical analysis</a> before parsing.  For example, you can decide whether a certain string is a valid identifier in C++ or not by using a regular expression.  This is possible because the language consisting of valid identifiers in C++ is a regular language.  But the set of valid C++ identifiers is usually not called a language outside TCS.</p>

<p>Disclaimers:</p>

<ol>
<li><p><a href="https://cstheory.stackexchange.com/questions/448/regular-expressions-arent">Some people distinguish “regular expression” and “regex.”</a>  In this answer, I am talking about regular expressions, not regexes, if we use this convention.</p></li>
<li><p>Actual C++ compilers do not probably use a regular expression for valid identifiers because excluding keywords makes the regular expression unmanageable.  They use a different technique to cope with this, but that is not the main point here.</p></li>
</ol>

CC BY-SA 3.0
2011-10-08T21:00:04.260Z
@CountablyInfinite: I do not think that your have understood anything I wrote in this answer, and I doubt that you know the usual meaning of the word “language” outside theoretical computer science.  However, if you are happy with downvoting, I do not care.
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-08T21:13:26.647Z
@CountablyInfinite: http://dictionary.reference.com/browse/language
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-08T21:33:59.750Z
@CountablyInfinite: Sigh.  When did _I_ exclude regular languages from languages?  In case it is not clear to you, I know the definition of the term “language” in TCS (as I wrote in this answer).  Unlike you, I also know what many people outside TCS mean by “language.”  Because of this, I understood why Eric Wilson asked this question in the way he asked.  Explaining the difference in the terminology inside and outside TCS hopefully resolved his confusion, which is what I did in this answer.
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-15T22:00:15.577Z
2011-07-15T22:00:15.577Z
2017-04-13T12:32:28.080Z
Tsuyoshi Ito
<p>If you ask a question about parsing HTML with regex, you will certainly be referenced to this famous <a href="https://stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732454#1732454">rant</a>. Though there is not a canonical rant for it, I've also been told that regex aren't powerful enough to parse SQL.</p>

<p>I'm a self-taught programmer, so I don't know much about languages from a theoretical perspective. Practically speaking, what are examples of languages or grammars that regex can always parse successfully?</p>

<p><strong>Edit:</strong> To clarify, I'd really like a few examples of languages that are used in the real world that fit in the category of regular languages, rather than some axioms or equivalent conditions, etc.</p>

CC BY-SA 3.0
2011-07-16T00:44:13.273Z
Your problem is ill defined: What are you allowed to do beside applying regex? You only get a linear list of strings from regex. That is far far away from a parse tree without doing some additional work. If that work is done by a Turing machine, then I claim all programming languages can be "parsed" with a regex that returns the entire string.
Chao Xu
CC BY-SA 3.0
2011-07-17T02:21:06.960Z
@ChaoXu I'm looking for languages in which regex can do whatever it is that you _can't_ do with regex and HTML.
Eric Wilson
<fl.formal-languages><regular-expressions><regular-language>
What are regular expressions good for?
Eric Wilson
# What are regular expressions good for?

(Asked by: username_0 on 2011-07-15)

If you ask a question about parsing HTML with regex, you will certainly be referenced to this famous [rant](https://stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732454#1732454). Though there is not a canonical rant for it, I've also been told that regex aren't powerful enough to parse SQL.

I'm a self-taught programmer, so I don't know much about languages from a theoretical perspective. Practically speaking, what are examples of languages or grammars that regex can always parse successfully?

**Edit:** To clarify, I'd really like a few examples of languages that are used in the real world that fit in the category of regular languages, rather than some axioms or equivalent conditions, etc.

**Tags:** fl.formal-languages, regular-expressions, regular-language

> **Comments:**
> **username_1**: Your problem is ill defined: What are you allowed to do beside applying regex? You only get a linear list of strings from regex. That is far far away from a parse tree without doing some additional work. If that work is done by a Turing machine, then I claim all programming languages can be "parsed" with a regex that returns the entire string.  
> **username_0**: @ChaoXu I'm looking for languages in which regex can do whatever it is that you _can't_ do with regex and HTML.  

---

## 7 answers

### Answer by username_5 on 2011-07-15. Score: 23 | Accepted answer

> Practically speaking, what are examples of languages or grammars that regex can always parse successfully?

A short answer is: Probably nothing that you call a language.

In theoretical computer science (TCS), a *language* simply means a set of words. But in most cases, what people call a “language” outside TCS has some recursive structure. “Recursive structure” is ambiguous here, but intuitively regular expressions cannot parse them because regular expressions even cannot parse [balanced parentheses](http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Use_of_lemma).

Many compilers use regular expressions for [lexical analysis](http://en.wikipedia.org/wiki/Lex_%28software%29) before parsing. For example, you can decide whether a certain string is a valid identifier in C++ or not by using a regular expression. This is possible because the language consisting of valid identifiers in C++ is a regular language. But the set of valid C++ identifiers is usually not called a language outside TCS.

Disclaimers:

1. [Some people distinguish “regular expression” and “regex.”](https://cstheory.stackexchange.com/questions/448/regular-expressions-arent) In this answer, I am talking about regular expressions, not regexes, if we use this convention.
2. Actual C++ compilers do not probably use a regular expression for valid identifiers because excluding keywords makes the regular expression unmanageable. They use a different technique to cope with this, but that is not the main point here.

> **Comments:**
> **username_5**: @CountablyInfinite: I do not think that your have understood anything I wrote in this answer, and I doubt that you know the usual meaning of the word “language” outside theoretical computer science.  However, if you are happy with downvoting, I do not care.  
> **username_5**: @CountablyInfinite: http://dictionary.reference.com/browse/language  
> **username_5**: @CountablyInfinite: Sigh.  When did _I_ exclude regular languages from languages?  In case it is not clear to you, I know the definition of the term “language” in TCS (as I wrote in this answer).  Unlike you, I also know what many people outside TCS mean by “language.”  Because of this, I understood why username_0 asked this question in the way he asked.  Explaining the difference in the terminology inside and outside TCS hopefully resolved his confusion, which is what I did in this answer.  

---

### Answer by username_2 on 2011-07-16. Score: 13

Some examples of regular languages with practical importance:

* (reasonable) email adresses (see comments for caveats)
* (well-formed) URLs (or even URI in general)
* the set of valid identifiers in any HPL
* a set of inappropriate words you want to filter from chat/comments/board
* the set of TCP headers (I guess)

There certainly are many, many more examples; in fact, every time you use regex as a programmer and do not use backreferences/groups (!) you define a regular language for some purpose.

> **Comments:**
> **username_3**: The subset of reasonable email addresses are regular.  Full RFC 5321 email recognition is at least as hard as the Dyck language and thus nonregular.  
> **username_2**: Interesting! Can you please elaborate which feature causes this? Wikipedia claims that email adresses have a maximum length; if that is true, the language is trivially regular (but that is an "artificial" constraint, true).  
> **username_3**: That's true, I guess I was talking about what you'd get without the length restriction.  I'll look up my attempt at an RFC 5322 parser tomorrow and see if I can tell you what it was; I can't remember offhand.  
> **username_4**: @username_3, you seem to have forgotten to get back with the results of checking your parser. Last time I wrote an e-mail address validator based on the RFC the only thing stopping me from making it a single regex was the length the thing would have been - I don't recall any nesting structure.  
> **username_5**: @PeterTaylor: [addr-spec in RFC 5322](http://tools.ietf.org/html/rfc5322#section-3.4.1) allows comments in various places, and comments can be nested.  For example, if I am not mistaken, `tsuyoshi.ito @ (this is just an example (so this address does not (probably) exist)) example.com` is a valid addr-spec.  Although this is _not_ what most people would recognize as an email address, those who say “email addresses as defined in RFC cannot be parsed by a regular expression” usually mean this fact.  
> **username_3**: @TsuyoshiIto: Yes, that's precisely what I meant.  
> **username_5**: @username_3: By the way, addr-spec in RFC 5322 is different from Mailbox in [RFC 5321](http://tools.ietf.org/html/rfc5321#section-4.1.2).  The latter is a regular language unless I am mistaken.  
> **username_3**: @TsuyoshiIto: I agree the two are different.  I'd have to look at 5321 carefully to see if it is regular or not.  But what I was actually thinking about in my Jul 17 comment was 5322.  

---

### Answer by username_6 on 2011-10-09. Score: 6

Most [check digit](http://en.wikipedia.org/wiki/Check_digit) algorithms can be implemented as regular expressions. This includes the UPC, EAN, bank routing number, ISBN-13, Luhn, and Verhoef systems described in the linked article, because each of these operates on a single digit of input at a time using a repeating pattern of operations on the digits.

> **Comments:**
> **username_7**: This is a nice example! Do you happen to know a web site or text book that gives a fully worked-out example of a regular expression that implements a real-world check digit algorithm? (I tried to do some googling but only found claims that regular expressions cannot be used for this... :)  
> **username_6**: I don't, sorry. It was more a theoretical observation based on the fact that they define regular languages. It might be the case that the corresponding regular expressions are somewhat cumbersome.  
> **username_7**: I wonder if these languages (and their simpler versions, such as summing all digits modulo something) are also natural examples of regular languages that admit a small and simple state machine, but the smallest regular expression is huge...  

---

### Answer by username_8 on 2011-07-15. Score: 3

Regular expressions can parse regular languages. There are many characterizations of regular languages, as witnessed by [the Wikipedia page on regular languages](http://en.wikipedia.org/wiki/Regular_language) (and you should have looked at it before asking, just like I did before answering). For example, they are precisely those languages that can be expressed by prefix grammars, or regular grammars.

> **Comments:**
> **username_0**: Thanks, I did look at that page. I didn't see what I was looking for there.  
> **username_8**: Ok, but did you see it when you looked again? It explicitly tells you that regular expressions parse the same family of languages as prefix grammars.  
> **username_9**: it's possible the OP wants "languages in the wild"  
> **username_0**: It's also possible that the OP doesn't know what a prefix grammer is.  
> **username_8**: I see. Languages in the wild that can be parsed by regexps: phone numbers, dates, apache web server logs, commands in a text-base adventure game, GPS locations, political slogans that win elections, etc. Not every language has to be complex.  

---

### Answer by username_10 on 2011-07-16. Score: 3

I see your rant and I raise you a [Tom Christiansen contribution](https://stackoverflow.com/questions/4231382/regular-expression-pattern-not-matching-anywhere-in-string/4234491#4234491). :-}

I'll take a little license and interpret your question to mean, "Please name some examples where regexes are natural and appropriate."

Small jobs, and in particular one-off jobs, are underappreciated, it seems to me. Suppose that you have one file to parse (maybe you are screen scraping, or maybe you have a data dump from last year and you need to extract the sixth column if it does not start with "%" or "#"). I use a lot of regexes for that.

Another example of small jobs are URL changers, such as in the config file format for Apache ([one of many examples here](http://httpd.apache.org/docs/2.0/mod/core.html#locationmatch)), or Django's [urls.py](https://docs.djangoproject.com/en/dev/topics/http/urls/).


---

### Answer by username_11 on 2011-07-15. Score: 1

I believe (unless I'm mistaken, in which case I would really like somebody to correct my error) that x86 assembly language can be parsed by a regular expression.

Regular expressions are good for searching text (pattern matching). Simple computational problems can also be expressed in terms of finite automata... although most interesting ones cannot.

> **Comments:**
> **username_11**: Well, with certain restrictions on addressing modes, perhaps...  

---

### Answer by username_12 on 2016-10-18. Score: 1

Many text markup languages are regular or nearly regular:

[troff](https://en.wikipedia.org/wiki/Troff)-style markup is regular.

I think [Markdown](https://cstheory.stackexchange.com/help/formatting) would be regular if links were always specified inline (as is required in comments).

[Wikipedia markup](https://en.wikipedia.org/wiki/Help:Wiki_markup) was regular for a while and still is for the most part.

HTML is mostly regular. The subset of HTML in which no element may be directly nested or nested within itself is regular, as far as I can see; if this limitation were imposed on today's web, we wouldn't really lose any power. For sites that work with nested `table`s or `div`s, let's allow them to be nested three or four deep. The resulting restricted HTML describes most (valid) web documents, and it is regular.

What makes using regular expressions for matching fragments of HTML a bad idea is HTML's pervasive reliance on matching pairs to identify subfragments (*begin tag - end tag, begin comment - end comment, begin quote - end quote*), but only allowing *unlimited* nesting depth of such pairs makes HTML nonregular, and while HTML allows that, it is often not used and not really needed.

> **Comments:**
> **username_0**: It's hard to imagine a modern web site -- using a library like Bootstrap -- without lots of nested `div`s.  
> **username_12**: Aren't most of those `div`s generated with JavaScript? I.e. they occur in the DOM tree, but not in the HTML.  
> **username_0**: No. Here is a simple example of Bootstrap HTML: http://getbootstrap.com/components/#panels-heading  The grid stuff is the ubiquitous example: http://getbootstrap.com/css/#grid-example-basic  
> **username_12**: Mmm ... indeed, that doesn't look like it's limited to some bounded depth in practice. I've changed my text accordingly.  

---

