You are here

Book Review: The Definitive ANTLR 4 Reference

The Definitive ANTLR 4 Reference

Disclosure: I received a complimentary review copy of this book.

I would have happily bought a copy, as I have bought copies of author Ter Parr's previous books, because he writes a different kind of "compiler" book.  The Definitive ANTLR 4 Reference integrates two of Parr's previous lines of thinking; it's a great introduction to the ANTLR4 parser, but even more, it's an introduction to how to think like a real-world compiler writer.

Compiler-Writing in the Real World

How is being a real-life compiler writer different than the wonderful world of set and graph theory presented in books like the Dragon book?  Well, I felt a great peace come over me when I read Parr's observations about the "language definition" for R:

We must deduce R's structure by wading through reference manuals, examples, and a formal yacc grammar from the existing implementation.

And that is how I spend a good bit of my time: wading through the ISO SQL standard, online documentation for quite a few existing implementions, a book or two, and maybe some blog postings to figure out what UPFOODELSERT should actually do to make our customers happy. (This is one of the few redeeming features to the "make them fix bugs" introduction most new hires get to the product: when the new hire is also a new grad, he or she will be somewhat inoculated against the shock of learning that nobody can say exactly what UPFOODELSERT does, only that someone important wants it, pronto.)

Learning by Doing

One of the things I like about this book, both from the perspective of an experienced ANTLR wrangler and from the (notional) perspective of someone just picking up the tool, is its emphasis on runnable examples: there's a small, but interesting and complete example in section 1.2 on page 6. Except for a break in Chapter 2 to introduce concepts, almost every section of the book uses a working example grammar. These examples are finely crafted; even heavily annotated, they typically take up less than a page, and they address some of the gnarlier parts of the compiler art, e.g., the problem of the >> in foo<bar<T>>, or using newlines as statement terminators.

One of my few complaints about this book is that specific bits of information can be difficult to pick out of this wealth of material, but given the choice I would go with Parr's approach.  On balance, having the working examples brings the concepts to life and makes the material much easier to learn.

The Honey Badger

ANTLR4 is a major rewrite of the ANTLR system to use an algorithm Parr calls Honey Badger -- an "adaptive LL(*)" algorithm that eats everything. There is not a lot of information about the algorithm per se in the book, but it does adequately call out the differences between adaptive LL(*) and the LL(*) algorithm in ANTLR3. The final non-reference chapter of the book does contain a short description of the algorithm ANTLR4 uses to remove left recursion from its generated grammars. If you're not familiar with left-recursion, trust me: you'll be very happy this feature exists.

In Summary

This is a very readable and useful introduction to ANTLR4 and, more generally, to using a parser generator to solve many language recognition problems that would otherwise require some contorted logic and unpleasant to maintain regular expressions.  I recommend it highly.

 

Add new comment