Expand description
A small, fast library for bottom-up tree automata.
A tree automaton reads a tree from the leaves upward. Each leaf receives a state, then each parent receives a state based on its symbol and the states assigned to its children. If the root reaches an accepting state, the tree is accepted.
The main trait is BottomUpTa. It treats an automaton as an oracle: given
a symbol and child states, it reports the possible parent states. This works
for both explicit automata, whose rules are stored in tables, and implicit
automata, whose rules are computed on demand.
Use ExplicitBuilder when all rules are known ahead of time. Use
Memo when an implicit automaton has its own state type, such as strings,
tuples, or syntax objects, but a runner needs dense StateId values. Use
materialize() when a finite implicit automaton should be explored and
frozen into an Explicit automaton.
Deterministic runners use StateId::STUCK as a sentinel for rejected
subtrees. A node assigned STUCK did not match any transition rule, or one
of its children was already stuck.
§Grammars, algebras, and codecs
Irtg combines a weighted grammar automaton with named homomorphisms and
algebras. Built-in algebras cover strings, trees, TAG strings, TAG derived
trees, and feature structures.
InputCodecRegistry discovers file readers by their exact result type:
both .irtg and Tulipac .tag codecs produce Irtg, while .auto
produces ExplicitWithSignature. OutputCodecRegistry discovers
textual encodings by an algebra’s public value type. An algebra’s preferred
GUI-neutral display is available through Algebra::visualize.
Codec metadata lookup is lazy: listing available formats does not read, evaluate, or encode anything.
§Parsing strategies and cancellation
Irtg::parse uses MaterializationStrategy::TopDownCondensed, the
recommended general default for complete chart construction.
Irtg::parse_with selects another strategy without changing the input
API. Interactive and service applications can use
Irtg::parse_with_control with a clonable ParseControl to request
cooperative cancellation from another thread; cancellation returns
IrtgError::Cancelled and never exposes a partial chart.
Algorithm performance depends on the loaded IRTG and input decomposition, not on the source filename. See the parsing-algorithm guide for selection advice and known trade-offs.
use rusty_alto::*;
use packed_term_arena::tree::TreeArena;
let a = Symbol(0);
let f = Symbol(1);
let mut builder = ExplicitBuilder::new();
let leaf = builder.new_state();
let root = builder.new_state();
builder.add_rule(a, vec![], leaf);
builder.add_rule(f, vec![leaf, leaf], root);
builder.add_accepting(root);
let automaton = builder.build();
let mut tree = TreeArena::new();
let left = tree.add_node(a, vec![]);
let right = tree.add_node(a, vec![]);
let root_node = tree.add_node(f, vec![left, right]);
let run = run_det(&automaton, &tree, root_node);
assert!(automaton.is_accepting(&run.root_state));Re-exports§
pub use algebras::APPEND_SYMBOL;pub use algebras::Algebra;pub use algebras::BinarizedTagTreeDecompositionAutomaton;pub use algebras::BinarizedTagTreeState;pub use algebras::Binarizing;pub use algebras::CONC11;pub use algebras::CONC12;pub use algebras::CONC21;pub use algebras::EvaluatingDecompositionAutomaton;pub use algebras::FS_EMBED_PREFIX;pub use algebras::FS_PROJECT_PREFIX;pub use algebras::FS_REMAP_PREFIX;pub use algebras::FS_UNIFY;pub use algebras::FeatureStructure;pub use algebras::FeatureStructureAlgebra;pub use algebras::FeatureStructureAttribute;pub use algebras::FeatureStructureFilter;pub use algebras::FeatureStructureNode;pub use algebras::FeatureStructureNodeId;pub use algebras::FeatureStructureParseError;pub use algebras::SentenceSxHeuristic;pub use algebras::Span;pub use algebras::StringAlgebra;pub use algebras::StringDecompositionAutomaton;pub use algebras::TAG_E;pub use algebras::TAG_EE;pub use algebras::TAG_HOLE;pub use algebras::TAG_SUBSTITUTE;pub use algebras::TagSpan;pub use algebras::TagStringAlgebra;pub use algebras::TagStringDecompositionAutomaton;pub use algebras::TagStringValue;pub use algebras::TagTreeAlgebra;pub use algebras::TagTreeContext;pub use algebras::TagTreeDecompositionAutomaton;pub use algebras::TreeAlgebra;pub use algebras::TreeValue;pub use algebras::UniversalSxHeuristic;pub use algebras::WRAP21;pub use algebras::WRAP22;pub use alto::AltoParseError;pub use alto::ExplicitWithSignature;pub use alto::ParsedTreeAutomaton;Deprecated pub use alto::parse_alto;pub use alto::parse_alto_with_signature;pub use application::AutomatonSummary;pub use application::EvaluatedInterpretation;pub use application::InterpretationInfo;pub use application::LanguageCardinality;pub use application::ParseStrategy;pub use application::RenderedInterpretation;pub use application::RenderedValue;pub use application::ResolvedRule;pub use astar::AstarOptions;pub use astar::AstarStats;pub use astar::PreparedAstarGrammar;pub use astar::astar_one_best;pub use astar::astar_one_best_with;pub use astar::astar_one_best_with_stats;pub use astar::astar_string_one_best_with_stats_prepared;pub use astar::materialize_astar_intersection;pub use astar::materialize_astar_intersection_with;pub use astar::materialize_astar_string_intersection_with_prepared;pub use astar::materialize_astar_viterbi_forest;pub use astar::materialize_astar_viterbi_forest_with;pub use codec::AltoTreeAutomatonInputCodec;pub use codec::CodecMetadata;pub use codec::DisplayCodec;pub use codec::FeatureStructureVisualizationCodec;pub use codec::InputCodec;pub use codec::InputCodecError;pub use codec::InputCodecRegistry;pub use codec::InputCodecRegistryError;pub use codec::IrtgInputCodec;pub use codec::OutputCodec;pub use codec::OutputCodecError;pub use codec::OutputCodecRegistry;pub use codec::RegisteredInputCodec;pub use codec::SpaceJoinCodec;pub use codec::TextOutputCodec;pub use codec::TextVisualizationCodec;pub use codec::TreeVisualizationCodec;pub use codec::VisualRepresentation;pub use codecs::TulipacError;pub use codecs::TulipacInputCodec;pub use combinators::Determinized;pub use combinators::InvHom;pub use combinators::Mapped;pub use combinators::Product;pub use control::ParseControl;pub use corpus::Corpus;pub use corpus::CorpusError;pub use corpus::CorpusWriter;pub use corpus::Instance;pub use corpus::read_corpus;pub use explicit::Explicit;pub use explicit::ExplicitBuildError;pub use explicit::ExplicitBuilder;pub use explicit::Rule;pub use heuristic::IntersectionHeuristic;pub use heuristic::MinHeuristic;pub use heuristic::OutsideHeuristic;pub use heuristic::ScoredZeroHeuristic;pub use heuristic::ZeroHeuristic;pub use homomorphism::HomLabel;pub use homomorphism::HomTerm;pub use homomorphism::Homomorphism;pub use homomorphism::HomomorphismError;pub use ids::Arity;pub use ids::StateId;pub use ids::Symbol;pub use interner::Interner;pub use irtg::AstarHeuristic;pub use irtg::EvaluatedAlgebraValue;pub use irtg::Interpretation;pub use irtg::Irtg;pub use irtg::IrtgError;pub use irtg::MaterializationStrategy;pub use irtg::NonNullFilteredChart;pub use irtg::ParseChart;pub use irtg::ParseInput;pub use irtg::TypedInterpretation;pub use irtg::parse_irtg;pub use materialize::IndexedCondensedIntersectionStats;pub use materialize::materialize;pub use materialize::materialize_indexed_condensed_intersection;pub use materialize::materialize_indexed_condensed_intersection_with_pairs;pub use materialize::materialize_topdown_condensed_intersection;pub use materialize::materialize_topdown_condensed_intersection_with_pairs;pub use memo::Memo;pub use memo::MemoStats;pub use obligatory_leaf::ObligatoryLeafHeuristic;pub use obligatory_leaf::ObligatoryLeafTables;pub use parseval::EvalbParamError;pub use parseval::EvalbParams;pub use parseval::ParsevalCounts;pub use parseval::ParsevalSkip;pub use parseval::compare_trees;pub use parseval::count_gold;pub use run::DetRun;pub use run::NonDetRun;pub use run::StateSet;pub use run::run_det;pub use run::run_nondet;pub use score::LogProbabilityScorer;pub use score::ProbabilityScorer;pub use score::WeightScorer;pub use set_trie::KeySet;pub use set_trie::SetTrie;pub use signature::Signature;pub use signature::SignatureError;pub use sorted_language::SortedLanguageIterator;pub use sorted_language::WeightedTree;pub use traits::BottomUpTa;pub use traits::CondensedTa;pub use traits::CondensedTopDownTa;pub use traits::DetBottomUpTa;pub use traits::IndexedBottomUpTa;pub use traits::StateUniverse;pub use traits::SymbolSet;pub use traits::TopDownTa;pub use viterbi::ViterbiTree;
Modules§
- algebras
- Algebra interfaces and decomposition automata.
- alto
- Reader for Alto’s textual finite-tree-automaton (
.auto) format. - alto_
ast - Shared AST and lexer for Alto-format automata and IRTGs.
- application
- Stable, owned presentation types for desktop and web frontends.
- astar
- A* intersection materializer for weighted tree automata.
- codec
- Typed input and output codecs.
- codecs
- Grammar and automaton input codecs.
- combinators
- Automaton combinators.
- control
- Cooperative cancellation for long-running parser operations.
- corpus
- Reading and writing Alto corpora.
- explicit
- Dense explicit weighted tree automata and their builder.
- heuristic
- Admissible heuristics for the A* intersection materializer.
- homomorphism
- Linear, nondeleting tree homomorphisms used by IRTG interpretations.
- ids
- Compact IDs for automaton states, ranked symbols, and arities.
- interner
- Stable interning from hashable values to dense
StateIds. - irtg
- Interpreted regular tree grammars.
- materialize
- Algorithms that explore implicit automata and materialize intersections.
- memo
- Memoizing adapter from rich implicit states to dense state IDs.
- obligatory_
leaf - Obligatory-leaf suffix filter — the F heuristic (Klein & Manning 2003,
adapted to the automaton-intersection setting; see
docs/f-heuristic-design.md). - parseval
- Fast EVALB-style Parseval scoring for constituency trees.
- run
- Deterministic and nondeterministic bottom-up automaton runners.
- score
- Rule-weight scoring conventions for Viterbi and A* algorithms.
- set_
trie - Trie index for matching tuples against sets of allowed keys.
- signature
- Ranked symbol signatures with stable dense symbol IDs.
- sorted_
language - Lazy k-best language iteration for explicit weighted tree automata.
- traits
- Core oracle traits for bottom-up, top-down, indexed, and condensed automata.
- viterbi
- One-best Viterbi extraction for explicit weighted tree automata.