Why it’s not possible to use regex to parse HTML/XML: a formal explanation in layman’s terms

by

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.

More Related Contents:

  1. What is the best regular expression to check if a string is a valid URL?
  2. Getting parts of a URL (Regex)
  3. How does Stack Overflow generate its SEO-friendly URLs?
  4. Is there something like a counter variable in regular expression replace?
  5. Collapse and Capture a Repeating Pattern in a Single Regex Expression
  6. What is the best regular expression to check if a string is a valid URL?
  7. Random string that matches a regexp [duplicate]
  8. Match linebreaks – \n or \r\n?
  9. Grammatical inference of regular expressions for given finite list of representative strings?
  10. Regular Expression Vs. String Parsing
  11. Why do regex engines allow / automatically attempt matching at the end of the input string?
  12. How to order regular expression alternatives to get longest match?
  13. How to negate specific word in regex? [duplicate]
  14. Support of \K in regex
  15. Regular expression to match numbers with or without commas and decimals in text
  16. Validating email addresses using jQuery and regex
  17. Bash Regular Expression — Can’t seem to match any of \s \S \d \D \w \W etc
  18. Regular Expression to match only alphabetic characters
  19. How to match digits in regex in bash script
  20. Why does strsplit use positive lookahead and lookbehind assertion matches differently?
  21. sed one-liner to convert all uppercase to lowercase?
  22. regular expression capture nth match
  23. What regex will match every character except comma ‘,’ or semi-colon ‘;’?
  24. Can I use Perl regular expressions to match balanced text?
  25. Match Sequence using RegEx After a Specified Character
  26. Nginx location “not equal to” regex
  27. How to escape dollar sign ($) in a string using perl regex
  28. Regex BNF Grammar
  29. How do I search and replace across multiple lines with Perl?
  30. What to do when a regular expression pattern doesn’t match anywhere in a string?

Leave a Comment