"a|a*b" should match "aa" but it doesn't

[zeng-y-l]

Example:

use logos::Logos;

#[derive(Debug, PartialEq, Logos)]
enum Tok {
    #[regex("a|a*b")]
    T,
}

fn main() {
    let lex = Tok::lexer("aa");
    assert_eq!(lex.collect::<Vec<_>>(), [Ok(Tok::T), Ok(Tok::T)]); // [Err(())]
}

Maybe it's related to #160. Is this a bug? Thank you so much!

[jeertmans]

Hi @zeng-y-l, I didn’t verify but I think you need to quote your patterns around the or operator; otherwise you current pattern needs to match a « b » at the end.

[zeng-y-l]

I want it to match a or a*b. I have tried a|(a*b), and the result is the same.

[zeng-y-l]

Graph:

{
    1: ::T,
    3: b ⇒ 1,
    4: [
        a ⇒ 4,
        _ ⇒ 3,
    ],
    5: {
        a ⇒ 4,
        b ⇒ 1,
        _ ⇒ 1,
    },
    8: {
        a ⇒ 5,
        b ⇒ 1,
    },
}

[minirop]

Seems to be an issue with the * operator, because something like #[regex("a|ab|aab|aaab|aaaab")] works fine yet #[regex("a|aaa*b")] doesn't.

[maciejhirsz]

This is 99% an issue with backtracking, once the lexer sees the second a it will attempt to match the loop and if it doesn't find b it errors instead of falling back to last potentially correct match.

[jeertmans]

Thanks for the update, I didn't see the notification!

I will create a new label (that we should also add to older similar issues) to track issues related to backtracking.