Skip to main content

lexigram_core/parser/
mod.rs

1// Copyright (c) 2025 Redglyph (@gmail.com). All Rights Reserved.
2
3use std::fmt::{Display, Formatter};
4use crate::fixed_sym_table::SymInfoTable;
5use crate::{AltId, TokenId, VarId};
6use crate::lexer::PosSpan;
7use crate::log::{LogMsg, Logger};
8
9pub(crate) mod tests;
10pub mod lr;
11pub mod ll1;
12
13// ---------------------------------------------------------------------------------------------
14
15#[derive(Clone, Copy, Default, PartialEq, PartialOrd, Eq, Ord, Debug, Hash)]
16pub enum Symbol {
17    T(TokenId),         // terminal
18    NT(VarId),          // non-terminal
19    #[default] Empty,   // empty symbol
20    End                 // end of stream
21}
22
23impl Symbol {
24    pub fn is_end(&self) -> bool {
25        matches!(self, Symbol::End)
26    }
27
28    pub fn is_empty(&self) -> bool {
29        matches!(self, Symbol::Empty)
30    }
31
32    pub fn is_t(&self) -> bool {
33        matches!(self, Symbol::T(_))
34    }
35
36    pub fn is_nt(&self) -> bool {
37        matches!(self, Symbol::NT(_))
38    }
39
40    pub fn is_t_or_nt(&self) -> bool {
41        matches!(self, Symbol::T(_) | Symbol::NT(_))
42    }
43
44    pub fn to_str<T: SymInfoTable>(&self, symbol_table: Option<&T>) -> String {
45        symbol_table.map(|t| t.get_str(self)).unwrap_or_else(|| self.to_string())
46    }
47
48    /// Converts the symbol to string, using the symbol table if available, and
49    /// surrounding it with quotes if it's a string literal.
50    pub fn to_str_quote<T: SymInfoTable>(&self, symbol_table: Option<&T>) -> String {
51        symbol_table.map(|t| t.get_name_quote(self)).unwrap_or_else(|| self.to_string())
52    }
53
54    pub fn to_str_name<T: SymInfoTable>(&self, symbol_table: Option<&T>) -> String {
55        symbol_table.map(|t| t.get_name(self)).unwrap_or_else(|| self.to_string())
56    }
57
58    /// Converts the symbol to string, using the symbol table if available.
59    pub fn to_str_ext<T: SymInfoTable>(&self, symbol_table: Option<&T>, ext: &String) -> String {
60        let mut result = self.to_str(symbol_table);
61        if let Some(t) = symbol_table {
62            if t.is_symbol_t_data(self) {
63                result.push_str(&format!("({ext})"));
64            }
65        }
66        result
67    }
68
69    /// Converts the symbol to a string that's explicit for the user, using the symbol table
70    /// if available to display the token name in case of a variable token.
71    pub fn to_str_type<T: SymInfoTable>(&self, symbol_table: Option<&T>, ext: &String) -> String {
72        match self {
73            Symbol::T(t) => format!("input {}", terminal_to_str_type(*t, symbol_table, ext)),
74            Symbol::NT(_) => format!("nonterminal {}", self.to_str(symbol_table)),
75            Symbol::Empty => "empty symbol".to_string(),
76            Symbol::End => "end of stream".to_string(),
77        }
78    }
79
80    /// Converts to symbols used in `sym!` and other related macros of the `lexigram` crate.
81    pub fn to_macro_item(&self) -> String {
82        match self {
83            Symbol::Empty => "e".to_string(),
84            Symbol::T(x) => format!("t {x}"),
85            Symbol::NT(x) => format!("nt {x}"),
86            Symbol::End => "end".to_string(),
87        }
88    }
89}
90
91/// Converts the terminal to string, using the symbol table if available to display the token name
92/// in case of variable token.
93pub fn terminal_to_str_type<T: SymInfoTable>(token: TokenId, symbol_table: Option<&T>, ext: &String) -> String {
94    let mut result = format!("{ext:?}");
95    if let Some(t) = symbol_table {
96        if t.is_token_data(token) {
97            result.push_str(&format!(" ({})", t.get_t_name(token)));
98        }
99    }
100    result
101}
102
103impl Display for Symbol {
104    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
105        match self {
106            Symbol::Empty => write!(f, "ε"),
107            Symbol::T(id) => write!(f, ":{id}"),
108            Symbol::NT(id) => write!(f, "{id}"),
109            Symbol::End => write!(f, "$"),
110        }
111    }
112}
113
114#[derive(Clone, Copy, PartialEq, Debug)]
115pub enum OpCode {
116    Empty,              // empty symbol
117    T(TokenId),         // terminal
118    NT(VarId),          // nonterminal
119    Loop(VarId),        // loop to same nonterminal
120    Exit(VarId),        // exit nonterminal
121    Hook,               // terminal hook callback
122    End,                // end of stream
123}
124
125
126impl Display for OpCode {
127    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
128        match self {
129            OpCode::Empty => write!(f, "ε"),
130            OpCode::T(t) => write!(f, ":{t}"),
131            OpCode::NT(v) => write!(f, "►{v}"),
132            OpCode::Loop(v) => write!(f, "●{v}"),
133            OpCode::Exit(v) => write!(f, "◄{v}"),
134            OpCode::Hook => write!(f, "▲"),
135            OpCode::End => write!(f, "$"),
136        }
137    }
138}
139
140impl OpCode {
141    pub fn is_loop(&self) -> bool {
142        matches!(self, OpCode::Loop(_))
143    }
144
145    pub fn is_empty(&self) -> bool {
146        matches!(self, OpCode::Empty)
147    }
148
149    pub fn has_span(&self) -> bool {
150        matches!(self, OpCode::T(_) | OpCode::NT(_))
151    }
152
153    pub fn matches(&self, s: Symbol) -> bool {
154        match self {
155            OpCode::Empty => s == Symbol::Empty,
156            OpCode::T(t) => s == Symbol::T(*t),
157            OpCode::NT(v) => s == Symbol::NT(*v),
158            OpCode::End => s == Symbol::End,
159            OpCode::Loop(_)
160            | OpCode::Exit(_)
161            | OpCode::Hook => false,
162        }
163    }
164
165    pub fn to_str<T: SymInfoTable>(&self, symbol_table: Option<&T>) -> String {
166        if let Some(t) = symbol_table {
167            match self {
168                OpCode::Empty => "ε".to_string(),
169                OpCode::T(v) => format!("{}{}", t.get_t_str(*v), if t.is_token_data(*v) { "!" } else { "" }),
170                OpCode::NT(v) => format!("►{}", t.get_nt_name(*v)),
171                OpCode::Loop(v) => format!("●{}", t.get_nt_name(*v)),
172                OpCode::Exit(f) => format!("◄{f}"),
173                OpCode::Hook => "▲".to_string(),
174                OpCode::End => "$".to_string(),
175            }
176        } else {
177            self.to_string()
178        }
179    }
180
181    pub fn to_str_name<T: SymInfoTable>(&self, symbol_table: Option<&T>) -> String {
182        if let Some(tbl) = symbol_table {
183            match self {
184                OpCode::T(v) => tbl.get_t_str(*v),
185                _ => self.to_str(symbol_table),
186            }
187        } else {
188            self.to_string()
189        }
190    }
191
192    pub fn to_str_quote<T: SymInfoTable>(&self, symbol_table: Option<&T>) -> String {
193        if let Some(t) = symbol_table {
194            match self {
195                OpCode::T(v) => format!("{}{}", Symbol::T(*v).to_str_quote(symbol_table), if t.is_token_data(*v) { "!" } else { "" }),
196                _ => self.to_str(symbol_table)
197            }
198        } else {
199            self.to_string()
200        }
201    }
202
203    pub fn to_str_ext<T: SymInfoTable>(&self, symbol_table: Option<&T>, ext: &String) -> String {
204        let mut result = self.to_str(symbol_table);
205        if let Some(t) = symbol_table {
206            if let OpCode::T(tok) = self {
207                if t.is_symbol_t_data(&Symbol::T(*tok)) {
208                    result.push_str(&format!("({ext})"));
209                }
210            }
211        }
212        result
213    }
214}
215
216impl From<Symbol> for OpCode {
217    fn from(value: Symbol) -> Self {
218        match value {
219            Symbol::Empty => OpCode::Empty,
220            Symbol::T(t) => OpCode::T(t),
221            Symbol::NT(v) => OpCode::NT(v),
222            Symbol::End => OpCode::End,
223        }
224    }
225}
226
227impl OpCode {
228    pub fn to_macro_item(&self) -> String {
229        match self {
230            OpCode::Empty => "e".to_string(),
231            OpCode::T(t) => format!("t {t}"),
232            OpCode::NT(v) => format!("nt {v}"),
233            OpCode::Loop(v) => format!("loop {v}"),
234            OpCode::Exit(v) => format!("exit {v}"),
235            OpCode::Hook => "hook".to_string(),
236            OpCode::End => "end".to_string(),
237        }
238    }
239}
240
241// ---------------------------------------------------------------------------------------------
242
243/// Codes returned by the [check_abort_request(...)](ListenerWrapper::check_abort_request) method of
244/// the listener (via the wrapper pass-through).
245#[derive(Clone, Copy, PartialEq, Debug)]
246pub enum Terminate {
247    /// Normal behaviour: continues parsing the text
248    None,
249    /// Irrecoverable error: stops parsing, calls the listener abort method, and returns an error
250    Abort,
251    /// Stops parsing, calls the listener exit method, and returns an Ok
252    Conclude,
253}
254
255/// Action calls to the wrapper with the method [ListenerWrapper::switch]. The wrapper translates the
256/// action accordingly to the current nonterminal and alternative; for example, by calling the
257/// appropriate listener callback.
258#[derive(PartialEq, Debug)]
259pub enum Call {
260    /// Enters a new nonterminal rule. The alternative is already known, but the values of the symbols
261    /// in that alternative haven't been scanned yet.
262    ///
263    /// This can be used to initialize the listener's variables when a particular rule is about to be
264    /// parsed (the listener methods associated with this action are normally optional since no
265    /// information is returned to the wrapper).
266    ///
267    /// The wrapper also uses this call to initialize stack items like accumulators used in rule loops
268    /// like `a -> b*`.
269    Enter,
270    /// Re-enters a loop nonterminal. This is currently not used in the wrapper.
271    Loop,
272    /// Exits an alternative, once all the symbols in it have been parsed: nonterminals and terminals.
273    ///
274    /// This is typically used to call an exit method of the listener and evaluate its value when it
275    /// has one.
276    Exit,
277    /// This action is used in two situations:
278    /// * when the parsing of the top rule has completed normally. In that case, the wrapper
279    ///   calls the [exit(...)] method of the listener (done in the generated code).
280    /// * when the parsing is [aborted](Terminate::Abort) or [concluded](Terminate::Conclude) in
281    ///   reaction to an [check_abort_request(...)](ListenerWrapper::check_abort_request) call. In
282    ///   that case, the wrapper calls the [abort(...)] method of the listener (done in the generated
283    ///   code).
284    ///
285    /// The [Terminate] value it contains tells the wrapper which of those eventualities has
286    /// occurred.
287    End(Terminate)
288}
289
290/// Result returned by [ListenerWrapper::push_nt_recovery_value].
291///
292/// * [Abort](RecoveryNt::Abort): stops using the wrapper/listener
293/// * [Skip](RecoveryNt::Skip): skips this nonterminal and tries to recover from a more global nonterminal
294/// * [Done](RecoveryNt::Done): recovery nonterminal has been pushed, parsing resumes normally
295#[derive(PartialEq, Debug)]
296pub enum RecoveryNt {
297    /// Aborts the wrapper/listener. Tries to recover the parser and continue to parse without calling the wrapper/listener any more.
298    Abort,
299    /// Skips the recovery at this level. Tries to recover from another nonterminal.
300    Skip,
301    /// The recovery nonterminal has been pushed. The parser can continue to parse the stream normally.
302    Done,
303}
304
305pub trait ListenerWrapper {
306    /// Calls the listener to execute Enter, Loop, Exit, and End actions.
307    #[allow(unused_variables)]
308    fn switch(&mut self, call: Call, nt: VarId, alt_id: AltId, t_data: Option<Vec<String>>) {}
309
310    /// Checks if the listener requests an abort (wrapper pass-through). This method is called at the end of
311    /// each parser iteration. If an error is too difficult to recover from, the listener can set a flag that
312    /// tells to return a [Terminate::Abort] on the next call, and implement this method to return
313    /// the appropriate status.
314    ///
315    /// In that case, the parser
316    /// * calls [abort(...)](ListenerWrapper::abort)
317    /// * calls [switch([Call::End]([Terminate::Abort]))](ListenerWrapper::switch) (if there was no syntax error)
318    /// * returns [ParserError::AbortRequest].
319    fn check_abort_request(&self) -> Terminate { Terminate::None }
320
321    /// Aborts the parsing.
322    fn abort(&mut self) {}
323
324    /// Gets access to the listener's log to report possible errors and information about the parsing.
325    fn get_log_mut(&mut self) -> &mut impl Logger;
326
327    /// Reports a message (note, info, warning, or error). The default behaviour adds the message to the log.
328    #[allow(unused_variables)]
329    fn report(&mut self, span_opt: Option<&PosSpan>, msg: LogMsg) {
330        self.get_log_mut().add(msg);
331    }
332
333    /// Checks that the stack is empty (the parser only checks that the stack is empty after successfully parsing a text)
334    fn is_stack_empty(&self) -> bool { true }
335
336    /// Checks that the stack_t is empty (the parser only checks that the stack is empty after successfully parsing a text)
337    fn is_stack_t_empty(&self) -> bool { true }
338
339    /// Checks that the stack_span is empty (the parser only checks that the stack is empty after successfully parsing a text)
340    fn is_stack_span_empty(&self) -> bool { true }
341
342    /// Allows to dynamically translate a token in the listener (wrapper pass-through)
343    #[allow(unused_variables)]
344    fn hook(&mut self, token: TokenId, text: &str, span: &PosSpan) -> TokenId {
345        token
346    }
347
348    /// Allows to intercept any token in the listener (wrapper pass-through)
349    #[allow(unused_variables)]
350    fn intercept_token(&mut self, token: TokenId, text: &str, span: &PosSpan) -> TokenId {
351        token
352    }
353
354    fn get_status(&self) -> Vec<String> { Vec::new() }
355
356    // Error recovery
357
358    /// Pushes a location span onto the (optional) span stack.
359    #[allow(unused_variables)]
360    fn push_span(&mut self, span: PosSpan) {}
361
362    fn pop_span(&mut self) -> PosSpan { PosSpan::empty() }
363    
364}
365
366// ---------------------------------------------------------------------------------------------
367
368pub type ParserToken = (TokenId, String, PosSpan);
369
370/// Code of the error that occurred during the parsing, returned by the
371/// [parse_stream(...)](LLParser::parse_stream) method of the parser.
372#[derive(PartialEq, Debug)]
373pub enum ParserError {
374    /// A syntax error was met. Either
375    /// * The next terminal of the parsed text doesn't match the expected one in the current rule
376    ///   alternative; for example, a rule `assign -> "let" Id "=" expr ";";` has just successfully
377    ///   scanned the terminal `"let"`, but the next one isn't `Id`.
378    /// * The next symbol doesn't correspond to any correct option for the next nonterminal (
379    ///   in other words, there is no entry in the parsing table for that combination). For example,
380    ///   in the same rule as above, the terminal `"="` has just been scanned successfully, but `expr`
381    ///   doesn't begin with the next one.
382    ///
383    /// This error is returned only when the parser doesn't try to recover from syntax errors; this
384    /// option is set with the [set_try_recover(...)](LLParser::set_try_recover) method and is
385    /// enabled by default.
386    ///
387    /// See also [ParserError::TooManyErrors].
388    SyntaxError,
389    /// Too many syntax errors were met, either
390    /// * during the parsing. The limit is set by the constant [LLParser::MAX_NBR_RECOVERS].
391    /// * by the lexer. The limit is set by the constant [LLParser::MAX_NBR_LEXER_ERRORS].
392    ///
393    /// This error is returned only when the parser tries to recover from syntactic or lexical errors;
394    /// this option is set with the [set_try_recover(...)](LLParser::set_try_recover) method and is
395    /// enabled by default.
396    ///
397    /// See also [ParserError::SyntaxError].
398    TooManyErrors,
399    /// The parser has reached an irrecoverable error, after trying to recover from a syntax error and
400    /// encountering the end of the text.
401    Irrecoverable,
402    /// The parser has reached the end of the top rule, but there are still terminals coming from
403    /// the lexer.
404    ///
405    /// Note that if the text is expected to contain something else after the part that must be parsed,
406    /// it is possible to tell the parser to conclude the parsing without looking any further. This
407    /// can be done in the listener with the [check_abort_request(...)] performed regularly by the
408    /// parser. See the [examples/terminate] parser to see how it can be used.
409    ExtraSymbol,
410    /// The parser has encountered the end of the text, but the top rule hasn't been fully parsed.
411    UnexpectedEOS,
412    /// This is an internal error that isn't supposed to happen.
413    UnexpectedError,
414    /// The text has been fully parsed, but syntax errors were encountered by the parser (and could
415    /// be recovered from).
416    ///
417    /// See also [ParserError::SyntaxError].
418    EncounteredErrors,
419    /// An [Abort](Terminate::Abort) was returned by the [check_abort_request(...)] method of the
420    /// listener.
421    AbortRequest,
422}
423
424impl Display for ParserError {
425    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
426        write!(f, "{}", match self {
427            ParserError::SyntaxError => "syntax error",
428            ParserError::TooManyErrors => "too many errors while trying to recover",
429            ParserError::Irrecoverable => "irrecoverable syntax error",
430            ParserError::ExtraSymbol => "extra symbol after end of parsing",
431            ParserError::UnexpectedEOS => "unexpected end of stream",
432            ParserError::UnexpectedError => "unexpected error",
433            ParserError::EncounteredErrors => "parsing failed due to previously encountered error(s)",
434            ParserError::AbortRequest => "abort request",
435        })
436    }
437}
438