Early's Items

This is achieved by enhancing the concept of an item. In Early's parser an item has the form:

$$i:\;\; {}_kX\; \rightarrow\; \alpha{}_\triangle \beta$$

where $i$ and $k$ are numbers, and $X\rightarrow \alpha\beta$ is a production rule. An item of this form is interpreted as meaning:

• We are at position $i$ on the input (when $i=0$ we are at the start of the string).
• The non-terminal $X$ corresponds to some sub-string of the input which starts at position $k$
• We have recognised an $\alpha$ on the input, and should we go on to recognise $\beta$, we can then make the reduction to $X$

If the start symbol is $S$, we can represent this situation as:

$$\overbrace{ x_0 \ldots \overbrace{ \overbrace{x_k \ldots x_{... ...ngle\; \overbrace{x_i \ldots}^{\beta} }^{X} \ldots x_{n-1} }^S$$

Thus at any stage during the parse we always have that $0 \leq k \leq i \leq n$ where $n$ is the length of the input string.

We will need to define a version of the closure operation for these items:

• State Closure (Marker before a non-terminal)
  For each state with an item of the form
  
  $$i:\;\; {}_kX\;\rightarrow\; \alpha{}_\triangle Y\beta$$
  
  
  where $Y$ is any non-terminal, take all rules of the form $Y\;\rightarrow\;\gamma$, and add the states for:
  
  $$i:\;\; {}_iY\;\rightarrow\; {}_\triangle \gamma$$