grammar_utils/lr0/
item.rs

1use std::collections::BTreeSet;
2
3use crate::*;
4
5#[derive(Clone, Copy)]
6pub struct Item<'g> {
7    rule: Rule<'g>,
8    pos: usize,
9}
10
11impl<'g> Item<'g> {
12    pub fn new(rule: Rule<'g>, pos: usize) -> Item<'g> {
13        assert!(pos <= rule.rhs().len());
14
15        Item {
16            rule,
17            pos,
18        }
19    }
20
21    pub fn rule(&self) -> Rule<'g> {
22        self.rule
23    }
24
25    pub fn pos(&self) -> usize {
26        self.pos
27    }
28
29    pub fn grammar(&self) -> &'g Grammar {
30        self.rule.grammar()
31    }
32
33    pub fn lhs(&'g self) -> Symbol<'g> {
34        self.rule.lhs()
35    }
36
37    pub fn rhs(&'g self) -> Vec<Symbol<'g>> {
38        self.rule.rhs()
39    }
40
41    pub fn next_symbol(&self) -> Option<Symbol<'g>> {
42        if self.pos() < self.rhs().len() {
43            Some(self.rule.rhs()[self.pos])
44        } else {
45            None
46        }
47    }
48
49    pub fn step(&self) -> Option<Item<'g>> {
50        if self.pos() < self.rhs().len() {
51            Some(Item::new(self.rule, self.pos + 1))
52        } else {
53            None
54        }
55    }
56
57    pub fn is_finished(&self) -> bool {
58        self.pos() == self.rhs().len()
59    }
60}
61
62impl<'g> std::fmt::Debug for Item<'g> {
63    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
64        let lhs = self.rule.lhs();
65        let rhs = self.rule.rhs();
66        write!(f, "{lhs:?} ->")?;
67        for i in 0..self.pos {
68            write!(f, " {:?}", &rhs[i])?;
69        }
70
71        write!(f, " .")?;
72
73        for i in self.pos..rhs.len() {
74            write!(f,  " {:?}", &rhs[i])?;
75        }
76        Ok(())
77    }
78}
79
80impl<'g> PartialEq for Item<'g> {
81    fn eq(&self, other: &Self) -> bool {
82        self.rule() == other.rule() && self.pos == other.pos
83    }
84}
85
86impl<'g> Eq for Item<'g> {}
87
88#[derive(Debug)]
89#[derive(Clone)]
90pub struct ItemSet<'g> {
91    grammar: &'g Grammar,
92    items: Vec<Item<'g>>,
93}
94
95impl<'g> PartialEq for ItemSet<'g> {
96    fn eq(&self, other: &Self) -> bool {
97        std::ptr::eq(self.grammar, other.grammar) && self.items == other.items
98    }
99}
100
101impl<'g> Eq for ItemSet<'g> {}
102
103
104impl<'g> ItemSet<'g> {
105    pub fn grammar(&self) -> &'g Grammar {
106        self.grammar
107    }
108
109    pub fn empty(grammar: &'g Grammar) -> Self {
110        ItemSet {
111            grammar,
112            items: vec![],
113        }
114    }
115
116    pub fn singleton(item: Item<'g>) -> Self {
117        let grammar: &'g Grammar = item.grammar();
118        let itemset = ItemSet {
119            grammar,
120            items: vec![item],
121        };
122        itemset.closure()
123    }
124
125    pub fn is_empty(&self) -> bool {
126        self.items.is_empty()
127    }
128
129    pub fn items(&self) -> Vec<Item<'g>> {
130        self.items.clone()
131    }
132
133    pub(crate) fn closure(&self) -> ItemSet<'g> {
134        let mut nonterms_added = BTreeSet::new();
135        let mut itemset = self.items.clone();
136
137        loop {
138            let mut dirty = false;
139            let mut new_items = vec![];
140
141            for item in &itemset {
142                if let Some(symbol) = item.next_symbol() {
143                    if symbol.is_nonterminal() {
144                        if !nonterms_added.contains(&symbol) {
145                            nonterms_added.insert(symbol);
146
147                            let symbol_rules = self.grammar
148                                .rules()
149                                .into_iter()
150                                .filter(|rule| {
151                                    rule.lhs() == symbol
152                                });
153
154                            for rule in symbol_rules {
155                                let item = Item::new(rule, 0);
156                                new_items.push(item);
157                                dirty = true;
158                            }
159                        }
160                    }
161                }
162
163            }
164
165            for item in new_items {
166                if !itemset.contains(&item) {
167                    itemset.push(item);
168                }
169            }
170
171            if !dirty {
172                break;
173            }
174        }
175
176        ItemSet {
177            grammar: self.grammar,
178            items: itemset,
179        }
180    }
181
182    pub fn follow(&self, symbol: Symbol<'g>) -> ItemSet<'g> {
183        let mut items = vec![];
184        for item in &self.items {
185            if let Some(next_symbol) = item.next_symbol() {
186                if next_symbol == symbol {
187                    items.push(item.step().unwrap());
188                }
189            }
190        }
191
192        let itemset = ItemSet {
193            grammar: self.grammar,
194            items,
195        };
196
197        itemset.closure()
198    }
199}
grammar_utils/lr0/item.rs

grammar_utils/lr0/
item.rs
