Class EarleyColumn

Represents a column in the Earley parsing chart, corresponding to a specific position in the input.

Inheritance

object

EarleyColumn

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Namespace: EarleyParser

Assembly: EarleyParser.dll

Syntax

public class EarleyColumn

Remarks

Each column maintains the set of all Earley states that have been generated at that position. The column implements the following key components:

1. State Management:
   • Predecessors: Dictionary of incomplete states, indexed by their next symbol
   • Reductors: Collection of completed states that can be used for completion
   • Epsilon state: Special state for handling empty productions
2. Processing Agendas:
   • ActionableCompleteStates: Priority queue of completed states to process
   • ActionableNonTerminalsToPredict: Queue of non-terminals that need prediction
3. State Addition:
   • AddState: Core method that processes new states according to the Earley algorithm
   • Handles both incomplete states (adding to predecessors)
   • Handles completed states (adding to completion agenda)

The column is a crucial component of the Earley algorithm, maintaining the set of all possible partial parses at each position in the input. It implements the dynamic programming aspect of the algorithm by storing and organizing states efficiently.