By georg


2012-07-03 07:52:24 8 Comments

Here on SO people sometimes say something like "you cannot parse X with regular expressions, because X is not a regular language". From my understanding however, modern regular expressions engines can match more than just regular languages in Chomsky's sense. My questions:

given a regular expression engine that supports

  • backreferences
  • lookaround assertions of unlimited width
  • recursion, like (?R)

what kind of languages can it parse? Can it parse any context-free language, and if not, what would be the counterexample?

(To be precise, by "parse" I mean "build a single regular expression that would accept all strings generated by the grammar X and reject all other strings").

Add.: I'm particularly interested to see an example of a context-free language that modern regex engines (Perl, Net, python regex module) would be unable to parse.

3 comments

@Alejandro Piad 2012-07-05 19:54:15

Modern regex engines can certainly parse a bigger set of languages than the regular languages set. So said, none of the four classic Chomsky sets are exactly recognized by regexes. All regular languages are clearly recognized by regexes. There are some classic context-free languages that cannot be recognized by regexes, such as the balanced parenthesis language a^n b^n, unless backreferences with counting are available. However, a regex can parse the language ww which is context-sensitive.

Actually, regular expressions in formal language theory are only lightly related to regexes. Matching regexes with unlimited backreference is NP-Complete in the most general case, so all pattern matching algorithms for powerful enough regexes are exponential, at least in the general case. However most times for most input they are quite fast. It is known that matching context-free languages is at most something faster than n^3, so there are some languages in regexes that are not context-free (like ww) but not all context-free languages can be parsed by regexes. Type 0 languages are non-decidable in general, son regexes don't get there.

So as a not very conclusive conclusion, regexes can parse a broad set of languages that include all regular languages, and some context-free and context-sensitive, but it is not exactly equal to any of those sets. There are other categories of languages, and other taxonomies, where you could find a more precise answer, but no taxonomy that includes context-free languages as a proper subset in a hierarchy of languages can provide a single language exactly recognized by regexes, because regexes only intersect in some part with context-free languages, and neither is a proper subset of the other.

@georg 2012-07-05 21:07:56

Thanks for the answer! An engine with recursion can parse a^n b^n: ^(|a(?1)b)$. Can you give an example of CFG that regex cannot handle? Also, what do you mean by ww?

@Bart Kiers 2012-07-06 08:32:31

@thg435, by ww he probably meant two identical chars, which a modern regex implementation can match like this: (.)\1 (as you probably are aware of, looking at your regex above :))

@Walter Tross 2012-07-07 14:04:31

@BartKiers or rather two identical words: (.+)\1

@Alejandro Piad 2012-07-10 13:55:44

ww means two identical strings, exactly as @WalterTross said. Sorry for the mistake with a^n b^n, I will edit to correct it.

@NikiC 2012-07-08 11:06:51

I recently wrote a rather long article on this topic: The true power of regular expressions.

To summarize:

  • Regular expressions with support for recursive subpattern references can match all context-free languages (e.g a^n b^n).
  • Regular expressions with lookaround assertions and subpattern references can match at least some context-sensitive languages (e.g. ww and a^n b^n c^n).
  • If the assertions have unlimited width (as you say), then all context-sensitive grammars can be matched. I don't know any regex flavor though that does not have fixed-width restrictions on lookbehind (and at the same time supports subpattern references).
  • Regular expressions with backreferences are NP-complete, so any other NP problem can be solved using regular expressions (after applying a polynomial-time transformation).

Some examples:

  • Matching the context-free language {a^n b^n, n>0}:

    /^(a(?1)?b)$/
    # or
    /^ (?: a (?= a* (\1?+ b) ) )+ \1 $/x
    
  • Matching the context-sensitive language {a^n b^n c^n, n>0}:

    /^
        (?=(a(?-1)?b)c)
        a+(b(?-1)?c)
    $/x
    # or
    /^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $/x
    

@georg 2012-07-08 11:20:16

Thanks! This is what I was looking for. regex module for python supports lookbehinds with groups and of unlimited length.

@Walter Tross 2012-07-08 11:44:15

I think that a distinction should be made between accepting (recognizing) and parsing. IMHO, parsing (from Latin pars, part) should mean to resolve into all component parts, i.e., to make them all available (e.g., in a parse tree). This is something that no regex engine (that I know, at least) is able to do - or am I wrong?

@NikiC 2012-07-08 12:19:36

@WalterTross Yes, you are right. I replaced "parse" with "match" in my answer :)

@NikiC 2012-07-08 12:23:00

@thg435 That looks interesting. Has a feature set similar to PCRE, but the variable-width lookbehind assertions are really something I haven't see before. Very nice!

@JDB 2013-02-06 13:38:47

.NET has no limit on backreferences and supports subpattern references. It is the only flavor with this capability that I am aware of.

@leo 2013-03-22 09:30:58

Great, great answer! But you should probably mention that this example need PCRE (pcre.org), so one should use pcregrep and it does not work for example with grep or egrep on the command line.

@BlueRaja - Danny Pflughoeft 2013-06-13 21:48:28

Accord to these answers lookarounds do not add any power to the language.

@NikiC 2013-06-14 08:13:08

@BlueRaja These answers are written under the assumption that you are adding only lookahead to a regular language. They do not cover whether lookahead makes the language more powerful if it already supports subpattern references. I'm pretty sure it does, because the ability to inspect context is what distinguishes context-free and context-sensitive languages.

@BlueRaja - Danny Pflughoeft 2013-06-14 16:32:37

Ah, ok thanks, +1 to you. Also, to anyone wondering what the difference between a "backreference" \1 and a "subpattern reference" (?1) is (Most sites seem to mix the two terms), see here.

@Ria 2012-07-06 07:48:14

You can read about regexes in An Introduction to Language And Linguistics By Ralph W. Fasold, Jeff Connor-Linton P.477

Chomsky Hierarchy:

Type0 >= Type1 >= Type2 >= Type3

Computational Linguistics mainly features Type 2 & 3 Grammars

Type 3 grammars:

–Include regular expressions and finite state automata (aka, finite state machines)

–The focal point of the rest of this talk

Type 2 grammars:

–Commonly used for natural language parsers

–Used to model syntactic structure in many linguistic theories (often supplemented by other mechanisms)

–We will play a key roll in the next talk on parsing.


most XMLs like Microsoft DGML (Directed Graph Markup Language) that has inter-relational links are samples that Regex are useless.


and this three answers may be useful:

1 - does-lookaround-affect-which-languages-can-be-matched-by-regular-expressions

2 - regular-expressions-arent

3 - where-do-most-regex-implementations-fall-on-the-complexity-scale

@georg 2012-07-06 09:24:08

Thanks for the links, very helpful.

@Ria 2012-07-06 10:14:34

XML or Microsoft DGML (Directed Graph Markup Language) are samples that Regex are useless.

Related Questions

Sponsored Content

9 Answered Questions

1 Answered Questions

[SOLVED] Should regex be used in a parser for an interpreter or compiler?

  • 2017-06-14 23:12:27
  • David
  • 239 View
  • 1 Score
  • 1 Answer
  • Tags:   regex parsing

1 Answered Questions

[SOLVED] The recognizing power of "modern" regexes

4 Answered Questions

[SOLVED] Match a^n b^n c^n (e.g. "aaabbbccc") using regular expressions (PCRE)

  • 2011-09-15 16:28:58
  • NikiC
  • 6212 View
  • 42 Score
  • 4 Answer
  • Tags:   php regex pcre

3 Answered Questions

[SOLVED] How can we match a^n b^n with Java regex?

1 Answered Questions

4 Answered Questions

2 Answered Questions

[SOLVED] Can extended regex implementations parse HTML?

  • 2011-02-08 13:28:58
  • Tesserex
  • 529 View
  • 6 Score
  • 2 Answer
  • Tags:   regex

3 Answered Questions

3 Answered Questions

Sponsored Content