Parsing Engine

danbikel.parser.constraints
Class PartialTreeConstraint

java.lang.Object
  extended by danbikel.parser.constraints.PartialTreeConstraint
All Implemented Interfaces:
SexpConvertible, Constraint, Serializable

public class PartialTreeConstraint
extends Object
implements Constraint, SexpConvertible

An implementation of a constraint to sit in a tree structure of constraints that represent a subgraph (certain brackets) of a tree, constraining a decoder to pursue only theories that contain the brackets of the constraint set of these objects.

See Also:
Serialized Form

Field Summary
protected  List children
          All child constraints of this constraint.
protected  int end
          The ending word index of the syntactic subtree covered by this constraint.
protected  boolean fullySatisfied
          Contains whether this constraint has been fully satisfied.
protected  Symbol label
          The nonterminal label associated with this constraint.
protected  Nonterminal nt
          A Nonterminal object for use with Treebank.parseNonterminal(Symbol,Nonterminal).
protected  Nonterminal otherNT
          A Nonterminal object for use with Treebank.parseNonterminal(Symbol,Nonterminal).
protected  PartialTreeConstraint parent
          The parent constraint of this constraint.
protected  boolean satisfied
          Contains whether this constraint has been partially satisfied.
protected  int start
          The starting word index of the syntactic subtree covered by this constraint.
 
Constructor Summary
protected PartialTreeConstraint()
          Constructs an empty constraint tree.
protected PartialTreeConstraint(PartialTreeConstraint parent, Sexp tree, IntCounter currWordIdx)
          A helper constructor for constructing a tree of constraints rooted at the specified subtree with the specified parent.
  PartialTreeConstraint(Sexp tree)
          Constructs a tree of constraints rooted at the specified syntactic tree.
 
Method Summary
 int end()
          Returns the end index of the span associated with this constraint.
protected  List getChildren()
          Returns the list of children of this constraint.
 Constraint getParent()
          Returns the parent of this constraint if this constraint has been fullySatisfied; otherwise, returns this constraint.
 boolean hasBeenSatisfied()
          Returns whether this constraint has been partially satisfied.
 boolean isLeaf()
          Returns whether this constraint corresponds to a preterminal in the original syntactic tree.
 boolean isLocallySatisfiedBy(Item item)
          Returns whether the specified item's span does not exceed the bounds of the span associated with this constraint.
 boolean isSatisfiedBy(Item item)
          Returns true if this constraint is satisfied by its local information.
protected  boolean isSatisfiedByPreterminal(CKYItem item)
          Returns true.
 boolean isViolatedBy(Item item)
          Throws an UnsupportedOperationException, as this operation is not appropriate for partial tree constraints.
 boolean isViolatedByChild(Item childItem)
          Returns whether the specified child chart item violates this constraint by having a span beyond the boundaries of this constraint's span.
 Symbol label()
          Returns the nonterminal label associated with this constraint.
protected  boolean labelMatches(Item item)
          Returns whether this constraint's label subsumes the label of the specified item.
protected  boolean spanMatches(Item item)
          Returns whether the start and end indices of the specified chart item are equal to the start and end indices, respectively, of the span associated with this constraint.
protected  boolean spanOK(Item item)
          Returns whether the span of the specified item crosses the span.
 int start()
          Returns the start index of the span associated with this constraint.
 Sexp toSexp()
          Returns a symbolic expression representing the tree of constraints rooted at this constraint (intended for debugging purposes).
 String toString()
          Returns a human-readable string representation of this constraint (intended for debugging purposes).
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

parent

protected PartialTreeConstraint parent
The parent constraint of this constraint.


children

protected List children
All child constraints of this constraint.


label

protected Symbol label
The nonterminal label associated with this constraint.


nt

protected Nonterminal nt
A Nonterminal object for use with Treebank.parseNonterminal(Symbol,Nonterminal).


otherNT

protected Nonterminal otherNT
A Nonterminal object for use with Treebank.parseNonterminal(Symbol,Nonterminal).


start

protected int start
The starting word index of the syntactic subtree covered by this constraint.


end

protected int end
The ending word index of the syntactic subtree covered by this constraint.


satisfied

protected boolean satisfied
Contains whether this constraint has been partially satisfied. A constraint of this type has been partially satisfied if, during the bottom-up decoding process, its label and other local information are found to be consisting with the derivation being pursued.


fullySatisfied

protected boolean fullySatisfied
Contains whether this constraint has been fully satisfied. A constraint of this type is fully satisfied if it is both partially satisfied and if all child constraints have been fully satisfied.

Constructor Detail

PartialTreeConstraint

public PartialTreeConstraint(Sexp tree)
Constructs a tree of constraints rooted at the specified syntactic tree.

Parameters:
tree - a possibly-underspecified syntactic tree representing nodes and spans that must be produced by any derivation pursued by the decoder

PartialTreeConstraint

protected PartialTreeConstraint()
Constructs an empty constraint tree.


PartialTreeConstraint

protected PartialTreeConstraint(PartialTreeConstraint parent,
                                Sexp tree,
                                IntCounter currWordIdx)
A helper constructor for constructing a tree of constraints rooted at the specified subtree with the specified parent.

Parameters:
parent - the parent of the specified tree, or null if the specified tree has no parent
tree - the tree for which to construct an isomorphic tree of constraints
currWordIdx - the start index of the span covered by the specified tree, threaded through the recursive calls to this constructor
Method Detail

isLeaf

public boolean isLeaf()
Returns whether this constraint corresponds to a preterminal in the original syntactic tree.

Specified by:
isLeaf in interface Constraint
Returns:
whether this constraint corresponds to a preterminal in the original syntactic tree.
See Also:
ConstraintSet.hasTreeStructure()

isViolatedByChild

public boolean isViolatedByChild(Item childItem)
Returns whether the specified child chart item violates this constraint by having a span beyond the boundaries of this constraint's span.

Specified by:
isViolatedByChild in interface Constraint
Parameters:
childItem - the child item to be tested
Returns:
whether the specified child chart item violates this constraint by having a span beyond the boundaries of this constraint's span.
See Also:
ConstraintSet.hasTreeStructure()

getParent

public Constraint getParent()
Returns the parent of this constraint if this constraint has been fullySatisfied; otherwise, returns this constraint.

Implementation note: While this method does not always return the parent constraint of this constraint, the semantics of this method are appropriate for imposing partial tree constraints during a bottom-up decoding process.

Specified by:
getParent in interface Constraint
Returns:
the parent of this constraint if this constraint has been fullySatisfied; otherwise, returns this constraint.
See Also:
ConstraintSet.hasTreeStructure()

getChildren

protected List getChildren()
Returns the list of children of this constraint.

Returns:
the list of children of this constraint.

label

public Symbol label()
Returns the nonterminal label associated with this constraint.

Returns:
the nonterminal label associated with this constraint.

start

public int start()
Returns the start index of the span associated with this constraint.

Returns:
the start index of the span associated with this constraint.

end

public int end()
Returns the end index of the span associated with this constraint.

Returns:
the end index of the span associated with this constraint.

isViolatedBy

public boolean isViolatedBy(Item item)
Throws an UnsupportedOperationException, as this operation is not appropriate for partial tree constraints.

Specified by:
isViolatedBy in interface Constraint
Parameters:
item - the item to test
Returns:
whether the specified item violates this constraint.

isSatisfiedByPreterminal

protected boolean isSatisfiedByPreterminal(CKYItem item)
Returns true.

Parameters:
item - a preterminal derivation item
Returns:
true under all circumstances

isSatisfiedBy

public boolean isSatisfiedBy(Item item)
Returns true if this constraint is satisfied by its local information. Internally, this constraint is said to be fully satisfied if all its child constraints are fully satisfied, and if the specified item has a matching span and a matching label, as determined by the spanMatches(Item) and labelMatches(Item) methods, respectively.

Specified by:
isSatisfiedBy in interface Constraint
Parameters:
item - the item to test for satisfaction by this constraint
Returns:
whether this constraint is satisfied the specified item
See Also:
isLocallySatisfiedBy(Item), spanMatches(Item), labelMatches(Item)

hasBeenSatisfied

public boolean hasBeenSatisfied()
Returns whether this constraint has been partially satisfied.

Specified by:
hasBeenSatisfied in interface Constraint
Returns:
whether this constraint has been partially satisfied.
See Also:
satisfied

isLocallySatisfiedBy

public boolean isLocallySatisfiedBy(Item item)
Returns whether the specified item's span does not exceed the bounds of the span associated with this constraint.

Specified by:
isLocallySatisfiedBy in interface Constraint
Parameters:
item - the chart item whose span is to be tested
Returns:
whether the specified item's span does not exceed the bounds of the span associated with this constraint.

spanOK

protected boolean spanOK(Item item)
Returns whether the span of the specified item crosses the span. of this constraint

Parameters:
item - the item whose span is to be tested
Returns:
whether the span of the specified item crosses the span

spanMatches

protected boolean spanMatches(Item item)
Returns whether the start and end indices of the specified chart item are equal to the start and end indices, respectively, of the span associated with this constraint.

Parameters:
item - the chart item whose span is to be compared to that associated with this constraint
Returns:
whether the start and end indices of the specified chart item are equal to the start and end indices, respectively, of the span associated with this constraint.

labelMatches

protected boolean labelMatches(Item item)
Returns whether this constraint's label subsumes the label of the specified item.

Parameters:
item - the item whose label is to be tested
Returns:
whether this constraint's label subsumes the label of the specified item.
See Also:
Nonterminal.subsumes(Nonterminal)

toSexp

public Sexp toSexp()
Returns a symbolic expression representing the tree of constraints rooted at this constraint (intended for debugging purposes).

Specified by:
toSexp in interface SexpConvertible
Returns:
a symbolic expression representing the tree of constraints rooted at this constraint

toString

public String toString()
Returns a human-readable string representation of this constraint (intended for debugging purposes).

Overrides:
toString in class Object
Returns:
a human-readable string representation of this constraint.

Parsing Engine

Author: Dan Bikel.