Building a simple Parser and Lexer in PHP

Compiler design is a complex endeavor, but also one of the most satisfying projects you can undertake. Lately I’ve been interested in compiler and parser design; my interest piqued by Debasish Ghosh’s wonderful book, DSLs in Action. Web development in general provides a far less opportunity to work in the domain of compiler or interpreter design. So the idea of building DSL’s was the perfect excuse for learning parser design.

To design a good DSL it is necessary to have some compiler design knowledge under your belt. The classic Dragon book is usually the first choice of reference to pickup on compiler design, but it is too theory oriented, and what I needed was something to get me started with writing code quickly, rather than mull over automata theory, syntax trees and other compiler theory concepts. My first choice was Ronald Maks Writing Compilers and Interpreters. Although it is an incredible book, it is rather elaborate in its presentation. What I instead wanted was a cookbook style presentation, using which I could quickly design some working code, and only later refer to the above books for more in-depth understanding.
(more…)

Read More