parol/analysis/
left_recursion.rs

1use crate::Cfg;
2use std::collections::{BTreeMap, HashSet};
3
4// ---------------------------------------------------
5// Part of the Public API
6// *Changes will affect crate's version according to semver*
7// ---------------------------------------------------
8///
9/// Detects left recursions.
10/// The result is a collection of vectors of non-terminal names that contain recursions.
11///
12pub fn detect_left_recursive_non_terminals(cfg: &Cfg) -> Vec<String> {
13    let nullables = cfg.calculate_nullable_non_terminals();
14    let mut can_start_with = cfg
15        .get_non_terminal_set()
16        .iter()
17        .map(|nt| (nt.clone(), HashSet::<String>::new()))
18        .collect::<BTreeMap<String, HashSet<String>>>();
19
20    // For all non-terminals A, B calculate the relation 'A can-start-with B'
21    let mut changed = true;
22    while changed {
23        changed = false;
24        for p in &cfg.pr {
25            let lhs = p.0.get_n_ref().unwrap();
26            let lhs_entry = can_start_with.get_mut(lhs).unwrap();
27            for s in &p.1 {
28                match s {
29                    crate::Symbol::N(n, _, _, _) => {
30                        changed |= lhs_entry.insert(n.clone());
31                        if !nullables.contains(n) {
32                            break;
33                        }
34                    }
35                    crate::Symbol::T(_) => break,
36                    crate::Symbol::S(_) | crate::Symbol::Push(_) | crate::Symbol::Pop => (),
37                }
38            }
39        }
40    }
41
42    // Calculate transitive closure of the relation 'A can-start-with B'
43    // Ex.: A->B, B->C => A->{B, C}
44    changed = true;
45    while changed {
46        changed = false;
47        for nt in can_start_with
48            .keys()
49            .cloned()
50            .collect::<Vec<String>>()
51            .iter()
52        {
53            let v = can_start_with
54                .get(nt)
55                .map_or(HashSet::default(), |s| s.clone());
56            for e in &v {
57                let t = can_start_with
58                    .get(e)
59                    .map_or(HashSet::default(), |s| s.clone());
60                if let Some(f) = can_start_with.get_mut(nt) {
61                    f.extend(t.iter().cloned())
62                }
63            }
64            changed |= v.len() < can_start_with.get(nt).map_or(0, |v| v.len());
65        }
66    }
67
68    // Return all non-terminals that have themselves in the 'can-start-with relation'
69    can_start_with.iter().fold(Vec::new(), |mut acc, (k, v)| {
70        if v.contains(k) {
71            acc.push(k.to_owned());
72        }
73        acc
74    })
75}
76
77#[cfg(test)]
78mod test {
79    use crate::obtain_grammar_config_from_string;
80
81    use super::detect_left_recursive_non_terminals;
82
83    #[derive(Debug)]
84    struct TestData {
85        input: &'static str,
86        recursive_non_terminals: &'static [&'static str],
87    }
88
89    const LL_TESTS: &[TestData] = &[
90        TestData {
91            input: r#"%start A %% A: B "r"; B: C "d"; C: A "t";"#,
92            recursive_non_terminals: &["A", "B", "C"],
93        },
94        TestData {
95            input: r#"%start S %% S: S "a"; S: ;"#,
96            recursive_non_terminals: &["S"],
97        },
98        TestData {
99            input: r#"%start A %% A: A B "d"; A: A "a"; A: "a"; B: B "e"; B: "b";"#,
100            recursive_non_terminals: &["A", "B"],
101        },
102        TestData {
103            input: r#"%start E %% E: E "+" E; E: E "*" E; E: "a";"#,
104            recursive_non_terminals: &["E"],
105        },
106        TestData {
107            input: r#"%start E %% E: E "+" T; E: T; T: T "*" F; T: F; F: "id";"#,
108            recursive_non_terminals: &["E", "T"],
109        },
110        TestData {
111            input: r#"%start S %% S: "(" L ")"; S: "a"; L: L "," S; L: S;"#,
112            recursive_non_terminals: &["L"],
113        },
114        TestData {
115            input: r#"%start S %% S: S "0" S "1" S; S: "0" "1";"#,
116            recursive_non_terminals: &["S"],
117        },
118        TestData {
119            input: r#"%start S %% S: A; A: A "d"; A: A "e"; A: "a" B; A: "a" "c"; B: "b" B "c"; B: "f";"#,
120            recursive_non_terminals: &["A"],
121        },
122        TestData {
123            input: r#"%start A %% A: A A "a"; A: "b";"#,
124            recursive_non_terminals: &["A"],
125        },
126        TestData {
127            input: r#"%start A %% A: B "a"; A: A "a"; A: "c"; B: B "b"; B: A "b"; B: "d";"#,
128            recursive_non_terminals: &["A", "B"],
129        },
130        TestData {
131            input: r#"%start X %% X: X S "b"; X: S "a"; X: "b"; S: S "b"; S: X "a"; S: "a";"#,
132            recursive_non_terminals: &["S", "X"],
133        },
134        TestData {
135            input: r#"%start S %% S: A "a"; S: "b"; A: A "c"; A: S "d"; A: ;"#,
136            recursive_non_terminals: &["A", "S"],
137        },
138    ];
139
140    #[test]
141    fn check_detect_left_recursive_non_terminals() {
142        for (i, test) in LL_TESTS.iter().enumerate() {
143            let grammar_config = obtain_grammar_config_from_string(test.input, false).unwrap();
144            let recursions = detect_left_recursive_non_terminals(&grammar_config.cfg);
145            assert_eq!(
146                test.recursive_non_terminals, recursions,
147                "Error at test #{i}"
148            );
149        }
150    }
151}
parol/analysis/left_recursion.rs

parol/analysis/
left_recursion.rs
