The delightql language implementation uses the tree-sitter parser generator as its front-end.

The TLDR for this decision is simple:

1. keep the tooling tied directly to the language’s source of truth
2. create a formal specification for the syntax of the language

The rest of this post just explains these two points.

One source of truth

I think this one is self-explanatory: the exact same grammar I use to parse the language is the exact same grammar that I can use in neovim for highlighting and text-objects. This makes tooling a first-class citizen with the language implementation.

But I take it further. As part of the delightql binary I have embedded the parser library as a dynamic library that you can extract with a subcommand:

DIR=$(mktemp -d ) ; dql editor export --dir $DIR ; tree $DIR
/tmp/tmp.q1OUmPGbmW/
    grammar/
    parser/
    queries/

written (parser for x86_64-unknown-linux-gnu, tree-sitter ABI 15)
/tmp/tmp.q1OUmPGbmW
├── grammar
│   ├── conflicts.js
│   ├── grammar.js
│   ├── package.json
│   ├── tokens.js
│   └── tree-sitter.json
├── parser
│   └── delightql.so
└── queries
    └── delightql
        ├── highlights-primary.scm
        ├── highlights.scm
        └── highlights-sigilforward.scm

5 directories, 9 files

To be very clear, the build process that generates the delightql binary for different architectures and OSes also builds the .so-equivalent parser and embeds it within the dql binary for later extraction.

Parser generators have existed for a very long time, but it wasn’t until tree-sitter came along that the tooling use-case of parsing feel, in some sense, solved.

This is one of the important things about tree-sitter: that it created a de facto standard. This is not to discount its other qualities: the GLR algorithm; the robustness of an algorithm designed for incremental parsing and error node generation; and that the C artifact it generates can be embedded in nearly everything. These are important too.

Formal specification for Delightql

When I started building delightql I was adamant that the language’s semantics and syntax be both formally specified.

To what degree this is actually advantageous, I am not sure, but I did not want the implementation to decide ambiguity nor to dissuade the creation of alternative implementations.

Semantics is not the same as syntax, as we all know, but it can be pretty close, if you work hard at it. Very minimal languages, especially homoiconic ones, are known for this quality and my hope was to place delightql among these.

To repeat: delightql’s syntax and semantics should be very closely aligned. So any advantage accrued to a formal syntactic specification should aid in the semantics.

Many languages author an ex post facto EBNF, but by using tree-sitter as the parser generator for the front-end I could specify first and then get both the specification and the implementation at the same time.

Benefits and drawbacks

I am well aware that using a parser generator – think YACC, ANTLR, etc. – is considered too “far from the metal”. This is an opinion I’ve seen a lot in the language implementation community. The argument goes that since it’s easy enough to write your own recursive descent parser you can be much more in tune with your grammar and write good error handling.

I buy that argument, and I also buy the argument that a parser generator doesn’t necessarily save you that much time in the long run.

Nevertheless, if I had to do it over I would still start with a parser generator. And if I had to explain a central emotional reason for this it would be that starting with a grammar specification feels more correct. A grammar is stripped of everything except for the essence.

When I look at an EBNF (or any other grammar specs like PEG, etc.) I see a data structure. I see a containment relationship, or a sum type (choice) or a product type (concatenation). I see the entire model without the ceremony of an implementation language.

And in the end, it might be a personal choice that matches how my brain works. I would rather see the data structure than think of how I would lex tokens and assemble a parse tree. I would rather be “implementation independent” and pay the cost of a bit more boilerplate during the CST to AST transformation.

Other benefits

A huge boon to my development of the language was the fact that I could see the results in my IDE (neovim) as soon as possible. This advantage is very much about feeling early victories and has little to do about substantive issues of semantics. But early visible victories are an important source of motivation when you are engaged in a multi-year effort.

Finally, the fact that a tree-sitter grammar is a javascript file that generates a grammar.json makes it nearly trivial to do fun things like generate railroad diagrams.

I have become a huge fan of these diagrams when I go through the SQLite documentation and hope one day to publish the entire delightql grammar this way.