Ocaml runtime parser generator

Question

I am writing a program that basically takes a grammar as input in a custom format (and some other rules) and generate an OCaml program (a checker) that, once compiled can check if an expression is accepted or not according to the grammar and the rules.

I use OCaml for the generator, with Menhir to parse the grammar and the rules. For now, I have to write a parser by hand for all the grammars I want to generate a checker. I would like to generate the code for a parser automatically, like Menhir does.

I could output a Menhir grammar and call Menhir from my OCaml program, but it would be tedious to have a proper error handling.

Is there any way to use Menhir as back-end (give the grammar to it to produce the parser at runtime) or is there any library that can do that in OCaml (or C since it can be linked with OCaml)?

If it's possible, I would like to be able to express the rules in the format described by the grammar as well, is there any library that can generate interpreters at runtime as well?

Answer 1

This is a broad and very interesting cross-disciplinary research area, so I will not even try to provide a comprehensive answer but instead provide some links and guidelines (which sort of contradicts the spirit of SO, but probably we should otherwise close this question as too broad).

Several projects tried and successfully implemented interactive parsers. If we will focus on projects written in OCaml then the following come to mind first: camlp5, coq, ott. Out of this, the most interesting and easy to comprehend, in my opinion, is the latter one, Ott. They have implemented a GLR parser, based on the reduction worklist algorithm which described, besides others techniques, in Scott McPeak's thesis.

An alternative approach would be to refrain from the parser generation and stick to the monadic parsers. Since the monadic parser defines a context-dependent grammar as runtime value it is possible to specify any interaction between the runtime and the defined grammar. This is actually a boon and a bane, as it is possible to define totally nonsensible grammars with conflicts. But as always, with great power comes great responsibility. OCaml has plenty of monadic parser combinators libraries, the first two that come to mind are mparser and angstrom.