Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Google Open-Sources Gumbo: C Library for Parsing HTML5

github.com

Post reply on HN
Print view View original

41–50 of 63 posts

Re: Google Open-Sources Gumbo: C Library for Parsing HTML5

#42

Post by jasonwocky »

avian wrote: post #34

I'm curious as to what was the motivation behind this project at Google. It seems to me that the only benefit of writing something like this in pure C would be performance gains over existing parsers, but it specifically says in the README that parsing performance was not one of the goals.

Most languages can be extended by C code without too much fuss. If the C is written in a platform-independent manner (which should be possible for this library), it's pretty much write-once, run-anywhere. Even if optimal performance wasn't a goal, it's still nice to have a single portable, performant html5 parser that's been tested against billions of pages.

Re: Google Open-Sources Gumbo: C Library for Parsing HTML5

#45

Post by clarry »

cliveowen wrote: post #23

I'm very excited because even though is useless for me is an enough small project to actually learn something of C programming...and from Google no less.

Coming from Google doesn't mean it's good code to learn from. Be careful not to pick up bad (and potentially disasterous, security-wise) habits like not checking for arithmetic overflows in functions such as enlarge_vector_if_full (vector.c) or maybe_resize_string_buffer (string_buffer.c) -- or not checking the return value from malloc.

Re: Google Open-Sources Gumbo: C Library for Parsing HTML5

#49

Post by badgar »

eliasmacpherson wrote: post #27
nostrademons wrote: post #9

Earlier quoted context omitted.

From a cursory glance at the Hubbub source: 1. Hubbub provides a SAX-style (callback-based) API, while Gumbo gives you a DOM-style (tree-based) struct directly. Hubbub is likely faster in this regard, Gumbo is easier to use out-of-the-box. 2. Gumbo is better tested. It's unclear whether Hubbub's 90% test coverage is "90% of the code is tested" or "90% of the tests pass", but Gumbo has 100% code coverage, 100% of html…

Have you seen this before? http://vtd-xml.sourceforge.net/faq.html#How_do_I_get_started... It's an xml parser that is neither DOM nor SAX. I haven't seen much mention of it before, except as a recommendation for Java devs. There's a C version too. It makes bold claims about performance. "Comparing with DOM, VTD-XML is significantly faster (up to 10x), more memory-efficient (up to 5x). Comparing with SAX/PULL, VTD-XML…

My undergrad thesis advisor, Bill McKeeman, wrote his parsers in this fashion. I implemented a parser using this model and extended its existing lexer.

The token stream is an array of 32 bit integers, each of which is the token type bitmasked onto an index into the input file of the start of the token. If you need the token text, you reparse. Caches can be implemented as small hash maps from token index to cached value.

The canonical AST is the CFG parse tree with fixups to convert recursion to children of a node type for a variable number of children. It is stored as an array of integers. The node is a sequence of integers, with one integer for the root followed by each child in sequence. Each internal node's value is the index of the CFG rule evaluated to produce the node, and the children of the node correspond to the CFG rule's right hand side (minus keywords). Terminals are stored as integer indexes into the token stream. Nonterminals are the integer index of the child internal node.

Bill has been a big name in compilers for the better part of 5 decades now, and he said he's been using this pattern for almost as long. It's ridiculously fast, which is why he used it decades ago for DEC.

Re: Google Open-Sources Gumbo: C Library for Parsing HTML5

#50

Post by nostrademons »

eliasmacpherson wrote: post #27
nostrademons wrote: post #9

Earlier quoted context omitted.

From a cursory glance at the Hubbub source: 1. Hubbub provides a SAX-style (callback-based) API, while Gumbo gives you a DOM-style (tree-based) struct directly. Hubbub is likely faster in this regard, Gumbo is easier to use out-of-the-box. 2. Gumbo is better tested. It's unclear whether Hubbub's 90% test coverage is "90% of the code is tested" or "90% of the tests pass", but Gumbo has 100% code coverage, 100% of html…

Have you seen this before? http://vtd-xml.sourceforge.net/faq.html#How_do_I_get_started... It's an xml parser that is neither DOM nor SAX. I haven't seen much mention of it before, except as a recommendation for Java devs. There's a C version too. It makes bold claims about performance. "Comparing with DOM, VTD-XML is significantly faster (up to 10x), more memory-efficient (up to 5x). Comparing with SAX/PULL, VTD-XML…

Interesting. I'm not familiar with the library. I'm familiar with the general programming model of parsing a document into a number of tokens and then encoding document structure into offsets between tokens.

It wouldn't have worked for Gumbo's purposes because

1. Gumbo captures a lot more information than can fit in a 64 bit token. For example, Gumbo decodes entity references; this requires that text be available in a fresh buffer because each individual character might be something different than the source text.

2. One of Gumbo's goals was to make it easy to write bindings in other languages. Most languages can bind to C structs easily, but binding to C function calls often requires a much more verbose preamble to setup args, return types, conversions, etc. (I was actually thinking of LLVM when I designed Gumbo's API, since the project it was initially for at the time was looking at LLVM as an embedded JIT. Binding to a struct that's C-formatted just requires defining a new type, but binding to a function call requires codegenning a lot of argument setup.)

Post reply on HN