Precedence Climbing

[CAD97]

It's possible to combine precedence climbing with pest-ast derives, but it currently requires doing so by implementing FromPest directly.

This is a fairly rote transformation; we could offer a way to automate this slightly.

[CAD97]

Initial draft idea:

#[derive(Debug, PrecClimb)]
#[prec_climb(rule(Rule::expression))]
pub enum Expression<'i> {
    #[prec_climb(infix(Rule::op_choice), assoc(Left), prec(2))]
    Choice(Box<Expression<'i>>, op::Choice, Box<Expression<'i>>),
    #[prec_climb(infix(Rule::op_strict_sequence), assoc(Left), prec(1))]
    StrictSequence(Box<Expression<'i>>, op::StrictSeq, Box<Expression<'i>>),
    #[prec_climb(infix(Rule::op_trivia_sequence), assoc(Left), prec(1))]
    TriviaSequence(Box<Expression<'i>>, op::TriviaSeq, Box<Expression<'i>>),
    #[prec_climb(primary)]
    Term(Term<'i>),
}

Potential knobs:

• Partially re-implement pest::prec_climber::PrecClimber based on FromPest machinery instead of Pairs to take advantage of its greater flexibility (eating multiple Pairs) and avoid this requisite patch to pest proper to manufacture a single-element Pairs iterator from the single Pair that PrecClimber hands out. (This would also eliminate needing to specify the rule for the operator, as we could just try the FromPest conversion.)

[dragostis]

This looks really good. Should we consider unary ops here as well? The reason why they're not implemented in prec_climber is because they're super simple to parse within the grammar itself, when actually creating the AST, maybe it makes sense to have a way to recognize those same unaries from the grammar itself.

[CAD97]

How would you bundle prefix and postfix operator handling into this? I understand how precedence climbing works for binary ops, but I'm unsure how it's extended to handle unary ops (and, forbid, tertiary ops).

And at this point, I'm thinking we'll want to add a pest_ast.pest set of provided (silent) parameterized rules to help support more advanced patterns we support in pest-ast.

This "runtime" support is starting to look like the direction to grow from here.

An interesting datapoint, however: syn::ExprBinary is just (Box<Expr>, BinOp, Box<Expr>) rather than having more typed information attached at the AST level.