meta_language/grammar/inference/
lexical.rs

1//! Lexical class inference for positive example corpora.
2
3use std::collections::{BTreeMap, BTreeSet};
4use std::fmt::Write as _;
5
6use crate::grammar::{CharClassItem, GrammarExpr, GrammarRule, RuleKind};
7use crate::source::ByteRange;
8
9/// Coarse Unicode-aware character category used for token segmentation.
10#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
11pub enum CharCategory {
12    /// Alphabetic character.
13    Letter,
14    /// Numeric character.
15    Digit,
16    /// Whitespace character.
17    Whitespace,
18    /// Meta-notation skeleton delimiter kept as an atomic token.
19    Delimiter,
20    /// Other ASCII punctuation or symbol character.
21    Punctuation,
22    /// Any character outside the coarse lexical categories.
23    Other,
24}
25
26/// Categorises one character into a coarse lexical class.
27#[must_use]
28pub fn categorise(value: char) -> CharCategory {
29    if value.is_whitespace() {
30        CharCategory::Whitespace
31    } else if is_delimiter(value) {
32        CharCategory::Delimiter
33    } else if value.is_alphabetic() {
34        CharCategory::Letter
35    } else if value.is_numeric() {
36        CharCategory::Digit
37    } else if value.is_ascii_punctuation() {
38        CharCategory::Punctuation
39    } else {
40        CharCategory::Other
41    }
42}
43
44/// One lossless token produced by lexical segmentation.
45#[derive(Clone, Debug, PartialEq, Eq)]
46pub struct Token {
47    /// Token source text.
48    pub text: String,
49    /// Coarse category that drove segmentation.
50    pub category: CharCategory,
51    /// Half-open byte span in the original text.
52    pub span: ByteRange,
53}
54
55/// Configuration for lexical class inference.
56#[derive(Clone, Copy, Debug, PartialEq, Eq)]
57pub struct LexicalConfig {
58    /// Maximum number of distinct forms that can remain a closed literal class.
59    pub max_closed_forms: usize,
60}
61
62impl Default for LexicalConfig {
63    fn default() -> Self {
64        Self {
65            max_closed_forms: 12,
66        }
67    }
68}
69
70/// Deterministic lexical model inferred from a positive corpus.
71#[derive(Clone, Debug, PartialEq, Eq)]
72pub struct LexicalModel {
73    /// Distinct characters observed in the training corpus, sorted by scalar value.
74    pub alphabet: Vec<char>,
75    /// Inferred token-level rules lowered to the grammar IR.
76    pub classes: Vec<GrammarRule>,
77    /// Configuration used to infer this model.
78    pub config: LexicalConfig,
79}
80
81impl LexicalModel {
82    /// Re-tokenises text with the same category-driven segmentation policy.
83    #[must_use]
84    pub fn tokenize(&self, text: &str) -> Vec<Token> {
85        tokenize_text(text, self.config)
86    }
87}
88
89/// Infers a lexical model from positive example texts.
90#[must_use]
91pub fn infer_lexical_classes(corpus: &[&str], config: &LexicalConfig) -> LexicalModel {
92    let mut alphabet = BTreeSet::new();
93    let mut forms_by_category = BTreeMap::<CharCategory, BTreeMap<String, usize>>::new();
94
95    for text in corpus {
96        alphabet.extend(text.chars());
97
98        for token in tokenize_text(text, *config) {
99            *forms_by_category
100                .entry(token.category)
101                .or_default()
102                .entry(token.text)
103                .or_default() += 1;
104        }
105    }
106
107    LexicalModel {
108        alphabet: alphabet.into_iter().collect(),
109        classes: infer_classes(&forms_by_category, *config),
110        config: *config,
111    }
112}
113
114fn tokenize_text(text: &str, _config: LexicalConfig) -> Vec<Token> {
115    let mut tokens = Vec::new();
116    let mut token_start = 0;
117    let mut token_end = 0;
118    let mut token_category = None;
119
120    for (index, value) in text.char_indices() {
121        let category = categorise(value);
122        let value_end = index + value.len_utf8();
123
124        let Some(current_category) = token_category else {
125            token_start = index;
126            token_end = value_end;
127            token_category = Some(category);
128            continue;
129        };
130
131        if continues_token(current_category, category) {
132            token_end = value_end;
133        } else {
134            tokens.push(Token {
135                text: text[token_start..token_end].to_string(),
136                category: current_category,
137                span: ByteRange::new(token_start, token_end),
138            });
139            token_start = index;
140            token_end = value_end;
141            token_category = Some(category);
142        }
143    }
144
145    if let Some(category) = token_category {
146        tokens.push(Token {
147            text: text[token_start..token_end].to_string(),
148            category,
149            span: ByteRange::new(token_start, token_end),
150        });
151    }
152
153    tokens
154}
155
156fn continues_token(current: CharCategory, next: CharCategory) -> bool {
157    if is_atomic(current) || is_atomic(next) {
158        return false;
159    }
160
161    current == next || (current == CharCategory::Letter && next == CharCategory::Digit)
162}
163
164const fn is_atomic(category: CharCategory) -> bool {
165    matches!(
166        category,
167        CharCategory::Delimiter | CharCategory::Punctuation
168    )
169}
170
171const fn is_delimiter(value: char) -> bool {
172    matches!(value, '(' | ')' | '[' | ']' | '{' | '}' | '\'' | '"' | '`')
173}
174
175fn infer_classes(
176    forms_by_category: &BTreeMap<CharCategory, BTreeMap<String, usize>>,
177    config: LexicalConfig,
178) -> Vec<GrammarRule> {
179    let mut classes = Vec::new();
180
181    for (category, forms) in forms_by_category {
182        match category {
183            CharCategory::Delimiter | CharCategory::Punctuation => {
184                classes.extend(forms.keys().map(|form| literal_rule(form)));
185            }
186            CharCategory::Digit | CharCategory::Whitespace => {
187                classes.push(open_rule(*category, forms.keys().map(String::as_str)));
188            }
189            CharCategory::Letter | CharCategory::Other => {
190                classes.extend(infer_mixed_category(*category, forms, config));
191            }
192        }
193    }
194
195    classes
196}
197
198fn infer_mixed_category(
199    category: CharCategory,
200    forms: &BTreeMap<String, usize>,
201    config: LexicalConfig,
202) -> Vec<GrammarRule> {
203    let has_repeated_forms = forms.values().any(|count| *count > 1);
204    let has_singleton_forms = forms.values().any(|count| *count == 1);
205
206    if forms.len() <= config.max_closed_forms && !(has_repeated_forms && has_singleton_forms) {
207        return forms.keys().map(|form| literal_rule(form)).collect();
208    }
209
210    let mut rules = Vec::new();
211    let mut open_forms = Vec::new();
212    let mut closed_forms = 0;
213
214    for (form, count) in forms {
215        if *count > 1 && closed_forms < config.max_closed_forms {
216            rules.push(literal_rule(form));
217            closed_forms += 1;
218        } else {
219            open_forms.push(form.as_str());
220        }
221    }
222
223    if !open_forms.is_empty() {
224        rules.push(open_rule(category, open_forms));
225    }
226
227    rules
228}
229
230fn literal_rule(form: &str) -> GrammarRule {
231    GrammarRule::new(literal_rule_name(form), GrammarExpr::terminal(form))
232        .with_kind(RuleKind::Token)
233}
234
235fn literal_rule_name(form: &str) -> String {
236    let mut name = String::from("literal");
237
238    for value in form.chars() {
239        name.push('_');
240        if value.is_ascii_alphanumeric() {
241            name.push(value.to_ascii_lowercase());
242        } else {
243            name.push('u');
244            write!(name, "{:04x}", u32::from(value)).expect("writing to a String cannot fail");
245        }
246    }
247
248    name
249}
250
251fn open_rule<'a>(category: CharCategory, forms: impl IntoIterator<Item = &'a str>) -> GrammarRule {
252    GrammarRule::new(open_rule_name(category), open_expr(category, forms))
253        .with_kind(RuleKind::Token)
254}
255
256const fn open_rule_name(category: CharCategory) -> &'static str {
257    match category {
258        CharCategory::Letter => "identifier",
259        CharCategory::Digit => "integer",
260        CharCategory::Whitespace => "whitespace",
261        CharCategory::Delimiter => "delimiter",
262        CharCategory::Punctuation => "punctuation",
263        CharCategory::Other => "other",
264    }
265}
266
267fn open_expr<'a>(category: CharCategory, forms: impl IntoIterator<Item = &'a str>) -> GrammarExpr {
268    let forms = forms.into_iter().collect::<Vec<_>>();
269
270    match category {
271        CharCategory::Letter => identifier_expr(&forms),
272        CharCategory::Digit if all_ascii_digits(&forms) => {
273            GrammarExpr::one_or_more(GrammarExpr::char_range('0', '9'))
274        }
275        CharCategory::Digit | CharCategory::Whitespace | CharCategory::Other => {
276            GrammarExpr::one_or_more(char_set_expr(&all_chars(&forms)))
277        }
278        CharCategory::Delimiter | CharCategory::Punctuation => {
279            GrammarExpr::choice(false, forms.into_iter().map(GrammarExpr::terminal))
280        }
281    }
282}
283
284fn identifier_expr(forms: &[&str]) -> GrammarExpr {
285    let mut first_chars = BTreeSet::new();
286    let mut rest_chars = BTreeSet::new();
287
288    for form in forms {
289        let mut chars = form.chars();
290        if let Some(first) = chars.next() {
291            first_chars.insert(first);
292            rest_chars.extend(chars);
293        }
294    }
295
296    let first = char_set_expr(&first_chars);
297    if rest_chars.is_empty() {
298        first
299    } else {
300        GrammarExpr::sequence([first, GrammarExpr::zero_or_more(char_set_expr(&rest_chars))])
301    }
302}
303
304fn all_ascii_digits(forms: &[&str]) -> bool {
305    forms
306        .iter()
307        .flat_map(|form| form.chars())
308        .all(|value| value.is_ascii_digit())
309}
310
311fn all_chars(forms: &[&str]) -> BTreeSet<char> {
312    forms.iter().flat_map(|form| form.chars()).collect()
313}
314
315fn char_set_expr(chars: &BTreeSet<char>) -> GrammarExpr {
316    GrammarExpr::char_class(false, char_class_items(chars))
317}
318
319fn char_class_items(chars: &BTreeSet<char>) -> Vec<CharClassItem> {
320    let mut items = Vec::new();
321    let mut chars = chars.iter().copied();
322    let Some(mut range_start) = chars.next() else {
323        return items;
324    };
325    let mut range_end = range_start;
326
327    for value in chars {
328        if u32::from(value) != u32::from(range_end).saturating_add(1) {
329            push_char_class_item(&mut items, range_start, range_end);
330            range_start = value;
331        }
332        range_end = value;
333    }
334
335    push_char_class_item(&mut items, range_start, range_end);
336    items
337}
338
339fn push_char_class_item(items: &mut Vec<CharClassItem>, start: char, end: char) {
340    if start == end {
341        items.push(CharClassItem::char(start));
342    } else {
343        items.push(CharClassItem::range(start, end));
344    }
345}
meta_language/grammar/inference/lexical.rs

meta_language/grammar/inference/
lexical.rs
