lexigram_core/parser/

mod.rs

// Copyright (c) 2025 Redglyph (@gmail.com). All Rights Reserved.

use std::fmt::{Display, Formatter};
use crate::fixed_sym_table::{FixedSymTable, SymInfoTable};
use crate::{AltId, TokenId, VarId};
use crate::lexer::{Pos, PosSpan};
use crate::log::{LogMsg, Logger};
use crate::alt::Alternative;

pub(crate) mod tests;

// ---------------------------------------------------------------------------------------------

#[derive(Clone, Copy, Default, PartialEq, PartialOrd, Eq, Ord, Debug, Hash)]
pub enum Symbol {
    T(TokenId),         // terminal
    NT(VarId),          // non-terminal
    #[default] Empty,   // empty symbol
    End                 // end of stream
}

impl Symbol {
    pub fn is_end(&self) -> bool {
        matches!(self, Symbol::End)
    }

    pub fn is_empty(&self) -> bool {
        matches!(self, Symbol::Empty)
    }

    pub fn is_t(&self) -> bool {
        matches!(self, Symbol::T(_))
    }

    pub fn is_nt(&self) -> bool {
        matches!(self, Symbol::NT(_))
    }

    pub fn is_t_or_nt(&self) -> bool {
        matches!(self, Symbol::T(_) | Symbol::NT(_))
    }

    pub fn to_str<T: SymInfoTable>(&self, symbol_table: Option<&T>) -> String {
        symbol_table.map(|t| t.get_str(self)).unwrap_or_else(|| self.to_string())
    }

    /// Converts the symbol to string, using the symbol table if available, and
    /// surrounding it with quotes if it's a string literal.
    pub fn to_str_quote<T: SymInfoTable>(&self, symbol_table: Option<&T>) -> String {
        symbol_table.map(|t| t.get_name_quote(self)).unwrap_or_else(|| self.to_string())
    }

    pub fn to_str_name<T: SymInfoTable>(&self, symbol_table: Option<&T>) -> String {
        symbol_table.map(|t| t.get_name(self)).unwrap_or_else(|| self.to_string())
    }

    /// Converts the symbol to string, using the symbol table if available.
    pub fn to_str_ext<T: SymInfoTable>(&self, symbol_table: Option<&T>, ext: &String) -> String {
        let mut result = self.to_str(symbol_table);
        if let Some(t) = symbol_table {
            if t.is_symbol_t_data(self) {
                result.push_str(&format!("({ext})"));
            }
        }
        result
    }

    /// Converts to symbols used in `sym!` and other related macros of the `lexigram` crate.
    pub fn to_macro_item(&self) -> String {
        match self {
            Symbol::Empty => "e".to_string(),
            Symbol::T(x) => format!("t {x}"),
            Symbol::NT(x) => format!("nt {x}"),
            Symbol::End => "end".to_string(),
        }
    }
}

impl Display for Symbol {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        match self {
            Symbol::Empty => write!(f, "ε"),
            Symbol::T(id) => write!(f, ":{id}"),
            Symbol::NT(id) => write!(f, "{id}"),
            Symbol::End => write!(f, "$"),
        }
    }
}

#[derive(Clone, Copy, PartialEq, Debug)]
pub enum OpCode {
    Empty,              // empty symbol
    T(TokenId),         // terminal
    NT(VarId),          // nonterminal
    Loop(VarId),        // loop to same nonterminal
    Exit(VarId),        // exit nonterminal
    Hook,               // terminal hook callback
    End,                // end of stream
}


impl Display for OpCode {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        match self {
            OpCode::Empty => write!(f, "ε"),
            OpCode::T(t) => write!(f, ":{t}"),
            OpCode::NT(v) => write!(f, "►{v}"),
            OpCode::Loop(v) => write!(f, "●{v}"),
            OpCode::Exit(v) => write!(f, "◄{v}"),
            OpCode::Hook => write!(f, "▲"),
            OpCode::End => write!(f, "$"),
        }
    }
}

impl OpCode {
    pub fn is_loop(&self) -> bool {
        matches!(self, OpCode::Loop(_))
    }

    pub fn is_empty(&self) -> bool {
        matches!(self, OpCode::Empty)
    }

    pub fn has_span(&self) -> bool {
        matches!(self, OpCode::T(_) | OpCode::NT(_))
    }

    pub fn matches(&self, s: Symbol) -> bool {
        match self {
            OpCode::Empty => s == Symbol::Empty,
            OpCode::T(t) => s == Symbol::T(*t),
            OpCode::NT(v) => s == Symbol::NT(*v),
            OpCode::End => s == Symbol::End,
            OpCode::Loop(_)
            | OpCode::Exit(_)
            | OpCode::Hook => false,
        }
    }

    pub fn to_str<T: SymInfoTable>(&self, symbol_table: Option<&T>) -> String {
        if let Some(t) = symbol_table {
            match self {
                OpCode::Empty => "ε".to_string(),
                OpCode::T(v) => format!("{}{}", t.get_t_str(*v), if t.is_token_data(*v) { "!" } else { "" }),
                OpCode::NT(v) => format!("►{}", t.get_nt_name(*v)),
                OpCode::Loop(v) => format!("●{}", t.get_nt_name(*v)),
                OpCode::Exit(f) => format!("◄{f}"),
                OpCode::Hook => "▲".to_string(),
                OpCode::End => "$".to_string(),
            }
        } else {
            self.to_string()
        }
    }

    pub fn to_str_name<T: SymInfoTable>(&self, symbol_table: Option<&T>) -> String {
        if let Some(tbl) = symbol_table {
            match self {
                OpCode::T(v) => tbl.get_t_str(*v),
                _ => self.to_str(symbol_table),
            }
        } else {
            self.to_string()
        }
    }

    pub fn to_str_quote<T: SymInfoTable>(&self, symbol_table: Option<&T>) -> String {
        if let Some(t) = symbol_table {
            match self {
                OpCode::T(v) => format!("{}{}", Symbol::T(*v).to_str_quote(symbol_table), if t.is_token_data(*v) { "!" } else { "" }),
                _ => self.to_str(symbol_table)
            }
        } else {
            self.to_string()
        }
    }

    pub fn to_str_ext<T: SymInfoTable>(&self, symbol_table: Option<&T>, ext: &String) -> String {
        let mut result = self.to_str(symbol_table);
        if let Some(t) = symbol_table {
            if let OpCode::T(tok) = self {
                if t.is_symbol_t_data(&Symbol::T(*tok)) {
                    result.push_str(&format!("({ext})"));
                }
            }
        }
        result
    }
}

impl From<Symbol> for OpCode {
    fn from(value: Symbol) -> Self {
        match value {
            Symbol::Empty => OpCode::Empty,
            Symbol::T(t) => OpCode::T(t),
            Symbol::NT(v) => OpCode::NT(v),
            Symbol::End => OpCode::End,
        }
    }
}

#[cfg(feature = "test_utils")]
impl OpCode {
    pub fn to_macro_item(&self) -> String {
        match self {
            OpCode::Empty => "e".to_string(),
            OpCode::T(t) => format!("t {t}"),
            OpCode::NT(v) => format!("nt {v}"),
            OpCode::Loop(v) => format!("loop {v}"),
            OpCode::Exit(v) => format!("exit {v}"),
            OpCode::Hook => "hook".to_string(),
            OpCode::End => "end".to_string(),
        }
    }
}

// ---------------------------------------------------------------------------------------------

/// Codes returned by the [check_abort_request(...)](ListenerWrapper::check_abort_request) method of
/// the listener (via the wrapper pass-through).
#[derive(Clone, Copy, PartialEq, Debug)]
pub enum Terminate {
    /// Normal behaviour: continues parsing the text
    None,
    /// Irrecoverable error: stops parsing, calls the listener abort method, and returns an error
    Abort,
    /// Stops parsing, calls the listener exit method, and returns an Ok
    Conclude,
}

/// Action calls to the wrapper with the method [ListenerWrapper::switch]. The wrapper translates the
/// action accordingly to the current nonterminal and alternative; for example, by calling the
/// appropriate listener callback.
#[derive(PartialEq, Debug)]
pub enum Call {
    /// Enters a new nonterminal rule. The alternative is already known, but the values of the symbols
    /// in that alternative haven't been scanned yet.
    ///
    /// This can be used to initialize the listener's variables when a particular rule is about to be
    /// parsed (the listener methods associated with this action are normally optional since no
    /// information is returned to the wrapper).
    ///
    /// The wrapper also uses this call to initialize stack items like accumulators used in rule loops
    /// like `a -> b*`.
    Enter,
    /// Re-enters a loop nonterminal. This is currently not used in the wrapper.
    Loop,
    /// Exits an alternative, once all the symbols in it have been parsed: nonterminals and terminals.
    ///
    /// This is typically used to call an exit method of the listener and evaluate its value when it
    /// has one.
    Exit,
    /// This action is used in two situations:
    /// * when the parsing of the top rule has completed normally. In that case, the wrapper
    ///   calls the [exit(...)] method of the listener (done in the generated code).
    /// * when the parsing is [aborted](Terminate::Abort) or [concluded](Terminate::Conclude) in
    ///   reaction to an [check_abort_request(...)](ListenerWrapper::check_abort_request) call. In
    ///   that case, the wrapper calls the [abort(...)] method of the listener (done in the generated
    ///   code).
    ///
    /// The [Terminate] value it contains tells the wrapper which of those eventualities has
    /// occurred.
    End(Terminate)
}

pub trait ListenerWrapper {
    /// Calls the listener to execute Enter, Loop, Exit, and End actions.
    #[allow(unused_variables)]
    fn switch(&mut self, call: Call, nt: VarId, alt_id: AltId, t_data: Option<Vec<String>>) {}

    /// Checks if the listener requests an abort (wrapper pass-through). This method is called at the end of
    /// each parser iteration. If an error is too difficult to recover from, the listener can set a flag that
    /// tells to return a [Terminate::Abort] on the next call, and implement this method to return
    /// the appropriate status.
    ///
    /// In that case, the parser
    /// * calls [abort(...)](ListenerWrapper::abort)
    /// * calls [switch([Call::End]([Terminate::Abort]))](ListenerWrapper::switch) (if there was no syntax error)
    /// * returns [ParserError::AbortRequest].
    fn check_abort_request(&self) -> Terminate { Terminate::None }

    /// Aborts the parsing.
    fn abort(&mut self) {}

    /// Gets access to the listener's log to report possible errors and information about the parsing.
    fn get_log_mut(&mut self) -> &mut impl Logger;

    /// Reports a message (note, info, warning, or error). The default behaviour adds the message to the log.
    #[allow(unused_variables)]
    fn report(&mut self, span_opt: Option<&PosSpan>, msg: LogMsg) {
        self.get_log_mut().add(msg);
    }

    /// Pushes a location span onto the (optional) span stack
    #[allow(unused_variables)]
    fn push_span(&mut self, span: PosSpan) {}

    /// Checks that the stack is empty (the parser only checks that the stack is empty after successfully parsing a text)
    fn is_stack_empty(&self) -> bool { true }

    /// Checks that the stack_t is empty (the parser only checks that the stack is empty after successfully parsing a text)
    fn is_stack_t_empty(&self) -> bool { true }

    /// Checks that the stack_span is empty (the parser only checks that the stack is empty after successfully parsing a text)
    fn is_stack_span_empty(&self) -> bool { true }

    /// Allows to dynamically translate a token in the listener (wrapper pass-through)
    #[allow(unused_variables)]
    fn hook(&mut self, token: TokenId, text: &str, span: &PosSpan) -> TokenId {
        token
    }

    /// Allows to intercept any token in the listener (wrapper pass-through)
    #[allow(unused_variables)]
    fn intercept_token(&mut self, token: TokenId, text: &str, span: &PosSpan) -> TokenId {
        token
    }
}

// ---------------------------------------------------------------------------------------------

pub type ParserToken = (TokenId, String, PosSpan);

/// Code of the error that occurred during the parsing, returned by the
/// [parse_stream(...)](Parser::parse_stream) method of the parser.
#[derive(PartialEq, Debug)]
pub enum ParserError {
    /// A syntax error was met. Either
    /// * The next terminal of the parsed text doesn't match the expected one in the current rule
    ///   alternative; for example, a rule `assign -> "let" Id "=" expr ";";` has just successfully
    ///   scanned the terminal `"let"`, but the next one isn't `Id`.
    /// * The next symbol doesn't correspond to any correct option for the next nonterminal (
    ///   in other words, there is no entry in the parsing table for that combination). For example,
    ///   in the same rule as above, the terminal `"="` has just been scanned successfully, but `expr`
    ///   doesn't begin with the next one.
    ///
    /// This error is returned only when the parser doesn't try to recover from syntax errors; this
    /// option is set with the [set_try_recover(...)](Parser::set_try_recover) method and is
    /// enabled by default.
    ///
    /// See also [ParserError::TooManyErrors].
    SyntaxError,
    /// Too many syntax errors were met, either
    /// * during the parsing. The limit is set by the constant [Parser::MAX_NBR_RECOVERS].
    /// * by the lexer. The limit is set by the constant [Parser::MAX_NBR_LEXER_ERRORS].
    ///
    /// This error is returned only when the parser tries to recover from syntactic or lexical errors;
    /// this option is set with the [set_try_recover(...)](Parser::set_try_recover) method and is
    /// enabled by default.
    ///
    /// See also [ParserError::SyntaxError].
    TooManyErrors,
    /// The parser has reached an irrecoverable error, after trying to recover from a syntax error and
    /// encountering the end of the text.
    Irrecoverable,
    /// The parser has reached the end of the top rule, but there are still terminals coming from
    /// the lexer.
    ///
    /// Note that if the text is expected to contain something else after the part that must be parsed,
    /// it is possible to tell the parser to conclude the parsing without looking any further. This
    /// can be done in the listener with the [check_abort_request(...)] performed regularly by the
    /// parser. See the [examples/terminate] parser to see how it can be used.
    ExtraSymbol,
    /// The parser has encountered the end of the text, but the top rule hasn't been fully parsed.
    UnexpectedEOS,
    /// This is an internal error that isn't supposed to happen.
    UnexpectedError,
    /// The text has been fully parsed, but syntax errors were encountered by the parser (and could
    /// be recovered from).
    ///
    /// See also [ParserError::SyntaxError].
    EncounteredErrors,
    /// An [Abort](Terminate::Abort) was returned by the [check_abort_request(...)] method of the
    /// listener.
    AbortRequest,
}

impl Display for ParserError {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", match self {
            ParserError::SyntaxError => "syntax error",
            ParserError::TooManyErrors => "too many errors while trying to recover",
            ParserError::Irrecoverable => "irrecoverable syntax error",
            ParserError::ExtraSymbol => "extra symbol after end of parsing",
            ParserError::UnexpectedEOS => "unexpected end of stream",
            ParserError::UnexpectedError => "unexpected error",
            ParserError::EncounteredErrors => "parsing failed due to previously encountered error(s)",
            ParserError::AbortRequest => "abort request",
        })
    }
}

/// Parser object. The [new(...)](Parser::new) method creates a new instance.
pub struct Parser<'a> {
    num_nt: usize,
    num_t: usize,
    alt_var: &'a [VarId],
    alts: Vec<Alternative>,
    opcodes: Vec<Vec<OpCode>>,
    init_opcodes: Vec<OpCode>,
    table: &'a [AltId],
    symbol_table: FixedSymTable,
    start: VarId,
    try_recover: bool,          // tries to recover from syntactical errors
}

impl<'a> Parser<'a> {
    /// Maximum number of error recoveries attempted when meeting a syntax error
    pub const MAX_NBR_RECOVERS: u32 = 5;
    pub const MAX_NBR_LEXER_ERRORS: u32 = 3;

    pub fn new(
        num_nt: usize,
        num_t: usize,
        alt_var: &'a [VarId],
        alts: Vec<Alternative>,
        opcodes: Vec<Vec<OpCode>>,
        init_opcodes: Vec<OpCode>,
        table: &'a [AltId],
        symbol_table: FixedSymTable,
        start: VarId,
    ) -> Self {
        Parser { num_nt, num_t, alt_var, alts, opcodes, init_opcodes, table, symbol_table, start, try_recover: true }
    }

    /// Gets a reference to the symbol table, if one is attached.
    pub fn get_symbol_table(&self) -> Option<&FixedSymTable> {
        Some(&self.symbol_table)
    }

    /// Sets the top nonterminal. The parser ends the parsing once the corresponding rule has been entirely parsed.
    pub fn set_start(&mut self, start: VarId) {
        assert!(self.num_nt > start as usize);
        self.start = start;
    }

    /// Enables or disables the recovery from syntactic or lexical errors.
    ///
    /// See also [ParserError::TooManyErrors] and [ParserError::SyntaxError].
    pub fn set_try_recover(&mut self, try_recover: bool) {
        self.try_recover = try_recover;
    }

    /// Determines with a quick simulation if `sym` is accepted by the grammar with the current
    /// `stack` and current stack symbol `stack_sym`.
    fn simulate(&self, stream_sym: Symbol, mut stack: Vec<OpCode>, mut stack_sym: OpCode) -> bool {
        const VERBOSE: bool = false;
        let error_skip_alt_id = self.alt_var.len() as AltId;
        let end_var_id = (self.num_t - 1) as VarId;
        if VERBOSE { print!("  next symbol could be: {}?", stream_sym.to_str(self.get_symbol_table())); }

        let ok = loop {
            match (stack_sym, stream_sym) {
                (OpCode::NT(var), _) | (OpCode::Loop(var), _) => {
                    let sr = if let Symbol::T(sr) = stream_sym { sr } else { end_var_id };
                    let alt_id = self.table[var as usize * self.num_t + sr as usize];
                    if alt_id >= error_skip_alt_id {
                        break false;
                    }
                    stack.extend(self.opcodes[alt_id as usize].clone());
                    stack_sym = stack.pop().unwrap();
                }
                (OpCode::Exit(_), _) => {
                    stack_sym = stack.pop().unwrap();
                }
                (OpCode::T(sk), Symbol::T(sr)) => {
                    break sk == sr;
                }
                (OpCode::End, Symbol::End) => {
                    break true;
                }
                (_, _) => {
                    break false;
                }
            }
        };
        if VERBOSE { println!(" {}", if ok { "yes" } else { "no" }); }
        ok
    }

    /// Parses the entire `stream`, calling the (listener) [wrapper](ListenerWrapper) with the
    /// [actions](Call) that correspond to the parser events.
    ///
    /// Returns `Ok(())` if the whole stream could be successfully parsed, or an
    /// [error](ParserError) if it couldn't.
    ///
    /// All errors are reported in the wrapper's log. Usually, the wrapper simply transmits the
    /// reports to the user listener's log (done in the generated code).
    pub fn parse_stream<I, L>(&mut self, wrapper: &mut L, mut stream: I) -> Result<(), ParserError>
        where I: Iterator<Item=ParserToken>,
              L: ListenerWrapper,
    {
        /// Outputs debug messages on stdout.
        const VERBOSE: bool = false;

        /// Delays the capture of the next token and the call to `intercept_token()` if it's possible.
        /// That allows to call as many `exit_*()` methods as possible in the listener, and so to
        /// update any information that may impact the translation of the next token.
        const DELAY_STREAM_INTERCEPTION: bool = cfg!(feature = "delay_stream_interception");

        let sym_table: Option<&FixedSymTable> = Some(&self.symbol_table);
        let mut stack = self.init_opcodes.clone();
        let mut stack_t = Vec::<String>::new();
        let error_skip_alt_id = self.alt_var.len() as AltId;
        let error_pop_alt_id = error_skip_alt_id + 1;
        if VERBOSE { println!("skip = {error_skip_alt_id}, pop = {error_pop_alt_id}"); }
        let mut recover_mode = false;
        let mut nbr_recovers = 0;
        let mut nbr_lexer_errors = 0;
        let end_var_id = (self.num_t - 1) as VarId;
        let mut stack_sym = stack.pop().unwrap();
        let mut stream_n = 0;
        let mut stream_pos = None;
        let mut stream_span = PosSpan::empty();
        let mut stream_sym = Symbol::default(); // must set fake value to comply with borrow checker
        let mut stream_str = String::default(); // must set fake value to comply with borrow checker
        let mut advance_stream = true;
        let mut hook_active = false;
        loop {
            if advance_stream &&
                (!DELAY_STREAM_INTERCEPTION                     // if optimization == false, only checks advance_stream
                    || (!matches!(stack_sym, OpCode::Exit(_))   // exit => needn't advance, unless...
                    || stream_sym == Symbol::Empty))            // Symbol::Empty => must advance no matter what
            {
                stream_n += 1;
                (stream_sym, stream_str) = stream.next().map(|(t, s, span)| {
                    // reads the next token and possibly transforms it in intercept_token() if it's used
                    // (if intercept_token() isn't used, it's optimized away)
                    let new_t = wrapper.intercept_token(t, &s, &span);
                    stream_pos = Some(span.first_forced());
                    stream_span = span;
                    (Symbol::T(new_t), s)
                }).unwrap_or_else(|| {
                    // checks if there's an error code after the end
                    if let Some((_t, s, span)) = stream.next() {
                        stream_span = span;
                        (Symbol::Empty, s)
                    } else {
                        (Symbol::End, String::new())
                    }
                });
                advance_stream = false;
                hook_active = true;
            }
            if VERBOSE {
                println!("{:-<40}", "");
                println!("input ({stream_n}{}): {}   stack_t: [{}]   stack: [{}]   current: {}",
                         if let Some(Pos(line, col)) = stream_pos { format!(", line {line}, col {col}") } else { String::new() },
                         stream_sym.to_str_ext(sym_table, &stream_str),
                         stack_t.join(", "),
                         stack.iter().map(|s| s.to_str(sym_table)).collect::<Vec<_>>().join(" "),
                         stack_sym.to_str_name(sym_table));
            }
            match (stack_sym, stream_sym) {
                (_, Symbol::Empty) => {
                    // lexer couldn't recognize the next symbol
                    if VERBOSE { println!("lexer error: {stream_str}"); }
                    wrapper.report(Some(&stream_span), LogMsg::Error(format!("lexical error: {stream_str}")));
                    nbr_lexer_errors += 1;
                    if nbr_lexer_errors >= Self::MAX_NBR_LEXER_ERRORS {
                        wrapper.report(None, LogMsg::Note(format!("too many lexical errors ({nbr_lexer_errors}), giving up")));
                        wrapper.abort();
                        return Err(ParserError::TooManyErrors);
                    }
                    advance_stream = true;
                }
                (OpCode::Hook, Symbol::T(t)) => {
                    if hook_active {
                        let new_t = wrapper.hook(t, stream_str.as_str(), &stream_span);
                        stream_sym = Symbol::T(new_t);
                        hook_active = false;
                    }
                    stack_sym = stack.pop().unwrap();
                }
                (OpCode::Hook, _) => {
                    // hooks may happen on other alternative symbols, in which case they're irrelevant
                    stack_sym = stack.pop().unwrap();
                }
                (OpCode::NT(var), _) | (OpCode::Loop(var), _) => {
                    let sr = if let Symbol::T(sr) = stream_sym { sr } else { end_var_id };
                    let alt_id = self.table[var as usize * self.num_t + sr as usize];
                    if VERBOSE {
                        println!("- table[{var}, {sr}] = {alt_id}: {} -> {}",
                                 Symbol::NT(var).to_str(self.get_symbol_table()),
                                 if alt_id >= error_skip_alt_id {
                                     "ERROR".to_string()
                                 } else if let Some(a) = self.alts.get(alt_id as usize) {
                                     a.to_str(sym_table)
                                 } else {
                                     "(alternative)".to_string()
                                 });
                    }
                    if !recover_mode && alt_id >= error_skip_alt_id {
                        let expected = (0..self.num_t as VarId).filter(|t| self.table[var as usize * self.num_t + *t as usize] < error_skip_alt_id)
                            .filter(|t| self.simulate(Symbol::T(*t), stack.clone(), stack_sym))
                            .map(|t| format!("'{}'", if t < end_var_id { Symbol::T(t).to_str(sym_table) } else { "<EOF>".to_string() }))
                            .collect::<Vec<_>>().join(", ");
                        let stream_sym_txt = if stream_sym.is_end() { "end of stream".to_string() } else { format!("input '{}'", stream_sym.to_str(sym_table)) };
                        let msg = format!("syntax error: found {stream_sym_txt} instead of {expected} while parsing '{}'{}",
                                          stack_sym.to_str(sym_table),
                                          if let Some(Pos(line, col)) = stream_pos { format!(", line {line}, col {col}") } else { String::new() });
                        if self.try_recover {
                            wrapper.report(Some(&stream_span), LogMsg::Error(msg));
                            if nbr_recovers >= Self::MAX_NBR_RECOVERS {
                                wrapper.report(None, LogMsg::Note(format!("too many errors ({nbr_recovers}), giving up")));
                                wrapper.abort();
                                return Err(ParserError::TooManyErrors);
                            }
                            nbr_recovers += 1;
                            recover_mode = true;
                        } else {
                            wrapper.report(Some(&stream_span), LogMsg::Error(msg));
                            wrapper.abort();
                            return Err(ParserError::SyntaxError);
                        }
                    }
                    if recover_mode {
                        if VERBOSE { println!("!NT {} <-> {}, alt_id = {alt_id}", stack_sym.to_str(self.get_symbol_table()), stream_sym.to_str(self.get_symbol_table())); }
                        if alt_id == error_skip_alt_id {
                            if stream_sym == Symbol::End {
                                let msg = "irrecoverable error, reached end of stream".to_string();
                                if VERBOSE { println!("(recovering) {msg}"); }
                                wrapper.report(None, LogMsg::Note(msg));
                                wrapper.abort();
                                return Err(ParserError::Irrecoverable);
                            }
                            if VERBOSE { println!("(recovering) skipping token {}", stream_sym.to_str(self.get_symbol_table())); }
                            advance_stream = true;
                        } else if alt_id == error_pop_alt_id {
                            if VERBOSE { println!("(recovering) popping {}", stack_sym.to_str(self.get_symbol_table())); }
                            stack_sym = stack.pop().unwrap();
                        } else if alt_id < error_skip_alt_id {
                            recover_mode = false;
                            let pos_str = if let Some(Pos(line, col)) = stream_pos { format!(", line {line}, col {col}") } else { String::new() };
                            wrapper.report(None, LogMsg::Note(format!("resynchronized on '{}'{pos_str}", stream_sym.to_str(self.get_symbol_table()))));
                            if VERBOSE { println!("(recovering) resynchronized{pos_str}"); }
                        } else {
                            panic!("illegal alt_id {alt_id}")
                        }
                    }
                    if !recover_mode {
                        let call = if stack_sym.is_loop() { Call::Loop } else { Call::Enter };
                        let t_data = std::mem::take(&mut stack_t);
                        if VERBOSE {
                            let f_str = if let Some(f) = &self.alts.get(alt_id as usize) {
                                f.to_str(sym_table)
                            } else {
                                "(alternative)".to_string()
                            };
                            println!(
                                "- to stack: [{}]",
                                self.opcodes[alt_id as usize].iter().filter(|s| !s.is_empty()).map(|s| s.to_str(sym_table))
                                    .collect::<Vec<_>>().join(" "));
                            println!(
                                "- {} {} -> {f_str} ({}): [{}]",
                                if stack_sym.is_loop() { "LOOP" } else { "ENTER" },
                                Symbol::NT(self.alt_var[alt_id as usize]).to_str(sym_table), t_data.len(), t_data.join(" "));
                        }
                        if nbr_recovers == 0 {
                            wrapper.switch(call, var, alt_id, Some(t_data));
                        }
                        stack.extend(self.opcodes[alt_id as usize].clone());
                        stack_sym = stack.pop().unwrap();
                    }
                }
                (OpCode::Exit(alt_id), _) => {
                    let var = self.alt_var[alt_id as usize];
                    let t_data = std::mem::take(&mut stack_t);
                    if VERBOSE {
                        println!(
                            "- EXIT {} syn ({}): [{}]",
                            Symbol::NT(var).to_str(sym_table), t_data.len(), t_data.join(" "));
                    }
                    if nbr_recovers == 0 {
                        wrapper.switch(Call::Exit, var, alt_id, Some(t_data));
                    }
                    stack_sym = stack.pop().unwrap();
                }
                (OpCode::T(sk), Symbol::T(sr)) => {
                    if !recover_mode && sk != sr {
                        let msg = format!(
                            "syntax error: found input '{}' instead of '{}'{}",
                            stream_sym.to_str(sym_table),
                            Symbol::T(sk).to_str(sym_table),
                            if let Some(Pos(line, col)) = stream_pos { format!(", line {line}, col {col}") } else { String::new() });
                        if self.try_recover {
                            wrapper.report(Some(&stream_span), LogMsg::Error(msg));
                            if nbr_recovers >= Self::MAX_NBR_RECOVERS {
                                wrapper.report(None, LogMsg::Note(format!("too many errors ({nbr_recovers}), giving up")));
                                wrapper.abort();
                                return Err(ParserError::TooManyErrors);
                            }
                            nbr_recovers += 1;
                            recover_mode = true;
                        } else {
                            wrapper.report(Some(&stream_span), LogMsg::Error(msg));
                            wrapper.abort();
                            return Err(ParserError::SyntaxError);
                        }
                    }
                    if recover_mode {
                        if VERBOSE { println!("!T {} <-> {}", Symbol::T(sk).to_str(self.get_symbol_table()), stream_sym.to_str(self.get_symbol_table())); }
                        if sk == sr {
                            recover_mode = false;
                            let pos_str = if let Some(Pos(line, col)) = stream_pos { format!(", line {line}, col {col}") } else { String::new() };
                            wrapper.report(Some(&stream_span), LogMsg::Note(format!("resynchronized on '{}'{pos_str}", stream_sym.to_str(self.get_symbol_table()))));
                            if VERBOSE { println!("(recovering) resynchronized{pos_str}"); }
                        } else {
                            if VERBOSE { println!("(recovering) popping {}", Symbol::T(sk).to_str(self.get_symbol_table())); }
                            stack_sym = stack.pop().unwrap();
                        }
                    }
                    if !recover_mode {
                        if VERBOSE { println!("- MATCH {}", stream_sym.to_str(sym_table)); }
                        if self.symbol_table.is_token_data(sk) {
                            stack_t.push(std::mem::take(&mut stream_str)); // must use take() to comply with borrow checker
                        }
                        stack_sym = stack.pop().unwrap();
                        wrapper.push_span(stream_span.take());
                        advance_stream = true;
                    }
                }
                (OpCode::End, Symbol::End) => {
                    if nbr_recovers == 0 {
                        wrapper.switch(Call::End(Terminate::None), 0, 0, None);
                    }
                    break;
                }
                (OpCode::End, _) => {
                    wrapper.report(Some(&stream_span), LogMsg::Error(format!("syntax error: found extra symbol '{}' after end of parsing", stream_sym.to_str(sym_table))));
                    wrapper.abort();
                    return Err(ParserError::ExtraSymbol);
                }
                (_, Symbol::End) => {
                    wrapper.report(None, LogMsg::Error(format!("syntax error: found end of stream instead of '{}'", stack_sym.to_str_name(sym_table))));
                    wrapper.abort();
                    return Err(ParserError::UnexpectedEOS);
                }
                (_, _) => {
                    let text = format!(
                        "unexpected syntax error: input '{}' while expecting '{}'{}",
                        stream_sym.to_str(sym_table), stack_sym.to_str_name(sym_table),
                        if let Some(Pos(line, col)) = stream_pos { format!(", line {line}, col {col}") } else { String::new() });
                    wrapper.report(Some(&stream_span), LogMsg::Error(text));
                    wrapper.abort();
                    return Err(ParserError::UnexpectedError);
                }
            }
            match wrapper.check_abort_request() {
                Terminate::None => {}
                terminate @ (Terminate::Abort | Terminate::Conclude) => {
                    if VERBOSE { println!("detected {terminate:?}"); }
                    stack_t.clear();
                    stack.clear();
                    wrapper.abort();
                    if nbr_recovers == 0 {
                        wrapper.switch(Call::End(terminate), 0, 0, None);
                    }
                    if terminate == Terminate::Abort {
                        return Err(ParserError::AbortRequest);
                    } else {
                        break;
                    }
                }
            }
        }
        assert!(stack_t.is_empty(), "stack_t: {}", stack_t.join(", "));
        assert!(stack.is_empty(), "stack: {}", stack.iter().map(|s| s.to_str(sym_table)).collect::<Vec<_>>().join(", "));
        if nbr_recovers == 0 {
            assert!(wrapper.is_stack_empty(), "symbol stack isn't empty");
            assert!(wrapper.is_stack_t_empty(), "text stack isn't empty");
            assert!(wrapper.is_stack_span_empty(), "span stack isn't empty");
            Ok(())
        } else {
            // when nbr_recovers > 0, we know that at least one error has been reported to the log, no need to add one here
            wrapper.abort();
            Err(ParserError::EncounteredErrors)
        }
    }
}

#[cfg(feature = "test_utils")]
impl<'a> Parser<'a> {
    pub fn get_alt_var(&self) -> &[VarId] {
        self.alt_var
    }

    pub fn get_alts(&self) -> &Vec<Alternative> {
        &self.alts
    }

    pub fn get_opcodes(&self) -> &Vec<Vec<OpCode>> {
        &self.opcodes
    }
}