Skip to main content

lexigram_core/parser/
ll1.rs

1// Copyright (c) 2026 Redglyph (@gmail.com). All Rights Reserved.
2
3use crate::alt::Alternative;
4use crate::parser::{terminal_to_str_type, Call, ListenerWrapper, OpCode, ParserError, ParserToken, Symbol, Terminate};
5use crate::{AltId, VarId};
6use crate::fixed_sym_table::{FixedSymTable, SymInfoTable};
7use crate::lexer::{Pos, PosSpan};
8use crate::log::LogMsg;
9
10/// LL(1) parser object. The [new(...)](LLParser::new) method creates a new instance.
11pub struct LLParser<'a> {
12    num_nt: usize,
13    num_t: usize,
14    alt_var: &'a [VarId],
15    alts: Vec<Alternative>,
16    opcodes: Vec<Vec<OpCode>>,
17    init_opcodes: Vec<OpCode>,
18    table: &'a [AltId],
19    symbol_table: FixedSymTable,
20    start: VarId,
21    try_recover: bool,          // tries to recover from syntactical errors
22}
23
24impl<'a> LLParser<'a> {
25    /// Maximum number of error recoveries attempted when meeting a syntax error
26    pub const MAX_NBR_PARSER_ERRORS: u32 = 5;
27    pub const MAX_NBR_LEXER_ERRORS: u32 = 3;
28
29    pub fn new(
30        num_nt: usize,
31        num_t: usize,
32        alt_var: &'a [VarId],
33        alts: Vec<Alternative>,
34        opcodes: Vec<Vec<OpCode>>,
35        init_opcodes: Vec<OpCode>,
36        table: &'a [AltId],
37        symbol_table: FixedSymTable,
38        start: VarId,
39    ) -> Self {
40        LLParser { num_nt, num_t, alt_var, alts, opcodes, init_opcodes, table, symbol_table, start, try_recover: true }
41    }
42
43    /// Gets a reference to the symbol table, if one is attached.
44    pub fn get_symbol_table(&self) -> Option<&FixedSymTable> {
45        Some(&self.symbol_table)
46    }
47
48    /// Sets the top nonterminal. The parser ends the parsing once the corresponding rule has been entirely parsed.
49    pub fn set_start(&mut self, start: VarId) {
50        assert!(self.num_nt > start as usize);
51        self.start = start;
52    }
53
54    /// Enables or disables the recovery from syntactic or lexical errors.
55    ///
56    /// See also [ParserError::TooManyErrors] and [ParserError::SyntaxError].
57    pub fn set_try_recover(&mut self, try_recover: bool) {
58        self.try_recover = try_recover;
59    }
60
61    /// Determines with a quick simulation if `sym` is accepted by the grammar with the current
62    /// `stack` and current stack symbol `stack_sym`.
63    fn simulate(&self, stream_sym: Symbol, mut stack: Vec<OpCode>, mut stack_sym: OpCode) -> bool {
64        const VERBOSE: bool = false;
65        let error_skip_alt_id = self.alt_var.len() as AltId;
66        let end_var_id = (self.num_t - 1) as VarId;
67        if VERBOSE { print!("  next symbol could be: {}?", stream_sym.to_str(self.get_symbol_table())); }
68
69        let ok = loop {
70            match (stack_sym, stream_sym) {
71                (OpCode::NT(var), _) | (OpCode::Loop(var), _) => {
72                    let sr = if let Symbol::T(sr) = stream_sym { sr } else { end_var_id };
73                    let alt_id = self.table[var as usize * self.num_t + sr as usize];
74                    if alt_id >= error_skip_alt_id {
75                        break false;
76                    }
77                    stack.extend(self.opcodes[alt_id as usize].clone());
78                    stack_sym = stack.pop().unwrap();
79                }
80                (OpCode::Exit(_), _) => {
81                    stack_sym = stack.pop().unwrap();
82                }
83                (OpCode::T(sk), Symbol::T(sr)) => {
84                    break sk == sr;
85                }
86                (OpCode::End, Symbol::End) => {
87                    break true;
88                }
89                (_, _) => {
90                    break false;
91                }
92            }
93        };
94        if VERBOSE { println!(" {}", if ok { "yes" } else { "no" }); }
95        ok
96    }
97
98    /// Parses the entire `stream`, calling the (listener) [wrapper](ListenerWrapper) with the
99    /// [actions](Call) that correspond to the parser events.
100    ///
101    /// Returns `Ok(())` if the whole stream could be successfully parsed, or an
102    /// [error](ParserError) if it couldn't.
103    ///
104    /// All errors are reported in the wrapper's log. Usually, the wrapper simply transmits the
105    /// reports to the user listener's log (done in the generated code).
106    pub fn parse_stream<I, L>(&mut self, wrapper: &mut L, mut stream: I) -> Result<(), ParserError>
107        where I: Iterator<Item=ParserToken>,
108              L: ListenerWrapper,
109    {
110        /// Outputs debug messages on stdout.
111        const VERBOSE: bool = false;
112
113        /// Delays the capture of the next token and the call to `intercept_token()` if it's possible.
114        /// That allows to call as many `exit_*()` methods as possible in the listener, and so to
115        /// update any information that may impact the translation of the next token.
116        const DELAY_STREAM_INTERCEPTION: bool = cfg!(feature = "delay_stream_interception");
117
118        let sym_table: Option<&FixedSymTable> = Some(&self.symbol_table);
119        let mut stack = self.init_opcodes.clone();
120        let mut stack_t = Vec::<String>::new();
121        let error_skip_alt_id = self.alt_var.len() as AltId;
122        let error_pop_alt_id = error_skip_alt_id + 1;
123        if VERBOSE { println!("skip = {error_skip_alt_id}, pop = {error_pop_alt_id}"); }
124        let mut recover_mode = false;
125        let mut nbr_parser_errors = 0;
126        let mut nbr_lexer_errors = 0;
127        let end_var_id = (self.num_t - 1) as VarId;
128        let mut stack_sym = stack.pop().unwrap();
129        let mut stream_n = 0;
130        let mut stream_pos = None;
131        let mut stream_span = PosSpan::empty();
132        let mut stream_sym = Symbol::default(); // must set fake value to comply with borrow checker
133        let mut stream_str = String::default(); // must set fake value to comply with borrow checker
134        let mut advance_stream = true;
135        let mut hook_active = false;
136        loop {
137            if advance_stream &&
138                (!DELAY_STREAM_INTERCEPTION                     // if optimization == false, only checks advance_stream
139                    || (!matches!(stack_sym, OpCode::Exit(_))   // exit => needn't advance, unless...
140                    || stream_sym == Symbol::Empty))            // Symbol::Empty => must advance no matter what
141            {
142                stream_n += 1;
143                (stream_sym, stream_str) = stream.next().map(|(t, s, span)| {
144                    // reads the next token and possibly transforms it in intercept_token() if it's used
145                    // (if intercept_token() isn't used, it's optimized away)
146                    let new_t = wrapper.intercept_token(t, &s, &span);
147                    stream_pos = Some(span.first_forced());
148                    stream_span = span;
149                    (Symbol::T(new_t), s)
150                }).unwrap_or_else(|| {
151                    // checks if there's an error code after the end
152                    if let Some((_t, s, span)) = stream.next() {
153                        stream_span = span;
154                        (Symbol::Empty, s)
155                    } else {
156                        (Symbol::End, String::new())
157                    }
158                });
159                advance_stream = false;
160                hook_active = true;
161            }
162            if VERBOSE {
163                println!("{:-<40}", "");
164                println!("input ({stream_n}{}): {}   stack_t: [{}]   stack: [{}]   current: {}",
165                         if let Some(Pos(line, col)) = stream_pos { format!(", line {line}, col {col}") } else { String::new() },
166                         stream_sym.to_str_ext(sym_table, &stream_str),
167                         stack_t.join(", "),
168                         stack.iter().map(|s| s.to_str(sym_table)).collect::<Vec<_>>().join(" "),
169                         stack_sym.to_str_name(sym_table));
170            }
171            match (stack_sym, stream_sym) {
172                (_, Symbol::Empty) => {
173                    // lexer couldn't recognize the next symbol
174                    if VERBOSE { println!("lexer error: {stream_str}"); }
175                    wrapper.report(Some(&stream_span), LogMsg::Error(format!("lexical error: {stream_str}")));
176                    if nbr_lexer_errors >= Self::MAX_NBR_LEXER_ERRORS {
177                        wrapper.report(None, LogMsg::Note(format!("too many lexical errors ({nbr_lexer_errors}), giving up")));
178                        wrapper.abort();
179                        return Err(ParserError::TooManyErrors);
180                    }
181                    nbr_lexer_errors += 1;
182                    advance_stream = true;
183                }
184                (OpCode::Hook, Symbol::T(t)) => {
185                    if hook_active {
186                        let new_t = wrapper.hook(t, stream_str.as_str(), &stream_span);
187                        stream_sym = Symbol::T(new_t);
188                        hook_active = false;
189                    }
190                    stack_sym = stack.pop().unwrap();
191                }
192                (OpCode::Hook, _) => {
193                    // hooks may happen on other alternative symbols, in which case they're irrelevant
194                    stack_sym = stack.pop().unwrap();
195                }
196                (OpCode::NT(var), _) | (OpCode::Loop(var), _) => {
197                    let sr = if let Symbol::T(sr) = stream_sym { sr } else { end_var_id };
198                    let alt_id = self.table[var as usize * self.num_t + sr as usize];
199                    if VERBOSE {
200                        println!("- table[{var}, {sr}] = {alt_id}: {} -> {}",
201                                 Symbol::NT(var).to_str(self.get_symbol_table()),
202                                 if alt_id >= error_skip_alt_id {
203                                     "ERROR".to_string()
204                                 } else if let Some(a) = self.alts.get(alt_id as usize) {
205                                     a.to_str(sym_table)
206                                 } else {
207                                     "(alternative)".to_string()
208                                 });
209                    }
210                    if !recover_mode && alt_id >= error_skip_alt_id {
211                        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)
212                            .filter(|t| self.simulate(Symbol::T(*t), stack.clone(), stack_sym))
213                            .map(|t| if t < end_var_id { Symbol::T(t).to_str_quote(sym_table) } else { "<EOF>".to_string() })
214                            .collect::<Vec<_>>().join(", ");
215                        let msg = format!(
216                            "syntax error: found {} instead of {expected} while parsing {}{}",
217                            stream_sym.to_str_type(sym_table, &stream_str),
218                            stack_sym.to_str(sym_table),
219                            if let Some(Pos(line, col)) = stream_pos { format!(", line {line}, col {col}") } else { String::new() });
220                        if self.try_recover {
221                            wrapper.report(Some(&stream_span), LogMsg::Error(msg));
222                            if nbr_parser_errors >= Self::MAX_NBR_PARSER_ERRORS {
223                                wrapper.report(None, LogMsg::Note(format!("too many errors ({nbr_parser_errors}), giving up")));
224                                wrapper.abort();
225                                return Err(ParserError::TooManyErrors);
226                            }
227                            nbr_parser_errors += 1;
228                            recover_mode = true;
229                        } else {
230                            wrapper.report(Some(&stream_span), LogMsg::Error(msg));
231                            wrapper.abort();
232                            return Err(ParserError::SyntaxError);
233                        }
234                    }
235                    if recover_mode {
236                        if VERBOSE { println!("!NT {} <-> {}, alt_id = {alt_id}", stack_sym.to_str(self.get_symbol_table()), stream_sym.to_str(self.get_symbol_table())); }
237                        if alt_id == error_skip_alt_id {
238                            if stream_sym == Symbol::End {
239                                let msg = "irrecoverable error, reached end of stream".to_string();
240                                if VERBOSE { println!("(recovering) {msg}"); }
241                                wrapper.report(None, LogMsg::Note(msg));
242                                wrapper.abort();
243                                return Err(ParserError::Irrecoverable);
244                            }
245                            if VERBOSE { println!("(recovering) skipping token {}", stream_sym.to_str(self.get_symbol_table())); }
246                            advance_stream = true;
247                        } else if alt_id == error_pop_alt_id {
248                            if VERBOSE { println!("(recovering) popping {}", stack_sym.to_str(self.get_symbol_table())); }
249                            stack_sym = stack.pop().unwrap();
250                        } else if alt_id < error_skip_alt_id {
251                            recover_mode = false;
252                            let pos_str = if let Some(Pos(line, col)) = stream_pos { format!(", line {line}, col {col}") } else { String::new() };
253                            wrapper.report(None, LogMsg::Note(format!("resynchronized on '{}'{pos_str}", stream_sym.to_str(self.get_symbol_table()))));
254                            if VERBOSE { println!("(recovering) resynchronized{pos_str}"); }
255                        } else {
256                            panic!("illegal alt_id {alt_id}")
257                        }
258                    }
259                    if !recover_mode {
260                        let call = if stack_sym.is_loop() { Call::Loop } else { Call::Enter };
261                        let t_data = std::mem::take(&mut stack_t);
262                        if VERBOSE {
263                            let f_str = if let Some(f) = &self.alts.get(alt_id as usize) {
264                                f.to_str(sym_table)
265                            } else {
266                                "(alternative)".to_string()
267                            };
268                            println!(
269                                "- to stack: [{}]",
270                                self.opcodes[alt_id as usize].iter().filter(|s| !s.is_empty()).map(|s| s.to_str(sym_table))
271                                    .collect::<Vec<_>>().join(" "));
272                            println!(
273                                "- {} {} -> {f_str} ({}): [{}]",
274                                if stack_sym.is_loop() { "LOOP" } else { "ENTER" },
275                                Symbol::NT(self.alt_var[alt_id as usize]).to_str(sym_table), t_data.len(), t_data.join(" "));
276                        }
277                        if nbr_parser_errors == 0 {
278                            wrapper.switch(call, var, alt_id, Some(t_data));
279                        }
280                        stack.extend(self.opcodes[alt_id as usize].clone());
281                        stack_sym = stack.pop().unwrap();
282                    }
283                }
284                (OpCode::Exit(alt_id), _) => {
285                    let var = self.alt_var[alt_id as usize];
286                    let t_data = std::mem::take(&mut stack_t);
287                    if VERBOSE {
288                        println!(
289                            "- EXIT {} syn ({}): [{}]",
290                            Symbol::NT(var).to_str(sym_table), t_data.len(), t_data.join(" "));
291                    }
292                    if nbr_parser_errors == 0 {
293                        wrapper.switch(Call::Exit, var, alt_id, Some(t_data));
294                    }
295                    stack_sym = stack.pop().unwrap();
296                }
297                (OpCode::T(sk), Symbol::T(sr)) => {
298                    if !recover_mode && sk != sr {
299                        let msg = format!(
300                            "syntax error: found input {} instead of {}{}",
301                            terminal_to_str_type(sr, sym_table, &stream_str),
302                            Symbol::T(sk).to_str_quote(sym_table),
303                            if let Some(Pos(line, col)) = stream_pos { format!(", line {line}, col {col}") } else { String::new() });
304                        if self.try_recover {
305                            wrapper.report(Some(&stream_span), LogMsg::Error(msg));
306                            if nbr_parser_errors >= Self::MAX_NBR_PARSER_ERRORS {
307                                wrapper.report(None, LogMsg::Note(format!("too many errors ({nbr_parser_errors}), giving up")));
308                                wrapper.abort();
309                                return Err(ParserError::TooManyErrors);
310                            }
311                            nbr_parser_errors += 1;
312                            recover_mode = true;
313                        } else {
314                            wrapper.report(Some(&stream_span), LogMsg::Error(msg));
315                            wrapper.abort();
316                            return Err(ParserError::SyntaxError);
317                        }
318                    }
319                    if recover_mode {
320                        if VERBOSE { println!("!T {} <-> {}", Symbol::T(sk).to_str(self.get_symbol_table()), stream_sym.to_str(self.get_symbol_table())); }
321                        if sk == sr {
322                            recover_mode = false;
323                            let pos_str = if let Some(Pos(line, col)) = stream_pos { format!(", line {line}, col {col}") } else { String::new() };
324                            wrapper.report(Some(&stream_span), LogMsg::Note(format!("resynchronized on '{}'{pos_str}", stream_sym.to_str(self.get_symbol_table()))));
325                            if VERBOSE { println!("(recovering) resynchronized{pos_str}"); }
326                        } else {
327                            if VERBOSE { println!("(recovering) popping {}", Symbol::T(sk).to_str(self.get_symbol_table())); }
328                            stack_sym = stack.pop().unwrap();
329                        }
330                    }
331                    if !recover_mode {
332                        if VERBOSE { println!("- MATCH {}", stream_sym.to_str(sym_table)); }
333                        if self.symbol_table.is_token_data(sk) {
334                            stack_t.push(std::mem::take(&mut stream_str)); // must use take() to comply with borrow checker
335                        }
336                        stack_sym = stack.pop().unwrap();
337                        wrapper.push_span(stream_span.take());
338                        advance_stream = true;
339                    }
340                }
341                (OpCode::End, Symbol::End) => {
342                    if nbr_parser_errors == 0 {
343                        wrapper.switch(Call::End(Terminate::None), 0, 0, None);
344                    }
345                    break;
346                }
347                (OpCode::End, _) => {
348                    wrapper.report(Some(&stream_span), LogMsg::Error(format!(
349                        "syntax error: found extra symbol {} after end of parsing",
350                        stream_sym.to_str_type(sym_table, &stream_str))));
351                    wrapper.abort();
352                    return Err(ParserError::ExtraSymbol);
353                }
354                (_, Symbol::End) => {
355                    wrapper.report(None, LogMsg::Error(format!("syntax error: found end of stream instead of {}", stack_sym.to_str_name(sym_table))));
356                    wrapper.abort();
357                    return Err(ParserError::UnexpectedEOS);
358                }
359                (_, _) => {
360                    let text = format!(
361                        "unexpected syntax error: {} while expecting {}{}",
362                        stream_sym.to_str_type(sym_table, &stream_str), stack_sym.to_str_name(sym_table),
363                        if let Some(Pos(line, col)) = stream_pos { format!(", line {line}, col {col}") } else { String::new() });
364                    wrapper.report(Some(&stream_span), LogMsg::Error(text));
365                    wrapper.abort();
366                    return Err(ParserError::UnexpectedError);
367                }
368            }
369            match wrapper.check_abort_request() {
370                Terminate::None => {}
371                terminate @ (Terminate::Abort | Terminate::Conclude) => {
372                    if VERBOSE { println!("detected {terminate:?}"); }
373                    stack_t.clear();
374                    stack.clear();
375                    wrapper.abort();
376                    if nbr_parser_errors == 0 {
377                        wrapper.switch(Call::End(terminate), 0, 0, None);
378                    }
379                    if terminate == Terminate::Abort {
380                        return Err(ParserError::AbortRequest);
381                    } else {
382                        break;
383                    }
384                }
385            }
386        }
387        assert!(stack_t.is_empty(), "stack_t: {}", stack_t.join(", "));
388        assert!(stack.is_empty(), "stack: {}", stack.iter().map(|s| s.to_str(sym_table)).collect::<Vec<_>>().join(", "));
389        if nbr_parser_errors == 0 && nbr_lexer_errors == 0 {
390            assert!(wrapper.is_stack_empty(), "symbol stack isn't empty");
391            assert!(wrapper.is_stack_t_empty(), "text stack isn't empty");
392            assert!(wrapper.is_stack_span_empty(), "span stack isn't empty");
393            Ok(())
394        } else {
395            // when nbr_recovers > 0, we know that at least one error has been reported to the log, no need to add one here
396            wrapper.abort();
397            Err(ParserError::EncounteredErrors)
398        }
399    }
400}
401
402#[cfg(feature = "test_utils")]
403impl<'a> LLParser<'a> {
404    pub fn get_alt_var(&self) -> &[VarId] {
405        self.alt_var
406    }
407
408    pub fn get_alts(&self) -> &Vec<Alternative> {
409        &self.alts
410    }
411
412    pub fn get_opcodes(&self) -> &Vec<Vec<OpCode>> {
413        &self.opcodes
414    }
415}