Josh Haberman

I’ve been quiet about Gazelle news lately, but since I wrote last I’ve hit 3 of my 6 goals for Gazelle 0.2, and one that I hadn’t thought to include. To review those goals and see which ones I’ve completed:

• complete Strong-LL(k) lookahead support. (it’s not 100% complete yet, but it’s definitely solid enough for a 0.2 release)
• a command-line compiler program (gzlc) that takes reasonable options and is simple enough to use by reading its –help
• a “tour” section for the manual
• a command-line program (gzlparse) that can output the parse tree in a useful format, so you can see how Gazelle parses your input text.
• a test suite, so that when people report bugs I can add the bugs to the test suite and not regress.
• (stretch): make Gazelle self-hosting, so that the parser is more robust and easier to understand than the hand-written recursive descent parser I’m currently using. I don’t want people to have to deal with corner-case parser bugs.
• a way to visualize grammars, to spot-check them against your expectations

It’s the grammar visualization that I forgot to include. I mentioned parse tree visualization a few blog posts ago, but this is different — one is visualizing how a bunch of text got parsed, the other is visualizing the grammar itself.

It still has room for improvement, but here is what my grammar visualization currently looks like for JSON. You can see an NFA for each one of your rules, a DFA for each state of lookahead, and the DFAs that do the lexing.

The latest code from Git (note that I recently moved from repo.or.cz to Github) can generate these grammar dumps — just pass ‘-d’ to gzlc.

Observation #1: stop-the-world garbage collection is a thorn in the side of latency-sensitive applications.

Observation #2: we will very soon have more cores than we know what to do with.

Prediction: fully concurrent garbage collection is the future of automatic memory management. I’m talking garbage collectors that run in other threads and clean up after me without ever stopping me in the middle of what I’m doing.

It will almost certainly be more expensive in terms of total CPU time, and probably can’t be as aggressive in terms of what it can reclaim at any point in time, but for most applications the latency guarantees will far outweigh.

Discuss.