grammar_utils/lr1/
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                eprintln!("ACTION:  {action:?}");
87                eprintln!();
88            }
89        }
90    }
91
92    pub fn run(&mut self, input: &mut impl Iterator<Item=Symbol<'g>>) {
93        while !self.halted {
94            if let Some(symbol) = self.head.pop() {
95                self.step(Some(symbol));
96            } else {
97                let symbol = input.next();
98                self.step(symbol);
99            }
100
101            self.step += 1;
102        }
103    }
104}
grammar_utils/lr1/machine.rs

grammar_utils/lr1/
machine.rs
