Class EarleyState

Represents an Earley Item/State in the parsing chart.

Inheritance

object

EarleyState

Implements

IEquatable<EarleyState>

Inherited Members

object.Equals(object, object)

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

Namespace: EarleyParser

Assembly: EarleyParser.dll

Syntax

public class EarleyState : IEquatable<EarleyState>

Remarks

An Earley State represents a partially matched grammar rule at a specific position in the input. The state contains the following components:

Core Components:
- The grammar rule being matched
- Current position of the dot in the rule's right-hand side
- References to start and end columns in the parse chart
Parse Tree Structure:
- Predecessor: The parent state that led to this state
- ReductorSpan: Collection of completed states that can be used to complete this state
- EndColumn: The column where this state completes (if completed)
State Properties:
- IsCompleted: Whether the dot has reached the end of the rule
- NextTerm: The next symbol to be matched (if not completed)
Parse Forest Navigation:
- Methods for traversing the parse forest
- Support for handling ambiguous parses
- Analysis of parse tree properties (recursion, basic trees)

The state is a fundamental building block of the Earley algorithm, representing both the progress of rule matching and the structure of the resulting parse forest.

Constructors

| Edit this page View Source

EarleyState(Rule, int, EarleyColumn)

Initializes a new instance of the EarleyState class.

Declaration

public EarleyState(Rule r, int dotIndex, EarleyColumn c)

Parameters

Type	Name	Description
Rule	r	The grammar rule being matched.
int	dotIndex	The initial position of the dot in the rule's right-hand side.
EarleyColumn	c	The column where this state begins.

Properties

| Edit this page View Source

DotIndex

Gets the current position of the dot in the rule's right-hand side.

Declaration

public int DotIndex { get; }

Property Value

Type	Description
int

| Edit this page View Source

EndColumn

Gets or sets the column where this state completes.

Declaration

public EarleyColumn EndColumn { get; set; }

Property Value

Type	Description
EarleyColumn

| Edit this page View Source

IsCompleted

Gets a value indicating whether this state is completed.

Declaration

public bool IsCompleted { get; }

Property Value

Type	Description
bool

| Edit this page View Source

NextTerm

Gets the next symbol to be matched in this state.

Declaration

public string NextTerm { get; }

Property Value

Type	Description
string

| Edit this page View Source

Predecessor

Gets or sets the predecessor state that led to this state.

Declaration

public EarleyState Predecessor { get; set; }

Property Value

Type	Description
EarleyState

| Edit this page View Source

ReductorSpan

Gets or sets the collection of completed states that can be used to complete this state.

Declaration

public EarleySpan ReductorSpan { get; set; }

Property Value

Type	Description
EarleySpan

| Edit this page View Source

Rule

Gets the grammar rule being matched in this state.

Declaration

public Rule Rule { get; }

Property Value

Type	Description
Rule

| Edit this page View Source

StartColumn

Gets the column where this state begins.

Declaration

public EarleyColumn StartColumn { get; }

Property Value

Type	Description
EarleyColumn

Methods

| Edit this page View Source

CountDerivations(Dictionary<EarleySpan, int>)

Counts the total number of derivations rooted at this state.

Declaration

public int CountDerivations(Dictionary<EarleySpan, int> visited)

Parameters

Type	Name	Description
Dictionary<EarleySpan, int>	visited	Dictionary to track visited spans and their derivation counts.

Returns

Type	Description
int	The total number of derivations.

| Edit this page View Source

CountLengthsOfBasicTrees(Dictionary<EarleySpan, List<int>>, HashSet<string>, HashSet<string>, bool)

Counts the lengths of basic trees rooted at this state.

Declaration

public List<int> CountLengthsOfBasicTrees(Dictionary<EarleySpan, List<int>> visited, HashSet<string> encounteredNTs, HashSet<string> recursiveNTs, bool insideRecursion)

Parameters

Type	Name	Description
Dictionary<EarleySpan, List<int>>	visited	Dictionary to track visited spans and their tree lengths.
HashSet<string>	encounteredNTs	Set of non-terminals encountered in the current path.
HashSet<string>	recursiveNTs	Set of non-terminals known to be recursive.
bool	insideRecursion	Indicates whether we are already inside a recursive structure.

Returns

Type	Description
List<int>	List of lengths of basic trees. Returns [-1] for recursive structures.

| Edit this page View Source

Equals(EarleyState)

Determines whether this state equals another state.

Declaration

public bool Equals(EarleyState other)

Parameters

Type	Name	Description
EarleyState	other	The state to compare with.

Returns

Type	Description
bool	True if the states are equal; otherwise, false.

| Edit this page View Source

Equals(object)

Determines whether this state equals another object.

Declaration

public override bool Equals(object obj)

Parameters

Type	Name	Description
object	obj	The object to compare with.

Returns

Type	Description
bool	True if the objects are equal; otherwise, false.

Overrides

object.Equals(object)

| Edit this page View Source

GetFormattedString(Grammar, Dictionary<EarleySpan, Color>, bool)

Gets formatted string representations of the parse tree.

Declaration

public List<StringBuilder> GetFormattedString(Grammar g, Dictionary<EarleySpan, Color> visited, bool onlyPartsOfSpeechSequence = false)

Parameters

Type	Name	Description
Grammar	g	The grammar used for parsing.
Dictionary<EarleySpan, Color>	visited	Dictionary to track visited spans and their colors.
bool	onlyPartsOfSpeechSequence	Whether to only include parts of speech in the output.

Returns

Type	Description
List<StringBuilder>	List of StringBuilder objects containing formatted string representations.

| Edit this page View Source

GetHashCode()

Gets the hash code for this state.

Declaration

public override int GetHashCode()

Returns

Type	Description
int	The hash code.

Overrides

object.GetHashCode()

| Edit this page View Source

GetPOSRulesInEachDerivation(Grammar, Dictionary<EarleySpan, List<HashSet<Rule>>>, int)

Gets the parts of speech rules in each derivation.

Declaration

public List<HashSet<Rule>> GetPOSRulesInEachDerivation(Grammar g, Dictionary<EarleySpan, List<HashSet<Rule>>> visited, int i)

Parameters

Type	Name	Description
Grammar	g	The grammar used for parsing.
Dictionary<EarleySpan, List<HashSet<Rule>>>	visited	Dictionary to track visited spans and their POS rules.
int	i	The index of the current derivation.

Returns

Type	Description
List<HashSet<Rule>>	List of sets of rules containing parts of speech.

| Edit this page View Source

ToString()

Returns a string representation of this state.

Declaration

public override string ToString()

Returns

Type	Description
string	String representation of the state.

Overrides

object.ToString()

Implements

IEquatable<T>