1use 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
11pub 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 fn pop_nt_value(&mut self) {}
60
61 #[allow(unused_variables)]
72 fn push_nt_recovery_value(&mut self, nt: VarId, err_span: &PosSpan) -> RecoveryNt { RecoveryNt::Abort }
73
74 fn syntax_error_recovered(&mut self) {}
77}
78
79pub struct LRParser<'a, T> {
81 num_nt: usize, num_t_full: usize, action: &'a [LRAction],
84 goto: &'a [LRStateId],
85 alt_nt_len: &'a [(VarId, u16, u16)], symbol_table: FixedSymTable, init_hook: bool, 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 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 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 (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 let (nt, alt_len, nbr_t) = self.alt_nt_len[alt as usize]; stack_state.drain(stack_state.len() - alt_len as usize..); 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 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 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 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 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 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 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 err_span += stream_span;
414 *stream_span = span;
415 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 wrapper.report(Some(stream_span), LogMsg::Error(format!("lexical error: {s}")));
425 continue;
426 } else {
427 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}