The blog » Design patterns are from hell^2! Some anonymous soul emailed me regarding my “Design patterns are from hell!” Post, arguing that “somehow, knowing patterns exist is the same as knowing different data structures exist” and that “understanding the different ways for creating objects (hello creational patterns) is like understanding the implications of deciding to use a dequeue rather than an array or rather than a linked list.” I was also bravely asked what I thought about these statements. Well, guess what, since one can never diss design patterns enough, this is what I think… They’re from hell! No, there are no similarities between data structures and algorithms on one side and design patterns on the other side! Rather, there are lots of distinctions but the perhaps most important one is that data structures and algorithms are language independent whereas design patterns are language dependent.
A second important distinction is that data structures and algorithms do not come encumbered with preferred usages. Data Structures and Algorithms with Object-Oriented Design Patte. Data Structures and Algorithms by John Morris. Parser Combinators. Many excellent ideas from functional programming apply to object oriented programming (functions are objects too, you know). Parser combinators in particular are a technique with a long history in the functional programming community. This is a blog post, so I’m not going to give a proper bibliography of the idea; suffice to say that it goes back decades, and that Phil Wadler, and Erik Meijer, among others, have done important work in this area. I myself was inspired to look into the topic by Martin Odersky’s Scala tutorial. I’ve built a simple parser combinator library in Smalltalk, and it seems to work out very nicely. I thought it would be good to write about it here, coming at the topic from an OO perspective.
So, what are parser combinators exactly? The basic idea is to view the operators of BNF (or regular expressions for that matter) as methods that operate on objects representing productions of a grammar. To make this concrete, lets look at a fairly standard rule for identifiers: