Prototyping With BNFC-meta

In a recent post Roman Cheplyaka showed off an extension he had made to wren gayle romano’s unification-fd which made it even easier to use. I decided I wanted to give it a spin, by starting on a little language idea I’ve been kicking around. Thinking about the front end, reminded me of one of my favorite libraries for prototyping, Jonas Duregard’s BNFC-meta.

BNFC-meta is built on BNFC, which allows one to specify a labelled BNF grammar and it will generate the Haskell types and parser. BNFC-meta takes it one step further and let’s you specify the grammar through a quasiquoter and generates the types, parser, pretty printer and a quasiquoters for your language using Template Haskell.

Hello World

To use this code you will need the package hosted on github so add to your stack.yaml:

- location:
   git: https://github.com/JonasDuregard/BNFC-meta
   commit: b285a7c74bf76f5a9f643737803b2379364ada00

and add to your extra-deps:

extra-deps: 
  ['BNFC-meta-0.5', 'alex-meta-0.3.0.9', 'happy-meta-0.2.0.9']

Let’s create a grammar for the lambda calculus:

{-# LANGUAGE TemplateHaskell, QuasiQuotes #-}
module Thump.FrontEnd where
import Language.LBNF.Compiletime
import Language.LBNF(lbnf, bnfc)
bnfc [lbnf|
Ap.  Expr ::= Expr Expr;
Lam. Expr ::= "\\" Ident "->" Expr;
Var. Expr ::= Ident;
|]

bnfc is Template Haskell function and it creates the types:

data Expr = Ap Expr Expr
          | Lam Ident Expr
          | Var Ident -- Ident is a built in that is a newtype 
                      -- around String. 

along with the parser pExpr, a lexer myLexer which can be combined:

> pExpr $ myLexer "\\x -> x"
Ok (Lam (Ident "x") (Var (Ident "x")))

Although for debugging it is easier to use the quasiquoter expr:

> [expr| \x -> x |]
Lam (Ident "x") (Var (Ident "x"))

And we can use the pretty printer printTree:

> putStrLn $ printTree [expr| \x -> x |]
\ x -> x

Pretty cool. Let’s see if our parser can handle a more complicated expression:

> [expr| (\x -> x) y |]
<interactive>:9:7: error:
  • syntax error at line 1 due to lexer error
  • In the quasi-quotation: [expr| (\x -> x) y |]

Oh no!

We need handle parentheses. There is built in support for this.

bnfc [lbnf|
Ap.  Expr  ::= Expr Expr;
Lam. Expr ::= "\\" Ident "->" Expr;
Var. Expr ::= Ident;
_.  Expr ::= "(" Expr ")" ; -- This is what was added
|]

Now it works:

> [expr| (\x -> x) y |]
Ap (Lam (Ident "x") (Var (Ident "x"))) (Var (Ident "y"))

But Wait There’s More!

There was actually a warning we should have paid attention to when our code compiled:

Warning: 8shift/reduce conflicts

Our grammar is ambiguous. We can fix this by making the precedence explicit and providing “coercions”

bnfc [lbnf|
Lam. Expr ::= "\\" Ident "->" Expr1;
Ap.  Expr1 ::= Expr1 Expr2;
Var. Expr2 ::= Ident;
coercions Expr 2 ; -- Shortcut for _.  Expr ::= "(" Expr ")" ;
|]

All of syntax and rules for BNFC are covered in the documentation. rules are particularly nice.

There’s Even More

I haven’t covered all the features. You can add antiquotes to the quasiquoter, the quasiquoter includes a rarely seen pattern quasiquoter, and BNFC has loads of features.

There are downsides (it is difficult to customize the lexer), but for prototyping it is very efficient way to get something you can use. Who knows, it might be all you need.