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<String>,
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<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();
// 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<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, terminals: &HashSet<String>) -> 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<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, &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<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 _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);
}
}
}