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

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

• Graham Hutton and Erik Meijer, Functional Pearl: Monadic parsing in Haskell (1998)
• Graham Hutton, Higher-order Functions for Parsing (1992)
• Jeroen Fokker, Functional Parsers (1995)

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.

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.

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).