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