[Feature Request] Rust Backend

[Centril]

Rust is quite a new language... but, it is an awesome language. Particularly, it features affine types, algebraic data types, and is in addition a systems programming language, so it's a nice replacement for C/C++ and allows for pattern matching instead of using the visitor pattern.

There are already a few parser generators,

• https://github.com/nikomatsakis/lalrpop
• https://github.com/kevinmehall/rust-peg
• https://github.com/goffrie/plex

As well as parser combinators:

• https://github.com/Geal/nom
• https://github.com/Marwes/combine
• https://github.com/m4rw3r/chomp

I'll see myself if I can do some development towards this end... ... but mainly, I'm registering this so we can coordinate =)

[shlevy]

Is there documentation anywhere on what is needed to add a new backend? I'm playing around with bnfc now and if it fits our use case we'll need to add one for Rust.

[andreasabel]

Hello @shlevy, thanks for your initiative!

Atm, there is no such documentation, but I can summarize the most important steps for a new backend:

1. a new Target in Options.hs: https://github.com/BNFC/bnfc/blob/157f9eb2b6d79308049f6cee92fbab3dc2e3a6ef/source/src/BNFC/Options.hs#L57-L61 handled in Main.hs: https://github.com/BNFC/bnfc/blob/157f9eb2b6d79308049f6cee92fbab3dc2e3a6ef/source/main/Main.hs#L72
2. the backend under https://github.com/BNFC/bnfc/tree/master/source/src/BNFC/Backend
3. a new parameter to the testsuite: https://github.com/BNFC/bnfc/blob/157f9eb2b6d79308049f6cee92fbab3dc2e3a6ef/testing/src/ParameterizedTests.hs#L326-L336

Concerning the backend itself, have a look at the other backends to see their structure and what files they produce.

Unfortunately, the backends were added quickly in the 2000s with not a lot of software-engineering principles in mind. So basically, cut-and-paste from an existing backend. This has lead to code bloat and has made BNFC not a pleasure to maintain. Since I have taken over maintainership I have tried to factorize the backends a bit, most recently I unified the C/C++/C++NoStl lexer/parser generator generators (they all targeted Bison). Reintroducing structure into aged code is a time-consuming business. I also spend effort to move the backends toward supporting all of LBNF, which was not the case (and still isn't the case for layout, which is only supported by Haskell/Agda).

This is to say that not all backends are in the state I would like them to be, and cannot serve as good models for backends.

Style-wise, have a look at the Agda backend https://github.com/BNFC/bnfc/blob/157f9eb2b6d79308049f6cee92fbab3dc2e3a6ef/source/src/BNFC/Backend/Agda.hs which is the most recent one. It uses Doc instead of String for its output (some older backends still use String). However, the Agda backend is atypical since it just generates a frontend to a parser generated for Haskell.

In the Haskell backend https://github.com/BNFC/bnfc/blob/157f9eb2b6d79308049f6cee92fbab3dc2e3a6ef/source/src/BNFC/Backend/Haskell.hs, I spend some effort to have it produce a good Makefile. Maybe the Haskell backend could be taken as a model for most aspects (I have put most work here). An exception is the generated lexer generator (Alex) input which does not use lexing states but only regular expressions. This works with Alex but may blow other lexer generators. Here, it might be better to follow the approach for flex, with lexing states: https://github.com/BNFC/bnfc/blob/157f9eb2b6d79308049f6cee92fbab3dc2e3a6ef/source/src/BNFC/Backend/C/CFtoFlexC.hs

Concerning maintenance: Would you be willing to maintain the new backend for the first couple of years?

Also, we (a master student an me) have started a reimplementation of BNFC with the aim of better and more structured code and with developing a common interface for the backends. If that prospers, part of your work would have to be reorganized or redone. But the "content" would stay the same, and there is also considerable work in figuring out the details of the Rust lexer/parser generator and AST/printer representation that would live on.

We could also consider to add the Rust backend directly to the reimplementation of BNFC. If you are interested in this, I could invite you to the new repo; then, we would likely have some developer meetings to synchronize.

[shlevy]

Wow, this is great, thank you! Let me get back to you later this week, after we've had a chance to really exercise BNFC for our use case, but definitely possible we'd be willing to maintain/work on the reimplementation!

[shlevy]

@andreasabel OK, we're pretty happy with BNFC and will want to move forward on implementing a Rust backend. I'd love to have it in the reimplementation, but it would also be good to be able to use whatever we write in the somewhat near term so we can get rid of FFI to C. Do you know how long it will take to get the new implementation usable? In any case, happy to join a developer meeting!

As for maintenance, yeah I can commit to maintaining it for a few years if we get to the point of merging.

[andreasabel]

@shlevy Great!
We decided here locally that it is better to place new backends in BNFC 2.x still (meaning here), to not put pressure on the BNFC-3 development process. The backends will then be ported to BNFC 3 once the new backend infrastructure has been settled. This means you can go ahead...

[chaserhkj]

Hi, I have implemented a preliminary tree-sitter backend that could generate bindings in Rust in #471. If any of the correspondents on this thread are interested, please help me test it out, thank you!

[kod-kristoff]

Also interested in a Rust backend.

@shlevy how far has the work on a rust backend gotten, do you have some code that I can start from?

[shlevy]

Unfortunately not, the project was cancelled not long after my messages above 😞