uu-parsinglib

[noughtmare]

The most important difference between uu-parsinglib and the parsec family of parser combinators is that the parsers in uu-parsinglib are based on CFGs instead of PEGs, which means that the alternative operation <|> is unbiased in uu-parsinglib. In my opinion, this allows you to write your parsers in a much more natural way (no more worrying about putting try in the right place!).

Furthermore, uu-parsinglib library has a lot of unique features and patterns:

• Online. this means that parsers can produce a result before they've seen all of the input. You can use this to write constant space log parsers.
• Error-correcting. The parsers will try to find a way to make a successful parse by inserting or deleting tokens in the input. This is actually required to be able to write online parsers, because they need to produce output even if there is an error later in the input.
• Merging, permuting, interleaving. Explained in the 2013 tech report below (I also don't know the details yet).
• Idiomatic. You can write parsers using idiom brackets, e.g. iI (+) '(' pNatural "plus" pNatural ')' Ii. Although, I think this is mostly a gimmick.
• Micro steps to resolve ambiguity. This can be used to disambiguate variable names and keywords.
• Explicit biased choice: <<|>, and greedy, e.g. pList, and non-greedy, e.g. pList_ng, variants of many combinators.

Technical reports for more info:

• https://www.cs.uu.nl/research/techreps/UU-CS-2008-044.html (also cited by your paper)
• https://www.cs.uu.nl/research/techreps/UU-CS-2013-005.html

I think the main thing that holds these ideas back is that the library is not really in a good state for mass adoption yet. It needs much better documentation and more active maintenance. I hope to be able to contribute something on that front.

[j-mie6]

Interesting, I do like the micro idea, it seems like a way to create so-called "soft" keywords, like those found in Scala 3. These are keywords which are only treated as keywords in specific positions, otherwise they can be regular variable names (this was done to allow for backwards compatibility with Scala 2 code). This is something I did want to explore how to do nicely in parsec-like libraries, as it's slightly non-obvious, especially when paired with the Overloaded Strings pattern, so it's cool to see a clean solution here!

Idiom brackets can, for sure, be supported by other frameworks (including parsec)! It seems like a particular sugaring that is close to Lifted Constructors in principle.

One of the reasons for try is to help improve error messages. It would be interesting to have a study of how the error messages compare to this library, particularly as it doesn't have try: are there any patterns that can be found to generate good error messages for such libraries?

I do agree that try's absence is more natural for writing parsers, however it does have some adverse effects on performance (personally, I prefer to write non-ambiguous parsers and eliminate try rather than insert a bunch of cuts to help improve performance): how does this library perform in that respect? Are there any considerations when designing parsers with this approach about how to keep them efficient?

[noughtmare]

I don't have enough experience using the library, but here's an excerpt of an interesting stackoverflow answer from the author of the package:

If one moves to the breadth-first strategy uu-parsinglib uses one has to keep track of several alternatives at the same time, and this take time. Two alternative, twice the time, etc.

The advantage of Parsec is that you can tune a back-tracking parser by liberal use of try constructs and by placing alternatives in the right order, but you are also more likely to ask questions on mailing list about why your parsers do not work as expected. You are not so much writing a grammar as writing parser. The uu-parsinglib starts from the other end of the spectrum: we try to accept quite a large collection of grammars (and the parsers implied by them).

My feeling is also that in the presence of try constructs having excellent error-repairing parsers is much more complicated. Once a try construct fails it is not possible to go back there and decide that, with a small correction, it is much better than the alternatives that come after it.

I do wonder how the error messages compare. One thing I noticed is that uu-parsinglib is able to give a list of all possible expected tokens at each point. I believe parsec-like parsers can only report the expected tokens of the current branch.

[j-mie6]

Parsec-like parsers typically produce the expected tokens of sibling branches as well as previous non-input consuming parents: the idea is that as soon as you get further into the input, the older tokens are no longer relevant (under the assumption that a try is not used). It's a tricky balancing act of trying to keep errors relevant to the current context. This is why I'd be keen to see a comparison between the two, it would be really cool if more insightful errors can be created!

It would also be nice to have a collection of pathological parsec-parsers where the error messages are really hard to make meaningful - they certainly exist!

[noughtmare]

Ah, I guess that shows my inexperience with parsec-like parsers.

It would be nice to have a benchmark for error-messages of parsers.

The closest thing I can find is a post by @chrisdone showing that you can create very helpful error messages with parsec, but those do seem like cherry picked examples.

[chrisdone]

You can test the parser out live here: https://chrisdone.com/toys/duet-delta/

[chrisdone]

Also the source for the parser is here https://github.com/chrisdone/duet/blob/master/src/Duet/Parser.hs