Astree：轻松解析

仅使用Rust快速将标记的线性结构解析为抽象语法树（AST）。

警告：Astree尚未准备好投入生产。许多功能尚未实现，文档也非常不完整。我正在努力改进这些，并将尽快完成。

思维模型

AST本质上是一棵表示概念之间层次关系的树。Astree提供了一种框架，用于使用Rust语言仅从任何源代码描述构建AST的规则。

我们可以将AST中的每个节点称为语法节点（SN）。SN可以分支到其他SN，称为其子节点（作为一个家族树的隐喻）。
此外，SN还可以分支到叶子，叶子是那些不分支到其他任何东西的SN。
叶子总是包含一个标记。将标记视为程序/语言中最小的意义单元。
SN由Rust的struct或enum表示。
Rust的struct表示一个SN，它是由其子节点组成的。
Rust的enum表示一个SN，在实际上只能作为其子节点之一的双亲。

下面是一个用这些术语定义的AST示例。在这种情况下，它表示一个包含函数列表的计算机程序。
函数有一个返回类型、没有参数和一个体，体由一系列语句组成。
返回类型可以是int关键字或float关键字。语句可以是ReturnStatement或其他我们可能以后定义的东西。ReturnStatement是一个后跟表达式的return关键字。然后我们会定义表达式，等等。

最后，你会找到Leaf，也就是用于其他SN（符号网络）的令牌容器。

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


// we could go on and on
struct Expr {
    // ...
}

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

// ...

现在我们已经定义了表示我们AST（抽象语法树）的类型，我们需要构建一个解析函数，该函数接收一个令牌列表并将其正确组装成树。因此，我们想要将类似这样的内容解析成一个程序：“int func() { return 2;}"。这听起来可能很令人畏惧和困难：确实是。

然而，多亏了Astree，我们不必走那么远。通过注释表示AST的Rust项目，我们可以使用Astree为每个SN自动生成类型安全的解析函数！

如何开始

1. 定义一个代表程序中每个最小意义实例的Token类型。它们通常是符号或小符号序列。
2. 首先定义一个顶层结构体，就像我们之前做的那样，然后逐步向下进行。
3. 使用#[derive(AstNode)]和#[token(<token>)]对每个非叶SN进行注释，其中token是您定义的Token类型。它可以有任意名称。
4. 使用#[derive(AstNode)]和#[leaf(<token>,<token_instance>)]对叶进行注释，其中token是您在步骤1中定义的Token类型，而token_instance是您期望这个叶包含的Token类型的特定实例。
5. 获取Token的迭代器，并在您定义的顶层类型上调用::parse(<iter>)。对于前面的示例，它将是Program。
6. 您将获得一个Result<Program,ParseError<Program>>。如果您的令牌匹配您给出的AST规范，您将获得正确解析的Program结构。
7. 根据需要扩展语法，知道您永远不必为任何内容构建解析函数。

示例

有关更多示例，请参阅测试文件夹。通常，测试将比任何未来的文档更准确，因为它们是由编译器检查错误的，而Markdown文件不是。Astree的内容远不止这些！我会尽快记录。

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
}

#[derive(AstNode)]
#[leaf(Token,Token::Identifier)]
struct Identifier{
    value: Token
}

#[derive(AstNode)]
#[leaf(Token,Token::LiteralInt)]
struct LiteralInt{
    value: Token
}

#[derive(AstNode)]
#[leaf(Token,Token::EqualSign)]
struct EqualSign{
    value: Token
}

待办事项列表

• 在文档中添加更多/更详尽的示例
• 对其他语法结构的引用
• 产品节点（结构体）
• 求和节点（枚举）
• 元组结构体
• 自引用语法结构
• 常见用例（分隔符、分隔符、Either）
• 实现常见std类型的解析
  • Option
  • Vec
  • 元组
  • 数组
  • Box
  • Rc
  • Arc
  • RefCell