instaparse VS org-parser

Caveats: I've used nom in anger, chumsky hardly at all, and tree-sitter only for prototyping. I'm using it for parsing a DSL, essentially a small programming language.

The essential difference between nom/chomsky and tree-sitter is that the former are libraries for constructing parsers out of smaller parsers, whereas tree-sitter takes a grammar specification and produces a parser. This may seem small at first, but is a massive difference in practice.

As far as ergonomics go, that's a rather subjective question. On the surface, the parser combinator libraries seem easier to use. They integrate well with the the host language, so you can stay in the same environment. But this comes with a caveat: parser combinators are a functional programming pattern, and Rust is only kind of a functional language, if you treat it juuuuust right. This will make itself known when your program isn't quite right; I've seen type errors that take up an entire terminal window or more. It's also very difficult to decompose a parser into functions. In the best case, you need to write your functions to be generic over type constraints that are subtle and hard to write. (again, if you get this wrong, the errors are overwhelming) I often give up and just copy the code. I have at times believed that some of these types are impossible to write down in a program (and can only exist in the type inferencer), but I don't know if that's actually true.

deep breath

Tree-sitter's user interface is rather different. You write your grammar in a javascript internal dsl, which gets run and produces a json file, and then a code generator reads that and produces C source code (I think the codegen is now written in rust). This is a much more roundabout way of getting to a parser, but it's worth it because: (1) tree-sitter was designed for parsing programming languages while nom very clearly was not, and (2) the parsers it generates are REALLY GOOD. Tree-sitter knows operator precedence, where nom cannot do this natively (there's a PR open for the next version: https://github.com/Geal/nom/pull/1362) Tree-sitter's parsing algorithm (GLR) is tolerant to recursion patterns that will send a parser combinator library off into the weeds, unless it uses special transformations to accommodate them.

It might sound like I'm shitting on nom here, but that's not the goal. It's a fantastic piece of work, and I've gotten a lot of value from it. But it's not for parsing programming languages. Reach for nom when you want to parse a binary file or protocol.

As for chumsky: the fact that it's a parser combinator library in Rust means that it's going to be subject to a lot of the same issues as nom, fundamentally. That's why I'm targeting tree-sitter next.

There's no reason tree-sitter grammars couldn't be written in an internal DSL, perhaps in parser-combinator style (https://github.com/engelberg/instaparse does this). That could smooth over a lot of the rough edges.

Sure, you can use https://github.com/Engelberg/instaparse to create parser for any language you want, or simply create DSL in basic clojure types, like vectors.

Enter org-parser! It is indeed such a thing implemented already! Remember the magical parser I mentioned above? It is already implemented here Engelberg/instaparse too (in a Lisp)! org-parser is built on top of it by providing a formal specification for org-mode in the EBN form. Any proof that org-parser works? Indeed, there is the celebrated organice which is built on top of it. Kudos for 200ok-ch!

You might enjoy checking out Instaparse, a Clojure library. Its project page reads, “What if context-free grammars were as easy to use as regular expressions?”

It’s not over-promising, either. I went from never having heard of it before to getting complete and correct parse trees of some ancient JSP Expression Language in about 20 minutes. Most of that time was spent typing in the BNF description that I could find only in an image.

https://github.com/Engelberg/instaparse

Instaparse sounds pretty close to what you're looking for assuming you're ok being limited to context-free grammars.

It is in EBNF, with some alternate conventions. It follows the syntax found in here, which I think is pretty easy to get behind.

Another way to solve it is to load the grammar directly into instaparse, specify the start rule :0 and count the successful applications of the parser to the messages:

Let me start by saying I like the goal and would like to see org mode accessible to everyone, but I do have some thoughts/reservations.

> For the little code I do write, I find having AI assistance (via CoPilot or Cody) to be tremendously helpful. So helpful, in fact, that I now tend to jump into VSCode for actual coding,

Aren't there both copilot and Cody plugins available in emacs?

> Use VSCode for everything. For me, this requires a full-featured org mode implementation. I currently feel stuck in Emacs just because of how great org mode is.

This seems much more difficult than creating plugins you need in emacs and with the downside that customization will be much worse in vscode, especially customization of behavior with things like hooks.

> Letting go of bug-for-bug compatibility with Emacs as a goal. Let's let the quirky behavior die off and move forward with a more cohesive program, even if it looks a little bit different.

If you don't have compatibility, then you aren't really implementing org-mode... you are starting fresh.

That's okay, but you'll likely annoy org-mode users and developers as documents ending in `.org` start not working the same.

Also there are languages besides Rust and Haskell that have an org parser implementation. For instance one written in Javascript already has a spec as you explain it and is used in production for organice[0]:

> Why is this project useful / Rationale

> Org mode in Emacs is implemented in org-element.el (API documentation). The spec for the Org syntax is written in prose. - https://github.com/200ok-ch/org-parser

> Portable. It should not be difficult to get this integrated into any editor.

This tells me you already have a language in mind such as Lua (can't think of any other easy to integrate languages)? I'd argue that's not very popular either though.

0: https://organice.200ok.ch/

I mean , you have parsers for JS and CLJS https://github.com/200ok-ch/org-parser

I don't think you did. You probably used the sister project https://github.com/200ok-ch/org-parser which has a well known issue regarding what you are describing: https://github.com/200ok-ch/org-parser/issues/56

organice has no such performance issues (and does not run on the JVM). I use it daily with 5k LOC files.

EBNF grammar - https://github.com/200ok-ch/org-parser/blob/master/resources...

From the readme:

> Org grammar for tree-sitter. It is not meant to implement emacs' orgmode parser, but to implement a grammar that can usefully parse org files to be used in neovim and any library that uses tree-sitter parsers.

This grammar is in active development and is being used by nvim-orgmode/orgmode [1], a org-mode neovim plugin.

Some additional resources some might find useful:

* Org Syntax - https://orgmode.org/worg/dev/org-syntax.html

* EBNF grammar - https://github.com/200ok-ch/org-parser/blob/master/resources...

[1] https://github.com/nvim-orgmode/orgmode

There's at least a parser using that as a spec at https://github.com/200ok-ch/org-parser

We have an issue with more information and we are working on it: https://github.com/200ok-ch/org-parser/issues/56

If you’re open to use a different Lisp, then maybe https://github.com/200ok-ch/org-parser is something for you.

I just wanted to chime in and mention that the folks who wrote organice[0] also came up with an EBNF grammar[1] for org-mode. Also of tangential interest is that work is actively being done on creating a tree-sitter version[2] of the grammar, although that work is not public (yet).

[0] https://github.com/200ok-ch/organice

[1] https://github.com/200ok-ch/org-parser/blob/master/resources...

[2] https://github.com/kristijanhusak/orgmode.nvim/issues/31#iss...