Talk:Earley parser

The article says that rules like

   a -> a b

will cause both top-down and bottom-up parsers to go into an infinite loop, but I thought it was only top-down parsers that had a problem with left-recursion. Any comments? — Cadr

Since no-one's commented, I'll go ahead and change the page... — Cadr

It's not exactly true, top down parsers like LL(1) will enter in a infinite loop, but other top-down parsers, indeterministic LL, (and I think some kind of top-down parser that uses breadth-first search also) will eventually finish.

Works on all CFGs?

http://pages.cpsc.ucalgary.ca/~aycock/spark/doc.html seems to suggest that "[...] should work with any Backus-Naur form (BNF) grammar, including grammars with empty right-hand sides and ambiguous grammars. There are apparently a few rather obscure cases where Earley's parsing algorithm fails, but they're not likely to crop up in any reasonable application."

NP-complete?

Parsing Unrestricted languages is not NP-complete, it is much harder.

It can be easily shown (simulation of Turing machines by grammars gives an immediate reduction of the halting problem to parsing of general languages) that the problem is not computable.

Unless anybody objects, I'll correct it.

--UrsusArctos 22:37, 19 Oct 2004 (UTC)

Be careful with the meaning of the word "parse", though. You could argue that you don't have to be able to decide a language in order to parse it, and consequently even unrestricted languages would be "parseable" in a sense, i.e. the sense that if there was a parse, you would get it eventually. I'm not sure there's any general agreement on whether this would count as "parsing" or not, so I think we should word it carefully. Otherwise yeah, the NP-complete thing is incorrect. Cadr 12:15, 20 Oct 2004 (UTC)

Turning the recognizer into a parser

Everyone describes Earley's algorithm as a parser, but no-one ever bothers to explain how you turn the recognizer into a parser. My understanding is that you modify the completer to record a backpointer.. but exactly what item gets the backpointer and what it is to point to is still kind of a mystery to me. I believe that the new item you are creating should receive the backpointer and it should point to the item you are copying (to advance the dot in). However this is not sufficient, you also need some mechanism to inherit backpointers, otherwise you end up with a disconnected tree. Can anyone clarify this process?

That would be very useful! Unfortunately, I haven't found any description about that yet... --ThSoft 21:39, 14 September 2006 (UTC)

My understanding is that you generate a certains number of Earley items, which may or may not be part of *a* complete parse. --92.137.198.224 (talk) 11:42, 1 August 2010 (UTC)

Error in the algorithm description?

I believe that:

• Prediction: For every state in S(k) of the form (X → α • Y β, j) (where j is the origin position as above), add (Y → • γ, j+1) to S(k) for every production with Y on the left-hand side.

Should be changed to:

• Prediction: For every state in S(k) of the form (X → α • Y β, j) (where j is the origin position as above), add (Y → • γ, k) to S(k) for every production with Y on the left-hand side.

This is a change of "j+1" to "k". See the example. —Preceding unsigned comment added by 87.116.85.20 (talk) 17:14, 4 December 2007 (UTC)

Unused symbol

Z is defined to represent a single nonterminal. However, it never gets used anywhere for the rest of the page. I believe that its definition should be removed. If nobody objects, I'll correct it. Opaldraggy (talk) 04:09, 14 December 2008 (UTC)

Added Parse::Marpa

I've added Parse::Marpa under External Links. It's a new implementation of a parser based on Earley's algorithm, with the improvements suggested by Aycock and Horspool. I'm the author of this Perl module, but I believe this edit is in compliance with WP:COS. --Jeffreykegler (talk) 01:58, 11 January 2009 (UTC)

Propose tidy of eternal links

I'd like to remove the subsections from external links section, so it would look the example below, any objections? This would be to make it concise and to avoid repeating information.

External links

• 'early' An Earley parser C -library.
• 'C Earley Parser' An Earley parser C.
• PEN A Java library that implements the Earley.
• Pep A Java library that implements the Earley algorithm and provides charts and parse trees as parsing artifacts.
• [1] A Java implementation of Earley parser.
• Marpa and Marpa::XS, Perl modules, incorporating improvements made to the Earley algorithm by Joop Leo, and by Aycock and Horspool.
• Parse::Earley An Perl module that implements Jay Earley's original algorithm.
• Charty a Python implementation of an Earley parser.
• NLTK a Python toolkit that has an Earley parser.
• Spark an Object Oriented "little language framework" for Python that implements an Earley parser.
• CL-EARLEY-PARSER A Common Lisp library that implements an Earley parser.
• Charty-Racket A Scheme / Racket implementation of an Earley parser.

Architectual (talk) 12:52, 27 October 2011 (UTC)

In the current organization you can see at a glance which language each is in. Unfortunately, that's often even more important than the quality of the implementation. Most users won't or can't consider an implementation that's not on their (often very short) list of preferred languages. --Jeffreykegler (talk) 15:16, 27 October 2011 (UTC)