rusty_alto/
alto.rs

1//! Reader for Alto's textual finite-tree-automaton (`.auto`) format.
2
3use crate::{
4    Explicit, ExplicitBuildError, ExplicitBuilder, FxHashMap, Interner, Signature, SignatureError,
5    StateId,
6    alto_ast::{AstFta, AstState, LexError, Tok, lex},
7    alto_grammar,
8};
9use lalrpop_util::ParseError;
10use thiserror::Error;
11
12/// An explicit automaton together with the symbol signature and state names used by its source.
13///
14/// Alto's `.auto` format writes rules top-down, for example
15/// `S! -> f(A,A) [1.0]`. This reader builds the equivalent bottom-up
16/// [`Explicit`] automaton, i.e. the rule above becomes `f(A,A) -> S`.
17#[derive(Clone, Debug)]
18pub struct ExplicitWithSignature {
19    /// Bottom-up explicit automaton built from the Alto rules.
20    pub automaton: Explicit,
21    /// Mapping from Alto state names to dense state IDs.
22    pub states: Interner<String>,
23    /// Mapping from Alto terminal symbols to symbol IDs.
24    pub signature: Signature,
25}
26
27/// Former name of [`ExplicitWithSignature`].
28#[deprecated(note = "renamed to ExplicitWithSignature")]
29pub type ParsedTreeAutomaton = ExplicitWithSignature;
30
31/// Error returned when parsing Alto `.auto` input.
32#[derive(Clone, Debug, Error, PartialEq)]
33pub enum AltoParseError {
34    /// A token was expected but not found.
35    #[error("expected {expected} at byte {offset}")]
36    Expected {
37        /// Human-readable token description.
38        expected: &'static str,
39        /// Byte offset in the input.
40        offset: usize,
41    },
42    /// An unexpected token was found.
43    #[error("unexpected token {found:?} at byte {offset}; expected {expected}")]
44    Unexpected {
45        /// Human-readable expected token description.
46        expected: &'static str,
47        /// Token that was found.
48        found: String,
49        /// Byte offset in the input.
50        offset: usize,
51    },
52    /// A quoted name reached end-of-file before the closing quote.
53    #[error("unterminated quoted name starting at byte {offset}")]
54    UnterminatedQuote {
55        /// Byte offset where the quote started.
56        offset: usize,
57    },
58    /// A block comment reached end-of-file before `*/`.
59    #[error("unterminated block comment starting at byte {offset}")]
60    UnterminatedComment {
61        /// Byte offset where the comment started.
62        offset: usize,
63    },
64    /// A variable token appeared in an automaton file or was malformed.
65    #[error("invalid variable at byte {offset}")]
66    InvalidVariable {
67        /// Byte offset where the variable started.
68        offset: usize,
69    },
70    /// A weight could not be parsed as `f64`.
71    #[error("invalid weight {text:?} at byte {offset}")]
72    InvalidWeight {
73        /// Weight text inside brackets.
74        text: String,
75        /// Byte offset where the weight started.
76        offset: usize,
77    },
78    /// One terminal symbol was used with two arities.
79    #[error("symbol {symbol:?} used with arities {first} and {second}")]
80    ArityMismatch {
81        /// Terminal symbol name.
82        symbol: String,
83        /// First observed arity.
84        first: usize,
85        /// Later conflicting arity.
86        second: usize,
87    },
88    /// LALRPOP reported a syntax error.
89    #[error("{0}")]
90    Syntax(String),
91    /// The automaton contained a duplicate transition.
92    #[error("{0}")]
93    Automaton(#[from] ExplicitBuildError),
94}
95
96impl From<SignatureError> for AltoParseError {
97    fn from(value: SignatureError) -> Self {
98        match value {
99            SignatureError::ArityMismatch {
100                symbol,
101                first,
102                second,
103            } => Self::ArityMismatch {
104                symbol,
105                first,
106                second,
107            },
108        }
109    }
110}
111
112impl From<LexError> for AltoParseError {
113    fn from(value: LexError) -> Self {
114        match value {
115            LexError::UnterminatedQuote { offset } => Self::UnterminatedQuote { offset },
116            LexError::UnterminatedComment { offset } => Self::UnterminatedComment { offset },
117            LexError::InvalidVariable { offset } => Self::InvalidVariable { offset },
118            LexError::Unexpected { found, offset } => Self::Unexpected {
119                expected: "Alto token",
120                found: found.to_string(),
121                offset,
122            },
123        }
124    }
125}
126
127/// Parse an Alto `.auto` file into a bottom-up explicit automaton.
128///
129/// Supported syntax follows Alto's `auto` codec:
130///
131/// - rules: `State! -> label(Child1, Child2) [0.5]`
132/// - nullary rules: `State -> label`
133/// - final states: `!` or `°` after any state occurrence
134/// - quoted names with single or double quotes
135/// - optional weights, defaulting to `1.0`
136/// - `// ...` line comments and `/* ... */` block comments
137pub fn parse_alto(input: &str) -> Result<ExplicitWithSignature, AltoParseError> {
138    let mut signature = Signature::new();
139    parse_alto_with_signature(input, &mut signature)
140}
141
142/// Parse an Alto `.auto` file using a caller-owned shared signature.
143///
144/// This is useful when automata and input trees should be compiled into the
145/// same raw [`crate::Symbol`] space. The returned [`ExplicitWithSignature`]
146/// contains a clone of the signature after parsing; the caller can keep using
147/// `signature` to parse or validate trees before running the automaton.
148pub fn parse_alto_with_signature(
149    input: &str,
150    signature: &mut Signature,
151) -> Result<ExplicitWithSignature, AltoParseError> {
152    let tokens = lex(input)?;
153    let ast = alto_grammar::FtaParser::new()
154        .parse(tokens.into_iter().map(Ok))
155        .map_err(parse_error_to_alto)?;
156    build_alto(ast, signature)
157}
158
159fn build_alto(
160    ast: AstFta,
161    signature: &mut Signature,
162) -> Result<ExplicitWithSignature, AltoParseError> {
163    let mut builder = ExplicitBuilder::new();
164    let mut states = Interner::new();
165    let mut state_ids = FxHashMap::default();
166
167    for rule in ast.rules {
168        let parent = state_id(&mut builder, &mut states, &mut state_ids, &rule.parent);
169        if rule.parent.is_final {
170            builder.add_accepting(parent);
171        }
172        let child_ids: Vec<_> = rule
173            .children
174            .iter()
175            .map(|child| {
176                let id = state_id(&mut builder, &mut states, &mut state_ids, child);
177                if child.is_final {
178                    builder.add_accepting(id);
179                }
180                id
181            })
182            .collect();
183        let symbol = signature.intern(rule.symbol.clone(), child_ids.len())?;
184        builder.add_weighted_rule(symbol, child_ids, parent, rule.weight.unwrap_or(1.0));
185    }
186
187    Ok(ExplicitWithSignature {
188        automaton: builder.try_build()?,
189        states,
190        signature: signature.clone(),
191    })
192}
193
194fn state_id(
195    builder: &mut ExplicitBuilder,
196    states: &mut Interner<String>,
197    state_ids: &mut FxHashMap<String, StateId>,
198    state: &AstState,
199) -> StateId {
200    if let Some(&id) = state_ids.get(&state.name) {
201        return id;
202    }
203    let id = builder.new_state();
204    let interned = states.intern(state.name.clone());
205    debug_assert_eq!(id, interned);
206    state_ids.insert(state.name.clone(), id);
207    id
208}
209
210fn parse_error_to_alto(err: ParseError<usize, Tok, String>) -> AltoParseError {
211    match err {
212        ParseError::InvalidToken { location } => AltoParseError::Unexpected {
213            expected: "Alto token",
214            found: "<invalid>".to_owned(),
215            offset: location,
216        },
217        ParseError::UnrecognizedEof { location, expected } => AltoParseError::Expected {
218            expected: leak_expected(expected),
219            offset: location,
220        },
221        ParseError::UnrecognizedToken { token, expected } => AltoParseError::Unexpected {
222            expected: leak_expected(expected),
223            found: token_display(&token.1),
224            offset: token.0,
225        },
226        ParseError::ExtraToken { token } => AltoParseError::Unexpected {
227            expected: "end of input",
228            found: token_display(&token.1),
229            offset: token.0,
230        },
231        ParseError::User { error } => AltoParseError::Syntax(error),
232    }
233}
234
235fn leak_expected(expected: Vec<String>) -> &'static str {
236    if expected.is_empty() {
237        "valid syntax"
238    } else {
239        Box::leak(expected.join(", ").into_boxed_str())
240    }
241}
242
243fn token_display(kind: &Tok) -> String {
244    match kind {
245        Tok::Name(name) => format!("name {name:?}"),
246        Tok::Number(number) => format!("number {number:?}"),
247        Tok::Variable(variable) => format!("variable ?{variable}"),
248        Tok::Interpretation => "interpretation".to_owned(),
249        Tok::Feature => "feature".to_owned(),
250        Tok::Arrow => "->".to_owned(),
251        Tok::LParen => "(".to_owned(),
252        Tok::RParen => ")".to_owned(),
253        Tok::LBracket => "[".to_owned(),
254        Tok::RBracket => "]".to_owned(),
255        Tok::Comma => ",".to_owned(),
256        Tok::Colon => ":".to_owned(),
257        Tok::Fin => "!".to_owned(),
258    }
259}
260
261#[cfg(test)]
262mod tests {
263    use super::*;
264    use crate::{BottomUpTa, DetBottomUpTa};
265
266    #[test]
267    fn parses_wiki_example_as_bottom_up() {
268        let parsed = parse_alto(
269            "
270            S! -> f(A,A) [1.0]
271            A -> g(A) [0.5]
272            A -> a [0.5]
273            ",
274        )
275        .unwrap();
276        let s = parsed.states.get(&"S".to_owned()).unwrap();
277        let a_state = parsed.states.get(&"A".to_owned()).unwrap();
278        let f = parsed.signature.get("f").unwrap();
279        let leaf = parsed.signature.get("a").unwrap();
280
281        let mut out = Vec::new();
282        parsed.automaton.step(leaf, &[], &mut |q| out.push(q));
283        assert_eq!(out, vec![a_state]);
284        assert_eq!(parsed.automaton.step_det(f, &[a_state, a_state]), Some(s));
285        assert!(parsed.automaton.is_accepting(&s));
286        let g = parsed.signature.get("g").unwrap();
287        let g_rule = parsed
288            .automaton
289            .rules()
290            .find(|rule| rule.symbol == g)
291            .unwrap();
292        assert_eq!(g_rule.weight, 0.5);
293    }
294
295    #[test]
296    fn accepts_whitespace_separated_rules_and_comments() {
297        let parsed =
298            parse_alto("q1 -> a /* ignored -> text */ q2! -> f(q1, // line\n q1)").unwrap();
299        let q1 = parsed.states.get(&"q1".to_owned()).unwrap();
300        let q2 = parsed.states.get(&"q2".to_owned()).unwrap();
301        let f = parsed.signature.get("f").unwrap();
302        assert_eq!(parsed.automaton.step_det(f, &[q1, q1]), Some(q2));
303    }
304
305    #[test]
306    fn parses_quoted_names_and_scientific_weights() {
307        let parsed =
308            parse_alto("'S,0-1'! -> r('A,0-1', \"B state\") [3.3921302578018993E-4]").unwrap();
309        let parent = parsed.states.get(&"S,0-1".to_owned()).unwrap();
310        let left = parsed.states.get(&"A,0-1".to_owned()).unwrap();
311        let right = parsed.states.get(&"B state".to_owned()).unwrap();
312        let symbol = parsed.signature.get("r").unwrap();
313        let rule = parsed.automaton.rules().next().unwrap();
314        assert_eq!(rule.result, parent);
315        assert_eq!(rule.children, &[left, right]);
316        assert_eq!(rule.symbol, symbol);
317        assert!((rule.weight - 3.3921302578018993E-4).abs() < 1e-12);
318    }
319
320    #[test]
321    fn detects_arity_mismatch() {
322        let err = parse_alto("S -> f(A) T -> f(A,A)").unwrap_err();
323        assert!(matches!(err, AltoParseError::ArityMismatch { .. }));
324    }
325
326    #[test]
327    fn can_parse_with_shared_signature() {
328        let mut signature = Signature::new();
329        let a = signature.intern("a".to_owned(), 0).unwrap();
330        let parsed = parse_alto_with_signature("S! -> a", &mut signature).unwrap();
331        assert_eq!(parsed.signature.get("a"), Some(a));
332        assert_eq!(signature.get("a"), Some(a));
333    }
334
335    #[test]
336    fn parses_nullary_empty_parens() {
337        let parsed = parse_alto("S! -> a()").unwrap();
338        let rule = parsed.automaton.rules().next().unwrap();
339        assert!(rule.children.is_empty());
340        assert_eq!(parsed.signature.arity(rule.symbol), 0);
341    }
342
343    #[test]
344    fn final_marker_on_child_marks_accepting_state() {
345        let parsed = parse_alto("S -> f(A!)").unwrap();
346        let a = parsed.states.get(&"A".to_owned()).unwrap();
347        assert!(parsed.automaton.is_accepting(&a));
348    }
349
350    #[test]
351    fn rejects_variable_tokens_in_automata() {
352        let err = parse_alto("S -> f(?1)").unwrap_err();
353        assert!(matches!(err, AltoParseError::Unexpected { .. }));
354    }
355
356    #[test]
357    fn lalrpop_rejects_trailing_junk() {
358        let err = parse_alto("S -> a [oops]").unwrap_err();
359        assert!(matches!(err, AltoParseError::Unexpected { .. }));
360    }
361
362    #[test]
363    fn rejects_duplicate_transitions() {
364        let err = parse_alto("S -> a [1.0] S -> a [2.0]").unwrap_err();
365        assert!(matches!(err, AltoParseError::Automaton(_)));
366    }
367}
rusty_alto/alto.rs

rusty_alto/
alto.rs
