# Leo's deterministic reduction for Earley Parsing

I am trying to build an Earley parser using the Wikipedia pesudocode as a base, with Aycock's fix for epsilon rules as follows:

def predict(self, column, symbol, state):
# original predict
for alternative in grammar[symbol]:
column.add(a new state corresponding to alternative)
# Aycock fix
if nullable(symbol):

And Leo's optimization for right recursion using the explanation here for further insight. I am able to understand how to parse Right Recursive grammars with it. However, I am confused when it comes to using it to parse non-right recursive grammars. For example, here is a grammar that can parse an example string aa

<start> := <A>
<A>     := <A> + 'a'
<A>     := \epsilon

Without the deterministic reduction from Leo, the Earley items constructed (pipe indicates the dot) are as follows: The parenthesis is in this format (starting column, earley set).

char: _ column[0]
<start>:= | <A>(0,0)     #1) init
<A>:= | <A> a(0,0)       #2) predict from 1
<A>:= |(0,0)             #3) predict from 1
<start>:= <A> |(0,0)     #4) epsilon complete from 3
<A>:= <A> | a(0,0)       #5) epsilon complete from 3

char: a column[1]
<A>:= <A> a |(0,1)       #6) scan a from 5
<start>:= <A> |(0,1)     #7) complete A from 1 (start col of 6)
<A>:= <A> | a(0,1)       #8) complete A from 2 (start col of 6)

char: a column[2]
<A>:= <A> a |(0,2)       #9) scan a from 8
<start>:= <A> |(0,2)     #10) complete A from 1 (start col of 9)
<A>:= <A> | a(0,2)       #11) complete A from 2 (start col of 9)

According to Leo,

Definition 2.1: An item is said to be on the deterministic reduction path above $$[A \rightarrow \gamma., i]$$ if it is $$[B > \rightarrow \alpha A ., k]$$ with $$[B \rightarrow \alpha . A, k]$$ being the only item in $$I_i$$ with the dot in front of A, or if it is on the deterministic reduction path above $$[B \rightarrow \alpha A ., > k]$$. An item on such a path is called topmost one if there is no item on the deterministic reduction path above it.

(I am assuming that $$[B \rightarrow \alpha A ., k]$$ is also in $$I_i$$.)

The completer is as follows:

def complete(self, column, state):
detred = self.deterministic_reduction(state)
if detred:
else:
for st in (matching states in start column of state):

# column 0

So, when it processes item (3) <A>:= |(0,0) in column[0] for completing, it finds both item (1) which obeys the restriction for a single item with dot before <A> and the corresponding item (4) with dot after. Hence, it considers (4) on the deterministic path. This does not change anything for column[0]. However, things change for column[1].

# column 1

When it processes (6) for completing, it again finds (1) and item (4), and hence (4) is considered a parent in the deterministic path. Hence, it saves a copy (4) to the column[1] rather than completing it traditionally in earley. This means that the item (8) <A>:= <A> | a(0,1) from the original Earley parse never gets created, which means no item for accepting the next a in column[2] (which should have been added to column[2] by scanning of this item), and the parsing fails.

So, my understanding of deterministic reduction bye Leo is somehow faulty. Where have I gone wrong?

I have read up on all materials I could get on Leo's optimization, but still unclear what I have missed. I think the item (4) should not be a parent because it is not a previous instance of the recursive rule in item (6). However, nothing in Leo's paper seems to explain how I can exclude such instances from the deterministic path.

If it helps, the complete self contained implementation is here.