1use 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
10pub 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, }
23
24impl<'a> LLParser<'a> {
25 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 pub fn get_symbol_table(&self) -> Option<&FixedSymTable> {
45 Some(&self.symbol_table)
46 }
47
48 pub fn set_start(&mut self, start: VarId) {
50 assert!(self.num_nt > start as usize);
51 self.start = start;
52 }
53
54 pub fn set_try_recover(&mut self, try_recover: bool) {
58 self.try_recover = try_recover;
59 }
60
61 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 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 const VERBOSE: bool = false;
112
113 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(); let mut stream_str = String::default(); let mut advance_stream = true;
135 let mut hook_active = false;
136 loop {
137 if advance_stream &&
138 (!DELAY_STREAM_INTERCEPTION || (!matches!(stack_sym, OpCode::Exit(_)) || stream_sym == Symbol::Empty)) {
142 stream_n += 1;
143 (stream_sym, stream_str) = stream.next().map(|(t, s, span)| {
144 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 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 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 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)); }
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 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}