

Comparse – Monadic Parsing Library



==================================






We've been all taught that creating a parser boils down to writing a context free grammar and then using some library like [Bison](http://www.gnu.org/software/bison/ "Bison"). By the way, such a library exists for JavaScript, too, it is called [Jison](http://zaach.github.io/jison/ "Jison"), and CoffeeScript uses it for parsing the source code.



We've been all taught that creating a parser boils down to writing a



context free grammar and then using some library like



[Bison](http://www.gnu.org/software/bison/ "Bison"). By the way, such



a library exists for JavaScript, too, it is called



[Jison](http://zaach.github.io/jison/ "Jison"), and CoffeeScript uses



it for parsing the source code.






On the other hand, I like the approach of functional parsers such as [Parsec](http://legacy.cs.uu.nl/daan/parsec.html) or [attoparsec](https://github.com/bos/attoparsec "attoparsec"), both written in Haskell. They allow for building complex parsing functions by combining simpler ones in various ways. A parsing function, once written, can be easily reused in other contexts.



On the other hand, I like the approach of functional parsers such as



[Parsec](http://legacy.cs.uu.nl/daan/parsec.html) or



[attoparsec](https://github.com/bos/attoparsec "attoparsec"), both



written in Haskell. They allow for building complex parsing functions



by combining simpler ones in various ways. A parsing function, once



written, can be easily reused in other contexts.






Even though JavaScript and CoffeeScript are not pure functional languages, they do implement the most important functional paradigm: functions are firstclass data that can, for instance, be passed as arguments to higherorder functions. Douglas Crockford also [demonstrated](https://www.youtube.com/watch?v=b0EF0VTs9Dc "Monads and Gonads") how the powerful concept of [monads](http://en.wikipedia.org/wiki/Monad_(functional_programming) "Monad") can be implemented in JavaScript.



Even though JavaScript and CoffeeScript are not pure functional



languages, they do implement the most important functional paradigm:



functions are firstclass data that can, for instance, be passed as



arguments to higherorder functions. Douglas Crockford also



[demonstrated](https://www.youtube.com/watch?v=b0EF0VTs9Dc "Monads and



Gonads") how the powerful concept of



[monads](http://en.wikipedia.org/wiki/Monad_(functional_programming)



"Monad") can be implemented in JavaScript.






So I was wondering whether a decent monadic parser could be written in CoffeeScript. The result is Comparse, a monadic parsing library, which is described in the rest of this text. Frankly, I didn't expect to get something nearly as elegant as the Haskell parsers mentioned above, primarily because Haskell has special syntactic sugar for monad programming (the “do” notation). Much to my surprise, monadic functions and their combinations can be written quite nicely in the CoffeeScript syntax (but maybe I am just weird and biased).



So I was wondering whether a decent monadic parser could be written in



CoffeeScript. The result is Comparse, a monadic parsing library, which



is described in the rest of this text. Frankly, I didn't expect to get



something nearly as elegant as the Haskell parsers mentioned above,



primarily because Haskell has special syntactic sugar for monad



programming (the “do” notation). Much to my surprise, monadic



functions and their combinations can be written quite nicely in the



CoffeeScript syntax (but maybe I am just weird and biased).






The implementation takes into account the lack of tail recursion optimization in JavaScript, so recursive functions are mostly rewritten using loops. Also, since JavaScript is _not_ a pure functional language, side effects and nonlocal variables are used in a few places for improving efficiency.



The implementation takes into account the lack of tail recursion



optimization in JavaScript, so recursive functions are mostly



rewritten using loops. Also, since JavaScript is _not_ a pure



functional language, side effects and nonlocal variables are used in



a few places for improving efficiency.






* [Annotated source code](comparse) 