Skip to content
TheChatArchiveThe Chat Archive
o1-mini-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}; 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 the standard 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 = &rule.head;
    
                for body in &rule.bodies {
                    let mut first_of_body = HashSet::new();
                    let mut can_be_empty = true;
    
                    for symbol in body {
                        if self.terminals.contains(symbol) {
                            first_of_body.insert(symbol.clone());
                            can_be_empty = false;
                            break;
                        } else if symbol == "ε" {
                            first_of_body.insert("ε".to_string());
                            can_be_empty = true;
                            break;
                        } else {
                            let sym_first = self.first_sets.get(symbol).unwrap();
                            first_of_body.extend(sym_first.iter().filter(|&s| s != "ε").cloned());
                            if !sym_first.contains("ε") {
                                can_be_empty = false;
                                break;
                            }
                        }
                    }
                    if can_be_empty {
                        first_of_body.insert("ε".to_string());
                    }
    
                    let nt_first = self.first_sets.get_mut(nt).unwrap();
                    let size_before = nt_first.len();
                    nt_first.extend(first_of_body);
                    if nt_first.len() > size_before {
                        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 nt = &rule.head;
                let follow_nt = self.follow_sets[nt].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) {
                            let mut first_beta = HashSet::new();
                            let mut beta_derives_epsilon = true;
                            for beta_symbol in symbols.iter().skip(i + 1) {
                                if self.terminals.contains(beta_symbol) {
                                    first_beta.insert(beta_symbol.clone());
                                    beta_derives_epsilon = false;
                                    break;
                                } else if beta_symbol == "ε" {
                                    first_beta.insert("ε".to_string());
                                } else {
                                    let first_beta_symbol = &self.first_sets[beta_symbol];
                                    first_beta.extend(
                                        first_beta_symbol.iter().filter(|&s| s != "ε").cloned(),
                                    );
                                    if !first_beta_symbol.contains("ε") {
                                        beta_derives_epsilon = false;
                                        break;
                                    }
                                }
                            }
    
                            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 beta_derives_epsilon || symbols.iter().skip(i + 1).next().is_none() {
                                follow_B.extend(follow_nt.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, // 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), 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, 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, 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 {
                    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 {
            if t == "ε" {
                let follow_set = &self.grammar.follow_sets[non_terminal];
                for tok in tokens {
                    if self.token_matches(tok, follow_set) {
                        return Ok(true);
                    }
                }
            } else {
                for tok in tokens {
                    if self.symbol_matches_token(t, tok) {
                        return Ok(true);
                    }
                }
            }
        }
        Ok(false)
    }
    
    /// Matches a token against a set of symbols (terminals).
    fn token_matches(&self, token: &TokenEnum, symbols: &HashSet<String>) -> bool {
        for symbol in symbols {
            if self.symbol_matches_token(symbol, token) {
                return true;
            }
        }
        false
    }
    
    /// Checks if a symbol matches a token.
    fn symbol_matches_token(&self, symbol: &str, token: &TokenEnum) -> bool {
        match symbol {
            "id" => matches!(token, TokenEnum::ID(_)),
            "number" => matches!(token, TokenEnum::NUMBER(_)),
            "+" => matches!(token, TokenEnum::PLUS),
            "-" => matches!(token, TokenEnum::MINUS),
            "*" => matches!(token, TokenEnum::STAR),
            "/" => matches!(token, TokenEnum::SLASH),
            "(" => matches!(token, TokenEnum::LPAREN),
            ")" => matches!(token, TokenEnum::RPAREN),
            "$" => matches!(token, TokenEnum::EOF),
            _ => 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> { // 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 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 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 grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
        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 grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
        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 grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
        let input = "";
        let mut parser = ParserStruct::new(input, &grammar, 1);
        let result = parser.parse();
        assert!(matches!(result, Err(ParseError::UnexpectedToken { .. })));
    }
    

    }

    error[E0596]: cannot borrow grammar as mutable, as it is not declared as mutable --> src/main.rs:880:9 | 880 | let grammar = Grammar::parse(&enbf)?; | ^^^^^^^ not mutable ... 887 | if !grammar.compute_first_sets().is_ok() || !grammar.compute_follow_sets().is_ok() { | ------- cannot borrow as mutable ------- cannot borrow as mutable | help: consider changing this to be mutable | 880 | let mut grammar = Grammar::parse(&enbf)?; | +++

    For more information about this error, try rustc --explain E0596. error: could not compile thepg (bin "thepg" test) due to previous error

    fix and give me the full final version of code

  2. Assistant

    Certainly! The error you've encountered is due to attempting to borrow the grammar variable as mutable without declaring it as such. Specifically, in your main function, you are trying to call mutable methods on an immutable grammar variable. To fix this, you need to declare grammar as mutable using the mut keyword.

    Below is the full corrected version of your thepg Rust script with the necessary modifications:

    #!/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};
    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 the standard 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 = &rule.head;
    
                    for body in &rule.bodies {
                        let mut first_of_body = HashSet::new();
                        let mut can_be_empty = true;
    
                        for symbol in body {
                            if self.terminals.contains(symbol) {
                                first_of_body.insert(symbol.clone());
                                can_be_empty = false;
                                break;
                            } else if symbol == "ε" {
                                first_of_body.insert("ε".to_string());
                                can_be_empty = true;
                                break;
                            } else {
                                let sym_first = self.first_sets.get(symbol).unwrap();
                                first_of_body.extend(sym_first.iter().filter(|&s| s != "ε").cloned());
                                if !sym_first.contains("ε") {
                                    can_be_empty = false;
                                    break;
                                }
                            }
                        }
                        if can_be_empty {
                            first_of_body.insert("ε".to_string());
                        }
    
                        let nt_first = self.first_sets.get_mut(nt).unwrap();
                        let size_before = nt_first.len();
                        nt_first.extend(first_of_body);
                        if nt_first.len() > size_before {
                            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 nt = &rule.head;
                    let follow_nt = self.follow_sets[nt].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) {
                                let mut first_beta = HashSet::new();
                                let mut beta_derives_epsilon = true;
                                for beta_symbol in symbols.iter().skip(i + 1) {
                                    if self.terminals.contains(beta_symbol) {
                                        first_beta.insert(beta_symbol.clone());
                                        beta_derives_epsilon = false;
                                        break;
                                    } else if beta_symbol == "ε" {
                                        first_beta.insert("ε".to_string());
                                    } else {
                                        let first_beta_symbol = &self.first_sets[beta_symbol];
                                        first_beta.extend(
                                            first_beta_symbol.iter().filter(|&s| s != "ε").cloned(),
                                        );
                                        if !first_beta_symbol.contains("ε") {
                                            beta_derives_epsilon = false;
                                            break;
                                        }
                                    }
                                }
    
                                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 beta_derives_epsilon || symbols.iter().skip(i + 1).next().is_none() {
                                    follow_B.extend(follow_nt.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,
        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,
                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 {
                        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 {
                if t == "ε" {
                    let follow_set = &self.grammar.follow_sets[non_terminal];
                    for tok in tokens {
                        if self.token_matches(tok, follow_set) {
                            return Ok(true);
                        }
                    }
                } else {
                    for tok in tokens {
                        if self.symbol_matches_token(t, tok) {
                            return Ok(true);
                        }
                    }
                }
            }
            Ok(false)
        }
    
        /// Matches a token against a set of symbols (terminals).
        fn token_matches(&self, token: &TokenEnum, symbols: &HashSet<String>) -> bool {
            for symbol in symbols {
                if self.symbol_matches_token(symbol, token) {
                    return true;
                }
            }
            false
        }
    
        /// Checks if a symbol matches a token.
        fn symbol_matches_token(&self, symbol: &str, token: &TokenEnum) -> bool {
            match symbol {
                "id" => matches!(token, TokenEnum::ID(_)),
                "number" => matches!(token, TokenEnum::NUMBER(_)),
                "+" => matches!(token, TokenEnum::PLUS),
                "-" => matches!(token, TokenEnum::MINUS),
                "*" => matches!(token, TokenEnum::STAR),
                "/" => matches!(token, TokenEnum::SLASH),
                "(" => matches!(token, TokenEnum::LPAREN),
                ")" => matches!(token, TokenEnum::RPAREN),
                "$" => matches!(token, TokenEnum::EOF),
                _ => 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" {
            // Recompute FIRST and FOLLOW sets if needed
            // Note: These sets are already computed during parsing, so this might be redundant
            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 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 grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
            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 grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
            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 grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
            let input = "";
            let mut parser = ParserStruct::new(input, &grammar, 1);
            let result = parser.parse();
            assert!(matches!(result, Err(ParseError::UnexpectedToken { .. })));
        }
    }
    

    Summary of Changes

    1. Mutable Declaration of grammar:

      • Issue: The error E0596 occurred because you tried to borrow grammar as mutable (grammar.compute_first_sets() and grammar.compute_follow_sets()) without declaring it as mutable.
      • Fix: Changed the declaration from let grammar = Grammar::parse(&enbf)?; to let mut grammar = Grammar::parse(&enbf)?; in the main function.
    2. Additional Improvements:

      • Comments: Kept all existing comments and documentation intact for clarity.
      • Redundancy Notice: Added a note in the main function indicating that compute_first_sets() and compute_follow_sets() are already called during grammar parsing, so calling them again might be redundant. You can consider removing these redundant calls if they're not necessary for your application's logic.

    Final Notes

    • Code Generation Placeholder: The CodeGenerator struct currently contains a placeholder for the generated code. You will need to implement the actual code generation logic based on your specific requirements.

    • Memory Leak Warning: The Lexer::new function uses Box::leak to convert a String to a &'static str. This results in a memory leak as the memory is never freed. While this might be acceptable for short-lived applications or scripts, it's recommended to manage memory more carefully in production code.

    • Error Handling: Ensure that all possible errors are adequately handled, especially in areas where the code currently has placeholder comments or incomplete implementations.

    • Testing: The provided tests cover various aspects of the grammar parsing and lexer functionality. Make sure to expand these tests as you develop further features to maintain robustness.

    With these changes, your thepg parser generator should compile successfully. You can now proceed with further development and enhancements as needed.