By mac


2011-07-19 17:06:13 8 Comments

There is no day on SO that passes without a question about parsing (X)HTML or XML with regular expressions being asked.

While it's relatively easy to come up with examples that demonstrates the non-viability of regexes for this task or with a collection of expressions to represent the concept, I could still not find on SO a formal explanation of why this is not possible done in layman's terms.

The only formal explanations I could find so far on this site are probably extremely accurate, but also quite cryptic to the self-taught programmer:

the flaw here is that HTML is a Chomsky Type 2 grammar (context free grammar) and RegEx is a Chomsky Type 3 grammar (regular expression)

or:

Regular expressions can only match regular languages but HTML is a context-free language.

or:

A finite automaton (which is the data structure underlying a regular expression) does not have memory apart from the state it's in, and if you have arbitrarily deep nesting, you need an arbitrarily large automaton, which collides with the notion of a finite automaton.

or:

The Pumping lemma for regular languages is the reason why you can't do that.

[To be fair: the majority of the above explanation link to wikipedia pages, but these are not much easier to understand than the answers themselves].

So my question is: could somebody please provide a translation in layman's terms of the formal explanations given above of why it is not possible to use regex for parsing (X)HTML/XML?

EDIT: After reading the first answer I thought that I should clarify: I am looking for a "translation" that also briefely explains the concepts it tries to translate: at the end of an answer, the reader should have a rough idea - for example - of what "regular language" and "context-free grammar" mean...

9 comments

@Gilles Quenot 2019-04-03 17:57:51

Don't parse XML/HTML with regex, use a proper XML/HTML parser and a powerful query.

theory :

According to the compiling theory, XML/HTML can't be parsed using regex based on finite state machine. Due to hierarchical construction of XML/HTML you need to use a pushdown automaton and manipulate LALR grammar using tool like YACC.

realLife©®™ everyday tool in a :

You can use one of the following :

xmllint often installed by default with libxml2, xpath1 (check my wrapper to have newlines delimited output

xmlstarlet can edit, select, transform... Not installed by default, xpath1

xpath installed via perl's module XML::XPath, xpath1

xidel xpath3

saxon-lint my own project, wrapper over @Michael Kay's Saxon-HE Java library, xpath3

or you can use high level languages and proper libs, I think of :

's lxml (from lxml import etree)

's XML::LibXML, XML::XPath, XML::Twig::XPath, HTML::TreeBuilder::XPath

, check this example

DOMXpath, check this example


Check: Using regular expressions with HTML tags

@bükWyrm 2018-06-20 00:31:11

In a purely theoretical sense, it is impossible for regular expressions to parse XML. They are defined in a way that allows them no memory of any previous state, thus preventing the correct matching of an arbitrary tag, and they cannot penetrate to an arbitrary depth of nesting, since the nesting would need to be built into the regular expression.

Modern regex parsers, however, are built for their utility to the developer, rather than their adherence to a precise definition. As such, we have things like back-references and recursion that make use of knowledge of previous states. Using these, it is remarkably simple to create a regex that can explore, validate, or parse XML.

Consider for example,

(?:
    <!\-\-[\S\s]*?\-\->
    |
    <([\w\-\.]+)[^>]*?
    (?:
        \/>
        |
        >
        (?:
            [^<]
            |
            (?R)
        )*
        <\/\1>
    )
)

This will find the next properly formed XML tag or comment, and it will only find it if it's entire contents are properly formed. (This expression has been tested using Notepad++, which uses Boost C++'s regex library, which closely approximates PCRE.)

Here's how it works:

  1. The first chunk matches a comment. It's necessary for this to come first so that it will deal with any commented-out code that otherwise might cause hang ups.
  2. If that doesn't match, it will look for the beginning of a tag. Note that it uses parentheses to capture the name.
  3. This tag will either end in a />, thus completing the tag, or it will end with a >, in which case it will continue by examining the tag's contents.
  4. It will continue parsing until it reaches a <, at which point it will recurse back to the beginning of the expression, allowing it to deal with either a comment or a new tag.
  5. It will continue through the loop until it arrives at either the end of the text or at a < that it cannot parse. Failing to match will, of course, cause it to start the process over. Otherwise, the < is presumably the beginning of the closing tag for this iteration. Using the back-reference inside a closing tag <\/\1>, it will match the opening tag for the current iteration (depth). There's only one capturing group, so this match is a simple matter. This makes it independent of the names of the tags used, although you could modify the capturing group to capture only specific tags, if you need to.
  6. At this point it will either kick out of the current recursion, up to the next level or end with a match.

This example solves problems dealing with whitespace or identifying relevant content through the use of character groups that merely negate < or >, or in the case of the comments, by using [\S\s], which will match anything, including carriage returns and new lines, even in single-line mode, continuing until it reaches a -->. Hence, it simply treats everything as valid until it reaches something meaningful.

For most purposes, a regex like this isn't particularly useful. It will validate that XML is properly formed, but that's all it will really do, and it doesn't account for properties (although this would be an easy addition). It's only this simple because it leaves out real world issues like this, as well as definitions of tag names. Fitting it for real use would make it much more of a beast. In general, a true XML parser would be far superior. This one is probably best suited for teaching how recursion works.

Long story short: use an XML parser for real work, and use this if you want to play around with regexes.

@Michael Kay 2018-09-02 08:57:46

The statement that this regex will only match if the input is well-formed is incorrect. It doesn't check that the names are valid XML names, it doesn't check attributes, it doesn't check entity and character references, it doesn't handle CDATA or processing instructions. When you say it has been tested, I very much doubt that it has been tested on anything resembling the XML conformance test suite. That's the problem with all attempts to process XML with regexes that I've ever seen: they work with a small number of inputs, but not with any XML that can legally be passed to your application.

@Michael Kay 2018-09-02 09:11:52

Also, there are well-formed inputs that the regex doesn't match. For example, it doesn't allow whitespace after the name in the end tag. Most of these glitches are easily fixed, but once you fix ALL the glitches you end up with something totally unusable. And of course the real gotcha is that you don't just want a parser to give you a yes/no answer, you want it to pass information to an application that does something useful with it.

@Michael Kay 2018-06-13 07:56:07

There's another practical reason for not using regular expressions to parse XML and HTML that has nothing to do with the computer science theory at all: your regular expression will either be hideously complicated, or it will be wrong.

For example, it's all very well writing a regular expression to match

<price>10.65</price>

But if your code is to be correct, then:

  • It must allow whitespace after the element name in both start and end tag

  • If the document is in a namespace, then it should allow any namespace prefix to be used

  • It should probably allow and ignore any unknown attributes appearing in the start tag (depending on the semantics of the particular vocabulary)

  • It may need to allow whitespace before and after the decimal value (again, depending on the detailed rules of the particular XML vocabulary).

  • It should not match something that looks like an element, but is actually in a comment or CDATA section (this becomes especially important if there is a possibility of malicious data trying to fool your parser).

  • It may need to provide diagnostics if the input is invalid.

Of course some of this depends on the quality standards you are applying. We see a lot of problems on StackOverflow with people having to generate XML in a particular way (for example, with no whitespace in the tags) because it is being read by an application that requires it to be written in a particular way. If your code has any kind of longevity then it's important that it should be able to process incoming XML written in any way that the XML standard permits, and not just the one sample input document that you are testing your code on.

@Ianus Chiaroscuro 2011-07-19 17:09:31

Because HTML can have unlimited nesting of <tags><inside><tags and="<things><that><look></like></tags>"></inside></each></other> and regex can't really cope with that because it can't track a history of what it's descended into and come out of.

A simple construct that illustrates the difficulty:

<body><div id="foo">Hi there!  <div id="bar">Bye!</div></div></body>

99.9% of generalized regex-based extraction routines will be unable to correctly give me everything inside the div with the ID foo, because they can't tell the closing tag for that div from the closing tag for the bar div. That is because they have no way of saying "okay, I've now descended into the second of two divs, so the next div close I see brings me back out one, and the one after that is the close tag for the first". Programmers typically respond by devising special-case regexes for the specific situation, which then break as soon as more tags are introduced inside foo and have to be unsnarled at tremendous cost in time and frustration. This is why people get mad about the whole thing.

@mac 2011-07-19 17:13:18

Appreciate the answer, but my question is not "why I can't use regex...". My question is about "translating" the formal explanations I provided! :)

@Ianus Chiaroscuro 2011-07-19 17:14:39

This is a translation of all of them in some sense, most proximately "Regular expressions can only match regular languages but HTML is a context-free language" and the one about finite automata. It's really all the same reason.

@mac 2011-07-19 17:19:16

Sorry, maybe I haven't been clear in my question (suggestions for improving it are welcome!). But I looking for an answer that also explains the "translation". Your answer doesn't clarify either the 'regular language' nor 'context-free language' concepts...

@Ianus Chiaroscuro 2011-07-19 17:21:45

Explaining those terms would be just as technical as the jargon itself, and a distraction from the actual meaning that all the precision language is getting at, that being what I posted.

@Kobi 2011-07-19 18:01:31

<(\w+)(?:\s+\w+="[^"]*")*>(?R)*</\1>|[\w\s!']+ matches your code sample.

@agent-j 2011-07-19 17:23:42

A grammar is a formal definition of where words can go. For example, adjectives preceed nouns in English grammar, but follow nouns en la gramática española. Context-free means that the grammer universally in all contexts. Context-sensitive means there are additional rules in certain contexts.

In C#, for example, using means something different in using System; at the top of files, than using (var sw = new StringWriter (...)). A more relevant example is the following code within code:

void Start ()
{
    string myCode = @"
    void Start()
    {
       Console.WriteLine (""x"");
    }
    ";
}

@A Person 2014-01-05 03:10:24

This is an understandable answer

@Taemyr 2015-06-04 09:41:30

But context-free does not mean regular. The language of matched paranthesis is context-free, but not regular.

@reinierpost 2015-11-20 17:54:54

What should be added is that regular expressions (unless you add such extensions as are present in Perl) are equivalent to regular grammars, which means they cannot described arbitrarily deeply nested structures such as arbitrarily deeply balanced parentheses or HTML element opening and closing tags.

@Sean McMillan 2011-07-19 17:31:33

A regular language is a language that can be matched by a finite state machine.

(Understanding Finite State machines, Push-down machines, and Turing machines is basically the curriculum of a fourth year college CS Course.)

Consider the following machine, which recognizes the string "hi".

(Start) --Read h-->(A)--Read i-->(Succeed)
  \                  \
   \                  -- read any other value-->(Fail) 
    -- read any other value-->(Fail)

This is a simple machine to recognize a regular language; Each expression in parenthesis is a state, and each arrow is a transition. Building a machine like this will allow you to test any input string against a regular language -- hence, a regular expression.

HTML requires you to know more than just what state you are in -- it requires a history of what you have seen before, to match tag nesting. You can accomplish this if you add a stack to the machine, but then it is no longer "regular". This is called a Push-down machine, and recognizes a grammar.

@mac 2011-07-20 08:55:48

"Understanding Finite State machines, Push-down machines, and Turing machines is basically the curriculum of a 300-level CS Course." I understand this is an attempt to state how difficult/advance the topic is, but I am unfamiliar with the school system you are referring to, could you please clarify in a non country-specific way? Thank you! :)

@Sean McMillan 2011-07-20 11:14:24

I've updated it. I don't know that it's too difficult to understand, just to explain in a stack overflow post.

@n.m. 2011-07-19 17:21:50

A regular expression is a machine with a finite (and typically rather small) number of discrete states.

To parse XML, C, or any other language with arbitrary nesting of language elements, you need to remember how deep you are. That is, you must be able to count braces/brackets/tags.

You cannot count with finite memory. There may be more brace levels than you have states! You might be able to parse a subset of your language that restricts the number of nesting levels, but it would be very tedious.

@Kobi 2011-07-19 18:51:43

The fact the HTML doesn't represent a regular language is a red herring. Regular expression and regular languages sound sort of similar, but are not - they do share the same origin, but there's a notable distance between the academic "regular languages" and the current matching power of engines. In fact, almost all modern regular expression engines support non-regular features - a simple example is (.*)\1. which uses backreferencing to match a repeated sequence of characters - for example 123123, or bonbon. Matching of recursive/balanced structures make these even more fun.

Wikipedia puts this nicely, in a quote by Larry Wall:

'Regular expressions' [...] are only marginally related to real regular expressions. Nevertheless, the term has grown with the capabilities of our pattern matching engines, so I'm not going to try to fight linguistic necessity here. I will, however, generally call them "regexes" (or "regexen", when I'm in an Anglo-Saxon mood).

"Regular expression can only match regular languages", as you can see, is nothing more than a commonly stated fallacy.

So, why not then?

A good reason not to match HTML with regular expression is that "just because you can doesn't mean you should". While may be possible - there are simply better tools for the job. Considering:

  • Valid HTML is harder/more complex than you may think.
  • There are many types of "valid" HTML - what is valid in HTML, for example, isn't valid in XHTML.
  • Much of the free-form HTML found on the internet is not valid anyway. HTML libraries do a good job of dealing with these as well, and were tested for many of these common cases.
  • Very often it is impossible to match a part of the data without parsing it as a whole. For example, you might be looking for all titles, and end up matching inside a comment or a string literal. <h1>.*?</h1> may be a bold attempt at finding the main title, but it might find:

    <!-- <h1>not the title!</h1> -->
    

    Or even:

    <script>
    var s = "Certainly <h1>not the title!</h1>";
    </script>
    

Last point is the most important:

  • Using a dedicated HTML parser is better than any regex you can come up with. Very often, XPath allows a better expressive way of finding the data you need, and using an HTML parser is much easier than most people realize.

A good summary of the subject, and an important comment on when mixing Regex and HTML may be appropriate, can be found in Jeff Atwood's blog: Parsing Html The Cthulhu Way.

When is it better to use a regular expression to parse HTML?

In most cases, it is better to use XPath on the DOM structure a library can give you. Still, against popular opinion, there are a few cases when I would strongly recommend using a regex and not a parser library:

Given a few of these conditions:

  • When you need a one-time update of your HTML files, and you know the structure is consistent.
  • When you have a very small snippet of HTML.
  • When you aren't dealing with an HTML file, but a similar templating engine (it can be very hard to find a parser in that case).
  • When you want to change parts of the HTML, but not all of it - a parser, to my knowledge, cannot answer this request: it will parse the whole document, and save a whole document, changing parts you never wanted to change.

@mac 2011-07-20 09:08:28

This is a very clear and nicely written piece on when (not to) use regex for parsing HTML, but it's hardly an answer to my question. May I suggest that you move it to this question instead? I think it would get you more reputation there but - above all - I think that would be a place where future visitors would find it more relevant (there is a comment by @Bart Kiers to my question that reminds visitors of the "extra power" of modern regex engines).

@Kobi 2011-07-20 10:52:47

@mac - Thanks a lot. Actually, I did give it some thought. I know I didn't answer your question, but I don't think the question is basically correct - you ask to explain the wrong reason... You have a good idea though, maybe the other question is more suitable...

@Steve Jessop 2011-07-19 17:24:55

Concentrate on this one:

A finite automaton (which is the data structure underlying a regular expression) does not have memory apart from the state it's in, and if you have arbitrarily deep nesting, you need an arbitrarily large automaton, which collides with the notion of a finite automaton.

The definition of regular expressions is equivalent to the fact that a test of whether a string matches the pattern can be performed by a finite automaton (one different automaton for each pattern). A finite automaton has no memory - no stack, no heap, no infinite tape to scribble on. All it has is a finite number of internal states, each of which can read a unit of input from the string being tested, and use that to decide which state to move to next. As special cases, it has two termination states: "yes, that matched", and "no, that didn't match".

HTML, on the other hand, has structures that can nest arbitrarily deep. To determine whether a file is valid HTML or not, you need to check that all the closing tags match a previous opening tag. To understand it, you need to know which element is being closed. Without any means to "remember" what opening tags you've seen, no chance.

Note however that most "regex" libraries actually permit more than just the strict definition of regular expressions. If they can match back-references, then they've gone beyond a regular language. So the reason why you shouldn't use a regex library on HTML is a little more complex than the simple fact that HTML is not regular.

@GDP2 2016-02-09 00:00:17

There's also a rather good explanation of finite state automata here: youtube.com/watch?v=vhiiia1_hC4

Related Questions

Sponsored Content

2 Answered Questions

[SOLVED] What is a Context Free Grammar?

1 Answered Questions

12 Answered Questions

[SOLVED] Can you provide some examples of why it is hard to parse XML and HTML with a regex?

  • 2009-03-31 14:13:39
  • Chas. Owens
  • 40894 View
  • 393 Score
  • 12 Answer
  • Tags:   html xml regex

1 Answered Questions

[SOLVED] Regexp parse type-3 grammar

1 Answered Questions

[SOLVED] Regular Language (yes or no)

4 Answered Questions

[SOLVED] Why do Ruby ERB and jQuery use regexes to parse HTML?

3 Answered Questions

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

3 Answered Questions

4 Answered Questions

[SOLVED] Why is it that regex cannot match an XML element?

2 Answered Questions

[SOLVED] Can extended regex implementations parse HTML?

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

Sponsored Content