grammar_utils/lr0/
machine.rs

1use crate::*;
2use super::*;
3
4pub struct Machine<'g, 't> {
5    parse_table: &'t ParseTable<'g>,
6    head: Vec<Symbol<'g>>,
7    stack: Vec<(StateIndex, Symbol<'g>)>,
8    halted: bool,
9    step: usize,
10}
11
12impl<'g, 't> Machine<'g, 't> {
13    pub fn new(parse_table: &'t ParseTable<'g>) -> Machine<'g, 't> {
14        Machine {
15            parse_table,
16            head: vec![],
17            stack: vec![],
18            halted: false,
19            step: 0,
20        }
21    }
22
23    fn state(&self) -> StateIndex {
24        self.stack
25            .last()
26            .map(|(state_index, _symbol)| {
27                *state_index
28            })
29            .unwrap_or(StateIndex(0))
30    }
31
32    fn step(&mut self, symbol: Option<Symbol<'g>>) {
33        let state = self.state();
34
35        {
36            eprintln!("STEP:   {:?}", self.step);
37            eprintln!("SYMBOL: {:?}", symbol);
38            eprintln!("STACK:  {:?}", &self.stack);
39            eprintln!("STATE:  {:?}", state);
40            eprintln!();
41
42            let state = &self.parse_table.states[usize::from(state)];
43            for item in state.itemset().items() {
44                eprintln!("    {item:?}");
45            }
46            eprintln!();
47        }
48
49
50        let key = (state, symbol);
51        let actions = &self.parse_table.actions.get(&key);
52
53        if let Some(actions) = actions {
54            let action = if actions.len() == 0 {
55                panic!("Machine halted unexpectedly")
56            } else if actions.len() == 1 {
57                actions[0]
58            } else {
59                panic!("Multiple actions: {actions:?}")
60            };
61
62            match action {
63                Action::Shift(dst_state_index) => {
64                                self.stack.push((dst_state_index, symbol.unwrap()));
65                            }
66                Action::Reduce(rule) => {
67                                self.head.insert(0, rule.lhs());
68
69                                if let Some(symbol) = symbol {
70                                    self.head.insert(0, symbol);
71                                }
72
73                                let mut children = vec![];
74
75                                for _ in 0..rule.rhs().len() {
76                                    let Some((_state, sym)) = self.stack.pop() else { panic!() };
77                                    children.insert(0, sym);
78                                }
79                            }
80                Action::Halt => {
81                    self.halted = true;
82                }
83            }
84        }
85    }
86
87    pub fn run(&mut self, input: &mut impl Iterator<Item=Symbol<'g>>) {
88        while !self.halted {
89            if let Some(symbol) = self.head.pop() {
90                self.step(Some(symbol));
91            } else {
92                let symbol = input.next();
93                self.step(symbol);
94            }
95
96            self.step += 1;
97        }
98    }
99}
grammar_utils/lr0/machine.rs

grammar_utils/lr0/
machine.rs
