#!/usr/bin/env rust-script
//! # Thepg: A Parser Generator in Rust
//!
//! **Thepg** is a parser generator that takes an Extended Backus–Naur Form (ENBF) grammar
//! and produces compile-ready Rust code for parsing according to that grammar.
//!
//! ## Features
//! - Supports LL(1) and LL(k) parsing strategies
//! - Generates lexing-free parsers
//! - Outputs all code in a single Rust file
//! - Includes comprehensive documentation and example usage within the generated parser
//!
//! ## Usage
//! To generate a parser, run the following command:
//! 
//! ```bash
//! cargo run --release -- grammar.enbf -o parser.rs --grammar-type LL1
//! ```
//! 
//! Replace `grammar.enbf` with your ENBF grammar file, and `parser.rs` with your desired output file name.
//!
//! ## Example
//! Given the following `arithmetic.enbf` grammar:
//!
//! ```enbf
//! # arithmetic.enbf
//! Expr ::= Term ExprPrime
//! ExprPrime ::= "+" Term ExprPrime | "-" Term ExprPrime | ε
//! Term ::= Factor TermPrime
//! TermPrime ::= "*" Factor TermPrime | "/" Factor TermPrime | ε
//! Factor ::= "(" Expr ")" | "id"
//! ```
//!
//! Running Thepg:
//!
//! ```bash
//! cargo run --release -- arithmetic.enbf -o arithmetic_parser.rs --grammar-type LL1
//! ```
//!
//! The above command will generate `arithmetic_parser.rs` containing the parser for arithmetic expressions.
//!
//! ## Generated Parser Structure
//! The generated parser will include:
//! - Token definitions
//! - Lexer implementation
//! - Parser struct with parsing functions
//! - Comprehensive documentation
//! - Example usage within test modules

use std::env;
use std::fs;
use std::io::{self, Write};
use std::collections::{HashSet, HashMap, VecDeque};

/// Represents a grammar rule
#[derive(Debug, Clone)]
struct Rule {
    head: String,
    bodies: Vec<Vec<String>>,
}

/// Represents the parsed grammar
#[derive(Debug)]
struct Grammar {
    rules: Vec<Rule>,
    terminals: HashSet<String>,
    non_terminals: HashSet<String>,
    first_sets: HashMap<String, HashSet<String>>,
    follow_sets: HashMap<String, HashSet<String>>,
}

impl Grammar {
    /// Parses the ENBF grammar from a string
    fn parse(enbf: &str) -> Result<Self, String> {
        let mut rules = Vec::new();
        let mut non_terminals = HashSet::new(); // To store non-terminals
        let mut terminals = HashSet::new();

        for (line_no, line) in enbf.lines().enumerate() {
            let line = line.trim();
            if line.is_empty() || line.starts_with("#") {
                continue;
            }
            let parts: Vec<&str> = line.split("::=").collect();
            if parts.len() != 2 {
                return Err(format!("Invalid rule at line {}", line_no + 1));
            }
            let head = parts[0].trim().to_string();
            non_terminals.insert(head.clone());
            let bodies_str = parts[1];
            let bodies: Vec<Vec<String>> = bodies_str.split('|').map(|body| {
                body.trim().split_whitespace().map(|s| s.to_string()).collect()
            }).collect();
            rules.push(Rule { head, bodies });
        }

        // Identify terminals
        for rule in &rules {
            for body in &rule.bodies {
                for symbol in body {
                    if !symbol.starts_with("<") && !symbol.ends_with(">")
                        && !symbol.starts_with("\"") && !symbol.starts_with("'")
                    {
                        terminals.insert(symbol.clone());
                    }
                }
            }
        }

        // Remove non-terminals from terminals set
        for nt in &non_terminals {
            terminals.remove(nt);
        }

        let mut grammar = Grammar {
            rules,
            terminals,
            non_terminals,
            first_sets: HashMap::new(),
            follow_sets: HashMap::new(),
        };

        grammar.compute_first_sets()?;
        grammar.compute_follow_sets()?;

        Ok(grammar)
    }

    /// Computes FIRST sets for all non-terminals
    fn compute_first_sets(&mut self) -> Result<(), String> {
        // Initialize FIRST sets
        for nt in &self.non_terminals {
            self.first_sets.insert(nt.clone(), HashSet::new());
        }

        let mut changed = true;

        while changed {
            changed = false;
            for rule in &self.rules {
                let head = &rule.head;
                let head_first = self.first_sets.get_mut(head).unwrap();
                for body in &rule.bodies {
                    let mut can_produce_epsilon = true;
                    for symbol in body {
                        if self.non_terminals.contains(symbol) {
                            let symbol_first = self.first_sets.get(symbol).unwrap();
                            let before = head_first.len();
                            head_first.extend(symbol_first.iter().filter(|&&s| s != "ε").cloned());
                            let after = head_first.len();
                            if after > before {
                                changed = true;
                            }
                            if !symbol_first.contains("ε") {
                                can_produce_epsilon = false;
                                break;
                            }
                        } else {
                            let before = head_first.len();
                            head_first.insert(symbol.clone());
                            let after = head_first.len();
                            if after > before {
                                changed = true;
                            }
                            can_produce_epsilon = false;
                            break;
                        }
                    }
                    if can_produce_epsilon {
                        let before = head_first.len();
                        head_first.insert("ε".to_string());
                        let after = head_first.len();
                        if after > before {
                            changed = true;
                        }
                    }
                }
            }
        }

        Ok(())
    }

    /// Computes FOLLOW sets for all non-terminals
    fn compute_follow_sets(&mut self) -> Result<(), String> {
        // Initialize FOLLOW sets
        for nt in &self.non_terminals {
            self.follow_sets.insert(nt.clone(), HashSet::new());
        }

        // Assume the first rule's head is the start symbol
        if let Some(start_rule) = self.rules.first() {
            self.follow_sets.get_mut(&start_rule.head).unwrap().insert("$".to_string()); // End marker
        } else {
            return Err("No rules found in the grammar.".to_string());
        }

        let mut changed = true;

        while changed {
            changed = false;
            for rule in &self.rules {
                let head = &rule.head;
                for body in &rule.bodies {
                    for i in 0..body.len() {
                        let symbol = &body[i];
                        if self.non_terminals.contains(symbol) {
                            let follow_set = self.follow_sets.get_mut(symbol).unwrap();
                            let before = follow_set.len();

                            // Compute FIRST of the rest of the body
                            let mut first_of_rest = HashSet::new();
                            let mut can_add_follow = true;
                            for sym in body.iter().skip(i + 1) {
                                if self.non_terminals.contains(sym) {
                                    let sym_first = self.first_sets.get(sym).unwrap();
                                    for f in sym_first {
                                        if f != "ε" {
                                            first_of_rest.insert(f.clone());
                                        }
                                    }
                                    if !sym_first.contains("ε") {
                                        can_add_follow = false;
                                        break;
                                    }
                                } else {
                                    first_of_rest.insert(sym.clone());
                                    can_add_follow = false;
                                    break;
                                }
                            }
                            // Add FIRST(rest) to FOLLOW(symbol)
                            follow_set.extend(first_of_rest);
                            if can_add_follow {
                                // If FIRST(rest) contains ε, add FOLLOW(head) to FOLLOW(symbol)
                                let head_follow = self.follow_sets.get(head).unwrap().clone();
                                follow_set.extend(head_follow);
                            }

                            let after = follow_set.len();
                            if after > before {
                                changed = true;
                            }
                        }
                    }
                }
            }
        }

        Ok(())
    }

    /// Generates Rust code for the parser
    fn generate_rust(&self, grammar_type: &str) -> String {
        let mut code = String::new();

        // Header with documentation
        code.push_str("//! # Generated Parser\n");
        code.push_str("//!\n");
        code.push_str("//! This parser was automatically generated by **Thepg**, a Rust-based parser generator.\n");
        code.push_str("//! It is designed to parse inputs based on the provided ENBF grammar.\n");
        code.push_str("//!\n");
        code.push_str("//! ## Features\n");
        code.push_str("//! - Lexer-free parsing\n");
        code.push_str("//! - Supports LL(1) and LL(k) parsing strategies\n");
        code.push_str("//!\n");
        code.push_str("//! ## Usage\n");
        code.push_str("//! ```rust\n");
        code.push_str("//! use crate::Parser;\n");
        code.push_str("//!\n");
        code.push_str("//! fn main() {\n");
        code.push_str("//!     let input = \"your_input_here\";\n");
        code.push_str("//!     let mut parser = Parser::new(input);\n");
        code.push_str("//!     match parser.parse() {\n");
        code.push_str("//!         Ok(_) => println!(\"Parsing succeeded.\"),\n");
        code.push_str("//!         Err(e) => println!(\"Parsing failed: {}\", e),\n");
        code.push_str("//!     }\n");
        code.push_str("//! }\n");
        code.push_str("//! ```\n");
        code.push_str("//!\n");
        code.push_str("//! ## Example\n");
        code.push_str("//! Given the following grammar:\n");
        code.push_str("//!\n");
        code.push_str("//! ```enbf\n");
        code.push_str("//! Expr ::= Term ExprPrime\n");
        code.push_str("//! ExprPrime ::= \"+\" Term ExprPrime | \"-\" Term ExprPrime | ε\n");
        code.push_str("//! Term ::= Factor TermPrime\n");
        code.push_str("//! TermPrime ::= \"*\" Factor TermPrime | \"/\" Factor TermPrime | ε\n");
        code.push_str("//! Factor ::= \"(\" Expr \")\" | \"id\"\n");
        code.push_str("//! ```\n");
        code.push_str("//!\n");
        code.push_str("//! After generating the parser, you can use it to parse arithmetic expressions like `id + id * id`.\n");
        code.push_str("//!\n");

        // Token definitions
        code.push_str("#[derive(Debug, PartialEq, Clone)]\n");
        code.push_str("pub enum Token {\n");
        for terminal in &self.terminals {
            code.push_str(&format!("    {},\n", Self::sanitize_token(terminal)));
        }
        code.push_str("    EOF,\n");
        code.push_str("}\n\n");

        // Lexer comments
        code.push_str("// The lexer is integrated within the parser and is lexer-free.\n");

        // Parser struct with documentation
        code.push_str("/// The Parser struct responsible for parsing the input string.\n");
        code.push_str("#[derive(Debug)]\n");
        code.push_str("pub struct Parser<'a> {\n");
        code.push_str("    input: Peekable<Chars<'a>>,\n");
        code.push_str("    current_token: Token,\n");
        code.push_str("}\n\n");

        // Implement Parser with documentation
        code.push_str("impl<'a> Parser<'a> {\n");
        code.push_str("    /// Creates a new parser instance with the given input string.\n");
        code.push_str("    ///\n");
        code.push_str("    /// # Arguments\n");
        code.push_str("    ///\n");
        code.push_str("    /// * `input` - A string slice that holds the input to be parsed.\n");
        code.push_str("    ///\n");
        code.push_str("    /// # Example\n");
        code.push_str("    ///\n");
        code.push_str("    /// ```rust\n");
        code.push_str("    /// let mut parser = Parser::new(\"id + id * id\");\n");
        code.push_str("    /// ```\n");
        code.push_str("    pub fn new(input: &'a str) -> Self {\n");
        code.push_str("        let mut chars = input.chars().peekable();\n");
        code.push_str("        let first_token = Parser::next_token(&mut chars);\n");
        code.push_str("        Parser {\n");
        code.push_str("            input: chars,\n");
        code.push_str("            current_token: first_token,\n");
        code.push_str("        }\n");
        code.push_str("    }\n\n");

        // Tokenizer with documentation
        code.push_str("    /// Retrieves the next token from the input.\n");
        code.push_str("    ///\n");
        code.push_str("    /// # Arguments\n");
        code.push_str("    ///\n");
        code.push_str("    /// * `chars` - A mutable reference to the Peekable character iterator.\n");
        code.push_str("    fn next_token(chars: &mut Peekable<Chars>) -> Token {\n");
        code.push_str("        while let Some(&c) = chars.peek() {\n");
        code.push_str("            match c {\n");
        for terminal in &self.terminals {
            if terminal.starts_with("\"") && terminal.ends_with("\"") {
                let symbol = &terminal[1..terminal.len()-1];
                if symbol.len() == 1 {
                    // Single character token
                    code.push_str(&format!("                '{}' => {{ chars.next(); Token::{} }},\n",
                        symbol.chars().next().unwrap(),
                        Self::sanitize_token(terminal)));
                } else {
                    // Multi-character token (not implemented)
                    // Placeholder for potential future implementation
                    code.push_str(&format!(
                        "                _ if chars.as_str().starts_with(\"{}\") => {{ for _ in 0..{} {{ chars.next(); }} Token::{} }},\n",
                        symbol,
                        symbol.len(),
                        Self::sanitize_token(terminal)
                    ));
                }
            } else if terminal.starts_with("'") && terminal.ends_with("'") {
                let symbol = &terminal[1..terminal.len()-1];
                if symbol.len() == 1 {
                    // Single character token
                    code.push_str(&format!("                '{}' => {{ chars.next(); Token::{} }},\n",
                        symbol.chars().next().unwrap(),
                        Self::sanitize_token(terminal)));
                }
            } else {
                // For simplicity, treat as identifier or number
                code.push_str(&format!("                _ if c.is_alphabetic() => Token::{},\n",
                    Self::sanitize_token(terminal)));
            }
        }
        code.push_str("                _ if c.is_whitespace() => { chars.next(); continue },\n");
        code.push_str("                _ => { chars.next(); Token::EOF },\n");
        code.push_str("            }\n");
        code.push_str("        }\n");
        code.push_str("        Token::EOF\n");
        code.push_str("    }\n\n");

        // Match and consume functions with documentation
        code.push_str("    /// Consumes the current token if it matches the expected token.\n");
        code.push_str("    ///\n");
        code.push_str("    /// # Arguments\n");
        code.push_str("    ///\n");
        code.push_str("    /// * `token` - The expected `Token` to consume.\n");
        code.push_str("    ///\n");
        code.push_str("    /// # Returns\n");
        code.push_str("    ///\n");
        code.push_str("    /// * `Ok(())` if the token matches and is consumed successfully.\n");
        code.push_str("    /// * `Err(String)` with an error message if the token does not match.\n");
        code.push_str("    fn eat(&mut self, token: Token) -> Result<(), String> {\n");
        code.push_str("        if self.current_token == token {\n");
        code.push_str("            self.current_token = Parser::next_token(&mut self.input);\n");
        code.push_str("            Ok(())\n");
        code.push_str("        } else {\n");
        code.push_str("            Err(format!(\"Expected {:?}, found {:?}\", token, self.current_token))\n");
        code.push_str("        }\n");
        code.push_str("    }\n\n");

        // Generate parsing functions using LL(1) table with documentation
        if grammar_type.to_uppercase() == "LL1" {
            for rule in &self.rules {
                let func_name = Self::sanitize_func(&rule.head);
                code.push_str(&format!("    /// Parses the `{}` non-terminal.\n", rule.head));
                code.push_str("    ///\n");
                code.push_str("    /// # Returns\n");
                code.push_str("    ///\n");
                code.push_str("    /// * `Ok(())` if parsing succeeds.\n");
                code.push_str("    /// * `Err(String)` with an error message if parsing fails.\n");
                code.push_str(&format!("    pub fn {}(&mut self) -> Result<(), String> {{\n", func_name));
                code.push_str("        match self.current_token {\n");
                for body in &rule.bodies {
                    if let Some(first) = Grammar::first_of_body(body, &self.first_sets) {
                        for terminal in &first {
                            if terminal != "ε" {
                                code.push_str(&format!("            Token::{} => {{\n",
                                    Self::sanitize_token(terminal)));
                                for symbol in body {
                                    if self.non_terminals.contains(symbol) {
                                        let sub_func = Self::sanitize_func(&symbol[1..symbol.len()-1]);
                                        code.push_str(&format!("                self.{}()?;\n", sub_func));
                                    } else {
                                        let tok = Self::sanitize_token(symbol);
                                        code.push_str(&format!("                self.eat(Token::{})?;\n", tok));
                                    }
                                }
                                code.push_str("                Ok(())\n");
                                code.push_str("            },\n");
                            }
                        }
                        if Grammar::body_can_produce_epsilon(body, &self.first_sets) {
                            let follow = self.follow_sets.get(&rule.head).unwrap();
                            for terminal in follow {
                                code.push_str(&format!("            Token::{} => {{\n",
                                    Self::sanitize_token(terminal)));
                                code.push_str("                // ε-production\n");
                                code.push_str("                Ok(())\n");
                                code.push_str("            },\n");
                            }
                        }
                    }
                }
                // Error case
                code.push_str("            _ => Err(format!(\"Unexpected token {:?} in parsing {}\", self.current_token, \"");
                code.push_str(&rule.head);
                code.push_str("\")),\n");
                code.push_str("        }\n");
                code.push_str("    }\n\n");
            }
        } else {
            // LL(k) not implemented in this example
            code.push_str("    // LL(k) parsing not implemented yet\n");
            for rule in &self.rules {
                let func_name = Self::sanitize_func(&rule.head);
                code.push_str(&format!("    /// Parses the `{}` non-terminal.\n", rule.head));
                code.push_str("    ///\n");
                code.push_str("    /// # Returns\n");
                code.push_str("    ///\n");
                code.push_str("    /// * `Ok(())` if parsing succeeds.\n");
                code.push_str("    /// * `Err(String)` with an error message if parsing fails.\n");
                code.push_str(&format!("    pub fn {}(&mut self) -> Result<(), String> {{\n", func_name));
                code.push_str("        // Implementation for LL(k) would go here\n");
                code.push_str("        Ok(())\n");
                code.push_str("    }\n\n");
            }
        }

        // Start symbol with documentation
        if let Some(start_rule) = self.rules.first() {
            let func_name = Self::sanitize_func(&start_rule.head);
            code.push_str("    /// Initiates the parsing process starting from the start symbol.\n");
            code.push_str("    ///\n");
            code.push_str("    /// # Returns\n");
            code.push_str("    ///\n");
            code.push_str("    /// * `Ok(())` if parsing succeeds.\n");
            code.push_str("    /// * `Err(String)` with an error message if parsing fails or extra tokens are found.\n");
            code.push_str("    pub fn parse(&mut self) -> Result<(), String> {\n");
            code.push_str(&format!("        self.{}()?\n", func_name));
            code.push_str("            .and_then(|_| {\n");
            code.push_str("                if self.current_token == Token::EOF {\n");
            code.push_str("                    Ok(())\n");
            code.push_str("                } else {\n");
            code.push_str("                    Err(\"Unexpected tokens after parsing complete\".to_string())\n");
            code.push_str("                }\n");
            code.push_str("            })\n");
            code.push_str("    }\n");
        }

        // End of impl
        code.push_str("}\n\n");

        // Example usage with documentation
        code.push_str("/// Example usage of the generated parser.\n");
        code.push_str("///\n");
        code.push_str("/// ```rust\n");
        code.push_str("/// use crate::Parser;\n");
        code.push_str("///\n");
        code.push_str("/// fn main() {\n");
        code.push_str("///     let input = \"id + id * id\";\n");
        code.push_str("///     let mut parser = Parser::new(input);\n");
        code.push_str("///     match parser.parse() {\n");
        code.push_str("///         Ok(_) => println!(\"Parsing succeeded.\"),\n");
        code.push_str("///         Err(e) => println!(\"Parsing failed: {}\", e),\n");
        code.push_str("///     }\n");
        code.push_str("/// }\n");
        code.push_str("/// ```\n\n");

        // Test module with documentation and example tests
        code.push_str("#[cfg(test)]\n");
        code.push_str("mod tests {\n");
        code.push_str("    use super::*;\n\n");
        code.push_str("    /// Tests the parser with a valid arithmetic expression.\n");
        code.push_str("    #[test]\n");
        code.push_str("    fn test_parser_valid() {\n");
        code.push_str("        let input = \"id + id * id\";\n");
        code.push_str("        let mut parser = Parser::new(input);\n");
        code.push_str("        assert!(parser.parse().is_ok());\n");
        code.push_str("    }\n\n");

        code.push_str("    /// Tests the parser with an input containing parentheses.\n");
        code.push_str("    #[test]\n");
        code.push_str("    fn test_parser_with_parentheses() {\n");
        code.push_str("        let input = \"( id + id ) * id\";\n");
        code.push_str("        let mut parser = Parser::new(input);\n");
        code.push_str("        assert!(parser.parse().is_ok());\n");
        code.push_str("    }\n\n");

        code.push_str("    /// Tests the parser with an invalid arithmetic expression.\n");
        code.push_str("    #[test]\n");
        code.push_str("    fn test_parser_invalid() {\n");
        code.push_str("        let input = \"id + * id\";\n");
        code.push_str("        let mut parser = Parser::new(input);\n");
        code.push_str("        assert!(parser.parse().is_err());\n");
        code.push_str("    }\n");
        code.push_str("}\n");

        code
    }

    /// Determines the FIRST set for a given body
    fn first_of_body(body: &Vec<String>, first_sets: &HashMap<String, HashSet<String>>) -> Option<HashSet<String>> {
        let mut first = HashSet::new();
        for symbol in body {
            if first_sets.contains_key(symbol) {
                let sym_first = &first_sets[symbol];
                first.extend(sym_first.iter().filter(|&&s| s != "ε").cloned());
                if !sym_first.contains("ε") {
                    return Some(first);
                }
            } else {
                first.insert(symbol.clone());
                return Some(first);
            }
        }
        first.insert("ε".to_string());
        Some(first)
    }

    /// Checks if a body can produce ε
    fn body_can_produce_epsilon(body: &Vec<String>, first_sets: &HashMap<String, HashSet<String>>) -> bool {
        for symbol in body {
            if first_sets.contains_key(symbol) {
                if !first_sets[symbol].contains("ε") {
                    return false;
                }
            } else {
                return false;
            }
        }
        true
    }

    /// Sanitizes token names to be Rust-compatible
    fn sanitize_token(token: &str) -> String {
        token.trim_matches('"')
             .trim_matches('\'')
             .replace("+", "PLUS")
             .replace("-", "MINUS")
             .replace("*", "STAR")
             .replace("/", "SLASH")
             .replace("(", "L_PAREN")
             .replace(")", "R_PAREN")
             .replace("{", "L_BRACE")
             .replace("}", "R_BRACE")
             .replace("[", "L_BRACKET")
             .replace("]", "R_BRACKET")
             .replace(",", "COMMA")
             .replace(";", "SEMICOLON")
             .replace(":", "COLON")
             .replace("<", "")
             .replace(">", "")
             .replace("|", "OR")
             .replace("=", "EQ")
             .replace("!", "EXCLAMATION")
             .replace("?", "QUESTION")
             .replace("#", "HASH")
             .replace("$", "DOLLAR")
             .replace("&", "AMPERSAND")
             .replace("@", "AT")
             .replace("~", "TILDE")
             .replace(".", "DOT")
             .replace("'", "")
             .to_uppercase()
    }

    /// Sanitizes function names to be Rust-compatible
    fn sanitize_func(func: &str) -> String {
        func.to_lowercase()
            .replace("<", "")
            .replace(">", "")
            .replace("-", "_")
            .replace(" ", "_")
    }
}

/// Entry point for Thepg
fn main() -> Result<(), String> {
    let args: Vec<String> = env::args().collect();
    if args.len() < 3 {
        return Err("Usage: thepg <input.enbf> -o <output.rs> --grammar-type <LL1|LLk>".to_string());
    }

    let input_file = &args[1];
    let mut output_file = String::from("parser.rs");
    let mut grammar_type = "LL1".to_string();

    let mut i = 2;
    while i < args.len() {
        match args[i].as_str() {
            "-o" => {
                if i + 1 < args.len() {
                    output_file = args[i + 1].clone();
                    i += 2;
                } else {
                    return Err("Expected output file after -o".to_string());
                }
            },
            "--grammar-type" => {
                if i + 1 < args.len() {
                    grammar_type = args[i + 1].clone();
                    i += 2;
                } else {
                    return Err("Expected grammar type after --grammar-type".to_string());
                }
            },
            _ => i += 1,
        }
    }

    let enbf = fs::read_to_string(input_file)
        .map_err(|e| format!("Failed to read input file: {}", e))?;
    
    let grammar = Grammar::parse(&enbf)?;

    // Optionally, check if the grammar is LL(1)
    if grammar_type.to_uppercase() == "LL1" {
        if !is_ll1(&grammar) {
            return Err("The provided grammar is not LL(1).".to_string());
        }
    }

    let rust_code = grammar.generate_rust(&grammar_type);

    fs::write(&output_file, rust_code)
        .map_err(|e| format!("Failed to write output file: {}", e))?;

    println!("Parser generated successfully in {}", output_file);
    Ok(())
}

/// Checks if the grammar is LL(1) by ensuring no parsing table conflicts
fn is_ll1(grammar: &Grammar) -> bool {
    // For each non-terminal, ensure that the FIRST sets of its productions are disjoint
    for rule in &grammar.rules {
        let mut first_sets = Vec::new();
        for body in &rule.bodies {
            if let Some(first) = Grammar::first_of_body(body, &grammar.first_sets) {
                first_sets.push(first);
            }
        }
        // Check pairwise disjoint
        for i in 0..first_sets.len() {
            for j in (i + 1)..first_sets.len() {
                let intersection: HashSet<_> = first_sets[i].intersection(&first_sets[j]).collect();
                if !intersection.is_empty() {
                    return false;
                }
            }
        }
    }
    true
}