The main problem was to find a (semi-)formal description of Nix language. I re-read the chapter on the expression language in the official Nix manual several times, but it lacked some details. There was also a page on NixOS wiki which described the language more formally, or, rather, in a way that was more suitable for my purpose. However, it also lacked some necessary details. For example, in the pattern expression used in lambda definitions it is possible to supply default values, e.g.

{x ? true, y, z} : if x then y else z

However, it is not clear what exactly can be put there. Can I use a let expression?

{x ? let n = g n; in !(n g), y, z}: ...

Or, maybe, it is restricted to simple arithmetic expressions?

{x ? 1+1, y, z}: ...

Oh Lisp,
  Remembering thee,
  Thy simplicity and clarity
  Is unrivalled.

    — Unknown author, circa early XXI century

To understand all those nuances I had to experiment in the repl. A lot. Sometimes, what seemed logical to me wasn't working as I expected, being more restrictive than I anticipated. Other times it was the opposite, allowing more general expressions where I would have expected an atomic value.

The result was quite a messy grammar specification with randomly sprinkled precedence annotations :). So it wasn't a huge surprise when I got

$ dune build
      menhir nix/parser.{ml,mli}
Warning: 12 states have shift/reduce conflicts.
Warning: one state has reduce/reduce conflicts.
Warning: 153 shift/reduce conflicts were arbitrarily resolved.
Warning: one reduce/reduce conflict was arbitrarily resolved.

After spending at least a couple of days in resolving the conflicts and continuous repl-wrangling I decided that I have had it enough and started from scratch.

This time around I started from the operator precedence table. Avoiding associativity declarations altogether, I explicitly encoded all the productions.

expr1:
| e = binary_expr(expr2, "->" {Impl}, expr1)
| e = expr2
    { e }

expr2:
| e = binary_expr(expr2, "||" {Or}, expr3)
| e = expr3
    { e }

expr3:
| e = binary_expr(expr3, "&&" {And}, expr4)
| e = expr4
    { e }

(* ... other productions here ... *)

expr14:
| (* ... *)

where

%inline binary_expr(Lhs, Op, Rhs):
lhs = Lhs; op = Op; rhs = Rhs
    { BinaryOp(op, lhs, rhs) }

is a parametrised production rule which expands into the rule that parses the left hand side, the operator, and the right hand side and constructs a BinaryOp value.

I think the ability to parametrise rules is one of the more powerful features of Menhir, which facilitates writing succinct grammars. There is a subtle difference between %inline and non-%inline rules. Namely, %inline rules are expanded in-place and may reduce the number of states/reductions in some cases.

For example

%inline expr8_ops:
| "+" {Plus}
| "-" {Minus}

expr8:
| e = binary_expr(expr8, expr8_ops, expr9)
| e = expr9
    { e }

expands expr8_ops into

expr8:
| e = binary_expr(expr8, "+" {Plus}, expr9)
| e = binary_expr(expr8, "-" {Minus}, expr9)
| e = expr9
   { e }

which after expanding binary_expr becomes

expr8:
| lhs=expr8, "+", rhs=expr9
   { BinaryOp(Plus, lhs, rhs) }
| lhs=expr8, "-", rhs=expr9
   { BinaryOp(Minus, lhs, rhs) }
| e = expr9
   { e }

Menhir comes with the standard library containing a number of pre-defined rules. For example, separated_nonempty_list accepts a separator rule and a rule of an individual element and returns a list built from the semantic actions returned by the elements:

attr_path:
| cs = separated_nonempty_list(".", attr_path_component)
    { cs (* a list of attr path components *) }

Even more exciting is that Menhir allows parameters which can be parametrised rules themselves, essentially providing a higher-order DSL. I haven't exploited the feature yet, but do hope to get back to it at some point.

Also a minor thing, but it is worth mentioning, the explicit encoding of the operator precedence rules make operator associativity obvious. For example

expr_1:
| expr_1; op; expr_2
| expr_2

defines a left-associative operator op (expr1 is on the left), while

expr_1:
| expr_2; op; expr_1
| expr_2

makes op associate to the right. Non-associative operators can be defined as

expr_1:
| expr_2; op; expr_2
| expr_2

I think that the explicitness of the approach provides for better locality and isolation, while the traditional approach, where the operator precedence table encoded elsewhere, may lead to some tricky and hard-to-debug errors. In my mind it is not dissimilar to lexical scoping versus dynamic scoping. When a language obeys lexical scoping rules, by looking at the function code in isolation one can fully understand what it does or what its behaviour depends on. Whilst in the latter case, the behavior of a function may change dramatically depending on the context it is put into.

The meticulous following of the operator precedence¹ table and the explicit, careful encoding of other rules eliminated all the shift/reduce conflicts with a singe reduce/reduce conflict left. I think it's a legit conflict that makes the grammar LR(2), not LR(1). The essence of the conflict is this: We may have an attribute set and a pattern in lambda definition

let attset = {b1 = 1; b2 = 5;} # ...
let func = {p1, p2}: # ...

In the degenerate case the list of formal parameters p1..pn and the list of bindings b1..bn may be empty, i.e.

let attset = {} ... # tokens: LBRACE RBRACE ...
let func = {}: ... # tokens: LBRACE RBRACE COLON ...

The parser, upon seeing RBRACE can not decide whether it should reduce LBRACE RBRACE sequence to an attr_set or it is the beginning of param_set.

My first solution was to mandate non-empty list of formal parameters in param_set. Which is somewhat substantiated by the fact that an empty parameter set makes no sense in a lazy language. Take Haskell for example. Since all the computations are suspended, declaring

f = 1

is equivalent to

let f () = 1

in a strict language. In other words, passing an empty parameter set to a pure function yields exactly the same result as if the body of the function is assigned to a value and that value is used in place of the function call. Hence, in a lazy language, it makes no sense to write

f x = z

where expression z does not have x as a free variable.

The creators of the language and package authors think differently, though, because parsing all the files in nixpkgs uncovered quite a number of the cases.

I got curious how could it work for the original, Bison-generated Nix parser. The answer was %glr-parser directive in the parser specification file. GLR parsers are capable of processing non-LR(1) grammars by "splitting the brain" and maintaining separate parse stacks simultaneously, until following one of the paths yields an error².

Menhir does not support the feature, so as a workaround I introduced another token, "{}" - EMPTY_CURLY - which eliminated the conflict. It still may fail to parse some valid expressions if there is a comment inside curly braces, e.g.

let f = { /* an empty parameter set */ }: 1

but I found that empty attribute sets are much more common and made LBRACE RBRACE sequence to unambiguously reduce to attr_set.

In addition to the above problem (i.e. parsing empty curly braces), I got a number of other errors. To be precise, the parser errored on 129 files out of 14,674 (which is less than 1%). The majority of the errors was due to the trailing comma in parameter sets:

let f = {a, b,}: a + b

I am not sure if it was done that way because of some legacy reasoning or just accidentally crept into the Bison parser, but since Nix manual doesn't mention the possibility of writing parameter sets in such a way, I left it as is.

Another class of problems, a rare one, but quite annoying, was in allowing re-definitions of some values:

let a = { true = true; false = "hi there", null = 8756}

The problem I see here is that re-declaring them may lead to some "funny" code

nix-repl> let false = true; in if false then "true" else "false"
"true"

Although I changed the grammar to allow those, I think it's a bad practice and should be made syntactically impossible.

Another oddity I encountered was an empty binding list in let expressions. That is, some of the .nix files in nixpkgs contain code like

let /* no bingings here */ in blah

That definitely makes no sense whatsoever so I left the requirement of a non-empty binding list for let expressions in place.

Last but not least was a special treatment of or keyword. or is a true keyword which is an essential part of the language, not just some value or a built-in function

nix-repl> let x {a = 1;}.b or "no b in the attr set"; in x
"no b in the attr set"

but it is still possible to re-define it!

nix-repl> let a = {or = 1;}; in a.or
1

I decided against fixing it because it seemed more of a historical accident rather than a technical decision and thus "shall not pass" :)

I am always keen to understand how "good" something is. For computer programs one obvious metric is how fast they are. However, it makes no sense to measure run time of a program in isolation, since the results may differ in an order of magnitude on different hardware configurations.

To have a base line I used the parser that comes with Nix itself. To be pedantic, it does a little bit more than just parsing (and that's the reason why it can not be used for tooling). Still, I think it is as good a starting point as anything else.

Menhir is awesome. It has --trace and --interpret flags which make debugging a grammar not an appalling task. The --dump flag outputs the finite automaton in a human-readable form into a text file, which I found invaluable for understanding the conflicts. And I applaud the idea of parametrised production rules.

I think the incremental API will be essential for some of the tools I have in mind, although given the performance results and still feeling the thrill of competition, I am tempted to write a Nix expression interpreter first :)

I am not sure if I should be comparing it to Bison but it is the only heavy-weight parser-generator tool I have some experience with. They have their strengths and weaknesses and different feature sets. Menhir is limited to LR(1) grammars which may be a deal breaker for some applications. Also, Bison's manual is insanely good. I would read it just for fun, like a morning paper or a fiction book. It is just that good. Menhir's manual, while being of a very good quality, pales in comparison.

With all of that I just re-instantiated the thought that if I ever find myself in a situation where I desperately need to write a compiler or two, OCaml would be the tool I reach out to first.

The source code of the parser specification is available on GitHub.