Timo Denk's Blog

Haskell BNF Parser

· Timo Denk

This is a brief update about a project I have been working on lately. It’s my first bigger Haskell project, and about parsing a Backus-Naur form (BNF) expression and returning it in JSON format. More formally, this can be seen as compilation between two languages, namely BNF and JSON.

BNF — JSON

A Backus-Naur form is a way of writing down the rules of a context-free grammar. For instance, an integral value could be defined as follows:

<integer> ::= <digit>|<integer><digit>
<digit>   ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

The same content can be expressed in JSON as well:

{"rules":[{"name":"integer","expr":[[{"ref":"digit"}],[{"ref":"integer"},{"ref":"digit"}]]},{"name":"digit","expr":[[{"l":"0"}],[{"l":"1"}],[{"l":"2"}],[{"l":"3"}],[{"l":"4"}],[{"l":"5"}],[{"l":"6"}],[{"l":"7"}],[{"l":"8"}],[{"l":"9"}]]}]}

Even though the JSON looks more verbose than the BNF, it is easier to process in other programming languages.

Haskell Project

The Haskell project consists of three parts, namely app, src, and test. It was developed in IntelliJ using the plugin “IntelliJ-Haskell”.

Source

The project’s source (src folder) contains the actual parser library. That is Haskell functions, which parse a string and return it in an internal-type representation (BNFDefinition). The internal types come along with an implementation of the instance ToJSON. If another Haskell project was going to use the parser logic it could simply import this library and make use of the functions.

Application

The application (app folder) starts a scotty web server and parses the request body of incoming requests using the aforementioned library. The response is in JSON format. Alongside with the conversion API-endpoint comes a minimalistic HTML site for testing.

The BNF parser application starts a web server and serves a simple HTML page for manual conversion from BNF to JSON.

Tests

The tests (test folder) consist of three kinds of tests:

  • Unit tests: The functionality of almost every piece of the parser is being tested with a set of multiple rules, which it must satisfy.
  • Integration tests: The repository contains three examples of valid, more extended BNFs, and a few invalid ones. During integration testing, the parser library must accept the valid ones and reject the invalid samples.
  • Property tests: The property testing validates that the parse function is inverse to show. That means, for any valid, randomly generated BNF $x$, the property$$\text{parse}\left(\text{show}\left(x\right)\right)=x$$ must hold.

Usage

The project can be found on GitHub https://github.com/Simsso/BNF-Parser. The repository contains a Dockerfile which starts the server. More details can be found in the repository’s README.md file.