BNF Converter - from a Small Idea to a Big System
Björn Bringert, Markus Forsberg, Michael Pellauer, Aarne Ranta,...

% NOTE: this is a txt2tags file.
% Create an html file from this file using:
% txt2tags retrospect2006.txt

%!target:latex


==Abstract==

The BNF Converter (BNFC) is a high-level compiler tool. The main idea
is to use a single source file - a BNF grammar - to generate a complete
compiler front end: lexer, parser, and pretty printer, as well as 
a language document. The single-source approach reduces the amount
of manually written code (down to just 1% compared to traditional tools),
and helps keep the modules in syncrony. Another dimension is the
multi-platform idea: the compiler components are generated in 
many different programming languages and their accompanying compiler
tools (C, C++, Java, Haskell, OCaml).

This paper traces the development of BNFC from the first proof-of-concept
implementation to the current state. The role of the implementation language
(Haskell) is discussed, as well as the different design decisions taken.
A survey is moreover made of the usage of BNFC, which is spread to many
different projects, partly thanks to the inclusion of BNFC in the Stable
distribution of Debian Linux.

In addition to a software development chronicle, this papers serves as
a summary of the different features of BNFC.



==The initial idea==

From GF: to use a grammar to derive parser, pretty-printer, and abstract syntax.

Purely declarative language implementation
- no Turing-complete semantic actions
- guaranteed portability


Example (show a grammar).


==Why semantic actions are harmful==

They destroy 
- complexity, since
linear LALR parsing can become exponential or undecidable.
- portability, if actions are written as arbitrary code
in the host language.
- reversibility, if the source string cannot be computed
from the resulting tree.
- inspectability, if grammatical well-formedness can
depend on decisions taken by the semantic actions.


A fundamental design principle has thus been that semantic actions
are only allowed insofar as they don't imply any of the harmful
consequences. Thus BNFC allows the following kind of actions:
- construction of syntax trees via data constructors (original version 2002)
- identity mappings, a.k.a. semantic dummies (``_``=) (2002)
- permutations of arguments via profiles (2004)
- noncanonical functions computed via ``def`` definitions (2006)


Of the later additions, profiles and ``def`` definitions may affect
complexity, and ``def`` definitions may also affect reversibility.
(How do we defend this?)



==The challenge of simplity==

The first reaction of almost everyone exposed to BNFC is "This is so simple!"
The second is either "This is trivial - I could have done this myself" or
"How impressive that it can be so simple".

Simplicity has been a challenge in at least three ways:
- to make it work in realistic scale without e.g. cluttering the generated
abstract syntax too much (see below)
- to //keep// it simple, avoid making it more powerful/rich/complex
- to convince potential users that it is still useful (a problem with
experienced compiler authors rather than newcomers)



==The first implementation==

Year 2002.

As in GF: the parser was an interpreter of the grammar.

"World's Smallest Compiler Compiler" implemented on 80 lines of Haskell, shown
in an old lecture
[WSCC http://www.cs.chalmers.se/Cs/Grundutb/Kurser/komp/2003/lectures/ccc05.html]

First step: generate the code (parser in Happy, using Markus's GF-to-Happy 
implementation, lexer in Alex, document in Latex, other modules in Haskell).

Example: show the code from the grammar in previous section, give statistics
on numbers of lines.

One milestone: implement the BNF grammar format in the format itself.



==Extensions==

We started to write lots of grammars, and found the following extensions
and shorthands useful:
- built-in types Int, String, Double, Char, Ident
- precedence levels and dummy coercions
- Haskell's list types
- internal rules
- separator, terminator, coercions, and rules macros


Later extensions and motivating examples (approximative years - to verify)
- Prolog's upper/lower case identifiers - regular expressions for token types 2003
- Agda - layout syntax 2003
- HOAS - profiles 2004
- Compiler messages - position tokens 2005
- GADT 2006
- Limited semantic actions - def clauses (Norell) 2006
- Alternative concrete syntaxes - multiple views 2006



==Back ends==

Cashing out the value of abstract grammar definition
- Java, C, C++ (Pellauer 2003)
- Java 1.5 (Bringert 2004)
- OCaml (Johannisson 2006)


==Nonstandard back ends==

Using BNFC to other tasks than programming language compilers
- XML - the use of BNFC as data exchange format (Ranta 2004)
- GLR in Haskell (Callaghan) - from GF to BNFC (Ranta 2005)


==Projects==

C (Persson) 2003

Java

GF and GFC 2003

ASN-1 2004


==Spreading==

Teaching

Research projects

Industry

Debian




==Future prospects==

We want to avoid creeping featurism, and making the formalism
essentially more powerful.

This is what distinguishes BNFC from most other compiler tools
(examples!) - in them, the users can do "whatever they want",
but the price is that it gets
- more complex to learn and to use
- more difficult to port
- maybe one loses the printer-parser symmetry



==Known shortcomings==

Error messages

White space handling

Overlapping ``token`` definitions



==Evaluation and reflection==

Code maintenance is giving trouble

The role of Haskell?


