parcours

Trait Combinator

Source 
pub trait Combinator<I, S>: Parser<I, S>
where
    Self: Sized,
{

Show 14 methods    // Provided methods
    fn then<P: Parser<I, S>>(self, other: P) -> All<(Self, P)> { ... }
    fn or<P: Parser<I, S>>(self, other: P) -> Any<(Self, P)>
       where I: Clone { ... }
    fn map<O, F: FnOnce(Self::O) -> O>(self, f: F) -> Map<Self, F> { ... }
    fn map_with<O, F: FnOnce(Self::O, &mut S) -> O>(
        self,
        f: F,
    ) -> MapWith<Self, F> { ... }
    fn filter<F: FnOnce(&Self::O) -> bool>(self, f: F) -> Filter<Self, F> { ... }
    fn filter_map<O, F: FnOnce(Self::O) -> Option<O>>(
        self,
        f: F,
    ) -> FilterMap<Self, F> { ... }
    fn then_ignore<P: Parser<I, S>>(
        self,
        other: P,
    ) -> Map<All<(Self, P)>, fn((<Self as Parser<I, S>>::O, <P as Parser<I, S>>::O)) -> Self::O> { ... }
    fn ignore_then<P: Parser<I, S>>(
        self,
        other: P,
    ) -> Map<All<(Self, P)>, fn((<Self as Parser<I, S>>::O, <P as Parser<I, S>>::O)) -> P::O> { ... }
    fn delimited_by<L, R>(
        self,
        l: L,
        r: R,
    ) -> Map<All<(L, Self, R)>, fn((L::O, Self::O, R::O)) -> Self::O>
       where L: Parser<I, S>,
             R: Parser<I, S> { ... }
    fn repeated<O>(self) -> Repeated<Self, fn() -> O>
       where I: Clone,
             Self: Clone,
             O: Default + Extend<Self::O> { ... }
    fn separated_by<Sep, O>(self, sep: Sep) -> SeparatedBy<Self, Sep, fn() -> O>
       where I: Clone,
             Self: Clone,
             Sep: Parser<I, S> + Clone,
             O: Default + Extend<Self::O> { ... }
    fn opt(self) -> Opt<Self>
       where I: Clone { ... }
    fn chain<P>(
        self,
        other: P,
    ) -> Map<All<(Self, P)>, fn((<Self as Parser<I, S>>::O, <P as Parser<I, S>>::O)) -> Chain<<Self::O as IntoIterator>::IntoIter, <P::O as IntoIterator>::IntoIter>>
       where P: Parser<I, S>,
             Self::O: IntoIterator,
             P::O: IntoIterator<Item = <Self::O as IntoIterator>::Item> { ... }
    fn and_then<P: Parser<I, S>, F: FnOnce(Self::O) -> P>(
        self,
        f: F,
    ) -> AndThen<Self, F> { ... }

}
Expand description

A combinator combines parsers to form new ones.

Every Parser implements the Combinator trait. To use the Combinator trait, import it as follows:

use parcours::Combinator;

Provided Methods§

Source

fn then<P: Parser<I, S>>(self, other: P) -> All<(Self, P)>

If both parsers yield an output, return the pair of their outputs.

The expression p0.then(p1) is equivalent to all((p0, p1)). However, p0.then(p1).then(p2) is equivalent to all((all((p0, p1)), p2)) not all((p0, p1, p2)). That means that if you chain together more than two parsers with then, things might get a bit messy, because you get nested tuples. In that case, using all directly is preferable.

Examples found in repository?
examples/bc.rs (line 154)
145fn atomic<'a>() -> impl Parser<&'a [Token], O = Expr> {
146    // succeed if the first element in the slice is the token `tk`
147    let eq = |tk| slice::first_filter(move |t, _| *t == tk);
148    // parentheses
149    let par = lazy!(expr).delimited_by(eq(Token::LPar), eq(Token::RPar));
150    // if the first token is a number, return a number expression, else fail
151    let num = slice::first_filter_map(select!(Token::Num(n) => Expr::Num(*n)));
152    let neg = slice::first_filter(|t, _| *t == Token::Op(Op::Sub));
153    let negs = neg.repeated::<Vec<_>>();
154    negs.then(par.or(num))
155        .map(|(negs, atom)| negs.iter().fold(atom, |acc, _x| Expr::Neg(Box::new(acc))))
156}
157
158/// Parse an expression from a token slice.
159///
160/// An expression is an atomic term followed by
161/// a (possibly empty) sequence of operator-atomic term pairs.
162///
163/// This uses precedence climbing to respect operator precedences.
164fn expr<'a>() -> impl Parser<&'a [Token], O = Expr> {
165    let op = slice::first_filter_map(select!(Token::Op(op) => *op));
166    atomic()
167        .then(op.then(lazy!(atomic)).repeated::<Vec<_>>())
168        // for precedence climbing to work, we have to implement
169        // a few traits for operators and expressions, see below
170        .map(|(head, tail)| prec_climb::climb(head, tail))
171}
More examples
Hide additional examples
examples/lambda.rs (line 156)
147fn term<'a>() -> impl Parser<&'a str, State<'a>, O = Term<'a>> {
148    let vars = ident()
149        .repeated()
150        .delimited_by(token("|"), token("|").or(expected("identifier or |")));
151    let abst = vars.and_then(|vars: Vec<_>| {
152        // we parse a term with the bound variables put into the state
153        with_vars(vars.clone(), lazy!(term)).map(|t| (Term::Abst(vars, Box::new(t))))
154    });
155    let args = atomic().repeated::<Vec<_>>();
156    let appl = atomic().then(args).map(|(head, args)| {
157        if args.is_empty() {
158            head
159        } else {
160            Term::Appl(Box::new(head), args)
161        }
162    });
163    abst.or(appl).then_ignore(space()).or(expected("term"))
164}
examples/json.rs (line 93)
87fn json<'a>() -> impl Parser<&'a str, O = JsonVal<&'a str>> {
88    let str = str().delimited_by(matches("\""), matches("\""));
89
90    let token = |s: &'a str| matches(s).then_ignore(space());
91    let arr = lazy!(json).separated_by(token(","));
92    let arr = arr.delimited_by(token("["), matches("]"));
93    let map = str.clone().then_ignore(token(":")).then(lazy!(json));
94    let map = map.separated_by(token(","));
95    let map = map.delimited_by(token("{"), matches("}"));
96
97    any((
98        arr.map(JsonVal::Arr),
99        map.map(JsonVal::Map),
100        str.map(JsonVal::Str),
101        num().map(JsonVal::Num),
102        matches("true").map(|_| JsonVal::True),
103        matches("false").map(|_| JsonVal::False),
104        matches("null").map(|_| JsonVal::Null),
105    ))
106    .then_ignore(space())
107}
Source

fn or<P: Parser<I, S>>(self, other: P) -> Any<(Self, P)>
where I: Clone,

If the first parser succeeds, return its output, otherwise return the output of the second parser.

The expression p0.or(p1)/*...*/.or(pn) is equivalent to any((p0, p1,/*..., */pn)). However, if more than two parsers are combined, any might yield better performance.

Examples found in repository?
examples/bc.rs (line 154)
145fn atomic<'a>() -> impl Parser<&'a [Token], O = Expr> {
146    // succeed if the first element in the slice is the token `tk`
147    let eq = |tk| slice::first_filter(move |t, _| *t == tk);
148    // parentheses
149    let par = lazy!(expr).delimited_by(eq(Token::LPar), eq(Token::RPar));
150    // if the first token is a number, return a number expression, else fail
151    let num = slice::first_filter_map(select!(Token::Num(n) => Expr::Num(*n)));
152    let neg = slice::first_filter(|t, _| *t == Token::Op(Op::Sub));
153    let negs = neg.repeated::<Vec<_>>();
154    negs.then(par.or(num))
155        .map(|(negs, atom)| negs.iter().fold(atom, |acc, _x| Expr::Neg(Box::new(acc))))
156}
More examples
Hide additional examples
examples/lambda.rs (line 129)
115fn atomic<'a>() -> impl Parser<&'a str, State<'a>, O = Term<'a>> + Clone {
116    let var = ident().map_with(|v, state: &mut State<'a>| {
117        // find the de Bruijn index of the variable
118        let db = state.vars.iter().rev().position(|b| *b == v);
119        // if the variable was not bound, then record this as error, but then continue,
120        // because such errors are not fatal parsing errors
121        Term::Var(db.unwrap_or_else(|| {
122            state.errs.push(Error::UnboundVar(v));
123            0
124        }))
125    });
126    // here, we see error reporting in action:
127    // if a term that was opened with a parenthesis is not closed by a parenthesis,
128    // we store an error message and fail
129    var.or(lazy!(term).delimited_by(token("("), token(")").or(expected("closing parenthesis"))))
130}
131
132/// Extend the state with variables, parse with `p`, then remove the variables again.
133fn with_vars<'a, I, P>(vars: Vec<&'a str>, p: P) -> impl Parser<I, State<'a>, O = P::O>
134where
135    P: Parser<I, State<'a>>,
136{
137    from_fn(|input, state: &mut State<'a>| {
138        let vars_len = vars.len();
139        state.vars.extend(vars);
140        let y = p.parse(input, state);
141        state.vars.truncate(state.vars.len() - vars_len);
142        y
143    })
144}
145
146/// Parse a term.
147fn term<'a>() -> impl Parser<&'a str, State<'a>, O = Term<'a>> {
148    let vars = ident()
149        .repeated()
150        .delimited_by(token("|"), token("|").or(expected("identifier or |")));
151    let abst = vars.and_then(|vars: Vec<_>| {
152        // we parse a term with the bound variables put into the state
153        with_vars(vars.clone(), lazy!(term)).map(|t| (Term::Abst(vars, Box::new(t))))
154    });
155    let args = atomic().repeated::<Vec<_>>();
156    let appl = atomic().then(args).map(|(head, args)| {
157        if args.is_empty() {
158            head
159        } else {
160            Term::Appl(Box::new(head), args)
161        }
162    });
163    abst.or(appl).then_ignore(space()).or(expected("term"))
164}
Source

fn map<O, F: FnOnce(Self::O) -> O>(self, f: F) -> Map<Self, F>

Apply a function to the output of the parser.

Examples found in repository?
examples/bc.rs (line 92)
85fn token<'a>() -> impl Parser<&'a str, O = Token> + Clone {
86    // try to match a given binary operator and return it if it is present
87    let match_op = |op: Op| {
88        from_fn(move |input: &str, _| Some((Token::Op(op), input.strip_prefix(op.as_char())?)))
89    };
90    any((
91        // nonempty sequence of digits
92        str::take_while1(|c, _| c.is_ascii_digit()).map(|n| Token::Num(n.parse().unwrap())),
93        str::matches("(").map(|_| Token::LPar),
94        str::matches(")").map(|_| Token::RPar),
95        // for every operator, try to match it
96        any([Op::Add, Op::Sub, Op::Mul, Op::Div, Op::Exp].map(match_op)),
97    ))
98}
99
100/// Parse whitespace.
101fn space<'a>() -> impl Parser<&'a str, O = &'a str> + Clone {
102    str::take_while(|c, _| c.is_ascii_whitespace())
103}
104
105/// Lex.
106fn tokens<'a>() -> impl Parser<&'a str, O = Vec<Token>> + Clone {
107    space().ignore_then(token().then_ignore(space()).repeated())
108}
109
110// We are now done with the lexer.
111// Next up: the parser.
112
113/// Expression.
114#[derive(Debug)]
115enum Expr {
116    /// Number
117    Num(usize),
118    /// Negation
119    Neg(Box<Expr>),
120    /// Combination of two expressions with a binary operator
121    Comb(Box<Expr>, Op, Box<Expr>),
122}
123
124impl Expr {
125    /// Evaluate an expression.
126    fn eval(&self) -> isize {
127        match self {
128            Self::Num(n) => (*n).try_into().unwrap(),
129            Self::Neg(e) => -e.eval(),
130            Self::Comb(l, op, r) => op.eval(l.eval(), r.eval()),
131        }
132    }
133}
134
135/// Parse an atomic expression.
136///
137/// An atomic expression is a (possibly empty) sequence of negations,
138/// followed by a number or a parenthesised expression.
139///
140/// Where the lexer had `&str` as input type,
141/// the parser has the output of the lexer as input type, namely `&[Token]`.
142/// That means that we use
143/// `parcours::slice` functions here instead of
144/// `parcours::str`   functions.
145fn atomic<'a>() -> impl Parser<&'a [Token], O = Expr> {
146    // succeed if the first element in the slice is the token `tk`
147    let eq = |tk| slice::first_filter(move |t, _| *t == tk);
148    // parentheses
149    let par = lazy!(expr).delimited_by(eq(Token::LPar), eq(Token::RPar));
150    // if the first token is a number, return a number expression, else fail
151    let num = slice::first_filter_map(select!(Token::Num(n) => Expr::Num(*n)));
152    let neg = slice::first_filter(|t, _| *t == Token::Op(Op::Sub));
153    let negs = neg.repeated::<Vec<_>>();
154    negs.then(par.or(num))
155        .map(|(negs, atom)| negs.iter().fold(atom, |acc, _x| Expr::Neg(Box::new(acc))))
156}
157
158/// Parse an expression from a token slice.
159///
160/// An expression is an atomic term followed by
161/// a (possibly empty) sequence of operator-atomic term pairs.
162///
163/// This uses precedence climbing to respect operator precedences.
164fn expr<'a>() -> impl Parser<&'a [Token], O = Expr> {
165    let op = slice::first_filter_map(select!(Token::Op(op) => *op));
166    atomic()
167        .then(op.then(lazy!(atomic)).repeated::<Vec<_>>())
168        // for precedence climbing to work, we have to implement
169        // a few traits for operators and expressions, see below
170        .map(|(head, tail)| prec_climb::climb(head, tail))
171}
More examples
Hide additional examples
examples/lambda.rs (line 153)
147fn term<'a>() -> impl Parser<&'a str, State<'a>, O = Term<'a>> {
148    let vars = ident()
149        .repeated()
150        .delimited_by(token("|"), token("|").or(expected("identifier or |")));
151    let abst = vars.and_then(|vars: Vec<_>| {
152        // we parse a term with the bound variables put into the state
153        with_vars(vars.clone(), lazy!(term)).map(|t| (Term::Abst(vars, Box::new(t))))
154    });
155    let args = atomic().repeated::<Vec<_>>();
156    let appl = atomic().then(args).map(|(head, args)| {
157        if args.is_empty() {
158            head
159        } else {
160            Term::Appl(Box::new(head), args)
161        }
162    });
163    abst.or(appl).then_ignore(space()).or(expected("term"))
164}
examples/json.rs (line 98)
87fn json<'a>() -> impl Parser<&'a str, O = JsonVal<&'a str>> {
88    let str = str().delimited_by(matches("\""), matches("\""));
89
90    let token = |s: &'a str| matches(s).then_ignore(space());
91    let arr = lazy!(json).separated_by(token(","));
92    let arr = arr.delimited_by(token("["), matches("]"));
93    let map = str.clone().then_ignore(token(":")).then(lazy!(json));
94    let map = map.separated_by(token(","));
95    let map = map.delimited_by(token("{"), matches("}"));
96
97    any((
98        arr.map(JsonVal::Arr),
99        map.map(JsonVal::Map),
100        str.map(JsonVal::Str),
101        num().map(JsonVal::Num),
102        matches("true").map(|_| JsonVal::True),
103        matches("false").map(|_| JsonVal::False),
104        matches("null").map(|_| JsonVal::Null),
105    ))
106    .then_ignore(space())
107}
Source

fn map_with<O, F: FnOnce(Self::O, &mut S) -> O>(self, f: F) -> MapWith<Self, F>

Apply a function to the output of the parser as well as the mutable state.

Examples found in repository?
examples/lambda.rs (lines 116-125)
115fn atomic<'a>() -> impl Parser<&'a str, State<'a>, O = Term<'a>> + Clone {
116    let var = ident().map_with(|v, state: &mut State<'a>| {
117        // find the de Bruijn index of the variable
118        let db = state.vars.iter().rev().position(|b| *b == v);
119        // if the variable was not bound, then record this as error, but then continue,
120        // because such errors are not fatal parsing errors
121        Term::Var(db.unwrap_or_else(|| {
122            state.errs.push(Error::UnboundVar(v));
123            0
124        }))
125    });
126    // here, we see error reporting in action:
127    // if a term that was opened with a parenthesis is not closed by a parenthesis,
128    // we store an error message and fail
129    var.or(lazy!(term).delimited_by(token("("), token(")").or(expected("closing parenthesis"))))
130}
Source

fn filter<F: FnOnce(&Self::O) -> bool>(self, f: F) -> Filter<Self, F>

Succeed only if the given function yields true for the parser output.

Examples found in repository?
examples/lambda.rs (line 88)
84fn ident<'a, S>() -> impl Parser<&'a str, S, O = &'a str> + Clone {
85    let pn = |c: &u8, _: &mut S| !c.is_ascii() || c.is_ascii_alphanumeric();
86    let p0 = |c: char| !c.is_ascii_digit();
87    take_while(pn)
88        .filter(move |s| s.chars().next().map(p0).unwrap_or(false))
89        .then_ignore(space())
90}
More examples
Hide additional examples
examples/json.rs (lines 54-57)
36fn num<'a, S>() -> impl Parser<&'a str, S, O = &'a str> + Clone {
37    // are we reading the first character?
38    let mut first = true;
39    // have we encountered no dot so far?
40    let mut no_dot = true;
41    // have we encountered no exponent character ('e' or 'E') so far?
42    let mut no_exp = true;
43    take_while(move |c, _| match c {
44        b'0'..=b'9' => {
45            first = false;
46            true
47        }
48        b'-' if first => core::mem::replace(&mut first, false),
49        b'.' if !first && no_dot && no_exp => core::mem::replace(&mut no_dot, false),
50        b'e' | b'E' if !first && no_exp => core::mem::replace(&mut no_exp, false),
51        _ => false,
52    })
53    // the last character of a number must always be a digit
54    .filter(|s| match s.bytes().last() {
55        Some(c) => c.is_ascii_digit(),
56        _ => false,
57    })
58}
Source

fn filter_map<O, F: FnOnce(Self::O) -> Option<O>>( self, f: F, ) -> FilterMap<Self, F>

If the given function yields Some(y) for the parser output, succeed with y, else fail.

Source

fn then_ignore<P: Parser<I, S>>( self, other: P, ) -> Map<All<(Self, P)>, fn((<Self as Parser<I, S>>::O, <P as Parser<I, S>>::O)) -> Self::O>

Run two parsers in sequence and discard result of second one.

Examples found in repository?
examples/bc.rs (line 107)
106fn tokens<'a>() -> impl Parser<&'a str, O = Vec<Token>> + Clone {
107    space().ignore_then(token().then_ignore(space()).repeated())
108}
More examples
Hide additional examples
examples/lambda.rs (line 89)
84fn ident<'a, S>() -> impl Parser<&'a str, S, O = &'a str> + Clone {
85    let pn = |c: &u8, _: &mut S| !c.is_ascii() || c.is_ascii_alphanumeric();
86    let p0 = |c: char| !c.is_ascii_digit();
87    take_while(pn)
88        .filter(move |s| s.chars().next().map(p0).unwrap_or(false))
89        .then_ignore(space())
90}
91
92/// Parse the given string, potentially followed by whitespace.
93fn token<S>(x: &str) -> impl Parser<&str, S, O = ()> + Clone {
94    matches(x).then_ignore(space())
95}
96
97/// Store the given error `s` if no other error was stored before, then fail.
98///
99/// Here, we use `from_fn` to implement some custom parsing logic
100/// that we cannot express with the normal parser combinators in parcours,
101/// in particular because we access and modify the state here.
102/// Alternatively, we could also implement the `Parser` trait manually,
103/// but this is more verbose than `from_fn`.
104///
105/// We only store an error if no other error was stored before.
106/// This is to prevent cascading errors which might be more confusing than helpful.
107fn expected<'a, O>(s: &'static str) -> impl Parser<&'a str, State<'a>, O = O> + Clone {
108    from_fn(move |input, state: &mut State| {
109        state.expected.get_or_insert((s, input));
110        None
111    })
112}
113
114/// Parse an atomic term, namely either a variable or a term enclosed by parentheses.
115fn atomic<'a>() -> impl Parser<&'a str, State<'a>, O = Term<'a>> + Clone {
116    let var = ident().map_with(|v, state: &mut State<'a>| {
117        // find the de Bruijn index of the variable
118        let db = state.vars.iter().rev().position(|b| *b == v);
119        // if the variable was not bound, then record this as error, but then continue,
120        // because such errors are not fatal parsing errors
121        Term::Var(db.unwrap_or_else(|| {
122            state.errs.push(Error::UnboundVar(v));
123            0
124        }))
125    });
126    // here, we see error reporting in action:
127    // if a term that was opened with a parenthesis is not closed by a parenthesis,
128    // we store an error message and fail
129    var.or(lazy!(term).delimited_by(token("("), token(")").or(expected("closing parenthesis"))))
130}
131
132/// Extend the state with variables, parse with `p`, then remove the variables again.
133fn with_vars<'a, I, P>(vars: Vec<&'a str>, p: P) -> impl Parser<I, State<'a>, O = P::O>
134where
135    P: Parser<I, State<'a>>,
136{
137    from_fn(|input, state: &mut State<'a>| {
138        let vars_len = vars.len();
139        state.vars.extend(vars);
140        let y = p.parse(input, state);
141        state.vars.truncate(state.vars.len() - vars_len);
142        y
143    })
144}
145
146/// Parse a term.
147fn term<'a>() -> impl Parser<&'a str, State<'a>, O = Term<'a>> {
148    let vars = ident()
149        .repeated()
150        .delimited_by(token("|"), token("|").or(expected("identifier or |")));
151    let abst = vars.and_then(|vars: Vec<_>| {
152        // we parse a term with the bound variables put into the state
153        with_vars(vars.clone(), lazy!(term)).map(|t| (Term::Abst(vars, Box::new(t))))
154    });
155    let args = atomic().repeated::<Vec<_>>();
156    let appl = atomic().then(args).map(|(head, args)| {
157        if args.is_empty() {
158            head
159        } else {
160            Term::Appl(Box::new(head), args)
161        }
162    });
163    abst.or(appl).then_ignore(space()).or(expected("term"))
164}
examples/json.rs (line 90)
87fn json<'a>() -> impl Parser<&'a str, O = JsonVal<&'a str>> {
88    let str = str().delimited_by(matches("\""), matches("\""));
89
90    let token = |s: &'a str| matches(s).then_ignore(space());
91    let arr = lazy!(json).separated_by(token(","));
92    let arr = arr.delimited_by(token("["), matches("]"));
93    let map = str.clone().then_ignore(token(":")).then(lazy!(json));
94    let map = map.separated_by(token(","));
95    let map = map.delimited_by(token("{"), matches("}"));
96
97    any((
98        arr.map(JsonVal::Arr),
99        map.map(JsonVal::Map),
100        str.map(JsonVal::Str),
101        num().map(JsonVal::Num),
102        matches("true").map(|_| JsonVal::True),
103        matches("false").map(|_| JsonVal::False),
104        matches("null").map(|_| JsonVal::Null),
105    ))
106    .then_ignore(space())
107}
Source

fn ignore_then<P: Parser<I, S>>( self, other: P, ) -> Map<All<(Self, P)>, fn((<Self as Parser<I, S>>::O, <P as Parser<I, S>>::O)) -> P::O>

Run two parsers in sequence and discard result of first one.

Examples found in repository?
examples/bc.rs (line 107)
106fn tokens<'a>() -> impl Parser<&'a str, O = Vec<Token>> + Clone {
107    space().ignore_then(token().then_ignore(space()).repeated())
108}
More examples
Hide additional examples
examples/json.rs (line 141)
123fn main() -> std::io::Result<()> {
124    /*
125    let bla = "y̆es";
126    let input = r#"[[1,true  ,   "bla" , 1  , []  ]] []2"#;
127    */
128
129    // read from file if one is provided as argument, else from standard input
130    let mut args = std::env::args();
131    args.next();
132    let input = match args.next() {
133        Some(arg) => std::fs::read_to_string(arg)?,
134        None => std::io::read_to_string(std::io::stdin())?,
135    };
136
137    //let input = many(r#"{"key": 12345}"#, 10_000_000);
138    //println!("{}", input.len());
139
140    // we first have to strip away any space, because that's what the parser expects
141    let out = space().ignore_then(json()).parse(&input, &mut ());
142    println!("Parsed JSON: {:?}", out);
143    Ok(())
144}
Source

fn delimited_by<L, R>( self, l: L, r: R, ) -> Map<All<(L, Self, R)>, fn((L::O, Self::O, R::O)) -> Self::O>
where L: Parser<I, S>, R: Parser<I, S>,

Run parsers l, self, and r in sequence and return only the output of self.

Examples found in repository?
examples/bc.rs (line 149)
145fn atomic<'a>() -> impl Parser<&'a [Token], O = Expr> {
146    // succeed if the first element in the slice is the token `tk`
147    let eq = |tk| slice::first_filter(move |t, _| *t == tk);
148    // parentheses
149    let par = lazy!(expr).delimited_by(eq(Token::LPar), eq(Token::RPar));
150    // if the first token is a number, return a number expression, else fail
151    let num = slice::first_filter_map(select!(Token::Num(n) => Expr::Num(*n)));
152    let neg = slice::first_filter(|t, _| *t == Token::Op(Op::Sub));
153    let negs = neg.repeated::<Vec<_>>();
154    negs.then(par.or(num))
155        .map(|(negs, atom)| negs.iter().fold(atom, |acc, _x| Expr::Neg(Box::new(acc))))
156}
More examples
Hide additional examples
examples/json.rs (line 88)
87fn json<'a>() -> impl Parser<&'a str, O = JsonVal<&'a str>> {
88    let str = str().delimited_by(matches("\""), matches("\""));
89
90    let token = |s: &'a str| matches(s).then_ignore(space());
91    let arr = lazy!(json).separated_by(token(","));
92    let arr = arr.delimited_by(token("["), matches("]"));
93    let map = str.clone().then_ignore(token(":")).then(lazy!(json));
94    let map = map.separated_by(token(","));
95    let map = map.delimited_by(token("{"), matches("}"));
96
97    any((
98        arr.map(JsonVal::Arr),
99        map.map(JsonVal::Map),
100        str.map(JsonVal::Str),
101        num().map(JsonVal::Num),
102        matches("true").map(|_| JsonVal::True),
103        matches("false").map(|_| JsonVal::False),
104        matches("null").map(|_| JsonVal::Null),
105    ))
106    .then_ignore(space())
107}
examples/lambda.rs (line 129)
115fn atomic<'a>() -> impl Parser<&'a str, State<'a>, O = Term<'a>> + Clone {
116    let var = ident().map_with(|v, state: &mut State<'a>| {
117        // find the de Bruijn index of the variable
118        let db = state.vars.iter().rev().position(|b| *b == v);
119        // if the variable was not bound, then record this as error, but then continue,
120        // because such errors are not fatal parsing errors
121        Term::Var(db.unwrap_or_else(|| {
122            state.errs.push(Error::UnboundVar(v));
123            0
124        }))
125    });
126    // here, we see error reporting in action:
127    // if a term that was opened with a parenthesis is not closed by a parenthesis,
128    // we store an error message and fail
129    var.or(lazy!(term).delimited_by(token("("), token(")").or(expected("closing parenthesis"))))
130}
131
132/// Extend the state with variables, parse with `p`, then remove the variables again.
133fn with_vars<'a, I, P>(vars: Vec<&'a str>, p: P) -> impl Parser<I, State<'a>, O = P::O>
134where
135    P: Parser<I, State<'a>>,
136{
137    from_fn(|input, state: &mut State<'a>| {
138        let vars_len = vars.len();
139        state.vars.extend(vars);
140        let y = p.parse(input, state);
141        state.vars.truncate(state.vars.len() - vars_len);
142        y
143    })
144}
145
146/// Parse a term.
147fn term<'a>() -> impl Parser<&'a str, State<'a>, O = Term<'a>> {
148    let vars = ident()
149        .repeated()
150        .delimited_by(token("|"), token("|").or(expected("identifier or |")));
151    let abst = vars.and_then(|vars: Vec<_>| {
152        // we parse a term with the bound variables put into the state
153        with_vars(vars.clone(), lazy!(term)).map(|t| (Term::Abst(vars, Box::new(t))))
154    });
155    let args = atomic().repeated::<Vec<_>>();
156    let appl = atomic().then(args).map(|(head, args)| {
157        if args.is_empty() {
158            head
159        } else {
160            Term::Appl(Box::new(head), args)
161        }
162    });
163    abst.or(appl).then_ignore(space()).or(expected("term"))
164}
Source

fn repeated<O>(self) -> Repeated<Self, fn() -> O>
where I: Clone, Self: Clone, O: Default + Extend<Self::O>,

Apply the given parser as often as possible.

This collect the outputs of the parser into the type O. If you do not want to allocate, you can use () as O.

Examples found in repository?
examples/bc.rs (line 107)
106fn tokens<'a>() -> impl Parser<&'a str, O = Vec<Token>> + Clone {
107    space().ignore_then(token().then_ignore(space()).repeated())
108}
109
110// We are now done with the lexer.
111// Next up: the parser.
112
113/// Expression.
114#[derive(Debug)]
115enum Expr {
116    /// Number
117    Num(usize),
118    /// Negation
119    Neg(Box<Expr>),
120    /// Combination of two expressions with a binary operator
121    Comb(Box<Expr>, Op, Box<Expr>),
122}
123
124impl Expr {
125    /// Evaluate an expression.
126    fn eval(&self) -> isize {
127        match self {
128            Self::Num(n) => (*n).try_into().unwrap(),
129            Self::Neg(e) => -e.eval(),
130            Self::Comb(l, op, r) => op.eval(l.eval(), r.eval()),
131        }
132    }
133}
134
135/// Parse an atomic expression.
136///
137/// An atomic expression is a (possibly empty) sequence of negations,
138/// followed by a number or a parenthesised expression.
139///
140/// Where the lexer had `&str` as input type,
141/// the parser has the output of the lexer as input type, namely `&[Token]`.
142/// That means that we use
143/// `parcours::slice` functions here instead of
144/// `parcours::str`   functions.
145fn atomic<'a>() -> impl Parser<&'a [Token], O = Expr> {
146    // succeed if the first element in the slice is the token `tk`
147    let eq = |tk| slice::first_filter(move |t, _| *t == tk);
148    // parentheses
149    let par = lazy!(expr).delimited_by(eq(Token::LPar), eq(Token::RPar));
150    // if the first token is a number, return a number expression, else fail
151    let num = slice::first_filter_map(select!(Token::Num(n) => Expr::Num(*n)));
152    let neg = slice::first_filter(|t, _| *t == Token::Op(Op::Sub));
153    let negs = neg.repeated::<Vec<_>>();
154    negs.then(par.or(num))
155        .map(|(negs, atom)| negs.iter().fold(atom, |acc, _x| Expr::Neg(Box::new(acc))))
156}
157
158/// Parse an expression from a token slice.
159///
160/// An expression is an atomic term followed by
161/// a (possibly empty) sequence of operator-atomic term pairs.
162///
163/// This uses precedence climbing to respect operator precedences.
164fn expr<'a>() -> impl Parser<&'a [Token], O = Expr> {
165    let op = slice::first_filter_map(select!(Token::Op(op) => *op));
166    atomic()
167        .then(op.then(lazy!(atomic)).repeated::<Vec<_>>())
168        // for precedence climbing to work, we have to implement
169        // a few traits for operators and expressions, see below
170        .map(|(head, tail)| prec_climb::climb(head, tail))
171}
More examples
Hide additional examples
examples/lambda.rs (line 149)
147fn term<'a>() -> impl Parser<&'a str, State<'a>, O = Term<'a>> {
148    let vars = ident()
149        .repeated()
150        .delimited_by(token("|"), token("|").or(expected("identifier or |")));
151    let abst = vars.and_then(|vars: Vec<_>| {
152        // we parse a term with the bound variables put into the state
153        with_vars(vars.clone(), lazy!(term)).map(|t| (Term::Abst(vars, Box::new(t))))
154    });
155    let args = atomic().repeated::<Vec<_>>();
156    let appl = atomic().then(args).map(|(head, args)| {
157        if args.is_empty() {
158            head
159        } else {
160            Term::Appl(Box::new(head), args)
161        }
162    });
163    abst.or(appl).then_ignore(space()).or(expected("term"))
164}
Source

fn separated_by<Sep, O>(self, sep: Sep) -> SeparatedBy<Self, Sep, fn() -> O>
where I: Clone, Self: Clone, Sep: Parser<I, S> + Clone, O: Default + Extend<Self::O>,

Apply the given parser as often as possible, separated by sep.

a.separated_by(b) corresponds to the regular expression (a(ba)*)?. The output of this parser is the collection of the outputs of a; that is, the outputs of b are discarded. Trailing bs are not consumed; for this, use a.separated_by(b).then_ignore(b.opt()).

To keep the outputs of b and demand at least one match of a, you may use a.then(b.then(a).repeated()) instead.

Examples found in repository?
examples/json.rs (line 91)
87fn json<'a>() -> impl Parser<&'a str, O = JsonVal<&'a str>> {
88    let str = str().delimited_by(matches("\""), matches("\""));
89
90    let token = |s: &'a str| matches(s).then_ignore(space());
91    let arr = lazy!(json).separated_by(token(","));
92    let arr = arr.delimited_by(token("["), matches("]"));
93    let map = str.clone().then_ignore(token(":")).then(lazy!(json));
94    let map = map.separated_by(token(","));
95    let map = map.delimited_by(token("{"), matches("}"));
96
97    any((
98        arr.map(JsonVal::Arr),
99        map.map(JsonVal::Map),
100        str.map(JsonVal::Str),
101        num().map(JsonVal::Num),
102        matches("true").map(|_| JsonVal::True),
103        matches("false").map(|_| JsonVal::False),
104        matches("null").map(|_| JsonVal::Null),
105    ))
106    .then_ignore(space())
107}
Source

fn opt(self) -> Opt<Self>
where I: Clone,

If the given parser succeeds, wrap its output in Some, else return None.

The resulting parser always succeeds.

Source

fn chain<P>( self, other: P, ) -> Map<All<(Self, P)>, fn((<Self as Parser<I, S>>::O, <P as Parser<I, S>>::O)) -> Chain<<Self::O as IntoIterator>::IntoIter, <P::O as IntoIterator>::IntoIter>>
where P: Parser<I, S>, Self::O: IntoIterator, P::O: IntoIterator<Item = <Self::O as IntoIterator>::Item>,

Convert the outputs of the given parsers to iterators and concatenate them.

use parcours::{Parser, Combinator, str::take_while1};
let digit = take_while1(|c, _| c.is_ascii_digit());
let alpha = take_while1(|c, _| c.is_ascii_alphabetic());
let both = digit.opt().chain(alpha.opt()).map(|i| i.collect());
assert_eq!(both.parse("123abc", &mut ()), Some((vec!["123", "abc"], "")))
Source

fn and_then<P: Parser<I, S>, F: FnOnce(Self::O) -> P>( self, f: F, ) -> AndThen<Self, F>

Run the first parser, then create a second parser from its output and run it.

Examples found in repository?
examples/lambda.rs (lines 151-154)
147fn term<'a>() -> impl Parser<&'a str, State<'a>, O = Term<'a>> {
148    let vars = ident()
149        .repeated()
150        .delimited_by(token("|"), token("|").or(expected("identifier or |")));
151    let abst = vars.and_then(|vars: Vec<_>| {
152        // we parse a term with the bound variables put into the state
153        with_vars(vars.clone(), lazy!(term)).map(|t| (Term::Abst(vars, Box::new(t))))
154    });
155    let args = atomic().repeated::<Vec<_>>();
156    let appl = atomic().then(args).map(|(head, args)| {
157        if args.is_empty() {
158            head
159        } else {
160            Term::Appl(Box::new(head), args)
161        }
162    });
163    abst.or(appl).then_ignore(space()).or(expected("term"))
164}

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors§

Source§

impl<I, S, T: Parser<I, S>> Combinator<I, S> for T