earley parser completion (newbie question)...

Main Page | Report this Page

Computers Forum Index » Computer Compilers » earley parser completion (newbie question)...

Page 1 of 1

earley parser completion (newbie question)...

Author

Message

sinistral...

Posted: Sun Oct 11, 2009 4:48 pm

Guest

Greetings

I've been trying to understand the workings of the Earley algorithm
and I'm having trouble with the example presented on Wikipedia:

http://en.wikipedia.org/wiki/Earley_parser

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?

Any pointers as to what I'm missing would be greatly appreciated.
..marc

Chris Dodd...

Posted: Mon Oct 12, 2009 12:35 am

Guest

[posted and mailed]

sinistral <marc.daya at (no spam) gmail.com> wrote in news:09-10-013 at (no spam) comp.compilers:

Quote:

I've been trying to understand the workings of the Earley algorithm
and I'm having trouble with the example presented on Wikipedia:

http://en.wikipedia.org/wiki/Earley_parser

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.

Page 1 of 1

All times are GMT The time now is Sat Nov 28, 2009 2:46 pm Computers Forum Index