|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--xrel.analyzer.TreeAutomaton
Tree automata are just like normal string automata but elements are trees instead of characters.
They have both normal and epsilon transitions. Normal transitions have the form q1 = tag[content] --> q2 (transit from q1 to q2 when the next input element is a tag with name "tag" and with the specified content), while epsilon (or null) transitions have the form q1 --> q2 (non deterministically transit from q1 to q2).
An automaton is a list of states, two subsets of this list that determine the initial states and the final states and the transitions (both the normal ones and the epsilon ones). A state of the automaton is an object of type State, while the transitions are objects of private classes defined inside TreeAutomaton.java.
Constructor Summary | |
TreeAutomaton()
Initializes an empty tree automaton. |
Method Summary | |
void |
build(xrel.parser.SymElement el)
Builds the automaton for a pattern. |
void |
compute_closures()
Computes the epsilon closures for each state. |
void |
dump(java.io.PrintStream out)
Writes out every information about the automaton. |
void |
epsilon_elimination()
Eliminates the null transitions from the automaton. |
boolean |
matchTree(xrel.parser.SimpleNode value,
xrel.parser.SymTable st,
boolean debug)
|
void |
remove_useless_states()
Removes the useless states from the automaton. |
void |
setStateTransitions()
|
Methods inherited from class java.lang.Object |
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
public TreeAutomaton()
Method Detail |
public boolean matchTree(xrel.parser.SimpleNode value, xrel.parser.SymTable st, boolean debug)
public void build(xrel.parser.SymElement el)
el
- the symbol element of the pattern.public void dump(java.io.PrintStream out)
out
- the stream to which print outpublic void compute_closures()
public void remove_useless_states()
Removes the useless states from the automaton.
N.B.: call this functions only after executing epsilon_elimination().
public void epsilon_elimination()
N.B.: you need to call compute_closures before to call this function.
public void setStateTransitions()
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |