Astray: effortless parsing

Automatically generate type safe Recursive Descent Parsers (RDP) from Rust structures representing an Abstract Syntax Tree (AST).

WARNING: Astray is not ready for production yet. Some features are missing and the documentation is very incomplete. I am working hard on these and will deliver on them as soon as possible.

Mental Model

An AST is, in essence, a tree that represents hierarchical relationships between concepts. An AST has a root, which represents the most encompassing structure in a syntax definition. The root is connected to nodes, and the nodes to other nodes, and so on. The end-nodes that do not link to any nodes but their parents are often called leafs.

Let's call each node in an AST a Syntax Node (SN)
SNs can branch to other SNs, which are called their children.
An SN that does not branch to another SN is called a Leaf
Leaf will always be contain a token.
A Token as the smallest unit of meaning in a program/language (usually symbols or small sets of symbols).
With Astray, SNs are represented by a struct or an enum
- A Rust struct represents a SN that is a composition of its children.
- A Rust enum represents a SN that could branch to either of its children

Below, an example of an AST defined in these terms. As an example, it defines the structure of a computer program:

A Program contains many Functions. Program is the root of our AST.
A Function has a return type, no arguments, and a function body, which consists of a many of Statements.
A return type can either be an int keyword or a float keyword.
A Statement can be either a ReturnStatement or something else we might define later.
A ReturnStatement is a return keyword followed by an Expression.
An Expression is just a literal integer.
The int, return and float keywords, as well as Identifier are leafs. They do not branch to other SN, but rather contain a Token.
In the end, we define the Token enum, which represents the smallest parsable unit in our syntax. They are the building blocks of the AST.

```rust struct Program { function: Vec }

struct Function { return_type: Type, identifier: Identifier, parens: (LParen, RParen) body: Vec }

enum Type { Int(KwInt), Float(KwFloat), }

enum Statement { ReturnStatement(ReturnStatement), // ... }

struct ReturnStatement { kw_return: KwReturn, // keyword return expr: Expr, }

struct Expr { expr: LiteralInt }

// Identifier, KwInt, KwFloat and KwReturn are all Leafs. // They are the bottom of the item hierarchy struct Identifier { value: Token }

struct KwReturn{ value: Token }

struct KwInt{ value: Token }

struct KwFloat{ value: Token }

struct LiteralInt { value: Token }

enum Token { KwReturn, KwInt, KwFloat, LiteralInt(u32), Identifier(String) }

// ... ```

Now that we have defined the types that represent our AST, we need to build a parser function that takes a list of tokens and correctly assembles the AST. So, we want to take something like "int func() { return 2;}", use a lexer to build a Vec<Token> and then parse that into a Program. Astray does not deal with the lexing part, you'll have to use an external crate for that, or build your own

Moving on to the parsing: traditionally, you'd have to build a RDP that would parse each struct and enum you have. This includes at least as many functions as SN you have defined (or less functions, but very big ones).

However, we don't need to go that far thanks to Astray. By annotating Rust items that represent SNs we can use Astray to automatically generate typesafe parsing functions for each SN!

How to start

Define a Token type that represents each building block of your AST.
Start by defining a top level struct (root), like we did before, and work your way down.
Annotate each SN that is not a leaf with #[derive(AstNode)], and then #[token(<token>)], where token is the Token type you defined. It can have any name.
Annotate Leafs with #[leaf(<token>,<token_instance>)], where token is the Token type you defined in step 1 and token_instance is the specific instance of the Token type that you are expecting this leaf to contain.
Get an interator of Tokens and call ::parse(&mut iter) on the top level type you defined. For the previous example, it would be Program::parse(&mut iter).
You'll get a Result<Program,ParseError<Program>>. If your tokens matched the specification of AST you gave, you'll have Program struct correctly parsed.
Extend the syntax as much as you want, knowing you will never have to build parsing functions for anything.

Example

For more examples, take a look at the tests folder. In general, tests will be more accurate than any future documentation, since they are checked for errors by the compiler, contrary to markdown files.

There is much more to Astray than this! I'll document it as soon as possible.

```rust fn main(){ let tokens = vec![ Token::Identifier("var1".to_string()), Token::EqualSign, Token::LiteralInt(2), ]

let result = AssignStatement::parse(&mut tokens.into_token_iter());
match result {
    Ok(assign_statement) => println!("Assign statement was successfully parsed"),
    Ok(parse_err) => println!("There was a parsing error {err}"),
}

}

enum Token { Identifier(String), EqualSign, LiteralInt(u32), }

[derive(AstNode)]

[token(Token)]

struct AssignStatement { ident: Identifier, eq: EqualSign, literal_int: LiteralInt }

[leaf(Token,Token::Identifier)]

struct Identifier{ value: Token }

[leaf(Token,Token::LiteralInt)]

struct LiteralInt{ value: Token }

[leaf(Token,Token::EqualSign)]

struct EqualSign{ value: Token }

```

TODO list

[ ] More/more thorough examples in the documentation
[X] Reference to other syntax structures
[X] Product nodes (structs)
[X] Sum nodes (enums)
[ ] Tuple structs
[ ] Self referencing SNs
[ ] Common use cases (Delimiters, Separators, Either)
[ ] Implementations of parse for common std types
- [X] Option
- [X] Vec
- [ ] Tuple
- [ ] Arrays
- [ ] Box
- [ ] Rc
- [ ] Arc
- [ ] RefCell