Re: earley parser completion (newbie question)

Chris Dodd <>
11 Oct 2009 22:35:04 +0200

          From comp.compilers

Related articles
earley parser completion (newbie question) (sinistral) (2009-10-11)
Re: earley parser completion (newbie question) (Chris Dodd) (2009-10-11)
| List of all articles for this month |

From: Chris Dodd <>
Newsgroups: comp.compilers
Date: 11 Oct 2009 22:35:04 +0200
Organization: X-Privat.Org NNTP Server -
References: 09-10-013
Keywords: parse
Posted-Date: 12 Oct 2009 23:54:50 EDT

[posted and mailed]

sinistral <> wrote in news:09-10-013@comp.compilers:
> I've been trying to understand the workings of the Earley algorithm
> and I'm having trouble with the example presented on Wikipedia:
> What I don't understand in this example is why state set S(3) doesn't
> include the state
> S -> M dot # complete from S(0)(3)
> Since we have a completion for the non-terminal M, wouldn't this be a
> valid completion?

The rule in S(3) we're completing M with is 'M -> T \dot (2)', so we only
look at S(2) for states with the \dot just before an 'M', per the completion
rule. Since 'S -> \dot M' is only in S(0) and not S(2), it's not a valid
completion. The only rules in S(2) with \dot M are 'S -> S + \dot M' and
'M -> \dot M * T', so that's all that we complete with M.

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.