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): column.add(state.advance())
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
<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 <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 <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 <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: column.add(detred) else: for st in (matching states in start column of state): column.add(st.advance())
So, when it processes item (3)
<A>:= |(0,0) in
column 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. However, things change for column.
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 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 (which should have been added to column 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.