edu.osu.ling.pep
Class Edge

java.lang.Object
  edu.osu.ling.pep.Edge

public class Edge
extends Object

An edge in a chart produced by an Earley parser. Edges consist of a dotted rule paired with an origin position within a string.

An edge is either active or passive depending on how far processing has succeeded in the dotted rule. When an edge is passive, parsing has successfully completed the left side category at the edge's origin position within the string being parsed.

Edges can be created by prediction based on a grammar rule, or by scanning an input token that matches the active category of some edge's dotted rule. An edge can also be completed based on another edge, allowing parse trees to trace the derivation of a string based on a Grammar. Upon creation, a completed edge advances the position of the edge's dotted rule by 1, but maintains the same origin position as the edge. It also maintains backpointers to the edges that were used in completing the new edge.

Edges are immutable and can not be altered once they are created. In an Earley parser, edges are only ever added, never removed or changed.

Version:

$LastChangedRevision: 1806 $

Author:

Scott Martin

See Also:

Chart, DottedRule

Constructor Summary

Edge(DottedRule dottedRule, int origin)
Creates an edge containing the specified dotted rule at the origin position given.

Edge(DottedRule dottedRule, int origin, Set<Edge> bases)
Creates an edge for the specified dotted rule and origin position, with the given set of edges as bases for its completion.

Method Summary

static Edge	complete(Edge toComplete, Edge basis) Completes the specified edge based on the specified basis.
boolean	equals(Object obj) Tests whether this edge is equal to another edge by comparing their dotted rules, origin positions, and basis edges.
Set<Edge>	getBases() Gets the bases for completion of this edge, in order of insertion.
DottedRule	getDottedRule() Gets this edge's dotted rule.
int	getOrigin() Gets this edge's origin position.
int	hashCode() Computes a hash code for this edge based on its dotted rule, origin position, and bases.
boolean	isPassive() Tests whether this is a passive edge or not.
static Edge	predictFor(Rule rule, int origin) Makes a predicted edge based on the specified rule, with the specified origin position.
static Edge	scan(Edge edge, String token) Creates an edge based on the given edge and the token that was just scanned.
String	toString() Gets a string representation of this edge.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

Edge

public Edge(DottedRule dottedRule,
            int origin)

Creates an edge containing the specified dotted rule at the origin position given.

Parameters:

dottedRule - The dotted rule at origin.

origin - The origin position within the string being parsed.

Throws:

IndexOutOfBoundsException - If origin < 0.

See Also:

Edge(DottedRule, int, Set)

Edge

public Edge(DottedRule dottedRule,
            int origin,
            Set<Edge> bases)

Creates an edge for the specified dotted rule and origin position, with the given set of edges as bases for its completion.

Parameters:

bases - The set of bases, in order, that completed this edge. If this is null, the empty set is used.

Throws:

IndexOutOfBoundsException - If origin < 0.

Since:

0.2

Method Detail

complete

public static Edge complete(Edge toComplete,
                            Edge basis)

Completes the specified edge based on the specified basis.

Parameters:

toComplete - The edge to complete.

basis - The basis on which this edge is being completed. This edge will be added to the set of bases already in the edge, if any are present.

Returns:

A new edge exactly like this one, except that its dotted rule's position is advanced by 1 and its bases contains basis.

Throws:

NullPointerException - if toComplete or basis is null.

IllegalArgumentException - If the specified basis is not a suitable edge for completing this edge. Reasons for this exception are that the basis edge:

• has a dotted rule whose position is 0 (meaning that no completion has actually taken place)
• has a dotted rule whose left category does not equal this edge's dotted rule's active category.

Since:

0.2

See Also:

DottedRule.advanceDot(DottedRule)

equals

public boolean equals(Object obj)

Tests whether this edge is equal to another edge by comparing their dotted rules, origin positions, and basis edges.

Overrides:

equals in class Object

Returns:

true iff the given object is an instance of Edge and its dotted rule, origin, and bases are equal to this edge's dotted rule, origin, and bases.

See Also:

DottedRule.equals(Object)

getBases

public Set<Edge> getBases()

Gets the bases for completion of this edge, in order of insertion. A completed edge inherits its bases from the edge from which it is created.

Returns:

If this edge was completed based on other edges, those edges are returned in their order of insertion. Otherwise, empty set is returned.

Since:

0.2

See Also:

complete(Edge, Edge)

getDottedRule

public DottedRule getDottedRule()

Gets this edge's dotted rule.

Returns:

The dotted rule specified when this edge was created.

getOrigin

public int getOrigin()

Gets this edge's origin position.

Returns:

The origin position given for this edge at creation.

hashCode

public int hashCode()

Computes a hash code for this edge based on its dotted rule, origin position, and bases.

Overrides:

hashCode in class Object

See Also:

DottedRule.hashCode()

isPassive

public boolean isPassive()

Tests whether this is a passive edge or not. An edge is passive when its dotted rule contains no active category.

Returns:

true iff the active category of this edge's dotted rule is null.

predictFor

public static Edge predictFor(Rule rule,
                              int origin)

Makes a predicted edge based on the specified rule, with the specified origin position.

Parameters:

rule - The rule to construct a predicted edge for.

origin - The origin position of the newly predicted edge.

Returns:

A new edge whose dotted rule is the specified rule at position 0. The new edge's origin is the specified origin.

Throws:

NullPointerException - If rule is null.

scan

public static Edge scan(Edge edge,
                        String token)

Creates an edge based on the given edge and the token that was just scanned.

Parameters:

edge - The edge whose active category is the just-scanned token.

token - The just-scanned token.

Returns:

A new edge just like the specified edge (including origin), but with its rule's dot position advanced by one. The new edge's bases incorporates the old edge and all of its bases.

Throws:

NullPointerException - If edge or token is null.

IllegalArgumentException - In any of the following cases:

1. The specified edge is passive.
2. The specified edge's dotted rule's active category is not a terminal.
3. The edge's rule's active category's name is not equal to the scanned token.

Since:

0.4

toString

public String toString()

Gets a string representation of this edge.

Overrides:

toString in class Object

Returns:

"0[S -> NP * VP]" for an edge at origin 0 and dotted rule S -> NP * VP.

See Also:

DottedRule.toString()