Given that the result of the parsing is not known (it could be an integer, a sum of expressions, or a product of expressions), you need to return one single type, at compiletime, which must be able to contain / branch / dispatch over these multiple possible implementors at runtime. That is, depending on your pattern, you'd want to say that you are returning...

an(y) Exp
implementor, but where you don't know which one exactly: that choice shall be dynamic / depend on the value of runtime data (such as the parsed string). If the set of possible results is extensible (e.g., by downstream users), then you'd want to use a dyn Trait
, such as a dyn Exp
, which, when returned, needs to be Box
ed (or Rc
ed): Box<dyn Expr>
, which you can then freely wrap in an Option
or a Result
, or a Vec
, or whatnot.

one of an integer literal, a sum of expressions, or a product of expressions exactly. The set of possible results is fixed / bounded, and you know all of the possibilities. In that case, the runtime / dyn
amic dispatch will just be branchbased, using an enum
.
Given your use case, you should really go for the latter:
pub enum Expr {
Int(Int),
Plus(Plus<Box<Expr>, Box<Expr>>),
Mult(Mult<Box<Expr>, Box<Expr>>),
}
pub struct Int{
pub(crate) val: i32,
}
pub struct Plus<T: Exp> {
pub e1: T,
pub e2: T,
}
pub struct Mult<T: Exp> {
pub e1: T,
pub e2: T,
}
And at that point, the generics are now superfluous / redundant: the only type meeting the Exp
contract will be that Expr
(or Box<Expr>
for technical reasons) disjonction of cases:
pub enum Expr {
Int(Int),
Plus(Plus),
Mult(Mult),
}
pub struct Int {
pub(crate) val: i32,
}
pub struct Plus {
pub e1: Box<Expr>,
pub e2: Box<Expr>,
}
pub struct Mult {
pub e1: Box<Expr>,
pub e2: Box<Expr>,
}
Congratulations, you now have an AST.
Note that you could flatten this data structure as:
pub enum Expr {
Int {
val: i32,
},
Sum {
e1: Box<Expr>, // or `Box<Self>`, it's the same, but showcases the recursive definition (which is why the `Box` or any other form of indirection is needed).
e2: Box<Expr>,
},
// ...
}
which has its pros and cons, so it's not necessarily better (e.g., no privacy), nor worse (e.g., simpler). EDIT: heh, @steffahn and I posted this part at almost the same minute
That syntax is to express a "third bullet" w.r.t. the two ones at the beginning of my post:
 you'd be returning some implementor, unknown to the caller, but which you, on the other hand, know. Note that this implementor is a fixed type. You thus can't use
impl Exp
in return position to say that you will be returning two (or more) possible implementors of Exp
. And since that's what you'd want to do when parsing runtime / dynamic data (an integer, or a sum, etc.), then > ... impl Exp
is not a good fit here