Translating Rust to other languages (Pt 1- Context Free Grammar)

Overview

At my place of current employment I write libraries in Rust which are called by other languages, on multiple operating systems, on multiple platforms. Furthermore, it involves taking in streams of data from different communications buses and decoding it into usable forms by other developers on those other platforms, in those other languages! As a result, I've got rust projects with hundreds of structs that are exposed through a Rust FFI.

I have zero desire to maintain those translations by hand, so I wrote a tool to do it for me. There are multiple ways to go about this, I could have written a naive translator which goes line by line and and expects the rust structs to look a very specific way. That, however, would not have been maintainable, or able to be shared, so I instead used a parsing library called Lark. Lark allows me to write a context-free grammar to specify the language I'm expecting, and provide a nice interface for me to turn defined symbols into python objects which are easy to work with. Once I have those objects, building source code in other languages is fairly trivial.

You can see the whole project here: https://github.com/LivingInSyn/Rust_Api_Generator

The Context Free Grammar

I won't go into too much detail on all of the ins and outs of writing a grammar. I will mostly be focusing on the grammar that I wrote. Lark has a good tutorial here, which goes much more in depth

When writing a grammar from scratch, I find that it's best to work from the inside out. That is, start with the most basic element, and work backwards. Thing names (variables, structs, etc) are a great place to start, and that's where we'll start today. We'll call our first symbol 'name' and it looks like this:

?name: /[a-z_A-Z][a-z_A-Z0-9]*/

The question mark operator in front says, if there's only one child of this symbol, don't wrap it in another object (when it's parsed), just give me the child. The ? is followed by the name of our symbol, which in this case is simply 'name'. Next is a regular expression which defines what a name can look like. In this Case, it's an upper or lowercase A-Z, or an underscore, followed by an unlimited number of alphanumeric characters and underscores.

Next we're going to define something we call an rtype. This won't make much sense until we make it further in the grammar, but suffice to say, an rtype is defined as either a name, or an array declaration. It looks like this

?rtype: name
    | array

Once we have a definition for an rtype, we can define a pointer modifier that we'll use in other declarations.

pointer: "*" mutable
    | "*" const

mutable: "mut"
const: "const"

Here we defined 3 symbols, pointer, mutable and const. We made mutable and const their own symbols because we want to be able to perform different actions based on their properties. Pointer is defined by the string "*" followed by one of those two symbols, which are in turn, defined by strings

Once we have a definition for an rtype and a pointer, we can define something called a 'modified type' This tells us if we're looking at a name in another declaration if it's a pointer or not. The brackets ([]) around the pointer symbol indicate that it's optional. Thus

*mut i16

and

i16

would both be matched by the ?modifiedtype symbol.

?modifiedtype: [pointer] rtype

Now lets backtrack a moment and define 'array' because we already used it in our rtype definition. Array is defined by an opening bracket, a modifiedtype, a semicolon, one or more digits that starts with 1-9 (can't be 0). Lastly, it must end with a closing bracket.

array: "[" modifiedtype ";" /[1-9]{1}[0-9]*/ "]"

Now that we've got a good handle on what some of the context free grammar rules look like, lets skip ahead a bit and see the rest of what we need to define a struct

reprc: "#[repr(C)]"

comment: /\/\/[^\n]*/

decl: [ispub] name ":" modifiedtype [","]
    | comment

?ispub: "pub"
struct:  [reprc] [ispub] "struct" name "{" decl+ "}"

Here we define the repr(C) instruction to rust which tells rust to have this struct use C-compliant memory layout. We'll use this (and pub) to decide which structs to translate. If it's not repr(C) and pub, it doesn't make sense to translate it, since it won't work over an FFI interface. We declare that a decl is a combination of if it's public or not, a name, a colon, a modified type, and an optional comma. It can also be comment, since we allow comments inside of struct definitions. It's worth noting here that we intentionally designed the grammar to NOT handle multiline comments. A preprocessor will remove them later. We want single line comments to move over, NOT multiline comments.

We define a struct as possibly reprc, possibly public, the word struct, a name, an opening brace, one or more decl's and a closing brace.

Next, we're going to define a few symbols that we're not going to translate between languages. We have to define them in our grammar so that it doesn't break when we parse the file. They are 'using' statements, 'extern crate' statements and 'impl' statements. The definitions are here:

externcrate: "extern" "crate" name [optionalas] ";"
?optionalas: "as" name

usedecl: "use" namespace+ ";"
?namespace: ["::"] name

impl: ["unsafe"] "impl" name "for" name "{}"

The final step is to define a start point for the file and a top level definition. There's also some instructions for Lark, basically ignore whitespace, and handle things as strings wherever possible.

?statement: struct
    | usedecl
    | comment
    | impl
    | externcrate

?start: statement+

//for use by lark
%import common.ESCAPED_STRING
%import common.WS
%ignore WS

The full context free grammar can be found here

Using the CFG

Now that we've got a CFG, lets parse it into an abstract syntax tree. We will work on the following rust struct as a starting point:

#[repr(C)]
pub struct bar {
    pub unsigned_32bit: u32,
    pub arraytest: [u8;10],
    pub pntr_array: [*mut c_char;4],
}

Next, we'll run the following python code. Basically, we're creating the parser, passing it in our grammar file that we made in the previous section. Then we're asking it to parse some input, and print the resulting syntax tree, in a pretty way.

from lark import Lark

gf = open("rgrammar.g", 'r')
parser = Lark(gf.read(), parser="lalr")
tree = parser.parse('''#[repr(C)]
pub struct bar {
    pub unsigned_32bit: u32,
    pub arraytest: [u8;10],
    pub pntr_array: [*mut c_char;4],
}''')
print(tree.pretty())

running this code gives the following output:

struct
  reprc
  ispub
  bar
  decl
    ispub
    unsigned_32bit
    u32
  decl
    ispub
    arraytest
    array
      u8
      10
  decl
    ispub
    pntr_array
    array
      modifiedtype
        pointer
          mutable
        c_char
      4

This is our abstract syntax tree. We can see that the struct has a reprc on it, is public, is named bar, and that it has 4 decl's in it, with all of their associated fields.

Conclusion

In this article, we talked about creating the CFG and using it to create a basic abstract syntax tree using Lark. In the next section(s), we'll use this information to massage the objects created by lark into a more usable form, and then finally, output code in other languages.

Comments

[#benaryorg]

I wonder whether you could use Rust's macro system for the AST creation.
I mean, it already builds an AST there, so you could use a macro that exposes a text version of the AST directly from the Rust compiler.
That way you wouldn't need to re-define the language externally.…

[Jeremy Mill]

Yup, I think you could. Other people suggested this on Reddit as well. This was fun to write though, and relatively quick