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}; 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), }

    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), } } }

    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(); // let mut symbols_in_bodies = HashSet::new(); // unused?

        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| {
                            if (s.starts_with('"') && s.ends_with('"')) || (s.starts_with('\'') && s.ends_with('\'')) {
                                s.trim_matches('"').trim_matches('\'').to_string()
                            } else {
                                s.to_string()
                            }
                        })
                        .collect()
                })
                .collect();
            rules.push(Rule { head, bodies });
        }
    
        // Identify terminals and check for undefined non-terminals
        for rule in &rules {
            for body in &rule.bodies {
                for symbol in body {
                    if symbol == "ε" {
                        continue;
                    } else if non_terminals.contains(symbol) {
                        // It's a non-terminal, do nothing
                    } else {
                        // It's a terminal
                        terminals.insert(symbol.clone());
                    }
                }
            }
        }
    
        // Now check that all symbols are either in terminals or non_terminals (or epsilon)
        for rule in &rules {
            for body in &rule.bodies {
                for symbol in body {
                    if symbol == "ε" {
                        continue;
                    } else if terminals.contains(symbol) || non_terminals.contains(symbol) {
                        // All good
                    } else {
                        return Err(ParseError::InvalidGrammar(format!("Symbol '{}' not found in grammar", symbol)));
                    }
                }
            }
        }
    
        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 first_of_body = Grammar::first_of_body(
                        body,
                        &self.first_sets,
                        &self.terminals,
                        &self.non_terminals,
                    )?;
    
                    let nt_first = self.first_sets.get_mut(nt).unwrap();
                    let size_before = nt_first.len();
                    nt_first.extend(first_of_body.clone());
                    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_symbol = &symbols[i];
                        if self.non_terminals.contains(b_symbol) {
                            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_symbol).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(())
    }
    
    /// Computes the FIRST set of a body (list of symbols) using the existing FIRST sets.
    fn first_of_body(
        body: &Vec<String>,
        first_sets: &HashMap<String, HashSet<String>>,
        terminals: &HashSet<String>,
        non_terminals: &HashSet<String>,
    ) -> Result<HashSet<String>, ParseError> {
        let mut first = HashSet::new();
        let mut can_derive_epsilon = true; // Initially assume that body can produce ε
    
        for symbol in body {
            if symbol == "ε" {
                first.insert("ε".to_string());
                continue; // Continue to next symbol
            }
    
            if terminals.contains(symbol) {
                first.insert(symbol.clone());
                can_derive_epsilon = false;
                break; // Terminals cannot derive ε
            } else if non_terminals.contains(symbol) {
                let sym_first = &first_sets[symbol];
                first.extend(sym_first.iter().filter(|&s| s != "ε").cloned());
                if sym_first.contains("ε") {
                    // The symbol can derive ε, continue to next symbol
                    // Do not break, because we need to consider the next symbol
                } else {
                    can_derive_epsilon = false; // The symbol cannot derive ε, so body cannot
                    break;
                }
            } else {
                return Err(ParseError::InvalidGrammar(format!(
                    "Symbol '{}' not found in grammar",
                    symbol
                )));
            }
        }
    
        if can_derive_epsilon {
            first.insert("ε".to_string());
        }
    
        Ok(first)
    }
    
    /// Checks if a body (list of symbols) can derive ε.
    fn body_can_produce_epsilon(
        body: &Vec<String>,
        first_sets: &HashMap<String, HashSet<String>>,
        terminals: &HashSet<String>,
        non_terminals: &HashSet<String>,
    ) -> bool {
        for symbol in body {
            if symbol == "ε" {
                return true;
            } else if non_terminals.contains(symbol) {
                if !first_sets[symbol].contains("ε") {
                    return false;
                }
            } else if terminals.contains(symbol) {
                return false;
            } else {
                // Symbol not found; assume it cannot derive ε
                return false;
            }
        }
        return true;
    }
    

    }

    use std::fmt;

    /// Sanitizes token names to be Rust-compatible by replacing or removing invalid characters. fn sanitize_token(token: &str) -> String { let token = token.trim_matches('"').trim_matches('''); match token { "==" => "EQEQ".to_string(), "!=" => "NEQ".to_string(), "<=" => "LEQ".to_string(), ">=" => "GEQ".to_string(), _ => token .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("<", "LT") .replace(">", "GT") .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 EQEQ, NEQ, LEQ, GEQ, // Keywords or single-character tokens Terminal(String), // Pattern-based tokens ID(String), NUMBER(i32), EOF, }

    impl fmt::Display for TokenEnum { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { match self { TokenEnum::PLUS => write!(f, "+"), TokenEnum::MINUS => write!(f, "-"), TokenEnum::STAR => write!(f, "*"), TokenEnum::SLASH => write!(f, "/"), TokenEnum::LPAREN => write!(f, "("), TokenEnum::RPAREN => write!(f, ")"), TokenEnum::EQEQ => write!(f, "=="), TokenEnum::NEQ => write!(f, "!="), TokenEnum::LEQ => write!(f, "<="), TokenEnum::GEQ => write!(f, ">="), TokenEnum::Terminal(s) => write!(f, "{}", s), TokenEnum::ID(s) => write!(f, "{}", s), TokenEnum::NUMBER(n) => write!(f, "{}", n), TokenEnum::EOF => write!(f, "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, terminals: &HashSet) -> Self { let input_owned = input.to_string(); let input_static: &'static str = Box::leak(input_owned.into_boxed_str());

        let mut regex_map: Vec<(Regex, fn(&str) -> TokenEnum)> = Vec::new();
    
        // Define token constructors as functions
        fn construct_eqeq(_s: &str) -> TokenEnum {
            TokenEnum::EQEQ
        }
        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())
        }
        fn construct_terminal(s: &str) -> TokenEnum {
            TokenEnum::Terminal(s.to_string())
        }
    
        // Order matters: longer patterns first
        regex_map.push((Regex::new(r"^\==").unwrap(), construct_eqeq));
        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));
    
        // Add terminals from the grammar
        for terminal in terminals {
            let pattern = format!("^{}", regex::escape(terminal));
            let regex = Regex::new(&pattern).unwrap();
            regex_map.push((regex, construct_terminal));
        }
    
        // 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();
            self.buffer.push(token.clone());
            if token == TokenEnum::EOF {
                break;
            }
        }
        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, &grammar.terminals); 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) {
            let mut expected_symbols = HashSet::new();
    
            for body in &rule.bodies {
                let first_set = Grammar::first_of_body(
                    body,
                    &self.grammar.first_sets,
                    &self.grammar.terminals,
                    &self.grammar.non_terminals,
                )?;
                let tokens = self.lexer.peek(self.k);
                let intersects =
                    self.should_use_production(&first_set, &tokens, non_terminal)?;
    
                if intersects {
                    match self.parse_production(body) {
                        Ok(nodes) => {
                            return Ok(ASTNode::NonTerminal(non_terminal.to_string(), nodes));
                        }
                        Err(e) => {
                            return Err(e);
                        }
                    }
                } else {
                    expected_symbols.extend(first_set.iter().cloned());
                }
            }
            Err(ParseError::UnexpectedToken {
                expected: expected_symbols.into_iter().collect(),
                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, token) {
            ("id", TokenEnum::ID(_)) => true,
            ("number", TokenEnum::NUMBER(_)) => true,
            ("+", TokenEnum::PLUS) => true,
            ("-", TokenEnum::MINUS) => true,
            ("*", TokenEnum::STAR) => true,
            ("/", TokenEnum::SLASH) => true,
            ("(", TokenEnum::LPAREN) => true,
            (")", TokenEnum::RPAREN) => true,
            ("==", TokenEnum::EQEQ) => true,
            ("!=", TokenEnum::NEQ) => true,
            ("<=", TokenEnum::LEQ) => true,
            (">=", TokenEnum::GEQ) => true,
            ("$", TokenEnum::EOF) => true,
            (s, TokenEnum::ID(ref id_str)) if s == id_str => true,
            (s, TokenEnum::Terminal(ref term_str)) if s == term_str => true,
            _ => false,
        }
    }
    
    /// Parses a production body and constructs the corresponding AST nodes.
    fn parse_production(&mut self, body: &Vec<String>) -> Result<Vec<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 if symbol == "ε" {
                // Epsilon production, do nothing
            } else if self.grammar.terminals.contains(symbol) {
                let token = self.eat_symbol(symbol)?;
                match token {
                    TokenEnum::ID(ref value) => children.push(ASTNode::Identifier(value.clone())),
                    TokenEnum::NUMBER(value) => children.push(ASTNode::Number(value)),
                    _ => children.push(ASTNode::Terminal(token)),
                }
            } else {
                return Err(ParseError::InvalidGrammar(format!(
                    "Unknown terminal symbol '{}'",
                    symbol
                )));
            }
        }
        Ok(children)
    }
    
    /// Consumes a token corresponding to a terminal symbol.
    fn eat_symbol(&mut self, symbol: &str) -> Result<TokenEnum, ParseError> {
        if self.symbol_matches_token(symbol, &self.current_token) {
            let token = self.current_token.clone();
            self.current_token = self.lexer.next_token();
            self.position += 1;
            Ok(token)
        } else {
            Err(ParseError::UnexpectedToken {
                expected: vec![symbol.to_string()],
                found: format!("{}", self.current_token),
                position: self.position,
            })
        }
    }
    

    }

    /// 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.");
    }
    
    // Additional processing can be done here...
    
    Ok(())
    

    }

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

    #[test]
    fn test_sanitize_token() {
        assert_eq!(sanitize_token("+"), "PLUS");
        assert_eq!(sanitize_token("-"), "MINUS");
        assert_eq!(sanitize_token("*"), "STAR");
        assert_eq!(sanitize_token("/"), "SLASH");
        assert_eq!(sanitize_token("("), "LPAREN");
        assert_eq!(sanitize_token(")"), "RPAREN");
        assert_eq!(sanitize_token("id"), "ID");
        assert_eq!(sanitize_token("number"), "NUMBER");
        assert_eq!(sanitize_token("="), "EQ");
        assert_eq!(sanitize_token("!="), "NEQ");
        assert_eq!(sanitize_token("<="), "LEQ");
        assert_eq!(sanitize_token(">="), "GEQ");
    }
    
    #[test]
    fn test_sanitize_func() {
        assert_eq!(sanitize_func("Expr"), "expr");
        assert_eq!(sanitize_func("ExprPrime"), "exprprime");
        assert_eq!(sanitize_func("Term"), "term");
        assert_eq!(sanitize_func("TermPrime"), "termprime");
        assert_eq!(sanitize_func("Factor"), "factor");
        assert_eq!(sanitize_func("Function-Name"), "function_name");
        assert_eq!(sanitize_func("My Function"), "my_function");
    }
    
    #[test]
    fn test_first_of_body() {
        let mut first_sets = HashMap::new();
        first_sets.insert(
            "Term".to_string(),
            vec!["ε".to_string(), "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 terminals: HashSet<String> = vec!["id".to_string(), "number".to_string()]
            .into_iter()
            .collect();
        let non_terminals: HashSet<String> =
            vec!["Term".to_string(), "ExprPrime".to_string()]
                .into_iter()
                .collect();
    
        let body = vec!["Term".to_string(), "ExprPrime".to_string()];
        let first = Grammar::first_of_body(&body, &first_sets, &terminals, &non_terminals).unwrap();
        assert!(first.contains("id"));
        assert!(first.contains("number"));
        assert!(first.contains("+"));
        assert!(first.contains("-"));
        assert!(first.contains("ε"));
    }
    
    #[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 terminals: HashSet<String> = HashSet::new();
        let non_terminals: HashSet<String> = vec!["A".to_string(), "B".to_string()]
            .into_iter()
            .collect();
    
        let body = vec!["A".to_string(), "B".to_string()];
        assert!(Grammar::body_can_produce_epsilon(
            &body,
            &first_sets,
            &terminals,
            &non_terminals
        ));
    
        let body_non_eps = vec!["A".to_string(), "C".to_string()];
        assert!(!Grammar::body_can_produce_epsilon(
            &body_non_eps,
            &first_sets,
            &terminals,
            &non_terminals
        ));
    }
    
    #[test]
    fn test_parser_long_input_unique() {
        let enbf = r#"
            S ::= a b c
            A ::= a
            B ::= b
            C ::= c
        "#;
        let grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
    
        let input = "a b c";
        let mut parser = ParserStruct::new(input, &grammar, 1);
        let ast = parser.parse().expect("Parser failed on input 'a b c'");
        assert!(matches!(ast, ASTNode::NonTerminal(_, _)));
    
        let invalid_input = "a c b";
        let mut parser_invalid = ParserStruct::new(invalid_input, &grammar, 1);
        let result = parser_invalid.parse();
        assert!(matches!(result, Err(ParseError::UnexpectedToken { .. })));
    }
    
    #[test]
    fn test_lexer_with_unrecognized_characters() {
        let input = "a b c $ %";
        let mut lexer = Lexer::new(input, &HashSet::new());
        let tokens = vec![
            lexer.next_token(),
            lexer.next_token(),
            lexer.next_token(),
            lexer.next_token(),
            lexer.next_token(),
            lexer.next_token(), // EOF
        ];
        assert_eq!(tokens[0], TokenEnum::ID("a".to_string()));
        assert_eq!(tokens[1], TokenEnum::ID("b".to_string()));
        assert_eq!(tokens[2], TokenEnum::ID("c".to_string()));
        // $ and % are unrecognized, so they should be skipped with warnings
        assert_eq!(tokens[3], TokenEnum::EOF);
    }
    
    #[test]
    fn test_parser_with_left_recursion() {
        let enbf = r#"
            Expr ::= Expr + Term | Term
            Term ::= number
        "#;
        let grammar_result = Grammar::parse(enbf);
        assert!(grammar_result.is_ok());
        let grammar = grammar_result.unwrap();
    
        // Since the grammar is left-recursive, our LL parser may not handle it correctly
        // Let's test parsing "number + number"
        let input = "number + number";
        let mut parser = ParserStruct::new(input, &grammar, 1);
        let result = parser.parse();
        assert!(result.is_err());
        assert!(matches!(result, Err(ParseError::UnexpectedToken { .. })));
    }
    
    #[test]
    fn test_first_and_follow_sets_with_epsilon() {
        let enbf = r#"
            S ::= A b
            A ::= a A | ε
        "#;
        let grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
        let first_S = &grammar.first_sets["S"];
        assert!(first_S.contains("a"));
        assert!(first_S.contains("b")); // Because A can produce ε, and "b" follows
    
        let follow_A = &grammar.follow_sets["A"];
        assert!(follow_A.contains("b"));
    }
    
    #[test]
    fn test_parser_with_epsilon_productions() {
        let enbf = r#"
            S ::= A b
            A ::= a | ε
        "#;
        let grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
    
        let input1 = "a b";
        let mut parser1 = ParserStruct::new(input1, &grammar, 1);
        let ast1 = parser1.parse().expect("Parser failed on input 'a b'");
        assert!(matches!(ast1, ASTNode::NonTerminal(_, _)));
    
        let input2 = "b";
        let mut parser2 = ParserStruct::new(input2, &grammar, 1);
        let ast2 = parser2.parse().expect("Parser failed on input 'b'");
        assert!(matches!(ast2, ASTNode::NonTerminal(_, _)));
    }
    
    #[test]
    fn test_parser_with_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, 1);
        let result = parser.parse();
        assert!(result.is_err());
        if let Err(ParseError::UnexpectedToken { found, .. }) = result {
            assert_eq!(found, "*");
        }
    }
    
    #[test]
    fn test_grammar_with_invalid_rule() {
        let enbf = r#"
            S ::= A B
            A ::= a
            B ::= b C
            # C is not defined
        "#;
        let grammar_result = Grammar::parse(enbf);
        assert!(grammar_result.is_err());
        if let Err(ParseError::InvalidGrammar(msg)) = grammar_result {
            assert!(msg.contains("Symbol 'C' not found in grammar"));
        }
    }
    
    #[test]
    fn test_parser_with_llk_lookahead() {
        let enbf = r#"
            S ::= a b | a c
        "#;
        let grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
    
        let input = "a b";
        let mut parser = ParserStruct::new(input, &grammar, 2); // Lookahead of 2
        let ast = parser.parse().expect("Parser failed on input 'a b'");
        assert!(matches!(ast, ASTNode::NonTerminal(_, _)));
    
        let input2 = "a c";
        let mut parser2 = ParserStruct::new(input2, &grammar, 2); // Lookahead of 2
        let ast2 = parser2.parse().expect("Parser failed on input 'a c'");
        assert!(matches!(ast2, ASTNode::NonTerminal(_, _)));
    
        // With lookahead of 1, the parser cannot distinguish between the two productions
        let mut parser3 = ParserStruct::new("a b", &grammar, 1);
        let result3 = parser3.parse();
        assert!(result3.is_err());
    }
    
    #[test]
    fn test_compute_first_sets_complex_grammar() {
        let enbf = r#"
            S ::= A B
            A ::= a | ε
            B ::= b
        "#;
        let grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
    
        let first_S = &grammar.first_sets["S"];
        assert!(first_S.contains("a"));
        assert!(first_S.contains("b"));
    
        let first_A = &grammar.first_sets["A"];
        assert!(first_A.contains("a"));
        assert!(first_A.contains("ε"));
    
        let first_B = &grammar.first_sets["B"];
        assert!(first_B.contains("b"));
    }
    
    #[test]
    fn test_compute_follow_sets_complex_grammar() {
        let enbf = r#"
            S ::= A C
            A ::= a | ε
            C ::= c
        "#;
        let grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
    
        let follow_S = &grammar.follow_sets["S"];
        assert!(follow_S.contains("$"));
    
        let follow_A = &grammar.follow_sets["A"];
        assert!(follow_A.contains("c"));
    
        let follow_C = &grammar.follow_sets["C"];
        assert!(follow_C.contains("$"));
    }
    
    #[test]
    fn test_parse_error_reporting() {
        let enbf = r#"
            S ::= a b
        "#;
        let grammar = Grammar::parse(enbf).expect("Failed to parse grammar");
    
        let input = "a c";
        let mut parser = ParserStruct::new(input, &grammar, 1);
        let result = parser.parse();
        assert!(result.is_err());
        if let Err(ParseError::UnexpectedToken { expected, found, position }) = result {
            assert_eq!(expected, vec!["b".to_string()]);
            assert_eq!(found, "c");
            assert_eq!(position, 1);
        }
    }
    

    }

  2. Assistant

    The code you've provided is a comprehensive attempt at building a parser generator in Rust that takes an Extended Backus–Naur Form (ENBF) grammar and generates Rust code for parsing based on that grammar. You've structured the code to parse the grammar, compute the FIRST and FOLLOW sets, and have set up the initial groundwork for the lexer and parser.

    However, there are a few issues and missing pieces in your code that need to be addressed to make it fully functional. Below, I'll outline the key points:

    1. Inconsistency Between CLI Definition and Usage Examples:

      • Issue: In your main function, you're using clap to define command-line arguments where the input file is expected via the --input (or -i) flag. However, in your usage examples within the documentation comments, the input file is provided as a positional argument without any flag.

      • Solution: Update your clap command definition to accept the input file as a positional argument to match your usage examples, or modify your usage instructions to include the --input flag. Here's how you can define a positional argument in clap:

        use clap::{Arg, Command};
        
        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")
                    .help("Input ENBF grammar file")
                    .required(true)
                    .index(1),
            )
            // Other arguments...
            .get_matches();
        
    2. Incomplete Code Generation Functionality:

      • Issue: After parsing the grammar and computing the FIRST and FOLLOW sets, the code doesn't proceed to generate the Rust code for the parser and lexer, nor does it write anything to the specified output file.

      • Solution: You need to implement the code generation logic that takes the Grammar struct and produces Rust code for the lexer, parser, and AST definitions. This involves traversing the grammar rules and generating Rust functions or structs that correspond to the non-terminals and terminals in your grammar.

      • Example Outline:

        • Lexer Generation: Create token definitions (enum Token) based on the terminals, and generate code for the lexer that can tokenize input strings.
        • Parser Generation: For each non-terminal, generate a parser function that can parse that non-terminal according to the grammar rules.
        • AST Structures: Define Rust structs or enums to represent the AST nodes corresponding to the grammar's non-terminals and terminals.
        • Write to Output File: Use std::fs::write to write the generated Rust code to the specified output file.
    3. Error Handling and User Feedback:

      • Issue: The current parsing functions may not provide detailed enough error messages when parsing fails.
      • Solution: Enhance the error handling in your parsing functions to include more context, such as the line number in the input file where the error occurred.
    4. Testing and Validation:

      • Issue: While you have provided unit tests, it's crucial to test the generated parser on actual inputs to ensure it works as expected.
      • Solution: After implementing code generation, write integration tests that compile the generated parser code, run it on test inputs, and validate the outputs.
    5. Modernizing Rust Code:

      • Issue: The use of extern crate is unnecessary in the 2018 edition of Rust and onwards.
      • Solution: Remove extern crate clap; and extern crate regex; as they are no longer needed.
    6. Shebang Line and Script Usage:

      • Issue: The shebang line #!/usr/bin/env rust-script suggests that this code is intended to be run as a script using rust-script. However, the code is more suited to being a binary crate rather than a script.
      • Solution: Decide whether you want this code to be a standalone script or a binary. If it's a binary, you can remove the shebang line and set it up as a standard Rust project using cargo. If you intend to use rust-script, you'll need to adjust the code to fit that context.
    7. Grammar and Parser Limitations:

      • Issue: The parser may not handle left-recursive grammars correctly, as LL parsers cannot handle left recursion.
      • Solution: If you need to support left-recursive grammars, you'll need to implement left recursion elimination or consider using a different parsing strategy (e.g., LR parsing).
    8. Code Style and Conventions:

      • Issue: The code could benefit from following Rust conventions more closely, such as naming and modularization.
      • Solution: Use rustfmt to format your code and consider breaking up large functions into smaller ones for readability.
    9. Example Implementation:

      To help you get started with the code generation part, here's a simplified example of how you might generate Rust code for the lexer and parser:

      // After parsing the grammar and computing FIRST and FOLLOW sets
      
      // Generate tokens
      let mut token_defs = String::new();
      for terminal in &grammar.terminals {
          let token_name = sanitize_token(terminal);
          token_defs.push_str(&format!("    {},\n", token_name));
      }
      
      // Generate lexer code
      let lexer_code = format!(
          "
      #[derive(Debug, Clone, PartialEq)]
      pub enum Token {{
      {}
          EOF,
      }}
      
      pub struct Lexer {{
          // Lexer state
      }}
      
      impl Lexer {{
          pub fn new(input: &str) -> Self {{
              // Initialize lexer
          }}
      
          pub fn next_token(&mut self) -> Token {{
              // Lexing logic
          }}
      }}
      ",
          token_defs
      );
      
      // Similarly, generate parser code based on grammar rules
      
      // Write generated code to output file
      let generated_code = format!(
          "{}\n{}\n", // Combine lexer and parser code
          lexer_code,
          "// Parser code here"
      );
      fs::write(output_file, generated_code)
          .map_err(|e| ParseError::InvalidGrammar(format!("Failed to write to output file: {}", e)))?;
      

      Note that this is a highly simplified example. You'll need to expand this to handle all the details of the grammar, including generating appropriate parser functions and AST node definitions.

    10. Documentation and Licensing:

      • Issue: Make sure to update the documentation and license information to reflect your actual code and authorship.
      • Solution: Replace placeholders like "Your Name <youremail@example.com>" with your actual name and email. Ensure that the license complies with your intentions.

    In conclusion, to make your parser generator fully functional, focus on implementing the code generation logic that turns your parsed grammar into actual Rust code for a lexer and parser. Ensure that the generated code is syntactically correct and handles all the grammar rules appropriately. Don't forget to test the generated parser with various inputs to validate its correctness.

    If you need further assistance with specific parts of the implementation or encounter any errors, feel free to ask!