Rustデータ構造で再帰的なEBNF文法を表現する方法は？

Question

次の例のEBNF文法があるとします。これは完璧な文法ではありませんが、問題を正しく示すはずです。 Wordは、文字と数字のいくつかの数とNumberある

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

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

Term = Word | Number 

は有効な数値リテラルです。

私はそうのような錆でこれを表現するために起動することができます。しかし、すでにここに問題があります

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

私はExprは必ずしもそれがあるので、それが自身の構造体や列挙型である必要はありませんので、typeを使用しようとしましたTermまたはそれ以外のExprのコレクションのみです。これを再帰的に定義することは困難です。 ExprとTermの共用体型をエミュレートしようとすると、その列挙体にExprを再定義し、Enum内に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), 
}