3 ms·

I think the Zalgo answer is an wonderful example of people thinking they are smarter than they really are. Spot the error: 1) HTML is not a regular language

by yarcob 5y ago

I think the Zalgo answer is an wonderful example of people thinking they are smarter than they really are. Spot the error: 1) HTML is not a regular language 2) Regular expressions can only parse regular languages 3) Regular expressions can not be used to to parse arbitrary HTML documents 4) If you try to use regular expressions to parse HTML documents, you are doing it wrong The error is between step 3 and 4: It's true that you can't write a regex that parses arbitrary HTML. However, very often we do not have to deal with arbitrary HTML. Very often we have to deal with documents that only use a subset of HTML and they can be parsed by regular expressions just fine.

bawolff 5y ago
> 2) Regular expressions can only parse regular languages This is false, regular expressions as popularly implemented can parse non-regular languages. For example, /^(.*)\1$/ is a non regular language.
- exmadscientist 5y ago
  Strictly (pedantically) speaking, using a backreference turns it from a "regular expression" into a "regex", regexes being a superset of regular expressions that are no longer strictly limited to being regular. Isn't terminology great?
- jjtheblunt 5y ago
  It's true, not false. You refer to a misleading overloading of the term when referring to the stack machines needed to realize 'regular expressions with backreference memories', which expands the language class to which they correspond. Citation : https://www.amazon.com/Introduction-Automata-Languages-Computation-Addison-Wesley/dp/020102988X https://www.amazon.com/Introduction-Automata-Languages-Compu...
  - bawolff 5y ago
    Context matters, in the context of the original post that was not how they used the term.
frank_nitti 5y ago
I've always taken it as a response to people trying to force regex solutions for all text parsing problems beyond string.split(), perhaps making the unfair assumption that the asker wasn't already aware of XML parsing libraries and just wanted to try it with regex...
mirekrusin 5y ago
There exist regexp that matches invalid html parsing regexps /.*/
lloeki 5y ago
> Very often we have to deal with documents that only use a subset of HTML and they can be parsed by regular expressions just fine. I agree, assuming the emitter of the document to be processed is a) correct (as in bug free, and as in knows the expected HTML subset and the corner cases of its ad hoc parsing method, and will never make a mistake nor assume the other end has an actual HTML parser) and b) has no ill intent. In practice, it is neither. > people thinking they are smarter than they really are I genuinely think it is the quippy expression of someone who has been burned way too much by the practical side of this that they prefer to frantically laugh at themselves as much as the issue out of despair of people trying to be smart with regexes. They chose to actually not be smart at all, and just use an HTML parser to parse HTML documents.
- hakfoo 5y ago
  One of the situations I've seen is roughly: System is up: returns XML or JSON or pretty-format-of-the-week System is down: It returns a HTML IIS error page. In the second case, all you might want is to extract the content of the first <h1> tag out of that error page. That's predictable enough of a task that a Regex might be able to handle it, especially if at that point you've already iven up on a full success and you're just salvaging a prettier error message than "system error".
  - yarcob 5y ago
    Exactly. In cases like this using an HTML/XML parser instead of a regular expression won't make a difference at all.
a-dub 5y ago
all the "string theory" means is that you cannot parse html completely or check its validity with a SINGLE regex based on a standard nfa or dfa. the reason why is that standard nfas and dfas cannot implement arbitrary counters for the purposes of keeping track of recursion depth or "how many open parens are currently open right now in the parsing?" there are a few subtle points here: 1) you CAN parse and validate non-regular languages by using regular expressions for subsets of them that ARE regular and then validating the whole. this is exactly what most parser generators generate. 2) you CAN use regular expressions to manipulate text in regular languages if you are careful. however, you should be extremely cautious, as non-regular parts of languages are often those that are used to support escaping or quoting or recursive sections of languages and subtle bugs in these sorts of things can sometimes have unintended consequences in terms of security. 3) you CAN use regular expressions for simple search and replace but see #2. if the language allows escaping or quoting, your regexes will not respect it on their own. this may have the unintended consequence of things you expect to have escaped not be escaped or vice versa. depending on other assertions in your project, this may or may not matter. in the worst case, it could result in a hard to track down or security critical bug. 4) regular expressions are implemented by simulating nfas and dfas. sometimes when implementing these simulations, programmers take advantage of the fact that they're programming and just slap counters in there giving their implementations the ability to support some non-regular languages. as a rule of thumb, if i'm dealing with untrusted input, i'll use a proper parser. so yes, you can use regular expressions, but you should understand their limitations if you do so. (which also means understanding your input language)
dragonwriter 5y ago
There might be a few narrow cases where using regex to parse XML/HTML might make sense, but even in majority of the cases where it might conceivably work it doesn’t make sense because XML/HTML parsing libraries exist and the time and effort you spend building, debugging, and maintaining your brittle, limited, ad hoc parser is still wasted effort that increases both the time to deliver and maintenance cost of the project it is part of.
jjtheblunt 5y ago
So, so glad to see someone cite the regular language issue in that naivete.
bborud 5y ago
> However, very often we do not have to deal with arbitrary HTML. That really depends on who "we" are and what you mean by"very often". I used to develop web crawlers, HTML parsers, document analysis infrastructure and various other things that come into contact with "content" for web crawlers at various search engine companies. If you assume people can produce valid, or even half way sane HTML, you'll be disappointed. As for how you parse insane HTML: with difficulty.
goto11 5y ago
The question is not about parsing at all. The question is about tokenization of XHTML. You can tokenize XHTML with a regular expression.

by yarcob 5y ago

bawolff 5y ago

> 2) Regular expressions can only parse regular languages This is false, regular expressions as popularly implemented can parse non-regular languages. For example, /^(.*)\1$/ is a non regular language.

exmadscientist 5y ago
Strictly (pedantically) speaking, using a backreference turns it from a "regular expression" into a "regex", regexes being a superset of regular expressions that are no longer strictly limited to being regular. Isn't terminology great?
jjtheblunt 5y ago
It's true, not false. You refer to a misleading overloading of the term when referring to the stack machines needed to realize 'regular expressions with backreference memories', which expands the language class to which they correspond. Citation : https://www.amazon.com/Introduction-Automata-Languages-Computation-Addison-Wesley/dp/020102988X https://www.amazon.com/Introduction-Automata-Languages-Compu...
- bawolff 5y ago
  Context matters, in the context of the original post that was not how they used the term.

frank_nitti 5y ago

I've always taken it as a response to people trying to force regex solutions for all text parsing problems beyond string.split(), perhaps making the unfair assumption that the asker wasn't already aware of XML parsing libraries and just wanted to try it with regex...

mirekrusin 5y ago

There exist regexp that matches invalid html parsing regexps /.*/

lloeki 5y ago

> Very often we have to deal with documents that only use a subset of HTML and they can be parsed by regular expressions just fine. I agree, assuming the emitter of the document to be processed is a) correct (as in bug free, and as in knows the expected HTML subset and the corner cases of its ad hoc parsing method, and will never make a mistake nor assume the other end has an actual HTML parser) and b) has no ill intent. In practice, it is neither. > people thinking they are smarter than they really are I genuinely think it is the quippy expression of someone who has been burned way too much by the practical side of this that they prefer to frantically laugh at themselves as much as the issue out of despair of people trying to be smart with regexes. They chose to actually not be smart at all, and just use an HTML parser to parse HTML documents.

hakfoo 5y ago
One of the situations I've seen is roughly: System is up: returns XML or JSON or pretty-format-of-the-week System is down: It returns a HTML IIS error page. In the second case, all you might want is to extract the content of the first <h1> tag out of that error page. That's predictable enough of a task that a Regex might be able to handle it, especially if at that point you've already iven up on a full success and you're just salvaging a prettier error message than "system error".
- yarcob 5y ago
  Exactly. In cases like this using an HTML/XML parser instead of a regular expression won't make a difference at all.

a-dub 5y ago

all the "string theory" means is that you cannot parse html completely or check its validity with a SINGLE regex based on a standard nfa or dfa. the reason why is that standard nfas and dfas cannot implement arbitrary counters for the purposes of keeping track of recursion depth or "how many open parens are currently open right now in the parsing?" there are a few subtle points here: 1) you CAN parse and validate non-regular languages by using regular expressions for subsets of them that ARE regular and then validating the whole. this is exactly what most parser generators generate. 2) you CAN use regular expressions to manipulate text in regular languages if you are careful. however, you should be extremely cautious, as non-regular parts of languages are often those that are used to support escaping or quoting or recursive sections of languages and subtle bugs in these sorts of things can sometimes have unintended consequences in terms of security. 3) you CAN use regular expressions for simple search and replace but see #2. if the language allows escaping or quoting, your regexes will not respect it on their own. this may have the unintended consequence of things you expect to have escaped not be escaped or vice versa. depending on other assertions in your project, this may or may not matter. in the worst case, it could result in a hard to track down or security critical bug. 4) regular expressions are implemented by simulating nfas and dfas. sometimes when implementing these simulations, programmers take advantage of the fact that they're programming and just slap counters in there giving their implementations the ability to support some non-regular languages. as a rule of thumb, if i'm dealing with untrusted input, i'll use a proper parser. so yes, you can use regular expressions, but you should understand their limitations if you do so. (which also means understanding your input language)

dragonwriter 5y ago

There might be a few narrow cases where using regex to parse XML/HTML might make sense, but even in majority of the cases where it might conceivably work it doesn’t make sense because XML/HTML parsing libraries exist and the time and effort you spend building, debugging, and maintaining your brittle, limited, ad hoc parser is still wasted effort that increases both the time to deliver and maintenance cost of the project it is part of.

jjtheblunt 5y ago

So, so glad to see someone cite the regular language issue in that naivete.

bborud 5y ago

> However, very often we do not have to deal with arbitrary HTML. That really depends on who "we" are and what you mean by"very often". I used to develop web crawlers, HTML parsers, document analysis infrastructure and various other things that come into contact with "content" for web crawlers at various search engine companies. If you assume people can produce valid, or even half way sane HTML, you'll be disappointed. As for how you parse insane HTML: with difficulty.

goto11 5y ago

The question is not about parsing at all. The question is about tokenization of XHTML. You can tokenize XHTML with a regular expression.