11 Oct 2009 22:35:04 +0200

Related articles |
---|

earley parser completion (newbie question) marc.daya@gmail.com (sinistral) (2009-10-11) |

Re: earley parser completion (newbie question) cdodd@acm.org (Chris Dodd) (2009-10-11) |

From: | Chris Dodd <cdodd@acm.org> |

Newsgroups: | comp.compilers |

Date: | 11 Oct 2009 22:35:04 +0200 |

Organization: | X-Privat.Org NNTP Server - http://www.x-privat.org |

References: | 09-10-013 |

Keywords: | parse |

Posted-Date: | 12 Oct 2009 23:54:50 EDT |

[posted and mailed]

sinistral <marc.daya@gmail.com> 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:*

*>*

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.