parol/analysis/
k_decision.rs

1use crate::analysis::LookaheadDFA;
2use crate::analysis::lookahead_dfa::ProductionIndex;
3use crate::analysis::{FirstSet, FollowSet, first_k, follow_k};
4use crate::grammar::cfg::NonTerminalIndexFn;
5use crate::{GrammarAnalysisError, MAX_K};
6use crate::{GrammarConfig, KTuples};
7use anyhow::{Result, anyhow, bail};
8use parol_runtime::log::trace;
9use std::cell::RefCell;
10use std::collections::BTreeMap;
11use std::rc::Rc;
12
13use super::follow::ResultMap;
14
15/// Cache of FirstSets
16#[derive(Debug, Default)]
17pub struct FirstCache(pub [Rc<RefCell<FirstSet>>; MAX_K + 1]);
18
19/// A cache entry consisting of a result map for enhanced generation of the next k set and the
20/// follow set for a given k
21#[derive(Debug, Clone, Default)]
22pub struct CacheEntry {
23    pub(crate) last_result: ResultMap,
24    pub(crate) follow_set: FollowSet,
25}
26
27impl CacheEntry {
28    /// If this method returns true, the follow set is empty.
29    /// This is used for the follow cache to indicate that the follow set is not yet calculated.
30    pub fn is_empty(&self) -> bool {
31        self.last_result.is_empty() && self.follow_set.is_empty()
32    }
33}
34
35/// Cache of FollowSets
36#[derive(Debug, Default)]
37pub struct FollowCache(pub [Rc<RefCell<CacheEntry>>; MAX_K + 1]);
38
39impl FirstCache {
40    /// Creates a new item
41    pub fn new() -> Self {
42        Self::default()
43    }
44
45    /// Utilizes the cache to get a FirstSet
46    pub fn get(&self, k: usize, grammar_config: &GrammarConfig) -> Rc<RefCell<FirstSet>> {
47        let exists = !self.0[k].borrow().is_empty();
48        if exists {
49            trace!("FirstCache::get: reusing first set for k={k}");
50            self.0[k].clone()
51        } else {
52            trace!("FirstCache::get: calculating first set for k={k}...");
53            let entry = first_k(grammar_config, k, self);
54            trace!(
55                "finished, k:{} prod: {}, nt: {}",
56                k,
57                entry.productions.len(),
58                entry.non_terminals.len()
59            );
60            *self.0[k].borrow_mut() = entry;
61            self.get(k, grammar_config)
62        }
63    }
64}
65
66impl FollowCache {
67    /// Creates a new item
68    pub fn new() -> Self {
69        Self::default()
70    }
71    /// Utilizes the cache to get a FollowSet
72    pub fn get(
73        &self,
74        k: usize,
75        grammar_config: &GrammarConfig,
76        first_cache: &FirstCache,
77    ) -> Rc<RefCell<CacheEntry>> {
78        let exists = !self.0[k].borrow().is_empty();
79        if exists {
80            trace!("FollowCache::get: reusing follow set for k={k}");
81            self.0[k].clone()
82        } else {
83            trace!("FollowCache::get: calculating follow set for k={k}...");
84            let (r, f) = follow_k(grammar_config, k, first_cache, self);
85            trace!(
86                "finished, k:{} res vec: {}, nt: {}",
87                k,
88                r.len(),
89                f.non_terminals.len()
90            );
91            *self.0[k].borrow_mut() = CacheEntry {
92                last_result: r,
93                follow_set: f,
94            };
95            self.get(k, grammar_config, first_cache)
96        }
97    }
98}
99
100///
101/// Calculates if for a certain non-terminal of grammar cfg the production to
102/// use can be determined deterministically with at maximum max_k lookahead.
103/// To accomplish this, for all productions of the given non-terminal k-tuples
104/// of at most length k are generated, starting with k=1.
105/// If all k-tuples are distinct between all productions the number k is
106/// returned. Otherwise the value of k is incremented by 1 and the process is
107/// retried.
108/// If k_max is exceeded the function returns an error.
109///
110pub fn decidable(
111    grammar_config: &GrammarConfig,
112    non_terminal: &str,
113    max_k: usize,
114    first_cache: &FirstCache,
115    follow_cache: &FollowCache,
116) -> Result<usize> {
117    let cfg = &grammar_config.cfg;
118    let productions = cfg.matching_productions(non_terminal);
119    if productions.is_empty() {
120        Err(anyhow!(
121            "The given non-terminal isn't part of the given grammar!"
122        ))
123    } else if productions.len() == 1 {
124        // The trivial case - no lookahead is needed.
125        Ok(0)
126    } else {
127        let nti = cfg.get_non_terminal_index_function();
128        let mut current_k = 1;
129        loop {
130            if current_k > max_k {
131                break;
132            }
133            let productions = cfg.matching_productions(non_terminal);
134            let k_tuples_of_productions = productions
135                .iter()
136                .map(|(pi, _)| {
137                    let k_tuples = first_cache
138                        .get(current_k, grammar_config)
139                        .borrow()
140                        .productions[*pi]
141                        .clone();
142                    (*pi, k_tuples)
143                })
144                .collect::<Vec<(ProductionIndex, KTuples)>>();
145
146            let cached = follow_cache.get(current_k, grammar_config, first_cache);
147            if let Some(follow_set) = cached
148                .borrow()
149                .follow_set
150                .non_terminals
151                .get(nti.non_terminal_index(non_terminal))
152            {
153                let concatenated_k_tuples = k_tuples_of_productions
154                    .iter()
155                    .map(|(i, t)| (*i, t.clone().k_concat(follow_set, current_k)))
156                    .collect::<Vec<(ProductionIndex, KTuples)>>();
157
158                if concatenated_k_tuples.iter().all(|(i, t1)| {
159                    concatenated_k_tuples
160                        .iter()
161                        .all(|(j, t2)| i == j || t1.is_disjoint(t2))
162                }) {
163                    return Ok(current_k);
164                }
165            } else {
166                bail!("Internal error");
167            }
168            current_k += 1;
169        }
170        bail!(GrammarAnalysisError::MaxKExceeded { max_k })
171    }
172}
173
174///
175/// Calculates maximum lookahead size where max_k is the limit.
176///
177pub fn calculate_k(
178    grammar_config: &GrammarConfig,
179    max_k: usize,
180    first_cache: &FirstCache,
181    follow_cache: &FollowCache,
182) -> Result<usize> {
183    let cfg = &grammar_config.cfg;
184    Ok(cfg
185        .get_non_terminal_set()
186        .iter()
187        .map(|n| decidable(grammar_config, n, max_k, first_cache, follow_cache).unwrap_or(max_k))
188        .fold(0, std::cmp::max))
189}
190
191///
192/// Calculates lookahead tuples for all productions, where max_k is the limit.
193///
194pub fn calculate_k_tuples(
195    grammar_config: &GrammarConfig,
196    max_k: usize,
197    first_cache: &FirstCache,
198    follow_cache: &FollowCache,
199) -> Result<BTreeMap<usize, KTuples>> {
200    let cfg = &grammar_config.cfg;
201    let nti = Rc::new(cfg.get_non_terminal_index_function());
202    cfg.get_non_terminal_set()
203        .iter()
204        .map(|n| {
205            (
206                n.clone(),
207                decidable(grammar_config, n, max_k, first_cache, follow_cache),
208            )
209        })
210        .try_fold(BTreeMap::new(), |acc, (nt, r)| {
211            r.and_then(|k| {
212                calculate_tuples_for_non_terminal(
213                    nt,
214                    k,
215                    grammar_config,
216                    first_cache,
217                    follow_cache,
218                    nti.clone(),
219                    acc,
220                )
221            })
222        })
223}
224
225fn calculate_tuples_for_non_terminal(
226    nt: String,
227    k: usize,
228    grammar_config: &GrammarConfig,
229    first_cache: &FirstCache,
230    follow_cache: &FollowCache,
231    nti: Rc<impl NonTerminalIndexFn>,
232    mut m: BTreeMap<usize, KTuples>,
233) -> std::result::Result<BTreeMap<usize, KTuples>, anyhow::Error> {
234    let productions = grammar_config.cfg.matching_productions(&nt);
235    let mut k_tuples = productions
236        .iter()
237        .fold(BTreeMap::new(), |mut acc, (pi, _)| {
238            let k_tuples = first_cache.get(k, grammar_config).borrow().productions[*pi].clone();
239            let cached = follow_cache.get(k, grammar_config, first_cache);
240            if let Some(follow_set) = cached
241                .borrow()
242                .follow_set
243                .non_terminals
244                .get(nti.non_terminal_index(&nt))
245            {
246                acc.insert(*pi, k_tuples.k_concat(follow_set, k));
247            }
248            acc
249        });
250    m.append(&mut k_tuples);
251    Ok(m)
252}
253
254// ---------------------------------------------------
255// Part of the Public API
256// *Changes will affect crate's version according to semver*
257// ---------------------------------------------------
258///
259/// Calculates lookahead DFAs for all non-terminals, where k is the limit.
260///
261pub fn calculate_lookahead_dfas(
262    grammar_config: &GrammarConfig,
263    max_k: usize,
264) -> Result<BTreeMap<String, LookaheadDFA>> {
265    let cfg = &grammar_config.cfg;
266
267    let first_cache = FirstCache::new();
268    let follow_cache = FollowCache::new();
269
270    let k_tuples_of_productions =
271        calculate_k_tuples(grammar_config, max_k, &first_cache, &follow_cache)?;
272    k_tuples_of_productions.iter().try_fold(
273        BTreeMap::<String, LookaheadDFA>::new(),
274        |mut acc, (i, t)| {
275            let nt = cfg[*i].get_n();
276            let dfa = LookaheadDFA::from_k_tuples(t, *i);
277            if let Some(found_dfa) = acc.remove(&nt) {
278                let united_dfa = found_dfa.unite(&dfa)?;
279                acc.insert(nt, united_dfa);
280            } else {
281                acc.insert(nt, dfa);
282            }
283            Ok(acc)
284        },
285    )
286}
287
288///
289/// Returns conflicts for a given non-terminal at given lookahead size.
290///
291pub fn explain_conflicts(
292    grammar_config: &GrammarConfig,
293    non_terminal: &str,
294    k: usize,
295    first_cache: &FirstCache,
296    follow_cache: &FollowCache,
297) -> Result<Vec<(ProductionIndex, KTuples, ProductionIndex, KTuples)>> {
298    let cfg = &grammar_config.cfg;
299    let productions = cfg.matching_productions(non_terminal);
300    if productions.is_empty() {
301        Err(anyhow!(
302            "The given non-terminal isn't part of the given grammar!"
303        ))
304    } else if productions.len() == 1 {
305        // The trivial case - no lookahead is needed, no conflicts can occur.
306        Ok(Vec::new())
307    } else {
308        let nti = cfg.get_non_terminal_index_function();
309        let productions = cfg.matching_productions(non_terminal);
310        let k_tuples_of_productions = productions
311            .iter()
312            .map(|(pi, _)| {
313                let k_tuples = first_cache.get(k, grammar_config).borrow().productions[*pi].clone();
314                (*pi, k_tuples)
315            })
316            .collect::<Vec<(ProductionIndex, KTuples)>>();
317
318        let cached = follow_cache.get(k, grammar_config, first_cache);
319        if let Some(follow_set) = cached
320            .borrow()
321            .follow_set
322            .non_terminals
323            .get(nti.non_terminal_index(non_terminal))
324        {
325            let concatenated_k_tuples = k_tuples_of_productions
326                .iter()
327                .map(|(i, t)| (*i, t.clone().k_concat(follow_set, k)))
328                .collect::<Vec<(ProductionIndex, KTuples)>>();
329            let mut conflicting_k_tuples = Vec::new();
330            for (i, ki) in &concatenated_k_tuples {
331                for (j, kj) in &concatenated_k_tuples {
332                    if i != j
333                        && !ki.is_disjoint(kj)
334                        && !conflicting_k_tuples
335                            .iter()
336                            .any(|(p1, _, p2, _)| p1 != i && p2 != j)
337                    {
338                        conflicting_k_tuples.push((*i, ki.clone(), *j, kj.clone()));
339                    }
340                }
341            }
342            return Ok(conflicting_k_tuples);
343        }
344        Err(anyhow!("Internal error"))
345    }
346}
347
348#[cfg(test)]
349mod test {
350    use super::{FirstCache, FollowCache, calculate_k, decidable};
351    use crate::grammar::SymbolAttribute;
352    use crate::{Cfg, GrammarConfig, Pr, Symbol, Terminal, TerminalKind};
353
354    macro_rules! terminal {
355        ($term:literal) => {
356            Symbol::T(Terminal::Trm(
357                $term.to_string(),
358                TerminalKind::Legacy,
359                vec![0],
360                SymbolAttribute::None,
361                None,
362                None,
363                None,
364            ))
365        };
366    }
367
368    #[test]
369    fn check_decidable() {
370        let cfg = Cfg::with_start_symbol("S")
371            .add_pr(Pr::new("S", vec![terminal!("a"), Symbol::n("X")]))
372            .add_pr(Pr::new("X", vec![terminal!("b"), Symbol::n("S")]))
373            .add_pr(Pr::new(
374                "X",
375                vec![
376                    terminal!("a"),
377                    Symbol::n("Y"),
378                    terminal!("b"),
379                    Symbol::n("Y"),
380                ],
381            ))
382            .add_pr(Pr::new("Y", vec![terminal!("b"), terminal!("a")]))
383            .add_pr(Pr::new("Y", vec![terminal!("a"), Symbol::n("Z")]))
384            .add_pr(Pr::new(
385                "Z",
386                vec![terminal!("a"), Symbol::n("Z"), Symbol::n("X")],
387            ));
388        let grammar_config = GrammarConfig::new(cfg, 5);
389        let first_cache = FirstCache::new();
390        let follow_cache = FollowCache::new();
391        let result = decidable(&grammar_config, "S", 5, &first_cache, &follow_cache).unwrap();
392        assert_eq!(0, result);
393        let result = decidable(&grammar_config, "X", 5, &first_cache, &follow_cache).unwrap();
394        assert_eq!(1, result);
395        let result = decidable(&grammar_config, "Y", 5, &first_cache, &follow_cache).unwrap();
396        assert_eq!(1, result);
397        let result = decidable(&grammar_config, "Z", 5, &first_cache, &follow_cache).unwrap();
398        assert_eq!(0, result);
399        assert_eq!(
400            "The given non-terminal isn't part of the given grammar!",
401            decidable(&grammar_config, "A", 5, &first_cache, &follow_cache)
402                .err()
403                .unwrap()
404                .to_string()
405        );
406    }
407
408    #[test]
409    fn check_calculate_k() {
410        let cfg = Cfg::with_start_symbol("S")
411            .add_pr(Pr::new("S", vec![terminal!("a"), Symbol::n("X")]))
412            .add_pr(Pr::new("X", vec![terminal!("b"), Symbol::n("S")]))
413            .add_pr(Pr::new(
414                "X",
415                vec![
416                    terminal!("a"),
417                    Symbol::n("Y"),
418                    terminal!("b"),
419                    Symbol::n("Y"),
420                ],
421            ))
422            .add_pr(Pr::new("Y", vec![terminal!("b"), terminal!("a")]))
423            .add_pr(Pr::new("Y", vec![terminal!("a"), Symbol::n("Z")]))
424            .add_pr(Pr::new(
425                "Z",
426                vec![terminal!("a"), Symbol::n("Z"), Symbol::n("X")],
427            ));
428        let grammar_config = GrammarConfig::new(cfg, 5);
429        let first_cache = FirstCache::new();
430        let follow_cache = FollowCache::new();
431        let result = calculate_k(&grammar_config, 5, &first_cache, &follow_cache).unwrap();
432        assert_eq!(1, result);
433    }
434}
parol/analysis/k_decision.rs

parol/analysis/
k_decision.rs
