Haskell – How to best to represent a programming language’s grammar

compiler-constructiongrammarhaskellrepresentation

I've been looking at Haskell and I'd quite like to write a compiler in it (as a learning exercise), since a lot of its innate features can be readily applied to a compiler (particularly a recursive descent compiler).

What I can't quite get my head around is how to represent a language's grammar in a Haskell-ian way. My first thought was to use recursive data type definitions, but I can't see how I use them to match against keywords in the language ("if") for example.

Thoughts and suggestions greatly appreciated,

Pete

Best Answer

You represent programs using mutually recursive algebraic data types, and to parse programs you use parsing combinators. There are a million flavors; you will find three helpful tutorial papers on the schedule for my class for Monday, March 23, 2009. They are

The Hutton and Meijer paper is the shortest and simplest, but it uses monads, which are not obvious to the amateur. However they have a very nice grammar of and parser for expressions. If you don't grok monads yet, Fokker's tutorial is the one.

Related Topic