Skip to main content

gallop/
lib.rs

1//! Gallop - General LL(1) parser
2//!
3//! # Example
4//!
5//! ```ignore
6//! let mut grammar: Grammar = BTreeMap::new();
7//!
8//! grammar.insert("START", vec![
9//!   vec![RuleElement::NonTerminal("a+")],
10//! ]);
11//!
12//! grammar.insert("a+", vec![
13//!   vec![RuleElement::Terminal('a'), RuleElement::NonTerminal("a*")],
14//! ]);
15//!
16//! grammar.insert("a*", vec![
17//!   vec![RuleElement::Terminal('a'), RuleElement::NonTerminal("a*")],
18//!   vec![RuleElement::Empty],
19//! ]);
20//!
21//! let mut parser = Parser::new(&mut grammar).unwrap();
22//!
23//! assert!(parser.parse("aaa").unwrap() == ParseTree::NonTerminal {
24//!     symbol:   "START",
25//!     children: vec![ParseTree::Terminal('a'), ParseTree::Terminal('a'), ParseTree::Terminal('a')],
26//! });
27//! ```
28//!
29//! # Tutorial
30//!
31//! We'll use the above code to explain how to use ``Gallop``, but we'll do this by stepping
32//! backwards from the bottom and work our way up...
33//!
34//! A sucessful parsing results in a ``ParseTree``, which has the following type:
35//!
36//! ```ignore
37//! pub enum ParseTree<'a> {
38//!   Terminal(char),
39//!   NonTerminal {
40//!     symbol: &'a str,
41//!     children: Vec<ParseTree<'a>>,
42//!   }
43//! }
44//! ```
45//!
46//! - ``ParseTree::Terminal`` represents a single captured Unicode scalar value from the input.
47//! - ``ParseTree::NonTerminal`` is a recursive data structure to represent the current part of the parse tree
48//!
49//! To parse an input string, use the ``parse()`` function from a ``Parser``:
50//!
51//! ```ignore
52//! assert!(parser.parse("aaa").unwrap() == ParseTree::NonTerminal {
53//!     symbol:   "START",
54//!     children: vec![ParseTree::Terminal('a'), ParseTree::Terminal('a'), ParseTree::Terminal('a')],
55//! });
56//! ```
57//!
58//! To create a ``Parser``, pass it a reference to a ``Grammar``:
59//!
60//! ```ignore
61//! let mut parser = Parser::new(&mut grammar).unwrap();
62//! ```
63//!
64//! A ``Grammar`` has the following type:
65//!
66//! ```ignore
67//! type Grammar<'a> = BTreeMap<NonTerminal<'a>, Vec<Rule<'a>>>;
68//! ```
69//!
70//! The bare ``NonTerminal<'a>`` represents the left-hand side of a production rule, whilst
71//! each element in ``Vec<Rule<'a>>`` contains the ``OR``-seperated right-hand side of a
72//! production rule i.e:
73//!
74//! ```ignore
75//! 1. a+ -> 'a' a*
76//! 2. a* -> 'a' a* | ε
77//! ```
78//!
79//! is broken down into:
80//!
81//! ```ignore
82//! 1. a+ -> 'a' a*
83//! 2. a* -> 'a' a*
84//! 3. a* -> ε
85//! ```
86//!
87//! and is represented in code by:
88//!
89//! ```ignore
90//! grammar.insert("a+", vec![
91//!   vec![RuleElement::Terminal('a'), RuleElement::NonTerminal("a*")],
92//! ]);
93//!
94//! grammar.insert("a*", vec![
95//!   vec![RuleElement::Terminal('a'), RuleElement::NonTerminal("a*")],
96//!   vec![RuleElement::Empty],
97//! ]);
98//!
99//! ```
100//!
101//! As you can see in that last snippet of code, ``Rule``s are ``Vec<RuleElement>``s,
102//! which there are three types:
103//!
104//!   1. ``RuleElement::Terminal(char)`` - a single Unicode scalar value to scan against
105//!   2. ``RuleElement::NonTerminal(&str)`` - an intermediary syntactic variable
106//!   3. ``RuleElement::Empty``- the empty string
107//!
108//! The last bit of code remaining is about the ``START`` symbol, explained in the
109//! following section.
110//!
111//! # Reserved Non-Terminals
112//!
113//! **The START Symbol**
114//!
115//! As ``Gallop`` is a top-down parser, it needs to know which of it's ``NonTerminal``s
116//! is the "start" symbol. To keep things consistent, ``Gallop`` requires this to be ``START``:
117//!
118//! ```ignore
119//! let mut grammar: Grammar = BTreeMap::new();
120//!
121//! grammar.insert("START", vec![
122//!   ...
123//! ]);
124//!
125//! ```
126//!
127//! **Convenience Non-Terminals**
128//!
129//! Instead of reinventing the wheel each time for commonly used tasks, there are a number of
130//! convenience non-terminals already predefined. These work just like every other non-terminal
131//! e.g:
132//!
133//! ```ignore
134//! let mut country_code: Grammar = BTreeMap::new();
135//!
136//! country_code.insert("START", vec![
137//!   vec!["two-ascii-characters"],
138//! ]);
139//!
140//! country_code.insert("two-ascii-characters", vec![
141//!   vec!["ASCII-UPPERCASE", "ASCII-UPPERCASE"],
142//! ]);
143//! ```
144//!
145//! Note: Using one of the following on the left-hand side of a ``Grammar`` rule results
146//! in a ``ReservedNonTerminal`` ``GrammarError``:
147//!
148//! - ``ALPHABETIC`` ((0x00..0x10FFF).map(|c as char| c.is_lowercase() || c.is_uppercase())
149//! - ``ALPHANUMERIC`` (``ALPHABETIC``, ``NUMERIC``)
150//! - ``ASCII`` (0x00..0x7F)
151//! - ``ASCII-ALPHABETIC`` (``ASCII-LOWERCASE``, ``ASCII-UPPERCASE``)
152//! - ``ASCII-ALPHANUMERIC`` (``ASCII-ALPHABETIC``, ``ASCII-DIGIT``)
153//! - ``ASCII-CONTROL`` (0x00..0x1F, 0x7F)
154//! - ``ASCII-DIGIT`` ('0'..'9')
155//! - ``ASCII-HEXDIGIT`` (``ASCII-DIGIT``, 'a'..'f', 'A'..'F')
156//! - ``ASCII-HEXDIGIT-LOWERCASE`` (``ASCII-DIGIT``, 'a'..'f')
157//! - ``ASCII-HEXDIGIT-UPPERCASE`` (``ASCII-DIGIT``, 'A'..'F')
158//! - ``ASCII-LOWERCASE`` ('a'..'z')
159//! - ``ASCII-UPPERCASE`` ('A'..'Z')
160//! - ``ASCII-WHITESPACE`` (0x0020, 0x0009, 0x000A, 0x000C, 0x000D)
161//! - ``CONTROL`` (0x00..0x10FFF).map(|c as char| c.is_control())
162//! - ``LOWERCASE`` (0x00..0x10FFF).map(|c as char| c.is_lowercase())
163//! - ``NUMERIC`` (0x00..0x10FFF).map(|c as char| c.is_numeric())
164//! - ``UPPERCASE`` (0x00..0x10FFF).map(|c as char| c.is_uppercase())
165//! - ``WHITESPACE`` (0x00..0x10FFF).map(|c as char| c.is_whitespace())
166//!
167//! # Rolling Up the Parse Tree
168//!
169//! When dealing with complex inputs, it's sometimes more digestible to break the grammar
170//! into lots of smaller, more composable non-terminals. The drawback in doing this
171//! though, is the resulting ``ParseTree`` can be really awkward to work with.
172//!
173//! In the following example, we'll try to parse a string containing one or more 'a'
174//! characters:
175//!
176//! ```ignore
177//! let mut grammar: Grammar = BTreeMap::new();
178//!
179//! grammar.insert("START", vec![
180//!   vec![
181//!     RuleElement::NonTerminal("one-or-more-a")
182//!   ],
183//! ]);
184//!
185//! grammar.insert("one-or-more-a", vec![
186//!   vec![
187//!     RuleElement::Terminal('a'),
188//!     RuleElement::NonTerminal("zero-or-more-a"),
189//!   ],
190//! ]);
191//!
192//! grammar.insert("zero-or-more-a", vec![
193//!   vec![
194//!     RuleElement::Terminal('a'),
195//!     RuleElement::NonTerminal("zero-or-more-a"),
196//!   ],
197//!   vec![
198//!     RuleElement::Empty,
199//!   ],
200//! ]);
201//!
202//! let mut parser = Parser::new(&mut grammar).unwrap();
203//!
204//! assert!(parser.parse("aaa").unwrap() == ParseTree::NonTerminal {
205//!     symbol:   "START",
206//!     children: vec![
207//!         ParseTree::NonTerminal {
208//!             symbol:   "one-or-more-a",
209//!             children: vec![
210//!                 ParseTree::Terminal('a'),
211//!                 ParseTree::NonTerminal {
212//!                     symbol:   "zero-or-more-a",
213//!                     children: vec![
214//!                         ParseTree::Terminal('a'),
215//!                         ParseTree::NonTerminal {
216//!                             symbol:   "zero-or-more-a",
217//!                             children: vec![
218//!                                 ParseTree::Terminal('a'),
219//!                                 ParseTree::NonTerminal {
220//!                                     symbol:   "zero-or-more-a",
221//!                                     children: vec![],
222//!                                 },
223//!                             ],
224//!                         },
225//!                     ],
226//!                 },
227//!             ],
228//!         },
229//!     ],
230//! });
231//!
232//! ```
233//!
234//! Yuk! And the problem gets worse as the number of 'a' characters increases within the input string.
235//! It would be nice if we could hide some of these intermediate non-terminals... this is
236//! what ``rollup()`` does:
237//!
238//!   - Specify the ``NonTerminal``s to you want to be rolled up
239//!   - When a rolled up non-terminal is found:
240//!     - It's childen are promoted to siblings
241//!     - The rolled up non-terminal is removed
242//!
243//! Here's the same example from above, but now we rollup ``one-or-more-a`` and ``zero-or-more-a``:
244//!
245//! ```ignore
246//! let mut grammar: Grammar = BTreeMap::new();
247//!
248//! grammar.insert("START", vec![
249//!   vec![
250//!     RuleElement::NonTerminal("one-or-more-a")
251//!   ],
252//! ]);
253//!
254//! grammar.insert("one-or-more-a", vec![
255//!   vec![
256//!     RuleElement::Terminal('a'),
257//!     RuleElement::NonTerminal("zero-or-more-a"),
258//!   ],
259//! ]);
260//!
261//! grammar.insert("zero-or-more-a", vec![
262//!   vec![
263//!     RuleElement::Terminal('a'),
264//!     RuleElement::NonTerminal("zero-or-more-a"),
265//!   ],
266//!   vec![
267//!     RuleElement::Empty,
268//!   ],
269//! ]);
270//!
271//! let mut parser = Parser::new(&mut grammar).unwrap();
272//!
273//! parser.rollup(vec![
274//!     "one-or-more-a",
275//!     "zero-or-more-a",
276//! ]);
277//!
278//! assert!(parser.parse("aaa").unwrap() == ParseTree::NonTerminal {
279//!     symbol:   "START",
280//!     children: vec![
281//!       ParseTree::Terminal('a'),
282//!       ParseTree::Terminal('a'),
283//!       ParseTree::Terminal('a'),
284//!     ],
285//! });
286//!
287//! ```
288//!
289//! Much nicer!
290//!
291//! **NOTE**: As a convenience, non-terminals ending with ``'*'`` and ``'+'`` are rolled up automatically:
292//!
293//! ```ignore
294//! let mut grammar: Grammar = BTreeMap::new();
295//!
296//! grammar.insert("START", vec![
297//!   vec![
298//!     RuleElement::NonTerminal("a+")
299//!   ],
300//! ]);
301//!
302//! grammar.insert("a+", vec![
303//!   vec![
304//!     RuleElement::Terminal('a'),
305//!     RuleElement::NonTerminal("a*"),
306//!   ],
307//! ]);
308//!
309//! grammar.insert("a*", vec![
310//!   vec![
311//!     RuleElement::Terminal('a'),
312//!     RuleElement::NonTerminal("a*"),
313//!   ],
314//!   vec![
315//!     RuleElement::Empty,
316//!   ],
317//! ]);
318//!
319//! let mut parser = Parser::new(&mut grammar).unwrap();
320//!
321//! assert!(parser.parse("aaa").unwrap() == ParseTree::NonTerminal {
322//!     symbol:   "START",
323//!     children: vec![
324//!       ParseTree::Terminal('a'),
325//!       ParseTree::Terminal('a'),
326//!       ParseTree::Terminal('a'),
327//!     ],
328//! });
329//! ```
330
331use std::char;
332use std::collections::BTreeMap;
333use std::collections::BTreeSet;
334use std::iter::Peekable;
335use std::str::Chars;
336
337//
338// Public grammar types
339//
340
341/// The left and right hand side of the production rules
342pub type Grammar<'a> = BTreeMap<NonTerminal<'a>, Vec<Rule<'a>>>;
343
344/// An intermediary syntactic variable
345pub type NonTerminal<'a> = &'a str;
346
347/// A single Unicode scalar value
348pub type Terminal = char;
349
350/// The right-hand side of a ``Grammar`` production rule
351pub type Rule<'a> = Vec<RuleElement<'a>>;
352
353/// Elements that make up each ``Rule``
354#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
355pub enum RuleElement<'a> {
356    /// The empty string
357    Empty,
358    /// An intermediary syntactic variable
359    NonTerminal(&'a str),
360    /// A single Unicode scalar value to scan against
361    Terminal(char),
362}
363
364/// Possible errors that could happen when creating a ``Parser``
365#[derive(Clone, Debug, PartialEq)]
366pub enum GrammarError<'a> {
367    /// The ``Grammar`` has no rules defined yet
368    EmptyGrammar,
369    /// The ``START`` ``Rule`` is not defined yet (see "Reserved Non-terminals" section)
370    NoStartSymbol,
371    /// The specified ``NonTerminal`` is actually reserved (see "Reserved Non-terminals" section)
372    ReservedNonTerminal(NonTerminal<'a>),
373    /// The specified ``NonTerminal`` is used within a ``Rule`` but is not defined yet
374    UndefinedNonTerminal(NonTerminal<'a>),
375    /// The ``Grammar`` is invalid, as specified by:
376    InvalidGrammar {
377        /// The offending ``NonTerminal``
378        non_terminal: NonTerminal<'a>,
379        /// The offending ``Rule``
380        rule: Rule<'a>,
381        /// The offending ``RuleElement``
382        rule_element: RuleElement<'a>,
383    },
384    /// The ``Grammar`` has a conflict, as specified by:
385    Conflict {
386        /// The offending ``NonTerminal``
387        non_terminal: NonTerminal<'a>,
388        /// The offending ``Rule``
389        rule: Rule<'a>,
390        /// The offending ``RuleElement``
391        rule_element: RuleElement<'a>,
392    },
393}
394
395//
396// Public parsing types
397//
398
399/// The results from a parsing of the input text
400#[derive(Clone, Debug, PartialEq)]
401pub enum ParseTree<'a> {
402    /// A single captured Unicode scalar value from the input
403    Terminal(char),
404    /// A recursive data structure to represent the current part of the parse tree
405    NonTerminal {
406        /// The name of the intermediary syntactic variable found
407        symbol: &'a str,
408        /// A recursive ``ParseTree`` that lives under the current non-terminal
409        children: Vec<ParseTree<'a>>,
410    },
411}
412
413/// Possible errors that could happen during parsing
414#[derive(Clone, Debug, PartialEq)]
415pub enum ParseError {
416    /// We expected more input
417    NoMoreInput,
418    /// The character at the specified index is not valid within the ``Grammar``
419    InvalidInput(u64),
420}
421
422/// Holds the state of the parser for the provided ``Grammar``
423#[derive(Clone, Debug, PartialEq)]
424pub struct Parser<'a> {
425    parse_table: ParseTable<'a>,
426    rollups: BTreeSet<&'a str>,
427}
428
429//
430// Public functions
431//
432
433impl<'a> Parser<'a> {
434    /// Creates a ``Parser`` from the provided ``Grammar``
435    ///
436    /// ```ignore
437    /// let parser = match Parser::new(&mut grammar) {
438    ///   Ok(p)    => p,
439    ///   Err(err) => panic!("Error: {:#?}", err),
440    /// };
441    /// ```
442    pub fn new(grammar: &'a mut Grammar) -> Result<Parser<'a>, GrammarError<'a>> {
443        match grammar.contains_key("START") {
444            false => Err(GrammarError::NoStartSymbol),
445            true => match grammar.len() > 1 {
446                false => Err(GrammarError::EmptyGrammar),
447                true => {
448                    let reserved_non_terminals = get_reserved_non_terminals();
449                    let mut reserved_non_terminals_used = BTreeSet::new();
450
451                    for (non_terminal, rules) in grammar.iter() {
452                        if reserved_non_terminals.contains_key(non_terminal) {
453                            return Err(GrammarError::ReservedNonTerminal(non_terminal));
454                        }
455
456                        for rule in rules {
457                            for rule_element in rule {
458                                match *rule_element {
459                                    RuleElement::Terminal(_) => {}
460                                    RuleElement::Empty => {}
461                                    RuleElement::NonTerminal(u) => {
462                                        if !grammar.contains_key(u) {
463                                            return Err(GrammarError::UndefinedNonTerminal(u));
464                                        }
465
466                                        if reserved_non_terminals.contains_key(u) {
467                                            reserved_non_terminals_used.insert(u);
468                                        }
469                                    }
470                                }
471                            }
472                        }
473                    }
474
475                    for reserved_non_terminal_used in reserved_non_terminals_used {
476                        grammar.insert(
477                            reserved_non_terminal_used,
478                            reserved_non_terminals
479                                .get(reserved_non_terminal_used)
480                                .unwrap()
481                                .clone(),
482                        );
483                    }
484
485                    let first_set = match get_first_set(grammar) {
486                        Ok(first_set) => first_set,
487                        Err(err) => return Err(err),
488                    };
489
490                    let follow_set = get_follow_set(grammar, &first_set);
491
492                    match get_parse_table(grammar, &first_set, &follow_set) {
493                        Err(err) => Err(err),
494                        Ok(parse_table) => Ok(Parser {
495                            parse_table,
496                            rollups: BTreeSet::new(),
497                        }),
498                    }
499                }
500            },
501        }
502    }
503
504    /// Parse the provided string
505    ///
506    /// ```ignore
507    /// println!("Parse tree: {:#?}", parser.parse("a test string"));
508    /// ```
509    pub fn parse(&mut self, input: &'a str) -> Result<ParseTree<'a>, ParseError> {
510        let mut parse_tree = ParseTree::NonTerminal {
511            symbol: "START",
512            children: vec![],
513        };
514
515        let mut input_stack = InputStack {
516            input: input.chars().peekable(),
517            index: 0,
518        };
519
520        match self._parse(&mut parse_tree, &mut input_stack) {
521            Some(err) => Err(err),
522            None => match input_stack.input.peek().is_some() {
523                true => Err(ParseError::InvalidInput(input_stack.index)),
524                false => Ok(parse_tree),
525            },
526        }
527    }
528
529    /// Specify any non-terminals that you want rolled up (see "Rolling Up the Parse Tree" section)
530    ///
531    /// ```ignore
532    /// parser.rollup(vec![
533    ///     "digit+",
534    ///     "digit*",
535    /// ]);
536    /// ```
537    pub fn rollup(&mut self, non_terminals: Vec<NonTerminal<'a>>) {
538        for i in non_terminals {
539            self.rollups.insert(i);
540        }
541    }
542
543    fn _parse(
544        &self,
545        parse_tree: &mut ParseTree<'a>,
546        input_stack: &mut InputStack<'a>,
547    ) -> Option<ParseError> {
548        //  if current node is non-terminal
549        //      get parse table entry
550        //
551        //      foreach rule element from parse table entry
552        //          if rule element is a terminal
553        //              add consumed input as a child node
554        //          else
555        //              add non-terminal rule element as a child node
556        //              recurse
557
558        match *parse_tree {
559            ParseTree::Terminal(_) => {
560                panic!("This should never happen")
561            }
562            ParseTree::NonTerminal {
563                symbol,
564                ref mut children,
565            } => {
566                let parse_table_entry = match input_stack.input.peek() {
567                    None => {
568                        match self
569                            .parse_table
570                            .get(symbol)
571                            .unwrap()
572                            .get(&ParseTableElement::Empty)
573                        {
574                            Some(empty) => empty,
575                            None => return Some(ParseError::NoMoreInput),
576                        }
577                    }
578                    Some(next_input) => match self
579                        .parse_table
580                        .get(symbol)
581                        .unwrap()
582                        .get(&ParseTableElement::Terminal(*next_input))
583                    {
584                        None => return Some(ParseError::InvalidInput(input_stack.index)),
585                        Some(rule) => rule,
586                    },
587                };
588
589                let current_children = children;
590
591                for rule_element in parse_table_entry {
592                    match *rule_element {
593                        RuleElement::Empty => {}
594                        RuleElement::Terminal(u) => match input_stack.input.next() {
595                            None => return Some(ParseError::NoMoreInput),
596                            Some(next_input) => {
597                                match u == next_input {
598                                    false => {
599                                        return Some(ParseError::InvalidInput(input_stack.index))
600                                    }
601                                    true => current_children.push(ParseTree::Terminal(next_input)),
602                                }
603
604                                input_stack.index += 1;
605                            }
606                        },
607                        RuleElement::NonTerminal(u) => {
608                            let mut child = ParseTree::NonTerminal {
609                                symbol: u,
610                                children: vec![],
611                            };
612
613                            match self._parse(&mut child, input_stack) {
614                                Some(error) => return Some(error),
615                                None => {
616                                    match self.rollups.contains(u)
617                                        || u.ends_with('*')
618                                        || u.ends_with('+')
619                                    {
620                                        false => current_children.push(child),
621                                        true => match child {
622                                            ParseTree::Terminal(_) => {}
623                                            ParseTree::NonTerminal {
624                                                ref mut children, ..
625                                            } => {
626                                                current_children.append(children);
627                                            }
628                                        },
629                                    }
630                                }
631                            }
632                        }
633                    }
634                }
635            }
636        }
637
638        None
639    }
640}
641
642//
643// Private parsing types
644//
645
646#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
647enum ParseTableElement {
648    Empty,
649    Terminal(char),
650}
651
652type ParseTable<'a> = BTreeMap<NonTerminal<'a>, BTreeMap<ParseTableElement, Rule<'a>>>;
653
654#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
655enum FirstElement {
656    Empty,
657    Terminal(char),
658}
659
660type FirstSet<'a> = BTreeMap<NonTerminal<'a>, BTreeSet<FirstElement>>;
661type FollowSet<'a> = BTreeMap<NonTerminal<'a>, BTreeSet<Terminal>>;
662
663struct InputStack<'a> {
664    input: Peekable<Chars<'a>>,
665    index: u64,
666}
667
668//
669// Private functions
670//
671
672fn get_first_set<'a>(grammar: &Grammar<'a>) -> Result<FirstSet<'a>, GrammarError<'a>> {
673    //  while no change
674    //      foreach rule A -> RHS
675    //          if RHS == {Empty}
676    //              FirstSet(A) += Empty
677    //              continue
678    //
679    //          while FirstSet(Ui) derives Empty
680    //              Replace Ui with U(i+1)
681    //              break to next rule if no more Ui
682    //
683    //          if Ui is a terminal
684    //              FirstSet(A) += terminal
685    //              break to next rule
686    //
687    //          FirstSet(A) += FirstSet(Ui)
688
689    let mut first_set: FirstSet = grammar
690        .keys()
691        .map(|&non_terminal| (non_terminal, BTreeSet::new()))
692        .collect();
693
694    loop {
695        let mut has_changed = false;
696
697        for (non_terminal, rules) in grammar {
698            if rules.is_empty() {
699                return Err(GrammarError::InvalidGrammar {
700                    non_terminal,
701                    rule: vec![],
702                    rule_element: RuleElement::Empty,
703                });
704            }
705
706            for rule in rules {
707                let mut has_empty = false;
708
709                for rule_element in rule {
710                    match *rule_element {
711                        RuleElement::Empty => has_empty = true,
712                        RuleElement::Terminal(u) => {
713                            if first_set
714                                .get_mut(non_terminal)
715                                .unwrap()
716                                .insert(FirstElement::Terminal(u))
717                            {
718                                has_changed = true;
719                            }
720
721                            break;
722                        }
723                        RuleElement::NonTerminal(u) => match u == *non_terminal {
724                            true => continue,
725                            false => {
726                                let mut first_rule_element_clone = match first_set.get(u) {
727                                    Some(first_rule_element) => first_rule_element.clone(),
728                                    None => {
729                                        return Err(GrammarError::InvalidGrammar {
730                                            non_terminal,
731                                            rule: rule.clone(),
732                                            rule_element: rule_element.clone(),
733                                        })
734                                    }
735                                };
736
737                                let first_non_terminal = first_set.get_mut(non_terminal).unwrap();
738                                let old_length = first_non_terminal.len();
739
740                                let has_empty =
741                                    first_rule_element_clone.remove(&FirstElement::Empty);
742                                first_non_terminal.extend(first_rule_element_clone);
743
744                                if old_length != first_non_terminal.len() {
745                                    has_changed = true;
746                                }
747
748                                match has_empty {
749                                    true => continue,
750                                    false => break,
751                                }
752                            }
753                        },
754                    }
755                }
756
757                match has_empty && (1 == rule.iter().len()) {
758                    false => continue,
759                    true => {
760                        let first_non_terminal = first_set.get_mut(non_terminal).unwrap();
761
762                        match first_non_terminal.contains(&FirstElement::Empty) {
763                            true => continue,
764                            false => {
765                                first_non_terminal.insert(FirstElement::Empty);
766                                has_changed = true;
767                            }
768                        }
769                    }
770                }
771            }
772        }
773
774        match has_changed {
775            true => continue,
776            false => break,
777        }
778    }
779
780    Ok(first_set)
781}
782
783fn get_follow_set<'a>(grammar: &Grammar<'a>, first_set: &FirstSet<'a>) -> FollowSet<'a> {
784    //  while no change
785    //      foreach rule where we have A => ...By...
786    //          FollowSet(B) += FirstSet(y)
787    //
788    //          if y derives or *is* Empty
789    //              FollowSet(B) += FollowSet(A)
790
791    let mut follow_set: FollowSet = grammar
792        .keys()
793        .map(|&non_terminal| (non_terminal, BTreeSet::new()))
794        .collect();
795
796    loop {
797        let mut has_changed = false;
798
799        for (non_terminal, rules) in grammar {
800            let follow_non_terminal = follow_set.get(non_terminal).unwrap().clone();
801
802            for rule in rules {
803                for (i, rule_element_b) in rule.iter().enumerate() {
804                    match *rule_element_b {
805                        RuleElement::Empty => {}
806                        RuleElement::Terminal(_) => {}
807                        RuleElement::NonTerminal(b) => {
808                            let follow_rule_element_b = follow_set.get_mut(&b).unwrap();
809                            let mut extend_from_empty = false;
810
811                            for rule_element_y in rule.iter().skip(i + 1) {
812                                match *rule_element_y {
813                                    RuleElement::Empty => {}
814                                    RuleElement::Terminal(y) => {
815                                        if follow_rule_element_b.insert(y) {
816                                            has_changed = true;
817                                        }
818
819                                        break;
820                                    }
821                                    RuleElement::NonTerminal(y) => {
822                                        let mut first_rule_element_y =
823                                            first_set.get(y).unwrap().clone();
824
825                                        let has_empty = first_rule_element_y
826                                            .remove(&FirstElement::Empty)
827                                            || first_rule_element_y.is_empty();
828
829                                        for first_y in first_rule_element_y {
830                                            match first_y {
831                                                FirstElement::Empty => {}
832                                                FirstElement::Terminal(fy) => {
833                                                    match follow_rule_element_b.insert(fy) {
834                                                        true => has_changed = true,
835                                                        false => continue,
836                                                    }
837                                                }
838                                            }
839                                        }
840
841                                        match has_empty {
842                                            true => extend_from_empty = true,
843                                            false => break,
844                                        }
845                                    }
846                                }
847                            }
848
849                            match extend_from_empty || (i + 1) == rule.iter().len() {
850                                true => follow_rule_element_b.extend(follow_non_terminal.clone()),
851                                false => continue,
852                            }
853                        }
854                    }
855                }
856            }
857        }
858
859        match has_changed {
860            true => continue,
861            false => break,
862        }
863    }
864
865    follow_set
866}
867
868fn get_parse_table<'a>(
869    grammar: &Grammar<'a>,
870    first_set: &FirstSet<'a>,
871    follow_set: &FollowSet<'a>,
872) -> Result<ParseTable<'a>, GrammarError<'a>> {
873    //  foreach rule A -> RHS
874    //      foreach terminal a in FirstSet(RHS)
875    //          [A, a] = RHS
876    //
877    //      if RHS is, or derives, Empty
878    //          foreach terminal a in FollowSet(A)
879    //              [A, a] = RHS
880
881    let mut parse_table: ParseTable = grammar
882        .keys()
883        .map(|&non_terminal| (non_terminal, BTreeMap::new()))
884        .collect();
885
886    for (non_terminal, rules) in grammar {
887        let parse_table_non_terminal = parse_table.get_mut(non_terminal).unwrap();
888        let follow_non_terminal = follow_set.get(non_terminal).unwrap();
889
890        for rule in rules {
891            let mut extend_from_empty = false;
892
893            for rule_element in rule {
894                match *rule_element {
895                    RuleElement::Empty => extend_from_empty = true,
896                    RuleElement::Terminal(u) => {
897                        match parse_table_non_terminal
898                            .insert(ParseTableElement::Terminal(u), rule.clone())
899                            .is_some()
900                        {
901                            false => break,
902                            true => {
903                                return Err(GrammarError::Conflict {
904                                    non_terminal,
905                                    rule: rule.clone(),
906                                    rule_element: rule_element.clone(),
907                                })
908                            }
909                        }
910                    }
911                    RuleElement::NonTerminal(u) => {
912                        let mut first_rule_element = first_set.get(u).unwrap().clone();
913                        let has_empty = first_rule_element.remove(&FirstElement::Empty);
914
915                        for first_u in first_rule_element {
916                            match first_u {
917                                FirstElement::Empty => {}
918                                FirstElement::Terminal(fu) => {
919                                    match parse_table_non_terminal
920                                        .insert(ParseTableElement::Terminal(fu), rule.clone())
921                                        .is_some()
922                                    {
923                                        false => continue,
924                                        true => {
925                                            return Err(GrammarError::Conflict {
926                                                non_terminal,
927                                                rule: rule.clone(),
928                                                rule_element: rule_element.clone(),
929                                            })
930                                        }
931                                    }
932                                }
933                            }
934                        }
935
936                        match has_empty {
937                            true => continue,
938                            false => break,
939                        }
940                    }
941                }
942            }
943
944            match extend_from_empty {
945                false => continue,
946                true => {
947                    for follow_u in follow_non_terminal {
948                        match parse_table_non_terminal
949                            .insert(ParseTableElement::Terminal(*follow_u), rule.clone())
950                            .is_some()
951                        {
952                            false => continue,
953                            true => {
954                                return Err(GrammarError::Conflict {
955                                    non_terminal,
956                                    rule: rule.clone(),
957                                    rule_element: RuleElement::Empty,
958                                })
959                            }
960                        }
961                    }
962                }
963            }
964
965            let first_non_terminal = first_set.get(non_terminal).unwrap();
966
967            if first_non_terminal.contains(&FirstElement::Empty) {
968                parse_table_non_terminal.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
969            }
970        }
971    }
972
973    Ok(parse_table)
974}
975
976fn get_reserved_non_terminals<'a>() -> BTreeMap<NonTerminal<'a>, Vec<Rule<'a>>> {
977    let mut reserved_non_terminals = BTreeMap::new();
978
979    reserved_non_terminals.insert("ASCII", get_reserved_ascii());
980    reserved_non_terminals.insert("ASCII-CONTROL", get_reserved_ascii_control());
981    reserved_non_terminals.insert("ASCII-WHITESPACE", get_reserved_ascii_whitespace());
982    reserved_non_terminals.insert("ASCII-DIGIT", get_reserved_ascii_digit());
983    reserved_non_terminals.insert("ASCII-LOWERCASE", get_reserved_ascii_lowercase());
984    reserved_non_terminals.insert("ASCII-UPPERCASE", get_reserved_ascii_uppercase());
985    reserved_non_terminals.insert("ASCII-ALPHABETIC", get_reserved_ascii_alphabetic());
986    reserved_non_terminals.insert("ASCII-ALPHANUMERIC", get_reserved_ascii_alphanumeric());
987    reserved_non_terminals.insert(
988        "ASCII-HEXDIGIT-LOWERCASE",
989        get_reserved_ascii_hexdigit_lowercase(),
990    );
991    reserved_non_terminals.insert(
992        "ASCII-HEXDIGIT-UPPERCASE",
993        get_reserved_ascii_hexdigit_uppercase(),
994    );
995    reserved_non_terminals.insert("ASCII-HEXDIGIT", get_reserved_ascii_hexdigit());
996    reserved_non_terminals.insert("CONTROL", get_reserved_control());
997    reserved_non_terminals.insert("WHITESPACE", get_reserved_whitespace());
998    reserved_non_terminals.insert("NUMERIC", get_reserved_numeric());
999    reserved_non_terminals.insert("LOWERCASE", get_reserved_lowercase());
1000    reserved_non_terminals.insert("UPPERCASE", get_reserved_uppercase());
1001    reserved_non_terminals.insert("ALPHABETIC", get_reserved_alphabetic());
1002    reserved_non_terminals.insert("ALPHANUMERIC", get_reserved_alphanumeric());
1003
1004    reserved_non_terminals
1005}
1006
1007fn get_reserved_ascii<'a>() -> Vec<Vec<RuleElement<'a>>> {
1008    (0x0..(0x7f + 1u8))
1009        .into_iter()
1010        .map(|c| vec![RuleElement::Terminal(c as char)])
1011        .collect()
1012}
1013
1014fn get_reserved_ascii_control<'a>() -> Vec<Vec<RuleElement<'a>>> {
1015    let mut characters: Vec<Vec<RuleElement<'a>>> = (0x0..(0x1f + 1u8))
1016        .into_iter()
1017        .map(|c| vec![RuleElement::Terminal(c as char)])
1018        .collect();
1019
1020    characters.push(vec![RuleElement::Terminal(0x7f as char)]);
1021
1022    characters
1023}
1024
1025fn get_reserved_ascii_whitespace<'a>() -> Vec<Vec<RuleElement<'a>>> {
1026    ['\u{0020}', '\u{0009}', '\u{000a}', '\u{000c}', '\u{000d}']
1027        .iter()
1028        .map(|c| vec![RuleElement::Terminal(*c)])
1029        .collect()
1030}
1031
1032fn get_reserved_ascii_digit<'a>() -> Vec<Vec<RuleElement<'a>>> {
1033    (b'0'..(b'9' + 1u8))
1034        .into_iter()
1035        .map(|c| vec![RuleElement::Terminal(c as char)])
1036        .collect()
1037}
1038
1039fn get_reserved_ascii_lowercase<'a>() -> Vec<Vec<RuleElement<'a>>> {
1040    (b'a'..(b'z' + 1u8))
1041        .into_iter()
1042        .map(|c| vec![RuleElement::Terminal(c as char)])
1043        .collect()
1044}
1045
1046fn get_reserved_ascii_uppercase<'a>() -> Vec<Vec<RuleElement<'a>>> {
1047    (b'A'..(b'Z' + 1u8))
1048        .into_iter()
1049        .map(|c| vec![RuleElement::Terminal(c as char)])
1050        .collect()
1051}
1052
1053fn get_reserved_ascii_alphabetic<'a>() -> Vec<Vec<RuleElement<'a>>> {
1054    let mut characters = vec![];
1055
1056    characters.append(&mut get_reserved_ascii_lowercase().clone());
1057    characters.append(&mut get_reserved_ascii_uppercase().clone());
1058
1059    characters
1060}
1061
1062fn get_reserved_ascii_alphanumeric<'a>() -> Vec<Vec<RuleElement<'a>>> {
1063    let mut characters: Vec<Vec<RuleElement>> = Vec::new();
1064
1065    characters.append(&mut get_reserved_ascii_alphabetic().clone());
1066    characters.append(&mut get_reserved_ascii_digit().clone());
1067
1068    characters
1069}
1070
1071fn get_reserved_ascii_hexdigit_lowercase<'a>() -> Vec<Vec<RuleElement<'a>>> {
1072    let mut characters: Vec<Vec<RuleElement<'a>>> = (b'a'..(b'f' + 1u8))
1073        .into_iter()
1074        .map(|c| vec![RuleElement::Terminal(c as char)])
1075        .collect();
1076
1077    characters.append(&mut get_reserved_ascii_digit().clone());
1078
1079    characters
1080}
1081
1082fn get_reserved_ascii_hexdigit_uppercase<'a>() -> Vec<Vec<RuleElement<'a>>> {
1083    let mut characters: Vec<Vec<RuleElement<'a>>> = (b'A'..(b'F' + 1u8))
1084        .into_iter()
1085        .map(|c| vec![RuleElement::Terminal(c as char)])
1086        .collect();
1087
1088    characters.append(&mut get_reserved_ascii_digit().clone());
1089
1090    characters
1091}
1092
1093fn get_reserved_ascii_hexdigit<'a>() -> Vec<Vec<RuleElement<'a>>> {
1094    let mut characters: Vec<Vec<RuleElement>> = Vec::new();
1095
1096    characters.append(&mut get_reserved_ascii_digit().clone());
1097
1098    characters.append(
1099        &mut (b'a'..(b'f' + 1u8))
1100            .into_iter()
1101            .map(|c| vec![RuleElement::Terminal(c as char)])
1102            .collect(),
1103    );
1104
1105    characters.append(
1106        &mut (b'A'..(b'F' + 1u8))
1107            .into_iter()
1108            .map(|c| vec![RuleElement::Terminal(c as char)])
1109            .collect(),
1110    );
1111
1112    characters
1113}
1114
1115fn get_reserved_control<'a>() -> Vec<Vec<RuleElement<'a>>> {
1116    (0x0..(0x10FFFF + 1))
1117        .into_iter()
1118        .filter_map(char::from_u32)
1119        .filter(|c| (*c).is_control())
1120        .map(|c| vec![RuleElement::Terminal(c as char)])
1121        .collect()
1122}
1123
1124fn get_reserved_whitespace<'a>() -> Vec<Vec<RuleElement<'a>>> {
1125    (0x0..(0x10FFFF + 1))
1126        .into_iter()
1127        .filter_map(char::from_u32)
1128        .filter(|c| (*c).is_whitespace())
1129        .map(|c| vec![RuleElement::Terminal(c as char)])
1130        .collect()
1131}
1132
1133fn get_reserved_numeric<'a>() -> Vec<Vec<RuleElement<'a>>> {
1134    (0x0..(0x10FFFF + 1))
1135        .into_iter()
1136        .filter_map(char::from_u32)
1137        .filter(|c| (*c).is_numeric())
1138        .map(|c| vec![RuleElement::Terminal(c as char)])
1139        .collect()
1140}
1141
1142fn get_reserved_lowercase<'a>() -> Vec<Vec<RuleElement<'a>>> {
1143    (0x0..(0x10FFFF + 1))
1144        .into_iter()
1145        .filter_map(char::from_u32)
1146        .filter(|c| (*c).is_lowercase())
1147        .map(|c| vec![RuleElement::Terminal(c as char)])
1148        .collect()
1149}
1150
1151fn get_reserved_uppercase<'a>() -> Vec<Vec<RuleElement<'a>>> {
1152    (0x0..(0x10FFFF + 1))
1153        .into_iter()
1154        .filter_map(char::from_u32)
1155        .filter(|c| (*c).is_uppercase())
1156        .map(|c| vec![RuleElement::Terminal(c as char)])
1157        .collect()
1158}
1159
1160fn get_reserved_alphabetic<'a>() -> Vec<Vec<RuleElement<'a>>> {
1161    let mut characters: Vec<Vec<RuleElement>> = Vec::new();
1162
1163    characters.append(&mut get_reserved_lowercase().clone());
1164    characters.append(&mut get_reserved_uppercase().clone());
1165
1166    characters
1167}
1168
1169fn get_reserved_alphanumeric<'a>() -> Vec<Vec<RuleElement<'a>>> {
1170    let mut characters: Vec<Vec<RuleElement>> = Vec::new();
1171
1172    characters.append(&mut get_reserved_alphabetic().clone());
1173    characters.append(&mut get_reserved_numeric().clone());
1174
1175    characters
1176}
1177
1178#[cfg(test)]
1179mod new {
1180    use super::*;
1181
1182    #[test]
1183    fn no_start_symbol() {
1184        let mut grammar = Grammar::new();
1185
1186        match Parser::new(&mut grammar) {
1187            Ok(_) => panic!(),
1188            Err(err) => assert!(err == GrammarError::NoStartSymbol),
1189        }
1190    }
1191
1192    #[test]
1193    fn empty_grammar() {
1194        let mut grammar = Grammar::new();
1195        grammar.insert("START", vec![]);
1196
1197        match Parser::new(&mut grammar) {
1198            Err(err) => assert!(err == GrammarError::EmptyGrammar),
1199            Ok(_) => panic!(),
1200        }
1201    }
1202
1203    #[test]
1204    fn bad_parse_table() {
1205        let mut grammar = Grammar::new();
1206
1207        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1208
1209        grammar.insert(
1210            "A",
1211            vec![
1212                vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')],
1213                vec![RuleElement::Terminal('a'), RuleElement::Terminal('c')],
1214            ],
1215        );
1216
1217        match Parser::new(&mut grammar) {
1218            Ok(_) => panic!(),
1219            Err(err) => assert!(
1220                err == GrammarError::Conflict {
1221                    non_terminal: "A",
1222                    rule: vec![RuleElement::Terminal('a'), RuleElement::Terminal('c')],
1223                    rule_element: RuleElement::Terminal('a'),
1224                }
1225            ),
1226        }
1227    }
1228
1229    #[test]
1230    fn ok() {
1231        let mut grammar = Grammar::new();
1232
1233        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1234
1235        grammar.insert(
1236            "A",
1237            vec![vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')]],
1238        );
1239
1240        match Parser::new(&mut grammar) {
1241            Err(_) => panic!(),
1242            Ok(parser) => {
1243                let mut start_rules = BTreeMap::new();
1244                start_rules.insert(
1245                    ParseTableElement::Terminal('a'),
1246                    vec![RuleElement::NonTerminal("A")],
1247                );
1248
1249                let mut a_rules = BTreeMap::new();
1250                a_rules.insert(
1251                    ParseTableElement::Terminal('a'),
1252                    vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')],
1253                );
1254
1255                let mut expected_parse_table = BTreeMap::new();
1256                expected_parse_table.insert("START", start_rules);
1257                expected_parse_table.insert("A", a_rules);
1258
1259                assert!(
1260                    parser
1261                        == Parser {
1262                            parse_table: expected_parse_table,
1263                            rollups: BTreeSet::new(),
1264                        }
1265                );
1266            }
1267        }
1268    }
1269}
1270
1271#[cfg(test)]
1272mod parse {
1273    use super::*;
1274
1275    #[test]
1276    fn no_more_input() {
1277        let mut grammar = Grammar::new();
1278
1279        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1280
1281        grammar.insert(
1282            "A",
1283            vec![vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')]],
1284        );
1285
1286        let mut parser = Parser::new(&mut grammar).unwrap();
1287
1288        match parser.parse("") {
1289            Ok(_) => panic!(),
1290            Err(err) => assert!(err == ParseError::NoMoreInput),
1291        }
1292    }
1293
1294    #[test]
1295    fn invalid_input() {
1296        let mut grammar = Grammar::new();
1297
1298        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1299
1300        grammar.insert(
1301            "A",
1302            vec![vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')]],
1303        );
1304
1305        let mut parser = Parser::new(&mut grammar).unwrap();
1306
1307        match parser.parse("abb") {
1308            Ok(_) => panic!(),
1309            Err(err) => assert!(err == ParseError::InvalidInput(2)),
1310        }
1311    }
1312
1313    #[test]
1314    fn ok() {
1315        let mut grammar = Grammar::new();
1316
1317        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1318
1319        grammar.insert(
1320            "A",
1321            vec![vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')]],
1322        );
1323
1324        let mut parser = Parser::new(&mut grammar).unwrap();
1325
1326        match parser.parse("ab") {
1327            Err(_) => panic!(),
1328            Ok(parse_tree) => assert!(
1329                parse_tree
1330                    == ParseTree::NonTerminal {
1331                        symbol: "START",
1332                        children: vec![ParseTree::NonTerminal {
1333                            symbol: "A",
1334                            children: vec![ParseTree::Terminal('a'), ParseTree::Terminal('b'),],
1335                        },],
1336                    }
1337            ),
1338        }
1339    }
1340}
1341
1342#[cfg(test)]
1343mod _parse {
1344    use super::*;
1345
1346    #[test]
1347    #[should_panic]
1348    fn panic_on_terminal() {
1349        // in reality, this should never happen as we only ever enter _parse() on non-terminals
1350
1351        let mut start_rules = BTreeMap::new();
1352        start_rules.insert(
1353            ParseTableElement::Terminal('a'),
1354            vec![RuleElement::Terminal('b')],
1355        );
1356
1357        let mut parse_table = BTreeMap::new();
1358        parse_table.insert("START", start_rules);
1359
1360        let parser = Parser {
1361            parse_table: parse_table,
1362            rollups: BTreeSet::new(),
1363        };
1364
1365        let mut parse_tree = ParseTree::Terminal('a');
1366        let mut input_stack = InputStack {
1367            input: "a".chars().peekable(),
1368            index: 0,
1369        };
1370
1371        match parser._parse(&mut parse_tree, &mut input_stack) {
1372            _ => {}
1373        }
1374    }
1375
1376    #[test]
1377    fn no_input() {
1378        let mut grammar = Grammar::new();
1379
1380        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1381
1382        grammar.insert(
1383            "A",
1384            vec![vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')]],
1385        );
1386
1387        let mut parser = Parser::new(&mut grammar).unwrap();
1388
1389        match parser.parse("") {
1390            Ok(_) => panic!(),
1391            Err(err) => assert!(err == ParseError::NoMoreInput),
1392        }
1393    }
1394
1395    #[test]
1396    fn invalid_input() {
1397        let mut grammar = Grammar::new();
1398
1399        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1400
1401        grammar.insert(
1402            "A",
1403            vec![vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')]],
1404        );
1405
1406        let mut parser = Parser::new(&mut grammar).unwrap();
1407
1408        match parser.parse("c") {
1409            Ok(_) => panic!(),
1410            Err(err) => assert!(err == ParseError::InvalidInput(0)),
1411        }
1412    }
1413
1414    #[test]
1415    fn no_more_input() {
1416        let mut grammar = Grammar::new();
1417
1418        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1419
1420        grammar.insert(
1421            "A",
1422            vec![vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')]],
1423        );
1424
1425        let mut parser = Parser::new(&mut grammar).unwrap();
1426
1427        match parser.parse("a") {
1428            Ok(_) => panic!(),
1429            Err(err) => assert!(err == ParseError::NoMoreInput),
1430        }
1431    }
1432
1433    #[test]
1434    fn invalid_wrong_terminal() {
1435        let mut grammar = Grammar::new();
1436
1437        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1438
1439        grammar.insert(
1440            "A",
1441            vec![vec![
1442                RuleElement::Terminal('a'),
1443                RuleElement::Terminal('b'),
1444                RuleElement::Terminal('c'),
1445            ]],
1446        );
1447
1448        let mut parser = Parser::new(&mut grammar).unwrap();
1449
1450        match parser.parse("abd") {
1451            Ok(_) => panic!(),
1452            Err(err) => assert!(err == ParseError::InvalidInput(2)),
1453        }
1454    }
1455
1456    #[test]
1457    fn invalid_wrong_terminal_recursed() {
1458        let mut grammar = Grammar::new();
1459
1460        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1461
1462        grammar.insert(
1463            "A",
1464            vec![vec![
1465                RuleElement::Terminal('a'),
1466                RuleElement::NonTerminal("B"),
1467                RuleElement::Terminal('c'),
1468            ]],
1469        );
1470
1471        grammar.insert(
1472            "B",
1473            vec![vec![RuleElement::Terminal('d'), RuleElement::Terminal('e')]],
1474        );
1475
1476        let mut parser = Parser::new(&mut grammar).unwrap();
1477
1478        match parser.parse("adfc") {
1479            Ok(_) => panic!(),
1480            Err(err) => assert!(err == ParseError::InvalidInput(2)),
1481        }
1482    }
1483
1484    #[test]
1485    fn ok() {
1486        let mut grammar = Grammar::new();
1487
1488        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1489
1490        grammar.insert(
1491            "A",
1492            vec![vec![
1493                RuleElement::Terminal('a'),
1494                RuleElement::NonTerminal("B"),
1495                RuleElement::Terminal('c'),
1496            ]],
1497        );
1498
1499        grammar.insert(
1500            "B",
1501            vec![vec![RuleElement::Terminal('d'), RuleElement::Terminal('e')]],
1502        );
1503
1504        let mut parser = Parser::new(&mut grammar).unwrap();
1505
1506        match parser.parse("adec") {
1507            Err(_) => panic!(),
1508            Ok(parse_tree) => assert!(
1509                parse_tree
1510                    == ParseTree::NonTerminal {
1511                        symbol: "START",
1512                        children: vec![ParseTree::NonTerminal {
1513                            symbol: "A",
1514                            children: vec![
1515                                ParseTree::Terminal('a'),
1516                                ParseTree::NonTerminal {
1517                                    symbol: "B",
1518                                    children: vec![
1519                                        ParseTree::Terminal('d'),
1520                                        ParseTree::Terminal('e'),
1521                                    ],
1522                                },
1523                                ParseTree::Terminal('c'),
1524                            ],
1525                        },],
1526                    }
1527            ),
1528        }
1529    }
1530}
1531
1532#[cfg(test)]
1533mod get_first_set {
1534    use super::*;
1535
1536    #[test]
1537    fn is_empty() {
1538        let mut grammar = Grammar::new();
1539
1540        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1541
1542        grammar.insert("A", vec![]);
1543
1544        match get_first_set(&grammar) {
1545            Ok(_) => panic!(),
1546            Err(err) => assert!(
1547                err == GrammarError::InvalidGrammar {
1548                    non_terminal: "A",
1549                    rule: vec![],
1550                    rule_element: RuleElement::Empty,
1551                }
1552            ),
1553        }
1554    }
1555
1556    #[test]
1557    fn matching_non_terminal() {
1558        let mut grammar = Grammar::new();
1559
1560        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1561
1562        grammar.insert("A", vec![vec![RuleElement::NonTerminal("A")]]);
1563
1564        match get_first_set(&grammar) {
1565            Err(_) => panic!(),
1566            Ok(first_set) => {
1567                let mut expected_first_set = BTreeMap::new();
1568
1569                expected_first_set.insert("START", BTreeSet::new());
1570                expected_first_set.insert("A", BTreeSet::new());
1571
1572                assert!(first_set == expected_first_set);
1573            }
1574        }
1575    }
1576
1577    #[test]
1578    fn invalid_grammar() {
1579        let mut grammar = Grammar::new();
1580
1581        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1582
1583        grammar.insert("A", vec![vec![RuleElement::NonTerminal("B")]]);
1584
1585        match get_first_set(&grammar) {
1586            Ok(_) => panic!(),
1587            Err(err) => assert!(
1588                err == GrammarError::InvalidGrammar {
1589                    non_terminal: "A",
1590                    rule: vec![RuleElement::NonTerminal("B")],
1591                    rule_element: RuleElement::NonTerminal("B"),
1592                }
1593            ),
1594        }
1595    }
1596
1597    #[test]
1598    fn combo_e() {
1599        let mut grammar = Grammar::new();
1600
1601        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1602
1603        grammar.insert("A", vec![vec![RuleElement::Empty]]);
1604
1605        match get_first_set(&grammar) {
1606            Err(_) => panic!(),
1607            Ok(first_set) => {
1608                let mut expected_first_set: FirstSet = BTreeMap::new();
1609
1610                let mut a_first = BTreeSet::new();
1611                a_first.insert(FirstElement::Empty);
1612
1613                expected_first_set.insert("START", BTreeSet::new());
1614                expected_first_set.insert("A", a_first);
1615
1616                assert!(first_set == expected_first_set);
1617            }
1618        }
1619    }
1620
1621    #[test]
1622    fn combo_t() {
1623        let mut grammar = Grammar::new();
1624
1625        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1626
1627        grammar.insert("A", vec![vec![RuleElement::Terminal('a')]]);
1628
1629        match get_first_set(&grammar) {
1630            Err(_) => panic!(),
1631            Ok(first_set) => {
1632                let mut expected_first_set = BTreeMap::new();
1633
1634                let mut start_first = BTreeSet::new();
1635                start_first.insert(FirstElement::Terminal('a'));
1636
1637                let mut a_first = BTreeSet::new();
1638                a_first.insert(FirstElement::Terminal('a'));
1639
1640                expected_first_set.insert("START", start_first);
1641                expected_first_set.insert("A", a_first);
1642
1643                assert!(first_set == expected_first_set);
1644            }
1645        }
1646    }
1647
1648    #[test]
1649    fn combo_et() {
1650        let mut grammar = Grammar::new();
1651
1652        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1653
1654        grammar.insert(
1655            "A",
1656            vec![vec![RuleElement::Empty, RuleElement::Terminal('b')]],
1657        );
1658
1659        match get_first_set(&grammar) {
1660            Err(_) => panic!(),
1661            Ok(first_set) => {
1662                let mut expected_first_set = BTreeMap::new();
1663
1664                let mut start_first = BTreeSet::new();
1665                start_first.insert(FirstElement::Terminal('b'));
1666
1667                let mut a_first = BTreeSet::new();
1668                a_first.insert(FirstElement::Terminal('b'));
1669
1670                expected_first_set.insert("START", start_first);
1671                expected_first_set.insert("A", a_first);
1672
1673                assert!(first_set == expected_first_set);
1674            }
1675        }
1676    }
1677
1678    #[test]
1679    fn combo_ene() {
1680        let mut grammar = Grammar::new();
1681
1682        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1683
1684        grammar.insert(
1685            "A",
1686            vec![vec![RuleElement::Empty, RuleElement::NonTerminal("B")]],
1687        );
1688
1689        grammar.insert("B", vec![vec![RuleElement::Empty]]);
1690
1691        match get_first_set(&grammar) {
1692            Err(_) => panic!(),
1693            Ok(first_set) => {
1694                let mut expected_first_set = BTreeMap::new();
1695
1696                let mut b_first = BTreeSet::new();
1697                b_first.insert(FirstElement::Empty);
1698
1699                expected_first_set.insert("START", BTreeSet::new());
1700                expected_first_set.insert("A", BTreeSet::new());
1701                expected_first_set.insert("B", b_first);
1702
1703                assert!(first_set == expected_first_set);
1704            }
1705        }
1706    }
1707
1708    #[test]
1709    fn combo_ent() {
1710        let mut grammar = Grammar::new();
1711
1712        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1713
1714        grammar.insert(
1715            "A",
1716            vec![vec![RuleElement::Empty, RuleElement::NonTerminal("B")]],
1717        );
1718
1719        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);
1720
1721        match get_first_set(&grammar) {
1722            Err(_) => panic!(),
1723            Ok(first_set) => {
1724                let mut expected_first_set = BTreeMap::new();
1725
1726                let mut start_first = BTreeSet::new();
1727                start_first.insert(FirstElement::Terminal('c'));
1728
1729                let mut a_first = BTreeSet::new();
1730                a_first.insert(FirstElement::Terminal('c'));
1731
1732                let mut b_first = BTreeSet::new();
1733                b_first.insert(FirstElement::Terminal('c'));
1734
1735                expected_first_set.insert("START", start_first);
1736                expected_first_set.insert("A", a_first);
1737                expected_first_set.insert("B", b_first);
1738
1739                assert!(first_set == expected_first_set);
1740            }
1741        }
1742    }
1743
1744    #[test]
1745    fn combo_te() {
1746        let mut grammar = Grammar::new();
1747
1748        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1749
1750        grammar.insert(
1751            "A",
1752            vec![vec![RuleElement::Terminal('a'), RuleElement::Empty]],
1753        );
1754
1755        match get_first_set(&grammar) {
1756            Err(_) => panic!(),
1757            Ok(first_set) => {
1758                let mut expected_first_set = BTreeMap::new();
1759
1760                let mut start_first = BTreeSet::new();
1761                start_first.insert(FirstElement::Terminal('a'));
1762
1763                let mut a_first = BTreeSet::new();
1764                a_first.insert(FirstElement::Terminal('a'));
1765
1766                expected_first_set.insert("START", start_first);
1767                expected_first_set.insert("A", a_first);
1768
1769                assert!(first_set == expected_first_set);
1770            }
1771        }
1772    }
1773
1774    #[test]
1775    fn combo_tt() {
1776        let mut grammar = Grammar::new();
1777
1778        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1779
1780        grammar.insert(
1781            "A",
1782            vec![vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')]],
1783        );
1784
1785        match get_first_set(&grammar) {
1786            Err(_) => panic!(),
1787            Ok(first_set) => {
1788                let mut expected_first_set = BTreeMap::new();
1789
1790                let mut start_first = BTreeSet::new();
1791                start_first.insert(FirstElement::Terminal('a'));
1792
1793                let mut a_first = BTreeSet::new();
1794                a_first.insert(FirstElement::Terminal('a'));
1795
1796                expected_first_set.insert("START", start_first);
1797                expected_first_set.insert("A", a_first);
1798
1799                assert!(first_set == expected_first_set);
1800            }
1801        }
1802    }
1803
1804    #[test]
1805    fn combo_tn() {
1806        let mut grammar = Grammar::new();
1807
1808        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1809
1810        grammar.insert(
1811            "A",
1812            vec![vec![
1813                RuleElement::Terminal('a'),
1814                RuleElement::NonTerminal("B"),
1815            ]],
1816        );
1817
1818        grammar.insert("B", vec![vec![]]);
1819
1820        match get_first_set(&grammar) {
1821            Err(_) => panic!(),
1822            Ok(first_set) => {
1823                let mut expected_first_set = BTreeMap::new();
1824
1825                let mut start_first = BTreeSet::new();
1826                start_first.insert(FirstElement::Terminal('a'));
1827
1828                let mut a_first = BTreeSet::new();
1829                a_first.insert(FirstElement::Terminal('a'));
1830
1831                expected_first_set.insert("START", start_first);
1832                expected_first_set.insert("A", a_first);
1833                expected_first_set.insert("B", BTreeSet::new());
1834
1835                assert!(first_set == expected_first_set);
1836            }
1837        }
1838    }
1839
1840    #[test]
1841    fn combo_tne() {
1842        let mut grammar = Grammar::new();
1843
1844        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1845
1846        grammar.insert(
1847            "A",
1848            vec![vec![
1849                RuleElement::Terminal('a'),
1850                RuleElement::NonTerminal("B"),
1851            ]],
1852        );
1853
1854        grammar.insert("B", vec![vec![RuleElement::Empty]]);
1855
1856        match get_first_set(&grammar) {
1857            Err(_) => panic!(),
1858            Ok(first_set) => {
1859                let mut expected_first_set = BTreeMap::new();
1860
1861                let mut start_first = BTreeSet::new();
1862                start_first.insert(FirstElement::Terminal('a'));
1863
1864                let mut a_first = BTreeSet::new();
1865                a_first.insert(FirstElement::Terminal('a'));
1866
1867                let mut b_first = BTreeSet::new();
1868                b_first.insert(FirstElement::Empty);
1869
1870                expected_first_set.insert("START", start_first);
1871                expected_first_set.insert("A", a_first);
1872                expected_first_set.insert("B", b_first);
1873
1874                assert!(first_set == expected_first_set);
1875            }
1876        }
1877    }
1878
1879    #[test]
1880    fn combo_tnt() {
1881        let mut grammar = Grammar::new();
1882
1883        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1884
1885        grammar.insert(
1886            "A",
1887            vec![vec![
1888                RuleElement::Terminal('a'),
1889                RuleElement::NonTerminal("B"),
1890            ]],
1891        );
1892
1893        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);
1894
1895        match get_first_set(&grammar) {
1896            Err(_) => panic!(),
1897            Ok(first_set) => {
1898                let mut expected_first_set = BTreeMap::new();
1899
1900                let mut start_first = BTreeSet::new();
1901                start_first.insert(FirstElement::Terminal('a'));
1902
1903                let mut a_first = BTreeSet::new();
1904                a_first.insert(FirstElement::Terminal('a'));
1905
1906                let mut b_first = BTreeSet::new();
1907                b_first.insert(FirstElement::Terminal('c'));
1908
1909                expected_first_set.insert("START", start_first);
1910                expected_first_set.insert("A", a_first);
1911                expected_first_set.insert("B", b_first);
1912
1913                assert!(first_set == expected_first_set);
1914            }
1915        }
1916    }
1917
1918    #[test]
1919    fn combo_ne_e() {
1920        let mut grammar = Grammar::new();
1921
1922        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1923
1924        grammar.insert(
1925            "A",
1926            vec![vec![RuleElement::NonTerminal("B"), RuleElement::Empty]],
1927        );
1928
1929        grammar.insert("B", vec![vec![RuleElement::Empty]]);
1930
1931        match get_first_set(&grammar) {
1932            Err(_) => panic!(),
1933            Ok(first_set) => {
1934                let mut expected_first_set = BTreeMap::new();
1935
1936                let mut b_first = BTreeSet::new();
1937                b_first.insert(FirstElement::Empty);
1938
1939                expected_first_set.insert("START", BTreeSet::new());
1940                expected_first_set.insert("A", BTreeSet::new());
1941                expected_first_set.insert("B", b_first);
1942
1943                assert!(first_set == expected_first_set);
1944            }
1945        }
1946    }
1947
1948    #[test]
1949    fn combo_nt_e() {
1950        let mut grammar = Grammar::new();
1951
1952        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1953
1954        grammar.insert(
1955            "A",
1956            vec![vec![RuleElement::NonTerminal("B"), RuleElement::Empty]],
1957        );
1958
1959        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);
1960
1961        match get_first_set(&grammar) {
1962            Err(_) => panic!(),
1963            Ok(first_set) => {
1964                let mut expected_first_set = BTreeMap::new();
1965
1966                let mut start_first = BTreeSet::new();
1967                start_first.insert(FirstElement::Terminal('c'));
1968
1969                let mut a_first = BTreeSet::new();
1970                a_first.insert(FirstElement::Terminal('c'));
1971
1972                let mut b_first = BTreeSet::new();
1973                b_first.insert(FirstElement::Terminal('c'));
1974
1975                expected_first_set.insert("START", start_first);
1976                expected_first_set.insert("A", a_first);
1977                expected_first_set.insert("B", b_first);
1978
1979                assert!(first_set == expected_first_set);
1980            }
1981        }
1982    }
1983
1984    #[test]
1985    fn combo_ne_t() {
1986        let mut grammar = Grammar::new();
1987
1988        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
1989
1990        grammar.insert(
1991            "A",
1992            vec![vec![
1993                RuleElement::NonTerminal("B"),
1994                RuleElement::Terminal('c'),
1995            ]],
1996        );
1997
1998        grammar.insert("B", vec![vec![RuleElement::Empty]]);
1999
2000        match get_first_set(&grammar) {
2001            Err(_) => panic!(),
2002            Ok(first_set) => {
2003                let mut expected_first_set = BTreeMap::new();
2004
2005                let mut start_first = BTreeSet::new();
2006                start_first.insert(FirstElement::Terminal('c'));
2007
2008                let mut a_first = BTreeSet::new();
2009                a_first.insert(FirstElement::Terminal('c'));
2010
2011                let mut b_first = BTreeSet::new();
2012                b_first.insert(FirstElement::Empty);
2013
2014                expected_first_set.insert("START", start_first);
2015                expected_first_set.insert("A", a_first);
2016                expected_first_set.insert("B", b_first);
2017
2018                assert!(first_set == expected_first_set);
2019            }
2020        }
2021    }
2022
2023    #[test]
2024    fn combo_nt_t() {
2025        let mut grammar = Grammar::new();
2026
2027        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2028
2029        grammar.insert(
2030            "A",
2031            vec![vec![
2032                RuleElement::NonTerminal("B"),
2033                RuleElement::Terminal('c'),
2034            ]],
2035        );
2036
2037        grammar.insert("B", vec![vec![RuleElement::Terminal('d')]]);
2038
2039        match get_first_set(&grammar) {
2040            Err(_) => panic!(),
2041            Ok(first_set) => {
2042                let mut expected_first_set = BTreeMap::new();
2043
2044                let mut start_first = BTreeSet::new();
2045                start_first.insert(FirstElement::Terminal('d'));
2046
2047                let mut a_first = BTreeSet::new();
2048                a_first.insert(FirstElement::Terminal('d'));
2049
2050                let mut b_first = BTreeSet::new();
2051                b_first.insert(FirstElement::Terminal('d'));
2052
2053                expected_first_set.insert("START", start_first);
2054                expected_first_set.insert("A", a_first);
2055                expected_first_set.insert("B", b_first);
2056
2057                assert!(first_set == expected_first_set);
2058            }
2059        }
2060    }
2061}
2062
2063#[cfg(test)]
2064mod get_follow_set {
2065    use super::*;
2066
2067    #[test]
2068    fn combo_e() {
2069        let mut grammar = Grammar::new();
2070
2071        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2072
2073        grammar.insert("A", vec![vec![RuleElement::Empty]]);
2074
2075        let first_set = get_first_set(&grammar).unwrap();
2076        let mut expected_follow_set = BTreeMap::new();
2077
2078        expected_follow_set.insert("START", BTreeSet::new());
2079        expected_follow_set.insert("A", BTreeSet::new());
2080
2081        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2082    }
2083
2084    #[test]
2085    fn combo_t() {
2086        let mut grammar = Grammar::new();
2087
2088        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2089
2090        grammar.insert("A", vec![vec![RuleElement::Terminal('b')]]);
2091
2092        let first_set = get_first_set(&grammar).unwrap();
2093        let mut expected_follow_set = BTreeMap::new();
2094
2095        expected_follow_set.insert("START", BTreeSet::new());
2096        expected_follow_set.insert("A", BTreeSet::new());
2097
2098        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2099    }
2100
2101    #[test]
2102    fn combo_n_e() {
2103        let mut grammar = Grammar::new();
2104
2105        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2106
2107        grammar.insert("A", vec![vec![RuleElement::NonTerminal("B")]]);
2108
2109        grammar.insert("B", vec![vec![RuleElement::Empty]]);
2110
2111        let first_set = get_first_set(&grammar).unwrap();
2112        let mut expected_follow_set = BTreeMap::new();
2113
2114        expected_follow_set.insert("START", BTreeSet::new());
2115        expected_follow_set.insert("A", BTreeSet::new());
2116        expected_follow_set.insert("B", BTreeSet::new());
2117
2118        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2119    }
2120
2121    #[test]
2122    fn combo_n_t() {
2123        let mut grammar = Grammar::new();
2124
2125        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2126
2127        grammar.insert("A", vec![vec![RuleElement::NonTerminal("B")]]);
2128
2129        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);
2130
2131        let first_set = get_first_set(&grammar).unwrap();
2132        let mut expected_follow_set = BTreeMap::new();
2133
2134        expected_follow_set.insert("START", BTreeSet::new());
2135        expected_follow_set.insert("A", BTreeSet::new());
2136        expected_follow_set.insert("B", BTreeSet::new());
2137
2138        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2139    }
2140
2141    #[test]
2142    fn combo_ee() {
2143        let mut grammar = Grammar::new();
2144
2145        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2146
2147        grammar.insert("A", vec![vec![RuleElement::Empty, RuleElement::Empty]]);
2148
2149        let first_set = get_first_set(&grammar).unwrap();
2150        let mut expected_follow_set = BTreeMap::new();
2151
2152        expected_follow_set.insert("START", BTreeSet::new());
2153        expected_follow_set.insert("A", BTreeSet::new());
2154
2155        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2156    }
2157
2158    #[test]
2159    fn combo_et() {
2160        let mut grammar = Grammar::new();
2161
2162        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2163
2164        grammar.insert(
2165            "A",
2166            vec![vec![RuleElement::Empty, RuleElement::Terminal('b')]],
2167        );
2168
2169        let first_set = get_first_set(&grammar).unwrap();
2170        let mut expected_follow_set = BTreeMap::new();
2171
2172        expected_follow_set.insert("START", BTreeSet::new());
2173        expected_follow_set.insert("A", BTreeSet::new());
2174
2175        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2176    }
2177
2178    #[test]
2179    fn combo_en_e() {
2180        let mut grammar = Grammar::new();
2181
2182        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2183
2184        grammar.insert(
2185            "A",
2186            vec![vec![RuleElement::Empty, RuleElement::NonTerminal("B")]],
2187        );
2188
2189        grammar.insert("B", vec![vec![RuleElement::Empty]]);
2190
2191        let first_set = get_first_set(&grammar).unwrap();
2192        let mut expected_follow_set = BTreeMap::new();
2193
2194        expected_follow_set.insert("START", BTreeSet::new());
2195        expected_follow_set.insert("A", BTreeSet::new());
2196        expected_follow_set.insert("B", BTreeSet::new());
2197
2198        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2199    }
2200
2201    #[test]
2202    fn combo_en_t() {
2203        let mut grammar = Grammar::new();
2204
2205        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2206
2207        grammar.insert(
2208            "A",
2209            vec![vec![RuleElement::Empty, RuleElement::NonTerminal("B")]],
2210        );
2211
2212        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);
2213
2214        let first_set = get_first_set(&grammar).unwrap();
2215        let mut expected_follow_set = BTreeMap::new();
2216
2217        expected_follow_set.insert("START", BTreeSet::new());
2218        expected_follow_set.insert("A", BTreeSet::new());
2219        expected_follow_set.insert("B", BTreeSet::new());
2220
2221        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2222    }
2223
2224    #[test]
2225    fn combo_eee() {
2226        let mut grammar = Grammar::new();
2227
2228        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2229
2230        grammar.insert(
2231            "A",
2232            vec![vec![
2233                RuleElement::Empty,
2234                RuleElement::Empty,
2235                RuleElement::Empty,
2236            ]],
2237        );
2238
2239        let first_set = get_first_set(&grammar).unwrap();
2240        let mut expected_follow_set = BTreeMap::new();
2241
2242        expected_follow_set.insert("START", BTreeSet::new());
2243        expected_follow_set.insert("A", BTreeSet::new());
2244
2245        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2246    }
2247
2248    #[test]
2249    fn combo_eet() {
2250        let mut grammar = Grammar::new();
2251
2252        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2253
2254        grammar.insert(
2255            "A",
2256            vec![vec![
2257                RuleElement::Empty,
2258                RuleElement::Empty,
2259                RuleElement::Terminal('b'),
2260            ]],
2261        );
2262
2263        let first_set = get_first_set(&grammar).unwrap();
2264        let mut expected_follow_set = BTreeMap::new();
2265
2266        expected_follow_set.insert("START", BTreeSet::new());
2267        expected_follow_set.insert("A", BTreeSet::new());
2268
2269        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2270    }
2271
2272    #[test]
2273    fn combo_een_e() {
2274        let mut grammar = Grammar::new();
2275
2276        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2277
2278        grammar.insert(
2279            "A",
2280            vec![vec![
2281                RuleElement::Empty,
2282                RuleElement::Empty,
2283                RuleElement::NonTerminal("B"),
2284            ]],
2285        );
2286
2287        grammar.insert("B", vec![vec![RuleElement::Empty]]);
2288
2289        let first_set = get_first_set(&grammar).unwrap();
2290        let mut expected_follow_set = BTreeMap::new();
2291
2292        expected_follow_set.insert("START", BTreeSet::new());
2293        expected_follow_set.insert("A", BTreeSet::new());
2294        expected_follow_set.insert("B", BTreeSet::new());
2295
2296        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2297    }
2298
2299    #[test]
2300    fn combo_een_t() {
2301        let mut grammar = Grammar::new();
2302
2303        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2304
2305        grammar.insert(
2306            "A",
2307            vec![vec![
2308                RuleElement::Empty,
2309                RuleElement::Empty,
2310                RuleElement::NonTerminal("B"),
2311            ]],
2312        );
2313
2314        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);
2315
2316        let first_set = get_first_set(&grammar).unwrap();
2317        let mut expected_follow_set = BTreeMap::new();
2318
2319        expected_follow_set.insert("START", BTreeSet::new());
2320        expected_follow_set.insert("A", BTreeSet::new());
2321        expected_follow_set.insert("B", BTreeSet::new());
2322
2323        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2324    }
2325
2326    #[test]
2327    fn combo_ete() {
2328        let mut grammar = Grammar::new();
2329
2330        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2331
2332        grammar.insert(
2333            "A",
2334            vec![vec![
2335                RuleElement::Empty,
2336                RuleElement::Terminal('b'),
2337                RuleElement::Empty,
2338            ]],
2339        );
2340
2341        let first_set = get_first_set(&grammar).unwrap();
2342        let mut expected_follow_set = BTreeMap::new();
2343
2344        expected_follow_set.insert("START", BTreeSet::new());
2345        expected_follow_set.insert("A", BTreeSet::new());
2346
2347        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2348    }
2349
2350    #[test]
2351    fn combo_ett() {
2352        let mut grammar = Grammar::new();
2353
2354        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2355
2356        grammar.insert(
2357            "A",
2358            vec![vec![
2359                RuleElement::Empty,
2360                RuleElement::Terminal('b'),
2361                RuleElement::Terminal('c'),
2362            ]],
2363        );
2364
2365        let first_set = get_first_set(&grammar).unwrap();
2366        let mut expected_follow_set = BTreeMap::new();
2367
2368        expected_follow_set.insert("START", BTreeSet::new());
2369        expected_follow_set.insert("A", BTreeSet::new());
2370
2371        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2372    }
2373
2374    #[test]
2375    fn combo_etn_e() {
2376        let mut grammar = Grammar::new();
2377
2378        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2379
2380        grammar.insert(
2381            "A",
2382            vec![vec![
2383                RuleElement::Empty,
2384                RuleElement::Terminal('b'),
2385                RuleElement::NonTerminal("C"),
2386            ]],
2387        );
2388
2389        grammar.insert("C", vec![vec![RuleElement::Empty]]);
2390
2391        let first_set = get_first_set(&grammar).unwrap();
2392        let mut expected_follow_set = BTreeMap::new();
2393
2394        expected_follow_set.insert("START", BTreeSet::new());
2395        expected_follow_set.insert("A", BTreeSet::new());
2396        expected_follow_set.insert("C", BTreeSet::new());
2397
2398        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2399    }
2400
2401    #[test]
2402    fn combo_etn_t() {
2403        let mut grammar = Grammar::new();
2404
2405        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2406
2407        grammar.insert(
2408            "A",
2409            vec![vec![
2410                RuleElement::Empty,
2411                RuleElement::Terminal('b'),
2412                RuleElement::NonTerminal("C"),
2413            ]],
2414        );
2415
2416        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);
2417
2418        let first_set = get_first_set(&grammar).unwrap();
2419        let mut expected_follow_set = BTreeMap::new();
2420
2421        expected_follow_set.insert("START", BTreeSet::new());
2422        expected_follow_set.insert("A", BTreeSet::new());
2423        expected_follow_set.insert("C", BTreeSet::new());
2424
2425        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2426    }
2427
2428    #[test]
2429    fn combo_ene_e() {
2430        let mut grammar = Grammar::new();
2431
2432        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2433
2434        grammar.insert(
2435            "A",
2436            vec![vec![
2437                RuleElement::Empty,
2438                RuleElement::NonTerminal("B"),
2439                RuleElement::Empty,
2440            ]],
2441        );
2442
2443        grammar.insert("B", vec![vec![RuleElement::Empty]]);
2444
2445        let first_set = get_first_set(&grammar).unwrap();
2446        let mut expected_follow_set = BTreeMap::new();
2447
2448        expected_follow_set.insert("START", BTreeSet::new());
2449        expected_follow_set.insert("A", BTreeSet::new());
2450        expected_follow_set.insert("B", BTreeSet::new());
2451
2452        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2453    }
2454
2455    #[test]
2456    fn combo_ene_t() {
2457        let mut grammar = Grammar::new();
2458
2459        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2460
2461        grammar.insert(
2462            "A",
2463            vec![vec![
2464                RuleElement::Empty,
2465                RuleElement::NonTerminal("B"),
2466                RuleElement::Empty,
2467            ]],
2468        );
2469
2470        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);
2471
2472        let first_set = get_first_set(&grammar).unwrap();
2473        let mut expected_follow_set = BTreeMap::new();
2474
2475        expected_follow_set.insert("START", BTreeSet::new());
2476        expected_follow_set.insert("A", BTreeSet::new());
2477        expected_follow_set.insert("B", BTreeSet::new());
2478
2479        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2480    }
2481
2482    #[test]
2483    fn combo_ent_e() {
2484        let mut grammar = Grammar::new();
2485
2486        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2487
2488        grammar.insert(
2489            "A",
2490            vec![vec![
2491                RuleElement::Empty,
2492                RuleElement::NonTerminal("B"),
2493                RuleElement::Terminal('c'),
2494            ]],
2495        );
2496
2497        grammar.insert("B", vec![vec![RuleElement::Empty]]);
2498
2499        let first_set = get_first_set(&grammar).unwrap();
2500        let mut expected_follow_set = BTreeMap::new();
2501
2502        let mut b_follow = BTreeSet::new();
2503        b_follow.insert('c');
2504
2505        expected_follow_set.insert("START", BTreeSet::new());
2506        expected_follow_set.insert("A", BTreeSet::new());
2507        expected_follow_set.insert("B", b_follow);
2508
2509        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2510    }
2511
2512    #[test]
2513    fn combo_ent_t() {
2514        let mut grammar = Grammar::new();
2515
2516        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2517
2518        grammar.insert(
2519            "A",
2520            vec![vec![
2521                RuleElement::Empty,
2522                RuleElement::NonTerminal("B"),
2523                RuleElement::Terminal('c'),
2524            ]],
2525        );
2526
2527        grammar.insert("B", vec![vec![RuleElement::Terminal('d')]]);
2528
2529        let first_set = get_first_set(&grammar).unwrap();
2530        let mut expected_follow_set = BTreeMap::new();
2531
2532        let mut b_follow = BTreeSet::new();
2533        b_follow.insert('c');
2534
2535        expected_follow_set.insert("START", BTreeSet::new());
2536        expected_follow_set.insert("A", BTreeSet::new());
2537        expected_follow_set.insert("B", b_follow);
2538
2539        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2540    }
2541
2542    #[test]
2543    fn combo_enn_e() {
2544        let mut grammar = Grammar::new();
2545
2546        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2547
2548        grammar.insert(
2549            "A",
2550            vec![vec![
2551                RuleElement::Empty,
2552                RuleElement::NonTerminal("B"),
2553                RuleElement::NonTerminal("C"),
2554            ]],
2555        );
2556
2557        grammar.insert("B", vec![vec![RuleElement::Empty]]);
2558
2559        grammar.insert("C", vec![vec![RuleElement::Empty]]);
2560
2561        let first_set = get_first_set(&grammar).unwrap();
2562        let mut expected_follow_set = BTreeMap::new();
2563
2564        expected_follow_set.insert("START", BTreeSet::new());
2565        expected_follow_set.insert("A", BTreeSet::new());
2566        expected_follow_set.insert("B", BTreeSet::new());
2567        expected_follow_set.insert("C", BTreeSet::new());
2568
2569        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2570    }
2571
2572    #[test]
2573    fn combo_enn_t() {
2574        let mut grammar = Grammar::new();
2575
2576        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2577
2578        grammar.insert(
2579            "A",
2580            vec![vec![
2581                RuleElement::Empty,
2582                RuleElement::NonTerminal("B"),
2583                RuleElement::NonTerminal("C"),
2584            ]],
2585        );
2586
2587        grammar.insert("B", vec![vec![RuleElement::Empty]]);
2588
2589        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);
2590
2591        let first_set = get_first_set(&grammar).unwrap();
2592        let mut expected_follow_set = BTreeMap::new();
2593
2594        let mut b_follow = BTreeSet::new();
2595        b_follow.insert('d');
2596
2597        expected_follow_set.insert("START", BTreeSet::new());
2598        expected_follow_set.insert("A", BTreeSet::new());
2599        expected_follow_set.insert("B", b_follow);
2600        expected_follow_set.insert("C", BTreeSet::new());
2601
2602        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2603    }
2604
2605    #[test]
2606    fn combo_te() {
2607        let mut grammar = Grammar::new();
2608
2609        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2610
2611        grammar.insert(
2612            "A",
2613            vec![vec![RuleElement::Terminal('b'), RuleElement::Empty]],
2614        );
2615
2616        let first_set = get_first_set(&grammar).unwrap();
2617        let mut expected_follow_set = BTreeMap::new();
2618
2619        expected_follow_set.insert("START", BTreeSet::new());
2620        expected_follow_set.insert("A", BTreeSet::new());
2621
2622        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2623    }
2624
2625    #[test]
2626    fn combo_tt() {
2627        let mut grammar = Grammar::new();
2628
2629        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2630
2631        grammar.insert(
2632            "A",
2633            vec![vec![RuleElement::Terminal('b'), RuleElement::Terminal('c')]],
2634        );
2635
2636        let first_set = get_first_set(&grammar).unwrap();
2637        let mut expected_follow_set = BTreeMap::new();
2638
2639        expected_follow_set.insert("START", BTreeSet::new());
2640        expected_follow_set.insert("A", BTreeSet::new());
2641
2642        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2643    }
2644
2645    #[test]
2646    fn combo_tn_e() {
2647        let mut grammar = Grammar::new();
2648
2649        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2650
2651        grammar.insert(
2652            "A",
2653            vec![vec![
2654                RuleElement::Terminal('b'),
2655                RuleElement::NonTerminal("C"),
2656            ]],
2657        );
2658
2659        grammar.insert("C", vec![vec![RuleElement::Empty]]);
2660
2661        let first_set = get_first_set(&grammar).unwrap();
2662        let mut expected_follow_set = BTreeMap::new();
2663
2664        expected_follow_set.insert("START", BTreeSet::new());
2665        expected_follow_set.insert("A", BTreeSet::new());
2666        expected_follow_set.insert("C", BTreeSet::new());
2667
2668        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2669    }
2670
2671    #[test]
2672    fn combo_tn_t() {
2673        let mut grammar = Grammar::new();
2674
2675        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2676
2677        grammar.insert(
2678            "A",
2679            vec![vec![
2680                RuleElement::Terminal('b'),
2681                RuleElement::NonTerminal("C"),
2682            ]],
2683        );
2684
2685        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);
2686
2687        let first_set = get_first_set(&grammar).unwrap();
2688        let mut expected_follow_set = BTreeMap::new();
2689
2690        expected_follow_set.insert("START", BTreeSet::new());
2691        expected_follow_set.insert("A", BTreeSet::new());
2692        expected_follow_set.insert("C", BTreeSet::new());
2693
2694        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2695    }
2696
2697    #[test]
2698    fn combo_tee() {
2699        let mut grammar = Grammar::new();
2700
2701        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2702
2703        grammar.insert(
2704            "A",
2705            vec![vec![
2706                RuleElement::Terminal('b'),
2707                RuleElement::Empty,
2708                RuleElement::Empty,
2709            ]],
2710        );
2711
2712        let first_set = get_first_set(&grammar).unwrap();
2713        let mut expected_follow_set = BTreeMap::new();
2714
2715        expected_follow_set.insert("START", BTreeSet::new());
2716        expected_follow_set.insert("A", BTreeSet::new());
2717
2718        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2719    }
2720
2721    #[test]
2722    fn combo_tet() {
2723        let mut grammar = Grammar::new();
2724
2725        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2726
2727        grammar.insert(
2728            "A",
2729            vec![vec![
2730                RuleElement::Terminal('b'),
2731                RuleElement::Empty,
2732                RuleElement::Terminal('c'),
2733            ]],
2734        );
2735
2736        let first_set = get_first_set(&grammar).unwrap();
2737        let mut expected_follow_set = BTreeMap::new();
2738
2739        expected_follow_set.insert("START", BTreeSet::new());
2740        expected_follow_set.insert("A", BTreeSet::new());
2741
2742        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2743    }
2744
2745    #[test]
2746    fn combo_ten_e() {
2747        let mut grammar = Grammar::new();
2748
2749        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2750
2751        grammar.insert(
2752            "A",
2753            vec![vec![
2754                RuleElement::Terminal('b'),
2755                RuleElement::Empty,
2756                RuleElement::NonTerminal("C"),
2757            ]],
2758        );
2759
2760        grammar.insert("C", vec![vec![RuleElement::Empty]]);
2761
2762        let first_set = get_first_set(&grammar).unwrap();
2763        let mut expected_follow_set = BTreeMap::new();
2764
2765        expected_follow_set.insert("START", BTreeSet::new());
2766        expected_follow_set.insert("A", BTreeSet::new());
2767        expected_follow_set.insert("C", BTreeSet::new());
2768
2769        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2770    }
2771
2772    #[test]
2773    fn combo_ten_t() {
2774        let mut grammar = Grammar::new();
2775
2776        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2777
2778        grammar.insert(
2779            "A",
2780            vec![vec![
2781                RuleElement::Terminal('b'),
2782                RuleElement::Empty,
2783                RuleElement::NonTerminal("C"),
2784            ]],
2785        );
2786
2787        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);
2788
2789        let first_set = get_first_set(&grammar).unwrap();
2790        let mut expected_follow_set = BTreeMap::new();
2791
2792        expected_follow_set.insert("START", BTreeSet::new());
2793        expected_follow_set.insert("A", BTreeSet::new());
2794        expected_follow_set.insert("C", BTreeSet::new());
2795
2796        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2797    }
2798
2799    #[test]
2800    fn combo_tte() {
2801        let mut grammar = Grammar::new();
2802
2803        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2804
2805        grammar.insert(
2806            "A",
2807            vec![vec![
2808                RuleElement::Terminal('b'),
2809                RuleElement::Terminal('c'),
2810                RuleElement::Empty,
2811            ]],
2812        );
2813
2814        let first_set = get_first_set(&grammar).unwrap();
2815        let mut expected_follow_set = BTreeMap::new();
2816
2817        expected_follow_set.insert("START", BTreeSet::new());
2818        expected_follow_set.insert("A", BTreeSet::new());
2819
2820        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2821    }
2822
2823    #[test]
2824    fn combo_ttt() {
2825        let mut grammar = Grammar::new();
2826
2827        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2828
2829        grammar.insert(
2830            "A",
2831            vec![vec![
2832                RuleElement::Terminal('b'),
2833                RuleElement::Terminal('c'),
2834                RuleElement::Terminal('d'),
2835            ]],
2836        );
2837
2838        let first_set = get_first_set(&grammar).unwrap();
2839        let mut expected_follow_set = BTreeMap::new();
2840
2841        expected_follow_set.insert("START", BTreeSet::new());
2842        expected_follow_set.insert("A", BTreeSet::new());
2843
2844        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2845    }
2846
2847    #[test]
2848    fn combo_ttn_e() {
2849        let mut grammar = Grammar::new();
2850
2851        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2852
2853        grammar.insert(
2854            "A",
2855            vec![vec![
2856                RuleElement::Terminal('b'),
2857                RuleElement::Terminal('c'),
2858                RuleElement::NonTerminal("D"),
2859            ]],
2860        );
2861
2862        grammar.insert("D", vec![vec![RuleElement::Empty]]);
2863
2864        let first_set = get_first_set(&grammar).unwrap();
2865        let mut expected_follow_set = BTreeMap::new();
2866
2867        expected_follow_set.insert("START", BTreeSet::new());
2868        expected_follow_set.insert("A", BTreeSet::new());
2869        expected_follow_set.insert("D", BTreeSet::new());
2870
2871        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2872    }
2873
2874    #[test]
2875    fn combo_ttn_t() {
2876        let mut grammar = Grammar::new();
2877
2878        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2879
2880        grammar.insert(
2881            "A",
2882            vec![vec![
2883                RuleElement::Terminal('b'),
2884                RuleElement::Terminal('c'),
2885                RuleElement::NonTerminal("D"),
2886            ]],
2887        );
2888
2889        grammar.insert("D", vec![vec![RuleElement::Terminal('e')]]);
2890
2891        let first_set = get_first_set(&grammar).unwrap();
2892        let mut expected_follow_set = BTreeMap::new();
2893
2894        expected_follow_set.insert("START", BTreeSet::new());
2895        expected_follow_set.insert("A", BTreeSet::new());
2896        expected_follow_set.insert("D", BTreeSet::new());
2897
2898        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2899    }
2900
2901    #[test]
2902    fn combo_tne_e() {
2903        let mut grammar = Grammar::new();
2904
2905        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2906
2907        grammar.insert(
2908            "A",
2909            vec![vec![
2910                RuleElement::Terminal('b'),
2911                RuleElement::NonTerminal("C"),
2912                RuleElement::Empty,
2913            ]],
2914        );
2915
2916        grammar.insert("C", vec![vec![RuleElement::Empty]]);
2917
2918        let first_set = get_first_set(&grammar).unwrap();
2919        let mut expected_follow_set = BTreeMap::new();
2920
2921        expected_follow_set.insert("START", BTreeSet::new());
2922        expected_follow_set.insert("A", BTreeSet::new());
2923        expected_follow_set.insert("C", BTreeSet::new());
2924
2925        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2926    }
2927
2928    #[test]
2929    fn combo_tne_t() {
2930        let mut grammar = Grammar::new();
2931
2932        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2933
2934        grammar.insert(
2935            "A",
2936            vec![vec![
2937                RuleElement::Terminal('b'),
2938                RuleElement::NonTerminal("C"),
2939                RuleElement::Empty,
2940            ]],
2941        );
2942
2943        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);
2944
2945        let first_set = get_first_set(&grammar).unwrap();
2946        let mut expected_follow_set = BTreeMap::new();
2947
2948        expected_follow_set.insert("START", BTreeSet::new());
2949        expected_follow_set.insert("A", BTreeSet::new());
2950        expected_follow_set.insert("C", BTreeSet::new());
2951
2952        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2953    }
2954
2955    #[test]
2956    fn combo_tnt_e() {
2957        let mut grammar = Grammar::new();
2958
2959        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2960
2961        grammar.insert(
2962            "A",
2963            vec![vec![
2964                RuleElement::Terminal('b'),
2965                RuleElement::NonTerminal("C"),
2966                RuleElement::Terminal('d'),
2967            ]],
2968        );
2969
2970        grammar.insert("C", vec![vec![RuleElement::Empty]]);
2971
2972        let first_set = get_first_set(&grammar).unwrap();
2973        let mut expected_follow_set = BTreeMap::new();
2974
2975        let mut c_follow = BTreeSet::new();
2976        c_follow.insert('d');
2977
2978        expected_follow_set.insert("START", BTreeSet::new());
2979        expected_follow_set.insert("A", BTreeSet::new());
2980        expected_follow_set.insert("C", c_follow);
2981
2982        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
2983    }
2984
2985    #[test]
2986    fn combo_tnt_t() {
2987        let mut grammar = Grammar::new();
2988
2989        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
2990
2991        grammar.insert(
2992            "A",
2993            vec![vec![
2994                RuleElement::Terminal('b'),
2995                RuleElement::NonTerminal("C"),
2996                RuleElement::Terminal('d'),
2997            ]],
2998        );
2999
3000        grammar.insert("C", vec![vec![RuleElement::Terminal('e')]]);
3001
3002        let first_set = get_first_set(&grammar).unwrap();
3003        let mut expected_follow_set = BTreeMap::new();
3004
3005        let mut c_follow = BTreeSet::new();
3006        c_follow.insert('d');
3007
3008        expected_follow_set.insert("START", BTreeSet::new());
3009        expected_follow_set.insert("A", BTreeSet::new());
3010        expected_follow_set.insert("C", c_follow);
3011
3012        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3013    }
3014
3015    #[test]
3016    fn combo_tnn_e() {
3017        let mut grammar = Grammar::new();
3018
3019        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3020
3021        grammar.insert(
3022            "A",
3023            vec![vec![
3024                RuleElement::Terminal('b'),
3025                RuleElement::NonTerminal("C"),
3026                RuleElement::NonTerminal("D"),
3027            ]],
3028        );
3029
3030        grammar.insert("C", vec![vec![RuleElement::Empty]]);
3031
3032        grammar.insert("D", vec![vec![RuleElement::Empty]]);
3033
3034        let first_set = get_first_set(&grammar).unwrap();
3035        let mut expected_follow_set = BTreeMap::new();
3036
3037        expected_follow_set.insert("START", BTreeSet::new());
3038        expected_follow_set.insert("A", BTreeSet::new());
3039        expected_follow_set.insert("C", BTreeSet::new());
3040        expected_follow_set.insert("D", BTreeSet::new());
3041
3042        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3043    }
3044
3045    #[test]
3046    fn combo_tnn_t() {
3047        let mut grammar = Grammar::new();
3048
3049        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3050
3051        grammar.insert(
3052            "A",
3053            vec![vec![
3054                RuleElement::Terminal('b'),
3055                RuleElement::NonTerminal("C"),
3056                RuleElement::NonTerminal("D"),
3057            ]],
3058        );
3059
3060        grammar.insert("C", vec![vec![RuleElement::Empty]]);
3061
3062        grammar.insert("D", vec![vec![RuleElement::Terminal('e')]]);
3063
3064        let first_set = get_first_set(&grammar).unwrap();
3065        let mut expected_follow_set = BTreeMap::new();
3066
3067        let mut c_follow = BTreeSet::new();
3068        c_follow.insert('e');
3069
3070        expected_follow_set.insert("START", BTreeSet::new());
3071        expected_follow_set.insert("A", BTreeSet::new());
3072        expected_follow_set.insert("C", c_follow);
3073        expected_follow_set.insert("D", BTreeSet::new());
3074
3075        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3076    }
3077
3078    #[test]
3079    fn combo_nee_e() {
3080        let mut grammar = Grammar::new();
3081
3082        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3083
3084        grammar.insert(
3085            "A",
3086            vec![vec![
3087                RuleElement::NonTerminal("B"),
3088                RuleElement::Empty,
3089                RuleElement::Empty,
3090            ]],
3091        );
3092
3093        grammar.insert("B", vec![vec![RuleElement::Empty]]);
3094
3095        let first_set = get_first_set(&grammar).unwrap();
3096        let mut expected_follow_set = BTreeMap::new();
3097
3098        expected_follow_set.insert("START", BTreeSet::new());
3099        expected_follow_set.insert("A", BTreeSet::new());
3100        expected_follow_set.insert("B", BTreeSet::new());
3101
3102        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3103    }
3104
3105    #[test]
3106    fn combo_nee_t() {
3107        let mut grammar = Grammar::new();
3108
3109        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3110
3111        grammar.insert(
3112            "A",
3113            vec![vec![
3114                RuleElement::NonTerminal("B"),
3115                RuleElement::Empty,
3116                RuleElement::Empty,
3117            ]],
3118        );
3119
3120        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);
3121
3122        let first_set = get_first_set(&grammar).unwrap();
3123        let mut expected_follow_set = BTreeMap::new();
3124
3125        expected_follow_set.insert("START", BTreeSet::new());
3126        expected_follow_set.insert("A", BTreeSet::new());
3127        expected_follow_set.insert("B", BTreeSet::new());
3128
3129        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3130    }
3131
3132    #[test]
3133    fn combo_net_e() {
3134        let mut grammar = Grammar::new();
3135
3136        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3137
3138        grammar.insert(
3139            "A",
3140            vec![vec![
3141                RuleElement::NonTerminal("B"),
3142                RuleElement::Empty,
3143                RuleElement::Terminal('c'),
3144            ]],
3145        );
3146
3147        grammar.insert("B", vec![vec![RuleElement::Empty]]);
3148
3149        let first_set = get_first_set(&grammar).unwrap();
3150        let mut expected_follow_set = BTreeMap::new();
3151
3152        let mut b_follow = BTreeSet::new();
3153        b_follow.insert('c');
3154
3155        expected_follow_set.insert("START", BTreeSet::new());
3156        expected_follow_set.insert("A", BTreeSet::new());
3157        expected_follow_set.insert("B", b_follow);
3158
3159        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3160    }
3161
3162    #[test]
3163    fn combo_net_t() {
3164        let mut grammar = Grammar::new();
3165
3166        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3167
3168        grammar.insert(
3169            "A",
3170            vec![vec![
3171                RuleElement::NonTerminal("B"),
3172                RuleElement::Empty,
3173                RuleElement::Terminal('c'),
3174            ]],
3175        );
3176
3177        grammar.insert("B", vec![vec![RuleElement::Terminal('d')]]);
3178
3179        let first_set = get_first_set(&grammar).unwrap();
3180        let mut expected_follow_set = BTreeMap::new();
3181
3182        let mut b_follow = BTreeSet::new();
3183        b_follow.insert('c');
3184
3185        expected_follow_set.insert("START", BTreeSet::new());
3186        expected_follow_set.insert("A", BTreeSet::new());
3187        expected_follow_set.insert("B", b_follow);
3188
3189        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3190    }
3191
3192    #[test]
3193    fn combo_nen_e() {
3194        let mut grammar = Grammar::new();
3195
3196        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3197
3198        grammar.insert(
3199            "A",
3200            vec![vec![
3201                RuleElement::NonTerminal("B"),
3202                RuleElement::Empty,
3203                RuleElement::NonTerminal("C"),
3204            ]],
3205        );
3206
3207        grammar.insert("B", vec![vec![RuleElement::Empty]]);
3208
3209        grammar.insert("C", vec![vec![RuleElement::Empty]]);
3210
3211        let first_set = get_first_set(&grammar).unwrap();
3212        let mut expected_follow_set = BTreeMap::new();
3213
3214        expected_follow_set.insert("START", BTreeSet::new());
3215        expected_follow_set.insert("A", BTreeSet::new());
3216        expected_follow_set.insert("B", BTreeSet::new());
3217        expected_follow_set.insert("C", BTreeSet::new());
3218
3219        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3220    }
3221
3222    #[test]
3223    fn combo_nen_t() {
3224        let mut grammar = Grammar::new();
3225
3226        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3227
3228        grammar.insert(
3229            "A",
3230            vec![vec![
3231                RuleElement::NonTerminal("B"),
3232                RuleElement::Empty,
3233                RuleElement::NonTerminal("C"),
3234            ]],
3235        );
3236
3237        grammar.insert("B", vec![vec![RuleElement::Empty]]);
3238
3239        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);
3240
3241        let first_set = get_first_set(&grammar).unwrap();
3242        let mut expected_follow_set = BTreeMap::new();
3243
3244        let mut b_follow = BTreeSet::new();
3245        b_follow.insert('d');
3246
3247        expected_follow_set.insert("START", BTreeSet::new());
3248        expected_follow_set.insert("A", BTreeSet::new());
3249        expected_follow_set.insert("B", b_follow);
3250        expected_follow_set.insert("C", BTreeSet::new());
3251
3252        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3253    }
3254
3255    #[test]
3256    fn combo_nte_e() {
3257        let mut grammar = Grammar::new();
3258
3259        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3260
3261        grammar.insert(
3262            "A",
3263            vec![vec![
3264                RuleElement::NonTerminal("B"),
3265                RuleElement::Empty,
3266                RuleElement::Empty,
3267            ]],
3268        );
3269
3270        grammar.insert("B", vec![vec![RuleElement::Empty]]);
3271
3272        let first_set = get_first_set(&grammar).unwrap();
3273        let mut expected_follow_set = BTreeMap::new();
3274
3275        expected_follow_set.insert("START", BTreeSet::new());
3276        expected_follow_set.insert("A", BTreeSet::new());
3277        expected_follow_set.insert("B", BTreeSet::new());
3278
3279        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3280    }
3281
3282    #[test]
3283    fn combo_nte_t() {
3284        let mut grammar = Grammar::new();
3285
3286        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3287
3288        grammar.insert(
3289            "A",
3290            vec![vec![
3291                RuleElement::NonTerminal("B"),
3292                RuleElement::Empty,
3293                RuleElement::Empty,
3294            ]],
3295        );
3296
3297        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);
3298
3299        let first_set = get_first_set(&grammar).unwrap();
3300        let mut expected_follow_set = BTreeMap::new();
3301
3302        expected_follow_set.insert("START", BTreeSet::new());
3303        expected_follow_set.insert("A", BTreeSet::new());
3304        expected_follow_set.insert("B", BTreeSet::new());
3305
3306        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3307    }
3308
3309    #[test]
3310    fn combo_ntt_e() {
3311        let mut grammar = Grammar::new();
3312
3313        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3314
3315        grammar.insert(
3316            "A",
3317            vec![vec![
3318                RuleElement::NonTerminal("B"),
3319                RuleElement::Terminal('c'),
3320                RuleElement::Terminal('d'),
3321            ]],
3322        );
3323
3324        grammar.insert("B", vec![vec![RuleElement::Empty]]);
3325
3326        let first_set = get_first_set(&grammar).unwrap();
3327        let mut expected_follow_set = BTreeMap::new();
3328
3329        let mut b_follow = BTreeSet::new();
3330        b_follow.insert('c');
3331
3332        expected_follow_set.insert("START", BTreeSet::new());
3333        expected_follow_set.insert("A", BTreeSet::new());
3334        expected_follow_set.insert("B", b_follow);
3335
3336        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3337    }
3338
3339    #[test]
3340    fn combo_ntt_t() {
3341        let mut grammar = Grammar::new();
3342
3343        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3344
3345        grammar.insert(
3346            "A",
3347            vec![vec![
3348                RuleElement::NonTerminal("B"),
3349                RuleElement::Terminal('c'),
3350                RuleElement::Terminal('d'),
3351            ]],
3352        );
3353
3354        grammar.insert("B", vec![vec![RuleElement::Terminal('e')]]);
3355
3356        let first_set = get_first_set(&grammar).unwrap();
3357        let mut expected_follow_set = BTreeMap::new();
3358
3359        let mut b_follow = BTreeSet::new();
3360        b_follow.insert('c');
3361
3362        expected_follow_set.insert("START", BTreeSet::new());
3363        expected_follow_set.insert("A", BTreeSet::new());
3364        expected_follow_set.insert("B", b_follow);
3365
3366        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3367    }
3368
3369    #[test]
3370    fn combo_ntn_e() {
3371        let mut grammar = Grammar::new();
3372
3373        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3374
3375        grammar.insert(
3376            "A",
3377            vec![vec![
3378                RuleElement::NonTerminal("B"),
3379                RuleElement::Terminal('c'),
3380                RuleElement::NonTerminal("C"),
3381            ]],
3382        );
3383
3384        grammar.insert("B", vec![vec![RuleElement::Empty]]);
3385
3386        grammar.insert("C", vec![vec![RuleElement::Empty]]);
3387
3388        let first_set = get_first_set(&grammar).unwrap();
3389        let mut expected_follow_set = BTreeMap::new();
3390
3391        let mut b_follow = BTreeSet::new();
3392        b_follow.insert('c');
3393
3394        expected_follow_set.insert("START", BTreeSet::new());
3395        expected_follow_set.insert("A", BTreeSet::new());
3396        expected_follow_set.insert("B", b_follow);
3397        expected_follow_set.insert("C", BTreeSet::new());
3398
3399        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3400    }
3401
3402    #[test]
3403    fn combo_ntn_t() {
3404        let mut grammar = Grammar::new();
3405
3406        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3407
3408        grammar.insert(
3409            "A",
3410            vec![vec![
3411                RuleElement::NonTerminal("B"),
3412                RuleElement::Terminal('c'),
3413                RuleElement::NonTerminal("C"),
3414            ]],
3415        );
3416
3417        grammar.insert("B", vec![vec![RuleElement::Empty]]);
3418
3419        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);
3420
3421        let first_set = get_first_set(&grammar).unwrap();
3422        let mut expected_follow_set = BTreeMap::new();
3423
3424        let mut b_follow = BTreeSet::new();
3425        b_follow.insert('c');
3426
3427        expected_follow_set.insert("START", BTreeSet::new());
3428        expected_follow_set.insert("A", BTreeSet::new());
3429        expected_follow_set.insert("B", b_follow);
3430        expected_follow_set.insert("C", BTreeSet::new());
3431
3432        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3433    }
3434
3435    #[test]
3436    fn combo_nne() {
3437        let mut grammar = Grammar::new();
3438
3439        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3440
3441        grammar.insert(
3442            "A",
3443            vec![vec![
3444                RuleElement::NonTerminal("B"),
3445                RuleElement::NonTerminal("C"),
3446                RuleElement::Empty,
3447            ]],
3448        );
3449
3450        grammar.insert("B", vec![vec![RuleElement::Empty]]);
3451
3452        grammar.insert("C", vec![vec![RuleElement::Empty]]);
3453
3454        let first_set = get_first_set(&grammar).unwrap();
3455        let mut expected_follow_set = BTreeMap::new();
3456
3457        expected_follow_set.insert("START", BTreeSet::new());
3458        expected_follow_set.insert("A", BTreeSet::new());
3459        expected_follow_set.insert("B", BTreeSet::new());
3460        expected_follow_set.insert("C", BTreeSet::new());
3461
3462        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3463    }
3464
3465    #[test]
3466    fn combo_nne_t() {
3467        let mut grammar = Grammar::new();
3468
3469        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3470
3471        grammar.insert(
3472            "A",
3473            vec![vec![
3474                RuleElement::NonTerminal("B"),
3475                RuleElement::NonTerminal("C"),
3476                RuleElement::Empty,
3477            ]],
3478        );
3479
3480        grammar.insert("B", vec![vec![RuleElement::Empty]]);
3481
3482        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);
3483
3484        let first_set = get_first_set(&grammar).unwrap();
3485        let mut expected_follow_set = BTreeMap::new();
3486
3487        let mut b_follow = BTreeSet::new();
3488        b_follow.insert('d');
3489
3490        expected_follow_set.insert("START", BTreeSet::new());
3491        expected_follow_set.insert("A", BTreeSet::new());
3492        expected_follow_set.insert("B", b_follow);
3493        expected_follow_set.insert("C", BTreeSet::new());
3494
3495        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3496    }
3497
3498    #[test]
3499    fn combo_nnt_e() {
3500        let mut grammar = Grammar::new();
3501
3502        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3503
3504        grammar.insert(
3505            "A",
3506            vec![vec![
3507                RuleElement::NonTerminal("B"),
3508                RuleElement::NonTerminal("C"),
3509                RuleElement::Terminal('d'),
3510            ]],
3511        );
3512
3513        grammar.insert("B", vec![vec![RuleElement::Empty]]);
3514
3515        grammar.insert("C", vec![vec![RuleElement::Empty]]);
3516
3517        let first_set = get_first_set(&grammar).unwrap();
3518        let mut expected_follow_set = BTreeMap::new();
3519
3520        let mut b_follow = BTreeSet::new();
3521        b_follow.insert('d');
3522
3523        let mut c_follow = BTreeSet::new();
3524        c_follow.insert('d');
3525
3526        expected_follow_set.insert("START", BTreeSet::new());
3527        expected_follow_set.insert("A", BTreeSet::new());
3528        expected_follow_set.insert("B", b_follow);
3529        expected_follow_set.insert("C", c_follow);
3530
3531        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3532    }
3533
3534    #[test]
3535    fn combo_nnt_t() {
3536        let mut grammar = Grammar::new();
3537
3538        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3539
3540        grammar.insert(
3541            "A",
3542            vec![vec![
3543                RuleElement::NonTerminal("B"),
3544                RuleElement::NonTerminal("C"),
3545                RuleElement::Terminal('d'),
3546            ]],
3547        );
3548
3549        grammar.insert("B", vec![vec![RuleElement::Empty]]);
3550
3551        grammar.insert("C", vec![vec![RuleElement::Terminal('e')]]);
3552
3553        let first_set = get_first_set(&grammar).unwrap();
3554        let mut expected_follow_set = BTreeMap::new();
3555
3556        let mut b_follow = BTreeSet::new();
3557        b_follow.insert('e');
3558
3559        let mut c_follow = BTreeSet::new();
3560        c_follow.insert('d');
3561
3562        expected_follow_set.insert("START", BTreeSet::new());
3563        expected_follow_set.insert("A", BTreeSet::new());
3564        expected_follow_set.insert("B", b_follow);
3565        expected_follow_set.insert("C", c_follow);
3566
3567        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3568    }
3569
3570    #[test]
3571    fn combo_nnn_e() {
3572        let mut grammar = Grammar::new();
3573
3574        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3575
3576        grammar.insert(
3577            "A",
3578            vec![vec![
3579                RuleElement::NonTerminal("B"),
3580                RuleElement::NonTerminal("C"),
3581                RuleElement::NonTerminal("D"),
3582            ]],
3583        );
3584
3585        grammar.insert("B", vec![vec![RuleElement::Empty]]);
3586
3587        grammar.insert("C", vec![vec![RuleElement::Empty]]);
3588
3589        grammar.insert("D", vec![vec![RuleElement::Empty]]);
3590
3591        let first_set = get_first_set(&grammar).unwrap();
3592        let mut expected_follow_set = BTreeMap::new();
3593
3594        expected_follow_set.insert("START", BTreeSet::new());
3595        expected_follow_set.insert("A", BTreeSet::new());
3596        expected_follow_set.insert("B", BTreeSet::new());
3597        expected_follow_set.insert("C", BTreeSet::new());
3598        expected_follow_set.insert("D", BTreeSet::new());
3599
3600        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3601    }
3602
3603    #[test]
3604    fn combo_nnn_t_e() {
3605        let mut grammar = Grammar::new();
3606
3607        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3608
3609        grammar.insert(
3610            "A",
3611            vec![vec![
3612                RuleElement::NonTerminal("B"),
3613                RuleElement::NonTerminal("C"),
3614                RuleElement::NonTerminal("D"),
3615            ]],
3616        );
3617
3618        grammar.insert("B", vec![vec![RuleElement::Empty]]);
3619
3620        grammar.insert("C", vec![vec![RuleElement::Terminal('e')]]);
3621
3622        grammar.insert("D", vec![vec![RuleElement::Empty]]);
3623
3624        let first_set = get_first_set(&grammar).unwrap();
3625        let mut expected_follow_set = BTreeMap::new();
3626
3627        let mut b_follow = BTreeSet::new();
3628        b_follow.insert('e');
3629
3630        expected_follow_set.insert("START", BTreeSet::new());
3631        expected_follow_set.insert("A", BTreeSet::new());
3632        expected_follow_set.insert("B", b_follow);
3633        expected_follow_set.insert("C", BTreeSet::new());
3634        expected_follow_set.insert("D", BTreeSet::new());
3635
3636        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3637    }
3638
3639    #[test]
3640    fn combo_nnn_t_t() {
3641        let mut grammar = Grammar::new();
3642
3643        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3644
3645        grammar.insert(
3646            "A",
3647            vec![vec![
3648                RuleElement::NonTerminal("B"),
3649                RuleElement::NonTerminal("C"),
3650                RuleElement::NonTerminal("D"),
3651            ]],
3652        );
3653
3654        grammar.insert("B", vec![vec![RuleElement::Empty]]);
3655
3656        grammar.insert("C", vec![vec![RuleElement::Terminal('e')]]);
3657
3658        grammar.insert("D", vec![vec![RuleElement::Terminal('f')]]);
3659
3660        let first_set = get_first_set(&grammar).unwrap();
3661        let mut expected_follow_set = BTreeMap::new();
3662
3663        let mut b_follow = BTreeSet::new();
3664        b_follow.insert('e');
3665
3666        let mut c_follow = BTreeSet::new();
3667        c_follow.insert('f');
3668
3669        expected_follow_set.insert("START", BTreeSet::new());
3670        expected_follow_set.insert("A", BTreeSet::new());
3671        expected_follow_set.insert("B", b_follow);
3672        expected_follow_set.insert("C", c_follow);
3673        expected_follow_set.insert("D", BTreeSet::new());
3674
3675        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
3676    }
3677}
3678
3679#[cfg(test)]
3680mod get_parse_table {
3681    use super::*;
3682
3683    #[test]
3684    fn combo_e() {
3685        let mut grammar = Grammar::new();
3686
3687        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3688
3689        grammar.insert("A", vec![vec![RuleElement::Empty]]);
3690
3691        let first_set = get_first_set(&grammar).unwrap();
3692        let follow_set = get_follow_set(&grammar, &first_set);
3693
3694        let mut a_parse = BTreeMap::new();
3695        a_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
3696
3697        let mut expected_parse_table = BTreeMap::new();
3698        expected_parse_table.insert("START", BTreeMap::new());
3699        expected_parse_table.insert("A", a_parse);
3700
3701        assert!(
3702            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
3703        );
3704    }
3705
3706    #[test]
3707    fn combo_ee() {
3708        let mut grammar = Grammar::new();
3709
3710        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3711
3712        grammar.insert("A", vec![vec![RuleElement::Empty, RuleElement::Empty]]);
3713
3714        let first_set = get_first_set(&grammar).unwrap();
3715        let follow_set = get_follow_set(&grammar, &first_set);
3716
3717        let mut expected_parse_table = BTreeMap::new();
3718        expected_parse_table.insert("START", BTreeMap::new());
3719        expected_parse_table.insert("A", BTreeMap::new());
3720
3721        assert!(
3722            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
3723        );
3724    }
3725
3726    #[test]
3727    fn combo_et() {
3728        let mut grammar = Grammar::new();
3729
3730        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3731
3732        grammar.insert(
3733            "A",
3734            vec![vec![RuleElement::Empty, RuleElement::Terminal('b')]],
3735        );
3736
3737        let first_set = get_first_set(&grammar).unwrap();
3738        let follow_set = get_follow_set(&grammar, &first_set);
3739
3740        let mut start_parse = BTreeMap::new();
3741        start_parse.insert(
3742            ParseTableElement::Terminal('b'),
3743            vec![RuleElement::NonTerminal("A")],
3744        );
3745
3746        let mut a_parse = BTreeMap::new();
3747        a_parse.insert(
3748            ParseTableElement::Terminal('b'),
3749            vec![RuleElement::Empty, RuleElement::Terminal('b')],
3750        );
3751
3752        let mut expected_parse_table = BTreeMap::new();
3753        expected_parse_table.insert("START", start_parse);
3754        expected_parse_table.insert("A", a_parse);
3755
3756        assert!(
3757            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
3758        );
3759    }
3760
3761    #[test]
3762    fn combo_en_e() {
3763        let mut grammar = Grammar::new();
3764
3765        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3766
3767        grammar.insert(
3768            "A",
3769            vec![vec![RuleElement::Empty, RuleElement::NonTerminal("B")]],
3770        );
3771
3772        grammar.insert("B", vec![vec![RuleElement::Empty]]);
3773
3774        let first_set = get_first_set(&grammar).unwrap();
3775        let follow_set = get_follow_set(&grammar, &first_set);
3776
3777        let mut b_parse = BTreeMap::new();
3778        b_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
3779
3780        let mut expected_parse_table = BTreeMap::new();
3781        expected_parse_table.insert("START", BTreeMap::new());
3782        expected_parse_table.insert("A", BTreeMap::new());
3783        expected_parse_table.insert("B", b_parse);
3784
3785        assert!(
3786            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
3787        );
3788    }
3789
3790    #[test]
3791    fn combo_en_t() {
3792        let mut grammar = Grammar::new();
3793
3794        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3795
3796        grammar.insert(
3797            "A",
3798            vec![vec![RuleElement::Empty, RuleElement::NonTerminal("B")]],
3799        );
3800
3801        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);
3802
3803        let first_set = get_first_set(&grammar).unwrap();
3804        let follow_set = get_follow_set(&grammar, &first_set);
3805
3806        let mut start_parse = BTreeMap::new();
3807        start_parse.insert(
3808            ParseTableElement::Terminal('c'),
3809            vec![RuleElement::NonTerminal("A")],
3810        );
3811
3812        let mut a_parse = BTreeMap::new();
3813        a_parse.insert(
3814            ParseTableElement::Terminal('c'),
3815            vec![RuleElement::Empty, RuleElement::NonTerminal("B")],
3816        );
3817
3818        let mut b_parse = BTreeMap::new();
3819        b_parse.insert(
3820            ParseTableElement::Terminal('c'),
3821            vec![RuleElement::Terminal('c')],
3822        );
3823
3824        let mut expected_parse_table = BTreeMap::new();
3825        expected_parse_table.insert("START", start_parse);
3826        expected_parse_table.insert("A", a_parse);
3827        expected_parse_table.insert("B", b_parse);
3828
3829        assert!(
3830            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
3831        );
3832    }
3833
3834    #[test]
3835    fn combo_te_nt_nt() {
3836        let mut grammar = Grammar::new();
3837
3838        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3839
3840        grammar.insert(
3841            "A",
3842            vec![vec![RuleElement::Terminal('c')], vec![RuleElement::Empty]],
3843        );
3844
3845        grammar.insert(
3846            "B",
3847            vec![vec![
3848                RuleElement::NonTerminal("A"),
3849                RuleElement::Terminal('c'),
3850            ]],
3851        );
3852
3853        grammar.insert(
3854            "C",
3855            vec![vec![
3856                RuleElement::NonTerminal("A"),
3857                RuleElement::Terminal('c'),
3858            ]],
3859        );
3860
3861        let first_set = get_first_set(&grammar).unwrap();
3862        let follow_set = get_follow_set(&grammar, &first_set);
3863
3864        match get_parse_table(&mut grammar, &first_set, &follow_set) {
3865            Ok(_) => panic!(),
3866            Err(err) => assert!(
3867                err == GrammarError::Conflict {
3868                    non_terminal: "A",
3869                    rule: vec![RuleElement::Empty],
3870                    rule_element: RuleElement::Empty,
3871                }
3872            ),
3873        }
3874    }
3875
3876    #[test]
3877    fn combo_ne_nt_nt() {
3878        let mut grammar = Grammar::new();
3879
3880        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3881
3882        grammar.insert(
3883            "A",
3884            vec![vec![RuleElement::Terminal('c')], vec![RuleElement::Empty]],
3885        );
3886
3887        grammar.insert(
3888            "B",
3889            vec![vec![
3890                RuleElement::NonTerminal("A"),
3891                RuleElement::Terminal('c'),
3892            ]],
3893        );
3894
3895        grammar.insert(
3896            "C",
3897            vec![vec![
3898                RuleElement::NonTerminal("A"),
3899                RuleElement::Terminal('c'),
3900            ]],
3901        );
3902
3903        let first_set = get_first_set(&grammar).unwrap();
3904        let follow_set = get_follow_set(&grammar, &first_set);
3905
3906        match get_parse_table(&mut grammar, &first_set, &follow_set) {
3907            Ok(_) => panic!(),
3908            Err(err) => assert!(
3909                err == GrammarError::Conflict {
3910                    non_terminal: "A",
3911                    rule: vec![RuleElement::Empty],
3912                    rule_element: RuleElement::Empty,
3913                }
3914            ),
3915        }
3916    }
3917
3918    #[test]
3919    fn combo_t() {
3920        let mut grammar = Grammar::new();
3921
3922        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3923
3924        grammar.insert("A", vec![vec![RuleElement::Terminal('b')]]);
3925
3926        let first_set = get_first_set(&grammar).unwrap();
3927        let follow_set = get_follow_set(&grammar, &first_set);
3928
3929        let mut start_parse = BTreeMap::new();
3930        start_parse.insert(
3931            ParseTableElement::Terminal('b'),
3932            vec![RuleElement::NonTerminal("A")],
3933        );
3934
3935        let mut a_parse = BTreeMap::new();
3936        a_parse.insert(
3937            ParseTableElement::Terminal('b'),
3938            vec![RuleElement::Terminal('b')],
3939        );
3940
3941        let mut expected_parse_table = BTreeMap::new();
3942        expected_parse_table.insert("START", start_parse);
3943        expected_parse_table.insert("A", a_parse);
3944
3945        assert!(
3946            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
3947        );
3948    }
3949
3950    #[test]
3951    fn combo_te() {
3952        let mut grammar = Grammar::new();
3953
3954        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3955
3956        grammar.insert(
3957            "A",
3958            vec![vec![RuleElement::Terminal('b'), RuleElement::Empty]],
3959        );
3960
3961        let first_set = get_first_set(&grammar).unwrap();
3962        let follow_set = get_follow_set(&grammar, &first_set);
3963
3964        let mut start_parse = BTreeMap::new();
3965        start_parse.insert(
3966            ParseTableElement::Terminal('b'),
3967            vec![RuleElement::NonTerminal("A")],
3968        );
3969
3970        let mut a_parse = BTreeMap::new();
3971        a_parse.insert(
3972            ParseTableElement::Terminal('b'),
3973            vec![RuleElement::Terminal('b'), RuleElement::Empty],
3974        );
3975
3976        let mut expected_parse_table = BTreeMap::new();
3977        expected_parse_table.insert("START", start_parse);
3978        expected_parse_table.insert("A", a_parse);
3979
3980        assert!(
3981            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
3982        );
3983    }
3984
3985    #[test]
3986    fn combo_tt() {
3987        let mut grammar = Grammar::new();
3988
3989        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
3990
3991        grammar.insert(
3992            "A",
3993            vec![vec![RuleElement::Terminal('b'), RuleElement::Terminal('c')]],
3994        );
3995
3996        let first_set = get_first_set(&grammar).unwrap();
3997        let follow_set = get_follow_set(&grammar, &first_set);
3998
3999        let mut start_parse = BTreeMap::new();
4000        start_parse.insert(
4001            ParseTableElement::Terminal('b'),
4002            vec![RuleElement::NonTerminal("A")],
4003        );
4004
4005        let mut a_parse = BTreeMap::new();
4006        a_parse.insert(
4007            ParseTableElement::Terminal('b'),
4008            vec![RuleElement::Terminal('b'), RuleElement::Terminal('c')],
4009        );
4010
4011        let mut expected_parse_table = BTreeMap::new();
4012        expected_parse_table.insert("START", start_parse);
4013        expected_parse_table.insert("A", a_parse);
4014
4015        assert!(
4016            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
4017        );
4018    }
4019
4020    #[test]
4021    fn combo_t_t() {
4022        let mut grammar = Grammar::new();
4023
4024        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
4025
4026        grammar.insert(
4027            "A",
4028            vec![
4029                vec![RuleElement::Terminal('b')],
4030                vec![RuleElement::Terminal('b')],
4031            ],
4032        );
4033
4034        let first_set = get_first_set(&grammar).unwrap();
4035        let follow_set = get_follow_set(&grammar, &first_set);
4036
4037        match get_parse_table(&mut grammar, &first_set, &follow_set) {
4038            Ok(_) => panic!(),
4039            Err(err) => assert!(
4040                err == GrammarError::Conflict {
4041                    non_terminal: "A",
4042                    rule: vec![RuleElement::Terminal('b')],
4043                    rule_element: RuleElement::Terminal('b'),
4044                }
4045            ),
4046        }
4047    }
4048
4049    #[test]
4050    fn combo_t_et() {
4051        let mut grammar = Grammar::new();
4052
4053        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
4054
4055        grammar.insert(
4056            "A",
4057            vec![
4058                vec![RuleElement::Terminal('b')],
4059                vec![RuleElement::Empty, RuleElement::Terminal('b')],
4060            ],
4061        );
4062
4063        let first_set = get_first_set(&grammar).unwrap();
4064        let follow_set = get_follow_set(&grammar, &first_set);
4065
4066        match get_parse_table(&mut grammar, &first_set, &follow_set) {
4067            Ok(_) => panic!(),
4068            Err(err) => assert!(
4069                err == GrammarError::Conflict {
4070                    non_terminal: "A",
4071                    rule: vec![RuleElement::Empty, RuleElement::Terminal('b')],
4072                    rule_element: RuleElement::Terminal('b'),
4073                }
4074            ),
4075        }
4076    }
4077
4078    #[test]
4079    fn combo_tn_e() {
4080        let mut grammar = Grammar::new();
4081
4082        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
4083
4084        grammar.insert(
4085            "A",
4086            vec![vec![
4087                RuleElement::Terminal('b'),
4088                RuleElement::NonTerminal("C"),
4089            ]],
4090        );
4091
4092        grammar.insert("C", vec![vec![RuleElement::Empty]]);
4093
4094        let first_set = get_first_set(&grammar).unwrap();
4095        let follow_set = get_follow_set(&grammar, &first_set);
4096
4097        let mut start_parse = BTreeMap::new();
4098        start_parse.insert(
4099            ParseTableElement::Terminal('b'),
4100            vec![RuleElement::NonTerminal("A")],
4101        );
4102
4103        let mut a_parse = BTreeMap::new();
4104        a_parse.insert(
4105            ParseTableElement::Terminal('b'),
4106            vec![RuleElement::Terminal('b'), RuleElement::NonTerminal("C")],
4107        );
4108
4109        let mut c_parse = BTreeMap::new();
4110        c_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
4111
4112        let mut expected_parse_table = BTreeMap::new();
4113        expected_parse_table.insert("START", start_parse);
4114        expected_parse_table.insert("A", a_parse);
4115        expected_parse_table.insert("C", c_parse);
4116
4117        assert!(
4118            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
4119        );
4120    }
4121
4122    #[test]
4123    fn combo_tn_t() {
4124        let mut grammar = Grammar::new();
4125
4126        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
4127
4128        grammar.insert(
4129            "A",
4130            vec![vec![
4131                RuleElement::Terminal('b'),
4132                RuleElement::NonTerminal("C"),
4133            ]],
4134        );
4135
4136        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);
4137
4138        let first_set = get_first_set(&grammar).unwrap();
4139        let follow_set = get_follow_set(&grammar, &first_set);
4140
4141        let mut start_parse = BTreeMap::new();
4142        start_parse.insert(
4143            ParseTableElement::Terminal('b'),
4144            vec![RuleElement::NonTerminal("A")],
4145        );
4146
4147        let mut a_parse = BTreeMap::new();
4148        a_parse.insert(
4149            ParseTableElement::Terminal('b'),
4150            vec![RuleElement::Terminal('b'), RuleElement::NonTerminal("C")],
4151        );
4152
4153        let mut c_parse = BTreeMap::new();
4154        c_parse.insert(
4155            ParseTableElement::Terminal('d'),
4156            vec![RuleElement::Terminal('d')],
4157        );
4158
4159        let mut expected_parse_table = BTreeMap::new();
4160        expected_parse_table.insert("START", start_parse);
4161        expected_parse_table.insert("A", a_parse);
4162        expected_parse_table.insert("C", c_parse);
4163
4164        assert!(
4165            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
4166        );
4167    }
4168
4169    #[test]
4170    fn combo_n_e() {
4171        let mut grammar = Grammar::new();
4172
4173        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
4174
4175        grammar.insert("A", vec![vec![RuleElement::NonTerminal("B")]]);
4176
4177        grammar.insert("B", vec![vec![RuleElement::Empty]]);
4178
4179        let first_set = get_first_set(&grammar).unwrap();
4180        let follow_set = get_follow_set(&grammar, &first_set);
4181
4182        let mut b_parse = BTreeMap::new();
4183        b_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
4184
4185        let mut expected_parse_table = BTreeMap::new();
4186        expected_parse_table.insert("START", BTreeMap::new());
4187        expected_parse_table.insert("A", BTreeMap::new());
4188        expected_parse_table.insert("B", b_parse);
4189
4190        assert!(
4191            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
4192        );
4193    }
4194
4195    #[test]
4196    fn combo_n_t() {
4197        let mut grammar = Grammar::new();
4198
4199        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
4200
4201        grammar.insert("A", vec![vec![RuleElement::NonTerminal("B")]]);
4202
4203        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);
4204
4205        let first_set = get_first_set(&grammar).unwrap();
4206        let follow_set = get_follow_set(&grammar, &first_set);
4207
4208        let mut start_parse = BTreeMap::new();
4209        start_parse.insert(
4210            ParseTableElement::Terminal('c'),
4211            vec![RuleElement::NonTerminal("A")],
4212        );
4213
4214        let mut a_parse = BTreeMap::new();
4215        a_parse.insert(
4216            ParseTableElement::Terminal('c'),
4217            vec![RuleElement::NonTerminal("B")],
4218        );
4219
4220        let mut b_parse = BTreeMap::new();
4221        b_parse.insert(
4222            ParseTableElement::Terminal('c'),
4223            vec![RuleElement::Terminal('c')],
4224        );
4225
4226        let mut expected_parse_table = BTreeMap::new();
4227        expected_parse_table.insert("START", start_parse);
4228        expected_parse_table.insert("A", a_parse);
4229        expected_parse_table.insert("B", b_parse);
4230
4231        assert!(
4232            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
4233        );
4234    }
4235
4236    #[test]
4237    fn combo_ne_e() {
4238        let mut grammar = Grammar::new();
4239
4240        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
4241
4242        grammar.insert(
4243            "A",
4244            vec![vec![RuleElement::NonTerminal("B"), RuleElement::Empty]],
4245        );
4246
4247        grammar.insert("B", vec![vec![RuleElement::Empty]]);
4248
4249        let first_set = get_first_set(&grammar).unwrap();
4250        let follow_set = get_follow_set(&grammar, &first_set);
4251
4252        let mut b_parse = BTreeMap::new();
4253        b_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
4254
4255        let mut expected_parse_table = BTreeMap::new();
4256        expected_parse_table.insert("START", BTreeMap::new());
4257        expected_parse_table.insert("A", BTreeMap::new());
4258        expected_parse_table.insert("B", b_parse);
4259
4260        assert!(
4261            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
4262        );
4263    }
4264
4265    #[test]
4266    fn combo_ne_t() {
4267        let mut grammar = Grammar::new();
4268
4269        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
4270
4271        grammar.insert(
4272            "A",
4273            vec![vec![RuleElement::NonTerminal("B"), RuleElement::Empty]],
4274        );
4275
4276        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);
4277
4278        let first_set = get_first_set(&grammar).unwrap();
4279        let follow_set = get_follow_set(&grammar, &first_set);
4280
4281        let mut start_parse = BTreeMap::new();
4282        start_parse.insert(
4283            ParseTableElement::Terminal('c'),
4284            vec![RuleElement::NonTerminal("A")],
4285        );
4286
4287        let mut a_parse = BTreeMap::new();
4288        a_parse.insert(
4289            ParseTableElement::Terminal('c'),
4290            vec![RuleElement::NonTerminal("B"), RuleElement::Empty],
4291        );
4292
4293        let mut b_parse = BTreeMap::new();
4294        b_parse.insert(
4295            ParseTableElement::Terminal('c'),
4296            vec![RuleElement::Terminal('c')],
4297        );
4298
4299        let mut expected_parse_table = BTreeMap::new();
4300        expected_parse_table.insert("START", start_parse);
4301        expected_parse_table.insert("A", a_parse);
4302        expected_parse_table.insert("B", b_parse);
4303
4304        assert!(
4305            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
4306        );
4307    }
4308
4309    #[test]
4310    fn combo_ne_t_nt() {
4311        let mut grammar = Grammar::new();
4312
4313        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
4314
4315        grammar.insert(
4316            "A",
4317            vec![
4318                vec![RuleElement::NonTerminal("B")],
4319                vec![RuleElement::Empty],
4320            ],
4321        );
4322
4323        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);
4324
4325        grammar.insert(
4326            "C",
4327            vec![vec![
4328                RuleElement::NonTerminal("A"),
4329                RuleElement::Terminal('c'),
4330            ]],
4331        );
4332
4333        let first_set = get_first_set(&grammar).unwrap();
4334        let follow_set = get_follow_set(&grammar, &first_set);
4335
4336        match get_parse_table(&mut grammar, &first_set, &follow_set) {
4337            Ok(_) => panic!(),
4338            Err(err) => assert!(
4339                err == GrammarError::Conflict {
4340                    non_terminal: "A",
4341                    rule: vec![RuleElement::Empty],
4342                    rule_element: RuleElement::Empty,
4343                }
4344            ),
4345        }
4346    }
4347
4348    #[test]
4349    fn combo_nt_e() {
4350        let mut grammar = Grammar::new();
4351
4352        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
4353
4354        grammar.insert(
4355            "A",
4356            vec![vec![
4357                RuleElement::NonTerminal("B"),
4358                RuleElement::Terminal('c'),
4359            ]],
4360        );
4361
4362        grammar.insert("B", vec![vec![RuleElement::Empty]]);
4363
4364        let first_set = get_first_set(&grammar).unwrap();
4365        let follow_set = get_follow_set(&grammar, &first_set);
4366
4367        let mut start_parse = BTreeMap::new();
4368        start_parse.insert(
4369            ParseTableElement::Terminal('c'),
4370            vec![RuleElement::NonTerminal("A")],
4371        );
4372
4373        let mut a_parse = BTreeMap::new();
4374        a_parse.insert(
4375            ParseTableElement::Terminal('c'),
4376            vec![RuleElement::NonTerminal("B"), RuleElement::Terminal('c')],
4377        );
4378
4379        let mut b_parse = BTreeMap::new();
4380        b_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
4381        b_parse.insert(ParseTableElement::Terminal('c'), vec![RuleElement::Empty]);
4382
4383        let mut expected_parse_table = BTreeMap::new();
4384        expected_parse_table.insert("START", start_parse);
4385        expected_parse_table.insert("A", a_parse);
4386        expected_parse_table.insert("B", b_parse);
4387
4388        assert!(
4389            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
4390        );
4391    }
4392
4393    #[test]
4394    fn combo_nt_t() {
4395        let mut grammar = Grammar::new();
4396
4397        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
4398
4399        grammar.insert(
4400            "A",
4401            vec![vec![
4402                RuleElement::NonTerminal("B"),
4403                RuleElement::Terminal('c'),
4404            ]],
4405        );
4406
4407        grammar.insert("B", vec![vec![RuleElement::Terminal('d')]]);
4408
4409        let first_set = get_first_set(&grammar).unwrap();
4410        let follow_set = get_follow_set(&grammar, &first_set);
4411
4412        let mut start_parse = BTreeMap::new();
4413        start_parse.insert(
4414            ParseTableElement::Terminal('d'),
4415            vec![RuleElement::NonTerminal("A")],
4416        );
4417
4418        let mut a_parse = BTreeMap::new();
4419        a_parse.insert(
4420            ParseTableElement::Terminal('d'),
4421            vec![RuleElement::NonTerminal("B"), RuleElement::Terminal('c')],
4422        );
4423
4424        let mut b_parse = BTreeMap::new();
4425        b_parse.insert(
4426            ParseTableElement::Terminal('d'),
4427            vec![RuleElement::Terminal('d')],
4428        );
4429
4430        let mut expected_parse_table = BTreeMap::new();
4431        expected_parse_table.insert("START", start_parse);
4432        expected_parse_table.insert("A", a_parse);
4433        expected_parse_table.insert("B", b_parse);
4434
4435        assert!(
4436            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
4437        );
4438    }
4439
4440    #[test]
4441    fn combo_nn_e() {
4442        let mut grammar = Grammar::new();
4443
4444        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
4445
4446        grammar.insert(
4447            "A",
4448            vec![vec![
4449                RuleElement::NonTerminal("B"),
4450                RuleElement::NonTerminal("C"),
4451            ]],
4452        );
4453
4454        grammar.insert("B", vec![vec![RuleElement::Empty]]);
4455
4456        grammar.insert("C", vec![vec![RuleElement::Empty]]);
4457
4458        let first_set = get_first_set(&grammar).unwrap();
4459        let follow_set = get_follow_set(&grammar, &first_set);
4460
4461        let mut b_parse = BTreeMap::new();
4462        b_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
4463
4464        let mut c_parse = BTreeMap::new();
4465        c_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
4466
4467        let mut expected_parse_table = BTreeMap::new();
4468        expected_parse_table.insert("START", BTreeMap::new());
4469        expected_parse_table.insert("A", BTreeMap::new());
4470        expected_parse_table.insert("B", b_parse);
4471        expected_parse_table.insert("C", c_parse);
4472
4473        assert!(
4474            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
4475        );
4476    }
4477
4478    #[test]
4479    fn combo_nn_t() {
4480        let mut grammar = Grammar::new();
4481
4482        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
4483
4484        grammar.insert(
4485            "A",
4486            vec![vec![
4487                RuleElement::NonTerminal("B"),
4488                RuleElement::NonTerminal("C"),
4489            ]],
4490        );
4491
4492        grammar.insert("B", vec![vec![RuleElement::Empty]]);
4493
4494        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);
4495
4496        let first_set = get_first_set(&grammar).unwrap();
4497        let follow_set = get_follow_set(&grammar, &first_set);
4498
4499        let mut start_parse = BTreeMap::new();
4500        start_parse.insert(
4501            ParseTableElement::Terminal('d'),
4502            vec![RuleElement::NonTerminal("A")],
4503        );
4504
4505        let mut a_parse = BTreeMap::new();
4506        a_parse.insert(
4507            ParseTableElement::Terminal('d'),
4508            vec![RuleElement::NonTerminal("B"), RuleElement::NonTerminal("C")],
4509        );
4510
4511        let mut b_parse = BTreeMap::new();
4512        b_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
4513        b_parse.insert(ParseTableElement::Terminal('d'), vec![RuleElement::Empty]);
4514
4515        let mut c_parse = BTreeMap::new();
4516        c_parse.insert(
4517            ParseTableElement::Terminal('d'),
4518            vec![RuleElement::Terminal('d')],
4519        );
4520
4521        let mut expected_parse_table = BTreeMap::new();
4522        expected_parse_table.insert("START", start_parse);
4523        expected_parse_table.insert("A", a_parse);
4524        expected_parse_table.insert("B", b_parse);
4525        expected_parse_table.insert("C", c_parse);
4526
4527        assert!(
4528            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
4529        );
4530    }
4531
4532    #[test]
4533    fn combo_n_n() {
4534        let mut grammar = Grammar::new();
4535
4536        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
4537
4538        grammar.insert(
4539            "A",
4540            vec![
4541                vec![RuleElement::Terminal('b')],
4542                vec![RuleElement::NonTerminal("C")],
4543            ],
4544        );
4545
4546        grammar.insert("C", vec![vec![RuleElement::Terminal('b')]]);
4547
4548        let first_set = get_first_set(&grammar).unwrap();
4549        let follow_set = get_follow_set(&grammar, &first_set);
4550
4551        match get_parse_table(&mut grammar, &first_set, &follow_set) {
4552            Ok(_) => panic!(),
4553            Err(err) => assert!(
4554                err == GrammarError::Conflict {
4555                    non_terminal: "A",
4556                    rule: vec![RuleElement::NonTerminal("C")],
4557                    rule_element: RuleElement::NonTerminal("C"),
4558                }
4559            ),
4560        }
4561    }
4562
4563    #[test]
4564    fn combo_nn_t_t() {
4565        let mut grammar = Grammar::new();
4566
4567        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);
4568
4569        grammar.insert(
4570            "A",
4571            vec![
4572                vec![RuleElement::NonTerminal("B")],
4573                vec![RuleElement::NonTerminal("C")],
4574            ],
4575        );
4576
4577        grammar.insert("B", vec![vec![RuleElement::Terminal('b')]]);
4578
4579        grammar.insert("C", vec![vec![RuleElement::Terminal('b')]]);
4580
4581        let first_set = get_first_set(&grammar).unwrap();
4582        let follow_set = get_follow_set(&grammar, &first_set);
4583
4584        match get_parse_table(&mut grammar, &first_set, &follow_set) {
4585            Ok(_) => panic!(),
4586            Err(err) => assert!(
4587                err == GrammarError::Conflict {
4588                    non_terminal: "A",
4589                    rule: vec![RuleElement::NonTerminal("C")],
4590                    rule_element: RuleElement::NonTerminal("C"),
4591                }
4592            ),
4593        }
4594    }
4595}
4596
4597#[cfg(test)]
4598mod parsing_techniques_2nd_ed {
4599    use super::*;
4600
4601    fn get_grammar<'a>() -> Grammar<'a> {
4602        let mut grammar = Grammar::new();
4603
4604        grammar.insert("START", vec![vec![RuleElement::NonTerminal("Session")]]);
4605
4606        grammar.insert(
4607            "Session",
4608            vec![
4609                vec![
4610                    RuleElement::NonTerminal("Facts"),
4611                    RuleElement::NonTerminal("Question"),
4612                ],
4613                vec![
4614                    RuleElement::Terminal('('),
4615                    RuleElement::NonTerminal("Session"),
4616                    RuleElement::Terminal(')'),
4617                    RuleElement::NonTerminal("Session"),
4618                ],
4619            ],
4620        );
4621
4622        grammar.insert(
4623            "Facts",
4624            vec![
4625                vec![
4626                    RuleElement::NonTerminal("Fact"),
4627                    RuleElement::NonTerminal("Facts"),
4628                ],
4629                vec![RuleElement::Empty],
4630            ],
4631        );
4632
4633        grammar.insert(
4634            "Fact",
4635            vec![vec![
4636                RuleElement::Terminal('!'),
4637                RuleElement::NonTerminal("STRING"),
4638            ]],
4639        );
4640
4641        grammar.insert(
4642            "Question",
4643            vec![vec![
4644                RuleElement::Terminal('?'),
4645                RuleElement::NonTerminal("STRING"),
4646            ]],
4647        );
4648
4649        grammar.insert("STRING", vec![vec![RuleElement::Terminal('x')]]);
4650
4651        grammar
4652    }
4653
4654    #[test]
4655    fn pg_243() {
4656        let grammar = get_grammar();
4657
4658        let mut expected_first_set = BTreeMap::new();
4659
4660        let mut start_first = BTreeSet::new();
4661        start_first.insert(FirstElement::Terminal('('));
4662        start_first.insert(FirstElement::Terminal('?'));
4663        start_first.insert(FirstElement::Terminal('!'));
4664
4665        let mut session_first = BTreeSet::new();
4666        session_first.insert(FirstElement::Terminal('('));
4667        session_first.insert(FirstElement::Terminal('?'));
4668        session_first.insert(FirstElement::Terminal('!'));
4669
4670        let mut facts_first = BTreeSet::new();
4671        facts_first.insert(FirstElement::Empty);
4672        facts_first.insert(FirstElement::Terminal('!'));
4673
4674        let mut fact_first = BTreeSet::new();
4675        fact_first.insert(FirstElement::Terminal('!'));
4676
4677        let mut question_first = BTreeSet::new();
4678        question_first.insert(FirstElement::Terminal('?'));
4679
4680        let mut string_first = BTreeSet::new();
4681        string_first.insert(FirstElement::Terminal('x'));
4682
4683        expected_first_set.insert("START", start_first);
4684        expected_first_set.insert("Session", session_first);
4685        expected_first_set.insert("Facts", facts_first);
4686        expected_first_set.insert("Fact", fact_first);
4687        expected_first_set.insert("Question", question_first);
4688        expected_first_set.insert("STRING", string_first);
4689
4690        assert!(get_first_set(&grammar).unwrap() == expected_first_set);
4691    }
4692
4693    #[test]
4694    fn pg_246() {
4695        let grammar = get_grammar();
4696        let first_set = get_first_set(&grammar).unwrap();
4697
4698        let mut expected_follow_set: FollowSet = BTreeMap::new();
4699
4700        let mut session_first = BTreeSet::new();
4701        session_first.insert(')');
4702
4703        let mut facts_first = BTreeSet::new();
4704        facts_first.insert('?');
4705
4706        let mut fact_first = BTreeSet::new();
4707        fact_first.insert('!');
4708        fact_first.insert('?');
4709
4710        let mut question_first = BTreeSet::new();
4711        question_first.insert(')');
4712
4713        let mut string_first = BTreeSet::new();
4714        string_first.insert('!');
4715
4716        expected_follow_set.insert("START", BTreeSet::new());
4717        expected_follow_set.insert("Session", session_first);
4718        expected_follow_set.insert("Facts", facts_first);
4719        expected_follow_set.insert("Fact", fact_first);
4720        expected_follow_set.insert("Question", question_first);
4721        expected_follow_set.insert("STRING", string_first);
4722
4723        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
4724    }
4725
4726    #[test]
4727    fn pg_247() {
4728        let mut grammar = get_grammar();
4729        let first_set = get_first_set(&grammar).unwrap();
4730        let follow_set = get_follow_set(&grammar, &first_set);
4731
4732        let mut expected_parse_table: ParseTable = BTreeMap::new();
4733
4734        let mut start_parse = BTreeMap::new();
4735        start_parse.insert(
4736            ParseTableElement::Terminal('!'),
4737            vec![RuleElement::NonTerminal("Session")],
4738        );
4739
4740        start_parse.insert(
4741            ParseTableElement::Terminal('('),
4742            vec![RuleElement::NonTerminal("Session")],
4743        );
4744
4745        start_parse.insert(
4746            ParseTableElement::Terminal('?'),
4747            vec![RuleElement::NonTerminal("Session")],
4748        );
4749
4750        let mut session_parse = BTreeMap::new();
4751
4752        session_parse.insert(
4753            ParseTableElement::Terminal('('),
4754            vec![
4755                RuleElement::Terminal('('),
4756                RuleElement::NonTerminal("Session"),
4757                RuleElement::Terminal(')'),
4758                RuleElement::NonTerminal("Session"),
4759            ],
4760        );
4761
4762        session_parse.insert(
4763            ParseTableElement::Terminal('!'),
4764            vec![
4765                RuleElement::NonTerminal("Facts"),
4766                RuleElement::NonTerminal("Question"),
4767            ],
4768        );
4769
4770        session_parse.insert(
4771            ParseTableElement::Terminal('?'),
4772            vec![
4773                RuleElement::NonTerminal("Facts"),
4774                RuleElement::NonTerminal("Question"),
4775            ],
4776        );
4777
4778        let mut facts_parse = BTreeMap::new();
4779
4780        facts_parse.insert(
4781            ParseTableElement::Terminal('!'),
4782            vec![
4783                RuleElement::NonTerminal("Fact"),
4784                RuleElement::NonTerminal("Facts"),
4785            ],
4786        );
4787
4788        facts_parse.insert(ParseTableElement::Terminal('?'), vec![RuleElement::Empty]);
4789
4790        facts_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
4791
4792        let mut fact_parse = BTreeMap::new();
4793
4794        fact_parse.insert(
4795            ParseTableElement::Terminal('!'),
4796            vec![
4797                RuleElement::Terminal('!'),
4798                RuleElement::NonTerminal("STRING"),
4799            ],
4800        );
4801
4802        let mut question_parse = BTreeMap::new();
4803
4804        question_parse.insert(
4805            ParseTableElement::Terminal('?'),
4806            vec![
4807                RuleElement::Terminal('?'),
4808                RuleElement::NonTerminal("STRING"),
4809            ],
4810        );
4811
4812        let mut string_parse = BTreeMap::new();
4813
4814        string_parse.insert(
4815            ParseTableElement::Terminal('x'),
4816            vec![RuleElement::Terminal('x')],
4817        );
4818
4819        expected_parse_table.insert("START", start_parse);
4820        expected_parse_table.insert("Session", session_parse);
4821        expected_parse_table.insert("Facts", facts_parse);
4822        expected_parse_table.insert("Fact", fact_parse);
4823        expected_parse_table.insert("Question", question_parse);
4824        expected_parse_table.insert("STRING", string_parse);
4825
4826        assert!(
4827            get_parse_table(&mut grammar, &first_set, &follow_set).unwrap() == expected_parse_table
4828        );
4829    }
4830
4831    #[test]
4832    fn parse_ok() {
4833        let mut grammar = get_grammar();
4834        let mut parser = Parser::new(&mut grammar).unwrap();
4835
4836        assert!(
4837            parser.parse("!x?x").unwrap()
4838                == ParseTree::NonTerminal {
4839                    symbol: "START",
4840                    children: vec![ParseTree::NonTerminal {
4841                        symbol: "Session",
4842                        children: vec![
4843                            ParseTree::NonTerminal {
4844                                symbol: "Facts",
4845                                children: vec![
4846                                    ParseTree::NonTerminal {
4847                                        symbol: "Fact",
4848                                        children: vec![
4849                                            ParseTree::Terminal('!'),
4850                                            ParseTree::NonTerminal {
4851                                                symbol: "STRING",
4852                                                children: vec![ParseTree::Terminal('x'),],
4853                                            },
4854                                        ],
4855                                    },
4856                                    ParseTree::NonTerminal {
4857                                        symbol: "Facts",
4858                                        children: vec![],
4859                                    },
4860                                ],
4861                            },
4862                            ParseTree::NonTerminal {
4863                                symbol: "Question",
4864                                children: vec![
4865                                    ParseTree::Terminal('?'),
4866                                    ParseTree::NonTerminal {
4867                                        symbol: "STRING",
4868                                        children: vec![ParseTree::Terminal('x'),],
4869                                    },
4870                                ],
4871                            },
4872                        ],
4873                    },],
4874                }
4875        );
4876    }
4877}
4878
4879#[cfg(test)]
4880mod compilers_1st_ed {
4881    use super::*;
4882
4883    fn get_grammar<'a>() -> Grammar<'a> {
4884        let mut grammar = Grammar::new();
4885
4886        grammar.insert("START", vec![vec![RuleElement::NonTerminal("E")]]);
4887
4888        grammar.insert(
4889            "E",
4890            vec![vec![
4891                RuleElement::NonTerminal("T"),
4892                RuleElement::NonTerminal("Edash"),
4893            ]],
4894        );
4895
4896        grammar.insert(
4897            "Edash",
4898            vec![
4899                vec![
4900                    RuleElement::Terminal('+'),
4901                    RuleElement::NonTerminal("T"),
4902                    RuleElement::NonTerminal("Edash"),
4903                ],
4904                vec![RuleElement::Empty],
4905            ],
4906        );
4907
4908        grammar.insert(
4909            "T",
4910            vec![vec![
4911                RuleElement::NonTerminal("F"),
4912                RuleElement::NonTerminal("Tdash"),
4913            ]],
4914        );
4915
4916        grammar.insert(
4917            "Tdash",
4918            vec![
4919                vec![
4920                    RuleElement::Terminal('*'),
4921                    RuleElement::NonTerminal("F"),
4922                    RuleElement::NonTerminal("Tdash"),
4923                ],
4924                vec![RuleElement::Empty],
4925            ],
4926        );
4927
4928        grammar.insert(
4929            "F",
4930            vec![
4931                vec![
4932                    RuleElement::Terminal('('),
4933                    RuleElement::NonTerminal("E"),
4934                    RuleElement::Terminal(')'),
4935                ],
4936                vec![RuleElement::Terminal('i'), RuleElement::Terminal('d')],
4937            ],
4938        );
4939
4940        grammar
4941    }
4942
4943    #[test]
4944    fn pg_190() {
4945        let grammar = get_grammar();
4946
4947        let mut expected_first_set = BTreeMap::new();
4948
4949        let mut start_first = BTreeSet::new();
4950        start_first.insert(FirstElement::Terminal('('));
4951        start_first.insert(FirstElement::Terminal('i'));
4952
4953        let mut e_first = BTreeSet::new();
4954        e_first.insert(FirstElement::Terminal('('));
4955        e_first.insert(FirstElement::Terminal('i'));
4956
4957        let mut t_first = BTreeSet::new();
4958        t_first.insert(FirstElement::Terminal('('));
4959        t_first.insert(FirstElement::Terminal('i'));
4960
4961        let mut f_first = BTreeSet::new();
4962        f_first.insert(FirstElement::Terminal('('));
4963        f_first.insert(FirstElement::Terminal('i'));
4964
4965        let mut edash_first = BTreeSet::new();
4966        edash_first.insert(FirstElement::Terminal('+'));
4967        edash_first.insert(FirstElement::Empty);
4968
4969        let mut tdash_first = BTreeSet::new();
4970        tdash_first.insert(FirstElement::Terminal('*'));
4971        tdash_first.insert(FirstElement::Empty);
4972
4973        expected_first_set.insert("START", start_first);
4974        expected_first_set.insert("E", e_first);
4975        expected_first_set.insert("T", t_first);
4976        expected_first_set.insert("F", f_first);
4977        expected_first_set.insert("Edash", edash_first);
4978        expected_first_set.insert("Tdash", tdash_first);
4979
4980        assert!(get_first_set(&grammar).unwrap() == expected_first_set);
4981
4982        let mut expected_follow_set: FollowSet = BTreeMap::new();
4983
4984        let mut e_follow = BTreeSet::new();
4985        e_follow.insert(')');
4986
4987        let mut edash_follow = BTreeSet::new();
4988        edash_follow.insert(')');
4989
4990        let mut t_follow = BTreeSet::new();
4991        t_follow.insert('+');
4992        t_follow.insert(')');
4993
4994        let mut tdash_follow = BTreeSet::new();
4995        tdash_follow.insert('+');
4996        tdash_follow.insert(')');
4997
4998        let mut f_follow = BTreeSet::new();
4999        f_follow.insert('+');
5000        f_follow.insert('*');
5001        f_follow.insert(')');
5002
5003        expected_follow_set.insert("START", BTreeSet::new());
5004        expected_follow_set.insert("E", e_follow);
5005        expected_follow_set.insert("T", t_follow);
5006        expected_follow_set.insert("F", f_follow);
5007        expected_follow_set.insert("Edash", edash_follow);
5008        expected_follow_set.insert("Tdash", tdash_follow);
5009
5010        assert!(get_follow_set(&grammar, &expected_first_set) == expected_follow_set);
5011    }
5012
5013    #[test]
5014    fn pg_188() {
5015        let mut grammar = get_grammar();
5016        let first_set = get_first_set(&grammar).unwrap();
5017        let follow_set = get_follow_set(&grammar, &first_set);
5018
5019        let mut expected_parse_table: ParseTable = BTreeMap::new();
5020
5021        let mut start_parse = BTreeMap::new();
5022
5023        start_parse.insert(
5024            ParseTableElement::Terminal('i'),
5025            vec![RuleElement::NonTerminal("E")],
5026        );
5027
5028        start_parse.insert(
5029            ParseTableElement::Terminal('('),
5030            vec![RuleElement::NonTerminal("E")],
5031        );
5032
5033        let mut e_parse = BTreeMap::new();
5034
5035        e_parse.insert(
5036            ParseTableElement::Terminal('i'),
5037            vec![
5038                RuleElement::NonTerminal("T"),
5039                RuleElement::NonTerminal("Edash"),
5040            ],
5041        );
5042
5043        e_parse.insert(
5044            ParseTableElement::Terminal('('),
5045            vec![
5046                RuleElement::NonTerminal("T"),
5047                RuleElement::NonTerminal("Edash"),
5048            ],
5049        );
5050
5051        let mut edash_parse = BTreeMap::new();
5052
5053        edash_parse.insert(
5054            ParseTableElement::Terminal('+'),
5055            vec![
5056                RuleElement::Terminal('+'),
5057                RuleElement::NonTerminal("T"),
5058                RuleElement::NonTerminal("Edash"),
5059            ],
5060        );
5061
5062        edash_parse.insert(ParseTableElement::Terminal(')'), vec![RuleElement::Empty]);
5063
5064        edash_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
5065
5066        let mut t_parse = BTreeMap::new();
5067
5068        t_parse.insert(
5069            ParseTableElement::Terminal('i'),
5070            vec![
5071                RuleElement::NonTerminal("F"),
5072                RuleElement::NonTerminal("Tdash"),
5073            ],
5074        );
5075
5076        t_parse.insert(
5077            ParseTableElement::Terminal('('),
5078            vec![
5079                RuleElement::NonTerminal("F"),
5080                RuleElement::NonTerminal("Tdash"),
5081            ],
5082        );
5083
5084        let mut tdash_parse = BTreeMap::new();
5085
5086        tdash_parse.insert(ParseTableElement::Terminal('+'), vec![RuleElement::Empty]);
5087
5088        tdash_parse.insert(
5089            ParseTableElement::Terminal('*'),
5090            vec![
5091                RuleElement::Terminal('*'),
5092                RuleElement::NonTerminal("F"),
5093                RuleElement::NonTerminal("Tdash"),
5094            ],
5095        );
5096
5097        tdash_parse.insert(ParseTableElement::Terminal(')'), vec![RuleElement::Empty]);
5098
5099        tdash_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
5100
5101        let mut f_parse = BTreeMap::new();
5102
5103        f_parse.insert(
5104            ParseTableElement::Terminal('i'),
5105            vec![RuleElement::Terminal('i'), RuleElement::Terminal('d')],
5106        );
5107
5108        f_parse.insert(
5109            ParseTableElement::Terminal('('),
5110            vec![
5111                RuleElement::Terminal('('),
5112                RuleElement::NonTerminal("E"),
5113                RuleElement::Terminal(')'),
5114            ],
5115        );
5116
5117        expected_parse_table.insert("START", start_parse);
5118        expected_parse_table.insert("E", e_parse);
5119        expected_parse_table.insert("Edash", edash_parse);
5120        expected_parse_table.insert("T", t_parse);
5121        expected_parse_table.insert("Tdash", tdash_parse);
5122        expected_parse_table.insert("F", f_parse);
5123
5124        assert!(
5125            get_parse_table(&mut grammar, &first_set, &follow_set).unwrap() == expected_parse_table
5126        );
5127    }
5128
5129    #[test]
5130    fn parse_ok() {
5131        let mut grammar = get_grammar();
5132        let mut parser = Parser::new(&mut grammar).unwrap();
5133
5134        assert!(
5135            parser.parse("id").unwrap()
5136                == ParseTree::NonTerminal {
5137                    symbol: "START",
5138                    children: vec![ParseTree::NonTerminal {
5139                        symbol: "E",
5140                        children: vec![
5141                            ParseTree::NonTerminal {
5142                                symbol: "T",
5143                                children: vec![
5144                                    ParseTree::NonTerminal {
5145                                        symbol: "F",
5146                                        children: vec![
5147                                            ParseTree::Terminal('i'),
5148                                            ParseTree::Terminal('d'),
5149                                        ],
5150                                    },
5151                                    ParseTree::NonTerminal {
5152                                        symbol: "Tdash",
5153                                        children: vec![],
5154                                    },
5155                                ],
5156                            },
5157                            ParseTree::NonTerminal {
5158                                symbol: "Edash",
5159                                children: vec![],
5160                            },
5161                        ],
5162                    },],
5163                }
5164        );
5165    }
5166}
5167
5168#[cfg(test)]
5169mod compiler_design_in_c_1st {
5170    use super::*;
5171
5172    fn get_grammar<'a>() -> Grammar<'a> {
5173        let mut grammar = Grammar::new();
5174
5175        grammar.insert("START", vec![vec![RuleElement::NonTerminal("stmt")]]);
5176
5177        grammar.insert(
5178            "stmt",
5179            vec![vec![
5180                RuleElement::NonTerminal("expr"),
5181                RuleElement::Terminal(';'),
5182            ]],
5183        );
5184
5185        grammar.insert(
5186            "expr",
5187            vec![
5188                vec![
5189                    RuleElement::NonTerminal("term"),
5190                    RuleElement::NonTerminal("exprdash"),
5191                ],
5192                vec![RuleElement::Empty],
5193            ],
5194        );
5195
5196        grammar.insert(
5197            "exprdash",
5198            vec![
5199                vec![
5200                    RuleElement::Terminal('+'),
5201                    RuleElement::NonTerminal("term"),
5202                    RuleElement::NonTerminal("exprdash"),
5203                ],
5204                vec![RuleElement::Empty],
5205            ],
5206        );
5207
5208        grammar.insert(
5209            "term",
5210            vec![vec![
5211                RuleElement::NonTerminal("factor"),
5212                RuleElement::NonTerminal("termdash"),
5213            ]],
5214        );
5215
5216        grammar.insert(
5217            "termdash",
5218            vec![
5219                vec![
5220                    RuleElement::Terminal('*'),
5221                    RuleElement::NonTerminal("factor"),
5222                    RuleElement::NonTerminal("termdash"),
5223                ],
5224                vec![RuleElement::Empty],
5225            ],
5226        );
5227
5228        grammar.insert(
5229            "factor",
5230            vec![
5231                vec![
5232                    RuleElement::Terminal('('),
5233                    RuleElement::NonTerminal("expr"),
5234                    RuleElement::Terminal(')'),
5235                ],
5236                vec![RuleElement::Terminal('0')],
5237            ],
5238        );
5239
5240        grammar
5241    }
5242
5243    #[test]
5244    fn pg_214() {
5245        let grammar = get_grammar();
5246
5247        let mut expected_first_set = BTreeMap::new();
5248
5249        let mut start_first = BTreeSet::new();
5250        start_first.insert(FirstElement::Terminal('('));
5251        start_first.insert(FirstElement::Terminal('0'));
5252        start_first.insert(FirstElement::Terminal(';'));
5253
5254        let mut stmt_first = BTreeSet::new();
5255        stmt_first.insert(FirstElement::Terminal('('));
5256        stmt_first.insert(FirstElement::Terminal('0'));
5257        stmt_first.insert(FirstElement::Terminal(';'));
5258
5259        let mut expr_first = BTreeSet::new();
5260        expr_first.insert(FirstElement::Terminal('('));
5261        expr_first.insert(FirstElement::Terminal('0'));
5262        expr_first.insert(FirstElement::Empty);
5263
5264        let mut exprdash_first = BTreeSet::new();
5265        exprdash_first.insert(FirstElement::Terminal('+'));
5266        exprdash_first.insert(FirstElement::Empty);
5267
5268        let mut term_first = BTreeSet::new();
5269        term_first.insert(FirstElement::Terminal('('));
5270        term_first.insert(FirstElement::Terminal('0'));
5271
5272        let mut termdash_first = BTreeSet::new();
5273        termdash_first.insert(FirstElement::Terminal('*'));
5274        termdash_first.insert(FirstElement::Empty);
5275
5276        let mut factor_first = BTreeSet::new();
5277        factor_first.insert(FirstElement::Terminal('('));
5278        factor_first.insert(FirstElement::Terminal('0'));
5279
5280        expected_first_set.insert("START", start_first);
5281        expected_first_set.insert("stmt", stmt_first);
5282        expected_first_set.insert("expr", expr_first);
5283        expected_first_set.insert("exprdash", exprdash_first);
5284        expected_first_set.insert("term", term_first);
5285        expected_first_set.insert("termdash", termdash_first);
5286        expected_first_set.insert("factor", factor_first);
5287
5288        assert!(get_first_set(&grammar).unwrap() == expected_first_set);
5289    }
5290
5291    #[test]
5292    fn pg_217() {
5293        let grammar = get_grammar();
5294        let first_set = get_first_set(&grammar).unwrap();
5295
5296        let mut expected_follow_set: FollowSet = BTreeMap::new();
5297
5298        let mut expr_follow = BTreeSet::new();
5299        expr_follow.insert(')');
5300        expr_follow.insert(';');
5301
5302        let mut exprdash_follow = BTreeSet::new();
5303        exprdash_follow.insert(')');
5304        exprdash_follow.insert(';');
5305
5306        let mut term_follow = BTreeSet::new();
5307        term_follow.insert('+');
5308        term_follow.insert(';');
5309        term_follow.insert(')');
5310
5311        let mut termdash_follow = BTreeSet::new();
5312        termdash_follow.insert('+');
5313        termdash_follow.insert(';');
5314        termdash_follow.insert(')');
5315
5316        let mut factor_follow = BTreeSet::new();
5317        factor_follow.insert('*');
5318        factor_follow.insert('+');
5319        factor_follow.insert(';');
5320        factor_follow.insert(')');
5321
5322        expected_follow_set.insert("START", BTreeSet::new());
5323        expected_follow_set.insert("stmt", BTreeSet::new());
5324        expected_follow_set.insert("expr", expr_follow);
5325        expected_follow_set.insert("exprdash", exprdash_follow);
5326        expected_follow_set.insert("term", term_follow);
5327        expected_follow_set.insert("termdash", termdash_follow);
5328        expected_follow_set.insert("factor", factor_follow);
5329
5330        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
5331    }
5332
5333    #[test]
5334    fn get_parse_table_ok() {
5335        let mut grammar = get_grammar();
5336        let first_set = get_first_set(&grammar).unwrap();
5337        let follow_set = get_follow_set(&grammar, &first_set);
5338
5339        let mut expected_parse_table: ParseTable = BTreeMap::new();
5340
5341        let mut start_parse = BTreeMap::new();
5342
5343        start_parse.insert(
5344            ParseTableElement::Terminal('('),
5345            vec![RuleElement::NonTerminal("stmt")],
5346        );
5347
5348        start_parse.insert(
5349            ParseTableElement::Terminal('0'),
5350            vec![RuleElement::NonTerminal("stmt")],
5351        );
5352
5353        start_parse.insert(
5354            ParseTableElement::Terminal(';'),
5355            vec![RuleElement::NonTerminal("stmt")],
5356        );
5357
5358        let mut stmt_parse = BTreeMap::new();
5359
5360        stmt_parse.insert(
5361            ParseTableElement::Terminal('('),
5362            vec![RuleElement::NonTerminal("expr"), RuleElement::Terminal(';')],
5363        );
5364
5365        stmt_parse.insert(
5366            ParseTableElement::Terminal('0'),
5367            vec![RuleElement::NonTerminal("expr"), RuleElement::Terminal(';')],
5368        );
5369
5370        stmt_parse.insert(
5371            ParseTableElement::Terminal(';'),
5372            vec![RuleElement::NonTerminal("expr"), RuleElement::Terminal(';')],
5373        );
5374
5375        let mut stmt_parse = BTreeMap::new();
5376
5377        stmt_parse.insert(
5378            ParseTableElement::Terminal('('),
5379            vec![RuleElement::NonTerminal("expr"), RuleElement::Terminal(';')],
5380        );
5381
5382        stmt_parse.insert(
5383            ParseTableElement::Terminal('0'),
5384            vec![RuleElement::NonTerminal("expr"), RuleElement::Terminal(';')],
5385        );
5386
5387        stmt_parse.insert(
5388            ParseTableElement::Terminal(';'),
5389            vec![RuleElement::NonTerminal("expr"), RuleElement::Terminal(';')],
5390        );
5391
5392        let mut expr_parse = BTreeMap::new();
5393
5394        expr_parse.insert(
5395            ParseTableElement::Terminal('('),
5396            vec![
5397                RuleElement::NonTerminal("term"),
5398                RuleElement::NonTerminal("exprdash"),
5399            ],
5400        );
5401
5402        expr_parse.insert(
5403            ParseTableElement::Terminal('0'),
5404            vec![
5405                RuleElement::NonTerminal("term"),
5406                RuleElement::NonTerminal("exprdash"),
5407            ],
5408        );
5409
5410        expr_parse.insert(ParseTableElement::Terminal(')'), vec![RuleElement::Empty]);
5411
5412        expr_parse.insert(ParseTableElement::Terminal(';'), vec![RuleElement::Empty]);
5413
5414        expr_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
5415
5416        let mut exprdash_parse = BTreeMap::new();
5417
5418        exprdash_parse.insert(
5419            ParseTableElement::Terminal('+'),
5420            vec![
5421                RuleElement::Terminal('+'),
5422                RuleElement::NonTerminal("term"),
5423                RuleElement::NonTerminal("exprdash"),
5424            ],
5425        );
5426
5427        exprdash_parse.insert(ParseTableElement::Terminal(')'), vec![RuleElement::Empty]);
5428
5429        exprdash_parse.insert(ParseTableElement::Terminal(';'), vec![RuleElement::Empty]);
5430
5431        exprdash_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
5432
5433        let mut term_parse = BTreeMap::new();
5434
5435        term_parse.insert(
5436            ParseTableElement::Terminal('('),
5437            vec![
5438                RuleElement::NonTerminal("factor"),
5439                RuleElement::NonTerminal("termdash"),
5440            ],
5441        );
5442
5443        term_parse.insert(
5444            ParseTableElement::Terminal('0'),
5445            vec![
5446                RuleElement::NonTerminal("factor"),
5447                RuleElement::NonTerminal("termdash"),
5448            ],
5449        );
5450
5451        let mut termdash_parse = BTreeMap::new();
5452
5453        termdash_parse.insert(ParseTableElement::Terminal(')'), vec![RuleElement::Empty]);
5454
5455        termdash_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
5456
5457        termdash_parse.insert(
5458            ParseTableElement::Terminal('*'),
5459            vec![
5460                RuleElement::Terminal('*'),
5461                RuleElement::NonTerminal("factor"),
5462                RuleElement::NonTerminal("termdash"),
5463            ],
5464        );
5465
5466        termdash_parse.insert(ParseTableElement::Terminal('+'), vec![RuleElement::Empty]);
5467
5468        termdash_parse.insert(ParseTableElement::Terminal(';'), vec![RuleElement::Empty]);
5469
5470        let mut factor_parse = BTreeMap::new();
5471
5472        factor_parse.insert(
5473            ParseTableElement::Terminal('('),
5474            vec![
5475                RuleElement::Terminal('('),
5476                RuleElement::NonTerminal("expr"),
5477                RuleElement::Terminal(')'),
5478            ],
5479        );
5480
5481        factor_parse.insert(
5482            ParseTableElement::Terminal('0'),
5483            vec![RuleElement::Terminal('0')],
5484        );
5485
5486        expected_parse_table.insert("START", start_parse);
5487        expected_parse_table.insert("stmt", stmt_parse);
5488        expected_parse_table.insert("expr", expr_parse);
5489        expected_parse_table.insert("exprdash", exprdash_parse);
5490        expected_parse_table.insert("term", term_parse);
5491        expected_parse_table.insert("termdash", termdash_parse);
5492        expected_parse_table.insert("factor", factor_parse);
5493
5494        assert!(
5495            get_parse_table(&mut grammar, &first_set, &follow_set).unwrap() == expected_parse_table
5496        );
5497    }
5498
5499    #[test]
5500    fn parse_ok() {
5501        let mut grammar = get_grammar();
5502        let mut parser = Parser::new(&mut grammar).unwrap();
5503
5504        assert!(
5505            parser.parse("();").unwrap()
5506                == ParseTree::NonTerminal {
5507                    symbol: "START",
5508                    children: vec![ParseTree::NonTerminal {
5509                        symbol: "stmt",
5510                        children: vec![
5511                            ParseTree::NonTerminal {
5512                                symbol: "expr",
5513                                children: vec![
5514                                    ParseTree::NonTerminal {
5515                                        symbol: "term",
5516                                        children: vec![
5517                                            ParseTree::NonTerminal {
5518                                                symbol: "factor",
5519                                                children: vec![
5520                                                    ParseTree::Terminal('('),
5521                                                    ParseTree::NonTerminal {
5522                                                        symbol: "expr",
5523                                                        children: vec![],
5524                                                    },
5525                                                    ParseTree::Terminal(')'),
5526                                                ],
5527                                            },
5528                                            ParseTree::NonTerminal {
5529                                                symbol: "termdash",
5530                                                children: vec![],
5531                                            },
5532                                        ],
5533                                    },
5534                                    ParseTree::NonTerminal {
5535                                        symbol: "exprdash",
5536                                        children: vec![],
5537                                    },
5538                                ],
5539                            },
5540                            ParseTree::Terminal(';'),
5541                        ],
5542                    },],
5543                }
5544        );
5545    }
5546}
5547
5548#[cfg(test)]
5549mod rollup {
5550    use super::*;
5551
5552    fn set_grammar<'a>(grammar: &mut Grammar) {
5553        grammar.insert(
5554            "START",
5555            vec![vec![RuleElement::NonTerminal("one-or-more-a")]],
5556        );
5557
5558        grammar.insert(
5559            "one-or-more-a",
5560            vec![vec![
5561                RuleElement::Terminal('a'),
5562                RuleElement::NonTerminal("zero-or-more-a"),
5563            ]],
5564        );
5565
5566        grammar.insert(
5567            "zero-or-more-a",
5568            vec![
5569                vec![
5570                    RuleElement::Terminal('a'),
5571                    RuleElement::NonTerminal("zero-or-more-a"),
5572                ],
5573                vec![RuleElement::Empty],
5574            ],
5575        );
5576    }
5577
5578    #[test]
5579    pub fn no_rollup() {
5580        let mut grammar: Grammar = BTreeMap::new();
5581        set_grammar(&mut grammar);
5582
5583        let mut parser = Parser::new(&mut grammar).unwrap();
5584
5585        assert!(
5586            parser.parse("aaa").unwrap()
5587                == ParseTree::NonTerminal {
5588                    symbol: "START",
5589                    children: vec![ParseTree::NonTerminal {
5590                        symbol: "one-or-more-a",
5591                        children: vec![
5592                            ParseTree::Terminal('a'),
5593                            ParseTree::NonTerminal {
5594                                symbol: "zero-or-more-a",
5595                                children: vec![
5596                                    ParseTree::Terminal('a'),
5597                                    ParseTree::NonTerminal {
5598                                        symbol: "zero-or-more-a",
5599                                        children: vec![
5600                                            ParseTree::Terminal('a'),
5601                                            ParseTree::NonTerminal {
5602                                                symbol: "zero-or-more-a",
5603                                                children: vec![],
5604                                            },
5605                                        ],
5606                                    },
5607                                ],
5608                            },
5609                        ],
5610                    },],
5611                }
5612        );
5613    }
5614
5615    #[test]
5616    pub fn rollup() {
5617        let mut grammar: Grammar = BTreeMap::new();
5618        set_grammar(&mut grammar);
5619
5620        let mut parser = Parser::new(&mut grammar).unwrap();
5621
5622        parser.rollup(vec!["one-or-more-a", "zero-or-more-a"]);
5623
5624        assert!(
5625            parser.parse("aaa").unwrap()
5626                == ParseTree::NonTerminal {
5627                    symbol: "START",
5628                    children: vec![
5629                        ParseTree::Terminal('a'),
5630                        ParseTree::Terminal('a'),
5631                        ParseTree::Terminal('a'),
5632                    ],
5633                }
5634        );
5635    }
5636
5637    #[test]
5638    pub fn auto_rollup() {
5639        let mut grammar: Grammar = BTreeMap::new();
5640
5641        grammar.insert("START", vec![vec![RuleElement::NonTerminal("a+")]]);
5642
5643        grammar.insert(
5644            "a+",
5645            vec![vec![
5646                RuleElement::Terminal('a'),
5647                RuleElement::NonTerminal("a*"),
5648            ]],
5649        );
5650
5651        grammar.insert(
5652            "a*",
5653            vec![
5654                vec![RuleElement::Terminal('a'), RuleElement::NonTerminal("a*")],
5655                vec![RuleElement::Empty],
5656            ],
5657        );
5658
5659        let mut parser = Parser::new(&mut grammar).unwrap();
5660
5661        parser.rollup(vec!["a+", "a*"]);
5662
5663        assert!(
5664            parser.parse("aaa").unwrap()
5665                == ParseTree::NonTerminal {
5666                    symbol: "START",
5667                    children: vec![
5668                        ParseTree::Terminal('a'),
5669                        ParseTree::Terminal('a'),
5670                        ParseTree::Terminal('a'),
5671                    ],
5672                }
5673        );
5674    }
5675}