// module for generating the LR finite state machine
#![allow(dead_code)]
#![allow(unused_variables)]
#![allow(non_snake_case)]
#![allow(non_camel_case_types)]
#![allow(unused_parens)]
#![allow(unused_mut)]
#![allow(unused_assignments)]
#![allow(unused_doc_comments)]
#![allow(unused_imports)]
use std::collections::{HashMap,HashSet,BTreeSet};
use std::cell::{RefCell,Ref,RefMut};
//use std::rc::Rc;
use std::hash::{Hash,Hasher};
use std::mem;
use crate::grammar_processor::*;
use crate::lr_statemachine::{Stateaction,Statemachine,printrulela,add_action};
use crate::lr_statemachine::Stateaction::*;
// temporary
//use std::time::{Duration,SystemTime};
#[derive(Copy,Clone,PartialEq,Eq,Hash,Debug,PartialOrd,Ord)]
pub struct LALRitem(usize,usize); // rule index, position of the dot
// use Grammar.Symbols.len()+1 for the dummy mark
//propagation stores for each item if lookaheads should be propagated to
//(symindex,item). symindex identifies nextstate: FSM[si][symindex] lookup.
// don't know index yet because it's not pre-generated.
//Only kernel items will have entries (?)
pub struct LALRState
{
index: usize, // index into FSM vector
items: HashSet<LALRitem>,
kernel: HashSet<LALRitem>,
lookaheads: HashMap<LALRitem,RefCell<HashSet<usize>>>, //las for each item
propagation: HashMap<LALRitem,HashSet<(usize,LALRitem)>>,
lhss: BTreeSet<usize>, // set of lhs of rules in the state
}
impl LALRState
{
pub fn new(hint:usize) -> Self
{
LALRState {
index:0,
items:HashSet::with_capacity(hint),
kernel:HashSet::new(), //HashSet::with_capacity(16),
lookaheads:HashMap::with_capacity(hint),
propagation:HashMap::new(),
lhss: BTreeSet::new(),
}
}
fn insert(&mut self,item:LALRitem,lhs:usize) -> bool
{
let inserted = self.items.insert(item);
if inserted {
self.lhss.insert(lhs);
if self.lookaheads.get(&item).is_none()
{self.lookaheads.insert(item,RefCell::new(HashSet::new()));}
if self.propagation.get(&item).is_none()
{self.propagation.insert(item,HashSet::new());}
}
inserted
}
pub fn hashval_lalr(&mut self) -> usize // note: NOT UNIQUE
{
let mut key=self.items.len() + self.lhss.len()*1000000;
let limit = usize::MAX/1000 -1;
let mut cx = 6; //8
for s in &self.lhss {key+=1000*s; cx-=1; if cx==0 || key>=limit {break;}}
key
}
/*
pub fn hashval_lalr(&mut self) -> usize // note: NOT UNIQUE
{
let mut key=self.items.len()<<24 + self.lhss.len()<<16;
let limit = usize::MAX/1000 -1;
let mut cx = 8;
for LALRitem(ri,pi) in &self.kernel {
key += 500*ri+pi;
}
key
}
*/
pub fn state_eq(&self, state2:&LALRState) -> bool
{
// ignore index - set later
if self.items.len() != state2.items.len() {return false;}
for kitem in self.kernel.iter() {
if !state2.kernel.contains(kitem) {return false;}
}// for each item
true
}// state_eq
}//impl LALRState
impl PartialEq for LALRState
{
fn eq(&self, other:&LALRState) -> bool
{ self.state_eq(&other) }
fn ne(&self, other:&LALRState) ->bool
{ !self.state_eq(&other) }
}
impl Eq for LALRState {}
impl Grammar // Grammar additions
{
// First set of a sequence of symbols given set of lookaheads
pub fn Firstseqla(&self, Gs:&[Gsym], las:&HashSet<usize>) -> HashSet<usize>
{
let mut Fseq = HashSet::with_capacity(2);
let mut i = 0;
let mut nullable = true;
while nullable && i<Gs.len()
{
if (Gs[i].terminal) {Fseq.insert(Gs[i].index); nullable=false; }
else // Gs[i] is non-terminal
{
//println!("symbol {}, index {}", &Gs[i].sym, Gs[i].index);
let firstgsym = self.First.get(&Gs[i].index).unwrap();
for s in firstgsym { Fseq.insert(*s); }
if !self.Nullable.contains(&Gs[i].index) {nullable=false;}
}
i += 1;
}//while
if nullable {
for la in las {Fseq.insert(*la);}
}
Fseq
}//FirstSeqb
//determine if a sequence of symbols is nullable
pub fn Nullableseq(&self, Gs:&[Gsym]) -> bool
{
for g in Gs {
if g.terminal || !self.Nullable.contains(&g.index) {return false;}
}
return true;
}
}//impl Grammar
pub struct LALRMachine
{
pub Gmr: Grammar,
pub States: Vec<LALRState>,
pub Statelookup: HashMap<usize,BTreeSet<usize>>,
pub FSM: Vec<HashMap<usize,Stateaction>>,
sr_conflicts:HashMap<(usize,usize),(bool,bool)>,
}
impl LALRMachine
{
pub fn new(gram:Grammar) -> Self
{
LALRMachine {
Gmr: gram,
States: Vec::with_capacity(1024), // reserve 1K states
Statelookup: HashMap::with_capacity(1024),
FSM: Vec::with_capacity(8*1024),
sr_conflicts:HashMap::new(),
}
}//new
pub fn to_statemachine(self) -> Statemachine // transfer before writeparser
{
Statemachine {
Gmr: self.Gmr,
States: Vec::new(),
Statelookup:HashMap::new(),
FSM: self.FSM,
lalr:true,
Open:Vec::new(),
sr_conflicts:HashMap::new(),
}
}//to_statemachine
// generate the GOTO sets of a state with index si, creates new states.
// this verions does not add reduce actions since lookaheads needs to be
// propagated first. PURE LR(0);
fn makegotos(&mut self, si:usize)
{
let ref state = self.States[si];
// key to following hashmap is the next symbol's index after pi (the dot)
// the values of the map are the "kernels" of the next state to generate
let mut newstates:HashMap<usize,LALRState> = HashMap::with_capacity(64);
let mut keyvec:Vec<usize> = Vec::new(); //keys of newstates
for item in &state.items
{
let (itemri,itempi) = (item.0,item.1);
let rule = &self.Gmr.Rules[itemri]; // rule ref
if itempi<rule.rhs.len() { // can goto (dot before end of rule)
let nextsymi = rule.rhs[itempi].index;
if let None = newstates.get(&nextsymi) {
newstates.insert(nextsymi,LALRState::new(self.Gmr.Symbols.len()));
keyvec.push(nextsymi);
}
let symstate = newstates.get_mut(&nextsymi).unwrap();
// add new item to states associated with nextsymi
let newitem = LALRitem(itemri,itempi+1); //kernel item in new state
symstate.kernel.insert(newitem);
// SHIFT/GOTONEXT actions added by addstate function
}//can goto
/* NO REDUCE/ACCEPT UNTIL LATER */
}// for each item
// form closures for all new states and add to self.States list
for key in keyvec //keyvec must be separate to avoid borrow error
{
let mut kernelstate = newstates.remove(&key).unwrap();
closure0(&mut kernelstate,&self.Gmr);
self.addstate(kernelstate,si,key); //only place addstate called
}
}//makegotos
// addstate *** now pure LR(0)
// psi is previous state index, nextsym is next symbol
// state already closed by makegotos
fn addstate(&mut self, mut state:LALRState, psi:usize, nextsymi:usize)
{ let nextsym = &self.Gmr.Symbols[nextsymi].sym;
let newstateindex = self.States.len(); // index of new state
state.index = newstateindex;
let lookupkey = state.hashval_lalr();
if let None=self.Statelookup.get(&lookupkey) {
self.Statelookup.insert(lookupkey,BTreeSet::new());
}
let indices = self.Statelookup.get_mut(&lookupkey).unwrap();
let mut toadd = newstateindex; // defaut is add new state (will push)
for i in indices.iter() //compares only LR(0) kernel items
{
if &state==&self.States[*i] {toadd=*i; break; } // state i exists
}
if self.Gmr.tracelev>3 {println!("Transition to state {} from state {}, symbol {}..",toadd,psi,nextsym);}
if toadd==newstateindex { // add new state
indices.insert(newstateindex); // add to StateLookup index hashset
self.States.push(state);
self.FSM.push(HashMap::with_capacity(128)); // always add row to fsm at same time
}// add new state
// add to- or change FSM TABLE ... only Shift or Gotnext added here.
let gsymbol = &self.Gmr.Symbols[nextsymi];
let newaction = if gsymbol.terminal {Stateaction::Shift(toadd)}
else {Stateaction::Gotonext(toadd)};
add_action(&mut self.FSM, &self.Gmr, newaction,psi,nextsymi,&mut self.sr_conflicts,false); // no need to check conflicts with these actions
} //addstate
fn set_propagations(&mut self) // Algorithm 4.12 in old dragon book (4.63 new)
{
// add inital EOF lookahead to state 0.
let dummy = self.Gmr.Symbols.len()+1; // distinguish from real symbols (#)
for si in 0..self.States.len() {
// only do for kernel items - but must regenerate the closure
for kitem in self.States[si].kernel.clone() {
// calculate LR(1) closure of this item with dummy lookahead
let mut open = vec![(kitem,dummy)];
let mut closure = HashSet::new();
let mut closed = 0;
while closed < open.len()
{
let (item,itemla) = open[closed];
closed+=1;
closure.insert((item,itemla));
let (ri,pi) = (item.0,item.1);
let ruleri = &self.Gmr.Rules[ri];
let lhsi = ruleri.lhs.index;
if pi<ruleri.rhs.len() {// just generate LR(1) closure
let Bsym = &ruleri.rhs[pi];
if !self.Gmr.Symbols[Bsym.index].terminal { //nonterminal
for rulent in self.Gmr.Rulesfor.get(&Bsym.index).unwrap() {
let baseitem = LALRitem(*rulent,0);
let rulelas = self.Gmr.Firstseq(&ruleri.rhs[pi+1..],itemla);
let mut sponlas = self.States[si].lookaheads.get(&baseitem).unwrap().borrow_mut();
for la in rulelas.iter() {
let newitem = (baseitem,*la);
if !closure.contains(&newitem) {open.push(newitem);}
if *la<self.Gmr.Symbols.len() {sponlas.insert(*la);}
} // add new item to closure for each spontaneous la
}//for each rule for Bsym
}//Bsym is non-terminal
}//if pi<rhs.len()
}//while !closed // closure for one kernel item (kitem)
// decide if propagate or spontaneous
for (item,itemla) in closure.iter() {
let (ri,pi) = (item.0,item.1);
let ruleri = &self.Gmr.Rules[ri];
if pi >= ruleri.rhs.len() {continue;}
let Xsym = &ruleri.rhs[pi];
let mut nsi = self.FSM.len();//invalid default
match self.FSM[self.States[si].index].get(&Xsym.index) {
Some(Shift(nexts)) | Some(Gotonext(nexts)) => {nsi=*nexts;},
_ => {panic!("THIS SHOULD NOT HAPPEN!");},
}//match, nsi is the state number from transition on Xsym
let nextitem = LALRitem(ri,pi+1);
if *itemla!=dummy { // spontaneous item
let mut nextitemlas = self.States[nsi].lookaheads.get(&nextitem).unwrap().borrow_mut();
nextitemlas.insert(*itemla);
} // insert spontaneous directly to nextitem in nsi=GOTO(I,Xsym)
else {
let kpropagation = self.States[si].propagation.get_mut(&kitem).unwrap();
kpropagation.insert((nsi,nextitem));
} // propagate
}// for each item in closure of (kitem,dummy)
} // for kernel item in state si
} // for each state si
}//set_propagations (new version)
// faster but has a problem with non-determinism, too many lookaheads
// the "interior" must consists of LR(1) items, not just LR(0) items,
// each lookahead of the LR(0) item must be stored separately so it
// can be re-examined by the while closed...loop.
fn set_propagations0(&mut self) // and spontaneous lookaheads
{
let dummy = self.Gmr.Symbols.len()+1; // distinguish from real symbols (#)
for si in 0..self.States.len()
{
// only do for kernel items - but must regenerate the closure
for kitem in self.States[si].kernel.clone()
{
//if kitem.1<self.Gmr.Rules[kitem.0].rhs.len() {
self.States[si].lookaheads.get(&kitem).unwrap().borrow_mut().insert(dummy);
//}
let mut interior = HashSet::new(); //HashSet::new();
let mut closure = vec![kitem];
let mut closed = 0;
while closed<closure.len()
{
let item = closure[closed];
let (ri,pi) = (item.0,item.1);
let rulei = &self.Gmr.Rules[ri];
let lhsi = rulei.lhs.index;
let itemlas= self.States[si].lookaheads.get(&item).unwrap().borrow().clone();
for la in itemlas.iter() {interior.insert((item,*la));} //may include #
closed += 1;
if pi<rulei.rhs.len() {// find .X , X terminal or non-terminal
let Xsym = &rulei.rhs[pi]; // symbol X of dragon book
let propagate = self.States[si].lookaheads.get(&item).unwrap().borrow().contains(&dummy);
//if si==0 {println!("dummy in state 0, item {:?}: {}, kitem {:?}",&item,propagate,&kitem);}
// use existing FSM to find nextstate:
let mut nsi = self.FSM.len();//invlalid default
match self.FSM[self.States[si].index].get(&Xsym.index) {
Some(Shift(nexts)) | Some(Gotonext(nexts)) => {nsi=*nexts;},
_ => {panic!("THIS SHOULD NOT HAPPEN!");},
} // nsi is the state number from transition on Xsym
let nextitem = LALRitem(ri,pi+1);
if propagate /*&& item!=kitem*/ {
let kpropagation = self.States[si].propagation.get_mut(&kitem).unwrap();
kpropagation.insert((nsi,nextitem));
}// insert into propagation table
// always propagate the spontaneous items?
/*else*/ if si!=nsi || item!=nextitem { // the lookaheads of this item should be sent to nextstate
//let itemlas= self.States[si].lookaheads.get(&item).unwrap().borrow();
let mut nextlas = self.States[nsi].lookaheads.get(&nextitem).unwrap().borrow_mut();
for la in itemlas.iter() {
if *la<self.Gmr.Symbols.len() {
nextlas.insert(*la);
/*
let inserted2 = nextlas.insert(*la);
if inserted2 { //debug
let symname = &self.Gmr.Symbols[*la].sym;
let lhsindex = self.Gmr.Rules[nextitem.0].lhs.index;
let lhsname = &self.Gmr.Symbols[lhsindex].sym;
if lhsname=="UnaryExpr" && nextitem.0==40 && symname=="LSQUAREB" {
println!("{} ADDED TO LAS FOR UnaryExpr, rule {}",symname,nextitem.0);
}
}//debug
*/
}
}// for la in itemlas
}// if not propagate, then spontaneous
if !Xsym.terminal { // X is non-terminal, add closure items
// adds spontaneous lookaheads, plus #.
//let dummy2 = dummy+1;
let mut Xlookaheads = self.Gmr.Firstseq(&rulei.rhs[pi+1..],dummy);
if Xlookaheads.remove(&dummy) { // local use of dummy
// this could be the kernel item with dummy ... ?
//Xlookaheads.remove(&dummy);
for ila in itemlas.iter() {Xlookaheads.insert(*ila);}//dummy inserted
//Xlookaheads.remove(&dummy);
}
for rulent in self.Gmr.Rulesfor.get(&Xsym.index).unwrap() {
let newitem = LALRitem(*rulent,0); //non-kernel item
// if newitem!=item for borrow checks?
let mut slas = self.States[si].lookaheads.get(&newitem).unwrap().borrow_mut();
let mut reinsert = false;
for xla in Xlookaheads.iter() {
// don't propagate the dummy: possible fix 11/3/2022
//if *xla < self.Gmr.Symbols.len() {slas.insert(*xla);}
slas.insert(*xla);
/*
let rinsert1 = slas.insert(*xla);
if rinsert1 && *xla<self.Gmr.Symbols.len() { //debug
let symname = &self.Gmr.Symbols[*xla].sym;
let lhsindex = self.Gmr.Rules[newitem.0].lhs.index;
let lhsname = &self.Gmr.Symbols[lhsindex].sym;
if lhsname=="UnaryExpr" && newitem.0==40 && symname=="LSQUAREB" {
println!("{} ADDED TO LAS FOR UnaryExpr, rule {}",symname,newitem.0);
}
}//debug
*/
if !interior.contains(&(newitem,*xla)) {reinsert =true; }
}
// these lookaheads should be sent over to nextstate next loop
if reinsert /* !interior.contains(&newitem) */ {
closure.push(newitem); // add to "frontier"
}
//println!("lookaheads inserted for newitem {:?}: {:?}",&newitem,&Xlookaheads);
}// for each rule of this non-terminal X
}//X nonterminal
}// pi not at right end
}//while !closed
}//for each kernel item
}//for each state
}//set_propagations0
// called after all states created, propagations marked.
fn propagate_lookaheads(&mut self)
{
let mut changed = true;
//let mut round = 0;
while changed
{
//round +=1;
changed = false;
for si in 0..self.States.len()
{
for item in &self.States[si].kernel { //-borrow checker!
let (ri,pi) = (item.0, item.1);
//println!("propagate_lookahead looking at kernel item {:?}, state {}",&item,si);
//if pi>0 || ri == self.Gmr.startrulei { // kernel item
let itemlas = self.States[si].lookaheads.get(&item).unwrap().borrow();
let props = self.States[si].propagation.get(&item).unwrap();
//println!("props len {}", props.len());
for (nextstate,nextitem) in props.iter() {
//println!("{}: found nextitem ({},{}) in next state {}",self.States[*nextstate].items.contains(nextitem),nextitem.0,nextitem.1,nextstate);
let nextlasopt = self.States[*nextstate].lookaheads.get(nextitem);
if let Some(rfcell)=nextlasopt {
if *nextstate!=si || nextitem!=item { //runtime borrow check
let mut nextlas = rfcell.borrow_mut();
for la in itemlas.iter() {
if *la>=self.Gmr.Symbols.len() {continue;}
changed =nextlas.insert(*la)||changed;
}
}
}// some(refcell)
else {panic!("NO lookahead ENTRY!");}
} // each propagation mark
//}//kernel item
}//for each item in state
}//for each state
} // which changed
}//propagate_lookaheads
// set reduce actions and check for conflicts
fn set_reduce(&mut self)
{
for si in 0..self.States.len()
{
for item in &self.States[si].items
{
let (ri,pi) = (item.0,item.1);
let itemlas = self.States[si].lookaheads.get(item).unwrap().borrow();
if pi==self.Gmr.Rules[ri].rhs.len() { //dot at end of rhs
// let itemlas = self.States[si].lookaheads.get(item).unwrap().borrow();
for la in itemlas.iter() { // for each lookahead
if *la>=self.Gmr.Symbols.len() {continue;} // skip the dummy
//println!("adding reduce/accept rule {}, la {}",ri,&self.Gmr.Symbols[*la].sym);
let isaccept = (ri == self.Gmr.startrulei && la==&(self.Gmr.eoftermi));
if isaccept {
add_action(&mut self.FSM,&self.Gmr,Accept,si,*la,&mut self.sr_conflicts,false); // don't check conflicts here
}
else {
add_action(&mut self.FSM,&self.Gmr,Reduce(ri),si,*la,&mut self.sr_conflicts,true); // check conflicts here
//println!("added Reduced({}) to state {}, la {}",ri,si,la);
}
} // for each la
}//if reduce situation
} // for each item
} // for each state
}//set_reduce
//reform closure after lookaheads have propagated to kernels.
fn reclose(&mut self) // set remaining lookaheads
{
for state in self.States.iter_mut() {
for kitem in state.kernel.iter() {
let mut interior =HashSet::new();
let mut closure = vec![*kitem];
let mut closed = 0;
while closed<closure.len()
{
let item = closure[closed];
let (ri,pi) = (item.0,item.1);
let rulei = &self.Gmr.Rules[ri];
let lhsi = rulei.lhs.index;
interior.insert(item);
closed += 1;
if pi<rulei.rhs.len() && !rulei.rhs[pi].terminal {
let propagate = self.Gmr.Nullableseq(&rulei.rhs[pi+1..]);
if propagate {
let Xsym = &rulei.rhs[pi]; // symbol X of dragon book
// adds remaining lookaheads, plus #.
// spontaneously generated lookaheads already there .. only need
// to add from kernels.
let mut Xlookaheads = HashSet::new();
let itemlas = state.lookaheads.get(&item).unwrap().borrow();
for ila in itemlas.iter() {Xlookaheads.insert(*ila);}
for rulent in self.Gmr.Rulesfor.get(&Xsym.index).unwrap() {
let newitem = LALRitem(*rulent,0);
if !interior.contains(&newitem) {
closure.push(newitem); // add to "frontier"
}
// newitem cannot be kitem because newitem is non-kernel
if newitem!=item { //runtime borrow check!
let mut slas = state.lookaheads.get(&newitem).unwrap().borrow_mut();
for xla in Xlookaheads.iter() {slas.insert(*xla);}
}
}// for each rule of this non-terminal X
} //if propagate
}//X nonterminal
}//while !closed
} // for each kernel item
} //for each state
}//reclose -- adding too many
pub fn generatefsm(&mut self)
{
// tracing
if self.Gmr.tracelev>3 {
for i in 0..self.Gmr.Symbols.len() {println!("symbol {}: {}",i,&self.Gmr.Symbols[i].sym);}
for i in 0..self.Gmr.Rules.len() {println!("rule {}: {}-->length {}",i,&self.Gmr.Rules[i].lhs.sym,&self.Gmr.Rules[i].rhs.len());}
}
// create initial state, closure from initial item:
// START --> .topsym EOF
let mut startstate=LALRState::new(self.Gmr.Rules.len());
let startitem = LALRitem(self.Gmr.startrulei,0);
startstate.kernel.insert(startitem);
closure0(&mut startstate,&self.Gmr);
self.States.push(startstate); // add start state, first state
self.FSM.push(HashMap::with_capacity(128)); // row for state
// now generate closure for state machine (not individual states)
let mut closed:usize = 0;
//println!("before makegotos");
//let timer = SystemTime::now();
while closed<self.States.len()
{
self.makegotos(closed);
closed += 1;
}//while not closed
//println!("after makegotos");
//println!("states generated: {}",self.States.len());
//let t1 = timer.elapsed().unwrap_or(Duration::ZERO);
self.States[0].lookaheads.get(&startitem).unwrap().borrow_mut().insert(self.Gmr.eoftermi); // initial lookahead
self.set_propagations();
//println!("set_propagations");
//let t2 = timer.elapsed().unwrap_or(t1);
self.propagate_lookaheads();
//println!("after propagate_lookaheads");
//let t3 = timer.elapsed().unwrap_or(t2);
self.reclose(); // set lookaheads for non-kernel items
//println!("after reclose");
//let t4 = timer.elapsed().unwrap_or(t3);
self.set_reduce();
/*
let t5 = timer.elapsed().unwrap_or(t4);
let (t1m,t2m,t3m) = (t1.as_millis(),t2.as_millis(),t3.as_millis());
let (t4m,t5m) =(t4.as_millis(),t5.as_millis());
println!("time to call makegotos, LR(0) state table: {}",t1m);
println!("time to call set_propagation marks: {}",t2m-t1m);
println!("time to propagate_lookaheads: {}",t3m-t2m);
println!("time to reclose and finalize lookaheads: {}",t4m-t3m);
println!("time to set_reduce: {}",t5m-t4m);
*/
// optional trace
if self.Gmr.tracelev>2 {
for state in &self.States {printlalrstate(state,&self.Gmr);}
}
else if self.Gmr.tracelev>1 {
print!("INITIAL STATE: ");
printlalrstate(&self.States[0],&self.Gmr);
}
}//generatefsm
}//impl LALRMachine
//AXIOM: if item exists, an entry must exist for it in lookaheads
// purel LR0 state closure
fn closure0(state: &mut LALRState,Gmr:&Grammar)
{// assuming kernel is a kernel item and not? in state
let mut closure = Vec::new();
let mut onclosure = HashSet::new();
// start with kernel items
for kitem in state.kernel.iter() {
closure.push(*kitem); onclosure.insert(*kitem);
}
let mut closed = 0;
while closed < closure.len()
{
let item = closure[closed];
let (ri,pi) = (item.0,item.1);
let rulei = &Gmr.Rules[ri];
let lhsi = rulei.lhs.index;
state.insert(item,lhsi); // insert into state.items here
closed += 1;
if pi<rulei.rhs.len() && !rulei.rhs[pi].terminal {// add closure items
//let sympii = &rulei.rhs[pi].index;
for rulent in Gmr.Rulesfor.get(&rulei.rhs[pi].index).unwrap() {
let newitem = LALRitem(*rulent,0); // can't be kernel again
if !state.items.contains(&newitem) && !onclosure.contains(&newitem) {
closure.push(newitem); // add to "frontier"
onclosure.insert(newitem);
}
}// for each rule of this non-terminal X
}// not .X situation, no closure items added
}//while !closed
}//closure0 - pure LR(0)
//////
// independent function for tracing
pub fn printlalrstate(state:&LALRState,Gmr:&Grammar)
{
println!("-----------\nState {}:",state.index);
for (LALRitem(ri,pi),las) in state.lookaheads.iter()
{
let ref lhs_sym = Gmr.Rules[*ri].lhs.sym;
let ref rhs = Gmr.Rules[*ri].rhs;
print!(" ({}) {} --> ",ri,lhs_sym);
let mut position = 0;
for gsym in rhs
{
if &position==pi {print!(".");}
print!("{} ",gsym.sym);
position+=1;
}
if &position==pi {print!(". ");}
print!(" {{ ");
for la in las.borrow().iter()
{
if *la<Gmr.Symbols.len() { print!("{},",Gmr.symref(*la));}
}
println!(" }}");
}//for key
}//printlalrstate