osa1 / lexgen

A fully-featured lexer generator, implemented as a proc macro
MIT License
63 stars 7 forks source link

Implement backtracking #21

Closed osa1 closed 2 years ago

osa1 commented 2 years ago

This commit implements backtracking to the previous accepting state in lexers like the following:

lexer! {
    Lexer -> &'input str;

    'a'+ 'b' => return_match,
    'a' => return_match,
}

When input is "aaaa", we skip the accepting state for the second rule as we potentially have a longer match. However when we reach end of the input, we need to backtrack in input, and accept "a".

To implement this we add one more state to lexers, for the last match. When lexing fails, we run semantic action of the last match, if it exists. Otherwise we fail as before.

NFA and DFA simulations also updated to implement this behavior.

Other changes:

Fixes #16