use std::fmt;
use std::rc::Rc;
use crate::rules::{Grammar, Production, Rule};
#[derive(Debug, Clone, PartialEq)]
pub struct LR0 {
pub rule: Rc<Rule>,
pub pos: usize,
}
impl LR0 {
pub fn new(rule: &Rc<Rule>) -> Self {
Self {
rule: rule.clone(),
pos: 0,
}
}
pub fn is_active(&self) -> bool {
self.pos < self.rule.len()
}
pub fn advance(&self) -> Self {
assert!(self.is_active());
Self {
rule: self.rule.clone(),
pos: self.pos + 1,
}
}
pub fn next_production(&self) -> Option<&Production> {
self.rule.productions.get(self.pos)
}
}
impl fmt::Display for LR0 {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{} →", self.rule.symbol)?;
for idx in 0..self.rule.len() {
if idx == self.pos {
write!(f, " ・")?;
}
write!(f, " {}", self.rule.productions[idx])?;
}
if !self.is_active() {
write!(f, " ・")?;
}
Ok(())
}
}
#[derive(Debug, Clone, PartialEq)]
pub struct State {
pub lr0: LR0,
pub origin: usize,
}
impl State {
pub fn new(lr0: LR0, origin: usize) -> Self {
Self { lr0, origin }
}
pub fn advance(&self) -> Self {
Self::new(self.lr0.advance(), self.origin)
}
}
#[derive(Debug)]
pub struct Chart(Vec<Vec<State>>);
impl Chart {
pub fn new(length: usize) -> Self {
Self(vec![Vec::new(); length])
}
pub fn len(&self) -> usize {
self.0.len()
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn len_at(&self, k: usize) -> usize {
self.0[k].len()
}
pub fn has(&self, k: usize, state: &State) -> bool {
self.0[k].contains(state)
}
pub fn add(&mut self, k: usize, state: State) {
if !self.has(k, &state) {
self.0[k].push(state);
}
}
fn get_state(&self, k: usize, idx: usize) -> State {
self.0[k][idx].clone()
}
}
impl IntoIterator for Chart {
type Item = (usize, Vec<State>);
type IntoIter = std::iter::Enumerate<std::vec::IntoIter<Vec<State>>>;
fn into_iter(self) -> Self::IntoIter {
self.0.into_iter().enumerate()
}
}
impl fmt::Display for Chart {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
for k in 0..self.len() {
writeln!(f, "State {}:", k)?;
for state in self.0[k].iter() {
writeln!(f, " {}..{}: {}", state.origin, k, state.lr0)?;
}
}
Ok(())
}
}
pub fn parse_chart(g: &Grammar, input: &[&str]) -> Chart {
let mut chart = Chart::new(input.len() + 1);
for rule in g.rules.get(&g.start).expect("grammar missing start rules") {
chart.add(0, State::new(LR0::new(&rule), 0));
}
for k in 0..chart.len() {
let mut idx = 0;
while idx < chart.len_at(k) {
let state = chart.get_state(k, idx);
idx += 1;
if let Some(production) = state.lr0.next_production() {
if production.is_nonterminal() {
predictor(g, &mut chart, k, &state);
} else {
scanner(&mut chart, k, &state, input);
}
} else {
completer(&mut chart, k, &state);
}
}
}
chart
}
fn completer(chart: &mut Chart, k: usize, state: &State) {
assert!(!state.lr0.is_active(), "tried to complete active state");
for idx in 0..chart.len_at(state.origin) {
let other = chart.get_state(state.origin, idx);
if let Some(np) = other.lr0.next_production() {
if np.symbol == state.lr0.rule.symbol {
chart.add(k, other.advance())
}
}
}
}
fn predictor(g: &Grammar, chart: &mut Chart, k: usize, state: &State) {
assert!(state.lr0.is_active(), "tried to predict non-active state");
assert!(
state.lr0.next_production().unwrap().is_nonterminal(),
"tried to predict a terminal"
);
let needed_symbol = &state.lr0.next_production().unwrap().symbol;
for wanted_rule in g
.rules
.get(needed_symbol)
.unwrap_or_else(|| panic!("missing rules for production {}", needed_symbol))
{
chart.add(k, State::new(LR0::new(wanted_rule), k));
if g.is_nullable(&needed_symbol) {
chart.add(k, state.advance());
}
}
}
fn scanner(chart: &mut Chart, k: usize, state: &State, input: &[&str]) {
assert!(state.lr0.is_active(), "tried to scan non-active state");
assert!(
state.lr0.next_production().unwrap().is_terminal(),
"tried to scan a nonterminal"
);
let needed_symbol = &state.lr0.next_production().unwrap().symbol;
if k < input.len() && input[k] == needed_symbol {
chart.add(k + 1, state.advance());
}
}