|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--xrel.analyzer.TA
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:
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 = l[content] --> q2
and its meaning is: non deterministically transit from state q1 to state q2.q1 --> q2
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 |
protected boolean isBuilt
protected SymTable symtab
protected boolean debug
protected java.io.PrintStream out
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.
protected java.util.Vector states
protected java.util.Vector initialStates
protected java.util.Vector finalStates
protected java.util.Vector epsilonTransitions
protected java.util.Vector transitions
Constructor Detail |
public TA(java.lang.String nm, SymTable st, boolean dbg, java.io.PrintStream psOut)
Method Detail |
public void setDebug(boolean dbg)
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.
A
- the automaton to duplicatepublic java.util.HashSet getChildAutomata()
public java.util.HashSet getDescendantAutomata()
public abstract void build()
Subclasses must implement a matchTree function.
TODO this function will presumably change.
value
- the value to acceptprotected java.lang.String getName()
public java.lang.String toString()
toString
in class java.lang.Object
public boolean equals(java.lang.Object o)
equals
in class java.lang.Object
o
- the object to compare toObject.equals(java.lang.Object)
public int hashCode()
hashCode
in class java.lang.Object
Object.hashCode()
public void simplify()
public boolean isNull()
public void update(int BuildPhases)
public void force(int BuildPhases)
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.
TAState.set_epsClos(HashSet e_clos)
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:
N.B.:
protected void epsilon_elimination()
Eliminates the epsilon transitions from the automaton.
Algorithm:
Note that this is the standard algorithm you can find also in string automata.
N.B.:
protected void completeAutomaton()
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:
public void dump(java.io.PrintStream out)
Writes out every information about the automaton.
Specifically:
out
- the stream to which print outprotected 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)
protected void addEpsTransition(TAState Q1, TAState Q2)
protected void addEpsTransitions(java.util.Vector V1, java.util.Vector V2)
protected void addEpsTransitions(java.util.Vector V1, TAState Q)
protected void addEpsTransitions(TAState Q, java.util.Vector V2)
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
A
- the automaton to merge with the current oneFlags
- the parts of A to copy (see above)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |