Small parser, weird failure, faulty understanding?

[dovreshef]

I've tried to write a simple parser using the library to get a feel for it. The parser can parse expressions such as "1 = 1" or "2=2" but not "1=3". Also, the expression can be and'ed or or'ed together, and grouped.

The (whole) code is as follows:

use chumsky::{prelude::*, text::digits};

pub type Span = std::ops::Range<usize>;
pub type Spanned<T> = (T, Span);

fn parser() -> impl Parser<char, Spanned<String>, Error = Simple<char>> {
    let single_clause = digits(10)
        .then(just('=').padded())
        .then(digits(10))
        .try_map(|((lhs, _), rhs), span| match lhs == rhs {
            true => Ok(format!("{lhs} == {rhs}")),
            false => Err(Simple::custom(span, format!("{lhs} != {rhs}"))),
        });

    recursive(|nested| {
        let inner_expr = single_clause.or(nested.delimited_by(just('('), just(')')));

        let and_case = inner_expr
            .clone()
            .separated_by(just("or").padded())
            .map(|v| v.join(" OR "));

        let or_case = inner_expr
            .clone()
            .separated_by(just("and").padded())
            .map(|v| v.join(" AND "));

        inner_expr.or(or_case).or(and_case)
    })
    .map_with_span(|tok, span| (tok, span))
    .then_ignore(end())
}

fn main() {
    dbg!(parser().parse("1 = 1 or 2 = 2"));
}

The output is:

[src/main.rs:35] parser().parse("1 = 1 or 2 = 2") = Err(
    [
        Simple {
            span: 5..6,
            reason: Unexpected,
            expected: {
                None,
            },
            found: Some(
                ' ',
            ),
            label: None,
        },
    ],
)

If I understand the issue correctly, the parser terminates parsing after inner_expr fails, and does not continue to the other two cases .or(or_case).or(and_case). But I don't understand why, since these piece parsers are or'ed together.

What am I missing?

Thanks

[Zij-IT]

You are close, but are missing a key point of or parsers. In an or chain, the first parser that is able to successfully parse some of the input will "win" the chain, and stop the chain from parsing further. This means that because your inner_expr is written first, it will successfully parse the "1 = 1" and what remains of the input is " or 2 = 2". Parsing fails here, because there is no repeat, and even if there was, nothing could parse the remaining input successfully.

A simplified example of this problem is:

let result = just("fun").or(just("function")).then_ignore(end()).parse("function");
assert!(result.is_err());

This will error because just("fun") will successfully eat the first three letters, leaving "ction" unparsed. Chumsky will not attempt to backtrack to find the correct parser, once in the end parser, because a parser could be arbitrarily complex. In this case, the solution would be to swap the order of the two parsers. and if you give that a shot with your parser, you will notice that it will fail one of the two tests:

assert!(parser.parse("1 = 1 or 2 = 2").is_ok());
assert!(parser.parse("1 = 1 and 2 = 2").is_ok());

This is because whichever parser you chose to have parse the input first, will successfully parse the start, but then not be able to parse either " or 2 = 2" or " and 2 = 2.

What I assume you're after, is being able to chain and and or operations. This can get more complex with precedence, but assuming your grammar does not have it, you can do something like:

// This replaces lines 18-28 or your parser
inner_expr
    .clone()
    .then(
        choice((
            just("or")
                .padded()
                .ignore_then(nested.clone())
                .map(|n| format!("OR {n}")),
            just("and")
                .padded()
                .ignore_then(nested.clone())
                .map(|n| format!("AND {n}")),
        ))
        .repeated()
        .collect::<String>(),
    )
    .map(|(lhs, rhs)| format!("{lhs}{rhs}"))

This does a couple things different. At first it will accept any inner_expr and then it will try to parse any amount of or <inner_expr> and and <inner_expr>. Once it has, it collects all of the extras into a String and joins that string with the original inner_expr.

[dovreshef]

Thanks. I did not understand this at all about or.

[Zij-IT]

Not a problem! I have used the library a fair bit, and actually wrote the current pratt parser that is on the main branch (hopefully in 1.0.0.5-alpha), which should simplify problems like this. Your parser would actually look like what's below, and adding precedence would be as simple as changing the 1 by and to a 2.

recursive(|nested| {
    let inner_expr = single_clause.or(nested.delimited_by(just('('), just(')')));
    inner_expr.pratt(choice((
        left_infix(just("or").padded(), 1, |lhs, rhs| format!("{lhs} OR {rhs}")),
        left_infix(just("and").padded(), 1, |lhs, rhs| {
            format!("{lhs} AND {rhs}")
        }),
    )))
})
.map_with_span(|tok, span| (tok, span))
.then_ignore(end())