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:
        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.


I found the problem: Essentially, I misunderstood the definition. It says that

it is [B→αA.,k] with [B→α.A,k] being the only item in Ii with the dot in front of A, or if it is on the deterministic reduction path above [B→αA.,k].

Which should be interpreted as [B→αA.,k] should be considered to be created corresponding to [B→α.A,k]. The basic idea which seems to be elided in Leo's paper but given in Grune et al. (2008) is that, the deterministic reduction is basically simply an eager completion with all intermediate results thrown away. With this change, the parser works correctly.

(The "Parsing Techniques A Practical Guide" by Grune et al. from 2008 is the book I refer to here.)

  • $\begingroup$ Grune et al. (2008) it not a sufficient citation, Grune published many things that year. What is the paper title? $\endgroup$ – orlp Feb 6 at 19:54
  • $\begingroup$ @orlp I have added the title and a link. $\endgroup$ – rahul Feb 8 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.