How LR(2) Parsers Work

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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s