Shift-Reduce Parser in Haskell

Quick links: demo video, GitHub repository (README coming soon).

In the spring of 2022, I took a compiler design computer science elective at Harvey Mudd College. The course covered the whole process of compilation, from parsing through intermediate optimization to code generation, with assignments consisting of implementing concepts in Haskell. At the end of the course, we took on independent final projects to dive deeper into something not fully covered in the course.

I chose to implement a shift-reduce parser. This type of parser had been discussed briefly in class, but given its importance in the real world, I felt it merited a more extensive treatment. Relying primarily on this handout from a Stanford class, I taught myself how an LR(0) parse table is constructed and then implemented a parser for a simple LR(0) grammar from scratch in Haskell. More technical information and a live demonstration can be found in the video I recorded for class, and the full source code can be found in this GitHub repository.