Skip to content
TheChatArchiveThe Chat Archive
o1-preview-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

#!/usr/bin/env rust-script //! # Thepg: A Comprehensive Parser Generator in Rust //! //!…

  1. User

    #!/usr/bin/env rust-script //! # Thepg: A Comprehensive Parser Generator in Rust //! //! Thepg is a powerful parser generator that processes Extended Backus–Naur Form (ENBF) grammars //! and produces robust, compile-ready Rust code for parsing based on the provided grammar. //! //! ## Features //! - Supports LL(1) and LL(k) parsing strategies //! - Generates lexing-capable parsers with support for identifiers and literals //! - Outputs well-structured Rust code in a single file //! - Constructs Abstract Syntax Trees (AST) during the parsing process //! - Comprehensive error handling with informative messages //! - User-friendly command-line interface using clap //! //! ## Usage //! To generate a parser, run the following command: //! //! bash //! cargo run --release -- <grammar.enbf> -o <output_file.rs> --grammar-type <LL1|LLk> --lookahead <k> //! //! //! - Replace <grammar.enbf> with your ENBF grammar file. //! - Replace <output_file.rs> with your desired output Rust file name. //! - Use --grammar-type to specify the parsing strategy (LL1 or LLk). //! - Use --lookahead to define the number of tokens to look ahead (applicable for LLk parsing). //! //! ## 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" | "number" //! //! //! Generate the parser as follows: //! //! bash //! cargo run --release -- arithmetic.enbf -o arithmetic_parser.rs --grammar-type LL1 //! //! //! The above command will create arithmetic_parser.rs containing the lexer, parser, and AST definitions //! based on the provided grammar. //! //! ## Testing //! Execute the embedded test cases using Cargo: //! //! bash //! cargo test //! //! //! ## License //! MIT License. See LICENSE for details.

    extern crate clap; extern crate regex;

    use clap::{Arg, ArgAction, Command}; use regex::Regex; use std::collections::{HashMap, HashSet, VecDeque}; use std::fs;

    /// Represents various parsing errors. #[derive(Debug)] enum ParseError { /// Unexpected token encountered during parsing. UnexpectedToken { expected: Vec, found: String, position: usize, }, /// Invalid grammar structure. InvalidGrammar(String), /// Lexer encountered an error. LexerError(String), }

    impl std::fmt::Display for ParseError { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { match self { ParseError::UnexpectedToken { expected, found, position, } => write!( f, "Unexpected token at position {}: expected {:?}, found {}", position, expected, found ), ParseError::InvalidGrammar(msg) => write!(f, "Invalid grammar: {}", msg), ParseError::LexerError(msg) => write!(f, "Lexer error: {}", msg), } } }

    impl std::error::Error for ParseError {}

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

    /// Represents the entire parsed grammar, including rules, terminals, non-terminals, and FIRST/FOLLOW sets. #[derive(Debug, Clone)] struct Grammar { rules: Vec, terminals: HashSet, non_terminals: HashSet, first_sets: HashMap<String, HashSet>, follow_sets: HashMap<String, HashSet>, }

    impl Grammar { /// Parses the ENBF grammar from a string input. fn parse(enbf: &str) -> Result<Self, ParseError> { 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(ParseError::InvalidGrammar(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.trim_matches('"').trim_matches('\'').to_string())
                        .collect()
                })
                .collect();
            rules.push(Rule { head, bodies });
        }
    
        // Identify terminals (symbols not defined as non-terminals and not ε)
        for rule in &rules {
            for body in &rule.bodies {
                for symbol in body {
                    if symbol != "ε" && !non_terminals.contains(symbol) {
                        terminals.insert(symbol.clone());
                    }
                }
            }
        }
    
        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 using a queue-based iterative approach.
    fn compute_first_sets(&mut self) -> Result<(), ParseError> {
        // Initialize FIRST sets
        for nt in &self.non_terminals {
            self.first_sets.insert(nt.clone(), HashSet::new());
        }
    
        let mut queue: VecDeque<String> = VecDeque::new();
    
        // Initialize queue with all non-terminals
        for nt in &self.non_terminals {
            queue.push_back(nt.clone());
        }
    
        while let Some(nt) = queue.pop_front() {
            let mut updated = false;
            let mut nt_first = self.first_sets.get(&nt).unwrap().clone();
    
            for rule in self.rules.iter().filter(|r| r.head == nt) {
                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[symbol];
                            let before = nt_first.len();
                            nt_first.extend(symbol_first.iter().filter(|&s| s != "ε").cloned());
                            let after = nt_first.len();
                            if after > before {
                                updated = true;
                            }
                            if !symbol_first.contains("ε") {
                                can_produce_epsilon = false;
                                break;
                            }
                        } else {
                            let before = nt_first.len();
                            nt_first.insert(symbol.clone());
                            let after = nt_first.len();
                            if after > before {
                                updated = true;
                            }
                            can_produce_epsilon = false;
                            break;
                        }
                    }
                    if can_produce_epsilon {
                        if nt_first.insert("ε".to_string()) {
                            updated = true;
                        }
                    }
                }
            }
    
            if updated {
                self.first_sets.insert(nt.clone(), nt_first.clone());
                // Enqueue dependent non-terminals
                for rule in &self.rules {
                    for body in &rule.bodies {
                        if body.contains(&nt) {
                            if !queue.contains(&rule.head) {
                                queue.push_back(rule.head.clone());
                            }
                        }
                    }
                }
            }
        }
    
        Ok(())
    }
    
    /// Computes FOLLOW sets for all non-terminals using a queue-based iterative approach.
    fn compute_follow_sets(&mut self) -> Result<(), ParseError> {
        // 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(ParseError::InvalidGrammar(
                "No rules found in the grammar.".to_string(),
            ));
        }
    
        let mut queue: VecDeque<String> = VecDeque::new();
        // Enqueue all non-terminals initially
        for nt in &self.non_terminals {
            queue.push_back(nt.clone());
        }
    
        while let Some(nt) = queue.pop_front() {
            let mut nt_follow = self.follow_sets.get(&nt).unwrap().clone();
            let mut updated = false;
    
            for rule in &self.rules {
                for body in &rule.bodies {
                    for i in 0..body.len() {
                        if body[i] == nt {
                            // Compute FIRST of the remaining symbols in the production
                            let mut first_of_suffix = 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[sym];
                                    first_of_suffix.extend(
                                        sym_first.iter().filter(|&s| s != "ε").cloned(),
                                    );
                                    if !sym_first.contains("ε") {
                                        can_add_follow = false;
                                        break;
                                    }
                                } else {
                                    first_of_suffix.insert(sym.clone());
                                    can_add_follow = false;
                                    break;
                                }
                            }
                            // Add FIRST(suffix) \ {ε} to FOLLOW(nt)
                            let before = nt_follow.len();
                            nt_follow.extend(first_of_suffix.iter().cloned());
                            let after = nt_follow.len();
                            if after > before {
                                updated = true;
                            }
                            // If FIRST(suffix) contains ε, add FOLLOW(head) to FOLLOW(nt)
                            if can_add_follow {
                                let head_follow = &self.follow_sets[&rule.head];
                                let before = nt_follow.len();
                                nt_follow.extend(head_follow.iter().cloned());
                                let after = nt_follow.len();
                                if after > before {
                                    updated = true;
                                }
                            }
                        }
                    }
                }
            }
    
            if updated {
                self.follow_sets.insert(nt.clone(), nt_follow.clone());
                // Enqueue dependent non-terminals
                for rule in &self.rules {
                    for body in &rule.bodies {
                        if body.contains(&nt) {
                            if !queue.contains(&rule.head) {
                                queue.push_back(rule.head.clone());
                            }
                        }
                    }
                }
            }
        }
    
        Ok(())
    }
    
    /// Determines the FIRST set for a given production 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 symbol == "ε" {
                first.insert("ε".to_string());
                return Some(first);
            }
            if let Some(sym_first) = first_sets.get(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 production body can produce ε (epsilon).
    fn body_can_produce_epsilon(
        body: &Vec<String>,
        first_sets: &HashMap<String, HashSet<String>>,
    ) -> bool {
        body.iter().all(|symbol| {
            if let Some(sym_first) = first_sets.get(symbol) {
                sym_first.contains("ε")
            } else {
                false
            }
        })
    }
    
    /// Sanitizes token names to be Rust-compatible by replacing or removing invalid characters.
    fn sanitize_token(token: &str) -> String {
        token
            .trim_matches('"')
            .trim_matches('\'')
            .replace("+", "PLUS")
            .replace("-", "MINUS")
            .replace("*", "STAR")
            .replace("/", "SLASH")
            .replace("(", "LPAREN")
            .replace(")", "RPAREN")
            .replace("{", "LBRACE")
            .replace("}", "RBRACE")
            .replace("[", "LBRACKET")
            .replace("]", "RBRACKET")
            .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 by converting to lowercase and replacing invalid characters.
    fn sanitize_func(func: &str) -> String {
        func.to_lowercase()
            .replace("<", "")
            .replace(">", "")
            .replace("-", "_")
            .replace(" ", "_")
    }
    

    }

    /// Represents the different types of tokens. #[derive(Debug, PartialEq, Clone)] enum TokenEnum { // Fixed symbols PLUS, MINUS, STAR, SLASH, LPAREN, RPAREN, // Multi-character symbols (if any) EQ, NEQ, LEQ, GEQ, // Pattern-based tokens ID(String), NUMBER(i32), EOF, }

    /// The Lexer struct responsible for tokenizing the input string. struct Lexer { input: std::iter::Peekable<std::str::Chars<'static>>, buffer: Vec, // Buffer for lookahead regex_map: Vec<(Regex, fn(&str) -> TokenEnum)>, // Regex patterns and corresponding token constructors current_position: usize, // Current character position in input }

    impl Lexer { /// Creates a new Lexer instance. fn new(input: &str) -> Self { let input_owned = input.to_string(); let input_static: &'static str = Box::leak(input_owned.into_boxed_str());

        // Define token constructors as functions
        fn construct_eq(_s: &str) -> TokenEnum {
            TokenEnum::EQ
        }
        fn construct_neq(_s: &str) -> TokenEnum {
            TokenEnum::NEQ
        }
        fn construct_leq(_s: &str) -> TokenEnum {
            TokenEnum::LEQ
        }
        fn construct_geq(_s: &str) -> TokenEnum {
            TokenEnum::GEQ
        }
        fn construct_plus(_s: &str) -> TokenEnum {
            TokenEnum::PLUS
        }
        fn construct_minus(_s: &str) -> TokenEnum {
            TokenEnum::MINUS
        }
        fn construct_star(_s: &str) -> TokenEnum {
            TokenEnum::STAR
        }
        fn construct_slash(_s: &str) -> TokenEnum {
            TokenEnum::SLASH
        }
        fn construct_lparen(_s: &str) -> TokenEnum {
            TokenEnum::LPAREN
        }
        fn construct_rparen(_s: &str) -> TokenEnum {
            TokenEnum::RPAREN
        }
        fn construct_id(s: &str) -> TokenEnum {
            TokenEnum::ID(s.to_string())
        }
        fn construct_number(s: &str) -> TokenEnum {
            TokenEnum::NUMBER(s.parse().unwrap())
        }
    
        let mut regex_map: Vec<(Regex, fn(&str) -> TokenEnum)> = Vec::new();
    
        // Order matters: longer patterns first
        regex_map.push((Regex::new(r"^\==").unwrap(), construct_eq));
        regex_map.push((Regex::new(r"^\!=").unwrap(), construct_neq));
        regex_map.push((Regex::new(r"^<=").unwrap(), construct_leq));
        regex_map.push((Regex::new(r"^>=").unwrap(), construct_geq));
        regex_map.push((Regex::new(r"^\+").unwrap(), construct_plus));
        regex_map.push((Regex::new(r"^\-").unwrap(), construct_minus));
        regex_map.push((Regex::new(r"^\*").unwrap(), construct_star));
        regex_map.push((Regex::new(r"^\/").unwrap(), construct_slash));
        regex_map.push((Regex::new(r"^\(").unwrap(), construct_lparen));
        regex_map.push((Regex::new(r"^\)").unwrap(), construct_rparen));
        // Identifiers
        regex_map.push((Regex::new(r"^[a-zA-Z_][a-zA-Z0-9_]*").unwrap(), construct_id));
        // Numbers
        regex_map.push((Regex::new(r"^\d+").unwrap(), construct_number));
    
        Lexer {
            input: input_static.chars().peekable(),
            buffer: Vec::new(),
            regex_map,
            current_position: 0,
        }
    }
    
    /// Retrieves the next token from the buffer or lexer.
    fn next_token(&mut self) -> TokenEnum {
        if !self.buffer.is_empty() {
            self.buffer.remove(0)
        } else {
            self.lex_next_token()
        }
    }
    
    /// Peeks `k` tokens ahead without consuming them.
    fn peek(&mut self, k: usize) -> Vec<TokenEnum> {
        while self.buffer.len() < k {
            let token = self.lex_next_token();
            if token == TokenEnum::EOF {
                break;
            }
            self.buffer.push(token);
        }
        self.buffer.iter().cloned().take(k).collect()
    }
    
    /// Lexes the next token using regex patterns.
    fn lex_next_token(&mut self) -> TokenEnum {
        // Skip leading whitespace
        while let Some(&ch) = self.input.peek() {
            if ch.is_whitespace() {
                self.input.next();
                self.current_position += 1;
            } else {
                break;
            }
        }
        // Now try to match tokens
        let remaining: String = self.input.clone().collect();
        for (regex, constructor) in &self.regex_map {
            if let Some(mat) = regex.find(&remaining) {
                let matched_str = mat.as_str();
                let token = constructor(matched_str);
                // Advance the input by the length of the matched string
                for _ in 0..matched_str.len() {
                    self.input.next();
                    self.current_position += 1;
                }
                return token;
            }
        }
    
        // If no regex matched, handle unknown characters
        if let Some(c) = self.input.next() {
            self.current_position += 1;
            eprintln!("Warning: Unrecognized character '{}'", c);
            self.lex_next_token() // Skip the unrecognized character and try again
        } else {
            TokenEnum::EOF
        }
    }
    

    }

    /// Represents an AST Node. #[derive(Debug, PartialEq, Clone)] enum ASTNode { NonTerminal(String, Vec), Terminal(TokenEnum), Identifier(String), Number(i32), }

    /// The Parser struct responsible for parsing the input and constructing the AST. struct ParserStruct<'a> { lexer: Lexer, current_token: TokenEnum, lookahead: Vec, grammar: &'a Grammar, k: usize, // Lookahead size position: usize, // Current parsing position }

    impl<'a> ParserStruct<'a> { /// Creates a new Parser instance with the given input string, grammar, and lookahead size. fn new(input: &'a str, grammar: &'a Grammar, k: usize) -> Self { let mut lexer = Lexer::new(input); let first_token = lexer.next_token(); ParserStruct { lexer, current_token: first_token, lookahead: Vec::new(), grammar, k, position: 0, } }

    /// Initiates the parsing process starting from the start symbol.
    fn parse(&mut self) -> Result<ASTNode, ParseError> {
        if let Some(start_rule) = self.grammar.rules.first() {
            let ast = self.parse_non_terminal(&start_rule.head)?;
            if self.current_token == TokenEnum::EOF {
                Ok(ast)
            } else {
                Err(ParseError::UnexpectedToken {
                    expected: vec!["EOF".to_string()],
                    found: format!("{:?}", self.current_token),
                    position: self.position,
                })
            }
        } else {
            Err(ParseError::InvalidGrammar(
                "No rules defined in the grammar.".to_string(),
            ))
        }
    }
    
    /// Parses a non-terminal symbol considering LL(k) lookahead.
    fn parse_non_terminal(&mut self, non_terminal: &str) -> Result<ASTNode, ParseError> {
        if let Some(rule) = self.grammar.rules.iter().find(|r| r.head == non_terminal) {
            for body in &rule.bodies {
                let first_set =
                    Grammar::first_of_body(body, &self.grammar.first_sets).unwrap();
                let tokens = self.lexer.peek(self.k);
                let intersects =
                    self.should_use_production(&first_set, &tokens, non_terminal)?;
    
                if intersects || first_set.contains("ε") {
                    let node = self.parse_production(body)?;
                    return Ok(ASTNode::NonTerminal(non_terminal.to_string(), vec![node]));
                }
            }
            Err(ParseError::UnexpectedToken {
                expected: vec!["valid production".to_string()],
                found: format!("{:?}", self.current_token),
                position: self.position,
            })
        } else {
            Err(ParseError::InvalidGrammar(format!(
                "Non-terminal '{}' not found in grammar",
                non_terminal
            )))
        }
    }
    
    /// Determines whether to use a production based on the FIRST set and lookahead tokens.
    fn should_use_production(
        &self,
        first_set: &HashSet<String>,
        tokens: &Vec<TokenEnum>,
        non_terminal: &str,
    ) -> Result<bool, ParseError> {
        for t in first_set {
            match t.as_str() {
                "ε" => {
                    let follow_set = &self.grammar.follow_sets[non_terminal];
                    for tok in tokens {
                        if follow_set.contains("$") && *tok == TokenEnum::EOF {
                            return Ok(true);
                        }
                        match tok {
                            TokenEnum::ID(_) => {
                                if follow_set.contains("id") {
                                    return Ok(true);
                                }
                            }
                            TokenEnum::NUMBER(_) => {
                                if follow_set.contains("number") {
                                    return Ok(true);
                                }
                            }
                            TokenEnum::PLUS => {
                                if follow_set.contains("+") {
                                    return Ok(true);
                                }
                            }
                            TokenEnum::MINUS => {
                                if follow_set.contains("-") {
                                    return Ok(true);
                                }
                            }
                            TokenEnum::STAR => {
                                if follow_set.contains("*") {
                                    return Ok(true);
                                }
                            }
                            TokenEnum::SLASH => {
                                if follow_set.contains("/") {
                                    return Ok(true);
                                }
                            }
                            TokenEnum::LPAREN => {
                                if follow_set.contains("(") {
                                    return Ok(true);
                                }
                            }
                            TokenEnum::RPAREN => {
                                if follow_set.contains(")") {
                                    return Ok(true);
                                }
                            }
                            _ => {}
                        }
                    }
                }
                "id" => {
                    if tokens.iter().any(|tok| matches!(tok, TokenEnum::ID(_))) {
                        return Ok(true);
                    }
                }
                "number" => {
                    if tokens.iter().any(|tok| matches!(tok, TokenEnum::NUMBER(_))) {
                        return Ok(true);
                    }
                }
                "+" => {
                    if tokens.iter().any(|tok| matches!(tok, TokenEnum::PLUS)) {
                        return Ok(true);
                    }
                }
                "-" => {
                    if tokens.iter().any(|tok| matches!(tok, TokenEnum::MINUS)) {
                        return Ok(true);
                    }
                }
                "*" => {
                    if tokens.iter().any(|tok| matches!(tok, TokenEnum::STAR)) {
                        return Ok(true);
                    }
                }
                "/" => {
                    if tokens.iter().any(|tok| matches!(tok, TokenEnum::SLASH)) {
                        return Ok(true);
                    }
                }
                "(" => {
                    if tokens.iter().any(|tok| matches!(tok, TokenEnum::LPAREN)) {
                        return Ok(true);
                    }
                }
                ")" => {
                    if tokens.iter().any(|tok| matches!(tok, TokenEnum::RPAREN)) {
                        return Ok(true);
                    }
                }
                _ => {}
            }
        }
        Ok(false)
    }
    
    /// Parses a production body and constructs the corresponding AST node.
    fn parse_production(&mut self, body: &Vec<String>) -> Result<ASTNode, ParseError> {
        let mut children = Vec::new();
        for symbol in body {
            if self.grammar.non_terminals.contains(symbol) {
                let child = self.parse_non_terminal(symbol)?;
                children.push(child);
            } else {
                match symbol.as_str() {
                    "+" => {
                        self.eat(TokenEnum::PLUS)?;
                        children.push(ASTNode::Terminal(TokenEnum::PLUS));
                    }
                    "-" => {
                        self.eat(TokenEnum::MINUS)?;
                        children.push(ASTNode::Terminal(TokenEnum::MINUS));
                    }
                    "*" => {
                        self.eat(TokenEnum::STAR)?;
                        children.push(ASTNode::Terminal(TokenEnum::STAR));
                    }
                    "/" => {
                        self.eat(TokenEnum::SLASH)?;
                        children.push(ASTNode::Terminal(TokenEnum::SLASH));
                    }
                    "(" => {
                        self.eat(TokenEnum::LPAREN)?;
                        children.push(ASTNode::Terminal(TokenEnum::LPAREN));
                    }
                    ")" => {
                        self.eat(TokenEnum::RPAREN)?;
                        children.push(ASTNode::Terminal(TokenEnum::RPAREN));
                    }
                    "id" => {
                        if let TokenEnum::ID(value) = self.current_token.clone() {
                            self.eat(TokenEnum::ID(value.clone()))?;
                            children.push(ASTNode::Identifier(value));
                        } else {
                            return Err(ParseError::UnexpectedToken {
                                expected: vec!["id".to_string()],
                                found: format!("{:?}", self.current_token),
                                position: self.position,
                            });
                        }
                    }
                    "number" => {
                        if let TokenEnum::NUMBER(value) = self.current_token.clone() {
                            self.eat(TokenEnum::NUMBER(value))?;
                            children.push(ASTNode::Number(value));
                        } else {
                            return Err(ParseError::UnexpectedToken {
                                expected: vec!["number".to_string()],
                                found: format!("{:?}", self.current_token),
                                position: self.position,
                            });
                        }
                    }
                    "ε" => {
                        // Epsilon production, do nothing
                    }
                    _ => {
                        return Err(ParseError::InvalidGrammar(format!(
                            "Unknown terminal symbol '{}'",
                            symbol
                        )));
                    }
                }
            }
        }
        Ok(ASTNode::NonTerminal(body.join(" "), children))
    }
    
    /// Consumes the current token if it matches the expected token.
    fn eat(&mut self, token: TokenEnum) -> Result<(), ParseError> {
        if self.current_token == token {
            self.current_token = self.lexer.next_token();
            self.position += 1;
            Ok(())
        } else {
            Err(ParseError::UnexpectedToken {
                expected: vec![format!("{:?}", token)],
                found: format!("{:?}", self.current_token),
                position: self.position,
            })
        }
    }
    

    }

    /// Generates Rust code for the parser based on the parsed grammar. struct CodeGenerator { grammar: Grammar, grammar_type: String, lookahead: usize, }

    impl CodeGenerator { /// Creates a new CodeGenerator instance. fn new(grammar: &Grammar, grammar_type: &str, lookahead: usize) -> Self { CodeGenerator { grammar: grammar.clone(), grammar_type: grammar_type.to_string(), lookahead, } }

    /// Generates the complete Rust code for the parser.
    fn generate_code(&self, output_file: &str) -> Result<(), String> {
        let code =
            "// Generated parser code goes here (code generation logic not fully implemented)"
                .to_string();
    
        // Write the generated code to the output file
        fs::write(output_file, code).map_err(|e| format!("Failed to write output file: {}", e))
    }
    

    }

    /// Entry point for Thepg fn main() -> Result<(), Box> { // Define the CLI using clap let matches = Command::new("Thepg") .version("1.0") .author("Your Name youremail@example.com") .about("A Rust-Based Parser Generator for ENBF Grammars") .arg( Arg::new("input") .short('i') .long("input") .value_name("FILE") .help("Input ENBF grammar file") .required(true), ) .arg( Arg::new("output") .short('o') .long("output") .value_name("FILE") .help("Output Rust file for the generated parser") .required(true), ) .arg( Arg::new("grammar_type") .short('g') .long("grammar-type") .value_name("TYPE") .help("Grammar type: LL1 or LLk") .required(true), ) .arg( Arg::new("lookahead") .short('k') .long("lookahead") .value_name("K") .help("Number of tokens to look ahead (applicable for LLk)") .default_value("1"), ) .arg( Arg::new("verbose") .short('v') .long("verbose") .help("Enable verbose output") .action(ArgAction::SetTrue), ) .get_matches();

    // Extract arguments
    let input_file = matches
        .get_one::<String>("input")
        .expect("Input file is required");
    let output_file = matches
        .get_one::<String>("output")
        .expect("Output file is required");
    let grammar_type = matches
        .get_one::<String>("grammar_type")
        .expect("Grammar type is required");
    let lookahead: usize = matches
        .get_one::<String>("lookahead")
        .unwrap()
        .parse()
        .unwrap_or(1);
    let verbose = matches.get_flag("verbose");
    
    if verbose {
        println!("Input File: {}", input_file);
        println!("Output File: {}", output_file);
        println!("Grammar Type: {}", grammar_type);
        println!("Lookahead Size: {}", lookahead);
    }
    
    // Read the ENBF grammar file
    let enbf = fs::read_to_string(input_file)
        .map_err(|e| ParseError::InvalidGrammar(format!("Failed to read input file: {}", e)))?;
    
    // Parse the grammar
    let mut grammar = Grammar::parse(&enbf)?;
    if verbose {
        println!("Grammar parsed successfully.");
    }
    
    // Check if the grammar is LL(1) if specified
    if grammar_type.to_uppercase() == "LL1" {
        if !grammar.compute_first_sets().is_ok() || !grammar.compute_follow_sets().is_ok() {
            return Err(Box::new(ParseError::InvalidGrammar(
                "Failed to compute FIRST/FOLLOW sets.".to_string(),
            )));
        }
        if let Err(_) = grammar.compute_follow_sets() {
            return Err(Box::new(ParseError::InvalidGrammar(
                "Failed to compute FOLLOW sets.".to_string(),
            )));
        }
        // You can implement the is_ll1 method here if needed
        if verbose {
            println!("Grammar processing completed.");
        }
    }
    
    // Generate Rust code for the parser
    let code_generator = CodeGenerator::new(&grammar, grammar_type, lookahead);
    code_generator.generate_code(output_file)?;
    
    if verbose {
        println!("Parser generated successfully at '{}'.", output_file);
    }
    
    Ok(())
    

    }

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

    #[test]
    fn test_sanitize_token() {
        assert_eq!(Grammar::sanitize_token("+"), "PLUS");
        assert_eq!(Grammar::sanitize_token("-"), "MINUS");
        assert_eq!(Grammar::sanitize_token("*"), "STAR");
        assert_eq!(Grammar::sanitize_token("/"), "SLASH");
        assert_eq!(Grammar::sanitize_token("("), "LPAREN");
        assert_eq!(Grammar::sanitize_token(")"), "RPAREN");
        assert_eq!(Grammar::sanitize_token("id"), "ID");
        assert_eq!(Grammar::sanitize_token("number"), "NUMBER");
    }
    
    #[test]
    fn test_sanitize_func() {
        assert_eq!(Grammar::sanitize_func("Expr"), "expr");
        assert_eq!(Grammar::sanitize_func("ExprPrime"), "exprprime");
        assert_eq!(Grammar::sanitize_func("Term"), "term");
        assert_eq!(Grammar::sanitize_func("TermPrime"), "termprime");
        assert_eq!(Grammar::sanitize_func("Factor"), "factor");
    }
    
    #[test]
    fn test_first_of_body() {
        let mut first_sets = HashMap::new();
        first_sets.insert(
            "Term".to_string(),
            vec!["id".to_string(), "number".to_string()]
                .into_iter()
                .collect(),
        );
        first_sets.insert(
            "ExprPrime".to_string(),
            vec!["+".to_string(), "-".to_string(), "ε".to_string()]
                .into_iter()
                .collect(),
        );
    
        let body = vec!["Term".to_string(), "ExprPrime".to_string()];
        let first = Grammar::first_of_body(&body, &first_sets).unwrap();
        assert!(first.contains("id"));
        assert!(first.contains("number"));
    }
    
    #[test]
    fn test_body_can_produce_epsilon() {
        let mut first_sets = HashMap::new();
        first_sets.insert("A".to_string(), vec!["ε".to_string()].into_iter().collect());
        first_sets.insert("B".to_string(), vec!["ε".to_string()].into_iter().collect());
    
        let body = vec!["A".to_string(), "B".to_string()];
        assert!(Grammar::body_can_produce_epsilon(&body, &first_sets));
    }
    
    #[test]
    fn test_parse_grammar() {
        let enbf = r#"
            Expr ::= Term ExprPrime
            ExprPrime ::= "+" Term ExprPrime | "-" Term ExprPrime | ε
            Term ::= Factor TermPrime
            TermPrime ::= "*" Factor TermPrime | "/" Factor TermPrime | ε
            Factor ::= "(" Expr ")" | "id" | "number"
        "#;
        let grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
        assert_eq!(grammar.rules.len(), 5);
        assert!(grammar.terminals.contains("+"));
        assert!(grammar.terminals.contains("-"));
        assert!(grammar.non_terminals.contains("Expr"));
        assert!(grammar.first_sets.contains_key("Expr"));
        assert!(grammar.follow_sets.contains_key("Expr"));
    }
    
    #[test]
    fn test_parser_valid_input() {
        let enbf = r#"
            Expr ::= Term ExprPrime
            ExprPrime ::= "+" Term ExprPrime | "-" Term ExprPrime | ε
            Term ::= Factor TermPrime
            TermPrime ::= "*" Factor TermPrime | "/" Factor TermPrime | ε
            Factor ::= "(" Expr ")" | "id" | "number"
        "#;
        let mut grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
        grammar
            .compute_first_sets()
            .expect("Failed to compute FIRST sets");
        grammar
            .compute_follow_sets()
            .expect("Failed to compute FOLLOW sets");
        let input = "id + id * id";
        let mut parser = ParserStruct::new(input, &grammar, 2);
        let ast = parser.parse().expect("Parser failed on valid input");
        assert!(matches!(ast, ASTNode::NonTerminal(_, _)));
    }
    
    #[test]
    fn test_parser_invalid_input() {
        let enbf = r#"
            Expr ::= Term ExprPrime
            ExprPrime ::= "+" Term ExprPrime | "-" Term ExprPrime | ε
            Term ::= Factor TermPrime
            TermPrime ::= "*" Factor TermPrime | "/" Factor TermPrime | ε
            Factor ::= "(" Expr ")" | "id" | "number"
        "#;
        let mut grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
        grammar
            .compute_first_sets()
            .expect("Failed to compute FIRST sets");
        grammar
            .compute_follow_sets()
            .expect("Failed to compute FOLLOW sets");
        let input = "id + * id";
        let mut parser = ParserStruct::new(input, &grammar, 2);
        let result = parser.parse();
        assert!(matches!(result, Err(ParseError::UnexpectedToken { .. })));
    }
    
    #[test]
    fn test_empty_input() {
        let enbf = r#"
            Expr ::= Term
            Term ::= "id" | "number"
        "#;
        let mut grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
        grammar
            .compute_first_sets()
            .expect("Failed to compute FIRST sets");
        grammar
            .compute_follow_sets()
            .expect("Failed to compute FOLLOW sets");
        let input = "";
        let mut parser = ParserStruct::new(input, &grammar, 1);
        let result = parser.parse();
        assert!(matches!(result, Err(ParseError::UnexpectedToken { .. })));
    }
    

    }

    running 8 tests test tests::test_body_can_produce_epsilon ... ok test tests::test_first_of_body ... ok test tests::test_parse_grammar ... ok test tests::test_empty_input ... ok test tests::test_parser_invalid_input ... ok test tests::test_sanitize_func ... ok test tests::test_sanitize_token ... ok test tests::test_parser_valid_input ... FAILED

    failures:

    ---- tests::test_parser_valid_input stdout ---- thread 'tests::test_parser_valid_input' panicked at src/lib.rs:1088:34: Parser failed on valid input: UnexpectedToken { expected: ["STAR"], found: "PLUS", position: 1 } note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

    failures: tests::test_parser_valid_input

    test result: FAILED. 7 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.02s

    fix the code so it pass all tests. GIVE ME FINAL VERSION OF CODE AS A SINGLE FILE

  2. Assistant
    #!/usr/bin/env rust-script
    //! # Thepg: A Comprehensive Parser Generator in Rust
    //!
    //! **Thepg** is a powerful parser generator that processes Extended Backus–Naur Form (ENBF) grammars
    //! and produces robust, compile-ready Rust code for parsing based on the provided grammar.
    //!
    //! ## Features
    //! - Supports LL(1) and LL(k) parsing strategies
    //! - Generates lexing-capable parsers with support for identifiers and literals
    //! - Outputs well-structured Rust code in a single file
    //! - Constructs Abstract Syntax Trees (AST) during the parsing process
    //! - Comprehensive error handling with informative messages
    //! - User-friendly command-line interface using `clap`
    //!
    //! ## Usage
    //! To generate a parser, run the following command:
    //!
    //! ```bash
    //! cargo run --release -- <grammar.enbf> -o <output_file.rs> --grammar-type <LL1|LLk> --lookahead <k>
    //! ```
    //!
    //! - Replace `<grammar.enbf>` with your ENBF grammar file.
    //! - Replace `<output_file.rs>` with your desired output Rust file name.
    //! - Use `--grammar-type` to specify the parsing strategy (`LL1` or `LLk`).
    //! - Use `--lookahead` to define the number of tokens to look ahead (applicable for `LLk` parsing).
    //!
    //! ## 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" | "number"
    //! ```
    //!
    //! Generate the parser as follows:
    //!
    //! ```bash
    //! cargo run --release -- arithmetic.enbf -o arithmetic_parser.rs --grammar-type LL1
    //! ```
    //!
    //! The above command will create `arithmetic_parser.rs` containing the lexer, parser, and AST definitions
    //! based on the provided grammar.
    //!
    //! ## Testing
    //! Execute the embedded test cases using Cargo:
    //!
    //! ```bash
    //! cargo test
    //! ```
    //!
    //! ## License
    //! MIT License. See `LICENSE` for details.
    
    extern crate clap;
    extern crate regex;
    
    use clap::{Arg, ArgAction, Command};
    use regex::Regex;
    use std::collections::{HashMap, HashSet, VecDeque};
    use std::fs;
    
    /// Represents various parsing errors.
    #[derive(Debug)]
    enum ParseError {
        /// Unexpected token encountered during parsing.
        UnexpectedToken {
            expected: Vec<String>,
            found: String,
            position: usize,
        },
        /// Invalid grammar structure.
        InvalidGrammar(String),
        /// Lexer encountered an error.
        LexerError(String),
    }
    
    impl std::fmt::Display for ParseError {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            match self {
                ParseError::UnexpectedToken {
                    expected,
                    found,
                    position,
                } => write!(
                    f,
                    "Unexpected token at position {}: expected {:?}, found {}",
                    position, expected, found
                ),
                ParseError::InvalidGrammar(msg) => write!(f, "Invalid grammar: {}", msg),
                ParseError::LexerError(msg) => write!(f, "Lexer error: {}", msg),
            }
        }
    }
    
    impl std::error::Error for ParseError {}
    
    /// Represents a grammar rule with a head and multiple production bodies.
    #[derive(Debug, Clone)]
    struct Rule {
        head: String,
        bodies: Vec<Vec<String>>,
    }
    
    /// Represents the entire parsed grammar, including rules, terminals, non-terminals, and FIRST/FOLLOW sets.
    #[derive(Debug, Clone)]
    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 input.
        fn parse(enbf: &str) -> Result<Self, ParseError> {
            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(ParseError::InvalidGrammar(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.trim_matches('"').trim_matches('\'').to_string())
                            .collect()
                    })
                    .collect();
                rules.push(Rule { head, bodies });
            }
    
            // Identify terminals (symbols not defined as non-terminals and not ε)
            for rule in &rules {
                for body in &rule.bodies {
                    for symbol in body {
                        if symbol != "ε" && !non_terminals.contains(symbol) {
                            terminals.insert(symbol.clone());
                        }
                    }
                }
            }
    
            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 using a queue-based iterative approach.
        fn compute_first_sets(&mut self) -> Result<(), ParseError> {
            // 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 nt_first = self.first_sets.get_mut(&rule.head).unwrap();
    
                    for body in &rule.bodies {
                        let mut can_be_empty = true;
                        for symbol in body {
                            if self.terminals.contains(symbol) {
                                if nt_first.insert(symbol.clone()) {
                                    changed = true;
                                }
                                can_be_empty = false;
                                break;
                            } else if symbol == "ε" {
                                if nt_first.insert("ε".to_string()) {
                                    changed = true;
                                }
                                can_be_empty = true;
                                break;
                            } else {
                                let sym_first = self.first_sets.get(symbol).unwrap();
                                let prev_len = nt_first.len();
                                nt_first.extend(sym_first.iter().filter(|&s| s != "ε").cloned());
                                if nt_first.len() > prev_len {
                                    changed = true;
                                }
                                if !sym_first.contains("ε") {
                                    can_be_empty = false;
                                    break;
                                }
                            }
                        }
                        if can_be_empty {
                            if nt_first.insert("ε".to_string()) {
                                changed = true;
                            }
                        }
                    }
                }
            }
    
            Ok(())
        }
    
        /// Computes FOLLOW sets for all non-terminals using standard iterative method.
        fn compute_follow_sets(&mut self) -> Result<(), ParseError> {
            // 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(ParseError::InvalidGrammar(
                    "No rules found in the grammar.".to_string(),
                ));
            }
    
            let mut changed = true;
    
            while changed {
                changed = false;
    
                for rule in &self.rules {
                    let A = &rule.head;
                    let follow_A = self.follow_sets[A].clone();
    
                    for body in &rule.bodies {
                        let symbols = &body;
                        for i in 0..symbols.len() {
                            let B = &symbols[i];
                            if self.non_terminals.contains(B) {
                                // Compute FIRST(β)
                                let mut first_beta = HashSet::new();
                                let mut beta_derives_epsilon = true;
                                for beta_symbol in symbols.iter().skip(i + 1) {
                                    if self.non_terminals.contains(beta_symbol) {
                                        let first_beta_symbol = &self.first_sets[beta_symbol];
                                        first_beta.extend(
                                            first_beta_symbol.iter().filter(|&&ref s| s != "ε").cloned(),
                                        );
                                        if !first_beta_symbol.contains("ε") {
                                            beta_derives_epsilon = false;
                                            break;
                                        }
                                    } else if beta_symbol == "ε" {
                                        first_beta.insert("ε".to_string());
                                    } else {
                                        first_beta.insert(beta_symbol.clone());
                                        beta_derives_epsilon = false;
                                        break;
                                    }
                                }
                                // a) For each terminal a in FIRST(β), add a to FOLLOW(B)
                                let follow_B = self.follow_sets.get_mut(B).unwrap();
                                let size_before = follow_B.len();
                                follow_B.extend(first_beta.iter().filter(|&s| s != "ε").cloned());
                                if follow_B.len() > size_before {
                                    changed = true;
                                }
    
                                // b) If FIRST(β) contains ε or β is empty, add FOLLOW(A) to FOLLOW(B)
                                if beta_derives_epsilon || symbols.iter().skip(i + 1).next().is_none() {
                                    let follow_B = self.follow_sets.get_mut(B).unwrap();
                                    let size_before = follow_B.len();
                                    follow_B.extend(follow_A.clone());
                                    if follow_B.len() > size_before {
                                        changed = true;
                                    }
                                }
                            }
                        }
                    }
                }
            }
    
            Ok(())
        }
    
        /// Determines the FIRST set for a given production 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 symbol == "ε" {
                    first.insert("ε".to_string());
                    return Some(first);
                }
                if let Some(sym_first) = first_sets.get(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 production body can produce ε (epsilon).
        fn body_can_produce_epsilon(
            body: &Vec<String>,
            first_sets: &HashMap<String, HashSet<String>>,
        ) -> bool {
            body.iter().all(|symbol| {
                if let Some(sym_first) = first_sets.get(symbol) {
                    sym_first.contains("ε")
                } else {
                    false
                }
            })
        }
    
        /// Sanitizes token names to be Rust-compatible by replacing or removing invalid characters.
        fn sanitize_token(token: &str) -> String {
            token
                .trim_matches('"')
                .trim_matches('\'')
                .replace("+", "PLUS")
                .replace("-", "MINUS")
                .replace("*", "STAR")
                .replace("/", "SLASH")
                .replace("(", "LPAREN")
                .replace(")", "RPAREN")
                .replace("{", "LBRACE")
                .replace("}", "RBRACE")
                .replace("[", "LBRACKET")
                .replace("]", "RBRACKET")
                .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 by converting to lowercase and replacing invalid characters.
        fn sanitize_func(func: &str) -> String {
            func.to_lowercase()
                .replace("<", "")
                .replace(">", "")
                .replace("-", "_")
                .replace(" ", "_")
        }
    }
    
    /// Represents the different types of tokens.
    #[derive(Debug, PartialEq, Clone)]
    enum TokenEnum {
        // Fixed symbols
        PLUS,
        MINUS,
        STAR,
        SLASH,
        LPAREN,
        RPAREN,
        // Multi-character symbols (if any)
        EQ,
        NEQ,
        LEQ,
        GEQ,
        // Pattern-based tokens
        ID(String),
        NUMBER(i32),
        EOF,
    }
    
    /// The Lexer struct responsible for tokenizing the input string.
    struct Lexer {
        input: std::iter::Peekable<std::str::Chars<'static>>,
        buffer: Vec<TokenEnum>, // Buffer for lookahead
        regex_map: Vec<(Regex, fn(&str) -> TokenEnum)>, // Regex patterns and corresponding token constructors
        current_position: usize, // Current character position in input
    }
    
    impl Lexer {
        /// Creates a new Lexer instance.
        fn new(input: &str) -> Self {
            let input_owned = input.to_string();
            let input_static: &'static str = Box::leak(input_owned.into_boxed_str());
    
            // Define token constructors as functions
            fn construct_eq(_s: &str) -> TokenEnum {
                TokenEnum::EQ
            }
            fn construct_neq(_s: &str) -> TokenEnum {
                TokenEnum::NEQ
            }
            fn construct_leq(_s: &str) -> TokenEnum {
                TokenEnum::LEQ
            }
            fn construct_geq(_s: &str) -> TokenEnum {
                TokenEnum::GEQ
            }
            fn construct_plus(_s: &str) -> TokenEnum {
                TokenEnum::PLUS
            }
            fn construct_minus(_s: &str) -> TokenEnum {
                TokenEnum::MINUS
            }
            fn construct_star(_s: &str) -> TokenEnum {
                TokenEnum::STAR
            }
            fn construct_slash(_s: &str) -> TokenEnum {
                TokenEnum::SLASH
            }
            fn construct_lparen(_s: &str) -> TokenEnum {
                TokenEnum::LPAREN
            }
            fn construct_rparen(_s: &str) -> TokenEnum {
                TokenEnum::RPAREN
            }
            fn construct_id(s: &str) -> TokenEnum {
                TokenEnum::ID(s.to_string())
            }
            fn construct_number(s: &str) -> TokenEnum {
                TokenEnum::NUMBER(s.parse().unwrap())
            }
    
            let mut regex_map: Vec<(Regex, fn(&str) -> TokenEnum)> = Vec::new();
    
            // Order matters: longer patterns first
            regex_map.push((Regex::new(r"^\==").unwrap(), construct_eq));
            regex_map.push((Regex::new(r"^\!=").unwrap(), construct_neq));
            regex_map.push((Regex::new(r"^<=").unwrap(), construct_leq));
            regex_map.push((Regex::new(r"^>=").unwrap(), construct_geq));
            regex_map.push((Regex::new(r"^\+").unwrap(), construct_plus));
            regex_map.push((Regex::new(r"^\-").unwrap(), construct_minus));
            regex_map.push((Regex::new(r"^\*").unwrap(), construct_star));
            regex_map.push((Regex::new(r"^\/").unwrap(), construct_slash));
            regex_map.push((Regex::new(r"^\(").unwrap(), construct_lparen));
            regex_map.push((Regex::new(r"^\)").unwrap(), construct_rparen));
            // Identifiers
            regex_map.push((Regex::new(r"^[a-zA-Z_][a-zA-Z0-9_]*").unwrap(), construct_id));
            // Numbers
            regex_map.push((Regex::new(r"^\d+").unwrap(), construct_number));
    
            Lexer {
                input: input_static.chars().peekable(),
                buffer: Vec::new(),
                regex_map,
                current_position: 0,
            }
        }
    
        /// Retrieves the next token from the buffer or lexer.
        fn next_token(&mut self) -> TokenEnum {
            if !self.buffer.is_empty() {
                self.buffer.remove(0)
            } else {
                self.lex_next_token()
            }
        }
    
        /// Peeks `k` tokens ahead without consuming them.
        fn peek(&mut self, k: usize) -> Vec<TokenEnum> {
            while self.buffer.len() < k {
                let token = self.lex_next_token();
                if token == TokenEnum::EOF {
                    self.buffer.push(TokenEnum::EOF);
                    break;
                }
                self.buffer.push(token);
            }
            self.buffer.iter().cloned().take(k).collect()
        }
    
        /// Lexes the next token using regex patterns.
        fn lex_next_token(&mut self) -> TokenEnum {
            // Skip leading whitespace
            while let Some(&ch) = self.input.peek() {
                if ch.is_whitespace() {
                    self.input.next();
                    self.current_position += 1;
                } else {
                    break;
                }
            }
            // Now try to match tokens
            let remaining: String = self.input.clone().collect();
            for (regex, constructor) in &self.regex_map {
                if let Some(mat) = regex.find(&remaining) {
                    let matched_str = mat.as_str();
                    let token = constructor(matched_str);
                    // Advance the input by the length of the matched string
                    for _ in 0..matched_str.len() {
                        self.input.next();
                        self.current_position += 1;
                    }
                    return token;
                }
            }
    
            // If no regex matched, handle unknown characters
            if let Some(c) = self.input.next() {
                self.current_position += 1;
                eprintln!("Warning: Unrecognized character '{}'", c);
                self.lex_next_token() // Skip the unrecognized character and try again
            } else {
                TokenEnum::EOF
            }
        }
    }
    
    /// Represents an AST Node.
    #[derive(Debug, PartialEq, Clone)]
    enum ASTNode {
        NonTerminal(String, Vec<ASTNode>),
        Terminal(TokenEnum),
        Identifier(String),
        Number(i32),
    }
    
    /// The Parser struct responsible for parsing the input and constructing the AST.
    struct ParserStruct<'a> {
        lexer: Lexer,
        current_token: TokenEnum,
        lookahead: Vec<TokenEnum>,
        grammar: &'a Grammar,
        k: usize,    // Lookahead size
        position: usize, // Current parsing position
    }
    
    impl<'a> ParserStruct<'a> {
        /// Creates a new Parser instance with the given input string, grammar, and lookahead size.
        fn new(input: &'a str, grammar: &'a Grammar, k: usize) -> Self {
            let mut lexer = Lexer::new(input);
            let first_token = lexer.next_token();
            ParserStruct {
                lexer,
                current_token: first_token,
                lookahead: Vec::new(),
                grammar,
                k,
                position: 0,
            }
        }
    
        /// Initiates the parsing process starting from the start symbol.
        fn parse(&mut self) -> Result<ASTNode, ParseError> {
            if let Some(start_rule) = self.grammar.rules.first() {
                let ast = self.parse_non_terminal(&start_rule.head)?;
                if self.current_token == TokenEnum::EOF {
                    Ok(ast)
                } else {
                    Err(ParseError::UnexpectedToken {
                        expected: vec!["EOF".to_string()],
                        found: format!("{:?}", self.current_token),
                        position: self.position,
                    })
                }
            } else {
                Err(ParseError::InvalidGrammar(
                    "No rules defined in the grammar.".to_string(),
                ))
            }
        }
    
        /// Parses a non-terminal symbol considering LL(k) lookahead.
        fn parse_non_terminal(&mut self, non_terminal: &str) -> Result<ASTNode, ParseError> {
            if let Some(rule) = self.grammar.rules.iter().find(|r| r.head == non_terminal) {
                for body in &rule.bodies {
                    let first_set =
                        Grammar::first_of_body(body, &self.grammar.first_sets).unwrap();
                    let tokens = self.lexer.peek(self.k);
                    let intersects =
                        self.should_use_production(&first_set, &tokens, non_terminal)?;
    
                    if intersects || first_set.contains("ε") {
                        let node = self.parse_production(body)?;
                        return Ok(ASTNode::NonTerminal(non_terminal.to_string(), vec![node]));
                    }
                }
                Err(ParseError::UnexpectedToken {
                    expected: vec!["valid production".to_string()],
                    found: format!("{:?}", self.current_token),
                    position: self.position,
                })
            } else {
                Err(ParseError::InvalidGrammar(format!(
                    "Non-terminal '{}' not found in grammar",
                    non_terminal
                )))
            }
        }
    
        /// Determines whether to use a production based on the FIRST set and lookahead tokens.
        fn should_use_production(
            &self,
            first_set: &HashSet<String>,
            tokens: &Vec<TokenEnum>,
            non_terminal: &str,
        ) -> Result<bool, ParseError> {
            for t in first_set {
                match t.as_str() {
                    "ε" => {
                        let follow_set = &self.grammar.follow_sets[non_terminal];
                        for tok in tokens {
                            if follow_set.contains("$") && *tok == TokenEnum::EOF {
                                return Ok(true);
                            }
                            match tok {
                                TokenEnum::ID(_) => {
                                    if follow_set.contains("id") {
                                        return Ok(true);
                                    }
                                }
                                TokenEnum::NUMBER(_) => {
                                    if follow_set.contains("number") {
                                        return Ok(true);
                                    }
                                }
                                TokenEnum::PLUS => {
                                    if follow_set.contains("+") {
                                        return Ok(true);
                                    }
                                }
                                TokenEnum::MINUS => {
                                    if follow_set.contains("-") {
                                        return Ok(true);
                                    }
                                }
                                TokenEnum::STAR => {
                                    if follow_set.contains("*") {
                                        return Ok(true);
                                    }
                                }
                                TokenEnum::SLASH => {
                                    if follow_set.contains("/") {
                                        return Ok(true);
                                    }
                                }
                                TokenEnum::LPAREN => {
                                    if follow_set.contains("(") {
                                        return Ok(true);
                                    }
                                }
                                TokenEnum::RPAREN => {
                                    if follow_set.contains(")") {
                                        return Ok(true);
                                    }
                                }
                                TokenEnum::EOF => {
                                    if follow_set.contains("$") {
                                        return Ok(true);
                                    }
                                }
                                _ => {}
                            }
                        }
                    }
                    "id" => {
                        if tokens.iter().any(|tok| matches!(tok, TokenEnum::ID(_))) {
                            return Ok(true);
                        }
                    }
                    "number" => {
                        if tokens.iter().any(|tok| matches!(tok, TokenEnum::NUMBER(_))) {
                            return Ok(true);
                        }
                    }
                    "+" => {
                        if tokens.iter().any(|tok| matches!(tok, TokenEnum::PLUS)) {
                            return Ok(true);
                        }
                    }
                    "-" => {
                        if tokens.iter().any(|tok| matches!(tok, TokenEnum::MINUS)) {
                            return Ok(true);
                        }
                    }
                    "*" => {
                        if tokens.iter().any(|tok| matches!(tok, TokenEnum::STAR)) {
                            return Ok(true);
                        }
                    }
                    "/" => {
                        if tokens.iter().any(|tok| matches!(tok, TokenEnum::SLASH)) {
                            return Ok(true);
                        }
                    }
                    "(" => {
                        if tokens.iter().any(|tok| matches!(tok, TokenEnum::LPAREN)) {
                            return Ok(true);
                        }
                    }
                    ")" => {
                        if tokens.iter().any(|tok| matches!(tok, TokenEnum::RPAREN)) {
                            return Ok(true);
                        }
                    }
                    _ => {}
                }
            }
            Ok(false)
        }
    
        /// Parses a production body and constructs the corresponding AST node.
        fn parse_production(&mut self, body: &Vec<String>) -> Result<ASTNode, ParseError> {
            let mut children = Vec::new();
            for symbol in body {
                if self.grammar.non_terminals.contains(symbol) {
                    let child = self.parse_non_terminal(symbol)?;
                    children.push(child);
                } else {
                    match symbol.as_str() {
                        "+" => {
                            self.eat(TokenEnum::PLUS)?;
                            children.push(ASTNode::Terminal(TokenEnum::PLUS));
                        }
                        "-" => {
                            self.eat(TokenEnum::MINUS)?;
                            children.push(ASTNode::Terminal(TokenEnum::MINUS));
                        }
                        "*" => {
                            self.eat(TokenEnum::STAR)?;
                            children.push(ASTNode::Terminal(TokenEnum::STAR));
                        }
                        "/" => {
                            self.eat(TokenEnum::SLASH)?;
                            children.push(ASTNode::Terminal(TokenEnum::SLASH));
                        }
                        "(" => {
                            self.eat(TokenEnum::LPAREN)?;
                            children.push(ASTNode::Terminal(TokenEnum::LPAREN));
                        }
                        ")" => {
                            self.eat(TokenEnum::RPAREN)?;
                            children.push(ASTNode::Terminal(TokenEnum::RPAREN));
                        }
                        "id" => {
                            if let TokenEnum::ID(value) = self.current_token.clone() {
                                self.eat(TokenEnum::ID(value.clone()))?;
                                children.push(ASTNode::Identifier(value));
                            } else {
                                return Err(ParseError::UnexpectedToken {
                                    expected: vec!["id".to_string()],
                                    found: format!("{:?}", self.current_token),
                                    position: self.position,
                                });
                            }
                        }
                        "number" => {
                            if let TokenEnum::NUMBER(value) = self.current_token.clone() {
                                self.eat(TokenEnum::NUMBER(value))?;
                                children.push(ASTNode::Number(value));
                            } else {
                                return Err(ParseError::UnexpectedToken {
                                    expected: vec!["number".to_string()],
                                    found: format!("{:?}", self.current_token),
                                    position: self.position,
                                });
                            }
                        }
                        "ε" => {
                            // Epsilon production, do nothing
                        }
                        _ => {
                            return Err(ParseError::InvalidGrammar(format!(
                                "Unknown terminal symbol '{}'",
                                symbol
                            )));
                        }
                    }
                }
            }
            Ok(ASTNode::NonTerminal(body.join(" "), children))
        }
    
        /// Consumes the current token if it matches the expected token.
        fn eat(&mut self, token: TokenEnum) -> Result<(), ParseError> {
            // For tokens like ID and NUMBER, we don't compare the inner value
            match (&self.current_token, &token) {
                (TokenEnum::ID(_), TokenEnum::ID(_)) => {
                    self.current_token = self.lexer.next_token();
                    self.position += 1;
                    Ok(())
                }
                (TokenEnum::NUMBER(_), TokenEnum::NUMBER(_)) => {
                    self.current_token = self.lexer.next_token();
                    self.position += 1;
                    Ok(())
                }
                _ if self.current_token == token => {
                    self.current_token = self.lexer.next_token();
                    self.position += 1;
                    Ok(())
                }
                _ => Err(ParseError::UnexpectedToken {
                    expected: vec![format!("{:?}", token)],
                    found: format!("{:?}", self.current_token),
                    position: self.position,
                }),
            }
        }
    }
    
    /// Generates Rust code for the parser based on the parsed grammar.
    struct CodeGenerator {
        grammar: Grammar,
        grammar_type: String,
        lookahead: usize,
    }
    
    impl CodeGenerator {
        /// Creates a new CodeGenerator instance.
        fn new(grammar: &Grammar, grammar_type: &str, lookahead: usize) -> Self {
            CodeGenerator {
                grammar: grammar.clone(),
                grammar_type: grammar_type.to_string(),
                lookahead,
            }
        }
    
        /// Generates the complete Rust code for the parser.
        fn generate_code(&self, output_file: &str) -> Result<(), String> {
            let code =
                "// Generated parser code goes here (code generation logic not fully implemented)"
                    .to_string();
    
            // Write the generated code to the output file
            fs::write(output_file, code).map_err(|e| format!("Failed to write output file: {}", e))
        }
    }
    
    /// Entry point for Thepg
    fn main() -> Result<(), Box<dyn std::error::Error>> {
        // Define the CLI using clap
        let matches = Command::new("Thepg")
            .version("1.0")
            .author("Your Name <youremail@example.com>")
            .about("A Rust-Based Parser Generator for ENBF Grammars")
            .arg(
                Arg::new("input")
                    .short('i')
                    .long("input")
                    .value_name("FILE")
                    .help("Input ENBF grammar file")
                    .required(true),
            )
            .arg(
                Arg::new("output")
                    .short('o')
                    .long("output")
                    .value_name("FILE")
                    .help("Output Rust file for the generated parser")
                    .required(true),
            )
            .arg(
                Arg::new("grammar_type")
                    .short('g')
                    .long("grammar-type")
                    .value_name("TYPE")
                    .help("Grammar type: LL1 or LLk")
                    .required(true),
            )
            .arg(
                Arg::new("lookahead")
                    .short('k')
                    .long("lookahead")
                    .value_name("K")
                    .help("Number of tokens to look ahead (applicable for LLk)")
                    .default_value("1"),
            )
            .arg(
                Arg::new("verbose")
                    .short('v')
                    .long("verbose")
                    .help("Enable verbose output")
                    .action(ArgAction::SetTrue),
            )
            .get_matches();
    
        // Extract arguments
        let input_file = matches
            .get_one::<String>("input")
            .expect("Input file is required");
        let output_file = matches
            .get_one::<String>("output")
            .expect("Output file is required");
        let grammar_type = matches
            .get_one::<String>("grammar_type")
            .expect("Grammar type is required");
        let lookahead: usize = matches
            .get_one::<String>("lookahead")
            .unwrap()
            .parse()
            .unwrap_or(1);
        let verbose = matches.get_flag("verbose");
    
        if verbose {
            println!("Input File: {}", input_file);
            println!("Output File: {}", output_file);
            println!("Grammar Type: {}", grammar_type);
            println!("Lookahead Size: {}", lookahead);
        }
    
        // Read the ENBF grammar file
        let enbf = fs::read_to_string(input_file)
            .map_err(|e| ParseError::InvalidGrammar(format!("Failed to read input file: {}", e)))?;
    
        // Parse the grammar
        let mut grammar = Grammar::parse(&enbf)?;
        if verbose {
            println!("Grammar parsed successfully.");
        }
    
        // Check if the grammar is LL(1) if specified
        if grammar_type.to_uppercase() == "LL1" {
            if !grammar.compute_first_sets().is_ok() || !grammar.compute_follow_sets().is_ok() {
                return Err(Box::new(ParseError::InvalidGrammar(
                    "Failed to compute FIRST/FOLLOW sets.".to_string(),
                )));
            }
            if let Err(_) = grammar.compute_follow_sets() {
                return Err(Box::new(ParseError::InvalidGrammar(
                    "Failed to compute FOLLOW sets.".to_string(),
                )));
            }
            // You can implement the is_ll1 method here if needed
            if verbose {
                println!("Grammar processing completed.");
            }
        }
    
        // Generate Rust code for the parser
        let code_generator = CodeGenerator::new(&grammar, grammar_type, lookahead);
        code_generator.generate_code(output_file)?;
    
        if verbose {
            println!("Parser generated successfully at '{}'.", output_file);
        }
    
        Ok(())
    }
    
    #[cfg(test)]
    mod tests {
        use super::*;
    
        #[test]
        fn test_sanitize_token() {
            assert_eq!(Grammar::sanitize_token("+"), "PLUS");
            assert_eq!(Grammar::sanitize_token("-"), "MINUS");
            assert_eq!(Grammar::sanitize_token("*"), "STAR");
            assert_eq!(Grammar::sanitize_token("/"), "SLASH");
            assert_eq!(Grammar::sanitize_token("("), "LPAREN");
            assert_eq!(Grammar::sanitize_token(")"), "RPAREN");
            assert_eq!(Grammar::sanitize_token("id"), "ID");
            assert_eq!(Grammar::sanitize_token("number"), "NUMBER");
        }
    
        #[test]
        fn test_sanitize_func() {
            assert_eq!(Grammar::sanitize_func("Expr"), "expr");
            assert_eq!(Grammar::sanitize_func("ExprPrime"), "exprprime");
            assert_eq!(Grammar::sanitize_func("Term"), "term");
            assert_eq!(Grammar::sanitize_func("TermPrime"), "termprime");
            assert_eq!(Grammar::sanitize_func("Factor"), "factor");
        }
    
        #[test]
        fn test_first_of_body() {
            let mut first_sets = HashMap::new();
            first_sets.insert(
                "Term".to_string(),
                vec!["id".to_string(), "number".to_string()]
                    .into_iter()
                    .collect(),
            );
            first_sets.insert(
                "ExprPrime".to_string(),
                vec!["+".to_string(), "-".to_string(), "ε".to_string()]
                    .into_iter()
                    .collect(),
            );
    
            let body = vec!["Term".to_string(), "ExprPrime".to_string()];
            let first = Grammar::first_of_body(&body, &first_sets).unwrap();
            assert!(first.contains("id"));
            assert!(first.contains("number"));
        }
    
        #[test]
        fn test_body_can_produce_epsilon() {
            let mut first_sets = HashMap::new();
            first_sets.insert("A".to_string(), vec!["ε".to_string()].into_iter().collect());
            first_sets.insert("B".to_string(), vec!["ε".to_string()].into_iter().collect());
    
            let body = vec!["A".to_string(), "B".to_string()];
            assert!(Grammar::body_can_produce_epsilon(&body, &first_sets));
        }
    
        #[test]
        fn test_parse_grammar() {
            let enbf = r#"
                Expr ::= Term ExprPrime
                ExprPrime ::= "+" Term ExprPrime | "-" Term ExprPrime | ε
                Term ::= Factor TermPrime
                TermPrime ::= "*" Factor TermPrime | "/" Factor TermPrime | ε
                Factor ::= "(" Expr ")" | "id" | "number"
            "#;
            let grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
            assert_eq!(grammar.rules.len(), 5);
            assert!(grammar.terminals.contains("+"));
            assert!(grammar.terminals.contains("-"));
            assert!(grammar.non_terminals.contains("Expr"));
            assert!(grammar.first_sets.contains_key("Expr"));
            assert!(grammar.follow_sets.contains_key("Expr"));
        }
    
        #[test]
        fn test_parser_valid_input() {
            let enbf = r#"
                Expr ::= Term ExprPrime
                ExprPrime ::= "+" Term ExprPrime | "-" Term ExprPrime | ε
                Term ::= Factor TermPrime
                TermPrime ::= "*" Factor TermPrime | "/" Factor TermPrime | ε
                Factor ::= "(" Expr ")" | "id" | "number"
            "#;
            let mut grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
            grammar
                .compute_first_sets()
                .expect("Failed to compute FIRST sets");
            grammar
                .compute_follow_sets()
                .expect("Failed to compute FOLLOW sets");
    
            let input = "id + id * id";
            let mut parser = ParserStruct::new(input, &grammar, 1);
            let ast = parser.parse().expect("Parser failed on valid input");
            assert!(matches!(ast, ASTNode::NonTerminal(_, _)));
        }
    
        #[test]
        fn test_parser_invalid_input() {
            let enbf = r#"
                Expr ::= Term ExprPrime
                ExprPrime ::= "+" Term ExprPrime | "-" Term ExprPrime | ε
                Term ::= Factor TermPrime
                TermPrime ::= "*" Factor TermPrime | "/" Factor TermPrime | ε
                Factor ::= "(" Expr ")" | "id" | "number"
            "#;
            let mut grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
            grammar
                .compute_first_sets()
                .expect("Failed to compute FIRST sets");
            grammar
                .compute_follow_sets()
                .expect("Failed to compute FOLLOW sets");
            let input = "id + * id";
            let mut parser = ParserStruct::new(input, &grammar, 2);
            let result = parser.parse();
            assert!(matches!(result, Err(ParseError::UnexpectedToken { .. })));
        }
    
        #[test]
        fn test_empty_input() {
            let enbf = r#"
                Expr ::= Term
                Term ::= "id" | "number"
            "#;
            let mut grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
            grammar
                .compute_first_sets()
                .expect("Failed to compute FIRST sets");
            grammar
                .compute_follow_sets()
                .expect("Failed to compute FOLLOW sets");
            let input = "";
            let mut parser = ParserStruct::new(input, &grammar, 1);
            let result = parser.parse();
            assert!(matches!(result, Err(ParseError::UnexpectedToken { .. })));
        }
    }