#!/usr/bin/env rust-script //! # Thepg: A Comprehensive Parser Generator in Rust //! //!…
- 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-typeto specify the parsing strategy (LL1orLLk). //! - Use--lookaheadto define the number of tokens to look ahead (applicable forLLkparsing). //! //! ## Example //! Given the followingarithmetic.enbfgrammar: //! //!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 createarithmetic_parser.rscontaining 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. SeeLICENSEfor 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
grammaras 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 compilethepg(bin "thepg" test) due to previous errorfix and give me the full final version of code
- Assistant
Certainly! The error you've encountered is due to attempting to borrow the
grammarvariable as mutable without declaring it as such. Specifically, in yourmainfunction, you are trying to call mutable methods on an immutablegrammarvariable. To fix this, you need to declaregrammaras mutable using themutkeyword.Below is the full corrected version of your
thepgRust 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
-
Mutable Declaration of
grammar:- Issue: The error
E0596occurred because you tried to borrowgrammaras mutable (grammar.compute_first_sets()andgrammar.compute_follow_sets()) without declaring it as mutable. - Fix: Changed the declaration from
let grammar = Grammar::parse(&enbf)?;tolet mut grammar = Grammar::parse(&enbf)?;in themainfunction.
- Issue: The error
-
Additional Improvements:
- Comments: Kept all existing comments and documentation intact for clarity.
- Redundancy Notice: Added a note in the
mainfunction indicating thatcompute_first_sets()andcompute_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
CodeGeneratorstruct 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::newfunction usesBox::leakto convert aStringto 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
thepgparser generator should compile successfully. You can now proceed with further development and enhancements as needed. -