Re: Earley parser bugs?

Sylvain Schmitz <>
Thu, 26 Jul 2007 16:55:18 +0200

          From comp.compilers

Related articles
Earley parser (2005-05-03)
Earley parser bugs? (Daniel Zingaro) (2007-07-25)
Re: Earley parser bugs? (Sylvain Schmitz) (2007-07-26)
| List of all articles for this month |

From: Sylvain Schmitz <>
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

        S -> S S | a

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

Hope that helps,


Post a followup to this message

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