Total Parser Combinators - Agdarsec
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 35/100
Research direction
Start with the runtime termination check in cparsec.h at lines 164–166, then read the linked agdarsec paper and compare its constraints with the existing parser combinators. Determine whether a total design remains expressive enough, including the listed incompatible combinators and breaking changes. Done means documenting a concrete design direction and its tradeoffs.
Written by the indexing model from the issue text.
Description
Problem
Currently all our parsers terminate, but this is done by a check at runtime:
It'd be much better for this to not be possible at compile time
Research
I've found this paper on agdarsec (https://github.com/gallais/agdarsec/). A parser combinator library for Agda, which has "total parser combinators", that is parsers combinators that always terminate.
To do that it adds constraints and tradeoffs:
- For a parser to be successful, it must consume some of its input
- Failure is implemented by always returning the empty result list.
- Several combinators are incompatible, like
many,sepby, etc. Essentially all the ones that succeed on zero or more occurrences. eofis not representable by agdarsec- There is no
pureparser (since it succeeds but doesn't have to consume input)
Some breaking changes might be acceptable but one thing I'm not sure is it's expressive enough. I haven't found many examples.
- Dominant language
- C
- Stars
- 92
- Forks
- 3
- Avg merge
- 55m
- Merged PRs (30d)
- 2
Getting set up
This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from PostgREST/CParseC
-
difficulty: easy
Difficulty 2/5 1-3 hours Newbie friendliness 64/100
-
difficulty: easy
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
-
Difficulty 3/5 1-2 days Newbie friendliness 48/100
All issues in PostgREST/CParseC
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 65/100
-
performance solver
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
ChefKissInc/Inferno#319 ·
-
llvm-tools
Difficulty 1/5 Under an hour Newbie friendliness 72/100
llvm/llvm-project#235522 ·
Maintainers usually reply within 1 day
-
Difficulty 1/5 Under an hour Newbie friendliness 90/100
darktable-org/darktable#22791 ·
Maintainers usually reply within 1 day