Josh Haberman

I’m in Portland this weekend and picked up a few more parsing-related books. I wanted to list them here, since I wasn’t previously aware they existed despite my intense interest in this field.

The first is Selected Papers on Computer Languages, by Donald Knuth. I’m embarrassed to say that I wasn’t previously aware how much of the early theories and models about parsing come from Knuth. This book contains several of the original papers about the theories of LL(k), LR(k), etc:

The second is The Theory of Parsing, Translation, and Compiling. Volume I: Parsing, by Alfred Aho and Jeffrey Ullman. If those names sound familiar, it’s because they’re the guys who wrote the Dragon Book.

The last is Beautiful Code: Leading Programmers Explain How They Think. I had seen this book at various bookstores before but never felt compelled to look at it. But today I flipped through it and realized that many of the essays are about parsing:

• A Regular Expression Matcher, by Brian Kernighan. “I suggested to Rob [Pike] that we find the smallest regular expression package that would illustrate the basic ideas while still recognizing a useful and nontrivial class of patterns. Ideally the code would fit on a single page. Rob disappeared into his office. As I remember it now, he emerged in no more than an hour or two with [these] 30 lines of C code.
• Finding Things, by Tim Bray. Deals with searching logfiles with regular expressions.
• Correct, Beautiful, Fast (in That Order): Lessons from Designing XML Verifiers, by Elliotte Rusty Harold. Deals with parsing/verifying XML, what more needs to be said?
• Python’s Dictionary Implementation: Being All Things to All People, by Andrew Kuchling. Not about parsing, but about hashing, which I have quite recently been very interested in.

And though I mentioned it once before, I just want to reiterate how awesome Parsing Techniques: A Practical Guide is. Your guidebook to the entire field of parsing.