#![allow(missing_docs)]
use std::collections::{BTreeMap, VecDeque};
use std::rc::Rc;
use crate::history::RootHistoryNode;
use crate::prelude::*;
use crate::symbol::SymbolBitSet;
type Dot = u32;
type RuleId = u32;
type SetId = u32;
#[derive(Debug, Eq, PartialEq, Ord, PartialOrd)]
pub struct Lr0Items {
pub map: BTreeMap<RuleId, Lr0Item>,
}
#[derive(Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
pub struct Lr0Item {
pub rhs: Vec<Symbol>,
pub dot: Dot,
}
pub struct Lr0ClosureBuilder<'a, G> {
grammar: &'a mut G,
queue: VecDeque<Lr0Item>,
terminal_set: SymbolBitSet,
}
pub struct Lr0FsmBuilder<'a, G> {
closure: Lr0ClosureBuilder<'a, G>,
sets_queue: VecDeque<Rc<Lr0Items>>,
cached_sets: BTreeMap<Rc<Lr0Items>, u32>,
}
#[derive(Debug, Eq, PartialEq)]
pub struct Lr0Node {
pub items: Rc<Lr0Items>,
pub link: BTreeMap<Symbol, SetId>,
}
impl Lr0Items {
fn new() -> Self {
Lr0Items {
map: BTreeMap::new(),
}
}
}
impl<'a, G> Lr0ClosureBuilder<'a, G>
where
G: RuleContainer + Default,
for<'b> &'b G: RuleContainerRef<'b, Target = G>,
{
pub fn new(grammar: &'a mut G) -> Self {
Lr0ClosureBuilder {
queue: VecDeque::new(),
terminal_set: SymbolBitSet::terminal_set(&grammar),
grammar,
}
}
pub fn closure(&mut self, items: &mut Lr0Items) {
self.queue.clear();
self.queue.extend(items.map.values().cloned());
while let Some(item) = self.queue.pop_front() {
if let Some(nonterminal_postdot) = self.nonterminal_postdot(&item) {
for (rule_idx, rule) in self.grammar.rules().enumerate() {
if rule.lhs() == nonterminal_postdot {
let new_item = Lr0Item {
rhs: rule.rhs().to_vec(),
dot: 0,
};
if items
.map
.insert(rule_idx as RuleId, new_item.clone())
.is_none()
{
self.queue.push_back(new_item);
}
}
}
}
}
}
pub fn advance(&mut self, items: &Lr0Items, sym: Symbol) -> Option<Lr0Items> {
let mut new_items = Lr0Items::new();
for (&rule_id, item) in items.map.iter() {
if let Some(postdot) = self.postdot(item) {
if postdot == sym {
new_items.map.insert(
rule_id,
Lr0Item {
rhs: item.rhs.clone(),
dot: item.dot + 1,
},
);
}
}
}
if new_items.map.is_empty() {
None
} else {
self.closure(&mut new_items);
Some(new_items)
}
}
fn postdot(&self, item: &Lr0Item) -> Option<Symbol> {
item.rhs.get(item.dot as usize).cloned()
}
fn nonterminal_postdot(&self, item: &Lr0Item) -> Option<Symbol> {
match item.rhs.get(item.dot as usize) {
Some(&postdot) => {
if !self.terminal_set.has_sym(postdot) {
Some(postdot)
} else {
None
}
}
_ => None,
}
}
}
impl<'a, G> Lr0FsmBuilder<'a, G>
where
G: RuleContainer + Default,
for<'b> &'b G: RuleContainerRef<'b, Target = G>,
{
pub fn new(grammar: &'a mut G) -> Self {
Lr0FsmBuilder {
closure: Lr0ClosureBuilder::new(grammar),
sets_queue: VecDeque::new(),
cached_sets: BTreeMap::new(),
}
}
pub fn make_lr0_fsm(&mut self, start_sym: Symbol) -> Vec<Lr0Node> {
self.cached_sets.clear();
self.sets_queue.clear();
let initial_item_set = self.initial_item_set(start_sym);
self.introduce_set(initial_item_set, 0);
let mut result = vec![];
while let Some(items) = self.sets_queue.pop_front() {
let mut link = BTreeMap::new();
let terminals: Vec<Symbol> = self.closure.terminal_set.iter().collect();
for terminal in terminals {
if let Some(advanced_set) = self.closure.advance(&items, terminal) {
let id = self.id_of(Rc::new(advanced_set));
link.insert(terminal, id);
}
}
result.push(Lr0Node { items, link })
}
result
}
fn initial_item_set(&mut self, start_sym: Symbol) -> Rc<Lr0Items> {
let (_new_start, new_start_rule_id) = self.augment_grammar(start_sym);
let initial_item = Lr0Item {
rhs: vec![start_sym],
dot: 0,
};
let mut initial_item_set = Lr0Items::new();
initial_item_set.map.insert(new_start_rule_id, initial_item);
self.closure.closure(&mut initial_item_set);
Rc::new(initial_item_set)
}
fn augment_grammar(&mut self, start_sym: Symbol) -> (Symbol, RuleId) {
let new_start = self.closure.grammar.sym();
let rule_id = self.closure.grammar.rules().count() as RuleId;
let history_id = self
.closure
.grammar
.add_history_node(RootHistoryNode::NoOp.into());
self.closure
.grammar
.rule(new_start)
.rhs_with_history(&[start_sym], history_id);
(new_start, rule_id)
}
fn id_of(&mut self, items: Rc<Lr0Items>) -> SetId {
match self.cached_sets.get(&items) {
None => {
let id = self.cached_sets.len() as SetId;
self.introduce_set(items, id);
id
}
Some(&id) => id,
}
}
fn introduce_set(&mut self, items: Rc<Lr0Items>, id: SetId) {
self.cached_sets.insert(items.clone(), id);
self.sets_queue.push_back(items);
}
}