Package pyxb :: Package utils :: Module fac :: Class Node

Class Node

object --+
         |
        Node

Known Subclasses:

Abstract class for any node in the term tree.

In its original form a position (pos) is a tuple of non-negative integers comprising a path from a node in the term tree. It identifies a node in the tree. After the FAC has been constructed, only positions that are leaf nodes in the term tree remain, and the corresponding symbol value (Python instance) is used as the position.

An update instruction (psi) is a map from positions to either Node.RESET or Node.INCREMENT. It identifies actions to be taken on the counter states corresponding to the positions in its domain.

A transition is a pair containing a position and an update instruction. It identifies a potential next node in the state and the updates that are to be performed if the transition is taken.

A follow value is a map from a position to a set of transitions that may originate from the pos. This set is represented as a Python list since update instructions are dicts and cannot be hashed.

Instance Methods

[hide private]

__init__(self, **kw)
Create a FAC term-tree node.

source code

clone(self, *args, **kw)
Create a deep copy of the node.

source code

__get_metadata(self)
Application-specific metadata provided during construction.

source code

__get_first(self)
The first set for the node.

source code

_first(self)
Abstract method that defines first for the subclass.

source code

__get_last(self)
The last set for the node.

source code

_last(self)
Abstract method that defines last for the subclass.

source code

__get_nullable(self)
True iff the empty string is accepted by this node. source code

_nullable(self)
Abstract method that defines nullable for the subclass.

source code

__get_follow(self)
The follow map for the node.

source code

_follow(self)
Abstract method that defines follow for the subclass.

source code

reset(self)
Reset any term-tree state associated with the node.

source code

walkTermTree(self, pre, post, arg)
Utility function for term tree processing.

source code

_walkTermTree(self, position, pre, post, arg)
Abstract method implementing walkTermTree for the subclass.

source code

__get_posNodeMap(self)
A map from positions to nodes in the term tree.

source code

__get_nodePosMap(self)
A map from nodes to their position in the term tree.

source code

__resetAndValidate(self, node, pos, visited_nodes)

source code

buildAutomaton(self, state_ctor=<class 'pyxb.utils.fac.State'>, ctr_cond_ctor=<class 'pyxb.utils.fac.CounterCondition'>, containing_state=None)

source code

__get_counterPositions(self)
Implement definition 13.1 from HOV09.

source code

counterSubPositions(self, pos)
Implement definition 13.2 from HOV09.

source code

_facToString(self)
Obtain a description of the FAC in text format.

source code

Inherited from object: __delattr__, __format__, __getattribute__, __hash__, __new__, __reduce__, __reduce_ex__, __repr__, __setattr__, __sizeof__, __str__, __subclasshook__

Class Methods

[hide private]

_PosConcatPosSet(cls, pos, pos_set)
Implement definition 11.1 in HOV09.

source code

_PosConcatUpdateInstruction(cls, pos, psi)
Implement definition 11.2 in HOV09

source code

_PosConcatTransitionSet(cls, pos, transition_set)
Implement definition 11.3 in HOV09

source code

Class Variables

[hide private]

_Precedence = None
An integral value used for parenthesizing expressions.

RESET = False
An arbitrary value representing reset of a counter.

INCREMENT = True
An arbitrary value representing increment of a counter.

__metadata = None
hash(x)

__first = None
hash(x)

__last = None
hash(x)

__nullable = None
hash(x)

__follow = None
hash(x)

__posNodeMap = None
hash(x)

__nodePosMap = None
hash(x)

__counterPositions = None
hash(x)

Properties

[hide private]

metadata
Application-specific metadata provided during construction.

first
The first set for the node.

last
The last set for the node.

nullable
True iff the empty string is accepted by this node.

follow
The follow map for the node.

posNodeMap
A map from positions to nodes in the term tree.

nodePosMap
A map from nodes to their position in the term tree.

counterPositions
Implement definition 13.1 from HOV09.

Inherited from object: __class__

Method Details

[hide private]

init(self, **kw)
(Constructor)

source code

Create a FAC term-tree node.

Parameters:

metadata - Any application-specific metadata retained in the term tree for transfer to the resulting automaton.

Overrides: object.__init__

clone(self, *args, **kw)

source code

Create a deep copy of the node.

All term-tree--related attributes and properties are replaced with deep clones. Other attributes are preserved.

Parameters:

args - A tuple of arguments to be passed to the instance constructor.
kw - A dict of keywords to be passed to the instance constructor.

Note: Subclasses should pre-extend this method to augment the args and kw parameters as necessary to match the expectations of the __init__ method of the class being cloned.

__get_first(self)

source code

The first set for the node.

This is the set of positions leading to symbols that can appear first in a string matched by an execution starting at the node.

_first(self)

source code

Abstract method that defines first for the subclass.

The return value should be an iterable of tuples of integers denoting paths from this node through the term tree to a symbol.

__get_last(self)

source code

The last set for the node.

This is the set of positions leading to symbols that can appear last in a string matched by an execution starting at the node.

_last(self)

source code

Abstract method that defines last for the subclass.

The return value should be an iterable of tuples of integers denoting paths from this node through the term tree to a symbol.

_nullable(self)

source code

Abstract method that defines nullable for the subclass.

The return value should be True or False.

_follow(self)

source code

Abstract method that defines follow for the subclass.

The return value should be a map from tuples of integers (positions) to a list of transitions, where a transition is a position and an update instruction.

reset(self)

source code

Reset any term-tree state associated with the node.

Any change to the structure of the term tree in which the node appears invalidates memoized first/follow sets and related information. This method clears all that data so it can be recalculated. It does not clear the metadata link, or any existing structural data.

walkTermTree(self, pre, post, arg)

source code

Utility function for term tree processing.

Parameters:

pre - a callable that, unless None, is invoked at each node n with parameters n, pos, and arg, where pos is the tuple of integers identifying the path from the node at on which this method was invoked to the node being processed. The invocation occurs before processing any subordinate nodes.
post - as with pre but invocation occurs after processing any subordinate nodes.
arg - a value passed to invocations of pre and post.

__get_counterPositions(self)

source code

Implement definition 13.1 from HOV09.

The return value is the set of all positions leading to NumericalConstraint nodes for which either the minimum value is not 1 or the maximum value is not unbounded.

counterSubPositions(self, pos)

source code

Implement definition 13.2 from HOV09.

This is the subset of counterPositions that occur along the path to pos.

_facToString(self)

source code

Obtain a description of the FAC in text format.

This is a diagnostic tool, returning first, last, and follow maps using positions.

Class Variable Details

[hide private]

_Precedence

An integral value used for parenthesizing expressions.

A subterm that has a precedence less than that of its containing term must be enclosed in parentheses when forming a text expression representing the containing term.

Value:

None

Property Details

[hide private]

metadata

Application-specific metadata provided during construction.

Get Method:: __get_metadata(self) - Application-specific metadata provided during construction.

first

The first set for the node.

This is the set of positions leading to symbols that can appear first in a string matched by an execution starting at the node.

Get Method:: __get_first(self) - The first set for the node.

last

The last set for the node.

This is the set of positions leading to symbols that can appear last in a string matched by an execution starting at the node.

Get Method:: __get_last(self) - The last set for the node.

nullable

True iff the empty string is accepted by this node.

Get Method:: __get_nullable(self) - True iff the empty string is accepted by this node.

follow

The follow map for the node.

Get Method:: __get_follow(self) - The follow map for the node.

posNodeMap

A map from positions to nodes in the term tree.

Get Method:: __get_posNodeMap(self) - A map from positions to nodes in the term tree.

nodePosMap

A map from nodes to their position in the term tree.

Get Method:: __get_nodePosMap(self) - A map from nodes to their position in the term tree.

counterPositions

Implement definition 13.1 from HOV09.

The return value is the set of all positions leading to NumericalConstraint nodes for which either the minimum value is not 1 or the maximum value is not unbounded.

Get Method:: __get_counterPositions(self) - Implement definition 13.1 from HOV09.

Class Node

__init__(self, **kw) (Constructor)

clone(self, *args, **kw)

__get_first(self)

_first(self)

__get_last(self)

_last(self)

_nullable(self)

_follow(self)

reset(self)

walkTermTree(self, pre, post, arg)

__get_counterPositions(self)

counterSubPositions(self, pos)

_facToString(self)

_Precedence

metadata

first

last

nullable

follow

posNodeMap

nodePosMap

counterPositions

init(self, **kw)
(Constructor)