Re: Earley parser bugs?

Sylvain Schmitz <schmitz@i3s.unice.fr>
Thu, 26 Jul 2007 16:55:18 +0200

          From comp.compilers
Related articles
Earley parser mefrill@yandex.ru (2005-05-03)
Earley parser bugs? zingard@mcmaster.ca (Daniel Zingaro) (2007-07-25)
Re: Earley parser bugs? schmitz@i3s.unice.fr (Sylvain Schmitz) (2007-07-26)
| List of all articles for this month |
From: Sylvain Schmitz <schmitz@i3s.unice.fr>
Newsgroups: comp.compilers
Date: Thu, 26 Jul 2007 16:55:18 +0200
Organization: Compilers Central
References: 05-05-017 07-07-087
Keywords: parse, errors
Posted-Date: 26 Jul 2007 12:21:06 EDT

Daniel Zingaro wrote:
> I pulled the following message from the website text search. I find it
> hard to follow the example in the message though, and wonder if anyone
> can further explain why Earley's parsing extension to his recognizer
> algorithm given in his Ph.D. thesis does not correctly build parse
> trees. Any examples or references to papers would be appreciated. Thanks.


Elizabeth Scott presented a paper on the subject at LDTA'07: _SPPF-Style
Parsing From Earley Recognisers_, to appear in ENTCS. An example of
incorrect Earley parsing given there (and originally from Tomita) is the
grammar


        S -> S S | a


with input "aaa", for which Earley's parsing procedure allows spurious
derivations for "aaaa" and "aa".


--
Hope that helps,


      Sylvain


Post a followup to this message

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