brenoafb

Using BNFC with Stack

BNFC is a “compiler construction tool generating a compiler front-end from a Labelled BNF grammar.” We can write grammars in a .cf file and generate a base project by issuing the command

bnfc -m

One of the main tools for working with Haskell projects is Stack. The problem is that BNFC generates a whole project structure for you to work with, making it difficult to make it work with Stack.

Thankfully, Stack has no problems building the Alex (lexer) and Happy (parser) files generated by BNFC. So we can generate a BNFC project and copy the files that we want to use to a Stack project.

Running BNFC to generate the base files

First, put the grammar for your language in a .cf file. Here is the grammar for a arithmetic expression language.

EAdd. Exp  ::= Exp  "+" Exp1 ;
ESub. Exp  ::= Exp  "-" Exp1 ;
EMul. Exp1 ::= Exp1 "*" Exp2 ;
EDiv. Exp1 ::= Exp1 "/" Exp2 ;
EInt. Exp2 ::= Integer ;

coercions Exp 2 ;

Save this as Language.cf. Now, run BNFC to generate the base project files.

~ bnfc -m Language.cf

8 rules accepted

Use Alex 3.0 to compile LexLanguage.x.
writing new file ./AbsLanguage.hs
writing new file ./PrintLanguage.hs
writing new file ./LexLanguage.x
writing new file ./ParLanguage.y
writing new file ./TestLanguage.hs
writing new file ./ErrM.hs
writing new file ./SkelLanguage.hs
writing new file ./DocLanguage.txt
writing new file ./Makefile

Creating a Stack project

To create a Stack project with the default template, run stack new lang. Here, lang is the name of the project. You can name it however you want.

The files we are going to use are the Haskell, Alex, and Happy source files (.hs, .x, and .y respectively). Move these files (excluding TestLanguage.hs) to the src directory inside the directory generated by Stack. Replace the contents of the default app/Main.hs with the contents of TestLanguage.hs. For reference sake, I also like to keep the .cf grammar file in a folder grammarinside of the project.

The folder structure should now look something like the following.

├── language
│   ├── app
│   │   └── Main.hs
│   ├── ChangeLog.md
│   ├── grammar
│   │   └── Language.cf
│   ├── language.cabal
│   ├── LICENSE
│   ├── package.yaml
│   ├── README.md
│   ├── Setup.hs
│   ├── src
│   │   ├── AbsLanguage.hs
│   │   ├── ErrM.hs
│   │   ├── LexLanguage.x
│   │   ├── Lib.hs
│   │   ├── ParLanguage.y
│   │   ├── PrintLanguage.hs
│   │   └── SkelLanguage.hs
│   ├── stack.yaml
│   └── test
│       └── Spec.hs

Telling Stack to build the Alex and Happy files

In the package.yaml at the root of the project, under the executables section, add a subsection build-tools and add Happy and Alex under it. The executables section should look something like this.

executables:
  language-exe:
    main:                Main.hs
    source-dirs:         app
    ghc-options:
    - -threaded
    - -rtsopts
    - -with-rtsopts=-N
    dependencies:
    - language
    build-tools:
    - Alex
    - Happy

BNFC also uses the Data.Array library, so add it under dependencies.

dependencies:
- base >= 4.7 && < 5
- array

You may also edit the header of the package.yaml file with relevant information if you wish.

Trying it out

You can now run stack build to verify that everything builds correctly and run the default main provided by BNFC to print out the AST of some program in your language.

~ stack run
1 + 2 * (2 + 3 * 5)

Parse Successful!

[Abstract Syntax]

EAdd (EInt 1) (EMul (EInt 2) (EAdd (EInt 2) (EMul (EInt 3) (EInt 5))))

[Linearized tree]

1 + 2 * (2 + 3 * 5)

Final Remarks

You may want to remove the SkelLanguage.hs if you do not wish to use it. Also, the ErrM.hs seems to have the same behavior as the Either type, which would be nicer to use.

In the future, it would be nice to have a Stack template or at least a shell script that accepts a .cf file and automates the process. This should be pretty easy to do.

These days I prefer using Parsec instead of BNFC, which provides an easy and flexible way of specifying a language front-end in Haskell. The process is made even easier using the Token module, although BNFC can still be helpful due to its ability to generate front-ends for a variety of languages.