Many, many years back when I was a grad student, I picked up a phenomenal book on parsing: Parsing Techniques: A Practical Guide by Grune and Jacobs. That book was indispensable when I was teaching Stanford’s CS143 course on compiler design, and it taught me most of what I now know about parsing. Plus, it’s a great example of how to write a lucid introduction to difficult technical concepts.
One style of parsing that I didn’t learn a decade ago was LR(k) parsing with k > 1. This is a fairly uncommon style of parsing – I think it’s primarily of theoretical interest – but I was intrigued nonetheless. By following some leads from the book, asking some questions around on Stack Exchange, reading Knuth’s original paper On the Translation of Languages from Left to Right, and working through a few examples, I think I finally got a handle on how LR(2) parsing works, and the techniques that came up there are precisely what’s needed to handle more general LR(k) parsing.
I put together a writeup on LR(2) parsing on Stack Overflow, and I’m hoping that it’s a useful resource for other people interested in LR(k > 1) parsing in the future. It was fun to work through the details and examples, and I learned a bunch in the process!
