Repository: lalrpop/lalrpop (language: rust)

Issue:
lalrpop + logos | returning Err instead of pushing to ErrorRecovery
We are experiencing a similar issue to #992 and https://stackoverflow.com/questions/77999387/lalrpop-doesnt-recover-after-finding-an-invalid-token-even-though-i-should-have
Our code is here:
https://github.com/osta-lang/osta-rs/commit/1cb7beff638db2ddc72374a87f85d884122cbfea
The issue can be replicated from `calculator7` replacing the grammar by:
```rs
use std::str::FromStr;
use crate::ast::{Expr, Opcode};
use lalrpop_util::ErrorRecovery;

grammar<'err>(errors: &'err mut Vec<ErrorRecovery<usize, Token<'input>, &'static str>>);

pub Exprs: Vec<Box<Expr>> = {
    (<Term>)+,
}

Term: Box<Expr> = {
    Num => Box::new(Expr::Number(<>)),
    ! => { errors.push(<>); Box::new(Expr::Error) },
};

Num: i32 = {
    r"[0-9]+" => i32::from_str(<>).unwrap()
};
```
In the `22 * + 3` example I expect to get `22 error error 3`, but instead I get
```
called `Result::unwrap()` on an `Err` value: InvalidToken { location: 3 }
```


Discussion / hints:
Fixed adding TokenKind::Error variant in enum redeclaration in extern block.
```diff
  extern {
      type Location = usize;
      type Error = LexicalError;
  
      enum TokenKind {
+         "error" => TokenKind::Error(_),
```
Consider making a clarification in the [Error recovery with custom lexer](https://lalrpop.github.io/lalrpop/lexer_tutorial/006_error_recovery_custom_lexer.html) chapter of the book.

On the other hand, I think the parser should be able to recover from an `UnrecognizedToken` error.

I will leave the issue open if you want to discuss this last point. If you don't think it's necessary you can close it.
> On the other hand, I think the parser should be able to recover from an `UnrecognizedToken` error.

@dburgener explained the root cause in #992. And `UnrecognizedToken` actually refers to the error generated when parser encounters a token it did not expect, which has nothing to do with those undefined tokens. It's indeed ambiguous here.

See https://docs.rs/lalrpop-util/latest/lalrpop_util/enum.ParseError.html#variant.UnrecognizedToken
The code example above does not represent well the problem we were encountering. It is better illustrated in this commit: https://github.com/osta-lang/osta-rs/commit/1cb7beff638db2ddc72374a87f85d884122cbfea.
From what I understand from the book chapter [Error recovery with custom lexer](https://lalrpop.github.io/lalrpop/lexer_tutorial/006_error_recovery_custom_lexer.html), when the Lexer encounters something it cannot tokenize it issues an `Ok(TokenKind::Error)` instead of issuing the `Err(LexicalError)`. Then the parser tries to use this `TokenKind::Error`, which fails to find production rules that use the token (or because it is not defined in the `extern > enum` block, I don't know the exact cause). My intuition tells me that if an expression is defined as `<expr> “+” <term>` with error recovery, when it encounters a token it doesn't recognize it should run the error recovery routine instead of throwing the `UnrecognizedToken` error.
If there is something I did not understood I appreciate an explanation.

Another thing to mention is that it was fixed by putting `“error” => TokenKind::Error` in the `extern > enum` block, and this is not mentioned in the book chapter. Making a mention of the problem and this possible solution might be a good idea, or making some kind of clarification to prevent others from running into the same problem.
Yeah you have a good point and I am sorry for that vagueness. I was thinking that the users might've known the chore (eg adding `TokenKind::Error` into `extern`) because they already reach the advanced sections.

I will fix that soon as I just got back from the Spring Festival.
Thanks, @chanbengz.  A documentation update PR will be very welcome.

I'm still trying to understand the overall problem here.  There are two different possible errors: `InvalidToken`, and `UnrecognizedToken`.  `InvalidToken` is not recoverable, because it is a lexer error.  `UnrecognizedToken` is a parser error, and I think should be recoverable.  A lot of the discussion here mentions `UnrecognizedToken`, but the initial code snippet in the first post mentions `InvalidToken` in the error message.  Is the issue here actually, about `InvalidToken` or `UnrecognizedToken`?  If it's `UnrecognizedToken`, can you provide a reproducer?  I'm not really sure what to do with the linked commit, since I'm not clear what problem it is describing or how to trigger it.
I'm talking about `UnrecognizedToken`. In the referenced commit, I have a grammar which defines simple `expr`. The lexer instead of emitting `Err(LexicalError)` emits `Ok(Token::KindError)`. The point is that if you don't add `"error" => TokenKind::Error` in the `extern > enum` block it throws an `UnrecognizedToken` error when it encounters a `TokenKind::Error` instead of using the error recovery routine. If you add `"error" => TokenKind::Error` then the error recovery routine is called as expected. I think that the expected behavior is that even if that line is not there the error recovery procedure should be called.
Gotcha. As you see, logos is an external lexer to LALRPOP. The parser generator won't know what kinds of token it have unless you explicitly tell it via the `extern` block. And if you have some knowledge about table-driven parsing (LALRPOP is LR(1)), we can guess that without knowing the input tokens (`TokenKind::Error` as example here), the generator cannot derive a column for `TokenKind::Error` in ACTION function table. So you'll have to exhaust the externally-defined token in `extern`.

In LALRPOP's implementation, it'll first assign each token in `extern` a digit as index number for ACTION function. When state machine asks for the next token, it receives None if input token is not mapped and immediately returns Err which terminates the parsing.

I probably know how to fix it and it can also fix my previous issue. But I think it's not really a flaw and it's fully discussable (relevant code located at [lalrpop-util](https://github.com/lalrpop/lalrpop/blob/master/lalrpop-util/src/state_machine.rs#L623)):
1. when facing a lexer error, terminate or enter error recovery routine?
2. when inputing a token that defined externally but undefined in `extern`, terminate or enter error recovery routine?

Fix patch:
diff --git a/doc/src/lexer_tutorial/006_error_recovery_custom_lexer.md b/doc/src/lexer_tutorial/006_error_recovery_custom_lexer.md
index 0e0b7bb92..f248e1219 100644
--- a/doc/src/lexer_tutorial/006_error_recovery_custom_lexer.md
+++ b/doc/src/lexer_tutorial/006_error_recovery_custom_lexer.md
@@ -52,7 +52,7 @@ impl<'input> Iterator for Lexer<'input> {
 and then put a new member into `Token` enum to represent the error token
 (or your custom error type).
 
-```rust
+```diff
 pub enum Token {
     //...
 
@@ -61,6 +61,17 @@ pub enum Token {
 }
 ```
 
+Also update the extern block in `grammar.lalrpop`.
+
+```diff
+extern {
+      type Location = usize;
+      type Error = LexicalError;
+
+      enum Token {
++         "error" => Token::Error,
+```
+
 Like NaN is a number in JavaScript, we have now an `Token::Error` which is
 a token in our lexer.  This token can be passed to the parser, but if it is
 not used in the parser grammar, will not parse.  That transforms the lexer


Test patch: