Re: A formal grammar for Org

[Jakob Schöttl]

Am 01.06.21 um 11:53 schrieb Tom Gillespie:
> > We have a pretty similar project, org-parser[1]. It's also written in a Lisp 
> > dialect, Clojure, but it uses instaparse instead of brag as parser library.
> https://github.com/tgbugs/laundry/tree/next#similar-projects I managed
> to get it into my README as a reminder to myself to have a thorough
> look at it, but have been occupied with other work since then.
Thanks, I'll also set a link in our README to related work.
> > My idea was, to transform the formal grammar to a grammar.js for tree-sitter. 
> > It would be so cool, if it could be generated from one formal specification.
> Yes, that would be great. It would be a major step to have a couple of
> grammars for org that can be used for stuff like this and compared to
> each other, along with test cases that we can use to define correct
> behavior.
Right, that would be interesting. But it requires all parser to yield 
exactly the same structure (to be comparable). I think a design goal of 
org-parser is to provide a easy to use AST but not necessarily a 
100%-match to the AST from org-element.el.

How is it with laundry? Do you try to stick exactly to org modes parse 
result structure?

> One issue that I don't have a full understanding of at the
> moment is how certain ambiguous forms will impact the ability to
> transform directly into the tree sitter grammar.
>
> The reason I mention
> this is because I have had to move to a two phase parser in order to
> deal with ambiguous parses.
We also have two phases: "parse" and "transform" (the latter is 
basically a mapping function transforming nodes of the AST). I also see 
that as a problem for generating grammar.js.

a) For tree-sitter, depending of what we expect from it, it may not be 
necessary, to do the second phase. E.g. for syntax highlighting the 
context free grammar might be enough.

b) Since transformations of org-parser can be compiled to JS, it might 
be possible, to even create the grammar.js as two-phase parser.

> > Do you plan, in your parser, to do a transformation step from the raw parser AST to a 
> > higher-level AST? E.g. the raw parser AST would parse a (:date  "2021-06-01") 
> > and the transformed AST would transform this to a higher-level timestamp object.
> Yes. I already do that to a certain extent in the expander
> https://github.com/tgbugs/laundry/blob/next/laundry/expander.rkt (the
> raw AST is hard to work with directly), but there will be more. I also
> expect that I will add an intermediate step where the AST is
> rearranged to account for aspects of org semantics that cannot be
> captured by the context free part of the grammar.
>
> After that step there are a number of potential conversions, one of which will
> transform the AST into Racket structs, but I haven't made it quite
> that far yet. That said, I think that in terms of defining a canonical
> parse, I am aiming to do that in the transformed intermediate
> s-expression representation because I think it will be easier to
> define the correctness of certain user interactions on that form rather than
> on the higher level object representation, even if the higher level
> objects are ultimately used to actually implement that behavior.
Interesting. Yeah, because things like timestamps have language-specific 
representations may not be comparable across e.g. emacs lisp, rust, and 
clojure/JS.
> > Do you have any automated tests for your parser?
> Yes. See https://github.com/tgbugs/laundry/blob/next/laundry/test.rkt
> you can run them from the working directory via =raco test laundry=.
Ah, alright, I first didn't see them. Wow.

These parser projects are really a huge amount of work times 4 (grammar, 
transformation, tests, re-export) ^^
> It would be great to align the grammars and the behavior using a set
> of common test cases.
If it works out, that our parser have exactly the same resulting 
structure, that would be great. But not sure, if that works out, to be 
honest. At least we can share each others mean test.org files ^^

Best, Jakob