Re: Comparative studies of Generalized LR and LL parsing?

daw@mozart.cs.berkeley.edu (David Wagner)
6 Oct 2003 21:23:19 -0400

          From comp.compilers
Related articles
Comparative studies of Generalized LR and LL parsing? noemails@replyToTheGroup.nospam.org (Kunle Odutola) (2003-10-04)
Re: Comparative studies of Generalized LR and LL parsing? daw@mozart.cs.berkeley.edu (2003-10-06)
Re: Comparative studies of Generalized LR and LL parsing? haberg@matematik.su.se (2003-10-06)
Re: Comparative studies of Generalized LR and LL parsing? cfc@world.std.com (Chris F Clark) (2003-10-06)
Re: Comparative studies of Generalized LR and LL parsing? oliver@zeigermann.de (Oliver Zeigermann) (2003-10-27)
| List of all articles for this month |
From: daw@mozart.cs.berkeley.edu (David Wagner)
Newsgroups: comp.compilers
Date: 6 Oct 2003 21:23:19 -0400
Organization: University of California, Berkeley
References: 03-10-016
Keywords: parse, theory
Posted-Date: 06 Oct 2003 21:23:19 EDT

Kunle Odutola wrote:
>There has been a steady increase in the numbers of references to (and
>implementations of) "Generalized LR" or GLR parsing but virtually none
>for "Generalized LL" or GLL parsing. I'm left wondering if this is
>just a reflection of the original decision to bundle YACC with Unix.


Most of the algorithms for GLR parsing are really algorithms for
generalized recognition of context free languages given any
(non-deterministic) pushdown automata for the language. So, yes, the
methods all extend naturally to GLL parsing as well.


For instance, Tomita parsing is really a method for efficiently
testing, given a string S and a non-deterministic pushdown automaton
P, whether P accepts S. Most of the examples of Tomita's method
assume that P is constructed as a LR(1) automaton, but there is no
reason this has to be the case.

Post a followup to this message

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