yallop/ocaml-asp

Algebraic, staged parsing for OCaml: typed, compositional, and faster than yacc

Source code at GitHub https://github.com/yallop/ocaml-asp

{
  "createdAt": "2018-09-05T16:06:38Z",
  "defaultBranch": "master",
  "description": "Algebraic, staged parsing for OCaml: typed, compositional, and faster than yacc",
  "fullName": "yallop/ocaml-asp",
  "homepage": "",
  "language": "OCaml",
  "name": "ocaml-asp",
  "pushedAt": "2025-05-16T14:34:20Z",
  "stargazersCount": 104,
  "topics": [
    "functional-programming",
    "high-performance",
    "metaocaml",
    "ocaml",
    "parser-combinators",
    "parsing"
  ],
  "updatedAt": "2025-11-23T00:05:27Z",
  "url": "https://github.com/yallop/ocaml-asp"
}

asp: algebraic, staged parsing

asp is a typed, algebraic parser combinator library with some unusual features:

asp parsers are checked using an internal type system before they are run to ensure that the grammars they describe are unambiguous and free from left-recursion.

These constraints ensure that the input can be parsed in linear time without backtracking and with a single token of lookahead.
asp uses multi-stage programming to achieve much higher performance than most combinator libraries. Parsers constructed with asp can be compiled at runtime to efficient code that typically outperforms parsers written with the standard OCaml parser-generator ocamlyacc

The following paper has many more details:

            A typed, algebraic approach to parsing ([pdf][paper])
            Neelakantan R. Krishnaswami and Jeremy Yallop
            PLDI 2019
            (received Distinguished Paper Award & Distinguished Artifact Award)

Trying out asp

The [pldi-artifact]!(pldi-artifact) directory contains instructions for running the artifact, which can be used to try out the library and reproduce the benchmarks without installing the software.

Installation

Install the [BER MetaOCaml][ber-metaocaml] compiler using [OPAM][opam] !:
```
opam switch 4.11.1+BER
eval $(opam env)
```

Add the [metaocaml-opam][metaocaml-opam] repository:

opam remote add metaocaml git+https://github.com/metaocaml/metaocaml-opam.git

Install the asp package:
```
opam install asp
```

Running the benchmarks

Clone the repository and type make bench.

[paper] !: https://www.cl.cam.ac.uk/~jdy22/papers/a-typed-algebraic-approach-to-parsing.pdf [opam] !: https://opam.ocaml.org/ [letrec] !: https://github.com/yallop/metaocaml-letrec [ber-metaocaml] !: http://okmij.org/ftp/ML/MetaOCaml.html [metaocaml-opam] !: https://github.com/metaocaml/metaocaml-opam/