grammar_utils/ll1/
table.rs

1use std::collections::BTreeMap;
2
3use crate::*;
4
5pub struct ParseTable<'g> {
6    grammar: &'g Grammar,
7    start_symbol: Symbol<'g>,
8    table: BTreeMap<(Symbol<'g>, Option<Symbol<'g>>), Vec<Rule<'g>>>,
9}
10
11impl<'g> ParseTable<'g> {
12    pub fn build(grammar: &'g Grammar, start_symbol: Symbol<'g>) -> ParseTable<'g> {
13        ParseTable {
14            grammar,
15            start_symbol,
16            table: Self::build_table(grammar, start_symbol),
17        }
18    }
19
20    pub fn grammar(&self) -> &'g Grammar {
21        self.grammar
22    }
23
24    pub fn start_symbol(&self) -> Symbol<'g> {
25        self.start_symbol
26    }
27
28    fn build_table(grammar: &'g Grammar, start_symbol: Symbol<'g>)
29        -> BTreeMap<(Symbol<'g>, Option<Symbol<'g>>), Vec<Rule<'g>>> {
30
31        let analysis = GrammarAnalysis::build(grammar);
32        let mut map = BTreeMap::new();
33
34        let rules = grammar.rules();
35
36        for rule in rules.iter().copied() {
37            let rhs = rule.rhs();
38            if analysis.is_nullable_seq(&rhs) {
39                for follow in analysis.follow(rule.lhs()) {
40                    let key = (rule.lhs(), Some(follow));
41                    if !map.contains_key(&key) {
42                        map.insert(key, vec![]);
43                    }
44                    map.get_mut(&key).unwrap().push(rule);
45                }
46
47                if analysis.can_end_with(start_symbol, rule.lhs()) {
48                    let key = (rule.lhs(), None);
49                    if !map.contains_key(&key) {
50                        map.insert(key, vec![]);
51                    }
52                    map.get_mut(&key).unwrap().push(rule);
53                }
54            } else {
55                for first in analysis.first_seq(&rhs) {
56                    let key = (rule.lhs(), Some(first));
57                    if !map.contains_key(&key) {
58                        map.insert(key, vec![]);
59                    }
60                    map.get_mut(&key).unwrap().push(rule);
61                }
62            }
63        }
64
65        map
66    }
67
68    pub fn get(&self, state: Symbol<'g>, input: Option<Symbol<'g>>) -> Vec<Rule<'g>> {
69        self.table.get(&(state, input)).map(|v| v.as_slice()).unwrap_or_else(|| &[]).to_vec()
70    }
71}
72
73impl<'g> std::fmt::Debug for ParseTable<'g> {
74    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
75        for nonterminal in self.grammar.nonterminals() {
76            writeln!(f, "{nonterminal:?}")?;
77            for terminal in self.grammar.terminals() {
78                let entry = &self.get(nonterminal, Some(terminal));
79                if entry.len() > 0 {
80                    writeln!(f, "    {terminal:?}\t{entry:?}")?;
81                }
82            }
83
84            let entry = &self.get(nonterminal, None);
85            if entry.len() > 0 {
86                writeln!(f, "    EOF\t{entry:?}")?;
87            }
88        }
89        Ok(())
90    }
91}
grammar_utils/ll1/table.rs

grammar_utils/ll1/
table.rs
