grammar_utils/lr1/
machine.rs

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

grammar_utils/lr1/
machine.rs
