grammar_utils/lr1/
item.rs

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

grammar_utils/lr1/
item.rs
