blog :: Post "parsing-with-menhir"

Parsing with Menhir

2026-08-02 · 9 min

Menhir turns a grammar into an OCaml parser. This builds a small expression language end to end, then covers the parts you reach for once the grammar stops being small: conflicts, parameterized rules, source positions, and error messages that name something other than "syntax error".

§ 01

A little history

OCaml shipped with ocamlyacc, a direct descendant of the original yacc, generating LALR(1) parsers. Menhir arrived from INRIA in 2005 as a replacement: it accepts LR(1) grammars, so it rejects fewer grammars outright, and when it does reject one it explains the conflict in terms of an input that triggers it rather than a state number. It also added parameterized rules, a standard library of common patterns, and an incremental API that lets you drive the parser one token at a time. It is the parser generator the OCaml compiler itself now uses.

§ 02

Install, and the pieces of a parser

Install Menhir.

$ opam install menhir

A parser is three files. The AST it produces, a lexer that turns characters into tokens, and the grammar that turns tokens into the AST.

ast.ml - what the parser is building.

$ type expr =
$   | Int of int
$   | Add of expr * expr
$   | Sub of expr * expr
$   | Mul of expr * expr
$   | Div of expr * expr

lexer.mll - characters to tokens. The token type itself is generated by Menhir from the grammar, so the lexer opens the parser module.

$ { open Parser }
$  
$ rule read = parse
$   | [' ' '\t']+   { read lexbuf }
$   | '\n'          { Lexing.new_line lexbuf; read lexbuf }
$   | ['0'-'9']+ as n { INT (int_of_string n) }
$   | '+'           { PLUS }
$   | '-'           { MINUS }
$   | '*'           { TIMES }
$   | '/'           { DIV }
$   | '('           { LPAREN }
$   | ')'           { RPAREN }
$   | eof           { EOF }

parser.mly - tokens to AST. Declarations above the %%, rules below it.

$ %token <int> INT
$ %token PLUS MINUS TIMES DIV
$ %token LPAREN RPAREN
$ %token EOF
$  
$ %start <Ast.expr> main
$  
$ %%
$  
$ main:
$   | e = expr; EOF { e }
$  
$ expr:
$   | i = INT { Ast.Int i }
$   | e1 = expr; PLUS; e2 = expr { Ast.Add (e1, e2) }
$   | e1 = expr; MINUS; e2 = expr { Ast.Sub (e1, e2) }
$   | e1 = expr; TIMES; e2 = expr { Ast.Mul (e1, e2) }
$   | e1 = expr; DIV; e2 = expr { Ast.Div (e1, e2) }
$   | LPAREN; e = expr; RPAREN { e }

Naming the components (e1 = expr) is the Menhir style. ocamlyacc used positional $1 and $2, which Menhir still accepts and which you should not use in new grammars - renumbering after inserting a symbol is exactly the kind of silent breakage the names avoid.

§ 03

Wiring it into dune

In the dune file, alongside the library or executable stanza. Menhir and ocamllex are rule generators, not libraries, so they sit as their own stanzas.

$ (menhir
$  (modules parser)
$  (flags --explain))
$  
$ (ocamllex lexer)
$  
$ (executable
$  (name main))

Tell dune-project which Menhir syntax version you are writing against. Without this, dune assumes an old default.

$ (lang dune 3.16)
$ (using menhir 3.0)

Build. Dune runs ocamllex and Menhir, then compiles the results.

$ dune build

Drive it from main.ml.

$ let () =
$   let lexbuf = Lexing.from_channel stdin in
$   let ast = Parser.main Lexer.read lexbuf in
$   print_int (Interp.eval ast)

§ 04

Precedence, and the conflicts you get without it

The grammar above is ambiguous. Given 1 + 2 * 3, nothing in it says whether that is (1 + 2) * 3 or 1 + (2 * 3). Menhir reports this as a shift/reduce conflict.

Build, and read what it says.

$ dune build
Warning: one state has shift/reduce conflicts.
Warning: 4 shift/reduce conflicts were arbitrarily resolved.

--explain writes a parser.conflicts file describing an input that reaches the ambiguous state. Read that rather than guessing.

$ cat _build/default/parser.conflicts

Fix it with precedence declarations, above the %%. Later lines bind tighter, so TIMES and DIV beat PLUS and MINUS. %left makes them left-associative.

$ %left PLUS MINUS
$ %left TIMES DIV

Unary minus needs its own precedence level, higher than any binary operator. %prec overrides a rule's precedence, which would otherwise come from its rightmost terminal.

$ %left PLUS MINUS
$ %left TIMES DIV
$ %nonassoc UMINUS
$  
$ expr:
$   | MINUS; e = expr %prec UMINUS { Ast.Neg e }

Precedence declarations resolve conflicts by silencing them, which means they can also silence a conflict that was a real bug in the grammar. When a conflict appears in a part of the grammar that has nothing to do with operator precedence, read the .conflicts file and restructure the rules instead of reaching for %left.

Make unresolved conflicts fail the build rather than warn, once the grammar is clean. Worth doing early.

$ (menhir
$  (modules parser)
$  (flags --explain --strict))

§ 05

Parameterized rules and the standard library

A rule can take another rule as an argument. Menhir ships a standard library of these, which removes most of the recursive list boilerplate that yacc grammars accumulate.

A comma-separated argument list, in one line. separated_list handles the empty case and the trailing-element case for you.

$ call:
$   | f = ID; LPAREN; args = separated_list(COMMA, expr); RPAREN
$     { Ast.Call (f, args) }

The ones worth knowing by name.

option(X)                  -- X or nothing, as an OCaml option
list(X)                    -- zero or more
nonempty_list(X)           -- one or more
separated_list(SEP, X)     -- zero or more, separated
delimited(L, X, R)         -- X between two brackets, returning X
preceded(L, X)             -- drops the prefix
terminated(X, R)           -- drops the suffix

Write your own. This one accepts a trailing separator, which the standard library's version does not.

$ trailing_list(SEP, X):
$   | { [] }
$   | x = X { [x] }
$   | x = X; SEP; xs = trailing_list(SEP, X) { x :: xs }

%inline expands a rule at each use site instead of giving it its own states. This is the usual fix when factoring a grammar for readability introduces a conflict that was not there before.

$ %inline binop:
$   | PLUS { Ast.Add }
$   | MINUS { Ast.Sub }

§ 06

Positions

Every semantic action can see where its symbols came from. Attaching positions to AST nodes as you build them is much cheaper than reconstructing them later, and it is what lets a type error point at a line.

The keywords available inside an action.

$startpos, $endpos   -- the whole production, as Lexing.position
$loc                 -- that pair, as a tuple
$sloc                -- same, ignoring leading empty symbols
$startpos(e1)        -- one named symbol
$loc(e1)             -- one named symbol, as a pair

Carrying a location into every node.

$ expr:
$   | i = INT { { node = Ast.Int i; loc = $loc } }
$   | e1 = expr; PLUS; e2 = expr
$     { { node = Ast.Add (e1, e2); loc = $loc } }

Positions are only as good as the lexer. If the lexer does not call new_line on each newline, every line number after the first is wrong.

$   | '\n' { Lexing.new_line lexbuf; read lexbuf }

Set the filename before parsing, so positions report it.

$ let lexbuf = Lexing.from_channel ic in
$ Lexing.set_filename lexbuf path;

§ 07

Error messages

By default a failed parse raises Parser.Error and you know nothing beyond the position. Menhir's error machinery lets you attach a written message to each way the parse can fail, keyed by the parser state. This is the part that takes real effort, and the only way to get messages worth reading.

Switch to the table back-end, which is what the incremental and error APIs require, and link menhirLib.

$ (menhir
$  (modules parser)
$  (flags --table --explain))
$  
$ (executable
$  (name main)
$  (libraries menhirLib))

Generate one entry per distinct error state. Each comes with an example input that reaches it and a placeholder message.

$ menhir --list-errors parser.mly > parser.messages

An entry, after you have replaced the placeholder with something useful.

main: INT PLUS EOF
##
## Ends in an error in state: 6.
#
Expected an expression after this operator.

Compile the message file into an OCaml module exposing a message function.

$ menhir --compile-errors parser.messages parser.mly > parserMessages.ml

After the grammar changes, states move. This rewrites the file against the new grammar, keeping your text and flagging what needs attention.

$ menhir --update-errors parser.messages parser.mly > parser.messages.new
$ mv parser.messages.new parser.messages

Check that the file covers every error state and has no duplicates. Run this in CI - it is the thing that catches a grammar change nobody re-ran the update for.

$ menhir --compare-errors parser.messages --list-errors parser.mly

Driving the parser incrementally, so you can ask the interpreter which state it died in and look up the message.

$ module I = Parser.MenhirInterpreter
$  
$ let rec loop next_token lexbuf checkpoint =
$   match checkpoint with
$   | I.InputNeeded _ ->
$     let token = next_token lexbuf in
$     let startp = lexbuf.Lexing.lex_start_p in
$     let endp = lexbuf.Lexing.lex_curr_p in
$     loop next_token lexbuf (I.offer checkpoint (token, startp, endp))
$   | I.Shifting _ | I.AboutToReduce _ ->
$     loop next_token lexbuf (I.resume checkpoint)
$   | I.HandlingError env ->
$     let state = I.current_state_number env in
$     Error (ParserMessages.message state)
$   | I.Accepted ast -> Ok ast
$   | I.Rejected -> assert false

Start that loop from the entry point named by %start.

$ let parse lexbuf =
$   loop Lexer.read lexbuf
$     (Parser.Incremental.main lexbuf.Lexing.lex_curr_p)

§ 08

Inspecting the grammar

Run the parser on a token sequence without building the project, and see what it reduces to. Fastest way to check whether a rule does what you think.

$ menhir --interpret --interpret-show-cst parser.mly
INT PLUS INT EOF

Dump the LR automaton. Verbose, but it is the ground truth when a conflict explanation is not enough.

$ menhir --dump parser.mly
$ less parser.automaton

Trace shifts and reductions at runtime.

$ menhir --trace parser.mly

List rules and tokens the grammar declares but never uses. Both are usually leftovers from a refactor.

$ menhir --only-preprocess parser.mly

Add the inspection flags through dune rather than running menhir by hand, so they apply to every build.

$ (menhir
$  (modules parser)
$  (flags --explain --strict --dump))

That is the shape of it: a grammar and a lexer wired in through two dune stanzas, precedence declarations for the operator ambiguities and restructured rules for everything else, the standard library for lists, positions attached as you build, and a .messages file once "syntax error" stops being an acceptable answer.