xrel.analyzer
Class TA

java.lang.Object
  |
  +--xrel.analyzer.TA
All Implemented Interfaces:
java.lang.Cloneable, TABuildPhase
Direct Known Subclasses:
TADifference, TAProduct, TASimple, TAUnion

public abstract class TA
extends java.lang.Object
implements java.lang.Cloneable, TABuildPhase

Tree automata are just like normal string automata but elements are trees instead of characters. An automaton is a quadruple (Q,I,F,T) formed by a set Q of states, a subset I of Q that represents the set of the initial states, a subset F of Q that represents the set of final states and a set of transitions T.

Transitions can be either normal labeled transitions or epsilon (null) transitions. A normal labeled transition has the form:

   q1 = l[content] --> q2
and its meaning is: transit from state q1 to state q2 when the next input element is a tag with name "l" and with the specified content. An epsilon transition has the form:
   q1 --> q2
and its meaning is: non deterministically transit from state q1 to state q2.

Author:
Fabrizio Bisi

Field Summary
protected  boolean debug
           
protected  java.util.Vector epsilonTransitions
          epsilon or null transitions (this is a NFA).
protected  java.util.Vector finalStates
          the final states of the automaton.
protected  java.util.Vector initialStates
          the initial states of the automaton.
protected  boolean isBuilt
           
protected  java.lang.String name
          A unique name for each automaton.
protected  java.io.PrintStream out
           
protected  java.util.Vector states
          all the states of the automaton.
protected  SymTable symtab
           
protected  java.util.Vector transitions
          normal transitions of the NFA.
 
Fields inherited from interface xrel.analyzer.TABuildPhase
ALL_IN_ONE, DO_NOTHING, FULL_BUILD, SIMPLE_BUILD, STEP_BUILD, STEP_COMPLETE_AUT, STEP_NO_EPS_TRANS, STEP_NO_UNMATCHED_STATES, STEP_NO_UNREACH_STATES
 
Constructor Summary
TA(java.lang.String nm, SymTable st, boolean dbg, java.io.PrintStream psOut)
          Initializes an empty tree automaton.
 
Method Summary
protected  void addEpsTransition(TAState Q1, TAState Q2)
          Adds an epsilon transition from Q1 to Q2
protected  void addEpsTransitions(TAState Q, java.util.Vector V2)
          Adds epsilon transitions from state Q to every state in V2
protected  void addEpsTransitions(java.util.Vector V1, TAState Q)
          Adds epsilon transitions from every state in V1 to the state Q
protected  void addEpsTransitions(java.util.Vector V1, java.util.Vector V2)
          Adds epsilon transitions from every state in V1 to every state in V2
protected  void addState(TAState Q, int Flags)
           
protected  void addTrans(TAState Q1, TAState Q2, java.lang.String content, java.lang.String label, java.util.HashSet X)
           
abstract  void build()
          Subclasses must implement a matchTree function.
 java.lang.Object clone(java.lang.String newN)
          Duplicates the structure of the current automaton.
protected  void completeAutomaton()
          For each state set the Transition set and the flag isFinal.
protected  void compute_closures()
          For each state of the automaton compute the epsilon closure and update the information in the state object.
 void dump(java.io.PrintStream out)
          Writes out every information about the automaton.
protected  void epsilon_elimination()
          Eliminates the epsilon transitions from the automaton.
 boolean equals(java.lang.Object o)
          Two automata are equal if and only if they have the same internal name.
 void force(int BuildPhases)
           
 java.util.HashSet getChildAutomata()
          Returns the child automata, that is set of automata names specified in transitions but itself.
 java.util.HashSet getDescendantAutomata()
           
protected  java.lang.String getName()
           
 int hashCode()
          Redefines the HashCode function of Java using the hashing code of the string that represents the internal name.
 boolean isNull()
           
protected  void merge(TA A, int Flags)
          Merges the current automaton with another one.
 void remove_unmatched()
          Removes the unmatched states from the automaton.
protected  void remove_unreachable_states()
          Removes the unreachable states from the automaton.
 void setDebug(boolean dbg)
           
 void simplify()
           
 java.lang.String toString()
           
 void update(int BuildPhases)
           
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 

Field Detail

isBuilt

protected boolean isBuilt

symtab

protected SymTable symtab

debug

protected boolean debug

out

protected java.io.PrintStream out

name

protected java.lang.String name

A unique name for each automaton. It's used as a unique key to identify the automaton.

N.B.: two distinct automata with the same structure have distinct names.


states

protected java.util.Vector states
all the states of the automaton. They're TAState objects

initialStates

protected java.util.Vector initialStates
the initial states of the automaton. Note that it's a subset of the states of the automaton.

finalStates

protected java.util.Vector finalStates
the final states of the automaton. Note that it's subset of the states of the automaton.

epsilonTransitions

protected java.util.Vector epsilonTransitions
epsilon or null transitions (this is a NFA). They're TAEpsTransition objects.

transitions

protected java.util.Vector transitions
normal transitions of the NFA. They're TATransition objects. Note that the total number of transitions of an automaton is given by the number of normal transitions plus the number of the epsilon transitions.
Constructor Detail

TA

public TA(java.lang.String nm,
          SymTable st,
          boolean dbg,
          java.io.PrintStream psOut)
Initializes an empty tree automaton. Subclasses need to explicitly introduce one or more methods to build the automaton. Generally there is a method named build().
Method Detail

setDebug

public void setDebug(boolean dbg)

clone

public java.lang.Object clone(java.lang.String newN)

Duplicates the structure of the current automaton. Specifically it clones states and (consequently) transitions so that the resulting automaton will have different states.

States need to be unique for each automaton as they have internal status information (the isFinal flag and the exiting transitions); to mantain coherent the automaton transitions need to be remapped to new states so also transitions need to be changed, also if they could by itself to be shared between multiple automata (they don't have status information). If the flag isComplete is true this function calls completeAutomtaton() to update status information of the states.

Parameters:
A - the automaton to duplicate

getChildAutomata

public java.util.HashSet getChildAutomata()
Returns the child automata, that is set of automata names specified in transitions but itself.
Returns:
the set of child automata

getDescendantAutomata

public java.util.HashSet getDescendantAutomata()

build

public abstract void build()

Subclasses must implement a matchTree function.

TODO this function will presumably change.

Parameters:
value - the value to accept
Returns:
true if the value matches the automaton

getName

protected java.lang.String getName()

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object

equals

public boolean equals(java.lang.Object o)
Two automata are equal if and only if they have the same internal name. This is because each automaton has a unique internal name.
Overrides:
equals in class java.lang.Object
Parameters:
o - the object to compare to
Returns:
true if we have the same automaton
See Also:
Object.equals(java.lang.Object)

hashCode

public int hashCode()
Redefines the HashCode function of Java using the hashing code of the string that represents the internal name. I don't know if it's a good hashing functions but who cares?
Overrides:
hashCode in class java.lang.Object
Returns:
the hashing code of the automaton
See Also:
Object.hashCode()

simplify

public void simplify()

isNull

public boolean isNull()

update

public void update(int BuildPhases)

force

public void force(int BuildPhases)

compute_closures

protected void compute_closures()

For each state of the automaton compute the epsilon closure and update the information in the state object.

The epsilon closure of a state is the state itself plus all the states reachable with only epsilon transitions.

See Also:
TAState.set_epsClos(HashSet e_clos)

remove_unreachable_states

protected void remove_unreachable_states()

Removes the unreachable states from the automaton. Unreachable states are the states that can't be reached from the initial states.

Algorithm:

  1. Assign the initial states to the set of reachable states
  2. Add to the set of reachable states all the states reachable in a step that are not yet in the set
  3. Repeat step 2 until there are no more states to add to the set
  4. Discard the remaining states and update the set of final states

N.B.:


epsilon_elimination

protected void epsilon_elimination()

Eliminates the epsilon transitions from the automaton.

Algorithm:

  1. Add to the set of final states each state that has a final state in its epsilon closure
  2. Add to each state the exiting transitions that exit from all the states in its epsilon closure

Note that this is the standard algorithm you can find also in string automata.

N.B.:


completeAutomaton

protected void completeAutomaton()
For each state set the Transition set and the flag isFinal.

remove_unmatched

public void remove_unmatched()

Removes the unmatched states from the automaton. Unmatched states are states that can't be matched by any value.

Algorithm:

The intuition is to proceed backward from final states and mark all visited states. Note that this is the reverted remove_unreachable algorithm (that is remove_unreachable proceeds forward from initial states to final states, as remove_unmatched proceeds backward from final states to initial states)

In details:

  1. Assign the final states to the set of matchable states
  2. Add to the set of matchable states all the states that take in a matchable state in a step and that are not yet in the set
  3. Repeat step 2 until there are no more states to add to the set
  4. Discard the remaining states and update the set of initial states


dump

public void dump(java.io.PrintStream out)

Writes out every information about the automaton.

Specifically:

Parameters:
out - the stream to which print out

addState

protected void addState(TAState Q,
                        int Flags)

addTrans

protected void addTrans(TAState Q1,
                        TAState Q2,
                        java.lang.String content,
                        java.lang.String label,
                        java.util.HashSet X)

addEpsTransition

protected void addEpsTransition(TAState Q1,
                                TAState Q2)
Adds an epsilon transition from Q1 to Q2

addEpsTransitions

protected void addEpsTransitions(java.util.Vector V1,
                                 java.util.Vector V2)
Adds epsilon transitions from every state in V1 to every state in V2

addEpsTransitions

protected void addEpsTransitions(java.util.Vector V1,
                                 TAState Q)
Adds epsilon transitions from every state in V1 to the state Q

addEpsTransitions

protected void addEpsTransitions(TAState Q,
                                 java.util.Vector V2)
Adds epsilon transitions from state Q to every state in V2

merge

protected void merge(TA A,
                     int Flags)

Merges the current automaton with another one. This function must be used only internally to build a bigger automaton from two subpieces that will be thrown away. To merge two complete automata that you want use indipendently use the function union.

Note that this function let you copy only a part of the source automaton with the parameter Flags. To copy the whole automaton use

TAPiece.STATES | TAPiece.INITIAL | TAPiece.FINAL | TAPiece.TRANS

Parameters:
A - the automaton to merge with the current one
Flags - the parts of A to copy (see above)