metrale_grammar/grammar/functor/
mod.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// Grammar functor passes — port wave W3.
4//
5// Pure-Rust port of `cpp/grammar_functor.{h,cc}`: the normalization,
6// optimization, analysis and FSM-construction passes that turn a parsed
7// BNF AST into an optimized, FSM-accelerated grammar.
8//
9// The C++ uses a CRTP visitor (`GrammarFunctor` / `GrammarMutator`);
10// here that is a `GrammarMutator` trait with default visit methods, and
11// each concrete pass is its own struct.
12//
13// Module map:
14//   mutator              — GrammarMutator trait + shared state
15//   normalizer           — SingleElementExprEliminator, RootRuleRenamer,
16//                          GrammarNormalizer
17//   structure_normalizer — StructureNormalizer
18//   analyzer             — UsedRulesAnalyzer, RuleRefGraphFinder,
19//                          AllowEmptyRuleAnalyzer
20//   lookahead            — LookaheadAssertionAnalyzer
21//   optimizer            — ByteStringFuser, RuleInliner,
22//                          DeadCodeEliminator, RepetitionNormalizer,
23//                          GrammarOptimizer
24//   char_range           — UTF-8 character-range FSM helpers
25//   fsm_builder          — GrammarFsmBuilder (per-rule FSM construction)
26//   tag_dispatch_fsm     — TagDispatch FSM construction
27//   hash_walk            — per-FSM BFS structural hashing
28//   fsm_hasher           — GrammarFsmHasher
29//   constructor          — SubGrammarAdder, GrammarUnion, GrammarConcat
30
31pub mod analyzer;
32pub mod char_range;
33pub mod constructor;
34pub mod fsm_builder;
35pub mod fsm_hasher;
36pub mod hash_walk;
37pub mod lookahead;
38pub mod mutator;
39pub mod normalizer;
40pub mod optimizer;
41pub mod structure_normalizer;
42pub mod tag_dispatch_fsm;
43
44pub use analyzer::{AllowEmptyRuleAnalyzer, RuleRefGraphFinder, UsedRulesAnalyzer};
45pub use constructor::{GrammarConcat, GrammarUnion, add_sub_grammar};
46pub use fsm_builder::GrammarFsmBuilder;
47pub use fsm_hasher::{GrammarFsmHasher, hash_sequence};
48pub use lookahead::LookaheadAssertionAnalyzer;
49pub use mutator::{GrammarMutator, MutatorState};
50pub use normalizer::{GrammarNormalizer, RootRuleRenamer, SingleElementExprEliminator};
51pub use optimizer::{
52    ByteStringFuser, DeadCodeEliminator, GrammarOptimizer, RepetitionNormalizer, RuleInliner,
53};
54pub use structure_normalizer::StructureNormalizer;
55
56#[cfg(test)]
57mod integration_tests {
58    //! End-to-end pipeline tests: parse -> normalize -> optimize.
59    use crate::grammar::functor::{GrammarNormalizer, GrammarOptimizer};
60    use crate::grammar::parse_ebnf_default;
61    use crate::grammar::printer::print_grammar;
62
63    #[test]
64    fn full_pipeline_byte_string() {
65        let g = parse_ebnf_default("root ::= \"hello world\"\n").unwrap();
66        let norm = GrammarNormalizer::apply(g);
67        let opt = GrammarOptimizer::apply(norm);
68        assert!(opt.optimized);
69        let fsm = opt.per_rule_fsms[opt.root_rule_id() as usize]
70            .as_ref()
71            .unwrap();
72        assert!(fsm.accept_string(b"hello world"));
73    }
74
75    #[test]
76    fn full_pipeline_recursive_grammar() {
77        let ebnf = "root ::= \"(\" root \")\" | \"\"\n";
78        let g = parse_ebnf_default(ebnf).unwrap();
79        let norm = GrammarNormalizer::apply(g);
80        let opt = GrammarOptimizer::apply(norm);
81        assert!(opt.optimized);
82        assert!(!opt.allow_empty_rule_ids.is_empty());
83    }
84
85    #[test]
86    fn full_pipeline_alternation() {
87        let g = parse_ebnf_default("root ::= \"yes\" | \"no\"\n").unwrap();
88        let norm = GrammarNormalizer::apply(g);
89        let opt = GrammarOptimizer::apply(norm);
90        let fsm = opt.per_rule_fsms[opt.root_rule_id() as usize]
91            .as_ref()
92            .unwrap();
93        assert!(fsm.accept_string(b"yes"));
94        assert!(fsm.accept_string(b"no"));
95        assert!(!fsm.accept_string(b"maybe"));
96    }
97
98    #[test]
99    fn normalize_then_print_is_stable() {
100        let g = parse_ebnf_default("root ::= \"a\" sub\nsub ::= \"b\" | \"c\"\n").unwrap();
101        let norm = GrammarNormalizer::apply(g);
102        let printed = print_grammar(&norm);
103        assert!(printed.contains("root ::="));
104        assert!(printed.contains("sub ::="));
105    }
106
107    #[test]
108    fn optimizer_idempotent_on_optimized_grammar() {
109        let g = parse_ebnf_default("root ::= \"x\" \"y\"\n").unwrap();
110        let norm = GrammarNormalizer::apply(g);
111        let opt1 = GrammarOptimizer::apply(norm);
112        let opt2 = GrammarOptimizer::apply(opt1.clone());
113        assert_eq!(print_grammar(&opt1), print_grammar(&opt2));
114    }
115}
metrale_grammar/grammar/functor/mod.rs

metrale_grammar/grammar/functor/
mod.rs
