pub struct PrattParser<R: RuleType> { /* private fields */ }
Expand description
Struct containing operators and precedences, which can perform Pratt parsing on
primary, prefix, postfix and infix expressions over Pairs
. The tokens in Pairs
should alternate in the order:
prefix* ~ primary ~ postfix* ~ (infix ~ prefix* ~ primary ~ postfix*)*
§Panics
Panics will occur when:
pairs
is empty- The tokens in
pairs
does not alternate in the expected order. - No
map_*
function is specified for a certain kind of operator encountered inpairs
.
§Example
The following pest grammar defines a calculator which can be used for Pratt parsing.
WHITESPACE = _{ " " | "\t" | NEWLINE }
program = { SOI ~ expr ~ EOI }
expr = { prefix* ~ primary ~ postfix* ~ (infix ~ prefix* ~ primary ~ postfix* )* }
infix = _{ add | sub | mul | div | pow }
add = { "+" } // Addition
sub = { "-" } // Subtraction
mul = { "*" } // Multiplication
div = { "/" } // Division
pow = { "^" } // Exponentiation
prefix = _{ neg }
neg = { "-" } // Negation
postfix = _{ fac }
fac = { "!" } // Factorial
primary = _{ int | "(" ~ expr ~ ")" }
int = @{ (ASCII_NONZERO_DIGIT ~ ASCII_DIGIT+ | ASCII_DIGIT) }
Below is a PrattParser
that is able to parse an expr
in the above grammar. The order
of precedence corresponds to the order in which op
is called. Thus, mul
will
have higher precedence than add
. Operators can also be chained with |
to give them equal
precedence.
let pratt =
PrattParser::new()
.op(Op::infix(Rule::add, Assoc::Left) | Op::infix(Rule::sub, Assoc::Left))
.op(Op::infix(Rule::mul, Assoc::Left) | Op::infix(Rule::div, Assoc::Left))
.op(Op::infix(Rule::pow, Assoc::Right))
.op(Op::prefix(Rule::neg))
.op(Op::postfix(Rule::fac));
To parse an expression, call the map_primary
, map_prefix
, map_postfix
,
map_infix
and parse
methods as follows:
fn parse_expr(pairs: Pairs<Rule>, pratt: &PrattParser<Rule>) -> i32 {
pratt
.map_primary(|primary| match primary.as_rule() {
Rule::int => primary.as_str().parse().unwrap(),
Rule::expr => parse_expr(primary.into_inner(), pratt), // from "(" ~ expr ~ ")"
_ => unreachable!(),
})
.map_prefix(|op, rhs| match op.as_rule() {
Rule::neg => -rhs,
_ => unreachable!(),
})
.map_postfix(|lhs, op| match op.as_rule() {
Rule::fac => (1..lhs+1).product(),
_ => unreachable!(),
})
.map_infix(|lhs, op, rhs| match op.as_rule() {
Rule::add => lhs + rhs,
Rule::sub => lhs - rhs,
Rule::mul => lhs * rhs,
Rule::div => lhs / rhs,
Rule::pow => (1..rhs+1).map(|_| lhs).product(),
_ => unreachable!(),
})
.parse(pairs)
}
Note that map_prefix
, map_postfix
and map_infix
only need to be specified if the
grammar contains the corresponding operators.
Implementations§
Source§impl<R: RuleType> PrattParser<R>
impl<R: RuleType> PrattParser<R>
Sourcepub fn map_primary<'pratt, 'a, 'i, X, T>(
&'pratt self,
primary: X,
) -> PrattParserMap<'pratt, 'a, 'i, R, X, T>
pub fn map_primary<'pratt, 'a, 'i, X, T>( &'pratt self, primary: X, ) -> PrattParserMap<'pratt, 'a, 'i, R, X, T>
Maps primary expressions with a closure primary
.