parsing - 如何在 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 的集合s 或其他 Expr。但是很难递归定义它。如果我尝试使用枚举来模拟 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),
}