Astray：轻松解析

自动从代表抽象语法树 (AST) 的 Rust 结构生成类型安全的递归下降解析器 (RDP)。

警告：Astray 尚未准备好投入生产。一些功能尚未完善，文档也非常不完整。我正在努力改进这些，并尽快交付。

此仓库将 astray_core 和 astray_macro 合并到一个 crate 中。

心智模型

抽象语法树 (AST) 实质上是一个表示概念之间层次关系的树。AST 有一个根，它表示语法定义中最全面的结构。根连接到节点，节点连接到其他节点，依此类推。不连接任何节点但连接其父节点的末端节点通常被称为叶。

• 让我们称 AST 中的每个节点为语法节点 (SN)
• SN 可以分支到其他 SN，这些被称为它们的子节点。
• 不分支到其他 SN 的 SN 称为叶
• 叶始终是引用标记。
• 标记是程序/语言中意义的最小单位（通常是符号或小符号集）。
• 在 Astray 中，SN 由一个 struct 或一个 enum 表示
  • Rust struct 表示一个 SN，它是其子节点的组合
  • Rust enum 表示一个 SN，实际上可以分支到其子节点中的任何一个

以下是一个使用这些术语定义的 AST 示例。它定义了计算机程序的结构

• 程序包含许多函数。程序是 AST 的根。
• 函数有一个返回类型、没有参数和一个由多个语句组成的函数体。
• 返回类型可以是 int 关键字或 float 关键字。
• 语句可以是返回语句或其他我们以后可能定义的内容。
• 返回语句是一个 return 关键字后跟一个表达式。
• 表达式只是一个整数文字。
• int、return 和 float 关键字，以及标识符都是叶节点。它们不会分支到其他SN，而是包含一个标记。
• 最后，我们定义一个标记枚举，它代表我们语法中最小的可解析单元。它们是AST的构建块。

struct Program {
    function: Vec<Function>
}

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

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)
}

// ...

既然我们已经定义了代表我们的AST的类型，我们需要构建一个解析函数，该函数接受一个标记列表并正确地将AST组装起来。所以，我们想要处理类似 int func() return 2 的内容，使用词法分析器构建一个 Vec<Token>，然后将其解析成一个程序。Astray不处理词法分析部分。您将不得不使用一个外部包或自己构建。

接下来是解析：传统上，您必须为每个结构体和枚举构建一个RDP来解析。这至少包括与您定义的SN一样多的函数（或少一些函数，但更多）。这听起来很复杂且容易出错：这是因为确实如此。

然而，由于Astray，我们不需要走那么远。通过注释代表SN的Rust项目，我们可以使用Astray为每个SN自动生成类型安全的解析函数！

如何开始

1. 定义一个 Token 类型，它代表AST的每个构建块。
2. 首先定义一个顶级结构（根），就像我们之前做的那样，然后逐步向下。
3. 使用 #[SN(<token>)] 注释每个非叶SN，其中 <token> 是您定义的 Token 类型。它可以有任意名称。
4. 使用 #[leaf(<token>,<token_instance>)] 注释叶节点，其中 token 是您在步骤1中定义的 Token 类型，而 token_instance 是您期望这个叶节点包含的 Token 类型的特定实例。
5. 或者，只需使用 #[derive(leaf)] 注释Token类型。这将自动为每个枚举变体生成叶SN。
6. 获取 Token 的迭代器，并在您定义的顶级类型上调用 ::parse(&mut iter)。对于前面的示例，它将是 Program::parse(&mut iter)。
7. 您将得到一个 Result<Program,ParseError<Program>>。如果您的标记与您提供的 AST 规范匹配，则将正确解析 Program 结构体。
8. 根据需要扩展语法，知道您永远不必为任何内容构建解析函数。

示例

有关更多示例，请查看测试文件夹。一般来说，测试将比任何未来的文档更准确，因为它们由编译器检查错误，而 Markdown 文件则不是。

Astray 还有更多功能！我会尽快记录下来。

use astray::{SN, Leaf};

#[SN(Token)]
struct Program {
    function: Vec<Function>
}

#[SN(Token)]
struct Function {
    return_type: Type,
    identifier: Identifier,
    parens: (LParen, RParen)
    body: Vec<Statement>
}

#[SN(Token)]
enum Type {
    Int(KwInt),
    Float(KwFloat),
}

#[SN(Token)]
enum Statement {
    ReturnStatement(ReturnStatement),
}

#[SN(Token)]
struct ReturnStatement {
    kw_return: KwReturn, 
    expr: Expr,
}

#[SN(Token)]
struct Expr {
    expr: LiteralInt
}

#[derive(Leaf)] // auto generates leaf SNs for each node in this Enum
enum Token {
    KwReturn,
    KwInt,
    KwFloat,
    EqualSign,
    LeftParen,
    RightParen,
    LiteralInt(u32),
    Identifier(String)
}

fn main(){
    // result of lexing "int function1() return 2"
    let tokens = vec![
        Token::KwInt,
        Token::Identifier("function1".to_string())
        Token::LeftParen
        Token::RightParen
        Token::KwReturn,
        Token::LiteralInt(2),
    ]

    let result = Program::parse(&mut tokens.into_token_iter());
    let expected_program = Program {
        function: vec![
            Function {
                return_type: Type::Int(KwInt{token: Token::KwInt}),
                identifier: Identifier {
                    token: Token::Identifier("function1".to_string())
                },
                parens: (LParen {token: Token::LParen}, RParen {token: Token::RParen})
                body: vec![
                    Statement::ReturnStatement(ReturnStatement{
                        kw_return: KwReturn {token: Token::KwReturn}
                        expr: Expr {
                            expr: LiteralInt {token: Token::LiteralInt(2)}
                        }
                    })
                ]
            }
        ]
    }
    match result {
        Ok(result_program) => assert_eq!(result, expected_program),
        Err(parse_err) => println!("There was a parsing error: {err}"),
    }
}