Parsing Engine

danbikel.parser.constraints
Class PartialTreeConstraintSet

java.lang.Object
  extended by java.util.AbstractCollection
      extended by danbikel.parser.constraints.PartialTreeConstraintSet
All Implemented Interfaces:
ConstraintSet, Iterable, Collection

public class PartialTreeConstraintSet
extends AbstractCollection
implements ConstraintSet

Represents a set of constraints that correspond to a specific unlexicalized parse tree, for use when the bottom-up parsing algorithm needs to generate only the analyses that are consistent with a particular unlexicalized tree. Accordingly, the individual Constraint objects in this set form a tree structure isomorphic to the (possibly partial) syntactic tree with which they are constructed.


Field Summary
protected  ArrayList leaves
          The leaves of this tree of constraints in their correct order as they correspond to single words (technically, preterminals) of a sentence.
protected  ArrayList list
          A list of all the constraints in this set, for making iteration easy.
protected  PartialTreeConstraint root
          The root of this tree of constraints.
protected  int size
          The number of constraints in this set.
 
Constructor Summary
PartialTreeConstraintSet()
          Returns an empty set of constraints.
PartialTreeConstraintSet(Sexp tree)
          Returns a set of partial tree constraints whose tree structure is isomorphic to the specified (possibly partial) syntactic tree.
 
Method Summary
protected  void buildConstraintSet(Sexp tree)
          Builds the constraint tree from the specified unlexicalized parse tree.
protected  void collectNodes(PartialTreeConstraint tree)
          Collects the constraints in the specified tree of constraint objects.
 Constraint constraintSatisfying(Item item)
          Returns the first constraint in this set that is found that the specified item satisfies.
 boolean findAtLeastOneSatisfying()
          Returns true, since a satisfying constraint must be found for every chart item.
 boolean findNoViolations()
          Returns false, since this type of constraint set guarantees consistency among its constraints, meaning that, since every chart item must have an assigned, satisfying constraint, there cannot be any constraint violations, and therefore no such violation-checking needs to occur during decoding.
 boolean hasTreeStructure()
          Returns true, since this type of constraint set does, indeed, have a tree structure.
 boolean isViolatedBy(Item item)
          Simply throws an UnsupportedOperationException, since violations do not need to be checked for this type of constraint set.
 Iterator iterator()
          Returns an iterator over the constraints in this set.
 List leaves()
          Returns a list of the leaves in this tree of constraints.
static void main(String[] args)
          Test driver for this class.
 Constraint root()
          Returns the root of this tree of constraints.
 int size()
          Returns the number of constraints in this set.
 String toString()
          Returns a human-readable string representation of this tree of constraints.
 
Methods inherited from class java.util.AbstractCollection
add, addAll, clear, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface java.util.Collection
add, addAll, clear, contains, containsAll, equals, hashCode, isEmpty, remove, removeAll, retainAll, toArray, toArray
 

Field Detail

root

protected PartialTreeConstraint root
The root of this tree of constraints.


size

protected int size
The number of constraints in this set.


list

protected ArrayList list
A list of all the constraints in this set, for making iteration easy.


leaves

protected ArrayList leaves
The leaves of this tree of constraints in their correct order as they correspond to single words (technically, preterminals) of a sentence.

Constructor Detail

PartialTreeConstraintSet

public PartialTreeConstraintSet()
Returns an empty set of constraints.


PartialTreeConstraintSet

public PartialTreeConstraintSet(Sexp tree)
Returns a set of partial tree constraints whose tree structure is isomorphic to the specified (possibly partial) syntactic tree.

Parameters:
tree - a possibly partial syntatic tree whose node labels and spans are to be represented in any derivation pursued by the decoder
Method Detail

buildConstraintSet

protected void buildConstraintSet(Sexp tree)
Builds the constraint tree from the specified unlexicalized parse tree. As a necessary side-effect, the root and leaves data members will be set/populated by this method.

Parameters:
tree - the tree from which to build this constraint set

collectNodes

protected void collectNodes(PartialTreeConstraint tree)
Collects the constraints in the specified tree of constraint objects.

Parameters:
tree - the tree of constraint objects to be collected

hasTreeStructure

public boolean hasTreeStructure()
Returns true, since this type of constraint set does, indeed, have a tree structure.

Specified by:
hasTreeStructure in interface ConstraintSet
Returns:
true

findAtLeastOneSatisfying

public boolean findAtLeastOneSatisfying()
Returns true, since a satisfying constraint must be found for every chart item.

Specified by:
findAtLeastOneSatisfying in interface ConstraintSet
Returns:
true
See Also:
ConstraintSet.constraintSatisfying(Item)

findNoViolations

public boolean findNoViolations()
Returns false, since this type of constraint set guarantees consistency among its constraints, meaning that, since every chart item must have an assigned, satisfying constraint, there cannot be any constraint violations, and therefore no such violation-checking needs to occur during decoding.

Specified by:
findNoViolations in interface ConstraintSet
Returns:
false
See Also:
findAtLeastOneSatisfying()

root

public Constraint root()
Returns the root of this tree of constraints.

Specified by:
root in interface ConstraintSet
Returns:
the root constraint in a set if the set forms a tree structure
See Also:
ConstraintSet.hasTreeStructure()

leaves

public List leaves()
Returns a list of the leaves in this tree of constraints.

Specified by:
leaves in interface ConstraintSet
Returns:
a list containing the leaves of a tree-structured set of constraints
See Also:
ConstraintSet.hasTreeStructure()

isViolatedBy

public boolean isViolatedBy(Item item)
Simply throws an UnsupportedOperationException, since violations do not need to be checked for this type of constraint set.

Specified by:
isViolatedBy in interface ConstraintSet
Parameters:
item - the item to be checked for violations
Returns:
true if the specified item violates a constraint in this set, false otherwise
See Also:
findNoViolations()

constraintSatisfying

public Constraint constraintSatisfying(Item item)
Description copied from interface: ConstraintSet
Returns the first constraint in this set that is found that the specified item satisfies.

Specified by:
constraintSatisfying in interface ConstraintSet
Parameters:
item - the item for which a satisfying constraint is to be found
Returns:
the first constraint in this set that is found that the specified item satisfies.

toString

public String toString()
Returns a human-readable string representation of this tree of constraints.

Overrides:
toString in class AbstractCollection
Returns:
a human-readable string representation of this tree of constraints

size

public int size()
Returns the number of constraints in this set.

Specified by:
size in interface Collection
Specified by:
size in class AbstractCollection

iterator

public Iterator iterator()
Returns an iterator over the constraints in this set.

Specified by:
iterator in interface Iterable
Specified by:
iterator in interface Collection
Specified by:
iterator in class AbstractCollection
Returns:
an iterator over the constraints in this set

main

public static void main(String[] args)
Test driver for this class.

Parameters:
args -

Parsing Engine

Author: Dan Bikel.