Haskell - How to best to represent a programming language's grammar?

Question

Hey,

I've been looking at Haskell and I'd quite like to write a compiler (as a learning exercise) in it, since a lot of it's innate features can be readily applied to a compiler (particularly a recursive decent 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

Answer 1

I can't tell from the tone of your question whether this is the first time you're attempting to write a compiler, or if you've written compilers before and are looking for advice specific to Haskell. If you're already a compiler guru, what little advice I have to offer isn't going to help. :)

Programming language grammars are commonly represented in BNF form, which can be used by tools like Yacc or Bison to parse source code. I don't know if this counts as a Haskell-ian way to do it, but it's the only way that I've heard of. With some digging around you can probably dig up a tool to generate Haskell code from a BNF grammar; I found this tool which claims to be able to do that.

A quick Google search turned up this BNF grammar for Haskell, and there are probably others out there, in case you want to write a compiler for Haskell (maybe you'd like to write a Haskell compiler in Haskell?) BNF grammars for C and Java seem to be popular.

Finally, if you're looking for a book about compiler design, the classic text is "The Dragon Book".

Answer 2

Unfortunately there's no Haskell grammar for ANTLR, but perhaps you can use the link cited above to create one. ANTLR is a great Java-based parser generator.

Steve Yegge has a nice blog about writing compilers, if you need more motivation. It's entertaining.

Answer 3

A recursive data type is fine for this. For example, given the language:

expr ::= var
      |  "true"
      |  "false"
      |  "if" expr "then" expr "else" expr
      |  "(" expr ")"

an example expression in this language would be:

if true then x else (if false then y else true)

Your Haskell data type would look something like this:

data Expr = Var String
          | Lit Bool
          | If Expr Expr Expr

Your parser then takes care to translate, e.g., x into Var "x", and true into Lit True, etc. I.e.:

parse "if x then false else true" 
  ==  If (Var "x") (Lit False) (Lit True)

For writing parsers you can roll your own using the techniques mentioned in Norman's answer, or using Parsec or use parser generators like Happy.

Answer 4

Maybe you can look at some real-world projects to see how they do it?

Less than a week ago, the Language-Python project was announced on the Haskell-Cafe mailinglist. It's a Python parser implemented in Haskell, using the Happy parser generator and Alex lexer generator.

And of course, there is Pugs, an implementation of Perl 6 in Haskell (the first implementation of Perl 6 that conforms to a significant subset of the Perl 6 specification).

Answer 5

For a real-world example of parsing and representing C in Haskell you can take a look at language-c.