6
$\begingroup$

If you ask a question about parsing HTML with regex, you will certainly be referenced to this famous rant. 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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Chao Xu
    Commented Jul 16, 2011 at 0:44
  • 1
    $\begingroup$ @ChaoXu I'm looking for languages in which regex can do whatever it is that you can't do with regex and HTML. $\endgroup$
    – Eric Wilson
    Commented Jul 17, 2011 at 2:21

7 Answers 7

Reset to default
23
$\begingroup$

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.

Many compilers use regular expressions for lexical analysis 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.” 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Commented Oct 8, 2011 at 21:00
  • $\begingroup$ @CountablyInfinite: dictionary.reference.com/browse/language $\endgroup$
    – Tsuyoshi Ito
    Commented Oct 8, 2011 at 21:13
  • 5
    $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Commented Oct 8, 2011 at 21:33
13
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ 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. $\endgroup$
    – Charles
    Commented Jul 17, 2011 at 5:21
  • $\begingroup$ 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). $\endgroup$
    – Raphael
    Commented Jul 17, 2011 at 10:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Charles
    Commented Jul 17, 2011 at 16:30
  • $\begingroup$ @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. $\endgroup$
    – Peter Taylor
    Commented Oct 8, 2011 at 22:10
  • 7
    $\begingroup$ @PeterTaylor: addr-spec in RFC 5322 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Oct 8, 2011 at 23:09
6
$\begingroup$

Most 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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... :) $\endgroup$
    – Jukka Suomela
    Commented Oct 9, 2011 at 10:58
  • $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Commented Oct 9, 2011 at 17:25
  • $\begingroup$ 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... $\endgroup$
    – Jukka Suomela
    Commented Oct 9, 2011 at 20:31
3
$\begingroup$

Regular expressions can parse regular languages. There are many characterizations of regular languages, as witnessed by the Wikipedia page on regular languages (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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks, I did look at that page. I didn't see what I was looking for there. $\endgroup$
    – Eric Wilson
    Commented Jul 15, 2011 at 20:43
  • $\begingroup$ 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. $\endgroup$
    – Andrej Bauer
    Commented Jul 15, 2011 at 20:48
  • 4
    $\begingroup$ it's possible the OP wants "languages in the wild" $\endgroup$
    – Suresh Venkat
    Commented Jul 15, 2011 at 20:50
  • 1
    $\begingroup$ It's also possible that the OP doesn't know what a prefix grammer is. $\endgroup$
    – Eric Wilson
    Commented Jul 15, 2011 at 20:52
  • 5
    $\begingroup$ 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. $\endgroup$
    – Andrej Bauer
    Commented Jul 16, 2011 at 8:04
3
$\begingroup$

I see your rant and I raise you a Tom Christiansen contribution. :-}

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), or Django's urls.py.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Well, with certain restrictions on addressing modes, perhaps... $\endgroup$
    – aegrisomnia
    Commented Jul 15, 2011 at 20:50
1
$\begingroup$

Many text markup languages are regular or nearly regular:

troff-style markup is regular.

I think Markdown would be regular if links were always specified inline (as is required in comments).

Wikipedia 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 tables or divs, 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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ It's hard to imagine a modern web site -- using a library like Bootstrap -- without lots of nested divs. $\endgroup$
    – Eric Wilson
    Commented Oct 19, 2016 at 12:36
  • $\begingroup$ Aren't most of those divs generated with JavaScript? I.e. they occur in the DOM tree, but not in the HTML. $\endgroup$
    – reinierpost
    Commented Oct 19, 2016 at 13:39
  • $\begingroup$ No. Here is a simple example of Bootstrap HTML: getbootstrap.com/components/#panels-heading The grid stuff is the ubiquitous example: getbootstrap.com/css/#grid-example-basic $\endgroup$
    – Eric Wilson
    Commented Oct 19, 2016 at 14:11
  • 1
    $\begingroup$ Mmm ... indeed, that doesn't look like it's limited to some bounded depth in practice. I've changed my text accordingly. $\endgroup$
    – reinierpost
    Commented Oct 20, 2016 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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