Talk:GLR parser

Untitled

GLR is pretty hard to sum-up. In the end, the "scanner" form should be described first, then the parse-forest can be described.

Presumably a little disambiguation is needed - GLR appears to be used both to refer to "infinite lookahead LR" (as in the grammar classification) but also to a specific algorithm for parsing such grammars. Perhaps the main GLR article can consider the grammar classification, and a subsection could consider algorithms?

no, infinite (actually unbounded) lookahead would be something different... GLR is an algorithm, not a grammar classification. "Context Free" is the grammar classification that corresponds to the GLR algorithm. Megacz 16:13, 14 August 2007 (UTC)

History and bibliography

Did you have a look at the following paper? Deterministic techniques for efficient non-deterministic parsers, Bernard Lang, Automata, Languages and Programming, 2nd Colloquium, University of Saarbrücken July 29–August 2, 1974. The abstract reads:

A general study of parallel non-deterministic parsing and translation à la Earley is developped formally, based on non-deterministic pushdown acceptor-transducers. Several results (complexity and efficiency) are established, some new and other previously proved only in special cases. As an application, we show that for every family of deterministic context-free pushdown parsers (e.g. precedence, LR(k), LL(k), ...) there is a family of general context-free parallel parsers that have the same efficiency in most practical cases (e.g. analysis of programming languages)

The paper contains all the known complexity results for these parsers GLR, GLL,... as well as optimization techniques. And it works in cubic time for any CF grammar. Teetooan (talk) 23:05, 25 February 2014 (UTC)

---

The date of Tamita paper publication is correct ? For me is 1984 and 1985. --Hentz (talk) 21:22, 16 October 2008 (UTC)

GLR and Earley worst-case complexity

It's probably worth noting that neither GLR nor Earley are $O(n^{3})$ in the worst case. There are pathological grammars which can trigger $O(n^{4})$ behavior in GLR and potentially-worse complexity in Earley. For example:

S ::= 'b'
    | S S
    | S S S

There are extensions of the GLR algorithm which can handle any CFG (including the above) in $O(n^{3})$ time, but they are really distinct algorithms (RIGLR, GLL, etc) rather than simply incremental improvements upon GLR. Daniel Spiewak (talk) 20:14, 12 May 2009 (UTC)

This is true for original GLR (Tomita) where the exponent is proportional to the RHS of the rules. But I can't see how this is true for Earley. I found only one place that mentions this exact grammar and exactly the same claim, but it doesn't do the analysis either. Can you explain your claim? bungalo (talk) 08:44, 21 May 2011 (UTC)

---

Is this paper an early version of the same algorithm? http://portal.acm.org/citation.cfm?id=363217&dl=GUIDE&coll=GUIDE&CFID=37572854&CFTOKEN=66268815 —Preceding unsigned comment added by Gtoal (talk • contribs) 15:51, 2 June 2009 (UTC)

I think what's missing here is some content on the complexity of the problem, as distinct from the algorithm, that gives us a bit more of the foundation on the article that we need. Ideally of course we should have this content in the parsing article - I'm happy to take this on, if nobody has any objections, then we can come back and fill out this section a bit more. As a temporary measure though I think we take away the incorrect complexity stuff - I'm happy to put some stopgap stuff in there if nobody objects in the next few days? 152.105.134.199 (talk) 15:34, 3 June 2011 (UTC) Turns out I hadn't logged in. FoughtKnox (talk) 15:35, 3 June 2011 (UTC)