4 ms·

2nd answer: "While arbitrary HTML with only a regex is impossible, it's sometimes appropriate to use them for parsing a limited, known set of HTML." This. So m

2nd answer: "While arbitrary HTML with only a regex is impossible, it's sometimes appropriate to use them for parsing a limited, known set of HTML." This. So much this. Yes, you can't parse arbitrary, unknown XML with regex. But I don't find myself parsing arbitrary, unknown XML very often. Usually I know exactly what I'm expecting and if I can't find the information I need then it's a problem. Regex parsing is perfect for this scenario - and much, much faster. I created a regex parser for Java that even handles namespaces and relative paths. Can it parse every XML file? No - you can't parse XML with regex. But I can parse everything I need to parse - and if I can't? I can always fall back on full-featured XML parsers.

dragontamer 6y ago
I found a one-pass top-down "XML parser". Not like a proper SAX parser, no... the XML had to be specially formatted, almost like TOML. <whatever> <--- Parser parsed this as a new section <foo attrib=bar> <--- All "XML" had to be one-per-line </whatever> <---- parser ignored this It was an "XML parser" per se, but it really was just a linear one-pass parser that tricked me into thinking it was XML. So really, it was more like TOML (or .INI files) than like XML. But I guess the advantage of making it "bastard XML" instead of TOML is that maybe this worked with XML-editors or something. I dunno...
- cbsks 6y ago
  I’ve written an XML parser like this for a toy project. I passed the XML through a prettifier first so that it was in a standard format. It wouldn’t work for every XML file, but it worked on the files that I needed it for. I have also had success searching through html files with grep after passing them through a prettifier. It’s ugly, but 90% of the time, it works every time!
  - dragontamer 6y ago
    The specific project I saw that did this had ALL of its configuration files in this "Bastard XML" format. Its ugly, but when 100% of your files you interpret match the one-per-line (and other clearly made-up rules), then it works 100% of the time!!
polote 6y ago
When I was working on a link parser in python for a crawler. I had two choices: 1. use some form of regex 2. use libxml and find links 1. was faster than 2. by a factor or two Does a link-only parser would have been faster ? Yeah probably but it is much more complex to do
- benlivengood 6y ago
  What was the average difference in accuracy? It's a fair tradeoff especially for a crawler where it's never guaranteed to reach all documents anyway.
- contravariant 6y ago
  Maybe I'm confused about the problem you're solving but regexp was faster than just: from lxml import html doc = html.from_string(response.content) doc.xpath('//a/@href') ?
  - polote 6y ago
    Yes exactly. I'm not even sure XPath was faster than iter on a tags. But I would need to check on that one
xurukefi 6y ago
In my experience, a regex can be a much more robust solution than an XML parser depending on the use case. Back in the days when I did some webscraping I often had parsers throwing exceptions becacuse of ivalid HTML. More often than not I switched to regular expressions, which always worked out flawlessly.
- metalliqaz 6y ago
  "always flawless" is a bold claim
  - oeiiooeieo 6y ago
    "I've never lost playing Russian Roulette"
  - mumblemumble 6y ago
    It's hard to imagine any web scraping being described as "flawless". But there's a whole lot of room for "worked fine for my purposes." I think that it's actually a pretty great example of a case where capturing data from HTML may not be best modeled as a parsing task. You might not need a whole parse tree just to match some pattern and grab an associated string. And skipping the parse may enable you to get useful data out of a file that technically can't be parsed due to syntactic errors. It's a fairly classic precision/recall tradeoff situation.
- btilly 6y ago
  Yes. HTML isn't XML. As you discovered, HTML in the real world is allowed to be malformed in various ways, while XML is not. A compliant parser MUST barf on various kinds of malformed text. (Search for "fatal error" in https://www.w3.org/TR/REC-xml/ https://www.w3.org/TR/REC-xml/ to verify.) This makes XML parsers inappropriate for HTML parsing. Interestingly, even perfectly valid HTML may not be valid XML. To see that consider <b>this <i>example</b> carefully</i>.
chubot 6y ago
All you need to parse HTML is regular expressions (to recognize tags) and a stack (to match tags). Your programming language has a stack -- a call stack. So in practice all you really need is regular expressions. (Which I tend to call "regular languages" to make a distinction with Perl-style regexes [1], although they work fine too in practice for this case) Using the call stack in a more functional style is nicer than using the OOP style that s in the Python standard library, which is probably inherited from Java, etc. I have done this with a bunch of HTML processors for the Oil blog and doc toolchain: https://github.com/oilshell/oil/tree/master/doctools https://github.com/oilshell/oil/tree/master/doctools It works well in practice and is correct and fast. Big caveat: this style is only for HTML that I generate myself, e.g. the blog and docs. There are a bunch of rules around matching tags in HTML5 that are subtle. Although one of the points here is that you don't have to do a full DOM-style parse and can ignore those rules for many useful cases. The other caveat is that HTML has a bunch of rules for what happens when you see a stray < or > that isn't part of a tag. This style makes it a hard syntax error, so it's really a subset of HTML (which has no syntax errors). For my purposes that is a feature rather than a bug, basically following Postel's law. I meant to write a blog post titled "why/when you can parse HTML with regexes" about this but didn't get around to it. There is also a caveat where parsing arbitrary name=value pairs with regexes isn't ergonomic, because it's hard to capture a variable number of pairs. However the point is that I wrote 5 or 6 useful and compact HTML processors that don't need that. In practice when you parse HTML you often have a "fixed schema". Concrete examples are generating a TOC from <h1>, <h2>, etc. and syntax highlighting <pre><code> blocks. Those all work great with the regex + call stack style. [1] http://www.oilshell.org/blog/2020/07/eggex-theory.html http://www.oilshell.org/blog/2020/07/eggex-theory.html edit: for completeness, another caveat is that the stack-based style is particularly bad for C++/Rust and arbitrary input because you could blow the stack, although we already limited the problem to "HTML generated ourselves"
- c-cube 6y ago
  What you're describing is using regex to _lex_ html, not parse it. The parser is easy to build once you have a lexer (after all most of XML's unpleasantness comes from escaping). It still isn't the same thing as parsing with regular expressions. Similarly you can't parse S-expressions with regular expressions, but if you have the lexer (e.g. with `lex` or other languages' equivalent) then the parser on top of it becomes absolutely trivial.

dragontamer 6y ago

I found a one-pass top-down "XML parser". Not like a proper SAX parser, no... the XML had to be specially formatted, almost like TOML. <whatever> <--- Parser parsed this as a new section <foo attrib=bar> <--- All "XML" had to be one-per-line </whatever> <---- parser ignored this It was an "XML parser" per se, but it really was just a linear one-pass parser that tricked me into thinking it was XML. So really, it was more like TOML (or .INI files) than like XML. But I guess the advantage of making it "bastard XML" instead of TOML is that maybe this worked with XML-editors or something. I dunno...

cbsks 6y ago
I’ve written an XML parser like this for a toy project. I passed the XML through a prettifier first so that it was in a standard format. It wouldn’t work for every XML file, but it worked on the files that I needed it for. I have also had success searching through html files with grep after passing them through a prettifier. It’s ugly, but 90% of the time, it works every time!
- dragontamer 6y ago
  The specific project I saw that did this had ALL of its configuration files in this "Bastard XML" format. Its ugly, but when 100% of your files you interpret match the one-per-line (and other clearly made-up rules), then it works 100% of the time!!

polote 6y ago

When I was working on a link parser in python for a crawler. I had two choices: 1. use some form of regex 2. use libxml and find links 1. was faster than 2. by a factor or two Does a link-only parser would have been faster ? Yeah probably but it is much more complex to do

benlivengood 6y ago
What was the average difference in accuracy? It's a fair tradeoff especially for a crawler where it's never guaranteed to reach all documents anyway.
contravariant 6y ago
Maybe I'm confused about the problem you're solving but regexp was faster than just: from lxml import html doc = html.from_string(response.content) doc.xpath('//a/@href') ?
- polote 6y ago
  Yes exactly. I'm not even sure XPath was faster than iter on a tags. But I would need to check on that one

xurukefi 6y ago

In my experience, a regex can be a much more robust solution than an XML parser depending on the use case. Back in the days when I did some webscraping I often had parsers throwing exceptions becacuse of ivalid HTML. More often than not I switched to regular expressions, which always worked out flawlessly.

metalliqaz 6y ago
"always flawless" is a bold claim
- oeiiooeieo 6y ago
  "I've never lost playing Russian Roulette"
- mumblemumble 6y ago
  It's hard to imagine any web scraping being described as "flawless". But there's a whole lot of room for "worked fine for my purposes." I think that it's actually a pretty great example of a case where capturing data from HTML may not be best modeled as a parsing task. You might not need a whole parse tree just to match some pattern and grab an associated string. And skipping the parse may enable you to get useful data out of a file that technically can't be parsed due to syntactic errors. It's a fairly classic precision/recall tradeoff situation.
btilly 6y ago
Yes. HTML isn't XML. As you discovered, HTML in the real world is allowed to be malformed in various ways, while XML is not. A compliant parser MUST barf on various kinds of malformed text. (Search for "fatal error" in https://www.w3.org/TR/REC-xml/ https://www.w3.org/TR/REC-xml/ to verify.) This makes XML parsers inappropriate for HTML parsing. Interestingly, even perfectly valid HTML may not be valid XML. To see that consider <b>this <i>example</b> carefully</i>.

chubot 6y ago

All you need to parse HTML is regular expressions (to recognize tags) and a stack (to match tags). Your programming language has a stack -- a call stack. So in practice all you really need is regular expressions. (Which I tend to call "regular languages" to make a distinction with Perl-style regexes [1], although they work fine too in practice for this case) Using the call stack in a more functional style is nicer than using the OOP style that s in the Python standard library, which is probably inherited from Java, etc. I have done this with a bunch of HTML processors for the Oil blog and doc toolchain: https://github.com/oilshell/oil/tree/master/doctools https://github.com/oilshell/oil/tree/master/doctools It works well in practice and is correct and fast. Big caveat: this style is only for HTML that I generate myself, e.g. the blog and docs. There are a bunch of rules around matching tags in HTML5 that are subtle. Although one of the points here is that you don't have to do a full DOM-style parse and can ignore those rules for many useful cases. The other caveat is that HTML has a bunch of rules for what happens when you see a stray < or > that isn't part of a tag. This style makes it a hard syntax error, so it's really a subset of HTML (which has no syntax errors). For my purposes that is a feature rather than a bug, basically following Postel's law. I meant to write a blog post titled "why/when you can parse HTML with regexes" about this but didn't get around to it. There is also a caveat where parsing arbitrary name=value pairs with regexes isn't ergonomic, because it's hard to capture a variable number of pairs. However the point is that I wrote 5 or 6 useful and compact HTML processors that don't need that. In practice when you parse HTML you often have a "fixed schema". Concrete examples are generating a TOC from <h1>, <h2>, etc. and syntax highlighting <pre><code> blocks. Those all work great with the regex + call stack style. [1] http://www.oilshell.org/blog/2020/07/eggex-theory.html http://www.oilshell.org/blog/2020/07/eggex-theory.html edit: for completeness, another caveat is that the stack-based style is particularly bad for C++/Rust and arbitrary input because you could blow the stack, although we already limited the problem to "HTML generated ourselves"

c-cube 6y ago
What you're describing is using regex to _lex_ html, not parse it. The parser is easy to build once you have a lexer (after all most of XML's unpleasantness comes from escaping). It still isn't the same thing as parsing with regular expressions. Similarly you can't parse S-expressions with regular expressions, but if you have the lexer (e.g. with `lex` or other languages' equivalent) then the parser on top of it becomes absolutely trivial.