Summoning Cthulhu by Parsing HTML with Regular Expressions (2021) | Hacker News Reader

Summoning Cthulhu by Parsing HTML with Regular Expressions (2021)

talbrenev.com

12 pointsdevelatio10 comments

As another example, we can look at the set of all palindromes. One way to check whether a string is a palindrome is to reverse it, and check that it is equal to its own reverse. This process requires storing a reversed copy of the string in memory. Since the string can be arbitrarily large, we require an arbitrarily large amount of memory. Any algorithm that I can come up with for determining whether a string is a palindrome runs into this same issue. By our rule of thumb, the set of palindromes is a non-regular language; this is indeed a fact which can be formally proved.

I'm pretty sure you can check if a string is a palindrome with O(1) space complexity? Just create a left pointer to the start of the string and a right pointer to the end and walk them towards the middle checking the chars they point to is equal each time?

That's not O(1), that's O(log n) memory, where `n` is the size of your string. You need `log n` bits to store the pointer. Granted, it's very limited for practical purposes, but you have to account for it in theoretical applications.

UPD: you can also say that you're actually writing a code for a Turing machine with two heads, and that would be ok. So, yeah, this is why the "you cannot write a constant-memory algorithm" definition is very hand-waving, one has to be extra careful with the model they're working in.

If you have a symbol that cannot be in the input (an EOT token), I think you can write it in O(1). You just change the input when you're done checking the outer symbols. Takes extra time, though.

how do you get to have the pointer to the end? welcome to the "accidently quadratic" world :)

That requires you to have the entire string in memory, so it’s still Ω(n). Regular languages can be recognized using O(1) space and a single reading pointer into the string, without even storing it whole; you can process it in a streaming manner.

There's no Cthulhu. TO͇̹̺ͅƝ̴ȳ̳ TH̘Ë͖́̉ ͠P̯͍̭O̚ N̐Y̡ H̸̡̪̯ͨ͊̽̅̾̎Ȩ̬̩̾͛ͪ̈́̀́͘ ̶̧̨̱̹̭̯ͧ̾ͬC̷̙̲̝͖ͭ̏ͥͮ͟Oͮ͏̮̪̝͍M̲̖͊̒ͪͩͬ̚̚͜Ȇ̴̟̟͙̞ͩ͌͝S̨̥̫͎̭ͯ̿̔̀ͅ

Put that in your regex and parse it.

I have a question about the arbitrary memory test and palindromes. Are we talking about the memory required to test? Or the memory required to hold the string? The only memory required to test a palindrome should be that for two characters because you only need compare the first and last character and continue toward the middle so long as those match. If you end up with 0 or 1 characters remaining and all previous comparisons have matched then the word is a palindrome. It doesn't seem that different to me than possibly infinitely testing if the next character is still an A in the case of (A*)

The memory required to test. Moreover, we do not have random access to the string, we may only read one byte at a time and cannot go back. You may call it "streaming access".

More formally, we're talking about finite automata: https://en.wikipedia.org/wiki/Deterministic_finite_automaton

As regards HTML, this article is terrible and completely wrong and demonstrates just why you shouldn’t try parsing HTML with regular expressions.

> Hello World! is valid HTML. Hello World! is also valid HTML. On the other hand, Hello World! is not valid HTML

The first one is correct: Hello World! is indeed valid HTML.

But Hello World! is not valid HTML (though, like everything, it has a well-defined parse), and probably never was (though I’d need to check to be sure; and I do know that unmatched used to be moderately popular, as it often achieved close to the same result as having the opening tag).

And Hello World! is valid HTML, and always has been.

It sounds like the writer is trying to parse a very limited or idealised subset of XML or XHTML, not HTML.

> HTML is a CFG*

> *Caveat: this should be true at least in theory, given HTML's tree structure. However, in practice, many browsers will be able to parse "invalid" HTML (for example, you can forget to add a closing tag, and in most cases the browser will be perfectly fine with that). Even worse, browsers don't all agree on what valid HTML actually is. Since this blog post is about regexes, and not about HTML, I decided to leave out any discussion about how to actually define HTML.

That footnote at the end is the nail in the coffin that confirms that the author is just completely clueless about HTML as it exists now, and probably its historical state too. HTML parsing is exhaustively defined, with all browsers having used the same parsing algorithm for a decade or so. (I will admit that there have been a few minor changes in that algorithm over time; <template> is probably the most significant, though in practice that’s kinda more about interpretation than parsing.) This is not something that can be said of many languages. In practice even XML isn’t as well defined or consistent as HTML (will DTD entities work? External ones? &c.).

“Valid” is basically just a rubber stamp in HTML—that certain places in the state machine can report a parse error, but that nothing will actually come of it. There’s no intrinsic reason to care about validity: HTML that is labelled invalid will work just as well as valid HTML¹. The only reason to think about it is that it suggests you may have made a mistake.

¹ Not necessarily true per https://html.spec.whatwg.org/multipage/parsing.html#parse-er...: user agents are allowed to abort on the first parse error; but in practice I’ve never heard of any implementation doing so.

Reply on news.ycombinator.com