use std::borrow::Borrow;
use std::cell::{Ref, RefCell, RefMut};
use std::collections::{HashMap, HashSet};
use std::collections::hash_map::RandomState;
use std::hash::Hash;
use std::iter::{FromIterator, Map};
use std::slice::Iter;
use crate::grammar::context_free_grammar::ContextFreeGrammar;
use crate::grammar::context_free_grammar_production::ContextFreeGrammarProduction;
pub type SymbolsMap<T> = HashMap<T, HashSet<T>>;
pub struct FirstFollowSymbols<T> {
first_symbols: SymbolsMap<T>,
follow_symbols: SymbolsMap<T>,
}
impl<T> FirstFollowSymbols<T> {
fn converge<M, F>(model: &M, callback: F) -> ()
where
F: Fn(&M) -> bool,
{
while callback(model) {}
}
}
impl<T: Eq + Hash> FirstFollowSymbols<T> {
pub fn new(first_symbols: SymbolsMap<T>, follow_symbols: SymbolsMap<T>) -> Self {
FirstFollowSymbols {
first_symbols,
follow_symbols,
}
}
pub fn get_first_symbols<'a>(&'a self, symbol: &'a T) -> Option<&'a HashSet<T>> {
FirstFollowSymbols::get_symbols_from_hash_map(&self.first_symbols, symbol)
}
pub fn get_follow_symbols<'a>(&'a self, symbol: &'a T) -> Option<&'a HashSet<T>> {
FirstFollowSymbols::get_symbols_from_hash_map(&self.follow_symbols, symbol)
}
fn get_symbols_from_hash_map<'a>(
hash_map: &'a SymbolsMap<T>,
key: &T,
) -> Option<&'a HashSet<T>> {
hash_map.get(key)
}
fn ref_map_to_symbols_map(symbols_ref_map: HashMap<T, RefCell<HashSet<T>>>) -> SymbolsMap<T> {
HashMap::from_iter(
symbols_ref_map.into_iter().map(
|(symbol, symbols_ref)|
(symbol, symbols_ref.take())
)
)
}
}
impl<T: Clone + Eq + Hash> FirstFollowSymbols<T> {
pub fn from(grammar: &ContextFreeGrammar<T>) -> Self {
let first_symbols = Self::inner_get_first_symbols(grammar);
let follow_symbols = Self::inner_get_follow_symbols(grammar, &first_symbols);
Self::new(first_symbols, follow_symbols)
}
fn inner_get_first_symbols(grammar: &ContextFreeGrammar<T>) -> SymbolsMap<T> {
let non_terminal_symbols = grammar.get_non_terminal_symbols();
let terminal_symbols = grammar.get_terminal_symbols();
let first_symbols_map: HashMap<T, RefCell<HashSet<T>>> = Self::inner_get_first_symbols_initial_map(
&non_terminal_symbols,
&terminal_symbols,
);
Self::converge(&first_symbols_map, |model: &HashMap<T, RefCell<HashSet<T>>>| -> bool {
let mut updated_at_iter: bool = false;
let productions = non_terminal_symbols
.iter()
.map(|symbol| (symbol, grammar.get_productions(symbol).unwrap()));
for (symbol, tuple_productions) in productions {
let mut tuple_symbol_first_symbols: RefMut<HashSet<T>> =
first_symbols_map.get(symbol).unwrap().borrow_mut();
for production in tuple_productions {
updated_at_iter |= Self::inner_get_first_symbols_process_production(
grammar,
model,
&mut tuple_symbol_first_symbols,
&production,
);
}
}
updated_at_iter
});
Self::ref_map_to_symbols_map(first_symbols_map)
}
fn inner_get_first_symbols_initial_map(non_terminal_symbols: &Vec<T>, terminal_symbols: &Vec<T>)
-> HashMap<T, RefCell<HashSet<T>>> {
let non_terminal_symbols_iterator
= Self::inner_get_first_symbols_non_terminal_map(&non_terminal_symbols);
let terminal_symbols_iterator
= Self::inner_get_first_symbols_terminal_map(&terminal_symbols);
HashMap::from_iter(
non_terminal_symbols_iterator.chain(terminal_symbols_iterator),
)
}
fn inner_get_first_symbols_non_terminal_map(symbols: &Vec<T>)
-> Map<Iter<'_, T>, fn(&T) -> (T, RefCell<HashSet<T, RandomState>>)> {
symbols
.iter()
.map(|symbol| (symbol.clone(), RefCell::new(HashSet::new())))
}
fn inner_get_first_symbols_process_production(
grammar: &ContextFreeGrammar<T>,
first_symbols_map: &HashMap<T, RefCell<HashSet<T>>>,
tuple_symbol_first_symbols: &mut RefMut<HashSet<T>>,
production: &ContextFreeGrammarProduction<T>,
) -> bool {
let mut first_symbols_updated: bool = false;
let mut output_iterator_option: Option<Iter<T>> = Some(production.output.iter());
while output_iterator_option.is_some() {
let production_symbol_option = output_iterator_option.as_mut().unwrap().next();
match production_symbol_option {
Some(production_symbol) => {
first_symbols_updated |= Self::inner_get_first_symbols_process_production_symbol(
grammar,
first_symbols_map,
tuple_symbol_first_symbols,
&mut output_iterator_option,
&production.input,
production_symbol,
);
},
None => {
first_symbols_updated |= tuple_symbol_first_symbols.insert(
grammar.get_epsilon_symbol().clone()
);
break;
}
}
}
first_symbols_updated
}
fn inner_get_first_symbols_process_production_symbol(
grammar: &ContextFreeGrammar<T>,
first_symbols_map: &HashMap<T, RefCell<HashSet<T>>>,
tuple_symbol_first_symbols: &mut RefMut<HashSet<T>>,
output_iterator_option: &mut Option<Iter<T>>,
production_input: &T,
production_symbol: &T,
) -> bool {
let mut first_symbols_updated = false;
if production_symbol.eq(production_input) {
if !tuple_symbol_first_symbols.contains(grammar.get_epsilon_symbol()) {
*output_iterator_option = None;
}
} else {
if grammar.is_non_terminal(production_symbol) {
first_symbols_updated |= Self::inner_get_first_symbols_process_production_non_terminal_symbol(
grammar,
first_symbols_map,
tuple_symbol_first_symbols,
output_iterator_option,
production_symbol,
);
} else {
first_symbols_updated |= tuple_symbol_first_symbols.insert(production_symbol.clone());
*output_iterator_option = None
}
}
first_symbols_updated
}
fn inner_get_first_symbols_process_production_non_terminal_symbol(
grammar: &ContextFreeGrammar<T>,
first_symbols_map: &HashMap<T, RefCell<HashSet<T>>>,
tuple_symbol_first_symbols: &mut RefMut<HashSet<T>>,
output_iterator_option: &mut Option<Iter<T>>,
production_symbol: &T,
) -> bool {
let mut first_symbols_updated = false;
let symbol_first_symbols: Ref<HashSet<T>> =
first_symbols_map.get(production_symbol).unwrap().borrow();
if symbol_first_symbols.contains(grammar.get_epsilon_symbol()) {
first_symbols_updated |= Self::insert_many(
tuple_symbol_first_symbols,
&mut symbol_first_symbols
.iter()
.filter(|symbol| grammar.get_epsilon_symbol().ne(*symbol)),
);
} else {
first_symbols_updated |= Self::insert_many(
tuple_symbol_first_symbols,
&mut symbol_first_symbols.iter(),
);
*output_iterator_option = None
}
first_symbols_updated
}
fn inner_get_first_symbols_terminal_map(symbols: &Vec<T>)
-> Map<Iter<'_, T>, fn(&T) -> (T, RefCell<HashSet<T, RandomState>>)> {
symbols
.iter()
.map(
|symbol| {
let mut hash_set = HashSet::new();
hash_set.insert(symbol.clone());
(symbol.clone(), RefCell::new(hash_set))
},
)
}
fn inner_get_follow_symbols(
grammar: &ContextFreeGrammar<T>,
first_symbols_map: &SymbolsMap<T>,
) -> SymbolsMap<T> {
let non_terminal_symbols = grammar.get_non_terminal_symbols();
let follow_symbols_map: HashMap<T, RefCell<HashSet<T>>> = HashMap::from_iter(
non_terminal_symbols.iter()
.map(|symbol| (symbol.clone(), RefCell::new(HashSet::new()))),
);
Self::converge(&follow_symbols_map, |model| {
let mut updated_at_iter: bool = false;
let productions = non_terminal_symbols
.iter()
.map(|symbol| (symbol, grammar.get_productions(symbol).unwrap()));
for (_, tuple_productions) in productions {
for production in tuple_productions {
updated_at_iter |= Self::get_follow_symbols_process_production(
grammar,
first_symbols_map,
model,
production,
);
}
}
updated_at_iter
});
Self::ref_map_to_symbols_map(follow_symbols_map)
}
fn get_follow_symbols_process_production_last_epsilon_chain(
grammar: &ContextFreeGrammar<T>,
first_symbols_map: &SymbolsMap<T>,
follow_symbols_map: &HashMap<T, RefCell<HashSet<T>>>,
production: &ContextFreeGrammarProduction<T>,
) -> bool {
let mut follow_symbols_updated: bool = false;
let mut production_output_index: usize = production.output.len() - 1;
loop {
let output_symbol: &T = production.output.get(production_output_index).unwrap();
if output_symbol.ne(&production.input) && grammar.is_non_terminal(output_symbol) {
let input_follow_symbols = follow_symbols_map.get(&production.input).unwrap().borrow();
let mut symbol_follow_symbols_ref = follow_symbols_map.get(output_symbol).unwrap().borrow_mut();
input_follow_symbols.iter().for_each(|symbol| {
follow_symbols_updated |= symbol_follow_symbols_ref.insert(symbol.clone());
});
}
let output_symbol_first_symbols: &HashSet<T> = first_symbols_map
.get(output_symbol).unwrap().borrow();
let output_symbol_first_symbols_contains_epsilon: bool =
output_symbol_first_symbols.contains(grammar.get_epsilon_symbol());
if production_output_index == 0 || !output_symbol_first_symbols_contains_epsilon {
break;
} else {
production_output_index -= 1;
}
}
follow_symbols_updated
}
fn get_follow_symbols_process_production(
grammar: &ContextFreeGrammar<T>,
first_symbols_map: &SymbolsMap<T>,
follow_symbols_map: &HashMap<T, RefCell<HashSet<T>>>,
production: &ContextFreeGrammarProduction<T>,
) -> bool {
let mut follow_symbols_updated: bool = Self::get_follow_symbols_process_production_last_epsilon_chain(
grammar,
first_symbols_map,
follow_symbols_map,
&production,
);
let last_production_output_index: usize = production.output.len() - 1;
if last_production_output_index > 0 {
let mut production_output_index: usize = last_production_output_index - 1;
let mut first_indexes: Vec<usize> = vec![];
loop {
follow_symbols_updated |= Self::get_follow_symbols_process_production_symbol(
grammar,
first_symbols_map,
follow_symbols_map,
production,
production_output_index,
&mut first_indexes,
);
if production_output_index == 0 {
break
} else {
production_output_index -= 1;
}
}
}
follow_symbols_updated
}
fn get_follow_symbols_process_production_symbol(
grammar: &ContextFreeGrammar<T>,
first_symbols_map: &SymbolsMap<T>,
follow_symbols_map: &HashMap<T, RefCell<HashSet<T>>>,
production: &ContextFreeGrammarProduction<T>,
production_output_index: usize,
first_indexes: &mut Vec<usize>,
) -> bool {
let follow_symbols_updated: bool;
let current_symbol: &T = production.output.get(production_output_index).unwrap();
if grammar.is_non_terminal(current_symbol) {
follow_symbols_updated = Self::get_follow_symbols_process_production_non_terminal_symbol(
grammar,
first_symbols_map,
follow_symbols_map,
production,
production_output_index,
first_indexes,
current_symbol,
);
} else {
follow_symbols_updated = false;
first_indexes.clear();
}
follow_symbols_updated
}
fn get_follow_symbols_process_production_non_terminal_symbol(
grammar: &ContextFreeGrammar<T>,
first_symbols_map: &SymbolsMap<T>,
follow_symbols_map: &HashMap<T, RefCell<HashSet<T>>>,
production: &ContextFreeGrammarProduction<T>,
production_output_index: usize,
first_indexes: &mut Vec<usize>,
current_symbol: &T,
) -> bool {
let mut follow_symbols_updated: bool = false;
let next_symbol_index: usize = production_output_index + 1;
let next_symbol = production.output.get(next_symbol_index).unwrap();
if current_symbol.ne(next_symbol) {
let next_symbol_first_symbols = first_symbols_map.get(next_symbol).unwrap();
if !next_symbol_first_symbols.contains(grammar.get_epsilon_symbol()) {
first_indexes.clear();
}
first_indexes.push(next_symbol_index);
let mut current_symbol_follow_symbols = follow_symbols_map
.get(current_symbol)
.unwrap()
.borrow_mut();
follow_symbols_updated |= Self::update_follow_symbols_lambda_chain(
grammar,
first_symbols_map,
production,
first_indexes,
&mut current_symbol_follow_symbols,
);
}
follow_symbols_updated
}
fn insert_many(hash_set_ref: &mut RefMut<HashSet<T>>, iterator: &mut dyn Iterator<Item=&T>) -> bool {
let mut item_inserted: bool = false;
iterator.for_each(|symbol_first_symbol| {
item_inserted |= hash_set_ref.insert(symbol_first_symbol.clone());
});
item_inserted
}
fn update_follow_symbols_lambda_chain(
grammar: &ContextFreeGrammar<T>,
first_symbols_map: &SymbolsMap<T>,
production: &ContextFreeGrammarProduction<T>,
first_indexes: &Vec<usize>,
current_symbol_follow_symbols: &mut HashSet<T>,
) -> bool {
let mut follow_symbols_updated: bool = false;
first_indexes.iter().for_each(|index| {
let symbol: &T = production.output.get(*index).unwrap();
first_symbols_map.get(symbol)
.unwrap()
.iter()
.filter(|symbol| (grammar.get_epsilon_symbol()).ne(*symbol))
.for_each(|symbol| {
follow_symbols_updated |= current_symbol_follow_symbols.insert(symbol.clone());
});
});
follow_symbols_updated
}
}