xrel.analyzer
Class TreeAutomaton

java.lang.Object
  |
  +--xrel.analyzer.TreeAutomaton

public class TreeAutomaton
extends java.lang.Object

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.

Author:
Fabrizio Bisi

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

TreeAutomaton

public TreeAutomaton()
Initializes an empty tree automaton.
Method Detail

matchTree

public boolean matchTree(xrel.parser.SimpleNode value,
                         xrel.parser.SymTable st,
                         boolean debug)

build

public void build(xrel.parser.SymElement el)
Builds the automaton for a pattern.
Parameters:
el - the symbol element of the pattern.

dump

public void dump(java.io.PrintStream out)
Writes out every information about the automaton.
Parameters:
out - the stream to which print out

compute_closures

public void compute_closures()
Computes the epsilon closures for each state.

remove_useless_states

public void remove_useless_states()

Removes the useless states from the automaton.

N.B.: call this functions only after executing epsilon_elimination().


epsilon_elimination

public void epsilon_elimination()
Eliminates the null transitions from the automaton. This operation doesn't preserve the ambiguity.

N.B.: you need to call compute_closures before to call this function.


setStateTransitions

public void setStateTransitions()