compiler_course_helper/grammar/
grammar.rs

1use std::collections::{HashMap, HashSet};
2
3#[derive(Debug, Clone)]
4pub struct NonTerminal {
5    pub index: usize,
6    pub name: String,
7    pub first: HashSet<usize>,
8    pub follow: HashSet<usize>,
9    pub nullable: bool,
10    pub productions: Vec<Vec<usize>>,
11}
12
13impl NonTerminal {
14    pub fn new(index: usize, name: String) -> Self {
15        Self {
16            index,
17            name,
18            first: HashSet::new(),
19            follow: HashSet::new(),
20            nullable: false,
21            productions: Vec::new(),
22        }
23    }
24}
25
26#[derive(Debug, Clone)]
27pub enum Symbol {
28    NonTerminal(NonTerminal),
29    Terminal(String),
30}
31
32impl Symbol {
33    pub fn non_terminal(&self) -> Option<&NonTerminal> {
34        match self {
35            Symbol::NonTerminal(e) => Some(e),
36            Symbol::Terminal(_) => None,
37        }
38    }
39
40    pub fn mut_non_terminal(&mut self) -> Option<&mut NonTerminal> {
41        match self {
42            Symbol::NonTerminal(e) => Some(e),
43            Symbol::Terminal(_) => None,
44        }
45    }
46}
47
48#[derive(Debug, Clone)]
49pub struct Grammar {
50    valid_nullable_first_follow: bool,
51    pub symbols: Vec<Symbol>,
52    pub symbol_table: HashMap<String, usize>,
53    pub start_symbol: Option<usize>,
54}
55
56impl Grammar {
57    pub fn new() -> Self {
58        let mut g = Self {
59            valid_nullable_first_follow: false,
60            symbols: Vec::new(),
61            symbol_table: HashMap::new(),
62            start_symbol: None,
63        };
64
65        let e_idx = g.add_non_terminal(super::EPSILON);
66        g.symbols[e_idx].mut_non_terminal().unwrap().nullable = true;
67        g.symbol_table.insert("ε".to_string(), e_idx);
68
69        g.add_terminal(super::END_MARK.to_string());
70
71        g
72    }
73
74    pub fn get_symbol_by_name(&self, name: &str) -> &Symbol {
75        &self.symbols[self.symbol_table[name]]
76    }
77
78    pub fn terminal_iter(&self) -> impl Iterator<Item = &String> {
79        self.symbols.iter().filter_map(|s| {
80            if let Symbol::Terminal(name) = s {
81                Some(name)
82            } else {
83                None
84            }
85        })
86    }
87
88    pub fn non_terminal_iter(&self) -> impl Iterator<Item = &NonTerminal> {
89        self.symbols.iter().filter_map(|s| s.non_terminal()).skip(1)
90    }
91
92    pub fn non_terminal_iter_mut(&mut self) -> impl Iterator<Item = &mut NonTerminal> {
93        self.symbols
94            .iter_mut()
95            .filter_map(|s| s.mut_non_terminal())
96            .skip(1)
97    }
98
99    pub fn get_symbol_index(&self, name: &str) -> Option<usize> {
100        self.symbol_table.get(name).cloned()
101    }
102
103    pub fn add_non_terminal(&mut self, name: &str) -> usize {
104        let idx = self.symbols.len();
105        self.symbols
106            .push(Symbol::NonTerminal(NonTerminal::new(idx, name.to_string())));
107        self.symbol_table.insert(name.to_string(), idx);
108        idx
109    }
110
111    pub fn add_terminal(&mut self, name: String) -> usize {
112        let idx = self.symbols.len();
113        self.symbols.push(Symbol::Terminal(name.clone()));
114        self.symbol_table.insert(name, idx);
115        idx
116    }
117
118    pub fn add_production(&mut self, left: usize, right: Vec<usize>) {
119        self.symbols[left]
120            .mut_non_terminal()
121            .unwrap()
122            .productions
123            .push(right);
124    }
125
126    pub fn get_symbol_name(&self, index: usize) -> &str {
127        match &self.symbols[index] {
128            Symbol::NonTerminal(e) => e.name.as_str(),
129            Symbol::Terminal(e) => e.as_str(),
130        }
131    }
132
133    pub fn get_symbol_prime_name(&self, mut name: String) -> String {
134        while self.symbol_table.contains_key(&name) {
135            name.push('\'');
136        }
137        name
138    }
139
140    pub fn invalidate_nullable_first_follow(&mut self) {
141        self.valid_nullable_first_follow = false;
142        self.reset_nullable_first_follow();
143    }
144
145    pub fn is_nullable_first_follow_valid(&self) -> bool {
146        self.valid_nullable_first_follow
147    }
148
149    pub fn validate_nullable_first_follow(&mut self) {
150        self.valid_nullable_first_follow = true;
151    }
152
153    pub fn production_to_vec_str(&self, production: &Vec<usize>) -> Vec<&str> {
154        production
155            .iter()
156            .map(|idx| self.get_symbol_name(*idx))
157            .collect()
158    }
159}
compiler_course_helper/grammar/grammar.rs

compiler_course_helper/grammar/
grammar.rs
