如何在 Rust 数据结构中表示递归 EBNF 语法？

Question

假设我有以下示例 EBNF 语法。这不是一个完美的语法，但它应该正确地证明了问题。

Statement = FunctionDefinition | Assignment | Expr ;
Expr = { Term | "(" , Expr , ")" } ;

Assignment = Word , "=" , Expr ;
FunctionDefinition = Word , { Word } , "=" , Expr ;

Term = Word | Number

其中 Word 是一些字母和数字，Number 是有效的数字文字。

我可以像这样开始用 Rust 表示它：

enum Statement {
    FunctionDefinition {
        name: String,
        params: Vec<String>,
        body: Expr,
    },
    Assignment {
        name: String,
        body: Expr,
    },
    //TODO: Expr
}

这里已经有问题了。如何添加 Expr？ Expr 应该有自己的定义，因为它也在其他几个地方使用。给 Expr 自己单独的定义，然后将其添加到此枚举将重新定义它。

如果我仍然继续并开始尝试定义 Expr，我运行会遇到更多问题：

type Expr = Vec<...?...>;
// or maybe...
struct Expr {
    terms: Vec<Expr>, // but what about Term??
}

我尝试使用 type 因为 Expr 不一定需要是它自己的结构或枚举，因为它只是 Term 或其他 [=15= 的集合]s。但是很难递归定义它。如果我尝试使用枚举来模拟 Expr 和 Term 的联合类型，那么我必须在该枚举中重新定义 Expr 并在枚举中定义 Term，这使得 Term 在其他结构中不可用我将需要。

Answer 1

Expr 可以是 type 别名，但您需要定义一个 enum 来表示交替。 Term 也需要单独 enum.

enum Statement {
    FunctionDefinition {
        name: String,
        params: Vec<String>,
        body: Expr,
    },
    Assignment {
        name: String,
        body: Expr,
    },
    Expr(Expr),
}

type Expr = Vec<ExprItem>;

enum ExprItem {
    Term(Term),
    Parenthesized(Expr),
}

enum Term {
    Word(String),
    Number(f64),
}

如何在 Rust 数据结构中表示递归 EBNF 语法？

How to represent recursive EBNF grammar in Rust data structures?

parsing

ebnf

rust

data-structures