Package pyxb :: Package utils :: Module fac
[hide private]
[frames] | no frames]

Module fac

source code

This module provides Finite Automata with Counters.

FACs are type of state machine where a transition may include a constraint and a modification to a set of counters. They are used to implement regular expressions with numerical constraints, as are found in POSIX regexp, Perl, and XML schema.

The implementation here derives from Regular Expressions with Numerical Constraints and Automata with Counters, Dag Hovland, Lecture Notes in Computer Science, 2009, Volume 5684, Theoretical Aspects of Computing - ICTAC 2009, Pages 231-245. In what follows, this reference will be denoted HOV09.

A regular expression is directly translated into a term tree, where nodes are operators such as sequence, choice, and counter restrictions, and the leaf nodes denote symbols in the language of the regular expression.

In the case of XML content models, the symbols include element declarations and wildcard elements. A numerical constraint node corresponds to an XML particle, and choice and sequence nodes derive from model groups of types choice and sequence. As suggested in The Membership Problem for Regular Expressions with Unordered Concatenation and Numerical Constraints the all content model can be translated into state machine using choice and sequence at the cost of a quadratic size explosion. Since some XML content models might have a hundred terms in an unordered catenation, this is not acceptable, and the implementation here optimizes this construct by creating a leaf node in the automaton which in turn contains sub-automata for each term, and permits an exit transition only when all the terms that are required have been completed.

Note: In XSD 1.1 the restriction that terms in an all model group occur at most once has been removed. Since the current implementation removes a completed term from the set of available terms, this will not work: instead the subconfiguration with its counter values must be retained between matches.

Classes [hide private]
Exception raised when a FAC term tree is not a tree.
Exception raised when an unsatisfied update instruction is executed.
Symbol rejected by Configuration_ABC.step.
Configuration.step failed to find a valid transition.
Configuration.step found multiple transitions.
Mix-in used by symbols to provide a custom match implementation.
A thin wrapper around an object reference.
A counter condition is a range limit on valid counter values.
An update instruction pairs a counter with a mutation of that counter.
Representation of a FAC state transition.
Base class for something that represents an Automaton in execution.
The state of an Automaton in execution.
Support parallel execution of state machine.
Representation of a Finite Automaton with Counters.
Abstract class for any node in the term tree.
Intermediary for nodes that have multiple child nodes.
Intermediary for nodes that have no child nodes.
A term with a numeric range constraint.
A term that may be any one of a set of terms.
A term that is an ordered sequence of terms.
A term that is an unordered sequence of terms.
A leaf term that is a symbol.
Variables [hide private]
  log_ = <logging.Logger object>
  __package__ = 'pyxb.utils'