meta_language/grammar/
mod.rs

1//! Grammar intermediate representation and links encoding.
2//!
3//! The grammar IR is a small expression algebra that can hold PEG, BNF, EBNF,
4//! ABNF, and inferred grammars without committing to one textual surface
5//! syntax. Values can be encoded as first-class grammar links in a
6//! [`LinkNetwork`](crate::LinkNetwork).
7//!
8//! # Example
9//!
10//! ```
11//! use meta_language::{
12//!     FromLinks, Grammar, LinkType, LinksDecoder, LinksEncoder, ToLinks,
13//! };
14//!
15//! let expr = Grammar::expr();
16//! let grammar = Grammar::builder().start("word").rule("word", expr.rep1(expr.char_range('a', 'z'))).build();
17//!
18//! let mut encoder = LinksEncoder::new();
19//! let root = grammar.to_links(&mut encoder);
20//! let network = encoder.into_network();
21//! assert!(network.links().any(|link| link.metadata().link_type() == Some(LinkType::Grammar)));
22//! let mut decoder = LinksDecoder::new(&network);
23//! assert_eq!(Grammar::from_links(&mut decoder, root).expect("grammar decodes"), grammar);
24//! ```
25
26mod builder;
27pub mod concepts;
28pub mod decorators;
29pub mod emit;
30pub mod feature;
31pub mod feature_runtime;
32pub mod fidelity;
33pub mod import;
34pub mod inference;
35pub mod interchange;
36mod links;
37pub mod merge;
38mod metadata;
39pub mod reverse;
40pub mod round_trip;
41pub mod runtime;
42pub mod surface;
43pub mod translate;
44pub mod validate;
45
46pub use builder::{
47    ExprBuilder, GrammarBuilder, RepetitionBoundsError, canonical_repeat, choice, sequence,
48};
49pub use concepts::{
50    GRAMMAR_CONCEPTS, GrammarConcept, annotate_grammar_concepts, grammar_expr_concept_id,
51    rule_concept_id,
52};
53pub use decorators::{decorate_emitted, decorate_grammar, decorate_syntax_tree};
54pub use emit::{
55    EmitReport, GrammarEmitError, JsParserArtifacts, RustParserArtifacts, emit_abnf, emit_antlr,
56    emit_bnf, emit_ebnf, emit_gbnf, emit_javascript_parser, emit_lark, emit_peggy, emit_pest,
57    emit_rust_parser, emit_tree_sitter_grammar_js, emit_tree_sitter_grammar_js_with_report,
58    emit_tree_sitter_json, render_rust_type,
59};
60pub use feature::{
61    ByteClassItem, FEATURE_EXPRESSION_FORMS, FeatureExpr, FeatureForm, FieldType, FieldValue,
62    GrammarDeclarations, GrammarMacro, GrammarScanner, MATCHING_MODES, OPERATION_FORMS, Operation,
63    OperationCategory, PrecedenceEntry, RuleAttributes, SETTLING_STEPS, UnicodeClassItem,
64    default_settling, settling_problem,
65};
66pub use fidelity::{
67    FORMER_GRAMMAR_CONSTRUCTS, GRAMMAR_CONSTRUCTS, GRAMMAR_FORMATS, GrammarFidelityLevel,
68    GrammarFormatProfile, canonical_grammar_format, current_grammar_construct,
69    grammar_format_profile,
70};
71pub use import::{
72    GrammarImportError, import_abnf, import_antlr, import_bnf, import_ebnf, import_gbnf,
73    import_lark, import_pest, import_tree_sitter_json,
74};
75pub use inference::active::{
76    ActiveLearningConfig, ActiveLearningError, Dfa, GrammarAcceptorOracle,
77    Oracle as ActiveLearningOracle, ParserAcceptancePredicate, ParserMembershipOracle,
78    SamplingEquivalenceOracle, Symbol as ActiveSymbol, clean_structural_acceptance, learn_dfa,
79    learn_grammar,
80};
81pub use inference::advisor::{
82    AdviceDecision, AdviceDecisionKind, AdviceSource, ConceptNamingAdvisor, FallbackAdvisor,
83    MdlMergeAdvisor, MergeAdvisor, MergeCandidate, MergeRequest, MergeScore, NameCandidate,
84    NamingAdvisor, NamingRequest,
85};
86#[cfg(feature = "llm-assist")]
87pub use inference::advisor::{LlmClient, LlmError, LlmMergeAdvisor, LlmNamingAdvisor};
88pub use inference::cfg::{
89    InferenceOptions, InferenceReport, InferenceResult, Oracle, PositiveOnlyOracle, infer_cfg,
90    infer_cfg_with_advisors,
91};
92pub use inference::eval::{
93    BenchmarkReport, EvalError, GOLDEN_CORPORA, GoldenCorpus, GrammarOracle, MembershipOracle,
94    MetricScores, SampleConfig, ScoringMode, evaluate, mdl, run_corpus, run_named_corpus, sample,
95    size_symbols,
96};
97pub use inference::lexical::{
98    CharCategory, LexicalConfig, LexicalModel, Token, categorise, infer_lexical_classes,
99};
100pub use inference::minimize::{
101    Mdl, MinimizeOptions, MinimizeReport, MinimizeResult, mdl_cost, minimize,
102};
103pub use inference::prior::{
104    ByteSpan, Delimiter, LeafKind, PriorOptions, SeedNode, SeedTree, StructuralPrior,
105    WhitespacePolicy, build_structural_prior,
106};
107pub use inference::semantic::{
108    ConstraintAtom, ConstraintClause, ConstraintPattern, LengthUnit, NonTerminalRef,
109    SemanticConstraint, SemanticInferenceConfig, default_pattern_catalog, evaluate_atom,
110    evaluate_clause, evaluate_constraint, evaluate_probabilistic, mine_semantic_constraints,
111};
112pub use inference::sequitur::{Symbol, run_sequitur};
113pub use inference::state_merging::{InferredAutomaton, MergeStrategy, Sample, infer_dfa};
114pub use interchange::{
115    GRAMMAR_COMMAND_USAGE, GRAMMAR_EXPORT_FORMATS, GRAMMAR_IMPORT_FORMATS,
116    GRAMMAR_LOSSLESS_FORMATS, GrammarCommandOutput, GrammarEmitter, GrammarFileReader,
117    GrammarImporter, GrammarLayout, GrammarLayoutDefinition, GrammarLayoutImplicit,
118    GrammarLosslessError, GrammarSourceDefinition, GrammarSourceSplit, capture_grammar_layout,
119    deserialize_grammar, emit_grammar_lossless, grammar_emitter, grammar_importer,
120    import_grammar_lossless, parse_grammar_layout_links, parse_grammar_links,
121    parse_links_expression, parse_native_grammar, percent_decode_links_text,
122    percent_encode_links_text, render_declaration_links, render_grammar_layout_links,
123    render_grammar_links, render_links_expression, render_native_expression, render_native_feature,
124    render_native_grammar, render_rule_fields, render_rule_link, run_grammar_command,
125    serialize_grammar, split_grammar_source,
126};
127pub use merge::{
128    GRAMMAR_MERGE_METHOD, GrammarMergeAlternative, GrammarMergeAlternativeReason,
129    GrammarMergeDecision, GrammarMergeDecisionKind, GrammarMergeError, GrammarMergeFailure,
130    GrammarMergeFailureKind, GrammarMergeFailureReason, GrammarMergeNomination,
131    GrammarMergeNominationBasis, GrammarMergeNominationOutcome, GrammarMergeOptions,
132    GrammarMergeResult, GrammarMergeSource, GrammarRenameError, GrammarRenameErrorKind,
133    MergedGrammarGroup, RenamedGrammar, RuleAlias, assert_merge_complete, assert_merge_shares,
134    merge_grammars, normalized_rule_definition, rename_grammar_rule, restore_source_names,
135    shared_rule_decisions,
136};
137pub use metadata::{GrammarFormat, GrammarKind, GrammarSourceName};
138pub use reverse::{
139    GrammarReverseConversion, GrammarReverseFailure, GrammarReverseFailureKind,
140    GrammarReverseReport, GrammarReverseStage, GrammarReverseStatus,
141    check_grammar_reverse_conversion,
142};
143pub use round_trip::{
144    GRAMMAR_ROUND_TRIP_MARKER, GrammarEmitFn, GrammarImportFn, GrammarRoundTrip,
145    GrammarRoundTripError, GrammarRoundTripFailure, GrammarRoundTripFailureKind,
146    GrammarRoundTripReport, GrammarRoundTripStage, GrammarRoundTripStatus, accepts_text,
147    canonical_rule_definition, check_grammar_round_trip, mutate_grammar_start_rule,
148};
149pub use runtime::{GrammarParser, register_grammar, with_grammar};
150pub use surface::{
151    GrammarSurfaceError, grammar_from_lino, grammar_to_lino, parse_grammar_surface,
152    write_grammar_surface,
153};
154pub use translate::{
155    GrammarTranslateError, grammar_concept_translation_rules, translate_grammar_surface,
156};
157pub use validate::{
158    DiagnosticKind, GRAMMAR_DIAGNOSTIC_KINDS, GrammarDiagnostic, RuleSpan, Severity,
159    display_grammar_expression, validate,
160};
161
162use std::collections::BTreeSet;
163use std::fmt;
164
165/// One node of the grammar expression algebra.
166#[derive(Clone, Debug, PartialEq, Eq)]
167pub enum GrammarExpr {
168    /// Matches the empty string.
169    Empty,
170    /// Literal string terminal, for example `"fn"`.
171    Terminal(String),
172    /// Case-insensitive literal string terminal.
173    TerminalInsensitive(String),
174    /// Inclusive character range, for example `'a'..='z'`.
175    CharRange(char, char),
176    /// Explicit set of characters or ranges.
177    CharClass {
178        /// Whether the class is negated.
179        negated: bool,
180        /// Characters and ranges accepted by the class.
181        items: Vec<CharClassItem>,
182    },
183    /// The any-character wildcard.
184    AnyChar,
185    /// Reference to another grammar rule by name.
186    NonTerminal(String),
187    /// Alternation between expressions.
188    Choice {
189        /// Whether alternatives are ordered, as in PEG choice.
190        ordered: bool,
191        /// Alternative expressions.
192        alternatives: Vec<Self>,
193    },
194    /// Concatenation of expressions.
195    Sequence(Vec<Self>),
196    /// Optional expression.
197    Optional(Box<Self>),
198    /// Zero-or-more repetition.
199    ZeroOrMore(Box<Self>),
200    /// One-or-more repetition.
201    OneOrMore(Box<Self>),
202    /// Counted repetition.
203    Repeat {
204        /// Repeated expression.
205        expr: Box<Self>,
206        /// Minimum number of repetitions.
207        min: usize,
208        /// Maximum number of repetitions, or `None` for unbounded.
209        max: Option<usize>,
210    },
211    /// Positive lookahead predicate.
212    And(Box<Self>),
213    /// Negative lookahead predicate.
214    Not(Box<Self>),
215    /// Labelled or anonymous capture.
216    Capture {
217        /// Optional capture label.
218        label: Option<String>,
219        /// Captured expression.
220        expr: Box<Self>,
221    },
222    /// A form of the grammar feature union (`docs/grammar/feature-union.md`).
223    Feature(Box<FeatureExpr>),
224}
225
226impl GrammarExpr {
227    /// Builds an empty-string expression.
228    #[must_use]
229    pub const fn empty() -> Self {
230        Self::Empty
231    }
232
233    /// Builds a literal terminal expression.
234    #[must_use]
235    pub fn terminal(value: impl Into<String>) -> Self {
236        Self::Terminal(value.into())
237    }
238
239    /// Builds a case-insensitive literal terminal expression.
240    #[must_use]
241    pub fn terminal_insensitive(value: impl Into<String>) -> Self {
242        Self::TerminalInsensitive(value.into())
243    }
244
245    /// Builds an inclusive character range expression.
246    #[must_use]
247    pub const fn char_range(start: char, end: char) -> Self {
248        Self::CharRange(start, end)
249    }
250
251    /// Builds a character class expression.
252    #[must_use]
253    pub fn char_class<I>(negated: bool, items: I) -> Self
254    where
255        I: IntoIterator<Item = CharClassItem>,
256    {
257        Self::CharClass {
258            negated,
259            items: items.into_iter().collect(),
260        }
261    }
262
263    /// Builds an any-character wildcard expression.
264    #[must_use]
265    pub const fn any_char() -> Self {
266        Self::AnyChar
267    }
268
269    /// Builds a non-terminal reference expression.
270    #[must_use]
271    pub fn non_terminal(value: impl Into<String>) -> Self {
272        Self::NonTerminal(value.into())
273    }
274
275    /// Builds a choice expression.
276    #[must_use]
277    pub fn choice<I>(ordered: bool, alternatives: I) -> Self
278    where
279        I: IntoIterator<Item = Self>,
280    {
281        Self::Choice {
282            ordered,
283            alternatives: alternatives.into_iter().collect(),
284        }
285    }
286
287    /// Builds a sequence expression.
288    #[must_use]
289    pub fn sequence<I>(items: I) -> Self
290    where
291        I: IntoIterator<Item = Self>,
292    {
293        Self::Sequence(items.into_iter().collect())
294    }
295
296    /// Builds an optional expression.
297    #[must_use]
298    pub fn optional(expr: Self) -> Self {
299        Self::Optional(Box::new(expr))
300    }
301
302    /// Builds a zero-or-more repetition expression.
303    #[must_use]
304    pub fn zero_or_more(expr: Self) -> Self {
305        Self::ZeroOrMore(Box::new(expr))
306    }
307
308    /// Builds a one-or-more repetition expression.
309    #[must_use]
310    pub fn one_or_more(expr: Self) -> Self {
311        Self::OneOrMore(Box::new(expr))
312    }
313
314    /// Builds a counted repetition expression.
315    #[must_use]
316    pub fn repeat(expr: Self, min: usize, max: Option<usize>) -> Self {
317        Self::Repeat {
318            expr: Box::new(expr),
319            min,
320            max,
321        }
322    }
323
324    /// Builds a positive lookahead expression.
325    #[must_use]
326    pub fn and(expr: Self) -> Self {
327        Self::And(Box::new(expr))
328    }
329
330    /// Builds a negative lookahead expression.
331    #[must_use]
332    #[allow(clippy::should_implement_trait)]
333    pub fn not(expr: Self) -> Self {
334        Self::Not(Box::new(expr))
335    }
336
337    /// Builds a labelled capture expression.
338    #[must_use]
339    pub fn capture(label: impl Into<String>, expr: Self) -> Self {
340        Self::Capture {
341            label: Some(label.into()),
342            expr: Box::new(expr),
343        }
344    }
345
346    /// Builds an anonymous capture expression.
347    #[must_use]
348    pub fn capture_unlabeled(expr: Self) -> Self {
349        Self::Capture {
350            label: None,
351            expr: Box::new(expr),
352        }
353    }
354
355    /// Builds a feature union expression.
356    #[must_use]
357    pub fn feature(feature: FeatureExpr) -> Self {
358        Self::Feature(Box::new(feature))
359    }
360
361    /// Copies a feature form with every nested expression rewritten by `map`.
362    pub(crate) fn rewrite_feature(
363        feature: &FeatureExpr,
364        mut map: impl FnMut(&Self) -> Self,
365    ) -> Self {
366        let mut copy = feature.clone();
367        copy.map_expressions(&mut |expr| *expr = map(expr));
368        Self::Feature(Box::new(copy))
369    }
370
371    /// The first feature union form in this expression, in source order.
372    #[must_use]
373    pub fn first_feature(&self) -> Option<&FeatureExpr> {
374        match self {
375            Self::Feature(feature) => Some(feature),
376            Self::Choice { alternatives, .. } | Self::Sequence(alternatives) => {
377                alternatives.iter().find_map(Self::first_feature)
378            }
379            Self::Optional(inner)
380            | Self::ZeroOrMore(inner)
381            | Self::OneOrMore(inner)
382            | Self::And(inner)
383            | Self::Not(inner)
384            | Self::Repeat { expr: inner, .. }
385            | Self::Capture { expr: inner, .. } => inner.first_feature(),
386            Self::Empty
387            | Self::Terminal(_)
388            | Self::TerminalInsensitive(_)
389            | Self::CharRange(_, _)
390            | Self::CharClass { .. }
391            | Self::AnyChar
392            | Self::NonTerminal(_) => None,
393        }
394    }
395
396    pub(crate) fn collect_nonterminals(&self, names: &mut BTreeSet<String>) {
397        match self {
398            Self::Feature(feature) => feature.collect_references(names),
399            Self::NonTerminal(name) => {
400                names.insert(name.clone());
401            }
402            Self::Choice { alternatives, .. } => {
403                for alternative in alternatives {
404                    alternative.collect_nonterminals(names);
405                }
406            }
407            Self::Sequence(items) => {
408                for item in items {
409                    item.collect_nonterminals(names);
410                }
411            }
412            Self::Optional(expr)
413            | Self::ZeroOrMore(expr)
414            | Self::OneOrMore(expr)
415            | Self::And(expr)
416            | Self::Not(expr)
417            | Self::Capture { expr, .. }
418            | Self::Repeat { expr, .. } => expr.collect_nonterminals(names),
419            Self::Empty
420            | Self::Terminal(_)
421            | Self::TerminalInsensitive(_)
422            | Self::CharRange(_, _)
423            | Self::CharClass { .. }
424            | Self::AnyChar => {}
425        }
426    }
427}
428
429impl fmt::Display for GrammarExpr {
430    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
431        match self {
432            Self::Empty => formatter.write_str("empty"),
433            Self::Terminal(value) => write!(formatter, "{value:?}"),
434            Self::TerminalInsensitive(value) => write!(formatter, "i{value:?}"),
435            Self::CharRange(start, end) => write!(formatter, "{start:?}..={end:?}"),
436            Self::CharClass { negated, items } => {
437                let marker = if *negated { "^" } else { "" };
438                write!(formatter, "[{marker}")?;
439                for item in items {
440                    write!(formatter, "{item}")?;
441                }
442                formatter.write_str("]")
443            }
444            Self::AnyChar => formatter.write_str("."),
445            Self::NonTerminal(name) => formatter.write_str(name),
446            Self::Choice {
447                ordered,
448                alternatives,
449            } => {
450                let separator = if *ordered { " / " } else { " | " };
451                write_joined(formatter, alternatives, separator)
452            }
453            Self::Sequence(items) => write_joined(formatter, items, " "),
454            Self::Optional(expr) => write!(formatter, "({expr})?"),
455            Self::ZeroOrMore(expr) => write!(formatter, "({expr})*"),
456            Self::OneOrMore(expr) => write!(formatter, "({expr})+"),
457            Self::Repeat { expr, min, max } => match max {
458                Some(max) => write!(formatter, "({expr}){{{min},{max}}}"),
459                None => write!(formatter, "({expr}){{{min},}}"),
460            },
461            Self::And(expr) => write!(formatter, "&({expr})"),
462            Self::Not(expr) => write!(formatter, "!({expr})"),
463            Self::Capture { label, expr } => match label {
464                Some(label) => write!(formatter, "{label}:({expr})"),
465                None => write!(formatter, "capture({expr})"),
466            },
467            Self::Feature(feature) => {
468                formatter.write_str(&interchange::render_native_feature(feature))
469            }
470        }
471    }
472}
473
474/// One item inside a character class.
475#[derive(Clone, Debug, PartialEq, Eq)]
476pub enum CharClassItem {
477    /// A single character.
478    Char(char),
479    /// An inclusive character range.
480    Range(char, char),
481}
482
483impl CharClassItem {
484    /// Builds a single-character class item.
485    #[must_use]
486    pub const fn char(value: char) -> Self {
487        Self::Char(value)
488    }
489
490    /// Builds an inclusive character range class item.
491    #[must_use]
492    pub const fn range(start: char, end: char) -> Self {
493        Self::Range(start, end)
494    }
495}
496
497impl fmt::Display for CharClassItem {
498    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
499        match self {
500            Self::Char(value) => write!(formatter, "{}", value.escape_default()),
501            Self::Range(start, end) => {
502                write!(
503                    formatter,
504                    "{}-{}",
505                    start.escape_default(),
506                    end.escape_default()
507                )
508            }
509        }
510    }
511}
512
513/// How a rule participates in parsing.
514#[derive(Clone, Copy, Debug, PartialEq, Eq)]
515pub enum RuleKind {
516    /// A normal rule that participates in the parse tree.
517    Normal,
518    /// An atomic rule whose inner expression is treated as an indivisible token.
519    Atomic,
520    /// A silent rule that can be omitted from visible parse output.
521    Silent,
522    /// A token-level rule.
523    Token,
524}
525
526impl RuleKind {
527    /// Stable tag used in links encoding and display output.
528    #[must_use]
529    pub const fn as_str(self) -> &'static str {
530        match self {
531            Self::Normal => "normal",
532            Self::Atomic => "atomic",
533            Self::Silent => "silent",
534            Self::Token => "token",
535        }
536    }
537
538    pub(crate) fn from_tag(value: &str) -> Option<Self> {
539        match value {
540            "normal" => Some(Self::Normal),
541            "atomic" => Some(Self::Atomic),
542            "silent" => Some(Self::Silent),
543            "token" => Some(Self::Token),
544            _ => None,
545        }
546    }
547}
548
549impl fmt::Display for RuleKind {
550    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
551        formatter.write_str(self.as_str())
552    }
553}
554
555/// A named grammar rule.
556#[derive(Clone, Debug, PartialEq, Eq)]
557pub struct GrammarRule {
558    /// Rule name.
559    pub name: String,
560    /// Rule expression.
561    pub expr: GrammarExpr,
562    /// Rule participation kind.
563    pub kind: RuleKind,
564    /// Optional concept-ontology alignment.
565    pub concept: Option<String>,
566    /// The names the rule has in the grammars it was merged from.
567    pub source_names: Vec<GrammarSourceName>,
568    /// Optional free-text documentation or comment.
569    pub doc: Option<String>,
570    /// Parameters, channel, modes and action of the feature union.
571    pub attributes: RuleAttributes,
572}
573
574impl GrammarRule {
575    /// Builds a normal grammar rule.
576    #[must_use]
577    pub fn new(name: impl Into<String>, expr: GrammarExpr) -> Self {
578        Self {
579            name: name.into(),
580            expr,
581            kind: RuleKind::Normal,
582            concept: None,
583            source_names: Vec::new(),
584            doc: None,
585            attributes: RuleAttributes::default(),
586        }
587    }
588
589    /// Returns this rule with feature union attributes.
590    #[must_use]
591    pub fn with_attributes(mut self, attributes: RuleAttributes) -> Self {
592        self.attributes = attributes;
593        self
594    }
595
596    /// Returns this rule with a different rule kind.
597    #[must_use]
598    pub const fn with_kind(mut self, kind: RuleKind) -> Self {
599        self.kind = kind;
600        self
601    }
602
603    /// Returns this rule with concept-ontology alignment.
604    #[must_use]
605    pub fn with_concept(mut self, concept: impl Into<String>) -> Self {
606        self.concept = Some(concept.into());
607        self
608    }
609
610    /// Returns this rule with the names it has in the grammars it was merged
611    /// from.
612    #[must_use]
613    pub fn with_source_names(mut self, source_names: Vec<GrammarSourceName>) -> Self {
614        self.source_names = source_names;
615        self
616    }
617
618    /// Returns this rule with documentation text.
619    #[must_use]
620    pub fn with_doc(mut self, doc: impl Into<String>) -> Self {
621        self.doc = Some(doc.into());
622        self
623    }
624
625    /// Rule name.
626    #[must_use]
627    pub fn name(&self) -> &str {
628        &self.name
629    }
630
631    /// Rule expression.
632    #[must_use]
633    pub const fn expr(&self) -> &GrammarExpr {
634        &self.expr
635    }
636
637    /// Rule participation kind.
638    #[must_use]
639    pub const fn kind(&self) -> RuleKind {
640        self.kind
641    }
642
643    /// Concept-ontology alignment, when present.
644    #[must_use]
645    pub fn concept(&self) -> Option<&str> {
646        self.concept.as_deref()
647    }
648
649    /// The names the rule has in the grammars it was merged from.
650    #[must_use]
651    pub fn source_names(&self) -> &[GrammarSourceName] {
652        &self.source_names
653    }
654
655    /// Rule documentation, when present.
656    #[must_use]
657    pub fn doc(&self) -> Option<&str> {
658        self.doc.as_deref()
659    }
660}
661
662/// Order-preserving grammar.
663#[derive(Clone, Debug, Default, PartialEq, Eq)]
664pub struct Grammar {
665    rules: Vec<GrammarRule>,
666    start: Option<String>,
667    source_format: Option<GrammarFormat>,
668    declarations: GrammarDeclarations,
669    kinds: Vec<GrammarKind>,
670}
671
672impl Grammar {
673    /// Builds an empty grammar.
674    #[must_use]
675    pub const fn new() -> Self {
676        Self {
677            rules: Vec::new(),
678            start: None,
679            source_format: None,
680            declarations: GrammarDeclarations {
681                matching: None,
682                settling: None,
683                imports: Vec::new(),
684                modes: Vec::new(),
685                extras: Vec::new(),
686                conflicts: Vec::new(),
687                precedences: Vec::new(),
688                macros: Vec::new(),
689                scanners: Vec::new(),
690            },
691            kinds: Vec::new(),
692        }
693    }
694
695    /// Builds a fluent grammar builder.
696    #[must_use]
697    pub const fn builder() -> GrammarBuilder {
698        GrammarBuilder::new()
699    }
700
701    /// Builds an expression builder.
702    #[must_use]
703    pub const fn expr() -> ExprBuilder {
704        ExprBuilder
705    }
706
707    /// Returns this grammar with an additional rule.
708    #[must_use]
709    pub fn with_rule(mut self, rule: GrammarRule) -> Self {
710        self.rules.push(rule);
711        self
712    }
713
714    /// Returns this grammar with a start rule name.
715    #[must_use]
716    pub fn with_start(mut self, start: impl Into<String>) -> Self {
717        self.start = Some(start.into());
718        self
719    }
720
721    /// Returns this grammar with a source format.
722    #[must_use]
723    pub const fn with_source_format(mut self, source_format: GrammarFormat) -> Self {
724        self.source_format = Some(source_format);
725        self
726    }
727
728    /// Returns this grammar with feature union declarations.
729    #[must_use]
730    pub fn with_declarations(mut self, declarations: GrammarDeclarations) -> Self {
731        self.declarations = declarations;
732        self
733    }
734
735    /// The feature union declarations.
736    #[must_use]
737    pub const fn declarations(&self) -> &GrammarDeclarations {
738        &self.declarations
739    }
740
741    /// Replaces the feature union declarations.
742    pub fn set_declarations(&mut self, declarations: GrammarDeclarations) {
743        self.declarations = declarations;
744    }
745
746    /// The node kinds no rule defines that keep their source names.
747    #[must_use]
748    pub fn kinds(&self) -> &[GrammarKind] {
749        &self.kinds
750    }
751
752    /// Replaces the node kinds no rule defines.
753    pub fn set_kinds(&mut self, kinds: Vec<GrammarKind>) {
754        self.kinds = kinds;
755    }
756
757    /// Adds a rule to the grammar.
758    pub fn add_rule(&mut self, rule: GrammarRule) {
759        self.rules.push(rule);
760    }
761
762    /// Sets the grammar start rule name.
763    pub fn set_start(&mut self, start: impl Into<String>) {
764        self.start = Some(start.into());
765    }
766
767    /// Clears the explicit grammar start rule.
768    pub fn clear_start(&mut self) {
769        self.start = None;
770    }
771
772    /// Sets the grammar source format.
773    pub const fn set_source_format(&mut self, source_format: GrammarFormat) {
774        self.source_format = Some(source_format);
775    }
776
777    /// Returns all rules in source order.
778    #[must_use]
779    pub fn rules(&self) -> &[GrammarRule] {
780        &self.rules
781    }
782
783    /// Returns the rule with `name`, when present.
784    #[must_use]
785    pub fn rule(&self, name: &str) -> Option<&GrammarRule> {
786        self.rules.iter().find(|rule| rule.name == name)
787    }
788
789    /// Returns the explicitly configured start symbol, if present.
790    #[must_use]
791    pub fn start(&self) -> Option<&str> {
792        self.start.as_deref()
793    }
794
795    /// Returns the start rule, defaulting to the first rule when unset.
796    #[must_use]
797    pub fn start_rule(&self) -> Option<&GrammarRule> {
798        self.start
799            .as_deref()
800            .map_or_else(|| self.rules.first(), |start| self.rule(start))
801    }
802
803    /// Returns the source format, if known.
804    #[must_use]
805    pub const fn source_format(&self) -> Option<GrammarFormat> {
806        self.source_format
807    }
808
809    /// Returns rule names in source order.
810    #[must_use]
811    pub fn rule_names(&self) -> Vec<&str> {
812        self.rules.iter().map(GrammarRule::name).collect()
813    }
814
815    /// Returns non-terminal names referenced from every rule expression.
816    #[must_use]
817    pub fn referenced_nonterminals(&self) -> BTreeSet<String> {
818        let mut names = BTreeSet::new();
819        for rule in &self.rules {
820            rule.expr.collect_nonterminals(&mut names);
821        }
822        for extra in &self.declarations.extras {
823            extra.collect_nonterminals(&mut names);
824        }
825        for declared in &self.declarations.macros {
826            declared.expression.collect_nonterminals(&mut names);
827        }
828        names
829    }
830
831    /// Returns referenced non-terminals that do not have a local rule.
832    #[must_use]
833    pub fn undefined_nonterminals(&self) -> BTreeSet<String> {
834        let defined = self
835            .rules
836            .iter()
837            .map(|rule| rule.name.clone())
838            .chain(
839                self.declarations
840                    .external_tokens()
841                    .into_iter()
842                    .map(str::to_owned),
843            )
844            .collect::<BTreeSet<_>>();
845        self.referenced_nonterminals()
846            .difference(&defined)
847            .cloned()
848            .collect()
849    }
850}
851
852/// Copies the documentation of every rule of `source` onto the rule of
853/// `target` that `rename` names it.
854///
855/// As the JavaScript `carryRuleDocs` does, a rule of `source` without
856/// documentation, or one `target` lacks, changes nothing.
857#[must_use]
858pub fn carry_rule_docs(
859    mut target: Grammar,
860    source: &Grammar,
861    rename: &dyn Fn(&str) -> String,
862) -> Grammar {
863    for rule in source.rules() {
864        let Some(doc) = &rule.doc else {
865            continue;
866        };
867        let name = rename(&rule.name);
868        for carried in target
869            .rules
870            .iter_mut()
871            .filter(|carried| carried.name == name)
872        {
873            carried.doc = Some(doc.clone());
874        }
875    }
876    target
877}
878
879fn write_joined(
880    formatter: &mut fmt::Formatter<'_>,
881    expressions: &[GrammarExpr],
882    separator: &str,
883) -> fmt::Result {
884    if let Some((first, rest)) = expressions.split_first() {
885        write!(formatter, "{first}")?;
886        for expression in rest {
887            formatter.write_str(separator)?;
888            write!(formatter, "{expression}")?;
889        }
890    }
891    Ok(())
892}
meta_language/grammar/mod.rs

meta_language/grammar/
mod.rs
