6

This article argues that regular expressions cannot match nested structures because regexes are finite automatons.

He then offers a list of problems in which the answer states that the following cannot be solved using regexes:

  1. matching an XML element
  2. matching a C/VB/C# math expression
  3. matching a valid regex

Since 2 & 3 can conceivably contain brackets; this nesting is unsolvable for regexes. But why is it impossible to match an XML element ? (He didn't provide examples).

BoltClock
  • 700,868
  • 160
  • 1,392
  • 1,356
Frankie Ribery
  • 11,933
  • 14
  • 50
  • 64
  • 3
    relevant: http://stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags – meder omuraliev Jun 07 '11 at 02:57
  • Correction: "Why is it impossible to ***reliably*** match XML elements?" The danger is always that it *appears* to work initially... – deceze Jun 07 '11 at 02:59
  • 3
    Same issue as matching parentheses/brackets in a math expression. XML can be nested infinitely, so it's impossible to use regex as a complete solution. – Rafe Kettler Jun 07 '11 at 02:59
  • 2
    If you are lucky, the [author](http://stackoverflow.com/users/23283/jaredpar) of that article will give you an answer. – alex Jun 07 '11 at 03:01
  • 7
    Simply becaȕ͈̭̙̖̘̜ͨ̉ͭ͊ͅs͇̥̰̳e̶̐̄͌̿͑͛̍ the <͔̗̠̯̅͌͆̒͒͝c̫̠̟̺̥̊͊̅̏ḕ̷͔̟͈̯̘͈͌ͨn̶̯̝̲͋͗̿̄̿t̫̞͎ͤ̔̍̿ͨ͌ͫe̸͙̪̬͙̖̥̐ͩr̭͉͗͗>̩̜͙̼̘̤̩ͨ͊͒͑ͮͥ͢ cann̵̑̀o̪̥͎̝̳̺͈ͨ̂ͤͪ̉͗̀t̺̤̺̣̊́̓ͨͩ̈ ̸̲̓̐̅h̹͍͎̣̱͇ͨ̊ͦo̞͇̮͈̬ͤ̀ͧ̀̚ld. – BoltClock Jun 07 '11 at 03:03
  • 1
    @BoltClock Thanks for vandalising my comment :P – alex Jun 07 '11 at 03:12
  • @BoltClock, way to [plagiarize](http://stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732454#1732454) :-) – Mike Pennington Jun 07 '11 at 03:15

4 Answers4

3

You can match a limited subset of HTML tags, if you know in advance the tags to be matched.

But you can't (reliably or nicely) parse arbitrary HTML. It is not a regular language.

alex
  • 479,566
  • 201
  • 878
  • 984
1

How would you match this valid XML with regex?

<!--<d>>--<<--><div class='foo' id="bar" inline></div>

It's like making a wooden car. Sure you can try to do it, but why?

But then comes the part of parsing the XML. How would you extract a set of possibly infinite attributes from an infinite set of elements using a finite set of groups? It's just not possible due to the nature and structure of regex.

Blender
  • 289,723
  • 53
  • 439
  • 496
1

There are theoretical answers, based on what kind of grammar XML is and what kind of grammar regular expressions can match. These answers are sometimes flawed by the fact that most regular expression libraries we use today can do things that the formal regular expressions defined in computer science can't do (like back-references).

And there are practical answers. The practical answer is: don't do it because it's the wrong tool for the job, your code will be hard to write and unmaintainable, it will be inefficient, it will have bugs, and no-one will know how to change it when the structure of the document changes. And because there are better tools for the job, called XML parsers.

Michael Kay
  • 156,231
  • 11
  • 92
  • 164
0

Regular expressions are free of state. To parse an XML file, you need state. A < might signal the opening of an XML element. If it's inside a comment <!-- < --> or an attribute value "<" though it means something else. Using Regexen you can only express things in terms of things that come before or after other things. To correctly parse < as opening an XML element you'd need to express something along the lines of:

< but not after <!-- if <!-- wasn't followed by --> and not after " if " was not closed but only if " was an attribute because " as a text value has no influence on the next < and if not...

And that's only for a simple <, not even covering all the possibilities. There are a handful of XML special chars that all have the same kind of circular conditions. Constructing a Regex that expresses all these conditions correctly for all cases is virtually impossible. It's trivial with a state machine though.

deceze
  • 510,633
  • 85
  • 743
  • 889
  • 1
    FSAs/Regexes are not free of state, they just use a constant amount of state: if you have seen an `a` in matching `ab*` how can you know if the string matches without some kind of state. FSAs cannot handle nesting - i.e. `>` can only be acceptable if there is at least one unmatched `<` preceding it. – tobyodavies Jun 07 '11 at 03:27
  • I knew somebody who knows the terminology better than I would object to my use of "state"... :o) Please feel free to edit my answer. – deceze Jun 07 '11 at 03:29