var searchIndex = {};
searchIndex["cfg"] = {"doc":"Library for manipulations on context-free grammars. Most transformations are abstracted over\ngrammar representations.","items":[[3,"BinarizedCfg","cfg","Representation for grammars where right-hand sides of all rules have at most two symbols.",null,null],[3,"Cfg","","Basic representation of context-free grammars.",null,null],[3,"Symbol","","A common grammar symbol type.",null,null],[11,"clone","","",0,null],[11,"new","","Creates a BinarizedCfg.",0,{"inputs":[],"output":{"name":"self"}}],[11,"with_sym_source","","Creates an empty BinarizedCfg with the given symbol source.",0,{"inputs":[{"name":"symbolsource"}],"output":{"name":"self"}}],[11,"from_context_free","","Creates a BinarizedCfg by binarizing a context-free grammar.",0,{"inputs":[{"name":"g"}],"output":{"name":"binarizedcfg"}}],[11,"sort","","Sorts the rule array.",0,null],[11,"sort_by","","Sorts the rule array in place, using the argument to compare elements.",0,null],[11,"dedup","","Removes consecutive duplicate rules.",0,null],[11,"sym","","Returns generated symbols.",0,null],[11,"next_sym","","Generates a new unique symbol.",0,null],[11,"num_syms","","Returns the number of symbols in use.",0,null],[11,"eliminate_nulling_rules","","Eliminates all rules of the form `A ::= epsilon`.",0,null],[11,"sym_source","","",0,null],[11,"sym_source_mut","","",0,null],[11,"retain","","",0,null],[11,"add_rule","","",0,null],[0,"cycles","","Cycle detection and elimination.",null,null],[3,"Cycles","cfg::cycles","Provides information about cycles among unit derivations in the grammar. There are two ways of\npruning cycles.",null,null],[3,"CycleParticipants","","An iterator over the grammar's useless rules.",null,null],[11,"new","","Analyzes the grammar's cycles.",1,{"inputs":[{"name":"g"}],"output":{"name":"cycles"}}],[11,"cycle_free","","Checks whether the grammar is cycle-free.",1,null],[11,"cycle_participants","","Iterates over rules that participate in a cycle.",1,null],[11,"remove_cycles","","Removes all rules that participate in a cycle. Doesn't preserve the language represented\nby the grammar.",1,null],[11,"rewrite_cycles","","Rewrites all rules that participate in a cycle. Preserves the language represented\nby the grammar.",1,null],[11,"next","","",2,null],[11,"clone","cfg","",3,null],[11,"new","","Creates an empty context-free grammar.",3,{"inputs":[],"output":{"name":"self"}}],[11,"with_sym_source","","Creates an empty context-free grammar with the given symbol source.",3,{"inputs":[{"name":"symbolsource"}],"output":{"name":"self"}}],[11,"sym","","Returns generated symbols.",3,null],[11,"next_sym","","Generates a new unique symbol.",3,null],[11,"num_syms","","Returns the number of symbols in use.",3,null],[11,"sequence","","Starts building a sequence rule.",3,null],[11,"sequence_rules","","Returns sequence rules.",3,null],[11,"rewrite_sequences","","Forces a rewrite of sequence rules into grammar rules.",3,null],[11,"binarize","","Returns a binarized grammar which is weakly equivalent to this grammar.",3,null],[11,"sym_source","","",3,null],[11,"sym_source_mut","","",3,null],[11,"retain","","",3,null],[11,"add_rule","","",3,null],[0,"history","","Any data carried alongside a grammar rule can be its _history_. Rule histories may contain\nmore than semantic actions.",null,null],[3,"NullHistory","cfg::history","A history which carries no data. All operations on `NullHistory` are no-op.",null,null],[3,"CloneHistory","","Clone history.",null,null],[3,"DefaultHistory","","Factory of default histories.",null,null],[3,"NullHistorySource","","A source that only works for building NullHistory.",null,null],[4,"BinarizedRhsSubset","","Used to inform which symbols on a rule'Symbol RHS are nullable, and will be eliminated.",null,null],[13,"Left","","The first of two symbols.",4,null],[13,"Right","","The second of two symbols.",4,null],[13,"All","","All 1 or 2 symbols. The rule is nullable.",4,null],[8,"Action","","Trait for history types that may have semantic actions.",null,null],[10,"no_op","","Returns a history with no-op semantic action.",5,null],[8,"Binarize","","Trait for history types that allow the rule to be binarized.",null,null],[10,"binarize","","Returns a history. May record the binarization.",6,null],[8,"EliminateNulling","","Trait for history types that allow the rule to have nulling symbols\neliminated from the RHS.",null,null],[10,"eliminate_nulling","","Returns a history. May record the elimination.",7,null],[8,"AssignPrecedence","","Trait for history types that allow the rule to have its precedence assigned.",null,null],[10,"assign_precedence","","Returns a history. May record the precedence.",8,null],[8,"RewriteSequence","","Trait for history types that allow the sequence rule to be rewritten into grammar rules.",null,null],[16,"Rewritten","","Must be an `Action`, because all created grammar rules except the topmost one will have\nno-op semantic action.",9,null],[10,"top","","Returns a history. May record the rewrite.",9,null],[10,"bottom","","Returns a history. May record the rewrite.",9,null],[8,"HistorySource","","A trait for history factories.",null,null],[10,"build","","Create a history.",10,null],[11,"clone","","",4,null],[11,"default","","",11,{"inputs":[],"output":{"name":"nullhistory"}}],[11,"fmt","","",11,null],[11,"clone","","",11,null],[11,"no_op","","",11,null],[11,"binarize","","",11,null],[11,"eliminate_nulling","","",11,null],[11,"assign_precedence","","",11,null],[11,"top","","",11,null],[11,"bottom","","",11,null],[11,"new","","Creates a cloned history factory.",12,{"inputs":[{"name":"h"}],"output":{"name":"self"}}],[11,"build","","",12,null],[11,"new","","Creates a default history factory.",13,{"inputs":[],"output":{"name":"self"}}],[11,"build","","",13,null],[11,"clone","","",14,null],[11,"build","","",14,null],[0,"precedence","cfg","Precedenced rules are built with the builder pattern.",null,null],[3,"PrecedencedRuleBuilder","cfg::precedence","Precedenced rules are built in series of rule alternatives with equal precedence.",null,null],[4,"Associativity","","Specifies the associativity of an operator.",null,null],[13,"Left","","Left associative.",15,null],[13,"Right","","Right associative.",15,null],[13,"Group","","`Group` usually means the operand is delimited, e.g. by parentheses.",15,null],[11,"eq","","",15,null],[11,"clone","","",15,null],[11,"new","","Returns a precedenced rule builder.",16,{"inputs":[{"name":"d"},{"name":"symbol"}],"output":{"name":"self"}}],[11,"default_history","","Sets the default history source.",16,null],[11,"precedenced_rule","","Starts building a new precedenced rule. The differences in precedence among rules only\nmatter within a particular precedenced rule.",16,null],[11,"rule","","Starts building a new grammar rule.",16,null],[11,"history","","Assigns the rule history, which is used on the next call to `rhs`, unless overwritten by\na call to `rhs_with_history`.",16,null],[11,"rhs","","Creates a rule alternative. If history wasn't provided, the rule has the `Default` history.",16,null],[11,"rhs_with_history","","Creates a rule alternative with the given RHS and history.",16,null],[11,"associativity","","Assigns the associativity, which influences the next call to `rhs` or `rhs_with_history`.",16,null],[11,"lower_precedence","","Assigns lower precedence to rule alternatives that are built after this call.",16,null],[11,"drop","","",16,null],[0,"prediction","cfg","Prediction for predictive parsers.",null,null],[3,"MinimalDistance","cfg::prediction","Calculation of minimum distance from one part of the grammar to another.\nSimilar to multi-source shortest path search in a graph.",null,null],[3,"FirstSets","","FIRST sets.",null,null],[3,"FollowSets","","FOLLOW sets.",null,null],[11,"new","","Returns a new `MinimalDistance` for a grammar.",17,{"inputs":[{"name":"g"}],"output":{"name":"self"}}],[11,"distances","","Returns distances in order respective to the order of rule iteration.",17,null],[11,"minimal_distances","","Calculates minimal distance from one parts of the grammar to others.\nReturns distances in order respective to the order of rule iteration.",17,null],[11,"new","","Compute all FIRST sets of the grammar.",18,{"inputs":[{"name":"g"}],"output":{"name":"self"}}],[11,"first_sets","","Returns a reference to FIRST sets.",18,null],[11,"new","","Compute all FOLLOW sets of the grammar.\nReturns FollowSets.",19,{"inputs":[{"name":"g"},{"name":"symbol"},{"name":"firstsets"}],"output":{"name":"self"}}],[11,"follow_sets","","Returns a reference to FOLLOW sets.",19,null],[6,"PerSymbolSets","","The representation of FIRST and FOLLOW sets.",null,null],[0,"remap","cfg","Remaps symbols and removes unused symbols.",null,null],[3,"Remap","cfg::remap","Remaps symbols and removes unused symbols.",null,null],[3,"Mapping","","Contains maps for translation between internal and external symbols.",null,null],[12,"to_internal","","An array of internal symbols, indexed by external symbol ID.",20,null],[12,"to_external","","An array of external symbols, indexed by internal symbol ID.",20,null],[11,"new","","Creates `Remap` to record information about remapped symbols.",21,{"inputs":[{"name":"g"}],"output":{"name":"self"}}],[11,"remove_unused_symbols","","Removes unused symbols.",21,null],[11,"reorder_symbols","","Remaps symbols to satisfy given ordering constraints. The argument\nmust be a function that gives total order.",21,null],[11,"get_mapping","","Get the mapping.",21,null],[11,"new","","Creates a new instance of `Mapping`.",20,{"inputs":[{"name":"usize"}],"output":{"name":"self"}}],[11,"translate","","Translates symbols in this map using another symbol map.\nThis map becomes a combination of both mappings.",20,null],[0,"rule","cfg","This module defines grammar rules. Each rule in a context-free grammar\nconsists of a single symbol on its left-hand side and an array of symbols\non its right-hand side. In this library, each rule carries additional\nvalue called "history."",null,null],[3,"Rule","cfg::rule","Typical grammar rule representation.",null,null],[12,"rhs","","The rule's right-hand side.",22,null],[12,"history","","The rule's history.",22,null],[3,"RuleRef","","References rule's components.",null,null],[12,"lhs","","Left-hand side.",23,null],[12,"rhs","","Right-hand side.",23,null],[12,"history","","The rule's history.",23,null],[0,"builder","","Grammar rules can be built with the builder pattern.",null,null],[3,"RuleBuilder","cfg::rule::builder","The rule builder.",null,null],[11,"new","","Creates a rule builder.",24,{"inputs":[{"name":"c"}],"output":{"name":"rulebuilder"}}],[11,"default_history","","Sets the default history source.",24,null],[11,"rule","","Starts building a new rule with the given LHS.",24,null],[11,"history","","Assigns the rule history, which is used on the next call to `rhs`, or overwritten by a call\nto`rhs_with_history`.",24,null],[11,"rhs","","Adds a rule alternative to the grammar. If history wasn't provided, the rule has the\n`Default` history.",24,null],[11,"rhs_with_history","","Adds a rule alternative with the given RHS and history to the grammar.",24,null],[11,"precedenced_rule","","Starts building a new precedenced rule.",24,null],[0,"container","cfg::rule","Abstraction for collections of rules.",null,null],[8,"RuleContainer","cfg::rule::container","Trait for rule and symbol containers.",null,null],[16,"History","","The type of history carried with the rule.",25,null],[10,"sym_source","","Returns an immutable reference to the grammar's symbol source.",25,null],[10,"sym_source_mut","","Returns a mutable reference to the grammar's symbol source.",25,null],[11,"sym","","Returns generated symbols.",25,null],[11,"next_sym","","Generates a new unique symbol.",25,null],[11,"num_syms","","Returns the number of symbols in use.",25,null],[10,"retain","","Retains only the rules specified by the predicate.",25,null],[10,"add_rule","","Inserts a rule with `lhs` and `rhs` on its LHS and RHS. The rule carries `history`.",25,null],[8,"GrammarRule","cfg::rule","Trait for rules of a context-free grammar.",null,null],[16,"History","","The type of history carried with the rule.",26,null],[10,"lhs","","Returns the rule's left-hand side.",26,null],[10,"rhs","","Returns the rule's right-hand side.",26,null],[10,"history","","Returns a reference to the history carried with the rule.",26,null],[11,"fmt","","",22,null],[11,"clone","","",22,null],[11,"lhs","","",22,null],[11,"rhs","","",22,null],[11,"history","","",22,null],[11,"new","","Creates a new rule.",22,{"inputs":[{"name":"symbol"},{"name":"vec"},{"name":"h"}],"output":{"name":"self"}}],[11,"clone","","",23,null],[11,"lhs","","",23,null],[11,"rhs","","",23,null],[11,"history","","",23,null],[0,"sequence","cfg","Sequences are similar to regex repetitions with numbering.",null,null],[3,"Sequence","cfg::sequence","Sequence rule representation.",null,null],[12,"lhs","","The rule's left-hand side.",27,null],[12,"rhs","","The rule's right-hand side.",27,null],[12,"start","","The minimum number of repetitions.",27,null],[12,"end","","Either the inclusive maximum number of repetitions, or `None` if the number of repetitions\nis unlimited.",27,null],[12,"separator","","The way elements are separated in a sequence, or `Null`.",27,null],[12,"history","","The history carried with the sequence rule.",27,null],[4,"Separator","","The separator symbol and mode of separation in a sequence, or `Null` for no separation.",null,null],[13,"Trailing","","Separation with the trailing separator included. In other words, all elements are followed\nby the separator.",28,null],[13,"Proper","","The separator occurs between elements.",28,null],[13,"Liberal","","The union of `Trailing` and `Proper`. In other words, the trailing separator may or may not\nbe present.",28,null],[13,"Null","","No separation.",28,null],[0,"builder","","Sequence rules can be built with the builder pattern.",null,null],[3,"SequenceRuleBuilder","cfg::sequence::builder","Sequence rule builder.",null,null],[11,"new","","Creates a sequence rule builder.",29,{"inputs":[{"name":"d"}],"output":{"name":"self"}}],[11,"default_history","","Sets the default history source.",29,null],[11,"sequence","","Starts building a sequence rule.",29,null],[11,"separator","","Assigns the separator symbol and mode of separation.",29,null],[11,"intersperse","","Sets proper separation with the given separator symbol.",29,null],[11,"history","","Assigns the rule history, which is used on the next call to `rhs`, or overwritten by a call\nto `rhs_with_history`.",29,null],[11,"inclusive","","Assigns the inclusive range of the number of repetitions.",29,null],[11,"rhs","","Adds a sequence rule to the grammar.",29,null],[11,"rhs_with_history","","Adds a sequence rule to the grammar.",29,null],[0,"destination","cfg::sequence","Sequence destination.",null,null],[8,"SequenceDestination","cfg::sequence::destination","Trait for storing sequence rules in containers, with potential rewrites.",null,null],[10,"add_sequence","","Inserts a sequence rule.",30,null],[0,"rewrite","cfg::sequence","Rewrites sequence rules into production rules.",null,null],[3,"SequencesToProductions","cfg::sequence::rewrite","Rewrites sequence rules into production rules.",null,null],[11,"add_sequence","","",31,null],[11,"new","","Initializes a rewrite.",31,{"inputs":[{"name":"d"}],"output":{"name":"self"}}],[11,"rewrite_sequences","","Rewrites sequence rules.",31,null],[11,"rewrite","","Rewrites a sequence rule.",31,null],[11,"eq","cfg::sequence","",27,null],[11,"ne","","",27,null],[11,"hash","","",27,null],[11,"fmt","","",27,null],[11,"clone","","",27,null],[11,"eq","","",28,null],[11,"ne","","",28,null],[11,"hash","","",28,null],[11,"fmt","","",28,null],[11,"clone","","",28,null],[11,"inclusive","","Assigns the inclusive range of the number of repetitions.",27,null],[11,"separator","","Assigns the separator symbol and mode of separation.",27,null],[11,"prefix_separator","","Returns the kind of separation for a prefix sequence.",28,null],[11,"into","","",28,null],[0,"symbol","cfg","A type that can represent symbols in a context-free grammar. Symbols are distinguished by their\nIDs.",null,null],[3,"Symbol","cfg::symbol","A common grammar symbol type.",null,null],[11,"partial_cmp","cfg","",32,null],[11,"lt","","",32,null],[11,"le","","",32,null],[11,"gt","","",32,null],[11,"ge","","",32,null],[11,"eq","","",32,null],[11,"ne","","",32,null],[11,"cmp","","",32,null],[11,"hash","","",32,null],[11,"fmt","","",32,null],[11,"clone","","",32,null],[11,"from","","",32,{"inputs":[{"name":"symbolrepr"}],"output":{"name":"self"}}],[11,"into","","",32,null],[0,"set","cfg::symbol","Informs whether symbols are terminal or nonterminal.",null,null],[3,"SymbolBitSet","cfg::symbol::set","A set of symbols in the form of a bit vector.",null,null],[3,"Iter","","An iterator over a symbol set.",null,null],[11,"new","","Constructs a `SymbolBitSet`.",33,{"inputs":[{"name":"g"},{"name":"bool"}],"output":{"name":"self"}}],[11,"terminal_set","","Gathers information about whether symbols are terminal or nonterminal.\nConstructs a set of terminal symbols.",33,{"inputs":[{"name":"g"}],"output":{"name":"self"}}],[11,"has_sym","","Checks whether a given symbol is in this set.",33,null],[11,"into_bit_vec","","Converts into a bit vector.",33,null],[11,"iter","","Iterates over symbols in the set.",33,null],[11,"next","","",34,null],[0,"source","cfg::symbol","Source",null,null],[3,"SymbolSource","cfg::symbol::source","A source of numeric symbols.",null,null],[3,"Generate","","Iterator for generating symbols.",null,null],[8,"SymbolContainer","","Trait used to generate symbols.",null,null],[10,"generate","","Generates symbols.",35,{"inputs":[{"name":"symbolsource"}],"output":{"name":"self"}}],[11,"fmt","","",36,null],[11,"clone","","",36,null],[11,"new","","Creates a source of numeric symbols with an empty symbol space.",36,{"inputs":[],"output":{"name":"self"}}],[11,"sym","","Returns generated symbols.",36,null],[11,"next_sym","","Generates a new unique symbol.",36,null],[11,"num_syms","","Returns the number of symbols in use.",36,null],[11,"generate","","Returns an iterator that generates symbols.",36,null],[11,"generate","cfg","",32,{"inputs":[{"name":"symbolsource"}],"output":{"name":"self"}}],[11,"next","cfg::symbol::source","",37,null],[11,"usize","cfg","Cast the symbol's ID to `usize`.",32,null],[11,"from","","",32,{"inputs":[{"name":"usize"}],"output":{"name":"self"}}],[11,"into","","",32,null],[0,"usefulness","","Analysis of rule usefulness.",null,null],[3,"Usefulness","cfg::usefulness","Contains the information about usefulness of the grammar's rules.\nUseful rules are both reachable and productive.",null,null],[3,"UselessRules","","An iterator over the grammar's useless rules.",null,null],[3,"UselessRule","","A reference to a useless rule, together with the reason for its uselessness.",null,null],[12,"rule","","Reference to a rule.",38,null],[12,"unreachable","","Indicates whether the rule is unreachable.",38,null],[12,"unproductive","","Indicates whether the rule is unproductive.",38,null],[11,"fmt","","",38,null],[11,"clone","","",38,null],[11,"new","","Analyzes usefulness of the grammar's rules. In particular, it checks for reachable\nand productive symbols.",39,{"inputs":[{"name":"g"}],"output":{"name":"usefulness"}}],[11,"productivity","","Checks whether a symbol is productive. Can be used to determine the precise reason\nof a rule's unproductiveness.",39,null],[11,"reachable","","Sets symbol reachability. Takes an array of reachable symbols.",39,null],[11,"all_useful","","Checks whether all rules in the grammar are useful.",39,null],[11,"all_productive","","Checks whether all rules in the grammar are productive.",39,null],[11,"useless_rules","","Returns an iterator over the grammar's useless rules.",39,null],[11,"remove_useless_rules","","Removes useless rules. The language represented by the grammar doesn't change.",39,null],[11,"next","","",40,null],[8,"ContextFree","cfg","Trait for context-free grammars.",null,null],[11,"rule","","Starts building a new rule.",41,null],[11,"precedenced_rule","","Starts building a new precedenced rule.",41,null],[8,"ContextFreeRef","","This trait is currently needed to make the associated `Rules` iterator generic over a lifetime\nparameter.",null,null],[16,"RuleRef","","Immutable reference to a rule.",42,null],[16,"Rules","","Iterator over immutable references to the grammar's rules.",42,null],[10,"rules","","Returns an iterator over immutable references to the grammar's rules.",42,null],[8,"ContextFreeMut","","Allows access to a ContextFreeRef through mutable references.",null,null],[11,"rule","","Starts building a new rule.",41,null],[11,"precedenced_rule","","Starts building a new precedenced rule.",41,null]],"paths":[[3,"BinarizedCfg"],[3,"Cycles"],[3,"CycleParticipants"],[3,"Cfg"],[4,"BinarizedRhsSubset"],[8,"Action"],[8,"Binarize"],[8,"EliminateNulling"],[8,"AssignPrecedence"],[8,"RewriteSequence"],[8,"HistorySource"],[3,"NullHistory"],[3,"CloneHistory"],[3,"DefaultHistory"],[3,"NullHistorySource"],[4,"Associativity"],[3,"PrecedencedRuleBuilder"],[3,"MinimalDistance"],[3,"FirstSets"],[3,"FollowSets"],[3,"Mapping"],[3,"Remap"],[3,"Rule"],[3,"RuleRef"],[3,"RuleBuilder"],[8,"RuleContainer"],[8,"GrammarRule"],[3,"Sequence"],[4,"Separator"],[3,"SequenceRuleBuilder"],[8,"SequenceDestination"],[3,"SequencesToProductions"],[3,"Symbol"],[3,"SymbolBitSet"],[3,"Iter"],[8,"SymbolContainer"],[3,"SymbolSource"],[3,"Generate"],[3,"UselessRule"],[3,"Usefulness"],[3,"UselessRules"],[8,"ContextFree"],[8,"ContextFreeRef"]]};
initSearch(searchIndex);