I’ve recently discovered the fastparse Scala library GitHub - com-lihaoyi/fastparse: Writing Fast Parsers Fast in Scala and I wonder if we have a similar library in OCaml? I had a look at mparser and angstrom, but none of them seem to allow to easily define mutually recursive parsers, or to easily h…

The JSON parser in Orsetto (see Json_scan.ml ) is about 500 lines, about half of which is the lexical analyzer, and about 100 lines is some logic that I’m trying to make obsolescent in a future release. Parsing JSON objects is an illustrative example of where a backtracking feature of some kind is n…

@jhw Why do you think that backtracking is necessary for parsing json? I am sure that I can write a json parser with a combinator library which does not use backtracking. In the example I have given, backtracking was necessary because in a character parser (i.e. a lexerless parser) it is not possi…

[image] hbr: Why do you think that backtracking is necessary for parsing json? I am sure that I can write a json parser with a combinator library which does not use backtracking. I should clarify. It’s necessary for a validating parser. If all you want to do is recognize any well-formed synta…

How interesting. So when you see { "a": <json1>, "b": <json2>, "c": <json3> } you remember the positions of the start of the sub-trees, and then go back and validate-and-parse ? At first glance, to know where the sub-trees end, would seem to require at least parenthesis-matching of the entire su…

@jhw What do you mean by validating parser? A json parser should accept valid json and reject invalid json. Otherwise it would not be a json parser. And why do you think that validating requires backtracking?

[image] Chet_Murthy: Just curious how you do it. Well I don’t actually have a JSON Schema compiler yet, and I’m not sure I want to write one, but how Orsetto will handle this sort of thing is by parsing enough of the object between the delimeters to validate the syntax is well-formed, but it …

[image] hbr: What do you mean by validating parser? I mean a parser that rejects well-formed syntax if it’s invalid according to the data model.

[image] jhw: It will just memorize the stream position for the start of each field, Right, and to do this for the start of the second field, requires full parenthesis-matching of the text of the first field, yes? It sounds like this approach re-scans a deeply-nested subtree approximately O(d…

I think these are usually separate concerns. The parser constructs an AST, not caring about the data model, then a decoder transforms the well-formed AST into the required data (of course this can fail too).

Mmmm … so, in the case of languages used for wireline data-serialization, parsing directly into application data-structures is actually pretty important. Parsing first into JSON (or for that matter, XML DOM) and then into application datastructures is much more expensive (that intermediate tree get…

OCaml Parser combinator library as powerful as fastparse(Scala)?

Ecosystem

yawaramin April 16, 2021, 9:14pm 19

Yeah, you’re right of course for specific formats which allow defining schemas, like Thrift. I guess I was thinking more about JSON.

Topic		Replies	Views
[ANN] Parseff: parser combinator library for OCaml 5 Ecosystem announce	31	1009	March 31, 2026
Unicode-aware parser combinators Learning parsing	25	1312	September 13, 2023
High-performance lexing in OCaml Ecosystem performance , ocamllex	20	3269	April 1, 2021
Is it feasible to write parsers without using polymorphic variants for AST representation? Learning	16	2198	April 25, 2018
My way from LALR parsing to combinator parsing Community	6	2857	March 12, 2021

OCaml Parser combinator library as powerful as fastparse(Scala)?

Related topics