Skip to main content

lexigram_core/parser/
lr.rs

1// Copyright (c) 2026 Redglyph (@gmail.com). All Rights Reserved.
2
3use std::fmt::{Display, Formatter};
4use std::marker::PhantomData;
5use crate::{AltId, CollectJoin, TokenId, VarId};
6use crate::fixed_sym_table::{FixedSymTable, SymInfoTable};
7use crate::lexer::{Pos, PosSpan};
8use crate::log::LogMsg;
9use crate::parser::{terminal_to_str_type, Call, ListenerWrapper, ParserError, ParserToken, Symbol, Terminate, RecoveryNt};
10
11/// State index
12pub type LRStateId = u16;
13
14#[derive(Clone, Copy, Default, PartialEq, Debug)]
15pub enum LRAction {
16    #[default]
17    Error,
18    Shift(LRStateId),
19    ShiftHook(LRStateId),
20    Reduce(AltId),
21    Accept,
22}
23
24impl LRAction {
25    pub fn is_hook(&self) -> bool {
26        matches!(self, LRAction::ShiftHook(_))
27    }
28
29    pub fn is_action(&self) -> bool {
30        match self {
31            LRAction::Error => false,
32            LRAction::Shift(_)
33            | LRAction::ShiftHook(_)
34            | LRAction::Reduce(_)
35            | LRAction::Accept => true,
36        }
37    }
38}
39
40impl Display for LRAction {
41    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
42        match self {
43            LRAction::Error => write!(f, "-"),
44            LRAction::Shift(s) => write!(f, "s{s}"),
45            LRAction::ShiftHook(s) => write!(f, "${s}"),
46            LRAction::Reduce(a) => write!(f, "r{a}"),
47            LRAction::Accept => write!(f, "acc"),
48        }
49    }
50}
51
52pub trait WrapperLRErrorRecovery {
53    /// Requests the wrapper to pop a nonterminal value. Some intermediate nonterminal values may have to be
54    /// dropped when the parser is trying to recover from a syntax error.
55    ///
56    /// The wrapper may want to store the latest dropped value, in case [`push_nt_recovery_value`] is
57    /// called immediately after to request a recovery value. In most cases, the latest dropped value is
58    /// a good candidate, especially if it's a loop nonterminal.
59    fn pop_nt_value(&mut self) {}
60
61    /// Requests the wrapper to push a nonterminal value to resynchronize its stack in case of error recovery.
62    ///
63    /// The wrapper should ideally requires a value to the user through the listener interface, knowing this value
64    /// is used to recover from a syntax error.
65    ///
66    /// Returns
67    /// * [RecoveryNt::Done] if the stack could be resynchronized.
68    /// * [RecoveryNt::Skip] if the value couldn't be created and another recover point should be found.
69    /// * [RecoveryNt::Abort] if the wrapper can't be resynchronized. The parser will continue parsing the text
70    ///   to detect other parsing errors, but it won't call the wrapper any more, except to intercept tokens.
71    #[allow(unused_variables)]
72    fn push_nt_recovery_value(&mut self, nt: VarId, err_span: &PosSpan) -> RecoveryNt { RecoveryNt::Abort }
73
74    /// Notifies the wrapper that the parser has recovered from the syntax error. It can be used to forward
75    /// the notification to the listener.
76    fn syntax_error_recovered(&mut self) {}
77}
78
79/// Parser object. The [new(...)](LRParser::new) method creates a new instance.
80pub struct LRParser<'a, T> {
81    num_nt: usize,                          // doesn't include the goal NT
82    num_t_full: usize,                      // includes the end symbol
83    action: &'a [LRAction],
84    goto: &'a [LRStateId],
85    alt_nt_len: &'a [(VarId, u16, u16)],    // alt_id -> (nt, # symbols in alt, # terminals in alt)
86    symbol_table: FixedSymTable,            // must include terminals <$> and <empty> at the end
87    init_hook: bool,                        // first terminal must be intercepted
88    state_symbol: &'a [Symbol],
89    nt_value: &'a [bool],
90    _phantom: PhantomData<T>,
91}
92
93impl<'a, T> LRParser<'a, T> {
94    pub const MAX_NBR_PARSER_ERRORS: u32 = 5;
95    pub const MAX_NBR_LEXER_ERRORS: u32 = 3;
96
97    pub fn new(
98        num_nt: usize,
99        num_t_full: usize,
100        action: &'a [LRAction],
101        goto: &'a [LRStateId],
102        alt_nt_len: &'a [(VarId, u16, u16)],
103        symbol_table: FixedSymTable,
104        init_hook: bool,
105        state_symbol: &'a [Symbol],
106        nt_value: &'a [bool],
107    ) -> Self {
108        LRParser { num_nt, num_t_full, action, goto, alt_nt_len, symbol_table, init_hook, state_symbol, nt_value, _phantom: PhantomData }
109    }
110
111    fn t_to_string(&self, t: TokenId) -> String {
112        if self.num_t_full - 1 > t as usize {
113            Symbol::T(t as TokenId).to_str_quote(Some(&self.symbol_table))
114        } else {
115            "<EOF>".to_string()
116        }
117    }
118
119    /// Parses the entire `stream`, calling the (listener) [wrapper](ListenerWrapper) with the
120    /// [actions](Call) that correspond to the parser events.
121    ///
122    /// Returns `Ok(())` if the whole stream could be successfully parsed, or an
123    /// [error](ParserError) if it couldn't.
124    ///
125    /// All errors are reported in the wrapper's log. Usually, the wrapper simply transmits the
126    /// reports to the user listener's log (done in the generated code).
127    pub fn parse_stream<I, L>(&mut self, wrapper: &mut L, mut stream: I) -> Result<(), ParserError>
128        where I: Iterator<Item=ParserToken>,
129              L: ListenerWrapper + WrapperLRErrorRecovery,
130    {
131        const VERBOSE: bool = false;
132        const BEFORE: &str = "\u{1b}[33m";
133        const AFTER : &str = "\u{1b}[0m";
134        let sym_table: Option<&FixedSymTable> = Some(&self.symbol_table);
135        let token_error = self.num_t_full as TokenId;
136        let token_eof = token_error - 1;
137        let mut error = None;
138        let mut nbr_parser_errors = 0;
139        let mut nbr_lexer_errors = 0;
140        let mut state: LRStateId = 0;
141        let mut stack_state = vec![state];
142        let mut stack_t = vec![];
143        let mut advance_stream = true;
144        let mut stream_pos = None;
145        let mut stream_span = PosSpan::empty();
146        let mut stream_sym = TokenId::default();
147        let mut stream_str = String::default();
148        let mut call_wrapper = true;
149        let mut hook = self.init_hook;
150        loop {
151            if advance_stream {
152                (stream_sym, stream_str) = if let Some((t, s, span)) = stream.next() {
153                    stream_pos = Some(span.first_forced());
154                    stream_span = span;
155                    if !hook {
156                        let new_t = wrapper.intercept_token(t, &s, &stream_span);
157                        (new_t, s)
158                    } else {
159                        hook = false;
160                        let new_t = if nbr_parser_errors == 0 {
161                            let new_t = wrapper.hook(t, s.as_str(), &stream_span);
162                            if VERBOSE {
163                                println!(
164                                    "{BEFORE}hook changed {} to {}{AFTER}",
165                                    Symbol::T(t).to_str(Some(&self.symbol_table)), Symbol::T(new_t).to_str(Some(&self.symbol_table)))
166                            }
167                            new_t
168                        } else {
169                            t
170                        };
171                        (new_t, s)
172                    }
173                } else {
174                    if let Some((_t, s, _span)) = stream.next() {
175                        // an error code after the end means an unrecognized sequence: we may try to continue
176                        wrapper.report(Some(&stream_span), LogMsg::Error(format!("lexical error: {s}")));
177                        nbr_lexer_errors += 1;
178                        if nbr_lexer_errors <= Self::MAX_NBR_LEXER_ERRORS {
179                            continue;
180                        }
181                        error = Some(ParserError::TooManyErrors);
182                        break;
183                    } else {
184                        // end of stream
185                        (token_eof, String::new())
186                    }
187                };
188                advance_stream = false;
189            }
190            if VERBOSE {
191                println!(
192                    "{BEFORE}states [{}] {state}, stack_t [{}], input: {} ({stream_str:?}){AFTER}",
193                    stack_state.iter().map(|s| s.to_string()).join(" "),
194                    stack_t.iter().map(|s| format!("{s:?}")).join(", "),
195                    Symbol::T(stream_sym).to_str(sym_table)
196                );
197            }
198            let action = self.action[stream_sym as usize + state as usize * self.num_t_full];
199            match action {
200                LRAction::Shift(new_state) | LRAction::ShiftHook(new_state) => {
201                    hook = action.is_hook();
202                    if VERBOSE { println!("{BEFORE}- shift({new_state}){AFTER}"); }
203                    stack_state.push(new_state);
204                    if self.symbol_table.is_token_data(stream_sym) {
205                        stack_t.push(std::mem::take(&mut stream_str));
206                    }
207                    if call_wrapper { wrapper.push_span(stream_span.take()); }
208                    state = new_state;
209                    advance_stream = true;
210                }
211                LRAction::Reduce(alt) => {
212                    // alt: s -> ω
213                    let (nt, alt_len, nbr_t) = self.alt_nt_len[alt as usize];   // s
214                    stack_state.drain(stack_state.len() - alt_len as usize..);  // pop |ω| states
215                    let pop_state = *stack_state.last().unwrap();
216                    state = self.goto[nt as usize + pop_state as usize * self.num_nt];
217                    stack_state.push(state);
218                    if VERBOSE { println!("{BEFORE}- reduce({alt}) -> state {pop_state} -> goto {state}{AFTER}"); }
219                    let t_data = stack_t.drain(stack_t.len() - nbr_t as usize..).to_vec();
220                    if call_wrapper { wrapper.switch(Call::Exit, nt, alt, Some(t_data)); }
221                }
222                LRAction::Accept => {
223                    if VERBOSE { println!("{BEFORE}- accept{AFTER}"); }
224                    if call_wrapper { wrapper.switch(Call::End(Terminate::None), 0, 0, None); }
225                    stack_state.pop();
226                    stack_state.pop();
227                    break;
228                }
229                LRAction::Error => {
230                    let expected = (0..self.num_t_full)
231                        .filter(|t| self.action[*t + state as usize * self.num_t_full].is_action())
232                        .map(|t| self.t_to_string(t as TokenId))
233                        .join(", ");
234                    let sym_str = if stream_sym == token_eof {
235                        "end of stream".to_string()
236                    } else {
237                        format!("input {}", terminal_to_str_type(stream_sym, sym_table, &stream_str))
238                    };
239                    let msg = format!(
240                        "syntax error: unexpected {sym_str}{}{}",
241                        if expected.is_empty() { String::new() } else { format!(" instead of {expected}") },
242                        if let Some(Pos(line, col)) = stream_pos { format!(", line {line}, col {col}") } else { String::new() }
243                    );
244                    wrapper.report(Some(&stream_span), LogMsg::Error(msg));
245                    nbr_parser_errors += 1;
246                    if nbr_parser_errors > Self::MAX_NBR_PARSER_ERRORS {
247                        error = Some(ParserError::TooManyErrors);
248                        break;
249                    }
250                    let prev_call_wrapper = call_wrapper;
251                    if let Some(new_state) = self.recover(
252                        &mut stream,
253                        &mut stream_sym,
254                        &mut stream_str,
255                        &mut stream_pos,
256                        &mut stream_span,
257                        wrapper,
258                        &mut stack_state,
259                        &mut stack_t,
260                        &mut call_wrapper
261                    ) {
262                        let pos = if let Some(pos) = stream_pos { format!(" at {pos}") } else { String::new() };
263                        wrapper.report(None, LogMsg::Note(format!("resynchronized from syntax error on {}{pos}", self.t_to_string(stream_sym))));
264                        if prev_call_wrapper && !call_wrapper {
265                            wrapper.report(None, LogMsg::Note("the rest of the stream will be parsed, but the listener interface can't be used any more".to_string()));
266                        }
267                        state = new_state;
268                        stack_state.push(state);
269                        if call_wrapper {
270                            wrapper.syntax_error_recovered();
271                        }
272                    } else {
273                        if VERBOSE { println!("couldn't recover\n- states {stack_state:?}"); }
274                        error = Some(ParserError::SyntaxError);
275                        break;
276                    }
277                }
278            }
279            match wrapper.check_abort_request() {
280                Terminate::None => {}
281                terminate @ (Terminate::Abort | Terminate::Conclude) => {
282                    if VERBOSE { println!("{BEFORE}detected {terminate:?}{AFTER}"); }
283                    stack_state.clear();
284                    wrapper.abort();
285                    wrapper.switch(Call::End(terminate), 0, 0, None);
286                    if terminate == Terminate::Abort {
287                        return Err(ParserError::AbortRequest);
288                    } else {
289                        break;
290                    }
291                }
292            }
293        }
294        if nbr_parser_errors == 0 && nbr_lexer_errors == 0 && error.is_none() {
295            assert!(stack_t.is_empty(), "stack_t: {}", stack_t.join(", "));
296            assert!(stack_state.is_empty(), "stack_state: {}", stack_state.iter().map(LRStateId::to_string).collect::<Vec<_>>().join(", "));
297            assert!(wrapper.is_stack_empty(), "symbol stack isn't empty");
298            assert!(wrapper.is_stack_t_empty(), "text stack isn't empty");
299            assert!(wrapper.is_stack_span_empty(), "span stack isn't empty");
300            Ok(())
301        } else {
302            let err = error.unwrap_or(ParserError::EncounteredErrors);
303            wrapper.abort();
304            Err(err)
305        }
306    }
307
308    /// Returns the symbol on the left of the dot and whether it has a value.
309    fn get_state_symbol_and_value(&self, state: LRStateId) -> (Symbol, bool) {
310        let sym = self.state_symbol[state as usize];
311        let has_value = match sym {
312            Symbol::T(t) => self.symbol_table.is_token_data(t),
313            Symbol::NT(nt) => self.nt_value[nt as usize],
314            Symbol::Empty => false,
315            Symbol::End => panic!(),
316        };
317        (sym, has_value)
318    }
319
320    fn recover<I, L>(
321        &self,
322        stream: &mut I,
323        stream_sym: &mut u16,
324        stream_str: &mut String,
325        stream_pos: &mut Option<Pos>,
326        stream_span: &mut PosSpan,
327        wrapper: &mut L,
328        stack_state: &mut Vec<LRStateId>,
329        stack_t: &mut Vec<String>,
330        call_wrapper: &mut bool
331    ) -> Option<LRStateId>
332    where
333        I: Iterator<Item=ParserToken>,
334        L: ListenerWrapper + WrapperLRErrorRecovery,
335    {
336        const VERBOSE: bool = false;
337        const BEFORE_ANSI: &str = "\u{1b}[31m";
338        const AFTER_ANSI : &str = "\u{1b}[0m";
339        if VERBOSE { println!("{BEFORE_ANSI}parser panic-mode recovery:{AFTER_ANSI}"); }
340        let mut err_span = PosSpan::empty();
341        // finds a state with a GOTO, but don't pop the start state
342        while let Some(state) = stack_state.pop() {
343            if VERBOSE { println!("{BEFORE_ANSI}- states {stack_state:?} {state}{AFTER_ANSI}"); }
344            let goto_state = state;
345            let goto_row = state as usize * self.num_nt;
346            // check the available GOTO states:
347            let candidates = self.goto.iter().skip(goto_row).take(self.num_nt).enumerate()
348                .map(|(v, s)| (v as VarId, *s)).filter(|(_, s)| *s > 0)
349                .to_vec();
350            if VERBOSE {
351                println!(
352                    "{BEFORE_ANSI}- goto_state {goto_state}, candidates = {}, err_span {err_span}{AFTER_ANSI}",
353                    candidates.iter().map(|(v, st)| format!("({}, {st})", Symbol::NT(*v).to_str(Some(&self.symbol_table)))).join(", ")
354                );
355            }
356            if candidates.is_empty() {
357                if *call_wrapper {
358                    err_span += &wrapper.pop_span();
359                }
360                let (sym, has_value) = self.get_state_symbol_and_value(state);
361                match sym {
362                    Symbol::T(_) => {
363                        if has_value { stack_t.pop(); }
364                    }
365                    Symbol::NT(_) => {
366                        if has_value && *call_wrapper { wrapper.pop_nt_value(); }
367                    }
368                    _ => panic!()
369                }
370            }
371            if VERBOSE {
372                println!(
373                    "{BEFORE_ANSI}- candidates = {}, err_span {err_span}{AFTER_ANSI}",
374                    candidates.iter().map(|(v, st)| format!("({}, {st})", Symbol::NT(*v).to_str(Some(&self.symbol_table)))).join(", "));
375            }
376            let token_error = self.num_t_full as TokenId;
377            let token_eof = token_error - 1;
378            let mut skip = candidates.is_empty();
379            while !skip {
380                if VERBOSE { println!("{BEFORE_ANSI}  - states {stack_state:?} {state}, err_span {err_span}{AFTER_ANSI}"); }
381                for &(var, state) in &candidates {
382                    let action = &self.action[*stream_sym as usize + state as usize * self.num_t_full];
383                    if action.is_action() {
384                        if VERBOSE { println!("{BEFORE_ANSI}- symbol {} is fine for state {state}{AFTER_ANSI}", self.t_to_string(*stream_sym)); }
385                        // if the wrapper is called, it can skip the recovery of the current nonterminal and
386                        // recover at a higher level
387                        let recovery_result = if *call_wrapper { wrapper.push_nt_recovery_value(var, &err_span) } else { RecoveryNt::Abort };
388                        *call_wrapper &= recovery_result != RecoveryNt::Abort;
389                        skip = *call_wrapper && recovery_result == RecoveryNt::Skip;
390                        if !skip {
391                            // we put back the goto_state on the stack because it will be required after the action
392                            stack_state.push(goto_state);
393                            if *call_wrapper {
394                                wrapper.push_span(err_span);
395                                if VERBOSE {
396                                    println!("{BEFORE_ANSI}{}{AFTER_ANSI}", wrapper.get_status().join("\n"));
397                                    println!("{BEFORE_ANSI}- states {stack_state:?}{AFTER_ANSI}");
398                                }
399                            }
400                            return Some(state);
401                        } else if *call_wrapper {
402                            // removes the span corresponding to the skipped state and accumulates it
403                            err_span += &wrapper.pop_span();
404                        }
405                        if VERBOSE { println!("{BEFORE_ANSI}skipping this recovery point{AFTER_ANSI}"); }
406                    }
407                }
408                if !skip {
409                    (*stream_sym, *stream_str) = loop {
410                        if let Some((t, s, span)) = stream.next() {
411                            *stream_pos = Some(span.first_forced());
412                            // accumulates the position of the dropped token
413                            err_span += stream_span;
414                            *stream_span = span;
415                            // we can't say which interception to use, so we call both
416                            let t1 = wrapper.intercept_token(t, &s, stream_span);
417                            let t2 = wrapper.hook(t1, s.as_str(), stream_span);
418                            break (t2, s);
419                        } else {
420                            *stream_pos = None;
421                            if let Some((_t, s, _span)) = stream.next() {
422                                // an error code after the end means an unrecognized sequence: we may try to continue,
423                                // but we don't count the max lexical errors here for the sake of simplicity
424                                wrapper.report(Some(stream_span), LogMsg::Error(format!("lexical error: {s}")));
425                                continue;
426                            } else {
427                                // end of stream
428                                break (token_eof, String::new());
429                            }
430                        }
431                    };
432                    if *stream_sym == token_eof { return None; }
433                    if VERBOSE { println!("{BEFORE_ANSI}- no symbol was compatible, scanning new symbol {}{AFTER_ANSI}", self.t_to_string(*stream_sym)); }
434                }
435            }
436        }
437        None
438    }
439}