Early's Algorithm

Early's algorithm proceeds as follows:

Given any grammar with start symbol $S$, and some input string $x_0...x_{n-1}$ of length $n$,

1. Form the start state, which consists of the item
   
   $$0:\;\;{}_0\; \rightarrow {}_\triangle S$$
   
   
   and its closure

2. For each new state (for some position $i$) that we create, and for each item in that state:
   • Shift Input (Marker before a terminal)
     If the item is of the form
     
     $$i:\;\; {}_kX\;\rightarrow\; \alpha{}_\triangle a\beta$$
     
     
     where $a$ is a terminal symbol matching the input symbol $x_i$, create the state formed by taking the closure of:
     
     $$i+1:\;\; {}_kX\;\rightarrow\; \alpha a{}_\triangle \beta$$
     
     

   • Apply Rule (Marker at end of rule)
     If the item is of the form
     
     $$i:\;\; {}_kX\;\rightarrow\; \gamma{}_\triangle$$
     
     
     look at all those states for $k$ that have the marker to the left of $X$; ie items of the form
     
     $$k:\;\; {}_j Y\;\rightarrow\; \alpha{}_\triangle X \beta$$
     
     
     and create new states consisting of the closure of items of the form:
     
     $$i:\;\; {}_j Y\;\rightarrow\; \alpha X {}_\triangle \beta$$
     
     

3. Keep applying step (2) until all states up to $n$ have been generated. If one of these then contains the item
   
   $$n:\;\; {}_0\; \rightarrow\; S {}_\triangle$$
   
   
   the parse has been successful.