如何在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或其他Expr的集合。然而，这种递归定义很难实现。如果我尝试使用枚举类型来模拟Expr和Term的联合类型，那么我必须在该枚举中重新定义Expr并在枚举中定义Term，这将使得我需要的其他结构体无法使用Term。

- Sunjay Varma

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

- Francis Gagné

---

非常好！谢谢！我想没有办法避开 Expr(Expr) 或 Term(Term)。有点丑陋，但它能用。 - Sunjay Varma