Is it possible to do bi-directional parsing with Lark?

[thomasahle]

I was reading about bi-directional parsing, where you define your parser/grammar and pretty-printer/templating-language at the same time.

The basic idea is expressed by this example:

Is it possible to do something like that with Lark?

• https://ifl2014.github.io/submissions/ifl2014_submission_18.pdf
• https://www.reddit.com/r/ProgrammingLanguages/comments/14pghf5/defining_a_parser_and_a_prettyprinter/
• https://stackoverflow.com/questions/25000400/a-templating-engine-which-supports-generating-a-parser-from-a-template

[MegaIng]

Lark has a reconstructor, but you have to still manually build a pretty printer (inserting the correct ignored tokens, to for example match indentations between lines in a C-like language) manually on top of that.

At least based on my reading of the abstract and looking at the examples, I don't think the first linked paper actually does what you want. I am not actually sure what they mean with "bidirectional".

If you want to contribute facilities to do something like this, it might be possible to add them to lark. However, note that there is a pretty fundamental difference in syntactic form between a templating engine and a BNF-based parser. This might make more sense as a different library that uses lark in the background.

[erezsh]

Lark's reconstructor pretty much does what was described in that reddit post. Because the Lark grammar supports a few simple rules for turning CSTs directly into ASTs (e.g. dropping literals, inlining rules), we can also do the reverse operation. There is some ambiguity involved, but it can be solved relatively efficiently with our Earley parser. However, we don't yet have a good formulation for what derivations to prioritize, so sometime the resulting code can have some unnatural artifacts. It works and is even used by other packages, but mostly for simple languages like JSON.

(as aside: it would be interesting to see if LLMs can smooth those artifacts out).

P.S. thanks for making it a discussion and not an issue ;)

[nchammas]

Happy to start a new discussion if appropriate, but is this problem here similar to that of making an auto-formatter in Lark? i.e. I've created my DSL in Lark, and I also want to create a tool that will automatically format code in that DSL.

I see two examples in the documentation that use the reconstructor, one for JSON and one for Python.

Am I looking at the right place for guidance on how to make an auto-formatter in Lark?

[erezsh]

The Lark grammar doesn't contain the necessary information for an auto-formatter. There is no way to specify whitespace or newlines.

In theory, it might be possible to write an auto-formatter using the reconstructor, if you add the formatting instructions yourself. But I don't know if it's ever been done, and I don't have a ready solution for how to do it.

So you can try, but it's probably easier to just write a formatter manually, if it's only for one language.