gallop 1.0.7

//! Gallop - General LL(1) parser
//!
//! # Example
//!
//! ```ignore
//! let mut grammar: Grammar = BTreeMap::new();
//!
//! grammar.insert("START", vec![
//!   vec![RuleElement::NonTerminal("a+")],
//! ]);
//!
//! grammar.insert("a+", vec![
//!   vec![RuleElement::Terminal('a'), RuleElement::NonTerminal("a*")],
//! ]);
//!
//! grammar.insert("a*", vec![
//!   vec![RuleElement::Terminal('a'), RuleElement::NonTerminal("a*")],
//!   vec![RuleElement::Empty],
//! ]);
//!
//! let mut parser = Parser::new(&mut grammar).unwrap();
//!
//! assert!(parser.parse("aaa").unwrap() == ParseTree::NonTerminal {
//!     symbol:   "START",
//!     children: vec![ParseTree::Terminal('a'), ParseTree::Terminal('a'), ParseTree::Terminal('a')],
//! });
//! ```
//!
//! # Tutorial
//!
//! We'll use the above code to explain how to use ``Gallop``, but we'll do this by stepping
//! backwards from the bottom and work our way up...
//!
//! A sucessful parsing results in a ``ParseTree``, which has the following type:
//!
//! ```ignore
//! pub enum ParseTree<'a> {
//!   Terminal(char),
//!   NonTerminal {
//!     symbol: &'a str,
//!     children: Vec<ParseTree<'a>>,
//!   }
//! }
//! ```
//!
//! - ``ParseTree::Terminal`` represents a single captured Unicode scalar value from the input.
//! - ``ParseTree::NonTerminal`` is a recursive data structure to represent the current part of the parse tree
//!
//! To parse an input string, use the ``parse()`` function from a ``Parser``:
//!
//! ```ignore
//! assert!(parser.parse("aaa").unwrap() == ParseTree::NonTerminal {
//!     symbol:   "START",
//!     children: vec![ParseTree::Terminal('a'), ParseTree::Terminal('a'), ParseTree::Terminal('a')],
//! });
//! ```
//!
//! To create a ``Parser``, pass it a reference to a ``Grammar``:
//!
//! ```ignore
//! let mut parser = Parser::new(&mut grammar).unwrap();
//! ```
//!
//! A ``Grammar`` has the following type:
//!
//! ```ignore
//! type Grammar<'a> = BTreeMap<NonTerminal<'a>, Vec<Rule<'a>>>;
//! ```
//!
//! The bare ``NonTerminal<'a>`` represents the left-hand side of a production rule, whilst
//! each element in ``Vec<Rule<'a>>`` contains the ``OR``-seperated right-hand side of a
//! production rule i.e:
//!
//! ```ignore
//! 1. a+ -> 'a' a*
//! 2. a* -> 'a' a* | ε
//! ```
//!
//! is broken down into:
//!
//! ```ignore
//! 1. a+ -> 'a' a*
//! 2. a* -> 'a' a*
//! 3. a* -> ε
//! ```
//!
//! and is represented in code by:
//!
//! ```ignore
//! grammar.insert("a+", vec![
//!   vec![RuleElement::Terminal('a'), RuleElement::NonTerminal("a*")],
//! ]);
//!
//! grammar.insert("a*", vec![
//!   vec![RuleElement::Terminal('a'), RuleElement::NonTerminal("a*")],
//!   vec![RuleElement::Empty],
//! ]);
//!
//! ```
//!
//! As you can see in that last snippet of code, ``Rule``s are ``Vec<RuleElement>``s,
//! which there are three types:
//!
//!   1. ``RuleElement::Terminal(char)`` - a single Unicode scalar value to scan against
//!   2. ``RuleElement::NonTerminal(&str)`` - an intermediary syntactic variable
//!   3. ``RuleElement::Empty``- the empty string
//!
//! The last bit of code remaining is about the ``START`` symbol, explained in the
//! following section.
//!
//! # Reserved Non-Terminals
//!
//! **The START Symbol**
//!
//! As ``Gallop`` is a top-down parser, it needs to know which of it's ``NonTerminal``s
//! is the "start" symbol. To keep things consistent, ``Gallop`` requires this to be ``START``:
//!
//! ```ignore
//! let mut grammar: Grammar = BTreeMap::new();
//!
//! grammar.insert("START", vec![
//!   ...
//! ]);
//!
//! ```
//!
//! **Convenience Non-Terminals**
//!
//! Instead of reinventing the wheel each time for commonly used tasks, there are a number of
//! convenience non-terminals already predefined. These work just like every other non-terminal
//! e.g:
//!
//! ```ignore
//! let mut country_code: Grammar = BTreeMap::new();
//!
//! country_code.insert("START", vec![
//!   vec!["two-ascii-characters"],
//! ]);
//!
//! country_code.insert("two-ascii-characters", vec![
//!   vec!["ASCII-UPPERCASE", "ASCII-UPPERCASE"],
//! ]);
//! ```
//!
//! Note: Using one of the following on the left-hand side of a ``Grammar`` rule results
//! in a ``ReservedNonTerminal`` ``GrammarError``:
//!
//! - ``ALPHABETIC`` ((0x00..0x10FFF).map(|c as char| c.is_lowercase() || c.is_uppercase())
//! - ``ALPHANUMERIC`` (``ALPHABETIC``, ``NUMERIC``)
//! - ``ASCII`` (0x00..0x7F)
//! - ``ASCII-ALPHABETIC`` (``ASCII-LOWERCASE``, ``ASCII-UPPERCASE``)
//! - ``ASCII-ALPHANUMERIC`` (``ASCII-ALPHABETIC``, ``ASCII-DIGIT``)
//! - ``ASCII-CONTROL`` (0x00..0x1F, 0x7F)
//! - ``ASCII-DIGIT`` ('0'..'9')
//! - ``ASCII-HEXDIGIT`` (``ASCII-DIGIT``, 'a'..'f', 'A'..'F')
//! - ``ASCII-HEXDIGIT-LOWERCASE`` (``ASCII-DIGIT``, 'a'..'f')
//! - ``ASCII-HEXDIGIT-UPPERCASE`` (``ASCII-DIGIT``, 'A'..'F')
//! - ``ASCII-LOWERCASE`` ('a'..'z')
//! - ``ASCII-UPPERCASE`` ('A'..'Z')
//! - ``ASCII-WHITESPACE`` (0x0020, 0x0009, 0x000A, 0x000C, 0x000D)
//! - ``CONTROL`` (0x00..0x10FFF).map(|c as char| c.is_control())
//! - ``LOWERCASE`` (0x00..0x10FFF).map(|c as char| c.is_lowercase())
//! - ``NUMERIC`` (0x00..0x10FFF).map(|c as char| c.is_numeric())
//! - ``UPPERCASE`` (0x00..0x10FFF).map(|c as char| c.is_uppercase())
//! - ``WHITESPACE`` (0x00..0x10FFF).map(|c as char| c.is_whitespace())
//!
//! # Rolling Up the Parse Tree
//!
//! When dealing with complex inputs, it's sometimes more digestible to break the grammar
//! into lots of smaller, more composable non-terminals. The drawback in doing this
//! though, is the resulting ``ParseTree`` can be really awkward to work with.
//!
//! In the following example, we'll try to parse a string containing one or more 'a'
//! characters:
//!
//! ```ignore
//! let mut grammar: Grammar = BTreeMap::new();
//!
//! grammar.insert("START", vec![
//!   vec![
//!     RuleElement::NonTerminal("one-or-more-a")
//!   ],
//! ]);
//!
//! grammar.insert("one-or-more-a", vec![
//!   vec![
//!     RuleElement::Terminal('a'),
//!     RuleElement::NonTerminal("zero-or-more-a"),
//!   ],
//! ]);
//!
//! grammar.insert("zero-or-more-a", vec![
//!   vec![
//!     RuleElement::Terminal('a'),
//!     RuleElement::NonTerminal("zero-or-more-a"),
//!   ],
//!   vec![
//!     RuleElement::Empty,
//!   ],
//! ]);
//!
//! let mut parser = Parser::new(&mut grammar).unwrap();
//!
//! assert!(parser.parse("aaa").unwrap() == ParseTree::NonTerminal {
//!     symbol:   "START",
//!     children: vec![
//!         ParseTree::NonTerminal {
//!             symbol:   "one-or-more-a",
//!             children: vec![
//!                 ParseTree::Terminal('a'),
//!                 ParseTree::NonTerminal {
//!                     symbol:   "zero-or-more-a",
//!                     children: vec![
//!                         ParseTree::Terminal('a'),
//!                         ParseTree::NonTerminal {
//!                             symbol:   "zero-or-more-a",
//!                             children: vec![
//!                                 ParseTree::Terminal('a'),
//!                                 ParseTree::NonTerminal {
//!                                     symbol:   "zero-or-more-a",
//!                                     children: vec![],
//!                                 },
//!                             ],
//!                         },
//!                     ],
//!                 },
//!             ],
//!         },
//!     ],
//! });
//!
//! ```
//!
//! Yuk! And the problem gets worse as the number of 'a' characters increases within the input string.
//! It would be nice if we could hide some of these intermediate non-terminals... this is
//! what ``rollup()`` does:
//!
//!   - Specify the ``NonTerminal``s to you want to be rolled up
//!   - When a rolled up non-terminal is found:
//!     - It's childen are promoted to siblings
//!     - The rolled up non-terminal is removed
//!
//! Here's the same example from above, but now we rollup ``one-or-more-a`` and ``zero-or-more-a``:
//!
//! ```ignore
//! let mut grammar: Grammar = BTreeMap::new();
//!
//! grammar.insert("START", vec![
//!   vec![
//!     RuleElement::NonTerminal("one-or-more-a")
//!   ],
//! ]);
//!
//! grammar.insert("one-or-more-a", vec![
//!   vec![
//!     RuleElement::Terminal('a'),
//!     RuleElement::NonTerminal("zero-or-more-a"),
//!   ],
//! ]);
//!
//! grammar.insert("zero-or-more-a", vec![
//!   vec![
//!     RuleElement::Terminal('a'),
//!     RuleElement::NonTerminal("zero-or-more-a"),
//!   ],
//!   vec![
//!     RuleElement::Empty,
//!   ],
//! ]);
//!
//! let mut parser = Parser::new(&mut grammar).unwrap();
//!
//! parser.rollup(vec![
//!     "one-or-more-a",
//!     "zero-or-more-a",
//! ]);
//!
//! assert!(parser.parse("aaa").unwrap() == ParseTree::NonTerminal {
//!     symbol:   "START",
//!     children: vec![
//!       ParseTree::Terminal('a'),
//!       ParseTree::Terminal('a'),
//!       ParseTree::Terminal('a'),
//!     ],
//! });
//!
//! ```
//!
//! Much nicer!
//!
//! **NOTE**: As a convenience, non-terminals ending with ``'*'`` and ``'+'`` are rolled up automatically:
//!
//! ```ignore
//! let mut grammar: Grammar = BTreeMap::new();
//!
//! grammar.insert("START", vec![
//!   vec![
//!     RuleElement::NonTerminal("a+")
//!   ],
//! ]);
//!
//! grammar.insert("a+", vec![
//!   vec![
//!     RuleElement::Terminal('a'),
//!     RuleElement::NonTerminal("a*"),
//!   ],
//! ]);
//!
//! grammar.insert("a*", vec![
//!   vec![
//!     RuleElement::Terminal('a'),
//!     RuleElement::NonTerminal("a*"),
//!   ],
//!   vec![
//!     RuleElement::Empty,
//!   ],
//! ]);
//!
//! let mut parser = Parser::new(&mut grammar).unwrap();
//!
//! assert!(parser.parse("aaa").unwrap() == ParseTree::NonTerminal {
//!     symbol:   "START",
//!     children: vec![
//!       ParseTree::Terminal('a'),
//!       ParseTree::Terminal('a'),
//!       ParseTree::Terminal('a'),
//!     ],
//! });
//! ```

use std::char;
use std::collections::BTreeMap;
use std::collections::BTreeSet;
use std::iter::Peekable;
use std::str::Chars;

//
// Public grammar types
//

/// The left and right hand side of the production rules
pub type Grammar<'a> = BTreeMap<NonTerminal<'a>, Vec<Rule<'a>>>;

/// An intermediary syntactic variable
pub type NonTerminal<'a> = &'a str;

/// A single Unicode scalar value
pub type Terminal = char;

/// The right-hand side of a ``Grammar`` production rule
pub type Rule<'a> = Vec<RuleElement<'a>>;

/// Elements that make up each ``Rule``
#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
pub enum RuleElement<'a> {
    /// The empty string
    Empty,
    /// An intermediary syntactic variable
    NonTerminal(&'a str),
    /// A single Unicode scalar value to scan against
    Terminal(char),
}

/// Possible errors that could happen when creating a ``Parser``
#[derive(Clone, Debug, PartialEq)]
pub enum GrammarError<'a> {
    /// The ``Grammar`` has no rules defined yet
    EmptyGrammar,
    /// The ``START`` ``Rule`` is not defined yet (see "Reserved Non-terminals" section)
    NoStartSymbol,
    /// The specified ``NonTerminal`` is actually reserved (see "Reserved Non-terminals" section)
    ReservedNonTerminal(NonTerminal<'a>),
    /// The specified ``NonTerminal`` is used within a ``Rule`` but is not defined yet
    UndefinedNonTerminal(NonTerminal<'a>),
    /// The ``Grammar`` is invalid, as specified by:
    InvalidGrammar {
        /// The offending ``NonTerminal``
        non_terminal: NonTerminal<'a>,
        /// The offending ``Rule``
        rule: Rule<'a>,
        /// The offending ``RuleElement``
        rule_element: RuleElement<'a>,
    },
    /// The ``Grammar`` has a conflict, as specified by:
    Conflict {
        /// The offending ``NonTerminal``
        non_terminal: NonTerminal<'a>,
        /// The offending ``Rule``
        rule: Rule<'a>,
        /// The offending ``RuleElement``
        rule_element: RuleElement<'a>,
    },
}

//
// Public parsing types
//

/// The results from a parsing of the input text
#[derive(Clone, Debug, PartialEq)]
pub enum ParseTree<'a> {
    /// A single captured Unicode scalar value from the input
    Terminal(char),
    /// A recursive data structure to represent the current part of the parse tree
    NonTerminal {
        /// The name of the intermediary syntactic variable found
        symbol: &'a str,
        /// A recursive ``ParseTree`` that lives under the current non-terminal
        children: Vec<ParseTree<'a>>,
    },
}

/// Possible errors that could happen during parsing
#[derive(Clone, Debug, PartialEq)]
pub enum ParseError {
    /// We expected more input
    NoMoreInput,
    /// The character at the specified index is not valid within the ``Grammar``
    InvalidInput(u64),
}

/// Holds the state of the parser for the provided ``Grammar``
#[derive(Clone, Debug, PartialEq)]
pub struct Parser<'a> {
    parse_table: ParseTable<'a>,
    rollups: BTreeSet<&'a str>,
}

//
// Public functions
//

impl<'a> Parser<'a> {
    /// Creates a ``Parser`` from the provided ``Grammar``
    ///
    /// ```ignore
    /// let parser = match Parser::new(&mut grammar) {
    ///   Ok(p)    => p,
    ///   Err(err) => panic!("Error: {:#?}", err),
    /// };
    /// ```
    pub fn new(grammar: &'a mut Grammar) -> Result<Parser<'a>, GrammarError<'a>> {
        match grammar.contains_key("START") {
            false => Err(GrammarError::NoStartSymbol),
            true => match grammar.len() > 1 {
                false => Err(GrammarError::EmptyGrammar),
                true => {
                    let reserved_non_terminals = get_reserved_non_terminals();
                    let mut reserved_non_terminals_used = BTreeSet::new();

                    for (non_terminal, rules) in grammar.iter() {
                        if reserved_non_terminals.contains_key(non_terminal) {
                            return Err(GrammarError::ReservedNonTerminal(non_terminal));
                        }

                        for rule in rules {
                            for rule_element in rule {
                                match *rule_element {
                                    RuleElement::Terminal(_) => {}
                                    RuleElement::Empty => {}
                                    RuleElement::NonTerminal(u) => {
                                        if !grammar.contains_key(u) {
                                            return Err(GrammarError::UndefinedNonTerminal(u));
                                        }

                                        if reserved_non_terminals.contains_key(u) {
                                            reserved_non_terminals_used.insert(u);
                                        }
                                    }
                                }
                            }
                        }
                    }

                    for reserved_non_terminal_used in reserved_non_terminals_used {
                        grammar.insert(
                            reserved_non_terminal_used,
                            reserved_non_terminals
                                .get(reserved_non_terminal_used)
                                .unwrap()
                                .clone(),
                        );
                    }

                    let first_set = match get_first_set(grammar) {
                        Ok(first_set) => first_set,
                        Err(err) => return Err(err),
                    };

                    let follow_set = get_follow_set(grammar, &first_set);

                    match get_parse_table(grammar, &first_set, &follow_set) {
                        Err(err) => Err(err),
                        Ok(parse_table) => Ok(Parser {
                            parse_table,
                            rollups: BTreeSet::new(),
                        }),
                    }
                }
            },
        }
    }

    /// Parse the provided string
    ///
    /// ```ignore
    /// println!("Parse tree: {:#?}", parser.parse("a test string"));
    /// ```
    pub fn parse(&mut self, input: &'a str) -> Result<ParseTree<'a>, ParseError> {
        let mut parse_tree = ParseTree::NonTerminal {
            symbol: "START",
            children: vec![],
        };

        let mut input_stack = InputStack {
            input: input.chars().peekable(),
            index: 0,
        };

        match self._parse(&mut parse_tree, &mut input_stack) {
            Some(err) => Err(err),
            None => match input_stack.input.peek().is_some() {
                true => Err(ParseError::InvalidInput(input_stack.index)),
                false => Ok(parse_tree),
            },
        }
    }

    /// Specify any non-terminals that you want rolled up (see "Rolling Up the Parse Tree" section)
    ///
    /// ```ignore
    /// parser.rollup(vec![
    ///     "digit+",
    ///     "digit*",
    /// ]);
    /// ```
    pub fn rollup(&mut self, non_terminals: Vec<NonTerminal<'a>>) {
        for i in non_terminals {
            self.rollups.insert(i);
        }
    }

    fn _parse(
        &self,
        parse_tree: &mut ParseTree<'a>,
        input_stack: &mut InputStack<'a>,
    ) -> Option<ParseError> {
        //  if current node is non-terminal
        //      get parse table entry
        //
        //      foreach rule element from parse table entry
        //          if rule element is a terminal
        //              add consumed input as a child node
        //          else
        //              add non-terminal rule element as a child node
        //              recurse

        match *parse_tree {
            ParseTree::Terminal(_) => {
                panic!("This should never happen")
            }
            ParseTree::NonTerminal {
                symbol,
                ref mut children,
            } => {
                let parse_table_entry = match input_stack.input.peek() {
                    None => {
                        match self
                            .parse_table
                            .get(symbol)
                            .unwrap()
                            .get(&ParseTableElement::Empty)
                        {
                            Some(empty) => empty,
                            None => return Some(ParseError::NoMoreInput),
                        }
                    }
                    Some(next_input) => match self
                        .parse_table
                        .get(symbol)
                        .unwrap()
                        .get(&ParseTableElement::Terminal(*next_input))
                    {
                        None => return Some(ParseError::InvalidInput(input_stack.index)),
                        Some(rule) => rule,
                    },
                };

                let current_children = children;

                for rule_element in parse_table_entry {
                    match *rule_element {
                        RuleElement::Empty => {}
                        RuleElement::Terminal(u) => match input_stack.input.next() {
                            None => return Some(ParseError::NoMoreInput),
                            Some(next_input) => {
                                match u == next_input {
                                    false => {
                                        return Some(ParseError::InvalidInput(input_stack.index))
                                    }
                                    true => current_children.push(ParseTree::Terminal(next_input)),
                                }

                                input_stack.index += 1;
                            }
                        },
                        RuleElement::NonTerminal(u) => {
                            let mut child = ParseTree::NonTerminal {
                                symbol: u,
                                children: vec![],
                            };

                            match self._parse(&mut child, input_stack) {
                                Some(error) => return Some(error),
                                None => {
                                    match self.rollups.contains(u)
                                        || u.ends_with('*')
                                        || u.ends_with('+')
                                    {
                                        false => current_children.push(child),
                                        true => match child {
                                            ParseTree::Terminal(_) => {}
                                            ParseTree::NonTerminal {
                                                ref mut children, ..
                                            } => {
                                                current_children.append(children);
                                            }
                                        },
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        None
    }
}

//
// Private parsing types
//

#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
enum ParseTableElement {
    Empty,
    Terminal(char),
}

type ParseTable<'a> = BTreeMap<NonTerminal<'a>, BTreeMap<ParseTableElement, Rule<'a>>>;

#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
enum FirstElement {
    Empty,
    Terminal(char),
}

type FirstSet<'a> = BTreeMap<NonTerminal<'a>, BTreeSet<FirstElement>>;
type FollowSet<'a> = BTreeMap<NonTerminal<'a>, BTreeSet<Terminal>>;

struct InputStack<'a> {
    input: Peekable<Chars<'a>>,
    index: u64,
}

//
// Private functions
//

fn get_first_set<'a>(grammar: &Grammar<'a>) -> Result<FirstSet<'a>, GrammarError<'a>> {
    //  while no change
    //      foreach rule A -> RHS
    //          if RHS == {Empty}
    //              FirstSet(A) += Empty
    //              continue
    //
    //          while FirstSet(Ui) derives Empty
    //              Replace Ui with U(i+1)
    //              break to next rule if no more Ui
    //
    //          if Ui is a terminal
    //              FirstSet(A) += terminal
    //              break to next rule
    //
    //          FirstSet(A) += FirstSet(Ui)

    let mut first_set: FirstSet = grammar
        .keys()
        .map(|&non_terminal| (non_terminal, BTreeSet::new()))
        .collect();

    loop {
        let mut has_changed = false;

        for (non_terminal, rules) in grammar {
            if rules.is_empty() {
                return Err(GrammarError::InvalidGrammar {
                    non_terminal,
                    rule: vec![],
                    rule_element: RuleElement::Empty,
                });
            }

            for rule in rules {
                let mut has_empty = false;

                for rule_element in rule {
                    match *rule_element {
                        RuleElement::Empty => has_empty = true,
                        RuleElement::Terminal(u) => {
                            if first_set
                                .get_mut(non_terminal)
                                .unwrap()
                                .insert(FirstElement::Terminal(u))
                            {
                                has_changed = true;
                            }

                            break;
                        }
                        RuleElement::NonTerminal(u) => match u == *non_terminal {
                            true => continue,
                            false => {
                                let mut first_rule_element_clone = match first_set.get(u) {
                                    Some(first_rule_element) => first_rule_element.clone(),
                                    None => {
                                        return Err(GrammarError::InvalidGrammar {
                                            non_terminal,
                                            rule: rule.clone(),
                                            rule_element: rule_element.clone(),
                                        })
                                    }
                                };

                                let first_non_terminal = first_set.get_mut(non_terminal).unwrap();
                                let old_length = first_non_terminal.len();

                                let has_empty =
                                    first_rule_element_clone.remove(&FirstElement::Empty);
                                first_non_terminal.extend(first_rule_element_clone);

                                if old_length != first_non_terminal.len() {
                                    has_changed = true;
                                }

                                match has_empty {
                                    true => continue,
                                    false => break,
                                }
                            }
                        },
                    }
                }

                match has_empty && (1 == rule.iter().len()) {
                    false => continue,
                    true => {
                        let first_non_terminal = first_set.get_mut(non_terminal).unwrap();

                        match first_non_terminal.contains(&FirstElement::Empty) {
                            true => continue,
                            false => {
                                first_non_terminal.insert(FirstElement::Empty);
                                has_changed = true;
                            }
                        }
                    }
                }
            }
        }

        match has_changed {
            true => continue,
            false => break,
        }
    }

    Ok(first_set)
}

fn get_follow_set<'a>(grammar: &Grammar<'a>, first_set: &FirstSet<'a>) -> FollowSet<'a> {
    //  while no change
    //      foreach rule where we have A => ...By...
    //          FollowSet(B) += FirstSet(y)
    //
    //          if y derives or *is* Empty
    //              FollowSet(B) += FollowSet(A)

    let mut follow_set: FollowSet = grammar
        .keys()
        .map(|&non_terminal| (non_terminal, BTreeSet::new()))
        .collect();

    loop {
        let mut has_changed = false;

        for (non_terminal, rules) in grammar {
            let follow_non_terminal = follow_set.get(non_terminal).unwrap().clone();

            for rule in rules {
                for (i, rule_element_b) in rule.iter().enumerate() {
                    match *rule_element_b {
                        RuleElement::Empty => {}
                        RuleElement::Terminal(_) => {}
                        RuleElement::NonTerminal(b) => {
                            let follow_rule_element_b = follow_set.get_mut(&b).unwrap();
                            let mut extend_from_empty = false;

                            for rule_element_y in rule.iter().skip(i + 1) {
                                match *rule_element_y {
                                    RuleElement::Empty => {}
                                    RuleElement::Terminal(y) => {
                                        if follow_rule_element_b.insert(y) {
                                            has_changed = true;
                                        }

                                        break;
                                    }
                                    RuleElement::NonTerminal(y) => {
                                        let mut first_rule_element_y =
                                            first_set.get(y).unwrap().clone();

                                        let has_empty = first_rule_element_y
                                            .remove(&FirstElement::Empty)
                                            || first_rule_element_y.is_empty();

                                        for first_y in first_rule_element_y {
                                            match first_y {
                                                FirstElement::Empty => {}
                                                FirstElement::Terminal(fy) => {
                                                    match follow_rule_element_b.insert(fy) {
                                                        true => has_changed = true,
                                                        false => continue,
                                                    }
                                                }
                                            }
                                        }

                                        match has_empty {
                                            true => extend_from_empty = true,
                                            false => break,
                                        }
                                    }
                                }
                            }

                            match extend_from_empty || (i + 1) == rule.iter().len() {
                                true => follow_rule_element_b.extend(follow_non_terminal.clone()),
                                false => continue,
                            }
                        }
                    }
                }
            }
        }

        match has_changed {
            true => continue,
            false => break,
        }
    }

    follow_set
}

fn get_parse_table<'a>(
    grammar: &Grammar<'a>,
    first_set: &FirstSet<'a>,
    follow_set: &FollowSet<'a>,
) -> Result<ParseTable<'a>, GrammarError<'a>> {
    //  foreach rule A -> RHS
    //      foreach terminal a in FirstSet(RHS)
    //          [A, a] = RHS
    //
    //      if RHS is, or derives, Empty
    //          foreach terminal a in FollowSet(A)
    //              [A, a] = RHS

    let mut parse_table: ParseTable = grammar
        .keys()
        .map(|&non_terminal| (non_terminal, BTreeMap::new()))
        .collect();

    for (non_terminal, rules) in grammar {
        let parse_table_non_terminal = parse_table.get_mut(non_terminal).unwrap();
        let follow_non_terminal = follow_set.get(non_terminal).unwrap();

        for rule in rules {
            let mut extend_from_empty = false;

            for rule_element in rule {
                match *rule_element {
                    RuleElement::Empty => extend_from_empty = true,
                    RuleElement::Terminal(u) => {
                        match parse_table_non_terminal
                            .insert(ParseTableElement::Terminal(u), rule.clone())
                            .is_some()
                        {
                            false => break,
                            true => {
                                return Err(GrammarError::Conflict {
                                    non_terminal,
                                    rule: rule.clone(),
                                    rule_element: rule_element.clone(),
                                })
                            }
                        }
                    }
                    RuleElement::NonTerminal(u) => {
                        let mut first_rule_element = first_set.get(u).unwrap().clone();
                        let has_empty = first_rule_element.remove(&FirstElement::Empty);

                        for first_u in first_rule_element {
                            match first_u {
                                FirstElement::Empty => {}
                                FirstElement::Terminal(fu) => {
                                    match parse_table_non_terminal
                                        .insert(ParseTableElement::Terminal(fu), rule.clone())
                                        .is_some()
                                    {
                                        false => continue,
                                        true => {
                                            return Err(GrammarError::Conflict {
                                                non_terminal,
                                                rule: rule.clone(),
                                                rule_element: rule_element.clone(),
                                            })
                                        }
                                    }
                                }
                            }
                        }

                        match has_empty {
                            true => continue,
                            false => break,
                        }
                    }
                }
            }

            match extend_from_empty {
                false => continue,
                true => {
                    for follow_u in follow_non_terminal {
                        match parse_table_non_terminal
                            .insert(ParseTableElement::Terminal(*follow_u), rule.clone())
                            .is_some()
                        {
                            false => continue,
                            true => {
                                return Err(GrammarError::Conflict {
                                    non_terminal,
                                    rule: rule.clone(),
                                    rule_element: RuleElement::Empty,
                                })
                            }
                        }
                    }
                }
            }

            let first_non_terminal = first_set.get(non_terminal).unwrap();

            if first_non_terminal.contains(&FirstElement::Empty) {
                parse_table_non_terminal.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
            }
        }
    }

    Ok(parse_table)
}

fn get_reserved_non_terminals<'a>() -> BTreeMap<NonTerminal<'a>, Vec<Rule<'a>>> {
    let mut reserved_non_terminals = BTreeMap::new();

    reserved_non_terminals.insert("ASCII", get_reserved_ascii());
    reserved_non_terminals.insert("ASCII-CONTROL", get_reserved_ascii_control());
    reserved_non_terminals.insert("ASCII-WHITESPACE", get_reserved_ascii_whitespace());
    reserved_non_terminals.insert("ASCII-DIGIT", get_reserved_ascii_digit());
    reserved_non_terminals.insert("ASCII-LOWERCASE", get_reserved_ascii_lowercase());
    reserved_non_terminals.insert("ASCII-UPPERCASE", get_reserved_ascii_uppercase());
    reserved_non_terminals.insert("ASCII-ALPHABETIC", get_reserved_ascii_alphabetic());
    reserved_non_terminals.insert("ASCII-ALPHANUMERIC", get_reserved_ascii_alphanumeric());
    reserved_non_terminals.insert(
        "ASCII-HEXDIGIT-LOWERCASE",
        get_reserved_ascii_hexdigit_lowercase(),
    );
    reserved_non_terminals.insert(
        "ASCII-HEXDIGIT-UPPERCASE",
        get_reserved_ascii_hexdigit_uppercase(),
    );
    reserved_non_terminals.insert("ASCII-HEXDIGIT", get_reserved_ascii_hexdigit());
    reserved_non_terminals.insert("CONTROL", get_reserved_control());
    reserved_non_terminals.insert("WHITESPACE", get_reserved_whitespace());
    reserved_non_terminals.insert("NUMERIC", get_reserved_numeric());
    reserved_non_terminals.insert("LOWERCASE", get_reserved_lowercase());
    reserved_non_terminals.insert("UPPERCASE", get_reserved_uppercase());
    reserved_non_terminals.insert("ALPHABETIC", get_reserved_alphabetic());
    reserved_non_terminals.insert("ALPHANUMERIC", get_reserved_alphanumeric());

    reserved_non_terminals
}

fn get_reserved_ascii<'a>() -> Vec<Vec<RuleElement<'a>>> {
    (0x0..(0x7f + 1u8))
        .into_iter()
        .map(|c| vec![RuleElement::Terminal(c as char)])
        .collect()
}

fn get_reserved_ascii_control<'a>() -> Vec<Vec<RuleElement<'a>>> {
    let mut characters: Vec<Vec<RuleElement<'a>>> = (0x0..(0x1f + 1u8))
        .into_iter()
        .map(|c| vec![RuleElement::Terminal(c as char)])
        .collect();

    characters.push(vec![RuleElement::Terminal(0x7f as char)]);

    characters
}

fn get_reserved_ascii_whitespace<'a>() -> Vec<Vec<RuleElement<'a>>> {
    ['\u{0020}', '\u{0009}', '\u{000a}', '\u{000c}', '\u{000d}']
        .iter()
        .map(|c| vec![RuleElement::Terminal(*c)])
        .collect()
}

fn get_reserved_ascii_digit<'a>() -> Vec<Vec<RuleElement<'a>>> {
    (b'0'..(b'9' + 1u8))
        .into_iter()
        .map(|c| vec![RuleElement::Terminal(c as char)])
        .collect()
}

fn get_reserved_ascii_lowercase<'a>() -> Vec<Vec<RuleElement<'a>>> {
    (b'a'..(b'z' + 1u8))
        .into_iter()
        .map(|c| vec![RuleElement::Terminal(c as char)])
        .collect()
}

fn get_reserved_ascii_uppercase<'a>() -> Vec<Vec<RuleElement<'a>>> {
    (b'A'..(b'Z' + 1u8))
        .into_iter()
        .map(|c| vec![RuleElement::Terminal(c as char)])
        .collect()
}

fn get_reserved_ascii_alphabetic<'a>() -> Vec<Vec<RuleElement<'a>>> {
    let mut characters = vec![];

    characters.append(&mut get_reserved_ascii_lowercase().clone());
    characters.append(&mut get_reserved_ascii_uppercase().clone());

    characters
}

fn get_reserved_ascii_alphanumeric<'a>() -> Vec<Vec<RuleElement<'a>>> {
    let mut characters: Vec<Vec<RuleElement>> = Vec::new();

    characters.append(&mut get_reserved_ascii_alphabetic().clone());
    characters.append(&mut get_reserved_ascii_digit().clone());

    characters
}

fn get_reserved_ascii_hexdigit_lowercase<'a>() -> Vec<Vec<RuleElement<'a>>> {
    let mut characters: Vec<Vec<RuleElement<'a>>> = (b'a'..(b'f' + 1u8))
        .into_iter()
        .map(|c| vec![RuleElement::Terminal(c as char)])
        .collect();

    characters.append(&mut get_reserved_ascii_digit().clone());

    characters
}

fn get_reserved_ascii_hexdigit_uppercase<'a>() -> Vec<Vec<RuleElement<'a>>> {
    let mut characters: Vec<Vec<RuleElement<'a>>> = (b'A'..(b'F' + 1u8))
        .into_iter()
        .map(|c| vec![RuleElement::Terminal(c as char)])
        .collect();

    characters.append(&mut get_reserved_ascii_digit().clone());

    characters
}

fn get_reserved_ascii_hexdigit<'a>() -> Vec<Vec<RuleElement<'a>>> {
    let mut characters: Vec<Vec<RuleElement>> = Vec::new();

    characters.append(&mut get_reserved_ascii_digit().clone());

    characters.append(
        &mut (b'a'..(b'f' + 1u8))
            .into_iter()
            .map(|c| vec![RuleElement::Terminal(c as char)])
            .collect(),
    );

    characters.append(
        &mut (b'A'..(b'F' + 1u8))
            .into_iter()
            .map(|c| vec![RuleElement::Terminal(c as char)])
            .collect(),
    );

    characters
}

fn get_reserved_control<'a>() -> Vec<Vec<RuleElement<'a>>> {
    (0x0..(0x10FFFF + 1))
        .into_iter()
        .filter_map(char::from_u32)
        .filter(|c| (*c).is_control())
        .map(|c| vec![RuleElement::Terminal(c as char)])
        .collect()
}

fn get_reserved_whitespace<'a>() -> Vec<Vec<RuleElement<'a>>> {
    (0x0..(0x10FFFF + 1))
        .into_iter()
        .filter_map(char::from_u32)
        .filter(|c| (*c).is_whitespace())
        .map(|c| vec![RuleElement::Terminal(c as char)])
        .collect()
}

fn get_reserved_numeric<'a>() -> Vec<Vec<RuleElement<'a>>> {
    (0x0..(0x10FFFF + 1))
        .into_iter()
        .filter_map(char::from_u32)
        .filter(|c| (*c).is_numeric())
        .map(|c| vec![RuleElement::Terminal(c as char)])
        .collect()
}

fn get_reserved_lowercase<'a>() -> Vec<Vec<RuleElement<'a>>> {
    (0x0..(0x10FFFF + 1))
        .into_iter()
        .filter_map(char::from_u32)
        .filter(|c| (*c).is_lowercase())
        .map(|c| vec![RuleElement::Terminal(c as char)])
        .collect()
}

fn get_reserved_uppercase<'a>() -> Vec<Vec<RuleElement<'a>>> {
    (0x0..(0x10FFFF + 1))
        .into_iter()
        .filter_map(char::from_u32)
        .filter(|c| (*c).is_uppercase())
        .map(|c| vec![RuleElement::Terminal(c as char)])
        .collect()
}

fn get_reserved_alphabetic<'a>() -> Vec<Vec<RuleElement<'a>>> {
    let mut characters: Vec<Vec<RuleElement>> = Vec::new();

    characters.append(&mut get_reserved_lowercase().clone());
    characters.append(&mut get_reserved_uppercase().clone());

    characters
}

fn get_reserved_alphanumeric<'a>() -> Vec<Vec<RuleElement<'a>>> {
    let mut characters: Vec<Vec<RuleElement>> = Vec::new();

    characters.append(&mut get_reserved_alphabetic().clone());
    characters.append(&mut get_reserved_numeric().clone());

    characters
}

#[cfg(test)]
mod new {
    use super::*;

    #[test]
    fn no_start_symbol() {
        let mut grammar = Grammar::new();

        match Parser::new(&mut grammar) {
            Ok(_) => panic!(),
            Err(err) => assert!(err == GrammarError::NoStartSymbol),
        }
    }

    #[test]
    fn empty_grammar() {
        let mut grammar = Grammar::new();
        grammar.insert("START", vec![]);

        match Parser::new(&mut grammar) {
            Err(err) => assert!(err == GrammarError::EmptyGrammar),
            Ok(_) => panic!(),
        }
    }

    #[test]
    fn bad_parse_table() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![
                vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')],
                vec![RuleElement::Terminal('a'), RuleElement::Terminal('c')],
            ],
        );

        match Parser::new(&mut grammar) {
            Ok(_) => panic!(),
            Err(err) => assert!(
                err == GrammarError::Conflict {
                    non_terminal: "A",
                    rule: vec![RuleElement::Terminal('a'), RuleElement::Terminal('c')],
                    rule_element: RuleElement::Terminal('a'),
                }
            ),
        }
    }

    #[test]
    fn ok() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')]],
        );

        match Parser::new(&mut grammar) {
            Err(_) => panic!(),
            Ok(parser) => {
                let mut start_rules = BTreeMap::new();
                start_rules.insert(
                    ParseTableElement::Terminal('a'),
                    vec![RuleElement::NonTerminal("A")],
                );

                let mut a_rules = BTreeMap::new();
                a_rules.insert(
                    ParseTableElement::Terminal('a'),
                    vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')],
                );

                let mut expected_parse_table = BTreeMap::new();
                expected_parse_table.insert("START", start_rules);
                expected_parse_table.insert("A", a_rules);

                assert!(
                    parser
                        == Parser {
                            parse_table: expected_parse_table,
                            rollups: BTreeSet::new(),
                        }
                );
            }
        }
    }
}

#[cfg(test)]
mod parse {
    use super::*;

    #[test]
    fn no_more_input() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')]],
        );

        let mut parser = Parser::new(&mut grammar).unwrap();

        match parser.parse("") {
            Ok(_) => panic!(),
            Err(err) => assert!(err == ParseError::NoMoreInput),
        }
    }

    #[test]
    fn invalid_input() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')]],
        );

        let mut parser = Parser::new(&mut grammar).unwrap();

        match parser.parse("abb") {
            Ok(_) => panic!(),
            Err(err) => assert!(err == ParseError::InvalidInput(2)),
        }
    }

    #[test]
    fn ok() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')]],
        );

        let mut parser = Parser::new(&mut grammar).unwrap();

        match parser.parse("ab") {
            Err(_) => panic!(),
            Ok(parse_tree) => assert!(
                parse_tree
                    == ParseTree::NonTerminal {
                        symbol: "START",
                        children: vec![ParseTree::NonTerminal {
                            symbol: "A",
                            children: vec![ParseTree::Terminal('a'), ParseTree::Terminal('b'),],
                        },],
                    }
            ),
        }
    }
}

#[cfg(test)]
mod _parse {
    use super::*;

    #[test]
    #[should_panic]
    fn panic_on_terminal() {
        // in reality, this should never happen as we only ever enter _parse() on non-terminals

        let mut start_rules = BTreeMap::new();
        start_rules.insert(
            ParseTableElement::Terminal('a'),
            vec![RuleElement::Terminal('b')],
        );

        let mut parse_table = BTreeMap::new();
        parse_table.insert("START", start_rules);

        let parser = Parser {
            parse_table: parse_table,
            rollups: BTreeSet::new(),
        };

        let mut parse_tree = ParseTree::Terminal('a');
        let mut input_stack = InputStack {
            input: "a".chars().peekable(),
            index: 0,
        };

        match parser._parse(&mut parse_tree, &mut input_stack) {
            _ => {}
        }
    }

    #[test]
    fn no_input() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')]],
        );

        let mut parser = Parser::new(&mut grammar).unwrap();

        match parser.parse("") {
            Ok(_) => panic!(),
            Err(err) => assert!(err == ParseError::NoMoreInput),
        }
    }

    #[test]
    fn invalid_input() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')]],
        );

        let mut parser = Parser::new(&mut grammar).unwrap();

        match parser.parse("c") {
            Ok(_) => panic!(),
            Err(err) => assert!(err == ParseError::InvalidInput(0)),
        }
    }

    #[test]
    fn no_more_input() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')]],
        );

        let mut parser = Parser::new(&mut grammar).unwrap();

        match parser.parse("a") {
            Ok(_) => panic!(),
            Err(err) => assert!(err == ParseError::NoMoreInput),
        }
    }

    #[test]
    fn invalid_wrong_terminal() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('a'),
                RuleElement::Terminal('b'),
                RuleElement::Terminal('c'),
            ]],
        );

        let mut parser = Parser::new(&mut grammar).unwrap();

        match parser.parse("abd") {
            Ok(_) => panic!(),
            Err(err) => assert!(err == ParseError::InvalidInput(2)),
        }
    }

    #[test]
    fn invalid_wrong_terminal_recursed() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('a'),
                RuleElement::NonTerminal("B"),
                RuleElement::Terminal('c'),
            ]],
        );

        grammar.insert(
            "B",
            vec![vec![RuleElement::Terminal('d'), RuleElement::Terminal('e')]],
        );

        let mut parser = Parser::new(&mut grammar).unwrap();

        match parser.parse("adfc") {
            Ok(_) => panic!(),
            Err(err) => assert!(err == ParseError::InvalidInput(2)),
        }
    }

    #[test]
    fn ok() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('a'),
                RuleElement::NonTerminal("B"),
                RuleElement::Terminal('c'),
            ]],
        );

        grammar.insert(
            "B",
            vec![vec![RuleElement::Terminal('d'), RuleElement::Terminal('e')]],
        );

        let mut parser = Parser::new(&mut grammar).unwrap();

        match parser.parse("adec") {
            Err(_) => panic!(),
            Ok(parse_tree) => assert!(
                parse_tree
                    == ParseTree::NonTerminal {
                        symbol: "START",
                        children: vec![ParseTree::NonTerminal {
                            symbol: "A",
                            children: vec![
                                ParseTree::Terminal('a'),
                                ParseTree::NonTerminal {
                                    symbol: "B",
                                    children: vec![
                                        ParseTree::Terminal('d'),
                                        ParseTree::Terminal('e'),
                                    ],
                                },
                                ParseTree::Terminal('c'),
                            ],
                        },],
                    }
            ),
        }
    }
}

#[cfg(test)]
mod get_first_set {
    use super::*;

    #[test]
    fn is_empty() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert("A", vec![]);

        match get_first_set(&grammar) {
            Ok(_) => panic!(),
            Err(err) => assert!(
                err == GrammarError::InvalidGrammar {
                    non_terminal: "A",
                    rule: vec![],
                    rule_element: RuleElement::Empty,
                }
            ),
        }
    }

    #[test]
    fn matching_non_terminal() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert("A", vec![vec![RuleElement::NonTerminal("A")]]);

        match get_first_set(&grammar) {
            Err(_) => panic!(),
            Ok(first_set) => {
                let mut expected_first_set = BTreeMap::new();

                expected_first_set.insert("START", BTreeSet::new());
                expected_first_set.insert("A", BTreeSet::new());

                assert!(first_set == expected_first_set);
            }
        }
    }

    #[test]
    fn invalid_grammar() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert("A", vec![vec![RuleElement::NonTerminal("B")]]);

        match get_first_set(&grammar) {
            Ok(_) => panic!(),
            Err(err) => assert!(
                err == GrammarError::InvalidGrammar {
                    non_terminal: "A",
                    rule: vec![RuleElement::NonTerminal("B")],
                    rule_element: RuleElement::NonTerminal("B"),
                }
            ),
        }
    }

    #[test]
    fn combo_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert("A", vec![vec![RuleElement::Empty]]);

        match get_first_set(&grammar) {
            Err(_) => panic!(),
            Ok(first_set) => {
                let mut expected_first_set: FirstSet = BTreeMap::new();

                let mut a_first = BTreeSet::new();
                a_first.insert(FirstElement::Empty);

                expected_first_set.insert("START", BTreeSet::new());
                expected_first_set.insert("A", a_first);

                assert!(first_set == expected_first_set);
            }
        }
    }

    #[test]
    fn combo_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert("A", vec![vec![RuleElement::Terminal('a')]]);

        match get_first_set(&grammar) {
            Err(_) => panic!(),
            Ok(first_set) => {
                let mut expected_first_set = BTreeMap::new();

                let mut start_first = BTreeSet::new();
                start_first.insert(FirstElement::Terminal('a'));

                let mut a_first = BTreeSet::new();
                a_first.insert(FirstElement::Terminal('a'));

                expected_first_set.insert("START", start_first);
                expected_first_set.insert("A", a_first);

                assert!(first_set == expected_first_set);
            }
        }
    }

    #[test]
    fn combo_et() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Empty, RuleElement::Terminal('b')]],
        );

        match get_first_set(&grammar) {
            Err(_) => panic!(),
            Ok(first_set) => {
                let mut expected_first_set = BTreeMap::new();

                let mut start_first = BTreeSet::new();
                start_first.insert(FirstElement::Terminal('b'));

                let mut a_first = BTreeSet::new();
                a_first.insert(FirstElement::Terminal('b'));

                expected_first_set.insert("START", start_first);
                expected_first_set.insert("A", a_first);

                assert!(first_set == expected_first_set);
            }
        }
    }

    #[test]
    fn combo_ene() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Empty, RuleElement::NonTerminal("B")]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        match get_first_set(&grammar) {
            Err(_) => panic!(),
            Ok(first_set) => {
                let mut expected_first_set = BTreeMap::new();

                let mut b_first = BTreeSet::new();
                b_first.insert(FirstElement::Empty);

                expected_first_set.insert("START", BTreeSet::new());
                expected_first_set.insert("A", BTreeSet::new());
                expected_first_set.insert("B", b_first);

                assert!(first_set == expected_first_set);
            }
        }
    }

    #[test]
    fn combo_ent() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Empty, RuleElement::NonTerminal("B")]],
        );

        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);

        match get_first_set(&grammar) {
            Err(_) => panic!(),
            Ok(first_set) => {
                let mut expected_first_set = BTreeMap::new();

                let mut start_first = BTreeSet::new();
                start_first.insert(FirstElement::Terminal('c'));

                let mut a_first = BTreeSet::new();
                a_first.insert(FirstElement::Terminal('c'));

                let mut b_first = BTreeSet::new();
                b_first.insert(FirstElement::Terminal('c'));

                expected_first_set.insert("START", start_first);
                expected_first_set.insert("A", a_first);
                expected_first_set.insert("B", b_first);

                assert!(first_set == expected_first_set);
            }
        }
    }

    #[test]
    fn combo_te() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Terminal('a'), RuleElement::Empty]],
        );

        match get_first_set(&grammar) {
            Err(_) => panic!(),
            Ok(first_set) => {
                let mut expected_first_set = BTreeMap::new();

                let mut start_first = BTreeSet::new();
                start_first.insert(FirstElement::Terminal('a'));

                let mut a_first = BTreeSet::new();
                a_first.insert(FirstElement::Terminal('a'));

                expected_first_set.insert("START", start_first);
                expected_first_set.insert("A", a_first);

                assert!(first_set == expected_first_set);
            }
        }
    }

    #[test]
    fn combo_tt() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Terminal('a'), RuleElement::Terminal('b')]],
        );

        match get_first_set(&grammar) {
            Err(_) => panic!(),
            Ok(first_set) => {
                let mut expected_first_set = BTreeMap::new();

                let mut start_first = BTreeSet::new();
                start_first.insert(FirstElement::Terminal('a'));

                let mut a_first = BTreeSet::new();
                a_first.insert(FirstElement::Terminal('a'));

                expected_first_set.insert("START", start_first);
                expected_first_set.insert("A", a_first);

                assert!(first_set == expected_first_set);
            }
        }
    }

    #[test]
    fn combo_tn() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('a'),
                RuleElement::NonTerminal("B"),
            ]],
        );

        grammar.insert("B", vec![vec![]]);

        match get_first_set(&grammar) {
            Err(_) => panic!(),
            Ok(first_set) => {
                let mut expected_first_set = BTreeMap::new();

                let mut start_first = BTreeSet::new();
                start_first.insert(FirstElement::Terminal('a'));

                let mut a_first = BTreeSet::new();
                a_first.insert(FirstElement::Terminal('a'));

                expected_first_set.insert("START", start_first);
                expected_first_set.insert("A", a_first);
                expected_first_set.insert("B", BTreeSet::new());

                assert!(first_set == expected_first_set);
            }
        }
    }

    #[test]
    fn combo_tne() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('a'),
                RuleElement::NonTerminal("B"),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        match get_first_set(&grammar) {
            Err(_) => panic!(),
            Ok(first_set) => {
                let mut expected_first_set = BTreeMap::new();

                let mut start_first = BTreeSet::new();
                start_first.insert(FirstElement::Terminal('a'));

                let mut a_first = BTreeSet::new();
                a_first.insert(FirstElement::Terminal('a'));

                let mut b_first = BTreeSet::new();
                b_first.insert(FirstElement::Empty);

                expected_first_set.insert("START", start_first);
                expected_first_set.insert("A", a_first);
                expected_first_set.insert("B", b_first);

                assert!(first_set == expected_first_set);
            }
        }
    }

    #[test]
    fn combo_tnt() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('a'),
                RuleElement::NonTerminal("B"),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);

        match get_first_set(&grammar) {
            Err(_) => panic!(),
            Ok(first_set) => {
                let mut expected_first_set = BTreeMap::new();

                let mut start_first = BTreeSet::new();
                start_first.insert(FirstElement::Terminal('a'));

                let mut a_first = BTreeSet::new();
                a_first.insert(FirstElement::Terminal('a'));

                let mut b_first = BTreeSet::new();
                b_first.insert(FirstElement::Terminal('c'));

                expected_first_set.insert("START", start_first);
                expected_first_set.insert("A", a_first);
                expected_first_set.insert("B", b_first);

                assert!(first_set == expected_first_set);
            }
        }
    }

    #[test]
    fn combo_ne_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::NonTerminal("B"), RuleElement::Empty]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        match get_first_set(&grammar) {
            Err(_) => panic!(),
            Ok(first_set) => {
                let mut expected_first_set = BTreeMap::new();

                let mut b_first = BTreeSet::new();
                b_first.insert(FirstElement::Empty);

                expected_first_set.insert("START", BTreeSet::new());
                expected_first_set.insert("A", BTreeSet::new());
                expected_first_set.insert("B", b_first);

                assert!(first_set == expected_first_set);
            }
        }
    }

    #[test]
    fn combo_nt_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::NonTerminal("B"), RuleElement::Empty]],
        );

        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);

        match get_first_set(&grammar) {
            Err(_) => panic!(),
            Ok(first_set) => {
                let mut expected_first_set = BTreeMap::new();

                let mut start_first = BTreeSet::new();
                start_first.insert(FirstElement::Terminal('c'));

                let mut a_first = BTreeSet::new();
                a_first.insert(FirstElement::Terminal('c'));

                let mut b_first = BTreeSet::new();
                b_first.insert(FirstElement::Terminal('c'));

                expected_first_set.insert("START", start_first);
                expected_first_set.insert("A", a_first);
                expected_first_set.insert("B", b_first);

                assert!(first_set == expected_first_set);
            }
        }
    }

    #[test]
    fn combo_ne_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::Terminal('c'),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        match get_first_set(&grammar) {
            Err(_) => panic!(),
            Ok(first_set) => {
                let mut expected_first_set = BTreeMap::new();

                let mut start_first = BTreeSet::new();
                start_first.insert(FirstElement::Terminal('c'));

                let mut a_first = BTreeSet::new();
                a_first.insert(FirstElement::Terminal('c'));

                let mut b_first = BTreeSet::new();
                b_first.insert(FirstElement::Empty);

                expected_first_set.insert("START", start_first);
                expected_first_set.insert("A", a_first);
                expected_first_set.insert("B", b_first);

                assert!(first_set == expected_first_set);
            }
        }
    }

    #[test]
    fn combo_nt_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::Terminal('c'),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Terminal('d')]]);

        match get_first_set(&grammar) {
            Err(_) => panic!(),
            Ok(first_set) => {
                let mut expected_first_set = BTreeMap::new();

                let mut start_first = BTreeSet::new();
                start_first.insert(FirstElement::Terminal('d'));

                let mut a_first = BTreeSet::new();
                a_first.insert(FirstElement::Terminal('d'));

                let mut b_first = BTreeSet::new();
                b_first.insert(FirstElement::Terminal('d'));

                expected_first_set.insert("START", start_first);
                expected_first_set.insert("A", a_first);
                expected_first_set.insert("B", b_first);

                assert!(first_set == expected_first_set);
            }
        }
    }
}

#[cfg(test)]
mod get_follow_set {
    use super::*;

    #[test]
    fn combo_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert("A", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert("A", vec![vec![RuleElement::Terminal('b')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_n_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert("A", vec![vec![RuleElement::NonTerminal("B")]]);

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_n_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert("A", vec![vec![RuleElement::NonTerminal("B")]]);

        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_ee() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert("A", vec![vec![RuleElement::Empty, RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_et() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Empty, RuleElement::Terminal('b')]],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_en_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Empty, RuleElement::NonTerminal("B")]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_en_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Empty, RuleElement::NonTerminal("B")]],
        );

        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_eee() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Empty,
                RuleElement::Empty,
                RuleElement::Empty,
            ]],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_eet() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Empty,
                RuleElement::Empty,
                RuleElement::Terminal('b'),
            ]],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_een_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Empty,
                RuleElement::Empty,
                RuleElement::NonTerminal("B"),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_een_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Empty,
                RuleElement::Empty,
                RuleElement::NonTerminal("B"),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_ete() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Empty,
                RuleElement::Terminal('b'),
                RuleElement::Empty,
            ]],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_ett() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Empty,
                RuleElement::Terminal('b'),
                RuleElement::Terminal('c'),
            ]],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_etn_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Empty,
                RuleElement::Terminal('b'),
                RuleElement::NonTerminal("C"),
            ]],
        );

        grammar.insert("C", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("C", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_etn_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Empty,
                RuleElement::Terminal('b'),
                RuleElement::NonTerminal("C"),
            ]],
        );

        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("C", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_ene_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Empty,
                RuleElement::NonTerminal("B"),
                RuleElement::Empty,
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_ene_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Empty,
                RuleElement::NonTerminal("B"),
                RuleElement::Empty,
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_ent_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Empty,
                RuleElement::NonTerminal("B"),
                RuleElement::Terminal('c'),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        let mut b_follow = BTreeSet::new();
        b_follow.insert('c');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", b_follow);

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_ent_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Empty,
                RuleElement::NonTerminal("B"),
                RuleElement::Terminal('c'),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Terminal('d')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        let mut b_follow = BTreeSet::new();
        b_follow.insert('c');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", b_follow);

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_enn_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Empty,
                RuleElement::NonTerminal("B"),
                RuleElement::NonTerminal("C"),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        grammar.insert("C", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", BTreeSet::new());
        expected_follow_set.insert("C", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_enn_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Empty,
                RuleElement::NonTerminal("B"),
                RuleElement::NonTerminal("C"),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        let mut b_follow = BTreeSet::new();
        b_follow.insert('d');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", b_follow);
        expected_follow_set.insert("C", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_te() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Terminal('b'), RuleElement::Empty]],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_tt() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Terminal('b'), RuleElement::Terminal('c')]],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_tn_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('b'),
                RuleElement::NonTerminal("C"),
            ]],
        );

        grammar.insert("C", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("C", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_tn_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('b'),
                RuleElement::NonTerminal("C"),
            ]],
        );

        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("C", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_tee() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('b'),
                RuleElement::Empty,
                RuleElement::Empty,
            ]],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_tet() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('b'),
                RuleElement::Empty,
                RuleElement::Terminal('c'),
            ]],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_ten_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('b'),
                RuleElement::Empty,
                RuleElement::NonTerminal("C"),
            ]],
        );

        grammar.insert("C", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("C", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_ten_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('b'),
                RuleElement::Empty,
                RuleElement::NonTerminal("C"),
            ]],
        );

        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("C", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_tte() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('b'),
                RuleElement::Terminal('c'),
                RuleElement::Empty,
            ]],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_ttt() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('b'),
                RuleElement::Terminal('c'),
                RuleElement::Terminal('d'),
            ]],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_ttn_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('b'),
                RuleElement::Terminal('c'),
                RuleElement::NonTerminal("D"),
            ]],
        );

        grammar.insert("D", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("D", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_ttn_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('b'),
                RuleElement::Terminal('c'),
                RuleElement::NonTerminal("D"),
            ]],
        );

        grammar.insert("D", vec![vec![RuleElement::Terminal('e')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("D", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_tne_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('b'),
                RuleElement::NonTerminal("C"),
                RuleElement::Empty,
            ]],
        );

        grammar.insert("C", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("C", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_tne_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('b'),
                RuleElement::NonTerminal("C"),
                RuleElement::Empty,
            ]],
        );

        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("C", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_tnt_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('b'),
                RuleElement::NonTerminal("C"),
                RuleElement::Terminal('d'),
            ]],
        );

        grammar.insert("C", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        let mut c_follow = BTreeSet::new();
        c_follow.insert('d');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("C", c_follow);

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_tnt_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('b'),
                RuleElement::NonTerminal("C"),
                RuleElement::Terminal('d'),
            ]],
        );

        grammar.insert("C", vec![vec![RuleElement::Terminal('e')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        let mut c_follow = BTreeSet::new();
        c_follow.insert('d');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("C", c_follow);

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_tnn_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('b'),
                RuleElement::NonTerminal("C"),
                RuleElement::NonTerminal("D"),
            ]],
        );

        grammar.insert("C", vec![vec![RuleElement::Empty]]);

        grammar.insert("D", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("C", BTreeSet::new());
        expected_follow_set.insert("D", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_tnn_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('b'),
                RuleElement::NonTerminal("C"),
                RuleElement::NonTerminal("D"),
            ]],
        );

        grammar.insert("C", vec![vec![RuleElement::Empty]]);

        grammar.insert("D", vec![vec![RuleElement::Terminal('e')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        let mut c_follow = BTreeSet::new();
        c_follow.insert('e');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("C", c_follow);
        expected_follow_set.insert("D", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_nee_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::Empty,
                RuleElement::Empty,
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_nee_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::Empty,
                RuleElement::Empty,
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_net_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::Empty,
                RuleElement::Terminal('c'),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        let mut b_follow = BTreeSet::new();
        b_follow.insert('c');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", b_follow);

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_net_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::Empty,
                RuleElement::Terminal('c'),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Terminal('d')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        let mut b_follow = BTreeSet::new();
        b_follow.insert('c');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", b_follow);

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_nen_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::Empty,
                RuleElement::NonTerminal("C"),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        grammar.insert("C", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", BTreeSet::new());
        expected_follow_set.insert("C", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_nen_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::Empty,
                RuleElement::NonTerminal("C"),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        let mut b_follow = BTreeSet::new();
        b_follow.insert('d');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", b_follow);
        expected_follow_set.insert("C", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_nte_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::Empty,
                RuleElement::Empty,
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_nte_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::Empty,
                RuleElement::Empty,
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_ntt_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::Terminal('c'),
                RuleElement::Terminal('d'),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        let mut b_follow = BTreeSet::new();
        b_follow.insert('c');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", b_follow);

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_ntt_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::Terminal('c'),
                RuleElement::Terminal('d'),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Terminal('e')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        let mut b_follow = BTreeSet::new();
        b_follow.insert('c');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", b_follow);

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_ntn_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::Terminal('c'),
                RuleElement::NonTerminal("C"),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        grammar.insert("C", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        let mut b_follow = BTreeSet::new();
        b_follow.insert('c');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", b_follow);
        expected_follow_set.insert("C", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_ntn_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::Terminal('c'),
                RuleElement::NonTerminal("C"),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        let mut b_follow = BTreeSet::new();
        b_follow.insert('c');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", b_follow);
        expected_follow_set.insert("C", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_nne() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::NonTerminal("C"),
                RuleElement::Empty,
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        grammar.insert("C", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", BTreeSet::new());
        expected_follow_set.insert("C", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_nne_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::NonTerminal("C"),
                RuleElement::Empty,
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        let mut b_follow = BTreeSet::new();
        b_follow.insert('d');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", b_follow);
        expected_follow_set.insert("C", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_nnt_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::NonTerminal("C"),
                RuleElement::Terminal('d'),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        grammar.insert("C", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        let mut b_follow = BTreeSet::new();
        b_follow.insert('d');

        let mut c_follow = BTreeSet::new();
        c_follow.insert('d');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", b_follow);
        expected_follow_set.insert("C", c_follow);

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_nnt_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::NonTerminal("C"),
                RuleElement::Terminal('d'),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        grammar.insert("C", vec![vec![RuleElement::Terminal('e')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        let mut b_follow = BTreeSet::new();
        b_follow.insert('e');

        let mut c_follow = BTreeSet::new();
        c_follow.insert('d');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", b_follow);
        expected_follow_set.insert("C", c_follow);

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_nnn_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::NonTerminal("C"),
                RuleElement::NonTerminal("D"),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        grammar.insert("C", vec![vec![RuleElement::Empty]]);

        grammar.insert("D", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", BTreeSet::new());
        expected_follow_set.insert("C", BTreeSet::new());
        expected_follow_set.insert("D", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_nnn_t_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::NonTerminal("C"),
                RuleElement::NonTerminal("D"),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        grammar.insert("C", vec![vec![RuleElement::Terminal('e')]]);

        grammar.insert("D", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        let mut b_follow = BTreeSet::new();
        b_follow.insert('e');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", b_follow);
        expected_follow_set.insert("C", BTreeSet::new());
        expected_follow_set.insert("D", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn combo_nnn_t_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::NonTerminal("C"),
                RuleElement::NonTerminal("D"),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        grammar.insert("C", vec![vec![RuleElement::Terminal('e')]]);

        grammar.insert("D", vec![vec![RuleElement::Terminal('f')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let mut expected_follow_set = BTreeMap::new();

        let mut b_follow = BTreeSet::new();
        b_follow.insert('e');

        let mut c_follow = BTreeSet::new();
        c_follow.insert('f');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("A", BTreeSet::new());
        expected_follow_set.insert("B", b_follow);
        expected_follow_set.insert("C", c_follow);
        expected_follow_set.insert("D", BTreeSet::new());

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }
}

#[cfg(test)]
mod get_parse_table {
    use super::*;

    #[test]
    fn combo_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert("A", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut a_parse = BTreeMap::new();
        a_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);

        let mut expected_parse_table = BTreeMap::new();
        expected_parse_table.insert("START", BTreeMap::new());
        expected_parse_table.insert("A", a_parse);

        assert!(
            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
        );
    }

    #[test]
    fn combo_ee() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert("A", vec![vec![RuleElement::Empty, RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut expected_parse_table = BTreeMap::new();
        expected_parse_table.insert("START", BTreeMap::new());
        expected_parse_table.insert("A", BTreeMap::new());

        assert!(
            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
        );
    }

    #[test]
    fn combo_et() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Empty, RuleElement::Terminal('b')]],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut start_parse = BTreeMap::new();
        start_parse.insert(
            ParseTableElement::Terminal('b'),
            vec![RuleElement::NonTerminal("A")],
        );

        let mut a_parse = BTreeMap::new();
        a_parse.insert(
            ParseTableElement::Terminal('b'),
            vec![RuleElement::Empty, RuleElement::Terminal('b')],
        );

        let mut expected_parse_table = BTreeMap::new();
        expected_parse_table.insert("START", start_parse);
        expected_parse_table.insert("A", a_parse);

        assert!(
            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
        );
    }

    #[test]
    fn combo_en_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Empty, RuleElement::NonTerminal("B")]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut b_parse = BTreeMap::new();
        b_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);

        let mut expected_parse_table = BTreeMap::new();
        expected_parse_table.insert("START", BTreeMap::new());
        expected_parse_table.insert("A", BTreeMap::new());
        expected_parse_table.insert("B", b_parse);

        assert!(
            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
        );
    }

    #[test]
    fn combo_en_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Empty, RuleElement::NonTerminal("B")]],
        );

        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut start_parse = BTreeMap::new();
        start_parse.insert(
            ParseTableElement::Terminal('c'),
            vec![RuleElement::NonTerminal("A")],
        );

        let mut a_parse = BTreeMap::new();
        a_parse.insert(
            ParseTableElement::Terminal('c'),
            vec![RuleElement::Empty, RuleElement::NonTerminal("B")],
        );

        let mut b_parse = BTreeMap::new();
        b_parse.insert(
            ParseTableElement::Terminal('c'),
            vec![RuleElement::Terminal('c')],
        );

        let mut expected_parse_table = BTreeMap::new();
        expected_parse_table.insert("START", start_parse);
        expected_parse_table.insert("A", a_parse);
        expected_parse_table.insert("B", b_parse);

        assert!(
            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
        );
    }

    #[test]
    fn combo_te_nt_nt() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Terminal('c')], vec![RuleElement::Empty]],
        );

        grammar.insert(
            "B",
            vec![vec![
                RuleElement::NonTerminal("A"),
                RuleElement::Terminal('c'),
            ]],
        );

        grammar.insert(
            "C",
            vec![vec![
                RuleElement::NonTerminal("A"),
                RuleElement::Terminal('c'),
            ]],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        match get_parse_table(&mut grammar, &first_set, &follow_set) {
            Ok(_) => panic!(),
            Err(err) => assert!(
                err == GrammarError::Conflict {
                    non_terminal: "A",
                    rule: vec![RuleElement::Empty],
                    rule_element: RuleElement::Empty,
                }
            ),
        }
    }

    #[test]
    fn combo_ne_nt_nt() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Terminal('c')], vec![RuleElement::Empty]],
        );

        grammar.insert(
            "B",
            vec![vec![
                RuleElement::NonTerminal("A"),
                RuleElement::Terminal('c'),
            ]],
        );

        grammar.insert(
            "C",
            vec![vec![
                RuleElement::NonTerminal("A"),
                RuleElement::Terminal('c'),
            ]],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        match get_parse_table(&mut grammar, &first_set, &follow_set) {
            Ok(_) => panic!(),
            Err(err) => assert!(
                err == GrammarError::Conflict {
                    non_terminal: "A",
                    rule: vec![RuleElement::Empty],
                    rule_element: RuleElement::Empty,
                }
            ),
        }
    }

    #[test]
    fn combo_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert("A", vec![vec![RuleElement::Terminal('b')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut start_parse = BTreeMap::new();
        start_parse.insert(
            ParseTableElement::Terminal('b'),
            vec![RuleElement::NonTerminal("A")],
        );

        let mut a_parse = BTreeMap::new();
        a_parse.insert(
            ParseTableElement::Terminal('b'),
            vec![RuleElement::Terminal('b')],
        );

        let mut expected_parse_table = BTreeMap::new();
        expected_parse_table.insert("START", start_parse);
        expected_parse_table.insert("A", a_parse);

        assert!(
            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
        );
    }

    #[test]
    fn combo_te() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Terminal('b'), RuleElement::Empty]],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut start_parse = BTreeMap::new();
        start_parse.insert(
            ParseTableElement::Terminal('b'),
            vec![RuleElement::NonTerminal("A")],
        );

        let mut a_parse = BTreeMap::new();
        a_parse.insert(
            ParseTableElement::Terminal('b'),
            vec![RuleElement::Terminal('b'), RuleElement::Empty],
        );

        let mut expected_parse_table = BTreeMap::new();
        expected_parse_table.insert("START", start_parse);
        expected_parse_table.insert("A", a_parse);

        assert!(
            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
        );
    }

    #[test]
    fn combo_tt() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::Terminal('b'), RuleElement::Terminal('c')]],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut start_parse = BTreeMap::new();
        start_parse.insert(
            ParseTableElement::Terminal('b'),
            vec![RuleElement::NonTerminal("A")],
        );

        let mut a_parse = BTreeMap::new();
        a_parse.insert(
            ParseTableElement::Terminal('b'),
            vec![RuleElement::Terminal('b'), RuleElement::Terminal('c')],
        );

        let mut expected_parse_table = BTreeMap::new();
        expected_parse_table.insert("START", start_parse);
        expected_parse_table.insert("A", a_parse);

        assert!(
            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
        );
    }

    #[test]
    fn combo_t_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![
                vec![RuleElement::Terminal('b')],
                vec![RuleElement::Terminal('b')],
            ],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        match get_parse_table(&mut grammar, &first_set, &follow_set) {
            Ok(_) => panic!(),
            Err(err) => assert!(
                err == GrammarError::Conflict {
                    non_terminal: "A",
                    rule: vec![RuleElement::Terminal('b')],
                    rule_element: RuleElement::Terminal('b'),
                }
            ),
        }
    }

    #[test]
    fn combo_t_et() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![
                vec![RuleElement::Terminal('b')],
                vec![RuleElement::Empty, RuleElement::Terminal('b')],
            ],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        match get_parse_table(&mut grammar, &first_set, &follow_set) {
            Ok(_) => panic!(),
            Err(err) => assert!(
                err == GrammarError::Conflict {
                    non_terminal: "A",
                    rule: vec![RuleElement::Empty, RuleElement::Terminal('b')],
                    rule_element: RuleElement::Terminal('b'),
                }
            ),
        }
    }

    #[test]
    fn combo_tn_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('b'),
                RuleElement::NonTerminal("C"),
            ]],
        );

        grammar.insert("C", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut start_parse = BTreeMap::new();
        start_parse.insert(
            ParseTableElement::Terminal('b'),
            vec![RuleElement::NonTerminal("A")],
        );

        let mut a_parse = BTreeMap::new();
        a_parse.insert(
            ParseTableElement::Terminal('b'),
            vec![RuleElement::Terminal('b'), RuleElement::NonTerminal("C")],
        );

        let mut c_parse = BTreeMap::new();
        c_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);

        let mut expected_parse_table = BTreeMap::new();
        expected_parse_table.insert("START", start_parse);
        expected_parse_table.insert("A", a_parse);
        expected_parse_table.insert("C", c_parse);

        assert!(
            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
        );
    }

    #[test]
    fn combo_tn_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::Terminal('b'),
                RuleElement::NonTerminal("C"),
            ]],
        );

        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut start_parse = BTreeMap::new();
        start_parse.insert(
            ParseTableElement::Terminal('b'),
            vec![RuleElement::NonTerminal("A")],
        );

        let mut a_parse = BTreeMap::new();
        a_parse.insert(
            ParseTableElement::Terminal('b'),
            vec![RuleElement::Terminal('b'), RuleElement::NonTerminal("C")],
        );

        let mut c_parse = BTreeMap::new();
        c_parse.insert(
            ParseTableElement::Terminal('d'),
            vec![RuleElement::Terminal('d')],
        );

        let mut expected_parse_table = BTreeMap::new();
        expected_parse_table.insert("START", start_parse);
        expected_parse_table.insert("A", a_parse);
        expected_parse_table.insert("C", c_parse);

        assert!(
            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
        );
    }

    #[test]
    fn combo_n_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert("A", vec![vec![RuleElement::NonTerminal("B")]]);

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut b_parse = BTreeMap::new();
        b_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);

        let mut expected_parse_table = BTreeMap::new();
        expected_parse_table.insert("START", BTreeMap::new());
        expected_parse_table.insert("A", BTreeMap::new());
        expected_parse_table.insert("B", b_parse);

        assert!(
            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
        );
    }

    #[test]
    fn combo_n_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert("A", vec![vec![RuleElement::NonTerminal("B")]]);

        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut start_parse = BTreeMap::new();
        start_parse.insert(
            ParseTableElement::Terminal('c'),
            vec![RuleElement::NonTerminal("A")],
        );

        let mut a_parse = BTreeMap::new();
        a_parse.insert(
            ParseTableElement::Terminal('c'),
            vec![RuleElement::NonTerminal("B")],
        );

        let mut b_parse = BTreeMap::new();
        b_parse.insert(
            ParseTableElement::Terminal('c'),
            vec![RuleElement::Terminal('c')],
        );

        let mut expected_parse_table = BTreeMap::new();
        expected_parse_table.insert("START", start_parse);
        expected_parse_table.insert("A", a_parse);
        expected_parse_table.insert("B", b_parse);

        assert!(
            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
        );
    }

    #[test]
    fn combo_ne_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::NonTerminal("B"), RuleElement::Empty]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut b_parse = BTreeMap::new();
        b_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);

        let mut expected_parse_table = BTreeMap::new();
        expected_parse_table.insert("START", BTreeMap::new());
        expected_parse_table.insert("A", BTreeMap::new());
        expected_parse_table.insert("B", b_parse);

        assert!(
            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
        );
    }

    #[test]
    fn combo_ne_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![RuleElement::NonTerminal("B"), RuleElement::Empty]],
        );

        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut start_parse = BTreeMap::new();
        start_parse.insert(
            ParseTableElement::Terminal('c'),
            vec![RuleElement::NonTerminal("A")],
        );

        let mut a_parse = BTreeMap::new();
        a_parse.insert(
            ParseTableElement::Terminal('c'),
            vec![RuleElement::NonTerminal("B"), RuleElement::Empty],
        );

        let mut b_parse = BTreeMap::new();
        b_parse.insert(
            ParseTableElement::Terminal('c'),
            vec![RuleElement::Terminal('c')],
        );

        let mut expected_parse_table = BTreeMap::new();
        expected_parse_table.insert("START", start_parse);
        expected_parse_table.insert("A", a_parse);
        expected_parse_table.insert("B", b_parse);

        assert!(
            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
        );
    }

    #[test]
    fn combo_ne_t_nt() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![
                vec![RuleElement::NonTerminal("B")],
                vec![RuleElement::Empty],
            ],
        );

        grammar.insert("B", vec![vec![RuleElement::Terminal('c')]]);

        grammar.insert(
            "C",
            vec![vec![
                RuleElement::NonTerminal("A"),
                RuleElement::Terminal('c'),
            ]],
        );

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        match get_parse_table(&mut grammar, &first_set, &follow_set) {
            Ok(_) => panic!(),
            Err(err) => assert!(
                err == GrammarError::Conflict {
                    non_terminal: "A",
                    rule: vec![RuleElement::Empty],
                    rule_element: RuleElement::Empty,
                }
            ),
        }
    }

    #[test]
    fn combo_nt_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::Terminal('c'),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut start_parse = BTreeMap::new();
        start_parse.insert(
            ParseTableElement::Terminal('c'),
            vec![RuleElement::NonTerminal("A")],
        );

        let mut a_parse = BTreeMap::new();
        a_parse.insert(
            ParseTableElement::Terminal('c'),
            vec![RuleElement::NonTerminal("B"), RuleElement::Terminal('c')],
        );

        let mut b_parse = BTreeMap::new();
        b_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
        b_parse.insert(ParseTableElement::Terminal('c'), vec![RuleElement::Empty]);

        let mut expected_parse_table = BTreeMap::new();
        expected_parse_table.insert("START", start_parse);
        expected_parse_table.insert("A", a_parse);
        expected_parse_table.insert("B", b_parse);

        assert!(
            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
        );
    }

    #[test]
    fn combo_nt_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::Terminal('c'),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Terminal('d')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut start_parse = BTreeMap::new();
        start_parse.insert(
            ParseTableElement::Terminal('d'),
            vec![RuleElement::NonTerminal("A")],
        );

        let mut a_parse = BTreeMap::new();
        a_parse.insert(
            ParseTableElement::Terminal('d'),
            vec![RuleElement::NonTerminal("B"), RuleElement::Terminal('c')],
        );

        let mut b_parse = BTreeMap::new();
        b_parse.insert(
            ParseTableElement::Terminal('d'),
            vec![RuleElement::Terminal('d')],
        );

        let mut expected_parse_table = BTreeMap::new();
        expected_parse_table.insert("START", start_parse);
        expected_parse_table.insert("A", a_parse);
        expected_parse_table.insert("B", b_parse);

        assert!(
            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
        );
    }

    #[test]
    fn combo_nn_e() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::NonTerminal("C"),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        grammar.insert("C", vec![vec![RuleElement::Empty]]);

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut b_parse = BTreeMap::new();
        b_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);

        let mut c_parse = BTreeMap::new();
        c_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);

        let mut expected_parse_table = BTreeMap::new();
        expected_parse_table.insert("START", BTreeMap::new());
        expected_parse_table.insert("A", BTreeMap::new());
        expected_parse_table.insert("B", b_parse);
        expected_parse_table.insert("C", c_parse);

        assert!(
            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
        );
    }

    #[test]
    fn combo_nn_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![vec![
                RuleElement::NonTerminal("B"),
                RuleElement::NonTerminal("C"),
            ]],
        );

        grammar.insert("B", vec![vec![RuleElement::Empty]]);

        grammar.insert("C", vec![vec![RuleElement::Terminal('d')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut start_parse = BTreeMap::new();
        start_parse.insert(
            ParseTableElement::Terminal('d'),
            vec![RuleElement::NonTerminal("A")],
        );

        let mut a_parse = BTreeMap::new();
        a_parse.insert(
            ParseTableElement::Terminal('d'),
            vec![RuleElement::NonTerminal("B"), RuleElement::NonTerminal("C")],
        );

        let mut b_parse = BTreeMap::new();
        b_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);
        b_parse.insert(ParseTableElement::Terminal('d'), vec![RuleElement::Empty]);

        let mut c_parse = BTreeMap::new();
        c_parse.insert(
            ParseTableElement::Terminal('d'),
            vec![RuleElement::Terminal('d')],
        );

        let mut expected_parse_table = BTreeMap::new();
        expected_parse_table.insert("START", start_parse);
        expected_parse_table.insert("A", a_parse);
        expected_parse_table.insert("B", b_parse);
        expected_parse_table.insert("C", c_parse);

        assert!(
            expected_parse_table == get_parse_table(&mut grammar, &first_set, &follow_set).unwrap()
        );
    }

    #[test]
    fn combo_n_n() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![
                vec![RuleElement::Terminal('b')],
                vec![RuleElement::NonTerminal("C")],
            ],
        );

        grammar.insert("C", vec![vec![RuleElement::Terminal('b')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        match get_parse_table(&mut grammar, &first_set, &follow_set) {
            Ok(_) => panic!(),
            Err(err) => assert!(
                err == GrammarError::Conflict {
                    non_terminal: "A",
                    rule: vec![RuleElement::NonTerminal("C")],
                    rule_element: RuleElement::NonTerminal("C"),
                }
            ),
        }
    }

    #[test]
    fn combo_nn_t_t() {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("A")]]);

        grammar.insert(
            "A",
            vec![
                vec![RuleElement::NonTerminal("B")],
                vec![RuleElement::NonTerminal("C")],
            ],
        );

        grammar.insert("B", vec![vec![RuleElement::Terminal('b')]]);

        grammar.insert("C", vec![vec![RuleElement::Terminal('b')]]);

        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        match get_parse_table(&mut grammar, &first_set, &follow_set) {
            Ok(_) => panic!(),
            Err(err) => assert!(
                err == GrammarError::Conflict {
                    non_terminal: "A",
                    rule: vec![RuleElement::NonTerminal("C")],
                    rule_element: RuleElement::NonTerminal("C"),
                }
            ),
        }
    }
}

#[cfg(test)]
mod parsing_techniques_2nd_ed {
    use super::*;

    fn get_grammar<'a>() -> Grammar<'a> {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("Session")]]);

        grammar.insert(
            "Session",
            vec![
                vec![
                    RuleElement::NonTerminal("Facts"),
                    RuleElement::NonTerminal("Question"),
                ],
                vec![
                    RuleElement::Terminal('('),
                    RuleElement::NonTerminal("Session"),
                    RuleElement::Terminal(')'),
                    RuleElement::NonTerminal("Session"),
                ],
            ],
        );

        grammar.insert(
            "Facts",
            vec![
                vec![
                    RuleElement::NonTerminal("Fact"),
                    RuleElement::NonTerminal("Facts"),
                ],
                vec![RuleElement::Empty],
            ],
        );

        grammar.insert(
            "Fact",
            vec![vec![
                RuleElement::Terminal('!'),
                RuleElement::NonTerminal("STRING"),
            ]],
        );

        grammar.insert(
            "Question",
            vec![vec![
                RuleElement::Terminal('?'),
                RuleElement::NonTerminal("STRING"),
            ]],
        );

        grammar.insert("STRING", vec![vec![RuleElement::Terminal('x')]]);

        grammar
    }

    #[test]
    fn pg_243() {
        let grammar = get_grammar();

        let mut expected_first_set = BTreeMap::new();

        let mut start_first = BTreeSet::new();
        start_first.insert(FirstElement::Terminal('('));
        start_first.insert(FirstElement::Terminal('?'));
        start_first.insert(FirstElement::Terminal('!'));

        let mut session_first = BTreeSet::new();
        session_first.insert(FirstElement::Terminal('('));
        session_first.insert(FirstElement::Terminal('?'));
        session_first.insert(FirstElement::Terminal('!'));

        let mut facts_first = BTreeSet::new();
        facts_first.insert(FirstElement::Empty);
        facts_first.insert(FirstElement::Terminal('!'));

        let mut fact_first = BTreeSet::new();
        fact_first.insert(FirstElement::Terminal('!'));

        let mut question_first = BTreeSet::new();
        question_first.insert(FirstElement::Terminal('?'));

        let mut string_first = BTreeSet::new();
        string_first.insert(FirstElement::Terminal('x'));

        expected_first_set.insert("START", start_first);
        expected_first_set.insert("Session", session_first);
        expected_first_set.insert("Facts", facts_first);
        expected_first_set.insert("Fact", fact_first);
        expected_first_set.insert("Question", question_first);
        expected_first_set.insert("STRING", string_first);

        assert!(get_first_set(&grammar).unwrap() == expected_first_set);
    }

    #[test]
    fn pg_246() {
        let grammar = get_grammar();
        let first_set = get_first_set(&grammar).unwrap();

        let mut expected_follow_set: FollowSet = BTreeMap::new();

        let mut session_first = BTreeSet::new();
        session_first.insert(')');

        let mut facts_first = BTreeSet::new();
        facts_first.insert('?');

        let mut fact_first = BTreeSet::new();
        fact_first.insert('!');
        fact_first.insert('?');

        let mut question_first = BTreeSet::new();
        question_first.insert(')');

        let mut string_first = BTreeSet::new();
        string_first.insert('!');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("Session", session_first);
        expected_follow_set.insert("Facts", facts_first);
        expected_follow_set.insert("Fact", fact_first);
        expected_follow_set.insert("Question", question_first);
        expected_follow_set.insert("STRING", string_first);

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn pg_247() {
        let mut grammar = get_grammar();
        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut expected_parse_table: ParseTable = BTreeMap::new();

        let mut start_parse = BTreeMap::new();
        start_parse.insert(
            ParseTableElement::Terminal('!'),
            vec![RuleElement::NonTerminal("Session")],
        );

        start_parse.insert(
            ParseTableElement::Terminal('('),
            vec![RuleElement::NonTerminal("Session")],
        );

        start_parse.insert(
            ParseTableElement::Terminal('?'),
            vec![RuleElement::NonTerminal("Session")],
        );

        let mut session_parse = BTreeMap::new();

        session_parse.insert(
            ParseTableElement::Terminal('('),
            vec![
                RuleElement::Terminal('('),
                RuleElement::NonTerminal("Session"),
                RuleElement::Terminal(')'),
                RuleElement::NonTerminal("Session"),
            ],
        );

        session_parse.insert(
            ParseTableElement::Terminal('!'),
            vec![
                RuleElement::NonTerminal("Facts"),
                RuleElement::NonTerminal("Question"),
            ],
        );

        session_parse.insert(
            ParseTableElement::Terminal('?'),
            vec![
                RuleElement::NonTerminal("Facts"),
                RuleElement::NonTerminal("Question"),
            ],
        );

        let mut facts_parse = BTreeMap::new();

        facts_parse.insert(
            ParseTableElement::Terminal('!'),
            vec![
                RuleElement::NonTerminal("Fact"),
                RuleElement::NonTerminal("Facts"),
            ],
        );

        facts_parse.insert(ParseTableElement::Terminal('?'), vec![RuleElement::Empty]);

        facts_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);

        let mut fact_parse = BTreeMap::new();

        fact_parse.insert(
            ParseTableElement::Terminal('!'),
            vec![
                RuleElement::Terminal('!'),
                RuleElement::NonTerminal("STRING"),
            ],
        );

        let mut question_parse = BTreeMap::new();

        question_parse.insert(
            ParseTableElement::Terminal('?'),
            vec![
                RuleElement::Terminal('?'),
                RuleElement::NonTerminal("STRING"),
            ],
        );

        let mut string_parse = BTreeMap::new();

        string_parse.insert(
            ParseTableElement::Terminal('x'),
            vec![RuleElement::Terminal('x')],
        );

        expected_parse_table.insert("START", start_parse);
        expected_parse_table.insert("Session", session_parse);
        expected_parse_table.insert("Facts", facts_parse);
        expected_parse_table.insert("Fact", fact_parse);
        expected_parse_table.insert("Question", question_parse);
        expected_parse_table.insert("STRING", string_parse);

        assert!(
            get_parse_table(&mut grammar, &first_set, &follow_set).unwrap() == expected_parse_table
        );
    }

    #[test]
    fn parse_ok() {
        let mut grammar = get_grammar();
        let mut parser = Parser::new(&mut grammar).unwrap();

        assert!(
            parser.parse("!x?x").unwrap()
                == ParseTree::NonTerminal {
                    symbol: "START",
                    children: vec![ParseTree::NonTerminal {
                        symbol: "Session",
                        children: vec![
                            ParseTree::NonTerminal {
                                symbol: "Facts",
                                children: vec![
                                    ParseTree::NonTerminal {
                                        symbol: "Fact",
                                        children: vec![
                                            ParseTree::Terminal('!'),
                                            ParseTree::NonTerminal {
                                                symbol: "STRING",
                                                children: vec![ParseTree::Terminal('x'),],
                                            },
                                        ],
                                    },
                                    ParseTree::NonTerminal {
                                        symbol: "Facts",
                                        children: vec![],
                                    },
                                ],
                            },
                            ParseTree::NonTerminal {
                                symbol: "Question",
                                children: vec![
                                    ParseTree::Terminal('?'),
                                    ParseTree::NonTerminal {
                                        symbol: "STRING",
                                        children: vec![ParseTree::Terminal('x'),],
                                    },
                                ],
                            },
                        ],
                    },],
                }
        );
    }
}

#[cfg(test)]
mod compilers_1st_ed {
    use super::*;

    fn get_grammar<'a>() -> Grammar<'a> {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("E")]]);

        grammar.insert(
            "E",
            vec![vec![
                RuleElement::NonTerminal("T"),
                RuleElement::NonTerminal("Edash"),
            ]],
        );

        grammar.insert(
            "Edash",
            vec![
                vec![
                    RuleElement::Terminal('+'),
                    RuleElement::NonTerminal("T"),
                    RuleElement::NonTerminal("Edash"),
                ],
                vec![RuleElement::Empty],
            ],
        );

        grammar.insert(
            "T",
            vec![vec![
                RuleElement::NonTerminal("F"),
                RuleElement::NonTerminal("Tdash"),
            ]],
        );

        grammar.insert(
            "Tdash",
            vec![
                vec![
                    RuleElement::Terminal('*'),
                    RuleElement::NonTerminal("F"),
                    RuleElement::NonTerminal("Tdash"),
                ],
                vec![RuleElement::Empty],
            ],
        );

        grammar.insert(
            "F",
            vec![
                vec![
                    RuleElement::Terminal('('),
                    RuleElement::NonTerminal("E"),
                    RuleElement::Terminal(')'),
                ],
                vec![RuleElement::Terminal('i'), RuleElement::Terminal('d')],
            ],
        );

        grammar
    }

    #[test]
    fn pg_190() {
        let grammar = get_grammar();

        let mut expected_first_set = BTreeMap::new();

        let mut start_first = BTreeSet::new();
        start_first.insert(FirstElement::Terminal('('));
        start_first.insert(FirstElement::Terminal('i'));

        let mut e_first = BTreeSet::new();
        e_first.insert(FirstElement::Terminal('('));
        e_first.insert(FirstElement::Terminal('i'));

        let mut t_first = BTreeSet::new();
        t_first.insert(FirstElement::Terminal('('));
        t_first.insert(FirstElement::Terminal('i'));

        let mut f_first = BTreeSet::new();
        f_first.insert(FirstElement::Terminal('('));
        f_first.insert(FirstElement::Terminal('i'));

        let mut edash_first = BTreeSet::new();
        edash_first.insert(FirstElement::Terminal('+'));
        edash_first.insert(FirstElement::Empty);

        let mut tdash_first = BTreeSet::new();
        tdash_first.insert(FirstElement::Terminal('*'));
        tdash_first.insert(FirstElement::Empty);

        expected_first_set.insert("START", start_first);
        expected_first_set.insert("E", e_first);
        expected_first_set.insert("T", t_first);
        expected_first_set.insert("F", f_first);
        expected_first_set.insert("Edash", edash_first);
        expected_first_set.insert("Tdash", tdash_first);

        assert!(get_first_set(&grammar).unwrap() == expected_first_set);

        let mut expected_follow_set: FollowSet = BTreeMap::new();

        let mut e_follow = BTreeSet::new();
        e_follow.insert(')');

        let mut edash_follow = BTreeSet::new();
        edash_follow.insert(')');

        let mut t_follow = BTreeSet::new();
        t_follow.insert('+');
        t_follow.insert(')');

        let mut tdash_follow = BTreeSet::new();
        tdash_follow.insert('+');
        tdash_follow.insert(')');

        let mut f_follow = BTreeSet::new();
        f_follow.insert('+');
        f_follow.insert('*');
        f_follow.insert(')');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("E", e_follow);
        expected_follow_set.insert("T", t_follow);
        expected_follow_set.insert("F", f_follow);
        expected_follow_set.insert("Edash", edash_follow);
        expected_follow_set.insert("Tdash", tdash_follow);

        assert!(get_follow_set(&grammar, &expected_first_set) == expected_follow_set);
    }

    #[test]
    fn pg_188() {
        let mut grammar = get_grammar();
        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut expected_parse_table: ParseTable = BTreeMap::new();

        let mut start_parse = BTreeMap::new();

        start_parse.insert(
            ParseTableElement::Terminal('i'),
            vec![RuleElement::NonTerminal("E")],
        );

        start_parse.insert(
            ParseTableElement::Terminal('('),
            vec![RuleElement::NonTerminal("E")],
        );

        let mut e_parse = BTreeMap::new();

        e_parse.insert(
            ParseTableElement::Terminal('i'),
            vec![
                RuleElement::NonTerminal("T"),
                RuleElement::NonTerminal("Edash"),
            ],
        );

        e_parse.insert(
            ParseTableElement::Terminal('('),
            vec![
                RuleElement::NonTerminal("T"),
                RuleElement::NonTerminal("Edash"),
            ],
        );

        let mut edash_parse = BTreeMap::new();

        edash_parse.insert(
            ParseTableElement::Terminal('+'),
            vec![
                RuleElement::Terminal('+'),
                RuleElement::NonTerminal("T"),
                RuleElement::NonTerminal("Edash"),
            ],
        );

        edash_parse.insert(ParseTableElement::Terminal(')'), vec![RuleElement::Empty]);

        edash_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);

        let mut t_parse = BTreeMap::new();

        t_parse.insert(
            ParseTableElement::Terminal('i'),
            vec![
                RuleElement::NonTerminal("F"),
                RuleElement::NonTerminal("Tdash"),
            ],
        );

        t_parse.insert(
            ParseTableElement::Terminal('('),
            vec![
                RuleElement::NonTerminal("F"),
                RuleElement::NonTerminal("Tdash"),
            ],
        );

        let mut tdash_parse = BTreeMap::new();

        tdash_parse.insert(ParseTableElement::Terminal('+'), vec![RuleElement::Empty]);

        tdash_parse.insert(
            ParseTableElement::Terminal('*'),
            vec![
                RuleElement::Terminal('*'),
                RuleElement::NonTerminal("F"),
                RuleElement::NonTerminal("Tdash"),
            ],
        );

        tdash_parse.insert(ParseTableElement::Terminal(')'), vec![RuleElement::Empty]);

        tdash_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);

        let mut f_parse = BTreeMap::new();

        f_parse.insert(
            ParseTableElement::Terminal('i'),
            vec![RuleElement::Terminal('i'), RuleElement::Terminal('d')],
        );

        f_parse.insert(
            ParseTableElement::Terminal('('),
            vec![
                RuleElement::Terminal('('),
                RuleElement::NonTerminal("E"),
                RuleElement::Terminal(')'),
            ],
        );

        expected_parse_table.insert("START", start_parse);
        expected_parse_table.insert("E", e_parse);
        expected_parse_table.insert("Edash", edash_parse);
        expected_parse_table.insert("T", t_parse);
        expected_parse_table.insert("Tdash", tdash_parse);
        expected_parse_table.insert("F", f_parse);

        assert!(
            get_parse_table(&mut grammar, &first_set, &follow_set).unwrap() == expected_parse_table
        );
    }

    #[test]
    fn parse_ok() {
        let mut grammar = get_grammar();
        let mut parser = Parser::new(&mut grammar).unwrap();

        assert!(
            parser.parse("id").unwrap()
                == ParseTree::NonTerminal {
                    symbol: "START",
                    children: vec![ParseTree::NonTerminal {
                        symbol: "E",
                        children: vec![
                            ParseTree::NonTerminal {
                                symbol: "T",
                                children: vec![
                                    ParseTree::NonTerminal {
                                        symbol: "F",
                                        children: vec![
                                            ParseTree::Terminal('i'),
                                            ParseTree::Terminal('d'),
                                        ],
                                    },
                                    ParseTree::NonTerminal {
                                        symbol: "Tdash",
                                        children: vec![],
                                    },
                                ],
                            },
                            ParseTree::NonTerminal {
                                symbol: "Edash",
                                children: vec![],
                            },
                        ],
                    },],
                }
        );
    }
}

#[cfg(test)]
mod compiler_design_in_c_1st {
    use super::*;

    fn get_grammar<'a>() -> Grammar<'a> {
        let mut grammar = Grammar::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("stmt")]]);

        grammar.insert(
            "stmt",
            vec![vec![
                RuleElement::NonTerminal("expr"),
                RuleElement::Terminal(';'),
            ]],
        );

        grammar.insert(
            "expr",
            vec![
                vec![
                    RuleElement::NonTerminal("term"),
                    RuleElement::NonTerminal("exprdash"),
                ],
                vec![RuleElement::Empty],
            ],
        );

        grammar.insert(
            "exprdash",
            vec![
                vec![
                    RuleElement::Terminal('+'),
                    RuleElement::NonTerminal("term"),
                    RuleElement::NonTerminal("exprdash"),
                ],
                vec![RuleElement::Empty],
            ],
        );

        grammar.insert(
            "term",
            vec![vec![
                RuleElement::NonTerminal("factor"),
                RuleElement::NonTerminal("termdash"),
            ]],
        );

        grammar.insert(
            "termdash",
            vec![
                vec![
                    RuleElement::Terminal('*'),
                    RuleElement::NonTerminal("factor"),
                    RuleElement::NonTerminal("termdash"),
                ],
                vec![RuleElement::Empty],
            ],
        );

        grammar.insert(
            "factor",
            vec![
                vec![
                    RuleElement::Terminal('('),
                    RuleElement::NonTerminal("expr"),
                    RuleElement::Terminal(')'),
                ],
                vec![RuleElement::Terminal('0')],
            ],
        );

        grammar
    }

    #[test]
    fn pg_214() {
        let grammar = get_grammar();

        let mut expected_first_set = BTreeMap::new();

        let mut start_first = BTreeSet::new();
        start_first.insert(FirstElement::Terminal('('));
        start_first.insert(FirstElement::Terminal('0'));
        start_first.insert(FirstElement::Terminal(';'));

        let mut stmt_first = BTreeSet::new();
        stmt_first.insert(FirstElement::Terminal('('));
        stmt_first.insert(FirstElement::Terminal('0'));
        stmt_first.insert(FirstElement::Terminal(';'));

        let mut expr_first = BTreeSet::new();
        expr_first.insert(FirstElement::Terminal('('));
        expr_first.insert(FirstElement::Terminal('0'));
        expr_first.insert(FirstElement::Empty);

        let mut exprdash_first = BTreeSet::new();
        exprdash_first.insert(FirstElement::Terminal('+'));
        exprdash_first.insert(FirstElement::Empty);

        let mut term_first = BTreeSet::new();
        term_first.insert(FirstElement::Terminal('('));
        term_first.insert(FirstElement::Terminal('0'));

        let mut termdash_first = BTreeSet::new();
        termdash_first.insert(FirstElement::Terminal('*'));
        termdash_first.insert(FirstElement::Empty);

        let mut factor_first = BTreeSet::new();
        factor_first.insert(FirstElement::Terminal('('));
        factor_first.insert(FirstElement::Terminal('0'));

        expected_first_set.insert("START", start_first);
        expected_first_set.insert("stmt", stmt_first);
        expected_first_set.insert("expr", expr_first);
        expected_first_set.insert("exprdash", exprdash_first);
        expected_first_set.insert("term", term_first);
        expected_first_set.insert("termdash", termdash_first);
        expected_first_set.insert("factor", factor_first);

        assert!(get_first_set(&grammar).unwrap() == expected_first_set);
    }

    #[test]
    fn pg_217() {
        let grammar = get_grammar();
        let first_set = get_first_set(&grammar).unwrap();

        let mut expected_follow_set: FollowSet = BTreeMap::new();

        let mut expr_follow = BTreeSet::new();
        expr_follow.insert(')');
        expr_follow.insert(';');

        let mut exprdash_follow = BTreeSet::new();
        exprdash_follow.insert(')');
        exprdash_follow.insert(';');

        let mut term_follow = BTreeSet::new();
        term_follow.insert('+');
        term_follow.insert(';');
        term_follow.insert(')');

        let mut termdash_follow = BTreeSet::new();
        termdash_follow.insert('+');
        termdash_follow.insert(';');
        termdash_follow.insert(')');

        let mut factor_follow = BTreeSet::new();
        factor_follow.insert('*');
        factor_follow.insert('+');
        factor_follow.insert(';');
        factor_follow.insert(')');

        expected_follow_set.insert("START", BTreeSet::new());
        expected_follow_set.insert("stmt", BTreeSet::new());
        expected_follow_set.insert("expr", expr_follow);
        expected_follow_set.insert("exprdash", exprdash_follow);
        expected_follow_set.insert("term", term_follow);
        expected_follow_set.insert("termdash", termdash_follow);
        expected_follow_set.insert("factor", factor_follow);

        assert!(get_follow_set(&grammar, &first_set) == expected_follow_set);
    }

    #[test]
    fn get_parse_table_ok() {
        let mut grammar = get_grammar();
        let first_set = get_first_set(&grammar).unwrap();
        let follow_set = get_follow_set(&grammar, &first_set);

        let mut expected_parse_table: ParseTable = BTreeMap::new();

        let mut start_parse = BTreeMap::new();

        start_parse.insert(
            ParseTableElement::Terminal('('),
            vec![RuleElement::NonTerminal("stmt")],
        );

        start_parse.insert(
            ParseTableElement::Terminal('0'),
            vec![RuleElement::NonTerminal("stmt")],
        );

        start_parse.insert(
            ParseTableElement::Terminal(';'),
            vec![RuleElement::NonTerminal("stmt")],
        );

        let mut stmt_parse = BTreeMap::new();

        stmt_parse.insert(
            ParseTableElement::Terminal('('),
            vec![RuleElement::NonTerminal("expr"), RuleElement::Terminal(';')],
        );

        stmt_parse.insert(
            ParseTableElement::Terminal('0'),
            vec![RuleElement::NonTerminal("expr"), RuleElement::Terminal(';')],
        );

        stmt_parse.insert(
            ParseTableElement::Terminal(';'),
            vec![RuleElement::NonTerminal("expr"), RuleElement::Terminal(';')],
        );

        let mut stmt_parse = BTreeMap::new();

        stmt_parse.insert(
            ParseTableElement::Terminal('('),
            vec![RuleElement::NonTerminal("expr"), RuleElement::Terminal(';')],
        );

        stmt_parse.insert(
            ParseTableElement::Terminal('0'),
            vec![RuleElement::NonTerminal("expr"), RuleElement::Terminal(';')],
        );

        stmt_parse.insert(
            ParseTableElement::Terminal(';'),
            vec![RuleElement::NonTerminal("expr"), RuleElement::Terminal(';')],
        );

        let mut expr_parse = BTreeMap::new();

        expr_parse.insert(
            ParseTableElement::Terminal('('),
            vec![
                RuleElement::NonTerminal("term"),
                RuleElement::NonTerminal("exprdash"),
            ],
        );

        expr_parse.insert(
            ParseTableElement::Terminal('0'),
            vec![
                RuleElement::NonTerminal("term"),
                RuleElement::NonTerminal("exprdash"),
            ],
        );

        expr_parse.insert(ParseTableElement::Terminal(')'), vec![RuleElement::Empty]);

        expr_parse.insert(ParseTableElement::Terminal(';'), vec![RuleElement::Empty]);

        expr_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);

        let mut exprdash_parse = BTreeMap::new();

        exprdash_parse.insert(
            ParseTableElement::Terminal('+'),
            vec![
                RuleElement::Terminal('+'),
                RuleElement::NonTerminal("term"),
                RuleElement::NonTerminal("exprdash"),
            ],
        );

        exprdash_parse.insert(ParseTableElement::Terminal(')'), vec![RuleElement::Empty]);

        exprdash_parse.insert(ParseTableElement::Terminal(';'), vec![RuleElement::Empty]);

        exprdash_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);

        let mut term_parse = BTreeMap::new();

        term_parse.insert(
            ParseTableElement::Terminal('('),
            vec![
                RuleElement::NonTerminal("factor"),
                RuleElement::NonTerminal("termdash"),
            ],
        );

        term_parse.insert(
            ParseTableElement::Terminal('0'),
            vec![
                RuleElement::NonTerminal("factor"),
                RuleElement::NonTerminal("termdash"),
            ],
        );

        let mut termdash_parse = BTreeMap::new();

        termdash_parse.insert(ParseTableElement::Terminal(')'), vec![RuleElement::Empty]);

        termdash_parse.insert(ParseTableElement::Empty, vec![RuleElement::Empty]);

        termdash_parse.insert(
            ParseTableElement::Terminal('*'),
            vec![
                RuleElement::Terminal('*'),
                RuleElement::NonTerminal("factor"),
                RuleElement::NonTerminal("termdash"),
            ],
        );

        termdash_parse.insert(ParseTableElement::Terminal('+'), vec![RuleElement::Empty]);

        termdash_parse.insert(ParseTableElement::Terminal(';'), vec![RuleElement::Empty]);

        let mut factor_parse = BTreeMap::new();

        factor_parse.insert(
            ParseTableElement::Terminal('('),
            vec![
                RuleElement::Terminal('('),
                RuleElement::NonTerminal("expr"),
                RuleElement::Terminal(')'),
            ],
        );

        factor_parse.insert(
            ParseTableElement::Terminal('0'),
            vec![RuleElement::Terminal('0')],
        );

        expected_parse_table.insert("START", start_parse);
        expected_parse_table.insert("stmt", stmt_parse);
        expected_parse_table.insert("expr", expr_parse);
        expected_parse_table.insert("exprdash", exprdash_parse);
        expected_parse_table.insert("term", term_parse);
        expected_parse_table.insert("termdash", termdash_parse);
        expected_parse_table.insert("factor", factor_parse);

        assert!(
            get_parse_table(&mut grammar, &first_set, &follow_set).unwrap() == expected_parse_table
        );
    }

    #[test]
    fn parse_ok() {
        let mut grammar = get_grammar();
        let mut parser = Parser::new(&mut grammar).unwrap();

        assert!(
            parser.parse("();").unwrap()
                == ParseTree::NonTerminal {
                    symbol: "START",
                    children: vec![ParseTree::NonTerminal {
                        symbol: "stmt",
                        children: vec![
                            ParseTree::NonTerminal {
                                symbol: "expr",
                                children: vec![
                                    ParseTree::NonTerminal {
                                        symbol: "term",
                                        children: vec![
                                            ParseTree::NonTerminal {
                                                symbol: "factor",
                                                children: vec![
                                                    ParseTree::Terminal('('),
                                                    ParseTree::NonTerminal {
                                                        symbol: "expr",
                                                        children: vec![],
                                                    },
                                                    ParseTree::Terminal(')'),
                                                ],
                                            },
                                            ParseTree::NonTerminal {
                                                symbol: "termdash",
                                                children: vec![],
                                            },
                                        ],
                                    },
                                    ParseTree::NonTerminal {
                                        symbol: "exprdash",
                                        children: vec![],
                                    },
                                ],
                            },
                            ParseTree::Terminal(';'),
                        ],
                    },],
                }
        );
    }
}

#[cfg(test)]
mod rollup {
    use super::*;

    fn set_grammar<'a>(grammar: &mut Grammar) {
        grammar.insert(
            "START",
            vec![vec![RuleElement::NonTerminal("one-or-more-a")]],
        );

        grammar.insert(
            "one-or-more-a",
            vec![vec![
                RuleElement::Terminal('a'),
                RuleElement::NonTerminal("zero-or-more-a"),
            ]],
        );

        grammar.insert(
            "zero-or-more-a",
            vec![
                vec![
                    RuleElement::Terminal('a'),
                    RuleElement::NonTerminal("zero-or-more-a"),
                ],
                vec![RuleElement::Empty],
            ],
        );
    }

    #[test]
    pub fn no_rollup() {
        let mut grammar: Grammar = BTreeMap::new();
        set_grammar(&mut grammar);

        let mut parser = Parser::new(&mut grammar).unwrap();

        assert!(
            parser.parse("aaa").unwrap()
                == ParseTree::NonTerminal {
                    symbol: "START",
                    children: vec![ParseTree::NonTerminal {
                        symbol: "one-or-more-a",
                        children: vec![
                            ParseTree::Terminal('a'),
                            ParseTree::NonTerminal {
                                symbol: "zero-or-more-a",
                                children: vec![
                                    ParseTree::Terminal('a'),
                                    ParseTree::NonTerminal {
                                        symbol: "zero-or-more-a",
                                        children: vec![
                                            ParseTree::Terminal('a'),
                                            ParseTree::NonTerminal {
                                                symbol: "zero-or-more-a",
                                                children: vec![],
                                            },
                                        ],
                                    },
                                ],
                            },
                        ],
                    },],
                }
        );
    }

    #[test]
    pub fn rollup() {
        let mut grammar: Grammar = BTreeMap::new();
        set_grammar(&mut grammar);

        let mut parser = Parser::new(&mut grammar).unwrap();

        parser.rollup(vec!["one-or-more-a", "zero-or-more-a"]);

        assert!(
            parser.parse("aaa").unwrap()
                == ParseTree::NonTerminal {
                    symbol: "START",
                    children: vec![
                        ParseTree::Terminal('a'),
                        ParseTree::Terminal('a'),
                        ParseTree::Terminal('a'),
                    ],
                }
        );
    }

    #[test]
    pub fn auto_rollup() {
        let mut grammar: Grammar = BTreeMap::new();

        grammar.insert("START", vec![vec![RuleElement::NonTerminal("a+")]]);

        grammar.insert(
            "a+",
            vec![vec![
                RuleElement::Terminal('a'),
                RuleElement::NonTerminal("a*"),
            ]],
        );

        grammar.insert(
            "a*",
            vec![
                vec![RuleElement::Terminal('a'), RuleElement::NonTerminal("a*")],
                vec![RuleElement::Empty],
            ],
        );

        let mut parser = Parser::new(&mut grammar).unwrap();

        parser.rollup(vec!["a+", "a*"]);

        assert!(
            parser.parse("aaa").unwrap()
                == ParseTree::NonTerminal {
                    symbol: "START",
                    children: vec![
                        ParseTree::Terminal('a'),
                        ParseTree::Terminal('a'),
                        ParseTree::Terminal('a'),
                    ],
                }
        );
    }
}